聚类分析中K-means算法综述(DOC)

1攻读硕士学位研究生试卷（作业）封面（2015至2016学年度第一学期）题目论文选读科目聚类分析中K-means算法综述姓名王苑茹专业计算机技术入学年月2015年8月简短评语成绩：授课教师签字：2聚类分析中K-means算法综述摘要:聚类分析是数据挖掘中一个极其重要的研究方向，是一个将数据划分成簇的方法或手段。聚类分析可广泛利用在商务智能，Web搜索，生物学以及图像模式识别等众多方面。本文主要叙述聚类分析中的K-means聚类算法，总结了K-means聚类算法的研究现状，并针对K-means算法的相关改进做了综述。关键词：K-means聚类算法；数据子集；聚类中心；相似性度量和距离矩阵OverviewofK-meansalgorithminclusteringanalysisAbstract:Clusteringismajorfieldindataminingwhichalsoisanimportantmethodofdatapartitionorgrouping.Clusteringnowhasbeenappliedintovariouswaysinbusinessintelligence,Webclassification,biology,marketandsoon.Inthispaper,weintroducethespatialclusteringrules,Atthesametime,theclassicalK-meansalgorithmisdescribe,AndsomerelatedimprovementstoK-meansalgorithmaresummarized.Keywords:K-meansclusteringalgorithm;numberofclustersK;clusterinitialization;distancemetric31、引言K-means聚类算法是1955年由Steinhaus、1957年Lloyed、1965年Ball&Hall、1967年McQueen分别在他们各自研究的不同的科学领域独立提出的。空间聚类分析方法是空间数据挖掘理论中一个重要的领域，是从海量数据中发现知识的一个重要手段。k-means算法是空间聚类算法中应用非常广泛的算法，同时它也在聚类分析中起着重要作用。日益丰富的空间和非空间数据收集存储于空间数据库中，随着空间数据的不断膨胀，海量的空间数据的大小、复杂性都在快速增长，远远超出了人们的解译能力，从这些空间数据中发现邻域知识迫切需求产生一个多学科、多邻域综合交叉的新兴研究邻域，空间数据挖掘技术应运而生。虽然k-means聚类算法被提出已经快60年了，但是目前仍然是应用最为广泛的划分聚类算法之一]1[。容易实施、简单、高效、成功的应用案例和经验是其仍然流行的主要原因。本文主要叙述聚类分析中的K-means聚类算法，总结了K-means聚类算法的研究现状，并针对K-means算法的相关改进做了综述。2、经典K-means算法2.1K-means算法k-means聚类算法是一种基于形心的划分技术，是数据挖掘领域最为常用的聚类方法之一，最初起源于信号处理领域。它的目标是划分整个样本空间为若干个子空间，每个子空间中的样本点距离该空间中心点平均距离最小。因此，k-means是划分聚类的一种。k-means算法接受输入量k；然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。大体上说，k-means算法的工作过程说明如下：首先从n个数据对象任意选择k个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度，分别将它们分配给与其最相似的聚类；然后再计算每个所获新聚类的聚类中心；不断重复这一过程直到标准测度函数开始收敛为止。一般都采4用均方差作为标准测度函数。k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。假设数据集D包含n个欧氏空间中的对象。划分方法把D中的对象分配到K个簇jCC,...,1中，使得对象1≦i，j≤k,iCD且iCjC=Ø，一个目标函数用来评估划分的质量，使得簇内对象相互相似，而与其他簇中的对象相异。也就是说，该目标函数以簇内高相似性和簇间低相似性为目标。基于形心的划分iC技术使用簇的形心代表该簇。对象siC与该簇的代表ic之差用dist（s，ic）度量，其中dist（x，y）=sqrt(∑(21iiyx)^2)这里i=1,2..n。簇iC的质量可以用簇内变差度量，它是iC中所有对象和形心ic之间的误差的平方和，α=21),(icpkicsdisti（1）其中，α是数据集中所有对象的误差的平方和；s是空间中的点，表示给定的数据对象；ic是簇iC的形心]2[。2.2k-means算法流程k-means算法流程，首先，随机的选择k个对象，每个对象初始地代表了一个聚类的平均值或中心，对剩下的各个对象，根据其与每个聚类中心的欧氏距离，将它派发给最相似的聚类。之后，应用更新之后的均值作为新的聚类中心，再重新分配全部对象。继续迭代，一直到分配趋于稳定，也就是本轮迭代所形成聚类与前一轮形成的聚类相同。3、K-means聚类算法的参数及其改进k-means聚类算法需要用户指定3个参数：类别个数K，初始聚类中心、相似性和距离度量。针对这3个参数，k-means聚类算法出现了不同的改进和变种。3.1基于K值的改进在k-means算法中k是事先给定的，这个k值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是k-means算法的一个不足。有的算法是通过类的自动合并和分裂，得到较为合理的类型数目K，例如ISODATA算法。1)解决方法-聚类有效性函数5根据聚类有效性函数的方法是非常简单的一种解决方法，从［2，N］的区间内逐一选取k值，并利用该函数评价聚类的效果，最终得到最优的k值。中外有许多学者也是按照这种思想提出了一系列的解决方法。李永森等]3[提出的距离代价函数综合了类际距离和类内距离两项距离函数，类际距离为所有聚类中心到全域数据中心的距离之和。类内距离即所有类中对象到其聚类中心的距离之和。作者证明了当距离代价函数达到最小值时，空间聚类结果为最优，此时对应的k值为最佳聚类数。杨善林]4[提出的距离代价函数作为空间聚类的有效性检验函数,就是当距离代价函数达到最小值时侯,以距离代价最小准则实现了k值优化算法，空间聚类结果为最优.根据经验规则计算和确定最优解的上界,给出了求k值最优解kopt及其上界kmax的条件,并在理论上证明了经验规则kmax≤n的合理性.吴艳文等]5[提出的通过提供相对较易得到的k初值(大于kopt),得k个初始聚类。分析聚类之间相互关系,判断那些聚类应是同一类,从而得到对k值的优化。王朔等]6[提出基于非模糊型集群评估指标（DBI）的概念。该指标主要利用几何原理进行运算，分别以聚类间离散程度及位于同一类内数据对象的紧密程度为依据。即不同聚类间的相异性高而同一类内数据对象的相似性高，并以此来进行聚类结果的评估。当类内各数据对象间距离越小而类间距离越大时指标值则越小，代表各聚类内的数据对象越紧密且聚类间的差异大。指标值越小，表明此聚类数目下聚类结果越佳。DBI值越小代表各聚类内数据相似度越大而类间的相似度越小，由此得到最佳聚类数目。2）解决方案-遗传算法Bandyopadhyay等]7[提出了GCUK算法是基于遗传算法的。此算法的染色体是运用字符串方式来编码的，也就是将每个初始的聚类中心坐标按照顺序来进行编码，符号“#”来表示没有作为初始聚类中心的数据点，编码完成以后在逐代交叉运算中最后得到了最优k值。张月琴等]8[提出了优化值参数是基于遗传算法的。在遗传算法中,通过编码来实现染色体。依据k-means算法要找到最佳的k值,染色体的编码既是对k值的编码。在一般情况下，对于某类问题,总是有一聚类的最大类数MaxClassnum,这个值即可由用户来进行输入，也可以是给定的聚类样本个数。k是介于1和MaxClassnum之间的整数，可以使用二进制串既染色体来表示。6胡彧等]9[提出了由遗传操作中的变异操作来控制k值的大小。变异操作的本质是挖掘群体中个体的多样性，同时提高算法的局部随机搜索能力，防止出现未成熟收敛通过对个体适应度函数的求解，决定聚类数k值的变化方向。由于最初所给的聚类数k值并非是最佳聚类数，因此将最初所给种群中具有最大适应度值的个体做为最佳聚类数的榜样个体，其它个体的长度(即k值)向榜样个体的长度靠扰。3）其他方法孙雪等]10[提出了一种基于半监督k-means的k值全局寻优算法。设初始少量数据集带标记的为监督信息,数据集无标记的,监督信息数据集的标记为i和j.设k=2为初值,在完整的数据集上来进行constrained-k-means聚类.当k取不同值时,计算监督信息中被错误标记的数据总数N，公式如下：kcjcicnnN1),min(（1）其中c表示聚类后各簇的标号;icn,jcn表示在第c簇中标记的数据所占的比例为i,j.出现空簇的频率取决于K值上限,当出现空簇的频率大于50%时,则此时k被认为已取得最大值.在k值优化的整个过程中,如果某一簇内的监督信息满足以下条件,即jcicjcicnnnn),max(阈值（2）则该次聚类结果被认为是无效,保留有效的簇中心值,再开始新一轮聚类,在中心点选择上采取了半增量的迭代方式,提高了算法性能。上式阈值选取可采取重复实验的方法,一般当icn与jcn的数量相差较少时,类标记为c的簇就为无效的簇.使N取得最小值的k取值就为k-means聚类算法的最佳初值。田森平等]10[提出了根据所需聚类数据的分布的属性，来计算他们间的距离，经过这一系列变换，得到最终的聚类参数k值。从需要聚类的数据之中抽取出一部分样本数据，来获取聚类参数的抽样数据；再计算抽样数据间的距离来得到一沿对角线对称的距离矩阵，从这一距离矩阵之中找出一个大于零的最小距离即为mind(jixx,),作为高密度半径和簇划分半径的一个项，来保证这两个半径不会太小；对距离矩阵按列求平均值，再对这些平均值求iR求平均值得到R，根据|RRi|/R的误差来去掉噪声点，在噪声点去除完全后，重新计算R，根据R和mind(jixx,),求得了高密度半径R。再找出miniR，依据,d(jixx,)miniR7的关系来得到高密度个数的参数Z；最终根据R和mind(jixx,),获得簇划分的半径r，合并簇的中心点之间距离m，合并簇的边界点之间距离h。综上所述的研究可发现，学术界已经提出了许多种K值的选取方法，并且分别基于不同的解决方法。3.2初始聚类中心的选择k-means算法是贪心算法，在多项式时间内，只能得到局部最优。初始聚类中心的选择是随机选取的，不同的初始聚类中心选取方法得到的最终局部最优结果也不同。所以可能造成在同一类别的样本被强制当作两个类的初始聚类中心，使得聚类结果最终只能收敛于局部最优解，k-means算法的聚类效果在很大的程度上依赖于初始聚类中心的选择，因此，大量的初始聚类中心选取方案被提出。袁方等]11[提出了基于密度的优化初始聚类中心的方法，找到一组能反映数据分布特征的数据对象作为初始聚类中心首先计算数据对象ix所处区域的密度，来定义一个密度参数：以ix为中心，包含了常数Minpts个数据对象的半径称为对象ix的密度参数，用ε表示。ε越大，则说明数据对象所处区域的数据密度就越低。反之，ε越小，说明数据对象所处区域的数据密度越高。通过计算每个数据对象的密度参数，就可以发现处于高密度区域的点，从而得到一个高密度点集合D。在D中取处于最高密度区域的数据对象作为第1个聚类中心z1；取距离z1最远的一个高密度点作第2个聚类中心z2；计算D中各数据对象ix到z1,z2的距离d(ix,z1)，d(ix,z