一種新的平衡化譜聚類方法*

蘇揚， 胡恩良

(云南師范大學 數學學院，云南 昆明 650500)

1 引言

譜聚類(Spectral Clustering，SPC)是一種基于圖論的聚類方法，其本質是將聚類問題轉化為求解Laplacian 矩陣或相似矩陣的譜分解問題.與傳統聚類算法相比，譜聚類能夠在任意形狀樣本分布上聚類且收斂于全局最優(yōu)解[1].處理數據時，譜聚類僅需要構建樣本點之間的相似度矩陣，這對處理高維數據聚類具有一定優(yōu)勢.近年來，譜聚類算法獲得了持續(xù)改進和發(fā)展，例如：針對譜聚類中的相似度測量問題，Tasdemir等人[2]提出了一種基于測地線距離的混合相似性度量方法，應用不同類型的信息來表示數據點間的相似度；Wang等人[3]提出了一種譜多流形聚類算法(Spectral Multi-Manifold Clustering，SMMC)；Zhang 等人[4]提出了基于隨機游走來建立 Gaussian核相似矩陣.但要解決任意形狀樣本分布的數據聚類問題，迄今為止已提出的算法都是不完美的，譜聚類也不例外.

傳統譜聚類隱含了各簇數據點數量分布較均衡的假設，即要求所選各簇之間的數據點數量差異不大.因此對各簇間樣本點數相差懸殊的類不平衡問題，傳統譜聚類將不再適用.針對類不平衡問題，劉富等人[5]提出了一種基于聚類體量約束的模糊c-harmonic均值算法，劉歡等人[6]改進了EM聚類算法，王舒梵等人[7]構建了高斯混合模型聚類的SMOTE過采樣算法.然而，這些算法雖然提高了數據集類不平衡問題的聚類性能，但在處理高維數據集時容易產生“維數災難”現象，導致聚類質量降低.為此，本文提出了一種新的平衡化譜聚類算法(Balanced Spectral Clustering，BSPC)，該算法考慮譜聚類算法的基本特性融入了隸屬度矩陣的近似正交約束，在克服“均勻效應”[8]問題的同時保證了結果的準確性.

2 平衡化譜聚類

2.1 譜聚類分析

(1)

2.2 平衡化譜聚類

(2)

在模型(2)中：

i)約束“Fi.∈Δk,?i∈[n]={1,…,n}”僅使得數據點對各個聚類中心的隸屬度之和為1，而對各類樣本點的隸屬度總和沒有限制，由此在處理非平衡數據時，極易使“大類”樣本的隸屬度總和過高，“小類”樣本的隸屬度總和過低，這便導致了“均勻效應”.因此需要對大類和小類的隸屬度總和施加“平衡”約束；

ii)約束“FTF=I”對隸屬度矩陣施加正交約束“平衡”大類和小類的隸屬度總和[9].直觀的，若約束隸屬度矩陣F滿足近似正交(FTF≈I)，記F·p表示F的第P列，則

(3)

(4)

2.3 模型求解

為了求解問題(2)，利用文獻[10]中的跡懲罰函數，將問題(2)轉化為

(5)

其中μ是罰參數.經過計算可知，(5)式等價于

(6)

(7)

由于問題(7)中的目標函數是二次函數，所以可考慮利用Gauss-Newton(GN)法對其求解[11].記S(Ft)為g(F)在點Ft處的GN方向，則GN迭代格式為

Ft+1=Ft+αtS(Ft).

(8)

根據文獻[10]， 計算問題(7)的GN方向解析表達式，即

(9)

至此，平衡化譜聚類模型的近似問題(5)的求解算法可歸納為如下算法.

算法 平衡化譜聚類(BSPC)

輸入：Laplacian矩陣L，期望的聚類數k，罰參數μ，最大迭代次數T，終止精度ε.

輸出:聚類隸屬度矩陣F*.

step1 :設置t=0，初始點F0;

step2 :根據(9)式計算GN方向

St=S(Ft);

step3 :利用線搜索求St方向的歩長αt，根據(8)式更新F為

Ft+1=Ft+αtSt;

輸出F*=Ft+1.

3 實驗與分析

3.1 數據集選取

分別在模擬數據集和真實數據集上驗證BSPC算法的有效性.模擬數據集共4個，分別由具有二維高斯分布的類不平衡數據點構建，每個數據集包含300個樣本點，其中大尺寸類樣本點和小尺寸類樣本點的比例依次為9∶1(D1)、8∶2(D2)、7∶3(D3)和 6∶4(D4).真實數據集選用具有不同實際應用背景的UCI數據集，從中選取Chessboard、Spiral、Protein、Glass、 Heart、Cancer和CMC共7組數據作為測試集，所有數據集均經過類不平衡化處理，即各類的樣本比例作了設置(如表1).

表1 實驗所用數據集及其相關信息

3.2 性能評價指標

在實驗中，設置期望聚類數等于數據集真實類別數.由于所選數據集都有真實的類標號，可將其作為聚類結果的基準.采用聚類純度(Cluster Purity，CP)[11]來衡量聚類效果，CP定義如下：

(10)

其中，n為樣本總數，njl為真實第j類中與聚類輸出為第l中所含相同樣本數.CP定義是將每個聚類標號對應于與其含有相同樣本數最多的真實類標號，這k類中相同樣本數之和與樣本總數的占比，便是聚類純度.聚類純度越高且越接近1，表明聚類效果越好.

圖1 在Chessboard數據集上的收斂性Fig.1 Convergence on the Chessboard dataset

3.3 實驗結果及分析

在Chessboard數據集上運行BSPC算法，由圖1的算法迭代圖可知，BSPC算法的目標函數值具有迭代收斂性.

為了驗證本文算法的聚類效果，使用SPC算法[1]與本文算法進行比較，在所有測試數據集上，分別以不同的初始點運行30次，并在表2中報告平均聚類純度和標準差.可以看出，在多數情況下BSPC能獲得更大的CP值.這是因為：① BSPC在SPC的基礎上加入了正交約束項，使得大尺寸類的樣本聚類隸屬度降低，小尺寸類樣本的聚類隸屬度升高，從而緩解了聚類算法在不平衡數據上容易導致的均勻效應；②正交約束提高了類(簇)間的分離性.

圖2 在Chessboard數據集上的聚類效果Fig.2 Clustering effect on chessboard dataset

圖2中顯示SPC算法和BSPC算法在Chessboard數據集上的聚類結果，可看出BSPC更好地緩解了均勻效應，提高了各類(簇)間的分離性.

4 結語

在傳統譜聚類的基礎上提出了一種新的平衡化譜聚類模型，該模型在譜聚類的基礎上加入了對聚類隸屬度矩陣的正交約束，在11個不平衡數據集上的測試實驗結果表明，提出的新算法相比于傳統譜聚類具有更好的聚類效果.