关于K均值聚类算法的综述及改进分析

《关于K均值聚类算法的综述及改进分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、关于K均值聚类算法的综述及改进分析摘要：K-means聚类算法是空间聚类领域的重要算法。本文在介绍了空间聚类规则的基础之上，同时叙述了经典的K-means算法，并总结了一些针对K-means算法的相关改进。引言：聚类算法是我们在模式识别中学到的知识，而空间聚类分析方法是空间数据挖掘理论中一个重要的领域，是从海量数据中发现知识的一个重要手段。K-means算法是空间聚类算法中应用非常广泛的算法，同时它也在聚类分析中起着重要作用。日益丰富的空间和非空间数据收集存储于空间数据库中，随着空间数据的不断膨胀，海量的空间数据的大小、复杂性都在快速增长，远远超出了人们的解译能力，

2、从这些空间数据中发现邻域知识迫切需求产生一个多学科、多邻域综合交叉的新兴研究邻域，空间数据挖掘技术应运而生。空间聚类：空间聚类是空间数据挖掘的一个重要组成部分。作为数据挖掘的一个功能，空间聚类可以作为一个单独的工具用于获取数据的分布情况，观察每个聚类的特征，关注一个特定的聚类集合以深入分析。空间聚类也可以作为其它算法的预处理步骤，比如分类和特征描述，这些算法将在已发现的聚类上运行。空间聚类规则是把特征相近的空间实体数据划分到不同的组中，组间的差别尽可能大，组内的差别尽可能小。空间聚类规则与分类规则不同，它不顾及已知的类标记，在聚类前并不知道将要划分成几类和什么样的类

3、别，也不知道根据哪些空间区分规则来定义类。因而，在聚类中没有训练或测试数据的概念，这就是将聚类称为是无指导学习（unsupervisedlearning）的原因。在多维空间属性中，框定聚类问题是很方便的。给定m个变量描述的n个数据对象，每个对象可以表示为m维空间中的一个点，这时聚类可以简化为从一组非均匀分布点中确定高密度的点群。在多维空间中搜索潜在的群组则需要首先选择合理的相似性标准。已经提出的空间聚类的方法很多，目前，主要分为以下4种主要的聚类分析方法:①基于划分的方法包括K—平均法、K—中心点法和EM聚类法。它们都是采用一种迭代的重定位技术,尝试通过对象在划分间

4、移动来改进聚类效果。由于这类方法适用于发现大小相近的球状簇,故常用在设施选址等应用中。②基于层次的方法此法只是对对象集合进行分解。根据层次的分解方式,这类方法可分为凝聚和分裂两种,Birch,Cure和Chameleon是上述方法的改进。③基于密度的方法对给定类中的每个数据点,在一个给定范围的区域中必须包含超过某个阈值的数据点,才继续聚类。它可以用来发现任意形状的簇,过滤“噪声”。代表性的方法有:DBscan,Optics和Denclue。④基于栅格的方法把对象空间划为有限的数据单元,形成一个网格结构。该方法处理速度快,处理时间独立于数据对象的数目。常用的方法有ST

5、ING、WaveCluster以及CLIQUE等。在这些方法当中，K-means（k—均值）算法是一种应用十分广泛的聚类分析方法。经典的K-Means算法k-means算法接受输入量k；然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。大体上说，k-means算法的工作过程说明如下：首先从n个数据对象任意选择k个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相

6、似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数.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的距离。通常的空间聚

7、类算法是建立在各种距离基础上的，如欧几里得距离、曼哈顿距离和明考斯距离等。其中，最常用的是欧几里得距离。K-means算法的基本思想是：给定一个包含n个数据对象的数据库，以及要生成簇的数目k，随机选取k个对象作为初始的k个聚类中心；然后计算剩余各个样本到每一个聚类中心的距离，把该样本归到离它最近的那个聚类中心所在的类，对调整后的新类使用平均值的方法计算新的聚类中心；如果相邻两次的聚类中心没有任何变化，说明样本调整结束且聚类平均误差准则函数已经收敛。本算法在每次迭代中都要考察每个样本的分类是否正确，若不正确，就要调整。在全部样本调整完成后修改聚类中心，进入下一次迭