K-Means聚类算法

K-means聚类算法综述摘要：空间数据挖掘是当今计算机及GIS研究的热点之一。空间聚类是空间数据挖掘的一个重要功能。K-means聚类算法是空间聚类的重要算法。本综述在介绍了空间聚类规则的基础上，叙述了经典的K-means算法，并总结了一些针对K-means算法的改进。关键词：空间数据挖掘，空间聚类，K-means，K值1、引言现代社会是一个信息社会，空间信息已经与人们的生活已经密不可分。日益丰富的空间和非空间数据收集存储于空间数据库中，随着空间数据的不断膨胀，海量的空间数据的大小、复杂性都在快速增长，远远超出了人们的解译能力，从这些空间数据中发现邻域知识迫切需求产生一个多学科、多邻域综合交叉的新兴研究邻域，空间数据挖掘技术应运而生。空间聚类分析方法是空间数据挖掘理论中一个重要的领域，是从海量数据中发现知识的一个重要手段。K-means算法是空间聚类算法中应用广泛的算法，在聚类分析中起着重要作用。2、空间聚类空间聚类是空间数据挖掘的一个重要组成部分。作为数据挖掘的一个功能，空间聚类可以作为一个单独的工具用于获取数据的分布情况，观察每个聚类的特征，关注一个特定的聚类集合以深入分析。空间聚类也可以作为其它算法的预处理步骤，比如分类和特征描述，这些算法将在已发现的聚类上运行。空间聚类规则是把特征相近的空间实体数据划分到不同的组中，组间的差别尽可能大，组内的差别尽可能小。空间聚类规则与分类规则不同，它不顾及已知的类标记，在聚类前并不知道将要划分成几类和什么样的类别，也不知道根据哪些空间区分规则来定义类。（1）因而，在聚类中没有训练或测试数据的概念，这就是将聚类称为是无指导学习（unsupervisedlearning）的原因。（2）在多维空间属性中，框定聚类问题是很方便的。给定m个变量描述的n个数据对象，每个对象可以表示为m维空间中的一个点，这时聚类可以简化为从一组非均匀分布点中确定高密度的点群。在多维空间中搜索潜在的群组则需要首先选择合理的相似性标准。（2）已经提出的空间聚类的方法很多，目前，主要分为以下4种主要的聚类分析方法（3）:①基于划分的方法包括K—平均法、K—中心点法和EM聚类法。它们都是采用一种迭代的重定位技术,尝试通过对象在划分间移动来改进聚类效果。由于这类方法适用于发现大小相近的球状簇,故常用在设施选址等应用中。②基于层次的方法此法只是对对象集合进行分解。根据层次的分解方式,这类方法可分为凝聚和分裂两种,Birch,Cure和Chameleon是上述方法的改进。③基于密度的方法对给定类中的每个数据点,在一个给定范围的区域中必须包含超过某个阈值的数据点,才继续聚类。它可以用来发现任意形状的簇,过滤“噪声”。代表性的方法有:DBscan,Optics和Denclue。④基于栅格的方法把对象空间划为有限的数据单元,形成一个网格结构。该方法处理速度快,处理时间独立于数据对象的数目。常用的方法有STING、WaveCluster以及CLIQUE等。在这些方法中，K-means（k—均值）算法是一种应用十分广泛的聚类分析方法。3、经典的K-Means算法K-means聚类问题的假设是有一组N个数据的集合X={x1，x2，x3，…，xn}待聚类。K均值值聚类问题是要找到X的一个划分Pk={C1，C2，C3，…，Ck}，使目标函数f（Pk）=1(,)iikiiixcdxm最小。其中，mi=1/ni，iiixcx表示第i个簇中心位置，i=1，…，k；ni是簇Ci中数据项的个数；(,)iidxm表示xi到mi的距离。通常的空间聚类算法是建立在各种距离基础上的，如欧几里得距离、曼哈顿距离和明考斯距离等。其中，最常用的是欧几里得距离。（4）K-means算法的基本思想是：给定一个包含n个数据对象的数据库，以及要生成簇的数目k，随机选取k个对象作为初始的k个聚类中心；然后计算剩余各个样本到每一个聚类中心的距离，把该样本归到离它最近的那个聚类中心所在的类，对调整后的新类使用平均值的方法计算新的聚类中心；如果相邻两次的聚类中心没有任何变化，说明样本调整结束且聚类平均误差准则函数已经收敛。本算法在每次迭代中都要考察每个样本的分类是否正确，若不正确，就要调整。在全部样本调整完成后修改聚类中心，进入下一次迭代。如果在一次迭代算法中，所有的样本被正确分类，则不会有调整，聚类中心不会有变化。在算法迭代中值在不断减小，最终收敛至一个固定的值。该准则也是衡量算法是否正确的依据之一。（4）K-means算法的过程可以描述为：（5）算法：划分并计算基于簇中对象的平均值。输入：簇的数目K和包含n个对象的数据库。输出：平方误差总和最小条件下的K个簇。方法：1）任意选择K个对象作为初始的簇中心；2）将所有对象划分到相应的簇中；3）计算每个簇中对象的平均值，将所有对象重新赋给类似的簇；4）Repeat；5）until不再发生变化。K-means方法的缺陷在于它生成硬性划分的聚类，即每个数据点唯一地分配给一个且仅一个聚类。由于事先不知道实际的聚类情况，因此这可能是一中严重的局限。（2）同时，K-means算法很容易陷入局部极小值从而无法获取全局最优解，在大矢量空间空间搜索中性能下降。同时，K-means法对于孤立和异常数据敏感，并对非球型簇可能失效。4、改进的K-means算法针对经典的K-means算法的一些缺点，许多学者在原K-means的基础上提出了一些改进的方法。大体集中在距离的计算，初始点簇中心的优化选择等方面。在NimaAsgharbeygi和ArianMaleki的《GeodesicK-meansClustering》一文中，作者提到了使用测地距离（GeodesicDistance）代替经典的K-means算法中使用欧几里德距离衡量，从改善了经典k-means算法中的不足。如降低了对空间异常数据的敏感度，防止算法在非线性分离（notlinearlyseparable）情况下失效。（6）由于典型的K-means算法中，初始点簇中心的选择是随机的。算法的在选取随机的初始聚类中心时，可能会得到一个次最优聚类，具有较高的平方误差。解决方法之一是采用多次运算，每次使用一组不同的随机初始中心，然后选取具有最小总误差平方和的簇集。好的初始中心的选择，能够极大的减少算法所需时间，减少聚类结果的误差总和。优化初始中心的选择成为重要的研究点。总体来说，笔者将优化选择总结为两个研究方向，其一是直接对所有点簇进行处理，其二是先取样分析，通过各种对样本的分析方法得到初始点簇中心。(一)、直接对所有点簇进行处理这种方法的缺陷是很明显的，在空间数据量较小的情况下，它确实能够快速的完成初始聚类中心的优化，但是在数据量较大的情况下，运算量会成倍数增加。在徐义峰、陈春明、徐云青的《一种改进的k_均值聚类算法》一文中，研究了优化K—均值算法中优化初始的聚类中心。为了找到与数据在空间分布上相一致且相似程度较大的数据集合，采取下列步骤（7）：(1)计算数据对象两两之间的距离；(2)找出距离最近的两个数据对象，形成一个数据对象集合A1，并将它们从总的数据集合U中删除；(3)计算A1中每一个数据对象与数据对象集合U中每一个样本的距离,找出在U中与A1中最近的数据对象，将它并入集合A1并从U中删除，直到A1中的数据对象个数到达一定阈值；(4)再从U中找到样本两两间距离最近的两个数据对象构成A2，重复上面的过程,直到形成k个对象集合；(5)最后对k个对象集合分别进行算术平均，形成k个初始聚类中心。在赵伟、张姝、李文辉的《改进K-means的空间聚类算法》一文中，采用均值——标准差选取初始聚类中心。算法的基本思想是(4)：a)算出所有数据的均值假定为μ，标准差为σ。也就是说数据主要分布在(μ-σ,μ+σ)之间，在此区间由公式mi=(μ-σ)+2σi/N(i=1，⋯，N/M)选取K个点,即为初始聚类中心，其中K=N/M。b)计算各个数据对象到各聚类中心的距离,把数据对象归到离它最近的那个聚类中心所在的类。c)对调整后的新类计算新的聚类中心,如果相邻两次的聚类中心没有任何变化,说明数据对象调整结束。d)K值是预先给定的,未必就是最优解。基于类际离散度最大、类内离散度最小的原则，使用准则函数对K值进一步优化。以确定的聚类中心为初始聚类中心，计算各个数据对象与初始聚类中心距离，并计算距离准则函数,直到K大于或等于[N/M]。其中使准则函数值最小的K值作为最终划分聚类的个数。e)将空间对象重新根据欧氏距离公式分配到相应的聚类,更新各聚类中心，直到聚类结果不变。(二)、通过处理采样样本优化初始聚类中心采用这种方法，样本的采集非常重要，样本的代表性越充分，聚类中心的选择就越优良。在韩晓洪，胡彧的《K-means聚类算法的研究》一文中，提出先进行l次取样，然后在对取样的数据集采用K-means算法进行聚类，这样会产生l×k聚类中心。然后再对这l×k个聚类中心采取以下方法：先计算对象两两之间距离，再筛掉m个与其他对象之间距离之和最大的对象；从剩下的聚类中心中选出距离最大的两个点作为两个不同类的聚类中心；从剩余的聚类中心中找出和其他聚类中心的距离之和最大的点，作为另一个聚类中心为止。直到选出k个聚类中心。（9）在王磊，戚飞虎的《大矢量空间聚类的遗传K—均值算法》一文中提到，将遗传算法用于聚类分析上。文中将遗传算法与K-means相结合，使用遗传算法的思想，模仿生物学进化过程，在交叉操作中引入K-means算法，最终通过选择操作、交叉操作和变异操作等得到聚类结果，并通过实验验证了该算法的在大矢量空间聚类分析中的优良性能。（8）另外，也有一些学者提出了K值优化的问题，如在李永森，杨善林，马溪骏等的《空间聚类算法中的k值优化问题研究》一文中，认为在一些实际应用中（如物流配送），可以使用距离代价函数改进K-means算法，并认为距离代价函数当类内距离和类际距离函数函数相等时是距离代价函数的一个极值点，通过该极值点能较快地找到K的最优解。K值优化算法的过程可以描述为：(5)算法：在K-平均算法基础上，通过距离代价函数优化K值。输入：由用户给定的簇的数目Kr（Kr∈K）和包含n个对象的数据库。输出：距离代价函数最小条件下的Kr*个簇。方法：1）用K-平均算法实现Kr中所有数目下的空间聚类；2）根据距离代价函数分别计算不同聚类数目Kr下的S值；3）搜寻距离代价函数最小的S*，并记下相应的Kr*；4）结束。5、总结与展望k-means算法已经是一种比较成熟的算法，在空间数据挖掘中起着重要的作用。典型的K-Means算法有着其自身的局限性和缺陷。目前，针对k-means算法的改进很多。部分学者研究了不同距离算法下k-means算法的特性并取得了不错的成果。国内大部分研究都基于优化K值初始聚类中心，达到降低k-means算法复杂度的目的，方法很多。针对K值的输入，目前主要还是硬性的划分，具有较大的主观性，如何更好地优化K值，有待进一步的研究解决。同时，需要注意的是，在不同的领域中，其空间聚类算法除了具有一般算法的共性外，还具有其领域的独特性，一种优化算法在一个领域内是有效的，但是在其他领域可能失效。因此，只有考虑到不同领域的特性，选用合适的聚类算法及其优化方法，才能充分发挥空间数据挖掘的功能。同时，K-means算法已经推广出了很多算法，如K—中心值法，TheGlobeKernelk-Means聚类算法(10)等等参考文献：1李德仁，王树良，李德毅.空间数据挖掘理论与应用[M]北京：科学出版社，2006：P352ShashiShekhar，SanjayChawla.空间数据库[M].谢昆青等，译.北京：机械工业出版社，2004：P2393戴晓燕，过仲阳，李勤奋，吴健平.空间聚类的研究现状及其应用[J]上海地质2003.4NO.88:41-454赵伟，张姝，李文辉.改进K-means的空间聚类算法[J]计算机应用研究2008.7vol.25NO.7:1995-19975李永森，杨善林，马溪骏等.空间聚类算法中的K值优化问