聚类简介及最新发展介绍

1、 这种聚类4的算法一开始把数据空间划分成为有限个单元cell的网格结构,全部的处理都是以单个的单元为对象的。这么处理的一个明显的好处就是处理速度非常快，一般这是与目标数据库中记录的个数无关的，它只与把数据空间分为多少个单元有关。 这种聚类5的算法给每一个聚类假定一个模型，跟着去找寻能够不错地满足这个模型的数据集。而一个模型的类型可以是 除了以上五种基于不同根底量的聚类算法以外，还存在着使用模糊聚类的算法6，基于图论的聚类算法7等等。不同的算法有着不一样的使用场景，有的算法思想容易，适合在小数据集中使用；而有一些呢，那么使用在大数据集中会更加好，因为它可以发现任意形状的类簇。3 K-means聚

2、类算法 K-means算法属于基于划分的聚类算法，是一种最简单的无监督学习的算法，也是十大经典数据挖掘算法之一。 James MacQueen在1967年第一次使用了“K-means K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其似度就越大。该算法认为类簇是由距离靠近的对象组成的，因此把得到紧凑且独立的类簇作为最终目标。 K-means算法常常以欧式距离作为相似度测度，算法经常 假设给定的数据集X=xm|m=1,2,M，X中的样本用d个描述属性A1，A2，Ad来表示。数据样本xi=(xi1,xid)，xj=xj1,xjd，其中xi1,

3、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，那么这个类的代表点种子点就是：mi=1nj=1npi,j(3-2) KK个聚类子集X1，X2，XK；各个聚类子集

4、中的样本数量分别为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:调整聚类中心，即将聚类的中心移动到聚类的几何中心即平均值处；Step 4:重复第2步和第3步，直到聚类的中心不再移动，此时算法收敛。3.3 K-means聚类算法的重要问题3.3.1 K值的选取3.3.2 初始中心点的选取 从算法的描述可见，初始类簇的中心点对聚类的结果的

5、影响非常大，一旦初始值选取得不够好，那么可能导致无法得到有效的聚类结果。 假设要更好地解决该问题，那么可以考虑遗传算法。3.3.3 时间复杂度 算法的时间复杂度为O(N*K*T)，N为样本的数量，K为类簇的数量，而T为迭代的次数。当K和T均远远小于样本数量N时，复杂度为O(N)，具有最优复杂度。3.4 K-means聚类算法的总结 K-means聚类算法的缺点：K值和初始中心点的选取困难；对噪声点和孤立点很敏感，少量的该类数据将对中心点的计算产生非常大的影响；只能发现类球状的类簇。4 聚类的最新开展 Rodriguez 10发表的文章，为聚类算法的设计提供了一种新的思路。 这个新聚类算法的核心

6、思想在于对聚类中心的刻画上，作者认为聚类中心同时拥有以下两个特点： “距离相对更大； 考虑待聚类的数据集S=xi|i=1,2,N，dij=distxi, xj表示数据点xi，xj两者之间的某种距离，IS=1,2,N为相应的指标集。对于S中的任何数据点xiii。4.1 聚类中心i的定义 它包括截断核和高斯核两种计算方式。 截断核：i=jISiX(dij-dc)(4-1)Xx=1, x0为截断距离，需要由用户事先指点。 由定义易知，i表示的是S中与xi之间的距离小于dc的数据点的个数。 高斯核：i=jISie-(dijdc)2(4-3)i的定义 设qii=1N表示ii=1N的一个降序排列的下标序，

7、即它满足q1q2qN那么可定义qi=minqjjidqiqj,i2maxj2qj,i=1(4-4)4.1.3聚类中心的选取 至此，对于S中的每一数据点xi，可为其算得i,i,iIS。 考虑图4-1A中的例子，它包含28个二维数据点，将二元对i,ii=128在平面上画出来，i为横轴，i为纵轴，如图4-1B所示。都比拟大, 作为类簇的中心点. 26, 27, 28三个点的i比拟大但i较小，而这三个点在原始数据集中式离群点。 所以类簇中心的特点是同时具有较大的和值。 。 但不是所有情况都可用肉眼判断出聚类中心得情况。因此要计算一个将和值综合考虑的量i=ii,iIS(4-5) 显然值越大，越有可能聚类

8、中心，因此，只需对ii=1N做降序排列，然后从前往后选取假设干个作为聚类中心即可。 但对于确定聚类中心的个数也是一个问题。图4-2 降序排列的值示意图 如图4-2所示，把值作为纵轴，以下标为横轴，可见：非聚类中心的值比拟平滑，而从非聚类中心过渡到聚类中心时4.2 聚类算法描述 待聚类的数据集S=xi|i=1,2,N，设其包含nc(1)个类簇，而qii=1N仍表示ii=1N mjj=1ncxmj为第j个类簇中心 cii=1N：数据点归类属性标记，即cici个类簇 nii=1Nxi大的数据点中与xinqi=argminqjj0； 2计算ii=1N并生成其降序排列下标序qii=1N； 3计算ii=1

9、N及nii=1NStep 2: 确定聚类中心mjj=1nc，并初始化数据点归类属性标记cii=1N，具体为ci=k，若xi为聚类中心，且归属第k个类簇-1，其他情况Step 3: 对非聚类中心数据点进行归类；Step 4:假设nc1，那么将每个类簇中的数据点进一步分为类簇中心和类簇边缘。4.3 聚类算法结果展示图4-3 各种情况的测试结果 如图4-3所示，该算法能够很好地适应各种不同形状的类簇的情况，可拓展性比拟高。4.4 聚类算法小结 Rodriguez 10提出的算法在本质上是基于流形的做法。这一个 这一个聚类算法的思想十分的朴素，让人十分讶异。但是却表达了“简单就是美的这一哲学思维。 具

10、体上说，文章有一些细节并不没有深入讨论，比方对距离的具体衡量方式是什么，但本身距离问题本身就是一个活泼的研究领域，文章旨在提出一种聚类算法的新思路，而且具体问题中会有各种各样场景，还是需要根据实际问题的了解选择一个最适宜的距离会比拟好。5 总结 本文的具体脉络是首先通过对聚类的概述引入各种不同类别的聚类算法的介绍，然后通过对最经典，最容易理解的K-means聚类算法的具体描述和解释，简单初步地对聚类算法给出一个具体的印象和作用。然后再通过Rodriguez 10的文章所描述的聚类算法，提供一个聚类算法的最新的思路，并由此契合了“简单就是美的这一哲学思维。 具体来说，尽管聚类分析有着几十年的研究

11、历史,众多聚类算法相继被提出、相关的应用被展开,但聚类问题仍然存在着巨大的挑战。一些对聚类算法的总结,可以得出如下一些结论: 大多数聚类算法都需要预先给出参数,事实上,如果没有相关知识和经验,这在多数情况下是不可行的. 在很多文献中,研究者们给出了各自的聚类算法评价指标,并只给出其算法的优点。所以。 聚类算法的聚类结果有一定的不可预见性,在实际应用中应根据数据类型选择适宜的聚类算法(和可恰当的相似性度量方式),以取得最正确的聚类效果.针对不同数据集,进一步开展聚类算法预测分类数的能力研究。参考文献1 Grigorios Tzortzis, Aristidis Likas, The MinMax

12、 K-Means clustering algorithm, Pattern Recognition, Volume 47, Issue 7, 2021, Pages 2505-2516, ISSN 0031-3203, 2 Liang Bai, Xueqi Cheng, Jiye Liang, Huawei Shen, Yike Guo, Fast density clustering strategies based on the k-means algorithm, Pattern Recognition, Volume 71, 2021, Pages 375-386, ISSN 003

13、1-3203, 3 Sudipto Guha, Rajeev Rastogi, Kyuseok Shim, Cure: an efficient clustering algorithm for large 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

14、 Grid Approach to Spatial Data Mining. Conference: VLDB97, Proceedings of 23rd International Conference 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, C

15、omputer 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, 2004, Pages 202

16、7-2037, ISSN 0031-3203, .7 Sharan R, Shamir R. CLICK: a clustering algorithm with applications to gene expression analysis. Proc Int Conf Intell Syst Mol Biol. 2000;8:307-16.8 Zhong, Luo, KunHao Tang, Lin Li, Guang Yang and JingJing Ye. “An Improved Clustering Algorithm of Tunnel Monitoring Data for Cloud Computing. TheScientificWorldJournal (2021). 9 Murat Erisoglu, Nazif Calis, Sadullah Sakallioglu, A new algorithm for i