基于K_means聚类算法的研究

西南民族大学学报·自然科学版JournalofSouthwestUniversityforNationalitiesNaturalScienceEdition第35卷第1期Jan.2009___________________________________________________________________文章编号:1003-2843(2009)01-0198-03基于K-means聚类算法的研究步媛媛1,关忠仁2(1.成都信息工程学院计算机系,四川成都610225;2.成都信息工程学院网络中心,四川成都610225)摘要:原始的k-means算法[4]是从样本点的集合中随机选取K个中心,这种选取具有盲目性和随意性,它在很大程度上决定了算法的有效性.为消除选取初始中心的盲目性,应充分利用已有数据样本点的信息.采取对数据进行预处理的方式来选取初始中心.实验证明新的初始点的选取不仅提高了算法的计算效率,也提高了算法最终确定的聚类的精度.关键词:数据挖掘;聚类;k-means算法;聚类中心中图分类号:TP392文献标识码:A1引言聚类分析是数据挖掘中的一个重要功能,目前已应用于许多方面:数据挖掘和知识发现、模式识别和模式分类、数据压缩和向量量化.关于聚类分析有很多种方法,这些方法包括分割与合并方法、随机化方法和神经网络方法.其中在欧氏空间中的k-means聚类算法是最流行和最受关注的一种聚类分析算法.k-means是一种基于划分的聚类算法,它的思想是当一个类确定后,将类中数据点的几何平均值取为类的中心.其中初始聚类中心的选择对聚类结果的影响是很大的.如图所示,图1是三个类的实际分布,图2是选取了较好的初始聚类中心(+字标记的数据对象是聚类中心)得到的结果,图3是选取不大好的初始聚类中心得到的结果.从中可以看到,图2所示的类内部数据对象相似度和类与类之间的相异度均高于图3所示,最主要的体现是数据分布稠密.因此合理地选择初始聚类中心是很关键的.类似图3所示之类的选取聚类中心的k-means算法的结果会导致聚类算法效率低,算法迭代次数较多,CPU运行时间较长.因此怎样找到一组初始中心点,从而获得一个较好的聚类效果并提高聚类结果的精确度对k-means算法具有重要意义.图1三个类的实际分布图2选取了较好中心的聚类结果图3选取不好聚类中心的结果本文提出了一种寻找初始聚类中心的方法,使得初始聚类中心的分布尽可能体现数据的实际分布.实验表明了这种算法的可行性和有效性.2原始的k-means聚类算法[4]及改进的算法分析2.1原始k-means聚类算法___________________________收稿日期：2008-10-13作者简介：步媛媛(1984-),女,成都信息工程学院计算机系在读硕士研究生;关忠仕(1957-),男,成都信息工程学院网络中心高级工程师,硕士生导师._第__1_期____________________步媛媛等:基于K-means聚类算法__________________的研__究_____________________199__设待聚类的数据集:X=x1,x2,L,xn,k个聚类中心分别为zi,i=1,2,....n.有如下定义:定义1:两个数据对象间的欧几里德距离为d(i,j)=|xi1xj1||xi2xj2|L|xipxjp|222这里的i=(xi1,xi2,L,xip)和j=(xj1,xj2,L,xjp)是两个p维的数据对象.定义2:准则函数Ek|pmi|2E=i1pCI这里的E是数据库中所有对象的平方误差的总和,p是空间中的点,表示给定的数据对象,mi是簇Ci的平均值.这个准则试图使生成的结果簇尽可能地紧凑和独立.算法主要有三个过程组成:首先是选取初始的聚类中心;其次是样本点分类;最后是聚类中心的调整.其中后两个过程迭代交替进行.下面是k-means算法的流程描述:输入:簇的数目k和包含n个对象的数据库.输出:k个簇,使平方误差准则最小.方法:Step1Step2Step3Step4Step5任意选择k个对象作为初始的簇中心;repeat根据簇中对象的平均值,将每个对象重新赋给最类似的簇;更新簇的平均值,即计算每个簇中对象的平均值;until不再发生变化原始的k-means算法对初始聚类中心的选择是随意的和盲目的,这种选取方法很大程度上决定了算法的有效性和精确度.因此对初始中心的选择进行改进既很有意义也很有必要.本文的主要目的就是在欧几里德距离的意义下,确定相隔最远的两个数据点之间的距离,然后将数据集均分为k个段,在每段内取一个中心作为初始的中心.也就是改进上述算法中的step1.2.2改进的k-means聚类算法定义1:数据集中相隔最远的两个数据点之间的距离MM=max{d(i,j)}定义2:d=M/k定义3:假设一参照点为o,数据集中与点o之间的距离最大的点记为数据集中的大者mi,i=1,2,…,(k-1).Step1Step2Step3计算任意两个数据对象间的距离d(xi,xj),比较得出M.计算d;X1X;求出点m1;C1={X1中与点m1的距离小于d的点Um};1Step4X2=X-C1;求出点m2;C2={X2中与点m2的距离小于d的点Um};2……Step5Xk1=X-Ck2;求出点mk1;Ck1={Xk1中与点mk1的距离小于点d的点Umk1};UULCk1Step6CK=X-(C1UC2);xj,i=1,2,…,k.xjCIStep7计算中心zi=|C1I|Step8从这k个聚类中心出发,应用k-means聚类算法的步Step2,Step3,Step4,Step5,得到聚类.2.3两种算法的比较分析2.3.1简单例子证明为了说明改进的k-means聚类算法与原始的k-means聚类算法的不同,举一简单例子进行分析比较._2_0_0_____________________西__南_民_族__大_学__学_报_·_自__然_科__学_版____________________第__35_卷__例设有一数据样本集合为X={1,5,10,9,26,32,16,21,14},将X聚为3类,即k=3.分别用两种算法来执行.(1)原始的k-means聚类算法如表1所示:表1原始的k-means聚类算法步1234z111113z25589.512.3z31018.321.823.826.3C1{1}{1}{1}{1,5}{1,5}C2{5}C3E{10,9,26,32,16,21,14}{26,32,16,21,14}{26,32,16,21}{26,32,21}433.43230.8185.7293.4393.43{5,10,9}{5,10,9,14}{10,9,14,16}{10,9,14,16}5{26,32,21}共迭代5次.准则函数E一直是减小的.(2)改进的k-means聚类算法如表2所示:表2改进的k-means聚类算法步z1z2z3C2C3EC1129176.25{32,26}{16,14,21}{1,5,9,10}94.75算法迭代次数为1,较传统k-means聚类算法明显减少.聚类精确度较高.2.3.2实验结果接下来对规模较大的数据进行数值实验以进一步说明改进的k-means聚类算法的有效性.从CPU运行时间和迭代次数两个方面对它们的运行结果进行比较,说明改进的算法不仅是有效可行的,而且效率更高.表3是实验结果的数值对照:表3实验结果对照传统算法的传统算法的迭代次数改进算法的改进算法的迭代次数数据维数数据个数聚类个数CPU耗时CPU耗时2040801002001000510400.29s1.972s55.339s712290.23s1.342s33.828s449从表上可以得出结论:改进的算法减少了迭代次数,CPU计算时间也明显减少.3结论k-means聚类算法是一种广泛应用的聚类算法,计算速度快,资源消耗少.但是初始聚类中心选择的随机性决定了算法的有效性和聚类的精度.本文提出了一种充分利用数据样本集的信息,对数据进行预处理,得出初始聚类中心从而进行聚类.改进的算法为聚类节约了时间,而且聚类变得更加准确.参考文献:[1][2][3][4][5]袁方,周志勇.初始聚类中心优化的k-means算法[J].计算机工程,2007(5):224-227.连凤娜,吴锦林.一种改进的k-means聚类算法[J].电脑与信息技术,2008(4):124-128.徐义峰,陈春明.一种改进的k均值聚类算法[J].计算机应用与软件,2008(1):27-31.JIAWEIHAN,MICHELINEKAMBER.数据挖掘概念与技术[M].范明,孟小峰,译.北京:机械工业出版社,2007.袁玉波,杨传胜.数据挖掘与最优化技术及其应用[M].北京:科学出版社,2007.ResearchofclusteringalgorithmbasedonK-meansBUYuan-yuan,GUANZhong-ren12(1.DepartmentofComputerSciences,ChengduInstituteofInformationEngineering,Chengdu610041,P.R.C.;2.InternetManagementCenter,ChengduInstituteofInformationEngineering,Chengdu610041,P.R.C.)Abstract:Originalk-meansclusteringalgorithmisthemeansthatselectsKcentersrandomlyfromthedatasamplecluster.Thisselectionisblindandrandom,andtoacertainextentthevalidityofalgorithmliesontheselection.Inordertoavoidtheblindnessofselection,weshouldmakefulluseoftheinformationofexistingdatasampledot.Wemakepre-treatmentofthedatatochoosetheinitialcenter.Theexperimentimprovesnotonlythecalculationefficiencyofalgorithm,butalsotheprecisionofultimateclustering.Keywords:datamining;clustering;K-means;clusteringcenter