幾種經典聚類算法的比較研究

呂曉丹

（湖北汽車工業學院汽車工程師學院 湖北省十堰市 442002）

聚類算法是一種無監督學習算法，與監督學習不同的是，無監督學習算法的數據都是沒有標簽（類別）的。聚類算法的最終目標是通過樣本點的內部特征將數據集中的樣本點劃分為若干個子集，每一個子集稱之為一簇。那么，聚類的最優準則就是：簇內相似度高且簇間相似度低[1]。作為一種深入挖掘數據內在聯系的算法，聚類分析已經被廣泛應用在機器視覺、圖像處理、自然語言處理、生物信息、模式識別等眾多領域中[2-3]。

通常，我們將經典聚類算法分為四大類：

（1）基于劃分的聚類算法：這種方法首先指定簇的數量k，然后按照一定的劃分標準（比如歐式距離）將所有數據點進行劃分，使得每個簇內部的點之間相似度高且不同簇的數據點間相似度低。典型的有：K-means算法、K-medoids 算法、K-modes 算法。

（2）基于密度的聚類算法：這種方法不需要事先指定簇的數量k，而是根據密度將處于同一密度區域的點歸結為一類，同時忽視密度低或者孤立的數據點。代表性的算法有：DBSCAN算法、Density Peak Cluster算法。

（3）基于模型的聚類算法：這種方法首先構建數據集遵守的函數模型，然后通過最小化誤差的方法來確定模型參數和簇的劃分。代表性的算法有：Spectral Cluster 算法、高斯混合模型、神經網絡聚類等。

（4）綜合聚類算法：這種方法融合了兩種以上的數學思想或聚類算法，形成新的綜合性聚類算法。代表性的算法有：FCM 算法、模糊神經網絡聚類算法。

本文從四大類聚類算法中分別選取K-means 算法、Density Peak Cluster 算法、Spectral Cluster 算法和FCM算法作為比較研究對象，再從算法原理和對比實驗兩個方面來分析這幾種經典算法的異同和優略。

1 算法原理分析

1.1 K-means算法

K-means 算法又稱K-均值算法，它是由美國加州大學的J.B.MacQueen 在1967年提出來的。K-means 的主要算法流程如下[4]：

（1）K-means 算法會預先設定簇數為K。

（2）隨機選擇K 個樣本點作為初始簇中心，并計算數據集中每個樣本點到簇中心的歐幾里得距離。

（3）根據“就近原則”將樣本點分配到距其最近的簇中心所在的簇中。

（4）重復執行第2 步和第3 步的內容，直到達到最大的迭代次數或者簇中心不再變化為止。

由上述K-means 的算法流程可知，在K-means 中將兩點間的歐式距離作為樣本點間相似度的度量標準，也就是說兩個樣本點的空間歐式距離越近，則它們相似度越高，也就會被劃分到同一個簇中去。K-means 算法簡單直觀、易于實現、便于解釋。當簇是團狀、球狀且子簇之間存在一定距離時，便可以體現出K-means 算法良好的聚類效果，這是因為K-means 算法以歐式距離作為相似度的度量標準。但是，由于K-means 算法采用貪心策略，會導致算法陷入局部最優解。與此同時，當以歐式距離作為相似度度量標準時，就會導致K-means 算法對初始點的選擇和噪聲點離群點都十分敏感，導致算法效果不太穩定。

1.2 Density Peak Cluster算法

Density Peak Cluster 算法（簡稱DPC 算法）又稱密度峰值聚類算法，是由Alex Rodriguez 和Alessandro Laio 兩位學者于2014年提出的，相關成果發在SCIENCE期刊上[5]。

DPC 算法蘊含著一個假設，即：假設聚類中心擁有較高的本地密度并且距離其他高密度點有相對較遠的距離。其次，通過公式（1）和公式（2）分別計算每個點的本地密度ρ和與所有高密度點的相對距離的最小值δ。緊接著，將所有點的本地密度ρ 和相對距離最小值δ 繪制成一張決策圖，手動選取擁有高ρ 值和較高δ 值的點作為聚類中心點，最后將剩余的點依照“就近原則”分配到相應中心點所在的簇中。

DP 算法考慮了數據空間分布的特點，因此可以在對密度敏感的數據集上取得不錯的效果，與此同時它的算法復雜度比K-means 低。但是，由于它需要提前計算所有點的本地密度和相對距離，所以內存開銷較大，不便于大數據量的處理。

1.3 Spectral Cluster算法

Spectral Cluster 算法又名譜聚類算法，它的思想源自圖劃分理論。在圖論中，將數據集中的所有樣本點都視作圖的頂點V，將樣本點之間的連接視作圖的加權邊E，于是可以形成一張加權圖G（V，E）。聚類問題實質上就是圖G 的劃分問題，圖劃分成的一個個子圖就是數據聚類后得到的一個個簇。根據最優的聚類準則，最優的圖劃分方法具有如下特點：

（1）劃分后不同子圖之間邊的權重和盡可能小。

（2）劃分后同一子圖內部邊的權重和盡可能大。

此時，定義一個目標函數RatioCut：

在式（3）中，A1......Ak 代表分割后形成的k 個簇，代表簇A 和其他簇的相似度，代表簇Ai 的節點數。譜聚類問題就轉換成求RatioCut 最小值的問題，然而直接求解往往十分困難，可以通過定義圖G 的相似度矩陣W（公式（4））、拉普拉斯矩陣L（公式（5））及n 維向量f（公式（6）），然后經過一系列公式的推導（公式（7）），最終將求RatioCut 最小值的問題轉換成在需滿足公式（8）和公式（9）的前提條件下求解拉普拉斯矩陣最小特征值的問題。具體推導過程如下：

此外，由于拉普拉斯矩陣是一個半正定對稱陣，所有的特征值都大于等于0。而當L 的特征值是0 時，對應的特征向量是單位陣E，很明顯E 不滿足公式（9）中的限定性條件。根據Rayleigh-Ritz 原理，第2 小的特征值乃至于第n 小的特征值都是可用的。

于是，得到如下譜聚類算法流程[6]：

（1）構建一個相似度矩陣W，其中第i 行第j 列元素Wij代表樣本點i 和樣本點j 之間的相似度，它的計算方法見公式（4）。

（2）根據公式（5）計算相似度矩陣W 的度矩陣和拉普拉斯矩陣L。

（3）求得拉普拉斯矩陣L 的全部特征值，并按照遞增的順序排列。

（4）獲得前k 個特征值和對應的特征向量，將這k 個特征向量組合成一個n*k 的矩陣，對該矩陣的每一行執行K-means 聚類，最終每行的類別就代表原始空間中每一個樣本的類別。

從公式（4）可以看出譜聚類改進了相似度的度量方式，從一定程度上考慮了數據空間分布的特點，適合非凸流行數據；從第4 步可以看出，譜聚類實際上做了一定的降維操作，因而對高維數據有著較好的處理效果。但是，譜聚類仍然存在計算量大、時間復雜度和空間復雜度高、數據的先驗信息利用不足等問題。

1.4 FCM算法

FCM 算法的英文全稱是Fuzzy C-means Clustering，它是一種模糊聚類算法，融合了模糊數學的軟化分思想和聚類分析的原理。不同于硬劃分理論，FCM 算法通過隸屬度來確定每個數據點xi 屬于某一類j 的概率uij，也就是說一個點可能有40%的概率屬于A 簇，也有60%的概率屬于B 簇，而不是百分之百屬于某一個簇。

FCM 算法的主要流程是[7]：

（1）指定聚類數目k 和模糊系數m，并初始化隸屬度矩陣U。

（2）更新聚類中心vj

（3）更新隸屬度矩陣

（4）重復步驟2 和步驟3，直到兩次得到的隸屬度矩陣差距較小時或者達到最大迭代次數。

2 對比實驗驗證

為了將四種典型聚類算法的效果進行更為直觀的對比，本部分將進行聚類準確率對比實驗。

本文中的實驗環境含PC 機一臺，具體配置如下：

（1）CPU 為Intel(R)Core(TM)I5-6200U CPU@2.30GHz 2.4khz;

（2）內存空間是4G;

（3）編程軟件是 MATLAB;

（4）編程語言是m 語言。

本實驗采用單一變量原則，對K-means 聚類算法、FCM 聚類算法、Spectral Cluster 算法、Density Peak Cluster 算法在三個UCI 數據集[8]上進行聚類準確率的定量對比分析。

所謂UCI 數據集，指的是由加州大學歐文分校提出的一種適合模式識別和機器學習方向的開源數據集，很多學者會選擇使用UCI 上的數據集來驗證自己算法的正確性。到目前為止，UCI 共維護了622 個數據集，并且在持續更新中。這些數據集主要分為二值分類問題、多分類問題以及回歸擬合問題。

本文選取UCI 數據集中的BreastCancer、Transfusion和Ecoli 三個子集。其中，Breast Cancer 數據集是由威斯康星大學診療中心和計算機科學研究所發布的乳腺癌數據集，它包括了乳房腫塊的FNA 數字化圖像的計算特征。具體包含半徑、文理、周長、面積、平滑度、緊湊度、凹度、凹點、對稱、分形維數等十個實值特征和一個標簽信息（良性或者惡性）。Transfusion 數據集是一個獻血者數據庫。它包括最近一次獻血后的月數、獻血總次數、獻血總血量、首次獻血后的月數等四個特征和一個是否在2007年3月獻血的標簽。Ecoli 數據庫給出大腸桿菌基因組中每個ORF（潛在基因）特征的數據。提供了序列、同源性（與其他基因相似）、結構信息和功能等七個特征。三個UCI 數據集的簡介如表1所示。

表1：UCI 數據集簡介

依照慣例，我們采用聚類準確率作為衡量算法優略的核心指標，將四種聚類算法在三個UCI 數據集上的聚類準確率用表格的方式呈現出來。

由表2 可以看出：四種算法在三個數據集上的表現各有千秋。在BreastCancer 數據集上，FCM 算法的聚類準確率最高且達到0.6032，這一數據說明有超過60%的數據點會被正確聚類；在Transfusion 數據集上，Spectral Cluster 算法則表現最為突出，其聚類準確率達到了0.5267；在Ecoli 數據集上，聚類準確率最高是Density Peak Cluster 算法，它的準確率是0.7045，這一數字遠高于K-means 算法的0.0221、FCM 算法的0.2022和Spectral Cluster 算法的0.1875。

表2：實驗結果--聚類準確率

在K-means 中，利用歐式距離來度量樣本點之間的相似度，無法同時體現數據空間分布的全局一致性和局部一致性特征，因而對于具有高維特征的三種UCI 數據集效果都不太理想。FCM 算法采用軟化分的思想，對代價函數采用迭代的方式進行最小化，這種方式與數據維度無關，對擁有高維特征的BreastCancer 數據集具有較好的聚類效果。Spectral Cluster 算法通過指數化的相似度度量方式，充分考慮了數據空間分布的一致性問題，因而對于非凸流型數據集Transfusion 具有良好的聚類效果。Density Peak Cluster 算法通過設立“中心點本地密度高且遠離其他高密度點”的中心點假說，進一步構建決策圖，讓用戶手工選定聚類中心的方式來聚類，該算法尤其適合密度敏感的數據集，比如在Ecoli 數據集上該算法的聚類準確率超過70%。

3 結論

本文對K-means、FCM、Spectral Cluster、Density Peak Cluster 這四種經典聚類算法進行了理論分析和對比實驗。通過理論和實驗的對比研究，得出四種算法分別適合不同類型數據集的結論：K-means 算法更適合有明顯距離區分度的數據集；FCM 算法適合高維數據集；Spectral Cluster 算法在非凸流型數據集上有著較好的聚類效果；Density Peak Cluster 算法在密度敏感的數據集上效果不錯。

因此，在做聚類分析時，需要根據數據的特點來選擇相應的聚類算法，方可達到事半功倍的效果。