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

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

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

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

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

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

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

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

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

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

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

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