聚类简介及最新发展介绍.docx

这种聚类周的算法一开始把数据空间划分成为有限个单元cell)的网格结构，全部 的处理都是以单个的单元为对象的。这么处理的一个明显的好处就是处理速度非常快，一般 这是与目标数据库中记录的个数无关的，它只与把数据空间分为多少个单元有关。这种聚类的算法给每一个聚类假定一个模型，跟着去找寻能够不错地满足这个模 型的数据集。而一个模型的类型可以是除了以上五种基于不同根底量的聚类算法以外，还存在着使用模糊聚类的算法， 基于图论的聚类算法等等。不同的算法有着不一样的使用场景，有的算法思想容易，适合 在小数据集中使用；而有一些呢，那么使用在大数据集中会更加好，因为它可以发现任意形 状的类簇。3 K-means聚类算法K-means算法属于基于划分的聚类算法，是一种最简单的无监督学习的算法，也是 十大经典数据挖掘算法之一。James MacQucen 在 1967 年第一次使用了 “K-mcans"K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标， 即认为两个对象的距离越近，其似度就越大。该算法认为类簇是由距离靠近的对象组成的， 因此把得到紧凑且独立的类簇作为最终目标。K-means算法常常以欧式距离作为相似度测度，算法经常假设给定的数据集X=xJm = L2，,M, x中的样本用d个描述属性Ai，A2, .»Ad来表示。数据样本=(即，%d), Xj=(Xji，.,Xjd),其中Xii，.)id和x,.,Xjd分别是样本片和番的相对应的d个描述属性Ai，A2,，Ad的具体取值。样本Xi和番之间的相似度通常用它 们之间的距离d(Xi. Xj)来表示，距离越小，样本片和Xj越相似，差异度越小；距离越大，样本Xi和X避不相似，差异度越大。K-means算法常常以欧式距离作为相似度度量，欧式距离公式为:d（Xi，Xj） =12（Xik- XjJ2k = l(3-DK-means聚类算法选择类簇中的质心作为该类的代表点类C中有n个样本点，设 为Pi/，Pi.2,，Pim，那么这个类的代表点(种子点)就是：(3-2)KK个聚类子集Xi，X2,，Xk;各个聚类子集中的样本数量分别为口，皿，, 麻；各个聚类子集的均值代表点(也称聚类中心)分别为im，im，mK:KE = 22(p-mi)2i = lpeXj(3-3)3. 2 K-means聚类算法的描述St印1:从数据集中随机抽取k个质心作为初始聚类的中心；Step 2:计算数据集中所有的点到这k个点的距离，将点归到离其最近的聚类里；Step 3:调整聚类中心，即将聚类的中心移动到聚类的几何中心(即平均值)处；Step 4:重复第2步和第3步，直到聚类的中心不再移动，此时算法收敛。3. 3 K-means聚类算法的重要问题1 K值的选取3. 3. 2初始中心点的选取从算法的描述可见，初始类簇的中心点对聚类的结果的影响非常大，一旦初始值选 取得不够好，那么可能导致无法得到有效的聚类结果。假设要更好地解决该问题，那么可以考虑遗传算法。3. 3. 3时间复杂度算法的时间复杂度为O(N*K*T), N为样本的数量，K为类簇的数量，而T为迭代 的次数。当K和T均远远小于样本数量N时，复杂度为0(N),具有最优复杂度。3. 4 K-means聚类算法的总结K-mcans聚类算法的缺点：(1) K值和初始中心点的选取困难；(2)(3 )对噪声点和孤立点很敏感，少量的该类数据将对中心点的计算产生非常大 的影响；(4)只能发现类球状的类簇。4聚类的最新开展Rodriguez 10发表的文章，为聚类算法的设计提供了一种新的思路。这个新聚类算法的核心思想在于对聚类中心的刻画上，作者认为聚类中心同时拥有 以下两个特点：“距离”相对更大；考虑待聚类的数据集S = Xi|i = 12“，N, dij = dist(Xi，x/表示数据点受看两者之间的某种距离，卜二，为相应的指标集。对于S中的任何数据点XiPQi。4. 1聚类中心Pi的定义它包括截断核和高斯核两种计算方式。截断核：Pi =，X(d - df)jels0)(4-1)X(x) = %；(4-2)参数« > °为截断距离，需要由用户事先指点。由定义易知，Pi表示的是S中与Xi之间的距离小于4的数据点的个数。高斯核：P尸S e岑jism(4-3)济的定义设叫21表示pJi的一个降序排列的下标序，即它满足Pqi Pq2 PqN那么可定义mint%/ 2 2 q8q. = j<»' max 8q ,i = 1(4-4)4. 1.3聚类中心的选取至此，对于S中的每一数据点为,可为其算得(PS)iCls。考虑图41 (A)中的例子，它包含28个二维数据点,将二元对(P/i)i雪在平面上画出来，Pi为横轴，a为纵轴，如图4.1 (B)所示。都比较大，作为类簇的中心点.26, 27, 28三个点的可比较大但Pi较小，而这三个点在原始数据 集中式离群点。所以类簇中心的特点是同时具有较大的P和5值。O但不是所有情况都可用肉眼判断出聚类中心得情况。因此要计算一个将P和5值综 合考虑的量Yi = PiSpi E ls(4-5)显然Y值越大，越有可能聚类中心，因此，只需对丫3/1做降序排列，然后从前往 后选取假设干个作为聚类中心即可。但对于确定聚类中心的个数也是一个问题。图4-2降序排列的丫值示意图如图4-2所示，把Y值作为纵轴，以下标为横轴，可见：非聚类中心的Y值比较平滑, 而从非聚类中心过渡到聚类中心时丫2聚类算法描述待聚类的数据集, =%r= 1,2，,N,设其包含小(之1)个类簇，而瑞/1仍表示仙/1风般/叫为第j个类簇中心= 数据点归类属性标记，即Bi个类簇小/1为大的数据点中与七argmin ldq.q.J,i > 2n -q% j<i0,i = 1%$1%= 1,那么Xi属于边缘，为。那么属于中心。Stcpl: 11)确定截断距离« > °；(2)计算0务3并生成其降序排列下标序81；计算及旧/1Step 2:确定聚类中心并初始化数据点归类属性标记具体为假设为聚类中心，且归属第k个类簇-1,其他情况Step 3:对非聚类中心数据点进行归类；Step 4:假设网 > I那么将每个类簇中的数据点进一步分为类簇中心和类簇边缘。4. 3聚类算法结果展示图4-3各种情况的测试结果如图4-3所示，该算法能够很好地适应各种不同形状的类簇的情况，可拓展性比较 |W O4. 4聚类算法小结Rodriguez 10提出的算法在本质上是基于流形的做法。这一个这一个聚类算法的思想十分的朴素，让人十分讶异。但是却表达了“简单就是美" 的这一哲学思维。具体上说,文章有一些细节并不没有深入讨论，比方对距离的具体衡量方式是什么， 但本身距离问题本身就是一个活泼的研究领域，文章旨在提出一种聚类算法的新思路，而且 具体问题中会有各种各样场景,还是需要根据实际问题的了解选择个最适宜的距离会比较 好。5总结本文的具体脉络是首先通过对聚类的概述引入各种不同类别的聚类算法的介绍，然 后通过对最经典，最容易理解的K-means聚类算法的具体描述和解释，简单初步地对聚类 算法给出一个具体的印象和作用。然后再通过Rodriguez 10的文章所描述的聚类算法，提 供一个聚类算法的最新的思路，并由此契合了 “简单就是美"的这一哲学思维。具体来说，尽管聚类分析有着几十年的研究历史,众多聚类算法相继被提出、相关 的应用被展开，但聚类问题仍然存在着巨大的挑战。一些对聚类算法的总结，可以得出如下一 些结论：大多数聚类算法都需要预先给出参数,事实上，如果没有相关知识和经验，这在多数 情况下是不可行的.在很多文献中，研究者们给出了各自的聚类算法评价指标，并只给出其算法的优点。 所以。聚类算法的聚类结果有定的不可预见性，在实际应用中应根据数据类型选择适宜 的聚类算法(和可恰当的相似性度量方式)，以取得最正确的聚类效果.针对不同数据集,进一步 开展聚类算法预测分类数的能力研究。参考文献11 Grigorios Tzortzis, Aristidis Likas, The MinMax 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 0031-3203,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,:/dx.doi.org/10.1016/S0306-4379(01)00008-4.3 Wei Wang , Jiong Yang , Richard Muntz. A Statistical Information Grid Approach to Spatial Data Mining. Conference: VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, GreeceEytan Domany, Marcelo Blatt, Yoram Gdalyahu, Daphna Wcinshall, Supcrparamagnctic clustering of data: application to computer vision, Computer Physics Communications, Volume 121, 1999, Pages 5-12, ISSN 0010-4655, :/dx.doi.org/10.1016/S0010-4655(99)00267-2.4 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 2027-2037, ISSN 0031-3203,.5 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 Yc. "An Improved Clustering Algorithm of Tunnel Monitoring Data for Cloud Computing. TheScientificWorldJournal (2021).9 Murat Erisoglu, Nazif Calis, Sadullah Sakallioglu, A new algorithm for initial cluster centers in k-means algorithm, Pattern Recognition Letters, Volume 32, Issue 14, 2021, Pages 1701-1705, ISSN 0167-8655,.10 By Alex Rodriguez, Alessandro Laio. Clustering by fast search and find of density peaks. Science. 27 Jun 2021 : 1492-1496