基于局部密度構(gòu)造相似矩陣的譜聚類算法

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

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

1 引言

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

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

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

2 LDSC算法

2.1 算法思想

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

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

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

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

2.2 無向圖構(gòu)建

2.2.1 現(xiàn)有構(gòu)圖方法分析

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

圖1 原始樣本數(shù)據(jù)集

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

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

圖2 傳統(tǒng)構(gòu)圖方法的構(gòu)圖結(jié)果

2.2.2 局部密度定義

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

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

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

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

2.2.3 無向圖構(gòu)建步驟

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

構(gòu)圖算法步驟如下。

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

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

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鄰近點連線操作的點的個數(shù)），其對應點為 Vx， D(n-num)定義為

統(tǒng)計出 Vx一行對應鄰接矩陣中1的個數(shù)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，重新執(zhí)行Step 5；如果 Vxl的度已飽和（即度為k），則點 Vx不與點 Vxl相連，即鄰接矩陣中置0， l =l+1；否則，連接兩點，對應鄰接矩陣中置 1，且 c ount = c ount+ 1 ，l = l +1。

2) 如果count＞k-m，轉(zhuǎn)Step 6，否則重新執(zhí)行Step 5。

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

利用本文構(gòu)圖方法所得構(gòu)圖結(jié)果如圖3所示。

圖3 改進KNN構(gòu)圖結(jié)果(k=6)

從圖3中可以看出，3類樣本集有效分開且內(nèi)部連通，得到3個獨立的連通子圖，達到了預期目標?；诰植棵芏葮?gòu)圖，可以保證空間位置上相鄰的點互連，從而同屬一類。Step 5中的改進可以避免不同類數(shù)據(jù)點間互連。

2.3 相似矩陣構(gòu)造

現(xiàn)實世界中的很多系統(tǒng)都以網(wǎng)絡形式存在，具有同簇節(jié)點相互連接密集、異簇節(jié)點相互連接稀疏的特點。復雜網(wǎng)絡聚類方法可歸納為2類：基于優(yōu)化的方法和啟發(fā)式方法[13]?；趫D分割理論的譜聚類是一種基于優(yōu)化的聚類方法。啟發(fā)式方法將復雜網(wǎng)絡聚類問題轉(zhuǎn)化為預定義啟發(fā)式規(guī)則的設計問題，被廣為引用的GN算法的啟發(fā)式規(guī)則是：簇間連接的邊介數(shù)應大于簇內(nèi)連接的邊介數(shù)。邊介數(shù)概念最早由Girvan和Newman提出，被用作評估復雜網(wǎng)絡關鍵邊的重要度指標。本文借鑒GN算法思想，提出了一種新穎的基于邊介數(shù)度量的權(quán)值矩陣計算方法。

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

B計算式為

uv路徑的數(shù)目表示經(jīng)過邊e的點u到點v的最短路徑數(shù)目。

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

通過分析樣本數(shù)據(jù)集的分布特性，筆者研究得出樣本點分布具有如下性質(zhì)。

性質(zhì)1 點間傳遞相似性。

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

性質(zhì)2 點間阻斷性。

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

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

任意點對間權(quán)重賦值的步驟如下。

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

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

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

圖4 權(quán)值計算示例

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

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

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

2.4 算法實現(xiàn)

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

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

輸出：數(shù)據(jù)點集的劃分結(jié)果 C1,… ,Ck。

1) 利用本文提出的改進KNN算法對輸入的數(shù)據(jù)點構(gòu)造相似圖G。

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

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

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

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

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

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

3 實驗結(jié)果與分析

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

實驗1 人工數(shù)據(jù)集測試

1) 理想分類數(shù)據(jù)實驗

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

圖5 人造9類數(shù)據(jù)

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

2) 非線性數(shù)據(jù)實驗

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

圖6 本文譜聚類分類結(jié)果

圖7 雙月牙數(shù)據(jù)

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

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

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

圖9 本文算法針對3種人工挑戰(zhàn)性問題的聚類結(jié)果

圖10 文獻[10]算法針對3種人工挑戰(zhàn)性問題的聚類結(jié)果

實驗2 UCI數(shù)據(jù)集測試

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

表1 UCI數(shù)據(jù)集基本信息

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

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

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

表2 UCI數(shù)據(jù)集上的最優(yōu)聚類誤差和平均運行時間

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

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

4 結(jié)束語

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

[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]. 智能系統(tǒng)學報, 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] 楊博, 劉大有, 劉際明等. 復雜網(wǎng)絡聚類方法[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] 劉銘, 王曉龍, 劉遠超. 基于語義的高維數(shù)據(jù)聚類技術[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.