吳健，崔志明，時(shí)玉杰，盛勝利，龔聲蓉

（1. 蘇州大學(xué) 智能信息處理及應(yīng)用研究所，江蘇 蘇州 215006；2. 美國(guó)阿肯色中央大學(xué) 計(jì)算機(jī)科學(xué)系，阿肯色州 康威 72035-0001）

1 引言

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

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

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

2 LDSC算法

2.1 算法思想

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

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

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

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

2.2 無(wú)向圖構(gòu)建

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

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

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

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

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

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

2.2.2 局部密度定義

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

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

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

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

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

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

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

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

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

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

則矩陣P可表示為

Step4 選取剩余{Dx, x = 1,2,… ,n - num}中的最小值 D(n-num)（下標(biāo)n - n um表示未進(jìn)行k鄰近點(diǎn)連線操作的點(diǎn)的個(gè)數(shù)），其對(duì)應(yīng)點(diǎn)為 Vx， D(n-num)定義為

統(tǒng)計(jì)出 Vx一行對(duì)應(yīng)鄰接矩陣中1的個(gè)數(shù)m，然后將與k - m 個(gè)鄰近點(diǎn)連線?？芍?Vx的k鄰近點(diǎn)集{Vxl,l = 1 ,2,… , k }，Vxl表示距離點(diǎn) Vx第l近的點(diǎn)，初始化 l =1， c ount= 0 。

Step5 當(dāng)l≤k時(shí)，進(jìn)行如下判斷。

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

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

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

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

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

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

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

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

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

B計(jì)算式為

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

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

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

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

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

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

若不能直接也不能通過(guò)傳遞相似性得出兩點(diǎn)相似，則兩點(diǎn)不具有相似性。

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

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

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

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

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

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

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

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

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

2.4 算法實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

實(shí)驗(yàn)1 人工數(shù)據(jù)集測(cè)試

1) 理想分類數(shù)據(jù)實(shí)驗(yàn)

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

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

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

2) 非線性數(shù)據(jù)實(shí)驗(yàn)

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

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

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

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

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

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

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

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

實(shí)驗(yàn)2 UCI數(shù)據(jù)集測(cè)試

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

相似矩陣構(gòu)造是譜聚類中的瓶頸問(wèn)題。本文提出了一種基于局部密度構(gòu)造相似矩陣的譜聚類算法，算法首先對(duì)樣本點(diǎn)按照局部密度由密到疏進(jìn)行排序，并按照設(shè)計(jì)的連接策略構(gòu)建無(wú)向圖；然后基于邊介數(shù)構(gòu)造無(wú)向圖的權(quán)值矩陣，從而得到相似矩陣；最后利用經(jīng)典聚類方法對(duì)特征向量空間中的數(shù)據(jù)點(diǎn)進(jìn)行聚類。實(shí)驗(yàn)結(jié)果表明，本文算法得到的相似矩陣能更好地表示數(shù)據(jù)樣本點(diǎn)之間的相似性，算法具有較好的頑健性。但是，譜聚類算法存在著面對(duì)高維數(shù)據(jù)集時(shí)聚類正確率降低的共同問(wèn)題，下一步研究重心將放在提高高維數(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] 鄧曉政, 焦李成, 盧山. 基于非負(fù)矩陣分解的譜聚類集成SAR圖像分割[J]. 電子學(xué)報(bào), 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] 徐森, 盧志茂, 顧國(guó)昌. 使用譜聚類算法解決文本聚類集成問(wèn)題[J].通信學(xué)報(bào), 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] 李建元, 周腳根, 關(guān)佶紅等. 譜圖聚類算法研究進(jìn)展[J]. 智能系統(tǒng)學(xué)報(bào), 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]. 電子學(xué)報(bào), 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] 孔萬(wàn)增, 孫志海, 楊燦等. 基于本征間隙與正交特征向量的自動(dòng)譜聚類[J]. 電子學(xué)報(bào), 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] 楊博, 劉大有, 劉際明等. 復(fù)雜網(wǎng)絡(luò)聚類方法[J]. 軟件學(xué)報(bào), 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] 劉銘, 王曉龍, 劉遠(yuǎn)超. 基于語(yǔ)義的高維數(shù)據(jù)聚類技術(shù)[J]. 電子學(xué)報(bào), 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.