紀漢霖，李兆信

(上海理工大學，上海 200093)

0 引 言

聚類是重要而基礎的數據分析和挖掘的算法，在金融、教育、醫(yī)療、互聯(lián)網等方面有著廣泛的應用。聚類屬于無監(jiān)督學習范疇，在沒有數據標簽的條件下，可以依據數據之間的相似度(如距離)對數據進行先驗的分組，從而使得分組內的數據相似度盡可能高，分組之間的數據差異度盡可能大。

聚類算法在人工智能熱潮的推動下飛速發(fā)展，算法的種類不斷增多。如何為不同類型的數據集匹配恰當的聚類算法進而挖掘出數據集中的有效信息，是當下研究的熱點與難點，因此對聚類算法在不同數據類型中的效能和敏感性的對比分析是一個值得研究的課題。

1 聚類算法的分類

自Lawrence Hubert[1]于1972年提出聚類算法至今已經將近半個世紀，在這幾十年中學者們已經提出了上千種聚類算法[2]。聚類算法通過結合各個學科的技術和特點，融合發(fā)展為一個跨學科的方法，進而可以通過多種視角和方法對聚類算法進行歸類。聚類算法可以分為傳統(tǒng)方法和新方法兩大類，傳統(tǒng)的劃分有層次聚類(HC算法和Birch算法)、劃分式聚類(K-means)、基于密度的劃分(DBSCAN)、基于網格的劃分等(以STING和CLIQUE為代表)，近年來也有一些新發(fā)展的方法：基于約束的劃分、基于模糊的劃分、基于粒度的劃分、量子聚類、核聚類、譜聚類[3-5]，如圖1所示。

圖1 聚類算法的分類示意圖

以上這些算法大多是基于數據的特性而衍生出來的，導致算法對很多數據類型的適用效果并不好。因此在聚類研究中，學者們更側重于在特定數據集的基礎上對算法進行研究和改進。劉曉勇等(2011)[6]通過在AP算法中加入收縮因子，在服從[0,1]上均勻分布的模擬數據點上驗證了相關改進能夠加速算法的收斂速度。趙玉艷等(2008)[7]通過在BIRCH算法中加入ID傳播并改進近鄰密度的計算方法，在Manku GS和Motwani R(2002)[8]的DSI數據集上驗證了相關改進能夠加強算法的伸縮性并提高算法準確度。胡慶輝等(2013)[9]通過對GMM算法的系數中加入熵懲罰因子，在基于高斯分布而生成的人工數據集上驗證了相關改進能夠加快迭代速度并且可以提高魯棒性。陳黎飛等(2008)[10]通過構建聚類質量曲線確定層次聚類的聚類數目，在真實數據和人工合成數據集的基礎上驗證了相關改進能夠對數據進行更好的劃分。周林等(2012)[11]通過在譜聚類算法中使用連接三元組算法，在由加州大學UCI(University of California Irvine)數據庫中選取的數據集上驗證了相關改進能夠提高簇內數據相似度和計算效率。周愛武等(2011)[12]通過提出一種新的方法來確定K-means的聚類中心，在由UCI數據庫中提供的數據集上驗證了相關改進能夠降低孤立點對算法的影響。

在算法性能方面，之前的學者主要是對AP、Birch、GMM、HC、K-means等主流聚類算法在特定數據集上進行相關改進和研究，然而卻很少對算法在不同數據集上的表現進行相應的研究。即使在對算法進行橫向研究比較時，選用的數據測試集也多是來自加州大學UCI數據庫(UCI數據庫由真實數據生成的標準測試集組成)。馮曉蒲等(2010)[13]使用UCI數據庫中的IRIS對K-means、層次聚類、SOM和FCM四種算法做了對比研究，結果顯示FCM和K-means的聚類效果比較好，層次聚類算法的聚類效果最差，SOM的效率最低。與之前學者研究不同的是：文中利用由機器生成的數據集對算法進行橫向的研究，數據類型分為三類：離散型小數、離散型整數和連續(xù)型正數。

對比分析了Affinity Propagation、Birch、Gaussian Mixture Model、Hierarchical clustering、K-means和Spectral六種聚類算法，采用Silhouette Coefficient和Calinski-Harabaz Index為聚類評價指標對算法做了性能測試，采用算法在數據集上CPU消耗的時間作為評價指標對算法做了效率測試，以及在由不同數量級組成的數據集上對算法進行了敏感性分析。

2 聚類算法概述

(1)Affinity Propagation聚類算法。

AP算法是由Frey B J和Dueck D于2007年在科學雜志上最先提出來的聚類算法[14]，之后一直受到后來學者的關注與研究。AP算法對數據的特性沒有要求，數據集結構可以是對稱的也可以是非對稱的。AP算法不需要提前設定聚類中心的個數，因為該算法把數據集中的數據點作為潛在的聚類中心，通過算法的不斷迭代確定出聚類中心的數據點。

該算法通過計算出數據點之間的相似度，利用相似度組成方形矩陣，方陣對角線的值稱為參考度，參考度越大表示對應的數據點成為聚類中心點的概率越大。AP算法通過一種數據點和潛在聚類中心點互相選擇的機制來實現聚類，數據點通過計算發(fā)送到各個潛在聚類中心點的信息來決定自己屬于哪個簇，同樣的聚類中心也通過計算發(fā)送到各個數據點的信息判斷哪些數據點屬于本簇，在不斷的迭代下確定聚類的個數和聚類中心數據點。

(2)Birch聚類算法。

Birch算法是由Zhang T等在1996年提出的一種分層聚類算法[15]。算法使用聚類特征CF樹結構對數據點進行聚類。CF樹是由算法對不同子樹賦予不同的權重而組成的，每個子樹中包含一個特征元組，特征元組由數據點數、點與點之間的線性和點與點之間的平方和組成，因此CF樹中擁有每個子樹的特征統(tǒng)計信息。CF樹通過最大子樹的個數確定聚類個數，每個子樹中數據點與聚類中心之間的最大距離確定該數據點是否屬于本樹。在CF樹自上而下的掃描過程中，由于其擁有每個子樹的統(tǒng)計信息，所以不需要把所有數據都讀取到內存中，正是基于這個特性使得Birch算法能夠處理大規(guī)模的數據量。CF樹動態(tài)的特性使其能把讀取的新數據點插入到最近的子樹中，如果新的數據點的直徑超過了閾值，就會重新新建一棵子樹。通過元組的統(tǒng)計信息對數據集進行分類，然后在這個基礎上對新讀取的數據進行聚類，這使得消耗I/O時間相對其他分層算法要小。

(3)Gaussian Mixture Model聚類算法。

高斯混合模型采用概率為標準衡量數據之間的相似度。算法假設數據集是由一定數量的具有高斯分布特性的數據組成的，然后將數據點的協(xié)方差與高斯中心結合起來，進而實現GMM擬合的期望最大化。算法利用貝葉斯準則對數據進行隨機分類，然后計算每個數據點是由高斯分布模型生成的概率，在多次迭代調整參數后，最大化給定這些數據點的概率，進而為每個簇里分配最符合其高斯分布的數據[16]。

(4)Hierarchical聚類算法。

HC聚類主要分為自下而上的凝聚層次法和從上到下的分裂層次法，前者簇的數據點是從少到多依次合并直到滿足一定的條件而終止，后者是把數據點逐漸細分為小的簇，直到滿足條件不再細分而終止。文中使用的是scikit-learn的HC算法，其屬于凝聚分層法。算法先把每個數據點分為一類，然后利用相似度把兩類并成一類，不斷迭代，最后合并為K類。

(5)K-means聚類算法。

K-means算法在1955年最先由Steinhaus提出，之后其他領域也有學者在各自科研領域提出，直到1967年MacQueen[17]對前人的研究進行總結完善，并且給出了數學證明，使得K-means算法被廣泛應用。算法利用距離作為相似度的評價準則，通過不斷迭代使聚類中心點與簇內數據點的距離盡可能小。文中使用的是K-means++，該算法在數據集中隨機取一個數據點作為簇的中心點，然后計算其他數據點到聚類中心點的距離，距離越大所對應的數據點有可能成為下一個簇的中心點，通過不斷迭代確定K個聚類中心點，這樣就避免了其對聚類中心初始值選定的敏感問題。

(6)Spectral聚類算法。

譜聚類是一種基于對圖譜劃分的算法(2008)[18]，該算法對數據的空間形狀沒有要求。算法把數據集轉換為矩陣，通過計算矩陣的K個特征值和特征值對應的特征向量，使其組成一個特征向量空間，利用特定的劃分規(guī)則，比如基于距離的劃分規(guī)則，在多次迭代之后使簇內數據點的權重大(相似度高)，簇與簇之間的權重小(相似度低)。

綜上所述分析，文中選取數據屬性、時間復雜度、算法伸縮性、算法對噪聲的敏感程度、處理高維數據的能力、對復雜形狀的數據集是否適用這六個指標，對上述六種算法的性能進行了總結，如表1所示。

表1 部分聚類算法性能總結和比較

3 聚類有效性指標概述

由于文中的數據都是無標簽的，所以采用內部評價標準，利用數據集和聚類結果生成的標簽對聚類效果進行評估。小組內的數據相似度越高，小組與小組數據差異度越大，說明數據被很好地歸類。常用的評價指標有Silhouette Coefficient和Calinski-Harabaz Index。

3.1 Silhouette Coefficient

3.2 Calinski-Harabaz Index

Calinski-Harabaz Index是由Calinski和Harabaz[20]于1974年提出的一種評價指標。CH系數：

其中，K表示聚類中心的個數，tr(Bk)表示簇與簇之間離差矩陣的跡，tr(Wk)表示簇內離差矩陣的跡。Bk表示簇與簇之間的協(xié)方差矩陣，Wk表示簇內協(xié)方差矩陣。CH評分是簇間分離值與簇內分離值之值，比值越大代表聚類效果越好。

4 實驗測試及分析

本節(jié)利用數據的差異對Affinity Propagation、Birch、Gaussian Mixture Model、Hierarchical clustering、K-means和Spectral算法的聚類效果和效率進行了綜合實驗評估。所有算法由Python實現，Python的版本是Python 3.7.2，sklearn的版本是scikit-learn v0.21.1，實驗平臺采用Intel(R)Core(TM)i5-4210M CPU @ 2.6 GHz，8 G內存，Windows 10企業(yè)版。

4.1 實驗數據和測試方法

實驗數據均屬于機器數據，主要分為兩大類：連續(xù)型數據和離散型數據。其中連續(xù)型數據分為七類，離散型數據分為離散小數和離散整數兩類。具體信息如表2所示。

表2 數據描述

4.2 測試方法

為了探究聚類算法的有效性，對Affinity Propagation、Birch、Gaussian Mixture Model、Hierarchical clustering、K-means和Spectral算法分別在13類基準數據集上進行了測試。因為以上算法均屬于無監(jiān)督算法，所以聚類效果的評估使用了Silhouette Coefficient(以下簡稱輪廓系數)和Calinski-Harabasz Index(以下簡稱CH評分)，使用聚類算法消耗的時間作為算法效率的評價指標，并且探究了算法對數量級的敏感性分析。

4.3 效果評估

為了保持一致性，被測試算法被設定為四個聚類中心。其中Affinity Propagation 算法的preference=-50、Gaussian Mixture Model算法的covariance_type為'full'、K-means算法的內核為K-means++，random_state=28。

如圖2所示，為了區(qū)分，采用不同的形狀表示不同的算法。

(a)離散型小數

(b)離散型整數

(沒有AP算法的局部圖)

4.3.1 數據只有行數增加時

當數據集為離散數據時，從圖2(a)和(b)中可以看出，在輪廓系數中聚類效果隨著行數的增加而變差，CH評分中聚類效果隨著行數的增加而變好，在兩種評價指標下聚類效果最好的是K-means；當數據集為連續(xù)型正數時，從圖2(c)中可以看出，Birch、GMM、HC、K-means和Spectral的聚類效果在CH評分中很接近，AP算法大約在20行以上的聚類效果隨著行數的增加其CH評分遠遠高于其他五種算法，這主要是因為AP算法對數據的初始值不敏感，并且其聚類中心是數據集中的點，而不是由算法生成的中心點。然而在輪廓系數中，AP算法的評分反而是一個比較固定的值，且表現不如其他算法，這是因為AP算法的聚類中心點為已有數據點，數據的特性導致簇與簇之間的平均距離和簇內平均距離比較固定，進而使得輪廓系數的值隨行數的變動很小。

4.3.2 數據只有列數增加時

當數據集為離散數時，被測試算法的聚類效果隨著列數的增加而變差。從圖3(a)中可以看出，當數據集為離散型小數時，算法在兩種評價指標下的聚類效果很接近，其中Spectral算法隨列數的增加波動性變大，而其余算法則比較穩(wěn)定。從圖3(b)中可以看出，當數據隨集為離散型整數時，算法在兩種評價指標下聚類效果很接近，其中HC算法隨列數的增加波動性變大，而其余算法則比較穩(wěn)定；當數據集連續(xù)型正數時，從圖3(c)中可以看出，在兩種評價標準中，被測試算法的聚類效果中除了Spectral算法其余算法基本不受列數變動的影響，而且被測試算法的聚類效果在兩種評價標準中表現不同。在CH評分下被測試算法聚類效果最好的是AP，其次是K-means，在輪廓系數評分下被測試算法的聚類效果從好到差排名是：HC、K-means、GMM、Birch、AP。

(a)離散型小數

(b)離散型整數

(沒有AP算法的局部圖)

4.3.3 數據的行數和列數同時增加

當數據集為離散數據時，被測試算法的聚類效果隨著行數和列數的增加而變差。從圖4(a)中可以看出，當數據集為離散型小數時，算法在兩種評價指標下聚類效果很接近，其中Spectral算法的波動性很大。從圖4(b)中可以看出，當數據集為離散型整數，在行數超過75時，Spectral算法的CH評分最高；當數據集為連續(xù)型正數時，從圖4(c)中可以看出，被測試算法的聚類效果在兩種評價標準中表現不同。在CH評分下被測試算法聚類效果最好的是AP，其余算法的聚類效果則比較接近，在輪廓系數中當數據集的列數超過4列以后，AP算法的聚類效果最差。

(a)離散型小數

(b)離散型整數

(c)連續(xù)型正數

4.4 性能測試

本節(jié)在各種數據集上測試了不同算法的消耗時間，以消耗時間的多少作為評價算法效率的標準。本節(jié)在離散型小數、離散型整數和連續(xù)型正數中分別選取了500行2列的數據集作為研究對象。效果如圖5所示。

(沒有AP算法的局部圖)

從圖5上圖可以看出，AP算法消耗的時間最多，效率最低，這是因為AP算法要提前把數據點的相似度計算出來，加之AP算法的時間復雜度為O(n3)，最后使得AP算法消耗時間最多。AP算法在離散整數型數據集中消耗的時間最少。剩余五種被測試的算法消耗的時間接近，所以特意做了一個沒有AP算法的局部圖，如圖5下所示，其中Spectral算法消耗的時間最多，主要是因為Spectral算法是基于原有數據的相似度來計算特征值，所以花費的時間要多一些。Birch算法在小數中的計算速度最快，是因為其不需要把全部數據遍歷完，只需要對葉子節(jié)點進行處理，經過多次迭代以后得出聚類中心。因為機器讀取小數的速度要快于整數，所以Birch在小數中的效率要更高。K-means、GMM和HC算法在三類數據集中的表現差異不大，說明這三種算法對數據類型的敏感度比較低。

4.5 算法對數據敏感性分析

本節(jié)是由不同數量級的數據組成的數據集，由于AP、Birch和GMM算法需要變動參數，所以為了保持全文一致性，沒有對這三種算法做敏感性測試。數據集結構為300行2列。橫坐標的單位值代表十的一次方，測試結果如圖6所示。由圖6可知，在兩種評價標準下K-means要比其他兩種算法的聚類效果好，其中K-means和HC對數量級組成的數據集不敏感，Spectral算法對數量級比較敏感。

圖6 算法在不同數量級下的效果對比

5 結束語

通過上述分析，在聚類效果、性能和敏感性三個方面得到以下結論：

(1)聚類效果：①數據只有行數增加時，AP算法和K-means的聚類效果好于其他四種算法；②數據只有列數增加時：在數據類型為離散型小數中，算法的聚類效果很接近，其中Spectral算法的波動性最大。在數據類型為離散型整數中，算法的聚類效果很接近，其中HC算法的波動性最大。在數據類型為連續(xù)型正數中，AP算法和K-means的聚類效果好于其他算法；③數據的行數和列數同時增加時：在數據類型為離散小數中，算法的聚類效果很接近，其中Spectral算法的波動性最大。在數據類型為離散整數中，Spectral算法的聚類效果相對好于其他算法。在數據類型為連續(xù)型正數中，在CH評分下被測試算法的聚類效果最好的是AP，其余算法效果比較接近，在輪廓系數下當列數超過4以后，AP算法的聚類效果最差。

(2)性能：AP算法消耗的時間最多，效率最低，其次是Spectral算法，剩余幾種算法的計算效率比較接近。

(3)敏感性：K-means和HC對數量級不敏感，Spectral算法對數量級相對比較敏感。

綜上，在聚類效果、性能和對數量級的敏感性三個方面綜合來看，K-means算法相對優(yōu)于其他五種聚類算法。各個算法各有優(yōu)缺點：AP算法在連續(xù)型正數組成的數據集中，隨著行數的增大其聚類效果明顯好于其他算法。但是AP算法的效率在六種算法中是最差的；Birch算法的效率在數據類型為小數的數據集中表現最好，但其適用性相對最差；GMM算法聚類效率在連續(xù)型正數的數據集中表現的最好；HC和K-means算法的聚類效果在連續(xù)型正數組成的數據集中不受列數變動的影響，但在行數變化的離散型數據集中HC算法的聚類效果相對最差；Spectral算法對數據的敏感性相對最高，在小數構成的數據集中聚類效果相對最差。

雖然現在很多聚類算法不斷地被提出和改進，但是還沒有出現一種適用于不同數據特征的算法，這主要是因為聚類算法沒有迭代優(yōu)化其正確性，而過分強調簇內緊湊，簇間疏離。隨著大數據時代的到來，數據不僅越來越多而且數據結構越來越復雜，如何制定一種適合多種情況的聚類算法和評價指標將是下一步需要做的重要工作。