关于K均值聚类算法的综述及改进分析.doc_第1页
关于K均值聚类算法的综述及改进分析.doc_第2页
关于K均值聚类算法的综述及改进分析.doc_第3页
关于K均值聚类算法的综述及改进分析.doc_第4页
关于K均值聚类算法的综述及改进分析.doc_第5页
已阅读5页,还剩1页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

关于K均值聚类算法的综述及改进分析摘要:K-means聚类算法是空间聚类领域的重要算法。本文在介绍了空间聚类规则的基础之上,同时叙述了经典的K-means算法,并总结了一些针对K-means算法的相关改进。引言:聚类算法是我们在模式识别中学到的知识,而空间聚类分析方法是空间数据挖掘理论中一个重要的领域,是从海量数据中发现知识的一个重要手段。K-means算法是空间聚类算法中应用非常广泛的算法,同时它也在聚类分析中起着重要作用。日益丰富的空间和非空间数据收集存储于空间数据库中,随着空间数据的不断膨胀,海量的空间数据的大小、复杂性都在快速增长,远远超出了人们的解译能力,从这些空间数据中发现邻域知识迫切需求产生一个多学科、多邻域综合交叉的新兴研究邻域,空间数据挖掘技术应运而生。空间聚类:空间聚类是空间数据挖掘的一个重要组成部分。作为数据挖掘的一个功能,空间聚类可以作为一个单独的工具用于获取数据的分布情况,观察每个聚类的特征,关注一个特定的聚类集合以深入分析。空间聚类也可以作为其它算法的预处理步骤,比如分类和特征描述,这些算法将在已发现的聚类上运行。空间聚类规则是把特征相近的空间实体数据划分到不同的组中,组间的差别尽可能大,组内的差别尽可能小。空间聚类规则与分类规则不同,它不顾及已知的类标记,在聚类前并不知道将要划分成几类和什么样的类别,也不知道根据哪些空间区分规则来定义类。因而,在聚类中没有训练或测试数据的概念,这就是将聚类称为是无指导学习(unsupervised learning)的原因。在多维空间属性中,框定聚类问题是很方便的。给定m个变量描述的n个数据对象,每个对象可以表示为m维空间中的一个点,这时聚类可以简化为从一组非均匀分布点中确定高密度的点群。在多维空间中搜索潜在的群组则需要首先选择合理的相似性标准。已经提出的空间聚类的方法很多,目前,主要分为以下4种主要的聚类分析方法: 基于划分的方法包括K平均法、K中心点法和EM聚类法。它们都是采用一种迭代的重定位技术,尝试通过对象在划分间移动来改进聚类效果。由于这类方法适用于发现大小相近的球状簇,故常用在设施选址等应用中。基于层次的方法此法只是对对象集合进行分解。根据层次的分解方式,这类方法可分为凝聚和分裂两种, Birch, Cure和Chameleon是上述方法的改进。基于密度的方法对给定类中的每个数据点,在一个给定范围的区域中必须包含超过某个阈值的数据点,才继续聚类。它可以用来发现任意形状的簇,过滤“噪声”。代表性的方法有:DBscan,Optics和Denclue。基于栅格的方法把对象空间划为有限的数据单元,形成一个网格结构。该方法处理速度快,处理时间独立于数据对象的数目。常用的方法有STING、WaveCluster以及CLIQUE等。在这些方法当中,K-means(k均值)算法是一种应用十分广泛的聚类分析方法。经典的K-Means算法k-means 算法接受输入量 k ;然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”(引力中心)来进行计算的。 大体上说,k-means 算法的工作过程说明如下:首先从n个数据对象任意选择 k 个对象作为初始聚类中心;而对于所剩下其它对象,则根据它们与这些聚类中心的相似度(距离),分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。 下面详细地介绍K-means聚类问题,假设有一组N个数据的集合X=x1,x2,x3,xn待聚类。K均值值聚类问题是要找到X的一个划分Pk=C1,C2,C3,Ck,使目标函数f(Pk)=最小。其中,mi=1/ni,表示第i个簇中心位置,i=1,k;ni是簇Ci中数据项的个数;表示xi到mi的距离。通常的空间聚类算法是建立在各种距离基础上的,如欧几里得距离、曼哈顿距离和明考斯距离等。其中,最常用的是欧几里得距离。K-means算法的基本思想是:给定一个包含n个数据对象的数据库,以及要生成簇的数目k,随机选取k个对象作为初始的k个聚类中心;然后计算剩余各个样本到每一个聚类中心的距离,把该样本归到离它最近的那个聚类中心所在的类,对调整后的新类使用平均值的方法计算新的聚类中心;如果相邻两次的聚类中心没有任何变化,说明样本调整结束且聚类平均误差准则函数已经收敛。本算法在每次迭代中都要考察每个样本的分类是否正确,若不正确,就要调整。在全部样本调整完成后修改聚类中心,进入下一次迭代。如果在一次迭代算法中,所有的样本被正确分类,则不会有调整,聚类中心不会有变化。在算法迭代中值在不断减小,最终收敛至一个固定的值。该准则也是衡量算法是否正确的依据之一。K-means算法的过程可以描述为:算法:划分并计算基于簇中对象的平均值。输入:簇的数目K和包含n个对象的数据库。输出:平方误差总和最小条件下的K个簇。方法:1) 任意选择K个对象作为初始的簇中心;2) 将所有对象划分到相应的簇中;3) 计算每个簇中对象的平均值,将所有对象重新赋给类似的簇;4) 重复操作;5) 直到不再发生变化。K-means方法的缺陷在于它生成硬性划分的聚类,即每个数据点唯一地分配给一个且仅一个聚类。由于事先不知道实际的聚类情况,因此这可能是一中严重的局限。同时,K-means算法很容易陷入局部极小值从而无法获取全局最优解,在大矢量空间空间搜索中性能下降。同时,K-means法对于孤立和异常数据敏感,并对非球型簇可能失效。改进的K-means算法k-means算法中急需解决的问题主要有三个:1) 在k-means算法中,k是事先给定的,这个k值的选定是很难估计的。很多时候,我们事先并不知道给定的数据集应分成多少类最合适,这也是k-means算法的一个不足。有的算法是通过类的自动合并和分裂,得到较为合理的类型数目k,例如ISODALA算法。关于k-means算法中聚类数目k值的确定,有些根据方差分析理论,应用混合F统计量来确定最佳分类数,并应用了模糊划分墒来验证最佳分类数的正确性。2) 在k-means算法中常采用误差平方和准则函数作为聚类准则函数,考察误差平方和准则函数发现:如果各类之间区别明显且数据分布稠密,则误差平方和准则函数比较有效;但是如果各类的形状和大小差别很大,为使误差平方和的值达到最小,有可能出现将大的聚类分割的现象。此外在运用误差平方和准则函数测度聚类效果时,最佳聚类结果对应于目标函数的极值点,由于目标函数存在着许多局部极小点,而算法的每一步都是沿着目标函数减小的方向进行,若初始化落在了一个局部极小点附近,就会造成算法在局部极小处收敛。因此初始聚类中心的随机选取可能会陷入局部最优解,而难以获得全局最优解。3)从k-means算法框架可以看出,该算法需要不断地进行样本分类调整,不断地计算调整后的新的聚类中心。因此,当数据量非常大时,算法的时间开销是非常大的。所以需要对算法的时间复杂度进行分析、改进,提高算法应用范围。一种改进算法中提到了使用测地距离(Geodesic Distance)代替经典的K-means算法中使用欧几里德距离衡量,从改善了经典k-means算法中的不足。如降低了对空间异常数据的敏感度,防止算法在非线性分离(not linearly separable)情况下失效。由于典型的K-means算法中,初始点簇中心的选择是随机的。算法的在选取随机的初始聚类中心时,可能会得到一个次最优聚类,具有较高的平方误差。解决方法之一是采用多次运算,每次使用一组不同的随机初始中心,然后选取具有最小总误差平方和的簇集。好的初始中心的选择,能够极大的减少算法所需时间,减少聚类结果的误差总和。优化初始中心的选择成为重要的研究点。总体来说,将优化选择总结为两个研究方向,其一是直接对所有点簇进行处理,其二是先取样分析,通过各种对样本的分析方法得到初始点簇中心。1.直接对所有点簇进行处理这种方法的缺陷是很明显的,在空间数据量较小的情况下,它确实能够快速的完成初始聚类中心的优化,但是在数据量较大的情况下,运算量会成倍数增加。其中一种改进算法中研究了优化K均值算法中优化初始的聚类中心。为了找到与数据在空间分布上相一致且相似程度较大的数据集合,采取下列步骤:(1) 计算数据对象两两之间的距离;(2) 找出距离最近的两个数据对象,形成一个数据对象集合A1,并将它们从总的数据集合U中删除;(3) 计算A1 中每一个数据对象与数据对象集合U 中每一个样本的距离,找出在U中与A1 中最近的数据对象,将它并入集合A1 并从U 中删除,直到A1 中的数据对象个数到达一定阈值;(4) 再从U中找到样本两两间距离最近的两个数据对象构成A2,重复上面的过程,直到形成k个对象集合;(5) 最后对k个对象集合分别进行算术平均,形成k个初始聚类中心。还有一种改进算法,在这其中采用了均值标准差选取初始聚类中心。算法的基本思想是:算出所有数据的均值假定为,标准差为。也就是说数据主要分布在(-,+)之间,在此区间由公式m i =(-) + 2i /N ( i = 1,N /M )选取K个点,即为初始聚类中心,其中K =N /M。计算各个数据对象到各聚类中心的距离,把数据对象归到离它最近的那个聚类中心所在的类。c) 对调整后的新类计算新的聚类中心,如果相邻两次的聚类中心没有任何变化,说明数据对象调整结束。d) K值是预先给定的,未必就是最优解。基于类际离散度最大、类内离散度最小的原则,使用准则函数对K值进一步优化。以确定的聚类中心为初始聚类中心,计算各个数据对象与初始聚类中心距离,并计算距离准则函数,直到K大于或等于N /M 。其中使准则函数值最小的K值作为最终划分聚类的个数。e)将空间对象重新根据欧氏距离公式分配到相应的聚类,更新各聚类中心,直到聚类结果不变。2.通过处理采样样本优化初始聚类中心采用这种方法,样本的采集非常重要,样本的代表性越充分,聚类中心的选择就越优良。比如有一些改进算法中提出了K值优化的问题,认为在一些实际应用中(如物流配送),可以使用距离代价函数改进K-means算法,并认为距离代价函数当类内距离和类际距离函数函数相等时是距离代价函数的一个极值点,通过该极值点能较快地找到K的最优解。K 值优化算法的过程可以描述为:算法:在K-平均算法基础上,通过距离代价函数优化K值。输入:由用户给定的簇的数目Kr(KrK)和包含n 个对象的数据库。输出:距离代价函数最小条件下的Kr*个簇。方法:1) 用K-平均算法实现Kr 中所有数目下的空间聚类;2) 根据距离代价函数分别计算不同聚类数目Kr 下的S 值;3) 搜寻距离代价函数最小的S*,并记下相应的Kr*;4) 结束。总结与展望k-means算法已经是一种比较成熟的算法,在空间数据挖掘中起着重要的作用。典型的K-Means算法有着其自身的局限性和缺陷。目前,针对k-means算法的改进很多。部分学者研究了不同距离算法下k-means算法的特性并取得了不错的成果。国内大部分研究都基于优化K值初始聚类中心,达到降低k-means算法复杂度的目的,方法很多。 针对K值的输入,目前主要还是硬性的划分,具有较大的主观性,如何更好地优化K值,有待进一步的研究解决。同时,需要注意的是,在不同的领域中,其空间聚类算法除了具有一般算法的共性外,还具有其领域的独特性,一种优化算法在一个领域内是有效的,但是在其他领域可能失效。因此,只有考虑到不同领域的特性,选用合适的聚类算法及其优化方法,才能充分发挥空间数据挖掘的功能。 同时,K-means算法已经推广出了很多算法,如K中心值法,The Globe Kernel k-Means聚类算法等等 参考文献:1 李德仁,王树良,李德毅

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论