高魯棒性的改進最小生成樹聚類算法

沈陽理工大學信息科學與工程學院 李云帆 陳禹銘 文 峰

聚類是一種應用廣泛的無監督學習任務，目前的主流聚類方法種類繁多，但在實際應用中需要根據數據分布和具體要求選擇聚類方法或設定超參數，十分不便。針對這一問題，提出了一種改進的最小生成樹聚類算法，該算法通過充分利用簇規模信息，增強了其抗噪聲的能力，同時可以處理不同形狀、不同密度的簇。這種方法只需要設定聚類簇數一個超參數，此外還有易于實現、可解釋性強等優點。實驗結果表明，該改進算法具有更強的魯棒性，在多種測試集上的聚類效果明顯優于其他傳統方法，并在圖像分割應用上仍有著優秀的表現。

聚類是一種十分常見的無監督學習問題。根據算法思想不同，聚類算法可以分為很多種，如K-Means等基于劃分的方法和DBSCAN等基于密度的方法。最小生成樹(MST)聚類是一種基于圖論的聚類方法，算法等價于使用各節點間的相似度對所有數據構建最小生成樹，再將相似度大于閾值的邊刪去，從而得到一片森林，森林中每顆樹視為聚類結果中的一個簇。

經典的最小生成樹聚類算法具有分割閾值難以確定、易受離群點干擾、難以處理變密度數據等缺點。針對這些問題，本文提出基于簇規模信息的改進MST聚類算法，該算法只需給定聚類簇數，便可以通過計算并修改各邊權重的方式得到自適應抗噪聲的聚類結果。最終通過在模擬數據集和圖像分割應用上的實驗，證明了該方法的有效性。

1 算法原理與設計

1.1 基于簇規模信息的修正系數

聚類算法需要克服的一大困難對噪聲點的處理。

針對這一問題，本文的方法是引入平衡度修正系數的概念，通過對邊權值的修改，來控制聚類效果，避免產生相對容量極小的類。生成樹聚類中，每當分割一條邊，均會將一個簇劃分為兩個簇，設兩個簇的容量分別為m和n，則平衡度修正系數可以由兩者歸一化后的調和平均數開根號得到。記m和n的調和平均數為hm(m,n)，平衡度修正系數為Be，則有：

當m與n的和確定時，該函數圖像如圖1所示。可以看出，該函數具有良好性質，當兩個簇容量相差較大時，平衡度修正系數較小，修正后的邊權值降低，更不易于被分割，從而在一定程度上自適應地減少噪聲干擾。

圖1 平衡度修正系數與簇大小的關系

經典最小生成樹聚類方法不能處理變密度數據，容易將噪聲點單獨分為一類。對于這一問題，本文的解決方案是引入正比于當前分割簇容量的權重，稱為簇容量修正系數，這使算法更傾向于分割大的簇。設遍歷森林時當前邊所屬簇的容量為C，該樹相當于聚類過程中的一個簇，則當前邊的簇容量修正系數Se為：

相比于傳統最小生成樹聚類算法，改進后的算法使用修正后的邊權值We

'進行聚類。修正后的邊權值由原邊權值與兩個修正系數相乘求得，即：

1.2 算法流程

算法1：基于簇規模信息的改進最小生成樹聚類算法

輸入：聚類簇數N，樣本點集X

輸出：標簽列表Labels

步驟：

Step 1：計算樣本點集X的相似度矩陣，構造最小生成樹。

Step 2：遍歷最小生成樹的所有邊，根據公式(3)計算修正后的邊權值，并刪去權值最大的邊，增加一個簇。

Step 3：若簇數小于設定數，則重復Step 2，直到簇數達到目標數時聚類完畢，得到Labels。

2 實驗

2.1 模擬數據集實驗

以下是多個不同模擬數據集上對比實驗的結果。本文將改進算法同小批量K-Means、DBSCAN、經典最小生成樹聚類等算法進行對比實驗，其中所有算法均已進行超參數調優，部分算法規定當簇內樣本數小于最小簇容量時視為噪聲點，實驗結果如圖2所示，最右側一列為改進算法結果。

圖2 不同數據集上的聚類實驗結果

不難看出，改進后的最小生成樹聚類算法在眾多數據集上均具有非常強的優越性，可以擬合不同形狀或不同密度的簇，適應性極強。缺點是速度略微慢于大部分聚類算法，經測試，這主要是由計算樣本點相似度矩陣導致的。

2.2 圖像分割實驗

本文還將改進算法應用到了圖像分割領域。對于一張位圖，可以將其中每個像素點看作一個五維向量，前兩維儲存位置信息，后三位儲存RGB值（對于四通道圖像則為六維）。實際處理時可在兩者間適當的加權或進行歸一化。經實驗驗證，改進MST算法具有一定的無監督圖像分割能力，分割結果如圖3所示。其中左側為圖像原圖，右側為圖像分割后的結果。

圖3 圖像分割實驗結果

結論：本文提出了一種基于簇規模信息的改進最小生成樹聚類算法，并在模擬數據集和實際應用中進行充分實驗。實驗結果表明，該方法聚類效果明顯優于K-Means，DBSCAN等傳統聚類算法，且僅需要設定聚類簇數作為超參數，便可以在聚類中適應不同形狀或密度的簇，同時還具備一定抗噪聲能力，在多種數據集上與圖像分割應用中均具有很好的表現。