一種基于余弦函數(shù)和矩陣變換的譜聚類算法

張永紅，楊 朋，李 純

(1.哈爾濱工程大學(xué)信息與通信工程學(xué)院，哈爾濱150001;2.91685部隊69分隊，海南陵水572400)

聚類分析是一個十分困難而又非常重要的問題.目前已有上百種聚類算法，在所有的聚類算法中，K均值算法由于簡單高效而備受關(guān)注，它是使用最廣泛的算法之一.然而，它較易陷入局部最優(yōu)解[1].

譜聚類作為一種較新的聚類方法，可以彌補(bǔ)K-means算法的這一缺點.譜聚類方法對簇的形狀不作強(qiáng)的假設(shè)，也不存在局部最優(yōu)解，它只要求解決特征值分解問題[2].另外，譜聚類的理論依據(jù)相對比較充足.其有效性可以從不同的角度加以解釋，例如可以從譜圖理論[3]，圖上的隨機(jī)游走理論[3-4]，矩陣擾動分析理論[5]等角度解釋其有效性.

然而，傳統(tǒng)譜方法聚類的一大缺點是它解決特征值分解問題的固有計算復(fù)雜度為O(n3)[6].因此，快速地進(jìn)行特征值分解顯得尤為重要.

本文提出了CMTSC，它將余弦相似度的概念和矩陣變換技術(shù)結(jié)合起來，在保證取得較好的聚類效果的同時實現(xiàn)了更快速的特征值分解和聚類分析.因而具有一定的實際應(yīng)用價值.

1 傳統(tǒng)譜聚類

設(shè)無向圖G=(W，E，V)，其中:W，E，V 分別為圖G的相似度矩陣、邊集和頂點集，每條邊eij的權(quán)值為wij，它表示頂點ai與aj的相似程度.W=wij(1≤i，j≤n)包含了無向圖G的所有分類信息.

設(shè)給定數(shù)據(jù)集包含n個數(shù)據(jù)點，每個數(shù)據(jù)點由p個屬性進(jìn)行描述，則該數(shù)據(jù)集可描述為A∈Rn×p其相似度矩陣為W=wij(1≤i，j≤n)，它的度矩陣為 D=dii=∑j=N(i)wij(1≤i≤n)，其中:N(i)表示點i的鄰域內(nèi)的所有點.圖G的拉普拉斯矩陣L=D-W.歸一化的拉普拉斯矩陣為Ln=D-1/2LD-1/2.

傳統(tǒng)譜聚類的一般步驟可歸納如下.

算法1傳統(tǒng)譜聚類

輸入:待聚類數(shù)據(jù)集A，類別數(shù)K.

輸出:A中每個數(shù)據(jù)點所屬的類別.

1)根據(jù)數(shù)據(jù)集A建立圖G的相似度矩陣W，度矩陣D和拉普拉斯矩陣L.

2)對拉普拉斯矩陣L進(jìn)行特征值分解，取特征向量矩陣U的前K個最大的特征向量，構(gòu)建矩陣∈Rn×k

2 基于余弦函數(shù)和矩陣變換的譜聚類算法的構(gòu)造

2.1 余弦相似度

由給定的數(shù)據(jù)集 A∈Rn×p構(gòu)造圖G=(W，E，V)，這里 A=[a1，a2，…，an]T，其中:1≤i≤n，若采用余弦函數(shù)，則圖的相似度矩陣可表示為W=[wij]n×n，其中:

稱為余弦相似度，相應(yīng)地，稱W為余弦相似度矩陣.如果歸一化數(shù)據(jù)集A，即存在‖ai‖=‖aj‖=1，那么，余弦相似度可簡化為 wij=〈 ai，aj〉，相應(yīng)地，矩陣 W 可簡化為 W=[wij]n×n=AAT.借助軟件Matlab，可快速地得到矩陣W.

2.2 矩陣變換技術(shù)

定義1 滿足FR=I，但并不滿足RF=I的矩陣稱為矩陣F的右偽逆矩陣[7].

定理1 當(dāng)且僅當(dāng)m≤n時，矩陣F∈Cm×n可能存在右偽逆矩陣.且定義FRP=FT(FFT)-1是F的右偽逆矩陣[7].

命題1 如果已知矩陣 A∈Rn×p，F(xiàn)∈Rp×p和 B∈Rn×p，其中 n?p，那么，對于線性方程組 AF=B，它的解A可以記為:

A∈Rn×p設(shè)的奇異值分解為 A=U∑VT，其中，UUT=I∈Rn×n，VVT=E∈Rp×p，矩陣∑ =diag{σ1，σ2，…，σp}且 σ1≥σ2≥…≥σp≥0.不難推導(dǎo)出AT的奇異值分解為，

這樣可得，構(gòu)造矩陣 P=ATA=V∑2VT∈Rp×p，且 p?n.對等式A=U∑VT，兩邊可同時乘上矩陣(∑VT)RP，并用右偽逆矩陣的定義式，不難推導(dǎo)出，

矩陣變換的一個重要特點是:對小塊矩陣P進(jìn)行特征值分解，得到特征向量矩陣V，再借助矩陣變換的手段用矩陣V來表示特征向量矩陣U，從而跳過了直接對大塊矩陣W進(jìn)行特征值分解的過程.它的優(yōu)點在于實現(xiàn)了特征值分解過程的計算復(fù)雜度由O(n3)向O(np2+p3)的轉(zhuǎn)變.

2.3 基于余弦函數(shù)和矩陣變換的譜聚類算法的描述

給定一幅彩色圖像。因為對一幅彩色圖像，單個顏色空間不足以描述它的全部信息，因此，本文用RGB、LUV和HSV三個顏色空間，連同灰度值和空間位置來描述一個像素，這樣，圖中每個像素均可由一個p=10維的行向量來表示，相應(yīng)地圖像的數(shù)據(jù)集矩陣可表示為A∈Rn×p.

至此，CMTSC的實現(xiàn)步驟可以概括如下.

算法2一種基于余弦函數(shù)和矩陣變換的譜聚類算法(CMTSC)

輸入:數(shù)據(jù)集A∈Rn×p，聚類類別數(shù)K.

輸出:數(shù)據(jù)集A中每個數(shù)據(jù)對象所屬的類別.1)歸一化數(shù)據(jù)集A，并構(gòu)造小矩陣P.

2)特征值分解矩陣P，得到矩陣V和∑2.

3)取∑2和V的前K列構(gòu)成矩陣和VK.4)利用式(5)計算矩陣U，其中，∑+和V分別用和VK取代.

5)對歸一化后的矩陣U進(jìn)行K-means聚類.

表1展示了算法1和算法2兩者主要部分的計算復(fù)雜度，其中，n，p，K和t分別代表數(shù)據(jù)點總數(shù)，單個數(shù)據(jù)點的屬性個數(shù)，聚類類別數(shù)和K-means的迭代次數(shù).

表1 算法1和2的主要部分的計算復(fù)雜度

3 實驗設(shè)計與結(jié)果分析

為了驗證CMTSC的有效性和高效性，本文設(shè)計了兩組實驗.在UCI數(shù)據(jù)庫中部分?jǐn)?shù)據(jù)集上的聚類結(jié)果和在Berkeley圖像庫中部分圖像上的分割結(jié)果驗證了CMTSC的有效性和高效性.

實驗環(huán)境:硬件環(huán)境，CPU Intel Core 2 Quad Q6600 2.4G，Internal memory 4G，Hard disk Hitachi HDP 725050GLA360 500G.軟件環(huán)境，Windows 2003+Matlab2007b.

3.1 實驗數(shù)據(jù)描述及評價指標(biāo)

在表2的描述中，Sonar，C.M.C，Segmentation，B.C.W，Glass，Waveform 分別是如下數(shù)據(jù)集的縮寫，Connectionist Bench(Sonar，Mines vs.Rocks)，Contra- ceptive Method Choice，Image Segmentation，Breast Cancer Wisconsin(Original)，Glass Identification，和Waveform Database Generator(Version 1).圖1展示了取自Berkeley圖像庫中三幅大小為481×321的原始圖像，它們分別是馬，花，和房子.

表2 實驗數(shù)據(jù)集描述

圖1 三幅原始彩色圖像

文獻(xiàn)[8]采用F值度量法(F-measure)來度量聚類結(jié)果和已知類別標(biāo)簽的匹配程度.F-measure是文本聚類中常用的一種對聚類結(jié)果進(jìn)行外部評價的方法.當(dāng)聚類標(biāo)簽與真實的類別標(biāo)簽完全一致時，F(xiàn)值達(dá)到最大值1，反之為0.為了更好地評測聚類算法的性能，通常進(jìn)行多次聚類，獲得多次評價結(jié)果，最終的評價結(jié)果取其平均值.為了評價實驗所用算法對彩色圖像的分割效果，將它們的分割結(jié)果分別與人工分割的結(jié)果進(jìn)行對比.一般認(rèn)為，如果聚類算法所得結(jié)果與人工分割結(jié)果越接近，那么就認(rèn)為該算法越有效.

3.2 實驗方法及參數(shù)設(shè)置

以下是實驗中用到的幾種方法的參數(shù)設(shè)置:

K-means:實驗中用于測試的幾種算法在最后都用到了K-means，本文直接調(diào)用了Matlab內(nèi)置的K-means函數(shù).相關(guān)參數(shù)設(shè)置如下:隨機(jī)選擇K個樣本點作為初始聚類中心，距離參數(shù)選擇為余弦，最大允許迭代次數(shù)為100次，在進(jìn)行文本聚類實驗時算法迭代次數(shù)選擇為25次，在進(jìn)行圖像分割實驗時其迭代次數(shù)選擇為1次.

利用 Nystr?m 方法的譜聚類(Nystr?m):采用文獻(xiàn)[9]提出的方法進(jìn)行譜聚類.采樣點數(shù)選擇為100個，高斯核的尺度因子設(shè)置為0.5.實驗1、2中K分別為數(shù)據(jù)集的真實類別數(shù)和主觀分割數(shù).

基于 Nystr?m的快速譜聚類(FSCN):與Nystr?m的惟一區(qū)別是FSCN采用余弦相似度.除無需設(shè)置尺度因子外，其余參數(shù)設(shè)置同上[10].

CMTSC:CMTSC的結(jié)合了余弦函數(shù)、矩陣變換技術(shù)和傳統(tǒng)譜聚類方法.K的設(shè)置同上.

3.3 CMTSC在文本數(shù)據(jù)集上性能的驗證

為了驗證CMTSC對文本數(shù)據(jù)集進(jìn)行聚類分析的有效性和高效性，本文將它與K-means、Nystr?m和FSCN進(jìn)行了比較.所得的各組F值及相應(yīng)的執(zhí)行時間分別如表3、4所示.表中幾個重要結(jié)果用“粗體+下劃線”標(biāo)出.

表3 三種算法測試所得的F值

表4 三種算法的執(zhí)行時間(單位:s)

從表3、4中可以看出:1)在 Segmentation，B.C.W和Glass數(shù)據(jù)集上，F(xiàn)SCN取得了高于Nystr?m的F值，在其他三個數(shù)據(jù)集上，兩者取得了比較接近的F值，因為Nystr?m可以被應(yīng)用到文本聚類分析中，且FSCN和Nystr?m的惟一區(qū)別是FSCN采用了余弦相似度的概念，再者總的來說FSCN取得了不遜于K-means的F值，因此，可以說能夠成功地將余弦相似度引入到文本聚類分析中;2)在Sonar，C.M.C，Segmentation 和 B.C.W 數(shù)據(jù)集上，CMTSC都取得了最高的F值，在另外兩個數(shù)據(jù)集上，未取得最高的F值.這是聚類的復(fù)雜性所致.因此可說將CMTSC應(yīng)用于文本聚類分析中是有效的;3)FSCN的聚類效率高于Nystr?m，再聯(lián)系兩算法的區(qū)別，可以說余弦相似度的引入對算法的聚類效率的提高作了貢獻(xiàn)，這是由指數(shù)運(yùn)算的計算復(fù)雜度要高于乘法運(yùn)算的計算復(fù)雜度決定的;4)與其他幾種聚類算法相比，CMTSC最快地給出了F值，于是，不難得出CMTSC可以高效地進(jìn)行文本聚類分析的事實.5)在數(shù)據(jù)對象數(shù)為5 000的Waveform數(shù)據(jù)集上，CMTSC的執(zhí)行速度比K-means快了近2倍，且不基于抽樣技術(shù)，這表明，與抽樣技術(shù)一樣，矩陣變換技術(shù)可以被應(yīng)用到大規(guī)模數(shù)據(jù)集的聚類分析中.至此，CMTSC被應(yīng)用于文本聚類分析中的有效性和高效性得到了驗證.

3.4 CMTSC在圖像分割中的性能的驗證

為了驗證CMTSC的有效性和高效性，本文將之與 K-means、Nystr?m、FSCN 和人工分割算法在上述三幅彩色圖像上取得的分割結(jié)果進(jìn)行了對比分析.同時，為了提高前四種算法的抗噪性，文章對彩色圖像進(jìn)行了四鄰域加權(quán).加權(quán)算子為

經(jīng)過該加權(quán)預(yù)處理，圖像在一定程度上得到平滑，大部分較細(xì)小的噪聲點也被濾掉了.

圖2中，從左到右，前四列分別是K-means、Nystr?m、FSCN、CMTSC 的分割結(jié)果，第五列為人工分割結(jié)果(參考標(biāo)準(zhǔn)).表5給出了前四種算法相應(yīng)的執(zhí)行時間.

圖2 五種方法的分割結(jié)果

表5 各個算法的分割時間(單位:s)

一方面，對比圖2中三幅圖像的分割效果，可以得出，CMTSC的分割結(jié)果和人工分割的結(jié)果具有更強(qiáng)的一致性.從圖2中的第2列和第3列可以看出，在三幅圖像上Nyst?m和FSCN取得了幾乎完全一致的分割效果，且兩者的惟一區(qū)別是構(gòu)造相似度的技術(shù)不同.這表明這兩種相似度的構(gòu)造技術(shù)均有效，即說明余弦相似度可以被引入到圖像分割領(lǐng)域.再將前四列與最后一列作對比，不難看出，在對圖1(A)的分割上，因為圖的背景相對簡單，所以前4種方法取得了幾乎完全相同的效果，且與人工分割結(jié)果相近.這在一定程度上說明了CMTSC被應(yīng)用于圖像分割領(lǐng)域的有效性.在對圖1(B)的分割結(jié)果中可以看到第1列和第4列的分割結(jié)果更接近第5列.這進(jìn)一步說明了CMTSC的有效性.在對圖1(C)的分割結(jié)果中，第2、3、4列的效果更接近第5列.這表明矩陣變換技術(shù)和抽樣技術(shù)一樣可以被應(yīng)用到圖像分割領(lǐng)域.綜上所述，將CMTSC應(yīng)用于圖像分割領(lǐng)域是有效的.另一方面，從表5中可以看出，CMTSC的執(zhí)行效率最高.相對于Nystr?m的執(zhí)行時間，在上述三幅圖像上FSCN 分別縮短了 |10.925 9-3.333 8|/10.9259=69.49%，|10.711 6-3.380 4|/10.711 6=68.44% 和 |10.3636-3.4044|/10.3636=67.15%.這表明余弦相似度對提高算法的執(zhí)行效率作了較大的貢獻(xiàn)，另外還可以補(bǔ)充一點，即數(shù)據(jù)集的規(guī)模越大，其貢獻(xiàn)越大.Nystr?m和FSCN的執(zhí)行時間比K-means的執(zhí)行時間要長，而CMTSC的執(zhí)行時間比K-means的執(zhí)行時間要短.這表明，雖然譜聚類實現(xiàn)了數(shù)據(jù)從高維復(fù)雜結(jié)構(gòu)向低維簡單結(jié)構(gòu)的映射，在新的譜空間上得到了原數(shù)據(jù)集的一個低維嵌入，且這個嵌入在結(jié)構(gòu)分布上更為簡單，這在一定程度上會縮短譜算法在運(yùn)行K-means階段消耗的時間，但抽樣技術(shù)會比矩陣變換技術(shù)更耗時，這說明將矩陣變換技術(shù)應(yīng)用到圖像分割領(lǐng)域更具優(yōu)勢.綜上所述，CMTSC能夠在保證取得較好的聚類效果的同時擁有較高的執(zhí)行效率.至此，CMTSC被應(yīng)用于圖像分割領(lǐng)域的有效性和高效性得到了驗證.

4 結(jié)語

本文設(shè)計了一種基于余弦函數(shù)和矩陣變換的譜聚類算法.該算法將余弦函數(shù)和矩陣變換技術(shù)融入到譜聚類方法的基本思想之中，一方面，跳過了譜聚類方法在建立相似度圖時設(shè)置相關(guān)參數(shù)的過程，既降低了譜算法的難度，又降低了譜算法在計算相似度矩陣時所需的時間.另一方面，利用矩陣變換技術(shù)，以計算復(fù)雜度為O(npK+p3)而非O(n3)的代價實現(xiàn)了相似度矩陣W的特征值分解.最后通過實驗驗證了CMTSC在聚類分析中的有效性和高效性.

[1] 孫吉貴，劉 杰，趙連宇.聚類算法研究[J].軟件學(xué)報，2008，19(1):48-61.

[2] DING S F，ZHANG L W，ZHANG Y.Research on spectral clustering algorithms and prospects[C]//2010 2nd International conference on computer engineering and technology.Chengdu，China，2010:149-153.

[3] LUXBURG U.A tutorial on spectral clustering[J].Statistics and Computing，2007，17(4):395-416.

[4] ANDREW Y N，MICHAEL I J，YAIR W.On spectral clustering:analysis and an algorithm[C]//Proceedings of the Conference on Advances in Neural Information Processing Systems.Massachusetts，USA:MIT Press，2002:849-856.

[5] 李小斌，田 錚.基于譜聚類的圖像多尺度隨機(jī)樹分割[J].中國科學(xué)E輯:信息科學(xué)，2007，37(8):1073-1085.

[6] 徐 森，盧志茂，顧國昌.使用譜聚類算法解決文本聚類集成問題[J].通信學(xué)報，2010，31(6):58-66.

[7] 張賢達(dá).矩陣分析與應(yīng)用[M].北京:清華大學(xué)出版社，2004:72-73.

[8] TAN P N，SREINBACH M，KUMAR V.Introduction to Data Mining[M].MA，USA:Addison-Wesley，2006.

[9] CHARLESS F，SERGE B，F(xiàn)AN C，et al.Spectral grouping using the nystr?m method[J].IEEE Trans.Pattern Anal.Mach.Intell.，2004，26:214-225.

[10] 位小記，謝 紅，郭 慧.基于高階累積量和星座圖的調(diào)制識別算法[J].哈爾濱商業(yè)大學(xué)學(xué)報:自然科學(xué)版，2011，27(4):609-613.