經典聚類算法研究綜述

鄧林培

摘 要 文章通過介紹4種經典的聚類算法以加強人們對聚類算法的了解，同時對每一種算法的適用情況和優勢劣勢進行闡述。聚焦于聚類算法發展所呈現的趨勢和應用情景中涉及的領域，感知聚類算法在機器學習甚至人工智能領域的強大生命力。

關鍵詞 人工智能；機器學習；聚類；K-means

中圖分類號 TP2 文獻標識碼 A 文章編號 1674-6708（2019）230-0108-03

從1956年的達特茅斯會議到如今，不過短短60多年的時間，人工智能發展之迅速令人驚嘆。人工智能領域十分廣泛，神經網絡、自然語言處理、遺傳算法、深度學習，甚至哲學問題和未來趨勢等都是這一大學科中的一部分。對機器來說，所謂智能，實質是由人對它輸入算法和數據，機器本身運用算法從數據中進行學習，并由此處理新的實際問題。不光算法，像自然語言處理，哲學問題都可以與機器學習結合。

機器學習中有許多算法。其中聚類算法是一個大的分支。針對不同數據類型，聚類算法中有各種不用運行理念、不同基準的算法可將不同類型的樣本數據收聚到較好的結果。聚類算法中經典的算法如K-means算法、均值漂移算法、DBSCAN算法和層次聚類算法在當下仍經久不衰。同時，聚類算法在信息技術和人工智能浪潮的推涌之下，呈現出融合的新態勢。

1 經典聚類算法研究

1.1 K-means

K-means算法是一種應用極為廣泛的聚類算法[ 1 ]。它的核心思想是用戶指定k個初始的質心（隨機數）作為聚類的類別，并重復迭代直至算法收斂。

首先，計算所有數據點到這k個初始質心的距離，并以這個計算出的距離作為下一步分類標準，也就是說，各數據點到哪個質心距離最近，便決定它在此次類別的分取中屬于哪一類別。那么，初始定義的k個質心就會在迭代中將所有數據分為k個類別也就是k個簇。待對每個樣本點進行了距離計算并類別歸屬之后，再重新計算k個簇中每一個簇對應的質心，即更新質心。每個簇數據明朗，質心實際可求，于是，對所得的每一個簇的所有數據點求新質心，再以此質心替換隨機數質心做為新的距離計算標準，重復距離近便成一簇的過程。之后繼續重復質心更新和數據分簇過程，直至質心更新時，每簇的質心不再變化或僅有微小變化時，算法停止。最后所得的k個最終質心及它們所在簇包含的樣本點，即所期望的聚類結果。

K-means算法中k值也就是聚類的類別數是需要用戶自己定義的，當遇到一個復雜的數據結構，可能需要多次嘗試才能選取到一個較好的k值，使這個樣本數據聚成如此多個類才是最優的。

我們可以發現，因在最初的算法迭代中選取的初始質心為隨機定義而來，會致使聚類效果不好，迭代次數增多，可能僅得到局部最優結果。局部最優是K-means算法乃至機器學習算法存在的普遍問題。同時，K-means算法僅適用于數據聚類，并且在噪音數據出現時，由于其算法的原理，以距離平方和為準則，會使一些不合理的極端數據影響聚類結果。

針對它的這些缺陷，K-means算法衍生出的變種k-modes算法和K-prototype算法在一定程度上彌補了K-means算法的不足。

K-modes算法適用于離散型非數值型的集合，如時間、文本、顏色、大小等。它是以屬性來度量兩樣本的相關性D。比較兩樣本所有屬性，若屬性不同就給D加1，相同就加0。也就是說，D值越大，兩樣本就越不相關。這不相關程度越大就相當于k-means中的距離越遠。接著以每一簇中出現頻率最大的屬性值來代表那一簇的屬性，不斷更新簇，更新代表屬性，重復迭代。

K-prototype算法是對K-means算法和K-modes算法的結合，它適用于樣本記錄里面既有離散型數據又有數值型數據的集合。它結合K-means得到數值屬性和結合K-modes得到分類屬性，最終通過權重來得出樣本混合屬性。其更新也是兩者結合，并重復迭代得出結果。

當然，K-means算法以其運算迅速，操作簡單易行等優勢仍在各領域有著廣泛的應用。

1.2 均值漂移聚類

與K-means相似，都是基于質心的聚類算法。均值漂移算法[ 2 ]依賴于自定義半徑的圓形滑動窗口的移動。窗口會一直向著能使圓內數據點密度增大最快的方向靠近，直至窗口無論再向哪個方向移動，都無法再使更多點被包括進窗口內，即窗口內數據密度不再增加時，窗口才不再滑動。它與K-means的相似之處是它也需要先隨機選取窗口中心值和窗口半徑，待窗口滑到新的數據區時，中心值便隨之更新，即把窗口內所有數據點的平均值作為新的中心點而繼續滑動。

均值漂移算法的優點在于不需要我們事先確定類別數目，當初始的中心點數目足夠，它會自發收斂到密度最高的幾個區域。

此算法對密度分布差異較大的數據聚類效果好且受均值影響較小。但對分布均勻的數據來說，均值漂移算法收斂效果較差。

1.3 DBSCAN算法

DBSCAN是一種基于密度的聚類算法[ 3 ]，它的聚類思想是以密度可達關系導出可得的最大密度相連樣本集合，此即為聚類出的一個簇。

6）另取核心對象重復上兩步步驟。DBSCAN適用于任意稠密數據，對數據里的噪聲數據不敏感，聚類結果相對受其他因素干擾較少，可避免出現K-means受初始值影響大的情況。但正是由于其基于密度的算法特性，如果樣本密度不均，會導致出現聚類質量低的情況。且如果樣本數據多，DBSCAN聚類收斂耗時會較長，并不理想。

1.4 層次聚類算法

層次聚類包括自下而上的凝聚聚類和自上而下的分裂聚類方法[ 4 ]。

其中凝聚聚類要求我們首先得把每個數據點視為一個單一的簇，再將距離最近的兩個簇合并。這里就需要我們選定一個距離度量標準。例如我們可以使用簇間距離，即第一個簇中的數據點與第二個簇中的數據點之間的平均距離作為標準來進行合并。合并后重新計算各簇間距離，重復合并步驟，直到聚類成一簇或達到預設條件方可結束算法。

而分裂聚類與凝聚聚類恰好相反，它意在將一個大的數據集分裂成許多小簇。先將所有對象置于一個類中，然后逐漸分出小簇，使總數據集變為越來越小但個數越來越多的簇，直到每個對象獨自成簇或滿足了一定的終止條件。例如達到了我們希望的聚類簇數目，結束算法。

層次聚類不需要我們提前知道需要合成或分割所得的簇的數目，同時它可以使用多種距離計算方法來計算簇間距離，但也正是距離計算量大，層次聚類并不迅速，效率低。

2 聚類算法的發展趨勢與應用前景

2.1 發展趨勢

正如人類認識社會，需要區別不同事物，聯系相同相似事物一樣，數據的挖掘、處理也離不開聚類分析。在這個數據爆炸的時代，聚類算法大有用武之地。公司對目標顧客的分析，市場銷售的調研等等都與聚類算法有著密切聯系。不難發現，聚類算法中不同類型的算法有著不同適用領域，但每個算法都并不完美。各個算法之間存在一種相互彌補相互結合的關系，正與現代社會發展，領域不斷更新，各領域數據變得更龐大更多元更復雜的趨勢相適應。這無疑對算法提出了更高的要求，孤立的算法已經并不完全適用于這個時代。

2.2 應用前景

聚類算法可應用于圖像分割、機器視覺、數據壓縮和信息檢索，它功能強大，譬如檢索時可以使檢索時間縮短并且擁有更高的精確度。它還應用于一些生活中常用的軟件，如知識管理系統里的知識共享、知識推薦功能，學生成績統計分析軟件對成績的深度挖掘功能。

聚類算法可應用于建立數據庫，其中的文本聚類算法還被用來建立詞義網（Word Net）。隨著時代的發展，聚類算法的應用領域已從商業金融拓展到了教育互聯網等行業，同時對生物學、心理學、考古學、地質學的研究也都有重要作用。

3 結論與展望

聚類算法的發展已經到了一個融合互補的時期，它所包含的孤立的經典算法雖仍然能得到較為廣泛的應用但終會逐漸追逐不上時代日新月異的復雜變化。時代發展要求數據結構向著更復雜更靈活的方向發展。聚類算法要想繼續能將機器學習進行得正確而高速，勢必要在原本的經典算法的基礎之上，做出符合時代數據特征的創新。

在筆者看來，完美倒不是一件幸事，只有在對不完美的修正與創新中，才能擦出新的思維火花，在成果不斷更新被淘汰更新再換代的過程中，人類的智慧才得以更大可能的激發，社會才得以不斷進步。正因如此，聚類算法的未來，是互相融合互相補充的未來，是不斷改進與簡化的未來，至少以后的一段時期內，它的未來前景不可小覷。

參考文獻

[1]楊善林，李永森，胡笑旋，等.K-means算法中的K值優化問題研究[J].系統工程理論與實踐，2006，26（2）：97-101.

[2]周芳芳，樊曉平，葉榛.均值漂移算法的研究與應用[J].控制與決策，2007，22（8）：841-847.

[3]榮秋生，顏君彪，郭國強.基于DBSCAN聚類算法的研究與實現[J].計算機應用，2004，24（4）：45-46.

[4]史變霞，張明新.一種改進的層次聚類算法[J].微電子學與計算機，2010，27（12）：55-56.