资源描述：
《基于k_means聚类算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第35卷第1期文章编号：1003-2843(2009)01-0198-03基于K-means聚类算法的研究步媛媛1,关忠仁2(1.成都信息工程学院计算机系，卩4川成都610225;2.成都信息工程学院网络中心，P461O娜)摘要:原始的k-means算法［4］是从样本点的集合中随机选取K个中心，这种选取具有盲目性和随意性，它'在很大程度上决定了算法的有效性.为消除选取初始中心的盲目性，应充分利川已有数椐样本点的信息.采取对数据进行预处理的方式來选取初始屮心.实验证明新的初始点的选取不仅提高了算法的计算效率，也提商了算法
2、诚终确定的聚类的精度.关键词:数裾挖掘；聚类；k-means算法；聚类中心屮图分类号:TP392文献标识码：A1引言聚类分析是数据挖掘中的一个重要功能，H前已应用于许多方而：数裾挖掘和知识发现、模式识别和模式类、数据灰缩和M景景化.关于聚类分析有很多种方法，这些方法包括分割与合并方法、随机化方法和神经网络方法.K中在欧氏空间中的k-means聚类算法是敁流行和蛣受关注的一种聚类分析算法.k-means是一种葙于划分的聚类算法，它的思想是当一个类确定后，将类中数裾点的儿柯平均值取为类的屮心.其中初始聚类屮心的选择对聚类结
3、果的影响是很人的.如图所示，图1是三个类的实际分布，图2取了较好的初始聚类中心(+字标记的数据对象足聚类中心)得到的结果，阁3是选取不大好的初始聚类中心得到的结果.从屮可以看到，图2所示的类内部数据对象相似度和类与类之间的相异度均髙于图3所示，最主要的体现足数据分布稠密.因此合理地选择初始聚类中心是很关键的.类似图3所示之类的选収聚类中心的k-means算法的结果会导致聚类算法效率低，算法迭代次数较多，CPU运行吋间较长.因此怎样找到一组初始中心点，从而获得图1三个类的实际分布图2选取了较好中心的聚类结來图3选取不好聚
4、类中心的结來木文提出了一种寻找初始聚类屮心的方法，使得初始聚类屮心的分布从可能体现数据的实际分布.实验表明了这种算法的可行性和有效性2原始的k-means聚类算法［4］及改进的算法分析2.1原始k-means聚炎算法收稿日期：2008-10-13作者简介：步媛媛(1984-)，女，成都信息工程学院计算机系在读硕士研究虫;关忠什(1957-),男，成都信息工程学院网络屮心商级工程师，硕士生导师.—笫_1一期步媛媛等:基于K-means聚类算法的研_究199设待衆类的数掂集：X=x?,X2,E^(n,k个聚类中心分别为Zi
5、，i=1,2，....n.有如下定义：定义1:两个数据对象间的欧几里徳距离为d@jXFiIXji
6、
7、Xi2:Xj2!L
8、xUxjP这里的i=(Xii，Xi2，L,XiP)#j=(xji，xj2,L,xjP)是［^个p维的数裾对象.定义2:准则函数E222E=^l◄
9、pimi
10、2i1pCQ这里的E足数据库屮所奋对象的平方误差的总和，P足空间屮的点，表示给定的数据对象，m足簇G的平均值.这个准则试图使生成的结果簇尽可能地紧凑和独立.算法主要冇三个过程组成：首先是选取初始的聚类中心；其次是样木点分类;；是聚类中心的调整.其屮
11、后两个过程迭代交替进行.卜‘面足k-means算法的流程描述：输入：簇的数0k和包含n个对象的数据库.输出：k个簇，使平方误差准则最小.方法：Stepl任意选择k个对象作为初始的簇中心Step2repeatStep3根裾簇中对象的平均值，将每个对象重新赋给敁类似的簇：Step4更新簇的平均值，即计算每个簇屮对象的平均值；Step5until不再发生变化原始的k-means算法对初始聚类屮心的选择是随意的和盲H的，这种选取方法很人程度上决定了算法的旮效性和精确度.因此对初始屮心的选择进行改进既很有意义也很有必耍.本文的主
12、耍n的就是在欧几里徳距离的意义卜，确定相隔最远的两个数据点之间的距离，然后将数据集均分为k个段，在每段内取一个屮心作为的中心.也就是改进上述算法中的stepl.2.2改进的k-means聚炎算法定义1:数据集中相隔最远的两个数据点之间的距离MM=max{d(i,j)}定义2:d=M/k定义3:假设一参照点为0,数裾集中与点o之间的距离敁大的点记为数裾巢中的大者mi,i=1,2,対ep1计算任意两个数据对象M的距离d(Xi，Xj)，比较得出M.Step2计算d;Step3X1X;求出点mi;Ci={X冲与点mi的距离小于
13、d的点IJm};Step4X2=X-Ci;求出点m2;C2={X2中与点m2的距离小于d的点LJmStep5Xkn=X-Ck:2;求出点mxiiCkH={Xkii巾与点mkii的距离小于点d的点Umk：i};UUStep7计算中心Lq：iStepB达^輝滅totl?龙feterrie’ats聚类算法的步Step2,Step3,St
