聚類分析算法概述及其適用性比較

印曉天 湛高峰

摘 要：聚類算法作為大數據與人工智能領域重要的分析工具，受到了學術界的高度關注與廣泛研究。本文從算法設計思想的角度對現今主要的聚類算法進行了歸納總結。具體來講，針對中心聚類法、層次聚類法、密度聚類法、譜聚類法以及一些其他聚類算法分析了各自算法及其思想的優缺點與適用性，對算法的實際應用建立指導性作用。

關鍵詞：聚類分析 算法 適用性

中圖分類號：TP311 文獻標識碼：A 文章編號：1672-3791（2018）11（c）-0230-03

聚類分析作為機器學習的重要分析手段，是當前大數據時代下的熱點研究領域之一。在過去數十年間，產生了大量的聚類分析算法。本文對目前主流的聚類算法進行歸納總結，并對各自的優缺點和適用性進行比較分析。

通俗來講，聚類算法的目標是將具有共性的樣本歸為同一類型，而將沒有或者少有共性的樣本歸為不同類型。數學上對于共性的度量常用樣本之間的距離來衡量，而如何定義距離則需要根據實際情況具體分析。因此，聚類算法的目標是得到一系列內部聯系相對緊密、外部聯系相對稀疏的樣本集合（又稱為類簇）。聚類算法按實現方式，主要可以分為中心聚類、層次聚類、密度聚類、譜聚類等。下面就以上各類型聚類算法逐一介紹。由于本文著重分類介紹算法的思想，旨在分析各類算法的優缺點及其適用性，所以在介紹的時候不會拘泥于參數細節，而強調執行過程是如何體現算法思想的。具體的算法實現過程可參考相應文獻。

1 中心聚類法

中心聚類法是一類極為常見聚類算法。它以找各類簇的中心為基本任務，將離某中心最近那些點歸為該中心所代表的類簇。中心聚類的代表性算法是K-means[1-2]。K-means算法的執行是一個迭代的過程，以正整數K作為超參數，在每輪次更新K個類簇的中心。具體來說，給定空間中樣本點集合作為輸入，初始時算法以某種方式選定K個空間中的點作為K個類簇的初始中心點，這種選取方式可以是隨機的，也可以是根據輸入樣本的特征先驗選取。在每輪迭代的過程中，對每一個輸入樣本，計算他們到各個中心的距離，將其歸入距離最近的中心所代表的類簇中，這將得到一個樣本的類別劃分。然后對每一個聚類計算其新的中心，計算方式通常是取類簇中各自樣本集合的平均值，作為下一次迭代的中心。迭代直到每個類簇的中心相較于上一輪迭代的中心都僅產生足夠小的位移為止。

K-means算法的優點是計算簡單，迭代收斂速度快，尤其適合歐式空間中按向量和歐式距離定義的樣本聚類。但是其缺點也很明顯，最大的缺點是需要事先選定一個超參數K。一般在樣本數目很大的應用中，對于類別數目沒有先驗知識時，這個參數不好估計，通常需要對各種給定的值進行試探。其次，K-means算法找到的類簇中心由于類簇中樣本分布不定的原因，可能落在樣本分布稀疏的地方，導致與直觀上的聚類中心不符。為了克服這個問題，

人們提出在每次更新各類簇中心點的時候限制其在樣本點上選取，這就是K-medoids算法[3]。此外，還有高斯混合模型聚類，可以視為K-means算法的擴展，它假設類簇的各維度服從高斯分布，從而保證類簇中心的稠密性與類簇的凸性。另一個問題是K-means算法得到的類簇之間是剛性劃分，沒有重疊或軟性隸屬關系，這在某些應用場景中是與事實不合的（之后我們會看到，這也是大部分聚類算法的通病）。為此，人們提出模糊（Fuzzy）c-means聚類算法[4-5]，即設定在各類簇邊緣的樣本點可以依一定概率屬于多個類簇，概率值大小反映樣本對于該類別的隸屬程度。

2 層次聚類法

層次聚類法是另一類極為常見聚類算法。它的思想是通過逐層次的劃分方式將樣本點分成若干類簇的集合。層次聚類法一般把樣本及其之間的距離建模成帶權圖，其中包含頂點、邊以及邊的權重等參數。通常啟發式地有兩種層次劃分方式，即自頂向下的分裂法和自底向上的凝聚法。分裂法從初始將所有樣本視為同一類開始，通過某種規則將當前的每一個類簇拆分成兩個，直到每個類簇達到終止條件為止。而凝聚法則相反，它從初始將每一個樣本都視為不同類別，也是通過某種規則將當前的類簇兩兩合并成，直到每個類簇達到終止條件為止。

層次聚類法的拆分或者合并規則通常是基于某種特定的指標。分裂法中類型拆分的依據常用的是平衡割（Balanced Cut）。平衡割指的是移除之后能將圖分割成大小或體積相差不多的兩個子圖的邊的集合，分裂法中找的是權重之和最小的平衡割。之所以要求兩個子圖大小或體積相對平衡，是為了防止計算過程中出現僅僅為了達到數學上的極小值，而在圖中的一個小局部進行切分的情況，而這樣零散的小局部聚類通常不能很好地反映樣本的共性，且過于細小的切分通常也不是我們需要的聚類方式。當然，解決這一問題還有其他的指標，如稀疏割（Sparsest Cut）等。

凝聚法中通常有一個目標函數，算法在每輪次凝聚的過程中貪心地選取使得目標函數值優化最多的兩個類型的樣本集合進行合并，直到目標函數無法繼續優化或者達到其他終止條件為止。這個目標函數是定義在全樣本及其聚類劃分上的，它的大小從某種直觀上反映了該樣本劃分定義的聚類的質量。目前使用最為廣泛、最有代表性的目標函數是模塊性（Modularity），它反映的是在該劃分下的聚類程度與保持頂點度數不變的隨機連邊的聚類程度之間的差距。這一正向差距越大，表明該劃分的聚類效果越好。近年來有學者提出了圖的結構熵（Structural Entropy）的概念，從圖中隨機游走編碼極小化的角度定義了圖的K-維結構熵，并設計了基于二維結構熵極小化的凝聚聚類算法。

分裂法聚類的優點在于其算法過程完全是基于人們對聚類方式的直觀理解，思路清晰明確，因此效果一般較好，并且算法的遞歸過程天然地給出了樣本的層次聚類劃分，將樣本類型之間的距離以及樣本類型的更高層次聚類關系都展示了出來。但是缺點是計算過程緩慢，因為每輪迭代均要在當前子問題中求全局的劃分方式，且不論找最小平衡割的計算困難性，單是子問題的遞歸次數就已經與樣本規模成正比。而找最小平衡割的問題本身是困難的，有效時間內只能找到近似解。另一個問題是，分裂法的算法終止條件需要人為設定，即到底劃分到多細就（才）能滿足需要。這樣的條件需要對樣本有一定的先驗，或者取不同的參數進行多次嘗試。

凝聚法聚類的優點在于執行速度快，貪心凝聚的迭代過程中，目標函數的增量無論模塊性還是二維結構熵均能局部計算，因此以堆作為輔助的數據結構，這兩種算法均能在幾乎線性時間內完成。與分裂法相比，凝聚法的另一個優勢是它的目標函數清晰，所以終止條件明確且具有可解釋性。它的缺點是由于樣本的局部微觀結構導致初始時樣本的聚類方式比較任意，并且之后的算法執行過程中聚在同一類簇中的樣本無法再分開，從而就有可能造成最終的結果雖然使得目標函數值較優，但是與真實的聚類方式差距較大。當然，為了克服這一缺點，可以增加一些在貪心迭代過程中的樣本遷移策略來糾正初始時的錯誤。

3 密度聚類法

密度聚類法將內部連續稠密的樣本子集視為同一類型，代表性算法是DBSCAN（Density-Based Spatial Clustering of Applications with Noise）。DBSCAN算法首先將所有樣本點區分為核心點和非核心點，其中核心點指半徑r以內樣本點數目大于k的那些點，這里r，k均為參數。如果兩個核心點的距離不超過r，則稱之為直接密度可達。經過多次直接密度可達的核心點稱為密度可達。一個極大的密度可達的核心點子集并上其中各核心點半徑r以內的非核心點，即構成一個類簇。可以看到，DBSCAN算法得到的各類簇之間的核心點集不交，但非核心點集可能相交，并且還可能存在某些非核心點其r半徑內不包含任何核心點，這被視為噪聲。因此，DBSCAN算法允許類簇有重疊，也允許某些點不從屬于任何類簇，是其他大多數聚類算法所不具備的優勢。而DBSCAN算法的缺點是它用一個統一的尺度r和k來衡量所有類簇，很多時候這樣是不合適的。因此，人們提出了改進版本OPTICS（Ordering Points To Identify the Clustering Structure）算法，將半徑r設為靈活的參數，由算法自身來調節，但思想上與DBSCAN是統一的。

另一個基于密度的聚類算法是團滲透（Clique Percolation）算法。團是圖論中的經典概念，一個大小為k的團就是指k個點的完全圖。團滲透算法主要針對的是無向圖中的聚類問題。它以一個正整數k作為參數，首先找到圖中所有的極大團（即不存在更大的團以該團作為子集），然后當兩個極大團的交集大小為至少k-1時將兩個極大團合并，視為同一類簇。算法執行過程中是從一個極大團出發找與其交集大于等于k-1的“鄰居”團，如同液體的滲透蔓延，故而得名。以團作為類簇組成的基本元素在某些應用中是十分合理的，比如社交網絡，但k的取值不宜過大，通常取3或4即可，否則對類簇稠密度要求太高，不易找到合理的類簇。不難發現，團滲透算法也能找到重疊類簇。但是其缺點是對于類簇內部密度要求較高，且只能適用于圖的聚類，應用場景有很大的局限性。

4 譜聚類法

譜聚類（Spectral Clustering）是一種針對圖聚類的基于譜圖理論的聚類算法。它將圖中的每個頂點先用代數方法向量化，然后調用其他經典的聚類算法對向量樣本聚類。雖然算法執行步驟是代數的，但其直觀基于最小化各類簇的擴張性（expansion）。一個點集擴張性是指該點集向外聯系的邊的數目比上自身的大小，因此這是一個既考慮向外聯系的緊密程度又同時考慮類簇自身大小的數學量。算法執行過程首先計算圖的拉普拉斯矩陣的最小的k個特征值，這個k的設定需要根據特征值的分布，使得拉普拉斯矩陣的主要特征向量被指使出來。之后將這k個特征值對應的長度為n（n為頂點數目）的特征向量按各頂點分量構成k維向量并歸一化，再用其他聚類算法對這n個向量樣本進行聚類。譜聚類算法的優點是它可以處理聯系非常稀疏的樣本，并且它給出了一個對高維數據進行降維的方法。但缺點是由于涉及矩陣運算求特征值和特征向量，計算復雜度較高，且需要一個處理向量聚類的算法做輔助。

5 其他聚類方法

還有其他一些聚類方法沒有被歸入以上4種，如標簽傳播聚類法、神經網絡聚類法等。標簽傳播（Label Propagation）算法運用了隨機游走的思想，用當前頂點的標簽去預測下一步其鄰居的標簽。算法初始時可以有一些標注好的頂點，其標簽代表其所屬的真實類型，而其他頂點可隨機賦予標簽。算法迭代執行的每一步都視為每個頂點以隨機游走的方式將標簽傳給其鄰居，因此需計算每個頂點獲得其鄰居標簽的概率，但實現的時候只需計算矩陣與向量的乘法即可。然后除已標注頂點外，其他頂點獲得概率最大的那個標簽，多個概率最大標簽之間任意選取即可。算法執行至所有頂點標簽不再發生改變為止。可以看出，距離越近的兩個頂點之間越容易獲得共同的標簽。標簽傳播算法的優點是簡潔直觀，計算速度快，雖然在某些極端情況下算法不收斂，但實際問題中很難遇到這種情況。由于算法允許一些標注樣本的存在，所以標簽傳播也是一種簡單高效的半監督算法。其缺點也很明顯，由于初始對于非標注頂點的標簽是隨機賦予的，這使得算法結果差異很大，影響準確性。另外還有一類基于特定神經網絡模型的聚類算法，自組織映射（Self Organizing Maps）神經網絡算法。由于神經網絡的原理解釋仍是目前學術界的一大難題，所以這里所用的思想還并不明確，需要進一步探究，我們在此也不詳述。

6 結語

本文總結了目前常用的聚類算法，并按算法思想分類，闡述了基于其思想的算法實現過程，分析了優缺點與適用性。總體來說，沒有任何一個算法可以適用于所有的需求，需要根據實際應用場景選擇最適合的聚類算法。

參考文獻

[1] S. P. Lloyd. Least square quantization in PCM[A].Bell Telephone Laboratories Paper，Published much later in IEEE Transactions on Information Theory[C].1982：129-137.

[2] E. W. Forgy. Cluster analysis of multivariate data： efficiency versus interpretability of classifications[J]. Biometrics，1965（2）：768-769.

[3] L. Kaufman and P.J. Rousseeuw. Clustering by means of medoids[A].In Statistical Data Analysis Based on the L1-Norm and Related Methods[C].North-Holland，1987：405-416.

[4] J. C. Dunn. A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters[J].Journal of Cybernetics，1973（3）：32-57.

[5] J. C. Bezdek. Pattern Recognition with Fuzzy Objective Function Algorithms[Z]. ISBN 0-306-40671-3，1981.