基于局部密度構造相似矩陣的譜聚類算法

吳健，崔志明，時玉杰，盛勝利，龔聲蓉

（1. 蘇州大學 智能信息處理及應用研究所，江蘇 蘇州 215006；2. 美國阿肯色中央大學 計算機科學系，阿肯色州 康威 72035-0001）

1 引言

傳統的聚類分析方法受限于非凸形狀的樣本空間，當樣本空間不凸時，傳統聚類算法會陷入局部最優。為了克服樣本空間形狀的限制，研究者提出了譜聚類(spectral clustering)算法[1,2]。該算法不僅能夠在任意形狀的樣本空間上聚類，而且收斂于全局最優。與傳統的聚類算法相比，它能很好地解決非塊狀和非凸形數據的聚類問題。譜聚類的這種優良特性在圖像分割[3,4]和文檔聚類[5,6]等領域得到了成功的應用。

譜聚類是一種基于相似矩陣的聚類算法，它對相似矩陣進行變換得到拉普拉斯矩陣，然后對其特征向量進行聚類[1,2,7,8]。所以，相似矩陣構造的好壞是譜聚類算法優劣的重要因素。傳統的譜聚類算法采用歐式距離來表示樣本點之間的距離，并通過高斯核變換來計算樣本點之間的相似度，其僅考慮到了局部一致性，沒有考慮到全局一致性。王玲等人[9]提出密度敏感的相似性度量方法，該方法采用密度敏感的距離測度描述數據的實際聚類分布，它可以放大不同高密度區域內數據點間的距離，同時縮短同一高密度區域內數據點間的距離。相對傳統的相似矩陣計算方法，該方法的定義較復雜且計算復雜度較高。孔萬增等人[10]采用傳統譜聚類中的方法構造相似矩陣，利用本征間隙自動確定數據的聚類個數，并利用確定的類數和譜分解的特征向量之間的余弦值完成數據的聚類。文獻[1～10]中的譜聚類方法都沒有充分利用樣本點分布特性所隱含的先驗信息，不能構造很好的相似矩陣。當其面臨復雜樣本數據點集時，無法得到理想的聚類結果。

為了構建更符合樣本數據點分布特性的相似矩陣，本文提出了一種基于局部密度構造相似矩陣的譜聚類(LDSC, local density-based spectral clustering)算法。通過人工仿真數據集和UCI數據集進行測試，實驗結果表明，本文算法得到的相似矩陣能更好地表示數據樣本點之間的相似性，算法具有較好的頑健性。

2 LDSC算法

2.1 算法思想

樣本數據點集分布具有如下 2個一致性特征[11]。

1) 局部一致性：指的是在空間位置上相鄰的數據點具有較高的相似性。

2) 全局一致性：指的是位于同一流形上的數據點具有較高的相似性。

本文依據樣本數據點分布的局部和全局一致性特征，提出了一種基于局部密度構造相似矩陣的譜聚類算法。算法首先給出局部密度定義，對樣本數據點由密到疏排序，按序依次對樣本點進行連接操作，完成無向圖的構建。同時，借鑒GN算法思想[12]，采用邊介數作為樣本點對間的權值，從而計算出相似矩陣。然后，通過第一個極大本征間隙出現的位置來確定類個數，并利用經典聚類方法對特征向量空間中的數據點進行聚類。

2.2 無向圖構建

2.2.1 現有構圖方法分析

目前，用來構造無向圖的方法有ε閾值法、k近鄰法和互為k近鄰法。ε閾值法雖然簡便，但是由于樣本點分布的多樣性，ε的選取比較困難，很難選擇一個合適的ε以得到既連通又稀疏的圖。較之更好且常用的是k近鄰方法，k容易選取且能得到一個稀疏圖。但是k近鄰法把每一個數據點看成同等重要的點，隨機對點進行k近鄰連線，不僅計算量大而且可能導致不同類數據點間的互連，從而將不同類數據點歸為同類。互為k近鄰方法[8]雖能保證數據點間互連的對稱性，但其可能使同類樣本之間也無法得到連通圖。筆者以圖1所示樣本數據集為例進行分析。

圖1 原始樣本數據集

構建無向圖，即根據一定的策略給樣本空間中的數據點連線，最終得到樣本數據集對應的無向圖。圖1為原始數據集，分為上月、下月和最下面的不規則分布3類。

圖2中給出了利用3種現有方法構建無向圖的結果，從圖2中可以看出現有無向圖構建方法的局限性。圖2(a)的ε閾值構圖法中，閾值為0.3，從圖2(a)中很容易發現其存在的問題：同類樣本數據點間不連通，且存在較多孤立點。圖 2(b)的k近鄰方法雖然已形成連通圖，但也存在明顯的缺陷：不同類樣本數據點互連，即圖2(b)中的下月型數據集和最下面的不規則分布數據集中有互連現象，如果采用該方法，則必然會對譜聚類結果產生較大的影響。圖 2(c)的互為k近鄰方法中，上月、下月和不規則分布間沒有互連，但與ε閾值構圖法一樣，同類樣本之間不能構成連通圖，則其譜聚類結果會將同類樣本歸為不同類。

圖2 傳統構圖方法的構圖結果

2.2.2 局部密度定義

針對上節3種方法中存在的問題，期望設計出一種新的構圖方法，能夠使得各類數據集有效分開且同類樣本點連通，形成獨立的連通子圖。本文充分考慮樣本點集的局部密度，首先對樣本點按照局部密度進行排序，然后依照一定的連接策略完成無向圖的構建。為了敘述方便，先給出局部密度的定義。

定義 1 如果存在一個點與其k近鄰點的距離之和比其他樣本點都小，則該點所處的局部區域在整個樣本點集中越稠密。因此，筆者用樣本點與其k近鄰點距離之和的大小表示該點所處區域的稠密程度。記數據點iv與其k近鄰點的距離之和為iD，用iD表示數據點iv的局部密度，iD定義為

其中， di1≤di2≤… ≤ dij≤… ≤ dik， dij表示 vj和vi之間的距離。

由定義1可知， Di越小，則表明 vi附近數據點越集中； Di越大，則表明 vi附近數據點越稀疏。

2.2.3 無向圖構建步驟

采用局部密度思想，本文提出了基于局部密度的無向圖構建方法，局部密度越大的數據點能夠與其k鄰近點相連的機會越大。本文提出的方法可以避免ε閾值法、k近鄰方法和互為k近鄰方法在構建無向圖時存在的問題。

構圖算法步驟如下。

Step1 求每一個點 Vi到其k鄰近點的距離之和 Di( i = 1 ,… , n )。

Step2 對 Di( i = 1 ,… ,n )從小到大排序，選取最小的 D(n)對應的點 Vi，并記 n um= 1 ， D(n)定義如下（下標n表示未進行k鄰近點連線操作的點的個數）

Step3 對 Vi進行操作，即與k鄰近點連線。對應鄰接矩陣P中，初始 Pinitial中值都為-1，如果點 Vi和Vj相連，則置 pij=1且 pji= 1；若兩點不連，則置pij= 0 且 pji= 0 ；頂點自身一直為-1。定義 Pinitial為

則矩陣P可表示為

Step4 選取剩余{Dx, x = 1,2,… ,n - num}中的最小值 D(n-num)（下標n - n um表示未進行k鄰近點連線操作的點的個數），其對應點為 Vx， D(n-num)定義為

統計出 Vx一行對應鄰接矩陣中1的個數m，然后將與k - m 個鄰近點連線。可知 Vx的k鄰近點集{Vxl,l = 1 ,2,… , k }，Vxl表示距離點 Vx第l近的點，初始化 l =1， c ount= 0 。

Step5 當l≤k時，進行如下判斷。

1) 如果Vxl已與 Vx連接，l = l + 1，重新執行Step 5；如果 Vxl的度已飽和（即度為k），則點 Vx不與點 Vxl相連，即鄰接矩陣中置0， l =l+1；否則，連接兩點，對應鄰接矩陣中置 1，且 c ount = c ount+ 1 ，l = l +1。

2) 如果count＞k-m，轉Step 6，否則重新執行Step 5。

Step6 當num＜n時，num = n um+1，重復執行Step 4和Step 5；否則，程序結束。

利用本文構圖方法所得構圖結果如圖3所示。

圖3 改進KNN構圖結果(k=6)

從圖3中可以看出，3類樣本集有效分開且內部連通，得到3個獨立的連通子圖，達到了預期目標。基于局部密度構圖，可以保證空間位置上相鄰的點互連，從而同屬一類。Step 5中的改進可以避免不同類數據點間互連。

2.3 相似矩陣構造

現實世界中的很多系統都以網絡形式存在，具有同簇節點相互連接密集、異簇節點相互連接稀疏的特點。復雜網絡聚類方法可歸納為2類：基于優化的方法和啟發式方法[13]。基于圖分割理論的譜聚類是一種基于優化的聚類方法。啟發式方法將復雜網絡聚類問題轉化為預定義啟發式規則的設計問題，被廣為引用的GN算法的啟發式規則是：簇間連接的邊介數應大于簇內連接的邊介數。邊介數概念最早由Girvan和Newman提出，被用作評估復雜網絡關鍵邊的重要度指標。本文借鑒GN算法思想，提出了一種新穎的基于邊介數度量的權值矩陣計算方法。

邊介數[14]定義如下：圖中任意兩點的最短路徑經過這條邊的數目；如果不止一條最短路徑，則在這些路徑間等分邊介數值。邊e的邊介數e

B計算式為

uv路徑的數目表示經過邊e的點u到點v的最短路徑數目。

樣本數據點對應的無向圖構建完成后，需要給圖中的邊賦予權值。若樣本數據點有多類，則構建出的無向圖中會有多個獨立連通子圖，子圖內直接相連的點對的邊介數可以直接求解，但是在子圖內部和子圖之間存在點對間無直接邊相連的情況，求解這些點對間的“邊介數”至關重要，即如何給這些樣本點對賦予權值，需要作深入的研究。

通過分析樣本數據集的分布特性，筆者研究得出樣本點分布具有如下性質。

性質1 點間傳遞相似性。

已知點aV 和點bV 具有較高的相似性，bV 和Vc具有較高的相似性，則 Va和 Vc也具有較高的相似性。如下式所示

性質2 點間阻斷性。

若不能直接也不能通過傳遞相似性得出兩點相似，則兩點不具有相似性。

結合邊介數的定義和上述兩條性質，給無向圖中任意兩點賦予權重，即可得到無向圖對應的權值矩陣。以圖4為例具體說明如何給任意兩點賦權值。

任意點對間權重賦值的步驟如下。

1) 首先計算圖中每一條邊的邊介數，這個邊介數作為該邊所連接的兩點間的權值，即 w = Bab，abwab表示點a和點b的權值，顯然 wab= wba。

2) 由性質1中的點間傳遞相似性可知，雖然點a和c沒有邊直接相連，但其卻有較高的相似性。同理可知，點a和點g也具有較大的相似性。為解決此類問題，本文給出如下定義。

其中， wuv表示任意兩點u和v之間的權值，sum( eu→v)表示點u到點v的最短路徑上邊的條數， ∑ Bu→v表示點u到點v的最短路徑上各邊的邊介數之和。經分析可知，有邊直接相連的兩點間的權值亦可通過這個方法計算，用式(8)作為獨立連通子圖內任意兩點間權值的計算公式。顯然，wuv= wvu。

圖4 權值計算示例

3) 前兩點解決的是獨立連通子圖內任意兩點間權重的賦值問題，不能應用于獨立子圖間的樣本數據點，如圖4中的點a和點d，因為這兩點間不存在路徑。但由性質2中的點間阻斷性可知，點a和點d不具有相似性，據此作如下規定，若兩點間無路徑，則其權值為一較大的正數值M（或為無窮大）。此規定亦適用于無向圖中的孤立點。

經過上述3個步驟，可以計算得出數據樣本集中任意點對間的權值，從而得到了無向圖對應的權值矩陣。權值矩陣中2個數據點之間的數值越小，表示2個數據點越相似。譜聚類算法在聚類過程中需要對權值矩陣經過一定的變換得到相似矩陣。相似矩陣中的數值越大表示2個數據點越相似，屬于同一類的可能性越大。反之，2個點屬于同一類的可能性越小。這與權值矩陣中的數值表示含義相反。本文采用倒數的方式計算相似矩陣，由權值矩陣到相似矩陣的計算公式為

如果在權值矩陣中 2個點之間的權值是無窮大，則在相似矩陣中就設置為 0。由于權值矩陣中主對角線上的數值為 0，則在相似矩陣中主對角線上的數值應該為1。

2.4 算法實現

本文針對譜聚類算法中的相似矩陣構造進行了研究。首先利用上節中給出的方法對樣本數據點集進行無向圖構建，然后利用邊介數思想計算權值矩陣，經過數據變換得到相似矩陣，最后利用經典聚類方法對特征向量空間中的數據點進行聚類。具體步驟如下。

輸入：n個數據點 xi( i = 1 ,… , n )。

輸出：數據點集的劃分結果 C1,… ,Ck。

1) 利用本文提出的改進KNN算法對輸入的數據點構造相似圖G。

2) 對構造的相似圖G進行邊介數計算，按照2.3節所述方法求取權值矩陣W，并采用式(9)計算相似矩陣S。

3) 構造Laplacian矩陣 L = D-1/2S D-1/2，其中，D為對角度矩陣

4) 計算矩陣L的特征值，并對特征值進行從大到小的排序，找到第一個極大本征間隙出現的位置，記為k，k即為聚類類別數。

5) 計算k個最大特征值對應的特征向量v1, v2,… ,vk，構造矩陣V =［v1, v2,… ,vk］ ，對矩陣V中的每一行進行單位化處理，得到矩陣Y，即

6) 把矩陣Y的每一行看成k維空間中的點，利用傳統的聚類算法（如K-means算法）將其聚成k類。

7) 如果Y的第i行屬于第j類，則將原數據點xi也劃分到第j類。算法結束。

3 實驗結果與分析

為了驗證本文譜聚類算法的分類性能，本文進行了2組實驗：采用人工仿真數據集，分為理想分類數據集和非線性數據集，重點測試聚類算法的一般性和特殊性；選用具有真實數據含義的UCI數據集測試聚類算法的實際應用效果。實驗程序采用Dell PC機上的MATLAB 2010a實現，機器配置如下：Pentium(R) Dual-Core CPU E5300@2.60 GHz，4GB內存，Windows 7操作系統。

實驗1 人工數據集測試

1) 理想分類數據實驗

為了驗證本文算法的一般性，首先在理想分類數據集上進行實驗，理想數據集由計算機隨機產生，共180個樣本點，分為9類，如圖5(a)所示。為了使實驗結果更直觀、明顯，本文在實驗時對數據按類順序排列，由于樣本數據點按照類順序進行排列，因此它對應的相似矩陣S在主對角線上呈現出9個明顯的分塊，如圖5(b)所示。

圖5 人造9類數據

文獻[15]指出，當譜聚類算法的相似性矩陣是塊對角矩陣時，該算法可以找到完全正確的聚類結果。由此可知，本文譜聚類算法完全能夠解決一般性的問題。本文譜聚類算法對圖5(a)所示的9類數據樣本集有很好的分類性能，聚類的結果如圖6所示。

2) 非線性數據實驗

通過上一節對理想分類數據的實驗分析，驗證了本文譜聚類算法的有效性。在本節中，筆者將對一些復雜數據進行聚類實驗分析。傳統聚類算法，如 K-means算法、FCM 算法，基于歐式距離來描述樣本數據點之間的相似性。但是，樣本數據點之間的歐式距離較小并不意味著它們即屬于同一類，如圖7所示的數據樣本集。由于數據集是交叉的月牙型分布，不是塊狀分布，如采用傳統聚類算法對其進行聚類分析，其聚類效果會很不理想。

圖6 本文譜聚類分類結果

圖7 雙月牙數據

采用本文譜聚類算法，在類順序排列的相似矩陣上呈現出一條狹長的對角塊，如圖8(a)所示。在雙月型的數據集中屬于同一類的樣本點在物理位置上有可能比較遠，樣本點之間的最短路徑需要經過很多條邊相連，引起相似矩陣中同類樣本點間的相似度有所差異，所以該圖并不是嚴格意義上的塊對角分布，但還是可以從圖8(a)中清晰地看出樣本數據點集分成了2類。雙月型數據聚類結果準確無誤，聚類結果如圖8(b)所示。

筆者從一些挑戰性問題中選擇了3個較為困難的數據集。本文以文獻[10]提出的ASC算法作為比較算法。圖9(a)～圖9(c)是分別采用本文算法在這3個數據集上的聚類結果，對于這3個問題，本文算法可以成功得到聚類結果。圖10是ASC算法在這3個數據集上的聚類結果，從圖10中可以看出，圖10(b)和圖 10(c)發生了聚類錯誤，不能對線球形和波浪線數據集進行正確聚類。

圖8 本文譜聚類算法聚類分析

圖9 本文算法針對3種人工挑戰性問題的聚類結果

圖10 文獻[10]算法針對3種人工挑戰性問題的聚類結果

實驗2 UCI數據集測試

實驗采用的數據集選自國際通用數據庫UCI基準數據集中的Satimage數據集、Iris數據集、Ionosphere數據集以及 New-thyroid數據集進行本文算法和ASC算法的實驗比較。具體真實數據集的信息如表1所示，顯示了UCI 4個實驗數據集的基本屬性。

表1 UCI數據集基本信息

為了比較不同算法的性能，筆者使用的評價指標是聚類正確率[9]和時間開銷。假設已知聚類劃分為，算法獲得的聚類劃分為 Δ = { C1, C2, …, Ck}。? i ∈ [1,… ,ktrue]，j ∈ [1,…,k ]，用Confusion( i, j)表示已知聚類 Citrue和算法劃分的聚類 Cj之間相同的數據點個數，則聚類錯誤率定義為

其中，n為數據點的個數。聚類正確率的定義很容易根據式(11)得到。

表2是2種算法在每個數據集上的最優聚類誤差和平均運行時間結果。本文算法中的參數是k，而ASC算法中的主要參數是σ，2種算法中筆者都選擇最優的聚類結果進行實驗比較分析。文獻[10]中給出了Iris、Ionoshpere和New-thyroid數據集在得到最優結果時的σ值及其分類準確率，這里筆者使用同樣的參數值進行實驗。由于Satimage數據集中數據較多，文獻[10]在6類中隨機選取444個樣本數據進行實驗，本文也隨機選擇444個樣本數據，但由于數據不盡相同，所以這里選取的最優σ參數和文獻[10]中給出的有所不同。

表2 UCI數據集上的最優聚類誤差和平均運行時間

有研究表明，大多數聚類算法僅在少量數據形成的低維特征空間中擁有較好的聚類結果[16]。從表2中可以看出，由于Satimage和Ionoshpere數據集的維數分別為36和34，ASC算法在這2個數據集上的聚類正確率較低，而在維數較低的Iris和New-thyroid數據集上的聚類正確率相對較高。本文算法由于能夠更好地表示數據樣本點之間的相似性，在這4個數據集上的聚類效果均比ASC算法要好，尤其是維數較高的Ionoshpere數據集的聚類比ASC算法更優。

在平均運行時間上，本文算法要比 ASC算法運行時間略長，原因在于本文算法包含求解最短路徑的環節，而ASC算法沒有這個過程。LDSC算法的計算復雜度由求最短路徑的計算量所決定，本文采用Floyd最短路徑算法，該算法的計算復雜度為O( n3)。因此，LDSC算法的計算復雜度與原有譜聚類算法的計算復雜度在同一數量級上。

4 結束語

相似矩陣構造是譜聚類中的瓶頸問題。本文提出了一種基于局部密度構造相似矩陣的譜聚類算法，算法首先對樣本點按照局部密度由密到疏進行排序，并按照設計的連接策略構建無向圖；然后基于邊介數構造無向圖的權值矩陣，從而得到相似矩陣；最后利用經典聚類方法對特征向量空間中的數據點進行聚類。實驗結果表明，本文算法得到的相似矩陣能更好地表示數據樣本點之間的相似性，算法具有較好的頑健性。但是，譜聚類算法存在著面對高維數據集時聚類正確率降低的共同問題，下一步研究重心將放在提高高維數據集聚類正確率上。

[1] CRISTIANINI N, SHAWE-TAYLOR J, KANDOLA J. Spectral kernel methods for clustering[A]. Proceedings of the 13th Advances in Neural Information Processing Systems(NIPS 2001)[C]. Vancouver, British Columbia, Canada, 2001. 649-655.

[2] NG A Y, JORDAN M I, WEISS Y. On spectral clustering： analysis and an algorithm[A]. Proceedings of the 14th Advances in Neural Information Processing Systems(NIPS 2002)[C]. Vancouver, British Columbia,Canada, 2002. 849-856.

[3] 鄧曉政, 焦李成, 盧山. 基于非負矩陣分解的譜聚類集成SAR圖像分割[J]. 電子學報, 2011, 39(12)：2905-2909.DENG X Z, JIAO L C, LU S. Spectral clustering ensemble applied to SAR image segmentation using nonnegative matrix factorization[J].Acta Electronica Sinica, 2011, 39(12)：2905-2909.

[4] DUCOURNAU A, BRETTO A, RITAL S, et al. A reductive approach to hypergraph clustering： an application to image segmentation[J].Pattern Recognition, 2012, 45(7)：2788-2803.

[5] 徐森, 盧志茂, 顧國昌. 使用譜聚類算法解決文本聚類集成問題[J].通信學報, 2010, 31(6)：58-66.XU S, LU Z M, GU G C. Spectral clustering algorithms for document cluster ensemble problem[J]. Journal on Communications, 2010, 31(6)：58-66.

[6] ZHANG T P, TANG Y Y, FANG B, et al. Document clustering in correlation similarity measure space[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(6)：1002-1013.

[7] LUXBURG U V. A tutorial on spectral clustering[J]. Statistics and Computing, 2007, 17(4)：395-416.

[8] 李建元, 周腳根, 關佶紅等. 譜圖聚類算法研究進展[J]. 智能系統學報, 2011, 6(5)：405-414.LI J Y, ZHOU J G, GUAN J H, et al. A survey of clustering algorithms based on spectra of graphs[J]. CAAI Transactions on Intelligent Systems, 2011, 6(5)：405-414.

[9] 王玲, 薄列峰, 焦李成. 密度敏感的譜聚類[J]. 電子學報, 2007,35(8)：1577-1581.WANG L, BO L F, JIAO L C. Density-sensitive spectral clustering[J].Acta Electronica Sinica, 2007, 35(8)：1577-1581.

[10] 孔萬增, 孫志海, 楊燦等. 基于本征間隙與正交特征向量的自動譜聚類[J]. 電子學報, 2010, 38(8)：1880-1891.KONG W Z, SUN Z H, YANG C, et al. Automatic spectral clustering based on eigengap and orthogonal eigenvector[J]. Acta Electronica Sinica, 2010, 38(8)：1880-1891.

[11] ZHOU D, BOUSQUET O, LAL T N, et al. Learning with local and global consistency[A]. Proceedings of the 16th Advances in Neural Information Processing Systems(NIPS 2004)[C]. Vancouver, British Columbia, Canada, 2004. 321-328.

[12] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. The National Academy of Science, 2002,9(12)：7821-7826.

[13] 楊博, 劉大有, 劉際明等. 復雜網絡聚類方法[J]. 軟件學報, 2009,20(1)：54-66.YANG B, LIU D Y, LIU J M, et al. Complex network clustering algorithms[J]. Journal of Software, 2009, 20(1)：54-66.

[14] PINNEY J W, WESTHEAD D R. Betweenness-based Decomposition Methods for Social and Biological Networks[M]. Interdisciplinary Statistics and Bioinformatics, Leeds University Press, 2007.

[15] MEILA M, XU L. Multiway Cuts and Spectral Clustering[R]. University of Washington, 2003.

[16] 劉銘, 王曉龍, 劉遠超. 基于語義的高維數據聚類技術[J]. 電子學報, 2009, 37(5)：925-929.LIU M, WANG X L, LIU Y C. Clustering technology for high dimensional data based on semantics[J]. Acta Electronica Sinica, 2009,37(5)：925-929.