聚类简介及最新发展

1、聚类简介及最新发展1 引言 伴随着计算机技术近这些年来的高速猛烈的发展，人类采集与获取数据的能力大幅度提高，信息量迅速增长，互联网的发展更是为我们带来了海量的信息和数据。不过储存在各种数据媒体中的数据，在缺乏有力的分析工具的情况下，已经不是人类的理解和概括能力能够处理的了，正是因为这个理由，作为数据挖掘的一种有效的工具，聚类算法引起了人们的广泛关注。聚类分析是一个古老的问题，人类要认识世界就必须区别不同的事物并认识事物间的相似之处。 聚类是将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对

2、象相异。 “物以类聚，人以群分”，在自然科学和社会科学中，存在着大量的分类问题。聚类分析又称群分析，它是研究样品或指标）分类问题的一种统计分析方法。聚类分析以相似性为基础，在一个聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性。聚类分析又称群分析，它是研究（样品或指标）分类问题的一种统计分析方法，同时也是数据挖掘的一个重要算法。聚类与分类的不同在于，聚类所要求划分的类是未知的。 本文的文章脉络主要是：首先，先总体介绍聚类算法的几种分类，描述这几种分类的一些特点。然后，通过具体描述和介绍聚类算法中最经典，思想也十分明了清晰的K-means聚类算法来给出聚类算法一个具体的形象和它实际上能

3、得到的效果。紧接着，就是通过介绍和描述一个聚类最新的发展成果，让读者能够具体了解聚类算法的发展方向和最新的研究成果。最后就是对整篇文章的总结。2 聚类算法的分类 聚类算法可以广泛在市场分析，商业经营，决策支持，模式识别和图像处理等各个不同领域内应用，其主要包括下面几类：2.1 基于分层的聚类 这种聚类3的算法逐层分解给出的数据集，直到某种条件满足为止。算法又能够分为“自底向上”和“自顶向下”两种。比如在“自底向上”方法之中，初始时每一个数据纪录都构成一个单独的组，在下面进行的迭代中，它把那些相互邻近的组合并成一个组，直到某个条件满足或所有的记录组成一个分组为止。2.2 基于划分的聚类 这种聚类

4、1,8,9的算法对一个有N个元组或者纪录的数据集，构造K个分组，每一个分组就代表一个聚类，KN。并且这些分组满足下列条件：（1） 每一个分组至少包含一个数据纪录；（2）每一个数据纪录属于且仅属于一个分组；对于给定的K，一个原始的分组方法会在算法一开始给出，然后经过不停迭代的方法改变这些组别，令到每一次迭代之后的分组方式都较前一次有改进，改进的标准就是：同一分组中的记录越近越好，而不同分组中的纪录越远越好。2.3 基于密度的聚类 这种聚类2的算法与另外的聚类算法的一个根本不同是：它不是根据各种各样的距离的，而是基于密度的。所以因此能够解决基于距离的算法只可以找到“类圆形”的聚类的这一个不足。这种

5、聚类算法的指导思想就是，只要一个区域中的点的密度大于某个阈值，就添加它到与之相近的类别当中去。2.4 基于网格的方法 这种聚类4的算法一开始把数据空间划分成为有限个单元（cell）的网格结构,全部的处理都是以单个的单元为对象的。这么处理的一个明显的好处就是处理速度非常快，一般这是与目标数据库中记录的个数无关的，它只与把数据空间分为多少个单元有关。2.5基于模型的方法 这种聚类5的算法给每一个聚类假定一个模型，跟着去找寻能够不错地满足这个模型的数据集。而一个模型的类型可以是数据点在空间中的密度分布函数或者其它。它的一个潜在的假定就是：目标数据集是由一系列的概率分布所决定的。通常有两种尝试方向：统

6、计的方案和神经网络的方案。 除了以上五种基于不同基础量的聚类算法以外，还存在着使用模糊聚类的算法6，基于图论的聚类算法7等等。不同的算法有着不一样的使用场景，有的算法思想容易，适合在小数据集中使用；而有一些呢，则使用在大数据集中会更加好，因为它可以发现任意形状的类簇。3 K-means聚类算法 K-means算法属于基于划分的聚类算法，是一种最简单的无监督学习的算法，也是十大经典数据挖掘算法之一。 James MacQueen在1967年第一次使用了“K-means”这一个名字，但是算法的核心思想却是由Hugo Steinhaus在1957年给出的。1957年Stuart Lloyd在研究脉冲

7、编码调制技术是提出了一种关于K-means的标准算法，但知道1982年才发表。1965年E.W.Forgy正式发表了这一个算法，因此，K-means算法有时也被称为Lloyd-Forgy算法。 K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其似度就越大。该算法认为类簇是由距离靠近的对象组成的，因此把得到紧凑且独立的类簇作为最终目标。 K-means算法常常以欧式距离作为相似度测度，算法经常采用误差平方和准则函数作为聚类准则函数。3.1 K-means相似度度量，准则函数和类簇中心点 假设给定的数据集X=xm|m=1,2,M，X中的样本用

8、d个描述属性A1，A2，Ad来表示。数据样本xi=(xi1,xid)，xj=xj1,xjd，其中xi1,xid和xj1,xjd分别是样本xi和xj的相对应的d个描述属性A1，A2，Ad的具体取值。样本xi和xj之间的相似度通常用它们之间的距离d(xi, xj)来表示，距离越小，样本xi和xj越相似，差异度越小；距离越大，样本xi和xj越不相似，差异度越大。 K-means算法常常以欧式距离作为相似度度量，欧式距离公式为：dxi, xj=k=1dxik- xjk212(3-1) K-means聚类算法选择类簇中的质心作为该类的代表点类Ci中有n个样本点，设为pi,1，pi,2，pi,n，则这个类

9、的代表点（种子点）就是：mi=1nj=1npi,j(3-2) K-means聚类算法使用误差平方和准则函数来评价聚类性能。给定数据集X，假设X包含K个聚类子集X1，X2，XK；各个聚类子集中的样本数量分别为n1，n2，nK；各个聚类子集的均值代表点（也称聚类中心）分别为m1，m2，mK；则误差平方和准则函数公式为：E=i=1KpXi(p-mi)2(3-3) 3.2 K-means聚类算法的描述Step 1:从数据集中随机抽取k个质心作为初始聚类的中心；Step 2:计算数据集中所有的点到这k个点的距离，将点归到离其最近的聚类里；Step 3:调整聚类中心，即将聚类的中心移动到聚类的几何中心（即

10、平均值）处；Step 4:重复第2步和第3步，直到聚类的中心不再移动，此时算法收敛。3.3 K-means聚类算法的重要问题3.3.1 K值的选取 算法中K值需要在开始之前给定，不过这一个K值却又是非常难以估计的。很多时候，事前并不能够确定数据集应该分成多少个类别才是最适合的。这也是本算法的一个不足之处，一些算法专门探讨了K值的选取方法，如ISODATA算法，通过类的自动合并和分裂，得到较为合理的类簇数目K。3.3.2 初始中心点的选取 从算法的描述可见，初始类簇的中心点对聚类的结果的影响非常大，一旦初始值选取得不够好，则可能导致无法得到有效的聚类结果。 通常的做法是在样本空间随机生成，如果数

11、据量不大，可以让程序多运行几次，然后选择让准则函数的值最小的聚类结果作为最终的结果。 若要更好地解决该问题，则可以考虑遗传算法。3.3.3 时间复杂度 算法的时间复杂度为O(N*K*T)，N为样本的数量，K为类簇的数量，而T为迭代的次数。当K和T均远远小于样本数量N时，复杂度为O(N)，具有最优复杂度。3.4 K-means聚类算法的总结 K-means聚类算法的优点：K-means聚类算法确定的K个类簇达到平方误差最小。当类簇是密集的，且类与类之间区别明显时，效果比较好。对于处理大数据集，这个算法是高效和可拓展的，时间复杂度可达到最优。 K-means聚类算法的缺点：（1） K值和初始中心点

12、的选取困难；（2） 由于准则函数局部极小值存在，算法可能会陷入局部最优而达不到全局最优；（3） 对噪声点和孤立点很敏感，少量的该类数据将对中心点的计算产生非常大的影响；（4） 只能发现类球状的类簇。4 聚类的最新发展 Rodriguez 10发表的文章，为聚类算法的设计提供了一种新的思路。 这个新聚类算法的核心思想在于对聚类中心的刻画上，作者认为聚类中心同时拥有以下两个特点： 1.本身的密度大，即它被密度均不超过它的邻居包围； 2.与其他密度更大的数据点之间的“距离”相对更大； 考虑待聚类的数据集S=xi|i=1,2,N，dij=distxi, xj表示数据点xi，xj两者之间的某种距离，IS

13、=1,2,N为相应的指标集。对于S中的任何数据点xi可以为它定义局部密度i和它到更高密度的点的距离i。4.1 聚类中心4.1.1 局部密度i的定义 它包括截断核和高斯核两种计算方式。 截断核：i=jISiX(dij-dc)(4-1) 其中函数：Xx=1, x0为截断距离，需要由用户事先指点。 由定义易知，i表示的是S中与xi之间的距离小于dc的数据点的个数。 高斯核：i=jISie-(dijdc)2(4-3) 对比(4-1)和(4-3)易知，截断核为离散值，高斯核为连续值，因此相对来说，后者产生冲突（即不同的数据点具有相同的局部密度值）的概率更小。4.1.2到更高密度的点的距离i的定义 设qi

14、i=1N表示ii=1N的一个降序排列的下标序，即它满足q1q2qN则可定义qi=minqjjidqiqj,i2maxj2qj,i=1(4-4)4.1.3聚类中心的选取 至此，对于S中的每一数据点xi，可为其算得i,i,iIS。图 4-1 关于决定聚类中心的示例及示意图 考虑图4-1（A）中的例子，它包含28个二维数据点，将二元对i,ii=128在平面上画出来，i为横轴，i为纵轴，如图4-1（B）所示。 容易发现1号和10号都比较大, 作为类簇的中心点. 26, 27, 28三个点的i比较大但i较小，而这三个点在原始数据集中式离群点。 所以类簇中心的特点是同时具有较大的和值。 在确定了类簇中心之

15、后, 其它样本点依据局部密度从高到低依先后顺序确定所属的类别，每个人非中心的样本点类别为邻域内最近的高于该点样本点的点的样本点所属的类别。 但不是所有情况都可用肉眼判断出聚类中心得情况。因此要计算一个将和值综合考虑的量i=ii,iIS(4-5) 显然值越大，越有可能聚类中心，因此，只需对ii=1N做降序排列，然后从前往后选取若干个作为聚类中心即可。 但对于确定聚类中心的个数也是一个问题。图4-2 降序排列的值示意图 如图4-2所示，把值作为纵轴，以下标为横轴，可见：非聚类中心的值比较平滑，而从非聚类中心过渡到聚类中心时值有明显跳跃，可以此决定聚类中心的个数。4.2 聚类算法描述 待聚类的数据集

16、S=xi|i=1,2,N，设其包含nc(1)个类簇，而qii=1N仍表示ii=1N的一个降序排列的下标序，再因引入若干记号： mjj=1nc：各个聚类中心对应的数据点编号，即xmj为第j个类簇中心 cii=1N：数据点归类属性标记，即ci表示S中第i号数据点归属第ci个类簇 nii=1N：表示S中所有局部密度比xi大的数据点中与xi距离最近的数据点的编号，具体定义为nqi=argminqjj0； （2）计算ii=1N并生成其降序排列下标序qii=1N； （3）计算ii=1N及nii=1NStep 2: 确定聚类中心mjj=1nc，并初始化数据点归类属性标记cii=1N，具体为ci=k，若xi为

17、聚类中心，且归属第k个类簇-1，其他情况Step 3: 对非聚类中心数据点进行归类；Step 4:若nc1，则将每个类簇中的数据点进一步分为类簇中心和类簇边缘。4.3 聚类算法结果展示图4-3 各种情况的测试结果 如图4-3所示，该算法能够很好地适应各种不同形状的类簇的情况，可拓展性比较高。图4-4 不同密度下的测试结果 如图4-4所示，该算法能够很好地适应各种不同密度的情况，而图中的黑色点就是算法描述中的算法边缘点。4.4 聚类算法小结 Rodriguez 10提出的算法在本质上是基于流形的做法。这一个算法的过程可以总结为：首先搜索合适的局部密度最大点作为类簇中心，然后再将类簇标签从高密度点

18、向低密度点依次传播。 这一个聚类算法的思想十分的朴素，让人十分讶异。但是却体现了“简单就是美”的这一哲学思维。 具体上说，文章有一些细节并不没有深入讨论，比如对距离的具体衡量方式是什么，但本身距离问题本身就是一个活跃的研究领域，文章旨在提出一种聚类算法的新思路，而且具体问题中会有各种各样场景，还是需要根据实际问题的了解选择一个最合适的距离会比较好。5 总结 本文的具体脉络是首先通过对聚类的概述引入各种不同类别的聚类算法的介绍，然后通过对最经典，最容易理解的K-means聚类算法的具体描述和解释，简单初步地对聚类算法给出一个具体的印象和作用。然后再通过Rodriguez 10的文章所描述的聚类算

19、法，提供一个聚类算法的最新的思路，并由此契合了“简单就是美”的这一哲学思维。 具体来说，尽管聚类分析有着几十年的研究历史,众多聚类算法相继被提出、相关的应用被展开,但聚类问题仍然存在着巨大的挑战。一些对聚类算法的总结,可以得出如下一些结论: 大多数聚类算法都需要预先给出参数,事实上,如果没有相关知识和经验,这在多数情况下是不可行的. 在很多文献中,研究者们给出了各自的聚类算法评价指标,并只给出其算法的优点。所以,开展聚类算法(全面、客观的)评价标准、数据集特性的描述方法等研究,不仅时机成熟,而且有着重要意义。 聚类算法的聚类结果有一定的不可预见性,在实际应用中应根据数据类型选择合适的聚类算法(

20、和可恰当的相似性度量方式),以取得最佳的聚类效果.针对不同数据集,进一步开展聚类算法预测分类数的能力研究。参考文献1 Grigorios Tzortzis, Aristidis Likas, The MinMax K-Means clustering algorithm, Pattern Recognition, Volume 47, Issue 7, 2014, Pages 2505-2516, ISSN 0031-3203, /10.1016/j.patcog.2014.01.015.2 Liang Bai, Xueqi Cheng, Jiye Liang,

21、 Huawei Shen, Yike Guo, Fast density clustering strategies based on the k-means algorithm, Pattern Recognition, Volume 71, 2017, Pages 375-386, ISSN 0031-3203, /10.1016/j.patcog.2017.06.023.3 Sudipto Guha, Rajeev Rastogi, Kyuseok Shim, Cure: an efficient clustering algorithm for larg

22、e databases, Information Systems, Volume 26, Issue 1, 2001, Pages 35-58, ISSN 0306-4379, /10.1016/S0306-4379(01)00008-4.4 Wei Wang , Jiong Yang , Richard Muntz. A Statistical Information Grid Approach to Spatial Data Mining. Conference: VLDB97, Proceedings of 23rd International Confe

23、rence on Very Large Data Bases, August 25-29, 1997, Athens, Greece5 Eytan Domany, Marcelo Blatt, Yoram Gdalyahu, Daphna Weinshall, Superparamagnetic clustering of data: application to computer vision, Computer Physics Communications, Volume 121, 1999, Pages 5-12, ISSN 0010-4655, /10.1016/S0010-4655(99)00267-2.6 Haojun Sun, Shengrui Wang, Qingshan Jiang, FCM-Based Model Selection Algorithms for Determining the Number of Clusters, Pattern Recognition, Volume 37, Issue 10, 200