聚類簡(jiǎn)介及最新發(fā)展介紹

1、 這種聚類4的算法一開始把數(shù)據(jù)空間劃分成為有限個(gè)單元cell的網(wǎng)格結(jié)構(gòu),全部的處理都是以單個(gè)的單元為對(duì)象的。這么處理的一個(gè)明顯的好處就是處理速度非?？?，一般這是與目標(biāo)數(shù)據(jù)庫(kù)中記錄的個(gè)數(shù)無(wú)關(guān)的，它只與把數(shù)據(jù)空間分為多少個(gè)單元有關(guān)。 這種聚類5的算法給每一個(gè)聚類假定一個(gè)模型，跟著去找尋能夠不錯(cuò)地滿足這個(gè)模型的數(shù)據(jù)集。而一個(gè)模型的類型可以是 除了以上五種基于不同根底量的聚類算法以外，還存在著使用模糊聚類的算法6，基于圖論的聚類算法7等等。不同的算法有著不一樣的使用場(chǎng)景，有的算法思想容易，適合在小數(shù)據(jù)集中使用；而有一些呢，那么使用在大數(shù)據(jù)集中會(huì)更加好，因?yàn)樗梢园l(fā)現(xiàn)任意形狀的類簇。3 K-means聚

2、類算法 K-means算法屬于基于劃分的聚類算法，是一種最簡(jiǎn)單的無(wú)監(jiān)督學(xué)習(xí)的算法，也是十大經(jīng)典數(shù)據(jù)挖掘算法之一。 James MacQueen在1967年第一次使用了“K-means K-means算法是很典型的基于距離的聚類算法，采用距離作為相似性的評(píng)價(jià)指標(biāo)，即認(rèn)為兩個(gè)對(duì)象的距離越近，其似度就越大。該算法認(rèn)為類簇是由距離靠近的對(duì)象組成的，因此把得到緊湊且獨(dú)立的類簇作為最終目標(biāo)。 K-means算法常常以歐式距離作為相似度測(cè)度，算法經(jīng)常 假設(shè)給定的數(shù)據(jù)集X=xm|m=1,2,M，X中的樣本用d個(gè)描述屬性A1，A2，Ad來(lái)表示。數(shù)據(jù)樣本xi=(xi1,xid)，xj=xj1,xjd，其中xi1,

3、xid和xj1,xjd分別是樣本xi和xj的相對(duì)應(yīng)的d個(gè)描述屬性A1，A2，Ad的具體取值。樣本xi和xj之間的相似度通常用它們之間的距離d(xi, xj)來(lái)表示，距離越小，樣本xi和xj越相似，差異度越??；距離越大，樣本xi和xj越不相似，差異度越大。 K-means算法常常以歐式距離作為相似度度量，歐式距離公式為：dxi, xj=k=1dxik- xjk212(3-1) K-means聚類算法選擇類簇中的質(zhì)心作為該類的代表點(diǎn)類Ci中有n個(gè)樣本點(diǎn)，設(shè)為pi,1，pi,2，pi,n，那么這個(gè)類的代表點(diǎn)種子點(diǎn)就是：mi=1nj=1npi,j(3-2) KK個(gè)聚類子集X1，X2，XK；各個(gè)聚類子集

4、中的樣本數(shù)量分別為n1，n2，nK；各個(gè)聚類子集的均值代表點(diǎn)也稱聚類中心分別為m1，m2，mK；E=i=1KpXi(p-mi)2(3-3) 3.2 K-means聚類算法的描述Step 1:從數(shù)據(jù)集中隨機(jī)抽取k個(gè)質(zhì)心作為初始聚類的中心；Step 2:計(jì)算數(shù)據(jù)集中所有的點(diǎn)到這k個(gè)點(diǎn)的距離，將點(diǎn)歸到離其最近的聚類里；Step 3:調(diào)整聚類中心，即將聚類的中心移動(dòng)到聚類的幾何中心即平均值處；Step 4:重復(fù)第2步和第3步，直到聚類的中心不再移動(dòng)，此時(shí)算法收斂。3.3 K-means聚類算法的重要問(wèn)題3.3.1 K值的選取3.3.2 初始中心點(diǎn)的選取 從算法的描述可見(jiàn)，初始類簇的中心點(diǎn)對(duì)聚類的結(jié)果的

5、影響非常大，一旦初始值選取得不夠好，那么可能導(dǎo)致無(wú)法得到有效的聚類結(jié)果。 假設(shè)要更好地解決該問(wèn)題，那么可以考慮遺傳算法。3.3.3 時(shí)間復(fù)雜度 算法的時(shí)間復(fù)雜度為O(N*K*T)，N為樣本的數(shù)量，K為類簇的數(shù)量，而T為迭代的次數(shù)。當(dāng)K和T均遠(yuǎn)遠(yuǎn)小于樣本數(shù)量N時(shí)，復(fù)雜度為O(N)，具有最優(yōu)復(fù)雜度。3.4 K-means聚類算法的總結(jié) K-means聚類算法的缺點(diǎn)：K值和初始中心點(diǎn)的選取困難；對(duì)噪聲點(diǎn)和孤立點(diǎn)很敏感，少量的該類數(shù)據(jù)將對(duì)中心點(diǎn)的計(jì)算產(chǎn)生非常大的影響；只能發(fā)現(xiàn)類球狀的類簇。4 聚類的最新開展 Rodriguez 10發(fā)表的文章，為聚類算法的設(shè)計(jì)提供了一種新的思路。 這個(gè)新聚類算法的核心

6、思想在于對(duì)聚類中心的刻畫上，作者認(rèn)為聚類中心同時(shí)擁有以下兩個(gè)特點(diǎn)： “距離相對(duì)更大； 考慮待聚類的數(shù)據(jù)集S=xi|i=1,2,N，dij=distxi, xj表示數(shù)據(jù)點(diǎn)xi，xj兩者之間的某種距離，IS=1,2,N為相應(yīng)的指標(biāo)集。對(duì)于S中的任何數(shù)據(jù)點(diǎn)xiii。4.1 聚類中心i的定義 它包括截?cái)嗪撕透咚购藘煞N計(jì)算方式。 截?cái)嗪耍篿=jISiX(dij-dc)(4-1)Xx=1, x0為截?cái)嗑嚯x，需要由用戶事先指點(diǎn)。 由定義易知，i表示的是S中與xi之間的距離小于dc的數(shù)據(jù)點(diǎn)的個(gè)數(shù)。 高斯核：i=jISie-(dijdc)2(4-3)i的定義 設(shè)qii=1N表示ii=1N的一個(gè)降序排列的下標(biāo)序，

7、即它滿足q1q2qN那么可定義qi=minqjjidqiqj,i2maxj2qj,i=1(4-4)4.1.3聚類中心的選取 至此，對(duì)于S中的每一數(shù)據(jù)點(diǎn)xi，可為其算得i,i,iIS。 考慮圖4-1A中的例子，它包含28個(gè)二維數(shù)據(jù)點(diǎn)，將二元對(duì)i,ii=128在平面上畫出來(lái)，i為橫軸，i為縱軸，如圖4-1B所示。都比擬大, 作為類簇的中心點(diǎn). 26, 27, 28三個(gè)點(diǎn)的i比擬大但i較小，而這三個(gè)點(diǎn)在原始數(shù)據(jù)集中式離群點(diǎn)。 所以類簇中心的特點(diǎn)是同時(shí)具有較大的和值。 。 但不是所有情況都可用肉眼判斷出聚類中心得情況。因此要計(jì)算一個(gè)將和值綜合考慮的量i=ii,iIS(4-5) 顯然值越大，越有可能聚類

8、中心，因此，只需對(duì)ii=1N做降序排列，然后從前往后選取假設(shè)干個(gè)作為聚類中心即可。 但對(duì)于確定聚類中心的個(gè)數(shù)也是一個(gè)問(wèn)題。圖4-2 降序排列的值示意圖 如圖4-2所示，把值作為縱軸，以下標(biāo)為橫軸，可見(jiàn)：非聚類中心的值比擬平滑，而從非聚類中心過(guò)渡到聚類中心時(shí)4.2 聚類算法描述 待聚類的數(shù)據(jù)集S=xi|i=1,2,N，設(shè)其包含nc(1)個(gè)類簇，而qii=1N仍表示ii=1N mjj=1ncxmj為第j個(gè)類簇中心 cii=1N：數(shù)據(jù)點(diǎn)歸類屬性標(biāo)記，即cici個(gè)類簇 nii=1Nxi大的數(shù)據(jù)點(diǎn)中與xinqi=argminqjj0； 2計(jì)算ii=1N并生成其降序排列下標(biāo)序qii=1N； 3計(jì)算ii=1

9、N及nii=1NStep 2: 確定聚類中心mjj=1nc，并初始化數(shù)據(jù)點(diǎn)歸類屬性標(biāo)記cii=1N，具體為ci=k，若xi為聚類中心，且歸屬第k個(gè)類簇-1，其他情況Step 3: 對(duì)非聚類中心數(shù)據(jù)點(diǎn)進(jìn)行歸類；Step 4:假設(shè)nc1，那么將每個(gè)類簇中的數(shù)據(jù)點(diǎn)進(jìn)一步分為類簇中心和類簇邊緣。4.3 聚類算法結(jié)果展示圖4-3 各種情況的測(cè)試結(jié)果 如圖4-3所示，該算法能夠很好地適應(yīng)各種不同形狀的類簇的情況，可拓展性比擬高。4.4 聚類算法小結(jié) Rodriguez 10提出的算法在本質(zhì)上是基于流形的做法。這一個(gè) 這一個(gè)聚類算法的思想十分的樸素，讓人十分訝異。但是卻表達(dá)了“簡(jiǎn)單就是美的這一哲學(xué)思維。 具

10、體上說(shuō)，文章有一些細(xì)節(jié)并不沒(méi)有深入討論，比方對(duì)距離的具體衡量方式是什么，但本身距離問(wèn)題本身就是一個(gè)活潑的研究領(lǐng)域，文章旨在提出一種聚類算法的新思路，而且具體問(wèn)題中會(huì)有各種各樣場(chǎng)景，還是需要根據(jù)實(shí)際問(wèn)題的了解選擇一個(gè)最適宜的距離會(huì)比擬好。5 總結(jié) 本文的具體脈絡(luò)是首先通過(guò)對(duì)聚類的概述引入各種不同類別的聚類算法的介紹，然后通過(guò)對(duì)最經(jīng)典，最容易理解的K-means聚類算法的具體描述和解釋，簡(jiǎn)單初步地對(duì)聚類算法給出一個(gè)具體的印象和作用。然后再通過(guò)Rodriguez 10的文章所描述的聚類算法，提供一個(gè)聚類算法的最新的思路，并由此契合了“簡(jiǎn)單就是美的這一哲學(xué)思維。 具體來(lái)說(shuō)，盡管聚類分析有著幾十年的研究

11、歷史,眾多聚類算法相繼被提出、相關(guān)的應(yīng)用被展開,但聚類問(wèn)題仍然存在著巨大的挑戰(zhàn)。一些對(duì)聚類算法的總結(jié),可以得出如下一些結(jié)論: 大多數(shù)聚類算法都需要預(yù)先給出參數(shù),事實(shí)上,如果沒(méi)有相關(guān)知識(shí)和經(jīng)驗(yàn),這在多數(shù)情況下是不可行的. 在很多文獻(xiàn)中,研究者們給出了各自的聚類算法評(píng)價(jià)指標(biāo),并只給出其算法的優(yōu)點(diǎn)。所以。 聚類算法的聚類結(jié)果有一定的不可預(yù)見(jiàn)性,在實(shí)際應(yīng)用中應(yīng)根據(jù)數(shù)據(jù)類型選擇適宜的聚類算法(和可恰當(dāng)?shù)南嗨菩远攘糠绞?,以取得最正確的聚類效果.針對(duì)不同數(shù)據(jù)集,進(jìn)一步開展聚類算法預(yù)測(cè)分類數(shù)的能力研究。參考文獻(xiàn)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