譜圖聚類算法研究進展

李建元，周腳根，關佶紅，周水庚

(1.同濟大學 計算機科學與技術系，上海 201804;2.上海市農業科學院 數字農業與工程技術研究中心，上海 201106;3.復旦大學上海市智能信息處理重點實驗室，上海 200433)

譜圖聚類算法研究進展

李建元1，周腳根2，關佶紅1，周水庚3

(1.同濟大學 計算機科學與技術系，上海 201804;2.上海市農業科學院 數字農業與工程技術研究中心，上海 201106;3.復旦大學上海市智能信息處理重點實驗室，上海 200433)

近10多年來，關于譜圖聚類的研究成果非常豐富，為了總結和理清這些工作之間的脈絡關系，揭示最新的研究趨勢，回顧和比較了典型的圖割目標函數，以及這些目標函數的譜寬松解決方法，總結了譜聚類算法的本質.另外，討論了譜圖聚類的幾個關鍵問題:相似圖的構建方法、復雜性與擴充性、簇數估計、半監督譜學習等.最后，展望了譜圖聚類算法的主要研究趨勢，如探尋其理論解釋，構建更貼切的相似圖，通過學習篩選特征，應用實例化等.

譜圖聚類;圖割目標函數;譜寬松方法;相似圖構建;半監督學習

聚類技術是探測數據分析的關鍵步驟，具有非常重要的科學地位和應用價值.傳統的聚類算法如K－means［1］和 EM［2］等，它們雖然簡單，但缺乏處理復雜簇結構的能力，并可能陷入局部解.近10余年來，譜聚類算法作為一種有競爭力的技術，成為一個新的研究熱點，與之相關的研究成果也頗為豐富.

譜聚類是一類基于圖論的聚類算法，其算法框架一般包括兩大步:首先構造一個相似圖用以描述數據點之間的相似關系;然后根據某個優化目標將圖分割為若干不連通的子圖.子圖中包含的點集被視為簇.以聚類為目的的圖割優化目標通常均為NP離散最優化問題，譜聚類的提出使得問題可以在多項式時間內求解.較之K－means等傳統算法，譜聚類還具有另一優勢:它可以處理更為復雜的簇結構(如非凸數據［3－4］)，并找到全局寬松解.故而，譜聚類已被推廣應用到許多領域，如計算機視覺［5－8］、集成電路設計［9］、負載均衡［10－11］、生物信息［12－15］、文本分類［16－17］等.

譜聚類技術可以從以下幾個角度進行分類:1)從是否考慮樣本外擴展的角度，可以將其分為離線譜聚類(如文獻［3，5，18－19］等)和增量譜聚類(如文獻［20－21］等);2)從是否具有約束條件或者先驗知識的角度，可以將其分為無監督譜聚類和約束譜聚類(如文獻［22］等);3)按優化目標的個數可以將其分為單目標優化(絕大多數)和雙目標優化(如文獻［23］等);4)從運行環境上，可將其分為串行譜聚類和并行譜聚類(如文獻［24］等).

迄今為止，譜聚類技術已經得到長足的發展，總結和理清已有研究之間的關系，揭示未來的研究方向是十分有必要的.已出現的綜述文章各有側重.Verma等人［25］主要從實驗的角度比較了幾種典型的譜聚類算法的性能，并提出若干改進算法.Luxburg等人［26］從統計學習的理論高度比較了典型的歸一化和非歸一化譜聚類算法，并總結了相似圖構建方法和簇數估計等問題.Maurizio等人［27］調查了基于核的聚類方法和譜方法，并得出這2種方法的共同本質是跡最優化問題.國內方面，關于該領域較好的綜述如文獻［28］，其從算法層面上較為全面地進行了比較.

本文盡管與上述綜述文獻在內容上有一些重疊之處，但卻包含了一些新的內容.一方面，涉及的內容更全面、脈絡關系更清楚，如從圖論到代數分割特性的發展、從圖割目標函數到譜圖聚類算法的演變、譜圖聚類算法的本質等.另一方面，討論的問題更深入，如圖的構建、邊權的度量、簇數的估計、復雜性與擴充性、半監督譜學習.最后，總結了有待澄清的一些的理論和實際問題，指出了譜圖聚類算法的研究趨勢.

1 基本理論

1.1 圖論與代數圖論

圖論是數學的一個重要分支，是以1736年大數學家歐拉關于Konigsberg七橋問題的論文為里程碑開始發展的.它研究的是關于圖(graph)的理論和方法.簡單來說，圖是點集和邊集或弧集構成的圖形，其中邊或弧用來表示一對節點間存在某種關系，邊或弧可以賦予權值，權值用來量化節點之間的關系.根據是否加權，圖可分為無權圖和加權圖;根據邊是否具有方向，可將圖分為有向圖和無向圖.

常用的圖的表示方法有鄰接矩陣(記作A)和拉普拉斯矩陣(記作L).無權圖的鄰接矩陣表示法如圖1(a)、(c)所示，用0表示一對頂點間無邊，用1表示一對頂點間存在一條邊.加權圖是用某個實數來反映頂點之間關系之不同，如圖1(b)、(d)所示.拉普拉斯矩陣L=D－A，其中D為對角陣，對角線上的數值等于A的行和的絕對值，非對角元素為0.關于圖論的基本知識，可參考最新版圖論教程［29］.

圖1 圖及其鄰接矩陣Fig.1 Examples of graphs and adjacent matrices

代數圖論是圖論、線性代數以及矩陣計算理論相結合的交叉領域，其研究較早始于19世紀50年代.它是圖論的分支之一，旨在利用代數方法來研究圖，將圖的特性轉化為代數特性，然后利用代數特性和代數方法推導關于圖的定理.事實上，代數圖論的主要內容是圖的譜，粗略地說，譜指的是矩陣的特征值連同其多重解(multiplicites).最早的關于代數圖論的研究如:Fiedler［30］得出了圖的連通性的代數判據，即根據拉氏矩陣的第二小特征值是否為零可以判斷圖是否連通，與第二小特征值對應的特征向量后來被命名為Fiedler向量，它包含了二分一個圖所需要的指示信息.另外，Donath 和 Hoffman［31］、Bames［32］和 Donath［33］等的理論工作建立了圖的譜和圖割之間的另一些關聯.關于代數圖論較全面的介紹可參考文獻［34－36］.

1.2 矩陣與譜

大多數的譜聚類算法是基于拉普拉斯矩陣(以下簡稱“拉氏矩陣”)的譜來進行的.拉氏矩陣分為非歸一化的(L)和歸一化的2種.歸一化的又包括對稱方式(記作Ls)和隨機游走方式(記作Lr)，表達式分別如下:

文獻［37－38］給出了非歸一化拉氏矩陣的部分特性，文獻［36］進一步給出了歸一化拉氏矩陣的部分特性.拉氏矩陣的譜對于圖的分割提供了極為有用的信息，例如，基于Fiedler向量［30］可直接進行圖的二分，基于多個主要特征向量可以進行圖的k分.關于拉氏矩陣的特性，Luxburg［39］對其進行了較全面的概括，在此不再贅述.關于到底應該采用非歸一化拉氏矩陣還是歸一化拉氏矩陣的問題上目前存在著較大的分歧.采用歸一化拉氏矩陣的如文獻［5，23，40］，非歸一化拉氏矩陣的如文獻［41－42］.從實證的角度上，文獻［3，5，43］提供了歸一化拉氏矩陣更適用于譜聚類的證據，即意味著歸一化譜聚類性能比非歸一化譜聚類好.文獻［44］指出在某種特定的條件下采用非歸一化譜聚類較好.而文獻［26］從統計一致性的理論高度，證明了歸一化拉氏矩陣優于非歸一化拉氏矩陣的事實.

另一種可選的矩陣是概率轉移矩陣(記作P).概率轉移矩陣實質上就是相似矩陣的歸一化形式，其表達式如下:

由于歸一化后的相似矩陣的行和為1，因此P中的元素可以理解為馬爾可夫轉移概率.2個節點間的轉移概率越大，則同簇的可能性也越大.概率轉移矩陣的譜也包含了分割圖所需的必要信息，只不過與拉氏矩陣譜稍有區別，例如，次大特征值的特征向量可以指示圖的二分，多個主特征值的特征向量可以指示圖的k分割.有趣的是，如果λ是Px=λx的解，則1－λ 是方程 Lx=λDx的解［45］.

值得一提的另一種新穎矩陣是模塊度矩陣(記作 B).其相關研究主要出自復雜網絡社區［46－49］，它具有明顯物理意義，其表達式如下:

式中:d代表列向量，其元素為節點的度;m表示圖的總邊權;B中的元素表示的是成對節點間實際的邊數與期望的邊數之差，或者說是實際的邊數超出期望邊數的程度.因此，此類矩陣也直接促成了一個目標函數，即最優分割應使得各社區中(與“簇”相對應)邊的稠密程度盡量超出預期.就矩陣特性而言，模塊度矩陣與拉氏矩陣具有相似之處，例如:行和(列和)為0，0是其特征值;但又具有明顯區別，模塊度矩陣不是一個半正定矩陣，也就是說其部分特征值可能為負.就分割圖方面，基于其最大特征值的特征向量可以進行網絡二分，基于多個主特征向量可以進行網絡k分.

2 主要的圖割目標函數

圖割聚類的雛形是最小生成樹方法(minimum spanning tree，MST)［50－51］.之后出現的目標函數有最小割(minimum cut，Mincut)［32，52－53］、比率割(ratio cut， Rcut)［40，54－56］、 規 范 割 (normalized cut，Ncut)［5，57］、最 小 最 大 割 (max flow/min cut，MMCut)［58］和平均割(average cut，Acut)［59］等.除此以外，還有一些其他的優化目標，如用譜寬松來解決K－means目標函數的方法［60］，以及文獻［23］提出的雙準則方法.

最小生成樹(MST)聚類法是 Zahn［50］提出的，該算法首先由圖的鄰接矩陣得到最小生成樹，然后從最小生成樹中去除掉若干權值較大的邊從而產生一個連通分量集，以此達到聚類的目的.該方法在探測明顯分離的簇時是成功的，但若改變節點密度，其性能會變差.另一個缺點是，Zahn的研究是在事先知道簇結構(如分離簇、接觸簇、密度簇等)的前提下進行的.

圖的割是指去除一定的邊將一個圖分割為多個連通分量，其中被去除的邊權的總和稱為割(如式(1)所示).Bames［32］最早提出了最小割聚類準則，即在把一個圖分割成k個連通子圖時，尋求割的最小化.Alpert和Yao［18］較早提出了基于譜方法來解決最小割準則的方法，為后來的譜聚類的發展奠定了重要基礎.Wu 和 Leahy［53，61］將最小割運用到圖像分割領域，并基于網絡最大流理論［62］來求解最小割.該準則在圖像分割方面有些許成功的應用，但其最大的問題是可能會導致分割的嚴重不均衡，如分割出“孤點”及“小簇”.能夠產生較均衡的分割的研究有 Wei和 Cheng［40］提出的比率割、Shi和 Malik［5］提出的規范割、Ding等人［58］提出的最小最大割和Sarkar等人［59］提出的平均割，其目標函數分別為式(2)～(5).這些優化目標能夠較好地避免最小割造成的分割嚴重不均衡的問題.

以圖的二分割為例，令V為一個給定的點集，N表示V的一個子集，用M代表VN，w(·，·)表示2個點集之間邊的總邊權，則有:

近10年來復雜網絡的研究快速崛起，Newman系統地研究了無權網絡、加權網絡乃至有向網絡中的網絡社團結構譜算法，運用了模塊度(modularity)函數進行社團發現［46－49］.模塊度準則的思想較為新穎:以無權圖為例，當各社團中的邊的比例盡可能地超出“期望”的邊的比例時，才認為是合理的分割.其中“期望”的邊數指的是根據配置模型得到的一種隨機圖模型.這顯然與傳統的圖割聚類方法的出發點不同，其目標函數為

式中:Q表示模塊度;m表示圖中包含的邊數;ki表示編號為i的節點的度(kj類似);vi和vj只可取－1或1，當vi≠vj是表示將節點i和j劃分到不同社區，反之則屬于同一社區.

3 譜寬松方法解決圖割問題

最小化比率割、規范割、平均割以及最大化模塊度等，均為NP離散最優化問題.幸運的是，譜方法可以為該最優化問題提供一種多項式時間內的寬松解.這里的“寬松”指的是將離散最優化問題寬松到實數域，然后利用某種啟發式方法將其重新轉換為離散解.下面簡要介紹從目標函數到譜方法的演變［39，46，56］.

3.1 圖的二分割問題

3.1.1 比率割

設比率割為c，考慮一個最小化式(2)的圖的二分割問題，令|N|=pn，|M|=qn，其中p，q≥0 且滿足p+q=1，簇指示向量x的元素滿足:

令E表示一個包含n個元素的常向量，其每個元素均設為1.因為拉氏矩陣L的各特征向量正交，而E又是L的一個特征向量，故可得x·E=0.若eij是連接N和M2個點集的邊，則有xi－xj=q－(－p)=1;相反，若eij不是連接N和M2個點集的邊，則有xi－xj=0.從而可得

又因為

合并式(7)、(8)，根據瑞利商定理可得

也即c≥λ2/n，這將意味著圖的二分割的實數域解x由第二小特征值對應的特征向量給出，即求解方程Lx=λx，找到 λ2及其特征向量.由于聚類問題是“離散”最優化問題，故而需要將實數域解離散化，最簡單的離散化方法是閾值法，即:

3.1.2 平均割

與上同理，令指示向量x的分量滿足:

可以得出，在非歸一化拉氏矩陣L與平均割之間存在如下關系:

于是最小化平均割的問題與比率割的解決方法相似，需求解Lx=λx，x的離散化方法也與之類似.

3.1.3 規范割

令指示向量x滿足:

則有

又因為xTDx=vol(V)，故可得

令g=D1/2x，代入上式得

因此最小化規范割相當于求解Lsx=λx或者Lx=λDx，找到歸一化拉氏矩陣的第二小特征值對應的特征向量，然后將其離散化.

3.1.4 模塊度

對于任意無向加權圖，令w表示整個圖的總權值，di代表節點i與其他節點之間的總權值.令Bij=Aij－didj/2w，v為指示向量且僅可取1或－1，當vi=vj時表示節點i與j屬于同一個簇，反之屬于不同的簇.用于聚類的模塊度函數可表達為

式中:w可寫作w=vol(V)/2=∑ijAij，i＞j;di可寫作di=vol(Vi)/=∑jAij.因為∑idi=2w=∑jdj，故存在

于是可得

即矩陣的所有項之和等于0.進一步有

設v是矩陣B的特征向量ui的線性組合，即v=aiui，則有 ai=·v，于是有

另存在關系Bv=λv，故可得

若將v的取值寬松到實數域，則可得當λi取最大特征值且v平行于其對應的特征向量時，Q取最大值.但是網絡社區分割問題仍為離散最優化問題，故依然需要離散化步驟.Newman的方法是使得v的各分量與ui的各分量符號一致，也就是使二者盡量平行.

3.2 圖的k分割

以平均割目標函數為例，來說明圖的k分割問題的譜寬松解決方法［39］.

假定點集V可以分割為k個子集A1，A2，…，Ak，定義指示向量 hi=(h1，i，h2，i，…，hn，i)T，其中:

然后，令H是一個n行k列的矩陣，其列即為不同的指示向量.因為矩陣H的各列向量是相互正交的，即滿足HTH=I.于是有

并存在

綜上可得

即跡最小化問題.取拉氏矩陣的前k個特征向量作為列便可得到矩陣H.然而此處H中的項在實數域中，需要離散化才能達到分類的目的.最簡單的離散化方法是在實數域解H上采用K－means算法或者其他基準算法進行子空間上的聚類.

可以驗證，比率割下的k分割問題與平均割的情況類似，規范割的k分割問題需要將式(9)中的拉氏矩陣L替換為歸一化拉氏矩陣Ls，模塊度的k分割問題需要將式(9)中的拉氏矩陣L替換為模塊度矩陣B.

可見，這些最優化問題，均可運用譜方法來解決.不同的是，比率割、最小最大割、平均割派生出非歸一化的譜聚類算法，而規范割派生出歸一化的譜聚類算法，模塊度派生出一種新的譜分割算法.然而，它們共同的本質是約束條件下的跡最優化問題［63－64］，只不過針對的矩陣不同.

4 譜圖聚類中的幾個關鍵問題

4.1 構圖與加權

令wij為點i和點j之間的邊權，一種最典型的加權方式是利用高斯衰減公式，即wij=exp(－‖xi－xj‖2/σ2).在給定的一個點集上建立相似圖是譜聚類中最基本的問題，主要的方法如下.

1)ε 圖(即閾值圖):當‖xi－xj‖2＜ ε 時，相似度取0，否則取wij，其中ε為正實數.

2)k近鄰圖:當點i(或點j)是點j(或點i)的k個鄰近點之一時，相似度取wij，否則取0.

3)互為k近鄰圖:當i點和j點互相落在對方的k鄰域時，相似度取wij，否則設為0.

4)b－匹配圖［65］:在度約束的前提下最小化圖的總權值得到的一類圖，可利用信任擴散方法求解其權矩陣.

5)擬合圖［66］:以重構誤差為優化目標，節點加權度不小于1為約束條件，利用二次規劃求得的矩陣和圖.

閾值圖能夠確保節點間的相鄰關系幾何對稱，但閾值的選取比較困難.在一些情況下，甚至難以設定一個恰當的閾值得到一個既連通又稀疏的圖.相對較好的選擇應該是k近鄰圖，k容易選取也容易保證得到的是一個稀疏圖，但是k近鄰圖一般是不對稱的，即有向圖.為了使得鄰近關系對稱，通常的做法是簡單地消除方向.但是這樣將導致連接度的不均衡性，即存在若干hub節點，從而可能對聚類問題產生一定的負面干擾.另外，互為k近鄰圖，雖然能保證幾何對稱，可以用于捕捉那些最“重要”的簇，但其缺點是不容易得到稀疏連通圖(當參數k較小時).b－匹配圖就拓撲結構而言是規則的，在部分場合下是優于k近鄰圖的，主要原因是其不存在hub節點，不會造成簇間的邊過分稠密的問題;其缺點是構建一個b－匹配圖時間約為O(bn3)，難以擴展其處理大規模的問題.擬合圖是一種最新的研究成果，此類圖能更自然地表達數據間的關系，且能從理論上保證圖的稀疏性，其缺點依然是構圖的時間耗費太大.

總的來看，盡管新的構圖方法具有一些好的特性，但考慮到其時間耗費巨大，不及k近鄰圖或者互為k近鄰圖經濟實用.近來的一些理論研究已經著眼于討論k的界，即k大于多少時可以保證k近鄰圖的連通性.例如，針對包含足夠多數據點的平面泊松分布數據，Xue 和 Kumer［67］證 明了 當k≥5.177 4×logn時k近鄰圖連通的概率為1.Balister等人［68］進 一 步 證 明 了 更 緊 的 界，即 當k≥0.513 9×logn時，k近鄰圖連通的概率為1.Brito等人［69］利用蒙特卡羅仿真得出了一些實證的參數，這些結果為參數k的選取提供了一定的依據.

σ是高斯核參數，許多研究者都將其設為一個全局值［3，5］，其取值范圍一般滿足‖xi－xj‖ ＞ σ ＞0，通過加入參數σ，將原始的相似關系映射到其他空間.考慮到機器的計算精度，過小的σ會導致相似圖不連通.然而，全局設定σ的值實際上在一些情況下并不是理想的方法.文獻［19］探討了自適應設定局部參數的方式，能夠更加恰當地描述節點間的鄰域關系.其表達式如下:

式中:σi取點i與其第K個鄰近點之間的距離，σj類似.K是一個獨立的參數，從幾何意義上講，它是嵌入空間的數據維數的函數，K的選取較σ更容易.該方法對于常用的人工數據(如環形嵌套的簇結構、簇間密度不同的問題等)的處理效果較好.

4.2 簇數估計問題

自動估計簇數的研究大體上可以分為2類.一種方法是通過分析特征值.文獻［3］分析了在理想狀況下(簇與簇之間的距離為無窮遠)的簇數估計方法:對于歸一化相似矩陣，特征值為1的個數嚴格地對應著簇數.然而實際的情況沒有這么簡單，一種可選的方法是分析特征值缺口(eigen－gap)［70］，在部分應用中，此方法是有效的，但是其缺乏理論根據，而且缺口往往可大可小，難以取舍.文獻［71］提出將相似矩陣的特征值大于1的個數作為簇數的方法，實質上就是一種特征值缺口法.另一種更好的方法是分析特征向量，如文獻［19］通過引入旋轉矩陣和一個優化目標來發現最佳簇數.實驗表明，該方法在一些復雜的合成數據集和圖像分割應用上是有效的.

值得注意的是，以上這些方法要么是基于譜來估計簇數，要么是基于新的優化目標來估計簇數.而直接基于圖割優化目標來確定簇數的研究尚少.雖然Newman［47］提出的重復二分譜算法具有這種能力，但其算法是應用在網絡社區發現問題中的，在點集聚類問題上，尚需推廣和驗證.

4.3 復雜性與擴充性問題

快速求解稀疏矩陣的特征值和特征向量的主要算法是Arnoldi或者Lanczos算法，其他快速方法幾乎都是它們的變體，關于特征空間求解方法的總結可參看文獻［72］.

以非歸一化譜聚類為例，即求解Lx=λx，采用Lanczos算法求解的時間復雜性分析如下.設圖的總邊數為m，考慮典型的稀疏矩陣(即滿足m與節點數n成線性關系)，特征方程左邊需要O(m)次操作，右邊需要O(n)次操作，共O(m+n)次操作.再考慮上Lanczos算法的迭代次數O(n)，求解一個二分問題的時間約為O(n2).于是，重復二分譜聚類問題的時間復雜性約為O(n2logn)，解決k路譜聚類問題約為O(kn2)，空間復雜性為O(n2)，只有采用優化方法存儲稀疏矩陣，才能降低其空間復雜性和時間復雜性.

一些改進的譜算法試圖更快速實現該類算法.如Fowlkes等人［73］運用Nystrom近似方法避免計算整個相似矩陣，Dhillon等人［74］提出了一種不使用特征向量的方法，Yan等人［75］基于局部 K－means聚類或者隨機投影樹來快速近似譜聚類.這些方法雖然改善了擴充性問題，但是損失了精度，而且沒有討論空間復雜性方面的瓶頸問題.然而不論采取何種特征求解方法，當面對大規模的數據集時，都可能會遭遇空間上的瓶頸.考慮最壞的情況，也即非稀疏矩陣，設數據規模n=105，采用鄰接矩陣表示法或者拉氏矩陣表示法，由于每個浮點型實數需要占據4 Byte，則大約需要占用40 GB的存儲空間.

文獻［24］提出了一種并行譜聚類算法，既考慮了存儲空間的并行使用問題，也考慮到了并行分布式計算的問題.他們首先將n個數據實例分配到p個機器節點上，然后用最小磁盤I/O方法在每個機器節點上計算本地數據實例與所有數據實例之間的相似度.這2步與分布式特征求解和分布式參數調整結合起來，大大加速了聚類速度.其快速求解的算法采用的是較流行的ARPACK及其并行版本PARPACK［76］.通過十萬數量級上的文本分類和圖像分類的實證研究，表明了提出的算法有效地改善了譜聚類算法難以擴充到大規模數據集的問題.可見，若要解決大規模數量級的譜聚類問題，需要借助于并行算法.

4.4 半監督譜學習

通常，與分類問題本身無關的特征會使得大多數的譜聚類算法的性能大打折扣.幾乎所有譜聚類的應用都是在某種相似性度量假設基礎之上進行的，這些算法的成功依賴于度量方式的選擇.而已有的大多數譜聚類算法對于不相關的特征具有較差的魯棒性［77］.這種情況需要結合先驗知識來解決，在許多情況下，某些先驗知識是可以獲得的，如文獻［78］提及的空間一致性先驗信息，文獻［79］在相似性度量時依靠結合知識來減輕不相關特征造成的影響，文獻［77，80］提出了從數據中自動學習的方式來確定恰當的核或者相似性度量方法，文獻［77］提供了一個基于實例的相似矩陣學習的總體框架，文獻［78］提出了一種從數據中學習先驗知識的密度敏感的半監督聚類算法等，均取得了較好的效果.

5 結論與展望

圖分割的本質可以歸結為矩陣的跡最小化或最大化問題，而完成該最小化或最大化的任務需要依靠譜聚類算法.在絕大多數情況下，歸一化譜聚類的性能超過非歸一化譜聚類的性能，所以歸一化譜聚類的應用更為廣泛.它之所以吸引了大批研究者，最主要的原因有3點:1)它具有堅實的理論基礎——代數圖論;2)對于較復雜的簇結構，它能得到全局寬松解;3)它能在多項式時間內解決問題.近年來，在與圖和網絡相關的領域中，個性化的改進算法層出不窮，在某種程度上，譜聚類已經成為現代最流行的聚類算法之一.

以下提出今后依然需要探討的幾點問題.

1)譜聚類的理論解釋.例如，在譜聚類中，采用哪些特征向量最好?應該采用多少個特征向量最好?為什么?采用部分特征向量張成的子空間，保留了什么信息?損失了什么信息?

2)如何更恰當地構建相似圖，相似圖構建的好壞決定著譜聚類性能.近來提出的b－匹配圖和擬合圖就是非常有趣和有用的方法，盡管已有的構建方法已經不少，但關于該問題依然需要推陳出新，最核心的一點是如何本質地描述數據之間的關系.

3)加權方式或者參數選擇.雖然構圖的同時已經加權，但也可以考慮重新加權的問題.例如，流形學習領域的一個重要概念“局部線性重構”［81］就是一種有效的重加權方式.再比如，高斯核參數是譜聚類中的一個非常敏感的參數，該參數選擇的恰當與否直接影響著聚類的效果，關于自動選取該參數的研究是另一個難題.

4)如何將優化目標與簇數估計相結合，已有的絕大多數譜算法并不能根據其圖割優化目標來決定簇數，也就是說在算法運行之前簇數是給定的.然而，在許多應用場合中，事先知道簇數是不現實的，如何在圖割優化目標的指導下發現簇數是值得思考的.

5)探討基于其他矩陣的譜聚類算法.如文中提及的模塊度矩陣，它與拉氏矩陣的特性相似但又有很大區別，該算法在處理真實網絡時表現出很好的性能，但是推廣其用于譜聚類，依然有許多問題值得探討.

6)如何在構建相似圖的過程中進行自動特征篩選.例如:針對高維數據，L1圖的構建可以有效地捕捉最稀疏的特征，從而得到非常高的聚類和分類準確性［82］.

7)如何快速解決大規模或超大規模的譜聚類問題.隨著經濟和社會的發展，在許多行業中，需要處理的數據規模與日俱增，雖然現有的研究已經能夠解決10萬數量級的問題，但是解決更大規模的問題仍然具有挑戰性.

8)應用實例化.與各學科或應用領域相結合，通過改進典型的譜聚類算法切實解決實際問題.例如，在網絡文檔分類中，如何恰當地利用全局一致性信息，如何增量地聚類動態更新的博客社區等.

［1］LLOYD S P.Least squares quantization in PCM［J］.IEEE Transactions on Information Theory，1982，28(2):129－137.

［2］DEMPSTER A P，LAIRD N M，RUBIN D B.Maximum likelihood from incomplete data via the EM algorithm［J］.Journal of the Royal Statistical Society—Series B:Statistical Methodology，1977，39(1):1－38.

［3］NG A Y，JORDAN M I，WEISS Y.On spectral clustering:analysis and an algorithm［C］//PIETTERICH T G，BECKER S，GHAHRAMANI Z.Advances in Neural Information Processing Systems.Cambridge，USA:MIT Press，2001:849－856.

［4］RAHIMI A，RECHT B.Clustering with normalized cuts is clustering with a hyperplane［C］//Statistical Learning in Computer Vision Workshop in ECCV 2004.Prague，Czech Republic，2004:1－12.

［5］SHI J B，MALIK J.Normalized cuts and image segmentation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22(8):888－905.

［6］MALIK J，BELONGIE S，LEUNG T，et al.Contour and texture analysis for image segmentation［J］.International Journal of Computer Vision，2001，43(1):7－27.

［7］ZHANG X R，JIAO L C，LIU F.Spectral clustering ensemble applied to SAR image segmentation［J］.IEEE Transactions on Geoscience and Remote Sensing，2008，46(7):2126－2136.

［8］陶文兵，金海.一種新的基于圖譜理論的圖像閾值分割方法［J］.計算機學報，2007，30(1):110－119.

TAO Wenbing，JIN Hai.A new image thresholding method based on graph spectral theory［J］.Journal of Computers，2007，30(1):110－119.

［9］ALPERT C J，KAHNG A B.Multi－way partitioning via geometric embeddings，orderings and dynamic programming［J］.IEEE Transactions on Computer－Aaided Design of Integrated Circuits and Systems，1995，14(11):1342－1358.

［10］DRIESSCHE R V，ROOSE D.An improved spectral bisection algorithm and its application to dynamic load balancing［J］.Parallel Computing，1995，21(1):29－48.

［11］HENDRICKSON B，LELAND R.An improved spectral graph partitioning algorithm for mapping parallel computations［J］.SIAM Journal on Scientific Computing，1995，16(2):452－459.

［12］CRISTIANINI N，SHAWE－TAYLOR J，KANDOLA J.Spectral kernel methods for clustering［C］//Proceedings of the Neural Information Processing Systems.Vancouver，Canada，2001:649－655.

［13］KLUGER Y，BASRI R，CHANG J T，et al.Spectral biclustering of microarray data:coclustering genes and conditions［J］.Genome Research，2003，13(4):703－716.

［14］KULIS B，BASU S，DHILLON I S，et al.Semi－supervised graph clustering:a kernel approach［C］//International Conference on Machine Learning.New York，USA:ACM Press，2005:457－464.

［15］PACCANARO A，CHENNUBHOTLA C，CASBON J A.Spectral clustering of protein sequences［J］.Nucleic Acids Research，2006，34(5):1571－1580.

［16］DHILLON I S.Co－clustering documents and words using bipartite spectral graph partitioning［C］//Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York，USA:ACM Press，2001:269－274.

［17］謝永康，周雅倩，黃萱菁.一種基于譜聚類的共指消解方法［J］.中文信息學報，2009，23(3):10－16.

XIE Yongkang，ZHOU Yaqian，HUANG Xuanjing.A spectral clustering based coreference resolution method［J］.Journal of Chinese Information Processing，2009，23(3):10－16.

［18］ALPERT C J，YAO S Z.Spectral partitioning:the more eigenvectors，the better［C］//Proceedings of the 32nd Annual ACM/IEEE Design Automation Conference.New York，USA:ACM，1995:195－200.

［19］ZELNIK－MANOR L，PERONA P.Self－tuning spectral clustering［C］//Neural Information Processing Systems.Vancouver，Canada，2004，2:1601－1608.

［20］NING Huazhong，XU Wei，CHI Yun，et al.Incremental spectral clustering with application to monitoring of evolving blog communities［C］//Proceedings of the SIAM InternationalConference on Data Mining. Minneapolis，USA，2007:261－272.

［21］ALZATE C，SUYKENS J A K.Multiway spectral clustering with out－of－sample extensions through weighted kernel PCA［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32(2):335－347.

［22］YU S X，SHI J B.Grouping with bias［C］//The Fifteenth Annual Conference on Neural Information Processing Systems.Vancouver，Canada，2001:1327－1334.

［23］KANNAN R，VEMPALA S，VETTA A.On clusterings:good，bad，and spectral［J］.Journal of the ACM，2004，51(3):497－515.

［24］SONG Yangqiu，CHEN Wenyen，BAI Hongjie，et al.Parallel spectral clustering［C］//European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases.Antwerp，Belgium，2008:374－389.

［25］VERMA D，MEILA M.A comparison of spectral clustering algorithms，Technical Report UW－CSE－03－05－01［R］.Seattle，USA:Department of CSE，University of Washington，2003.

［26］LUXBURG U，BELKIN M，BOUSQUET O.Consistency of spectral clustering［J］.Annals of Statistics，2008，36(2):555－586.

［27］FILIPPONE M，CAMASTRA F，MASULLI F，et al.A survey of kernel and spectral methods for clustering［J］.Pattern Recognition，2008，41(1):176－190.

［28］蔡曉妍，戴冠中，楊黎斌.譜聚類算法綜述［J］.計算機科學，2008，35(7):14－17.

CAI Xiaoyan，DAI Guanzhong，YANG Libin.Survey on spectral clustering algorithms［J］.Computer Science，2008，35(7):14－17.

［29］DIESTEL R.Graph theory［M］.4th ed.Heidelberg，Germany:Springer－Verlag，2010.

［30］FIEDLER M.Algebraic connectivity of graphs［J］.Czechoslovak Mathematical Journal，1973，23(98):298－305.

［31］DONATH W E，HOFFMAN A J.Lower bounds for the partitioning of graphs［J］.IBM Journal of Research and Development，1973，17(5):420－425.

［32］BAMES E R.An algorithm for partitioning the nodes of a graph［J］.SIAM Journal on Algebraic and Discrete Methods，1982，17(5):541－550.

［33］DONATH W E.Logic partitioning［M］//PREAS B T，LORENZETTI M J.Physical Design Automation of VLSI Systems.［S.l.］:Benjamin/Cummings Pub Co，1988:65－86.

［34］BIGGS N L.Algebraic graph theory［M］.Cambridge，USA:Cambridge University Press，1974.

［35］BROUWER A E，HAEMERS W H.Spectra of graphs［EB/OL］. ［2010－10－05］.http://homepages.cwi.nl/～aeb/math/ipm.pdf.

［36］CHUNG F.Spectral graph theory［EB/OL］. ［2010－10－05］.http://www.ams.org/mathscinet－getitem?mr=1421568.

［37］MOHAR B.The Laplacian spectrum of graphs［M］//ALAVI Y，CHARTRAND G，OELLERMANN O R，et al.Graph Theory，Combinatorics，and Applications. ［S.l.］:Wiley，1991，2:871－898.

［38］MOHAR B.Some applications of Laplace eigenvalues of graphs［J］.Graph Symmetry:Algebraic Methods and Applications，1997，497(22):227－275.

［39］LUXBURG U.A tutorial on spectral clustering［J］.Statistics and Computing，2007，17(4):395－416.

［40］WEI Y C，CHENG C K.Toward efficient hierarchical designs by ratio cut partitioning［C］//IEEE International Conference on CAD.New York，USA，1989:298－301.

［41］BARNARD S，POTHEN A，SIMON H.A spectral algorithm for envelope reduction of sparse matrices［J］.Numerical Linear Algebra with Applications，1995，2(4):317－334.

［42］GUATTERY S，MILLER G L.On the quality of spectral separators［J］.SIAM Journal on Matrix Analysis and Applications，1998，19(3):701－719.

［43］WEISS Y.Segmentation using eigenvectors:a unifying view［C］//Proceedings of the Seventh IEEE International Conference on Computer Vision.Washington，DC，USA:IEEE Computer Society，1999:975－982.

［44］HIGHAM D，KIBBLE M.A unified view of spectral clustering［EB/OL］.［2010－10－05］.http://meyer.math.ncsu.edu/Meyer/Courses/Selee591RPresentation.pdf，2007.

［45］MEILA M，SHI J B.Learning segmentation by random walks［C］//LEEN T K，DIETTERICH T G，TRESP V.Advances in Neural Information Processing Systems.Cambridge，USA:MIT Press，2001:873－879.

［46］NEWMAN M E J.Finding community structure in networks using the eigenvectors of matrices［J］.Physical Review E，2006，74(3):036104.

［47］NEWMAN M E J.Modularity and community structure in networks［J］.Proceedings of the National Academy of Sciences of the United States，2006，103(23):8577－8582.

［48］NEWMAN M E J.Analysis of weighted networks［J］.Physical Review E，2004，70(5):056131.

［49］LEICHT E A，NEWMAN M E J.Community structure in directed networks［J］.Physical Review Letters，2008，100(11):118703.

［50］ZAHN C T.Graph－theoretic methods for detecting and describing gestalt clusters［J］.IEEE Transactions on Computers，1971，20(1):68－86.

［51］URQUHART R.Graph theoretical clustering based on limited neighborhood sets［J］.Pattern Recognition，1982，15(3):173－187.

［52］WAGNER D，WAGNER F.Between mincut and graph bisection［J］.Lecture Notes in Computer Science，1993，711:744－750.

［53］WU Z，LEAHY R.An optimal graph theoretic approach to data clustering:theory and its application to image segmentation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1993，15(11):1101－1113.

［54］CHAN P K，SCHLAG M D F，ZIEN J Y.Spectral k－way ratio－cut partitioning and clustering［J］.IEEE Transactions on Computer－Aided Design of Integrated Circuits and Systems，1994，13(9):1088－1096.

［55］WEI Y C，CHENG C K.A two－level two－way partitioning algorithm［C］//IEEE International Conference on CAD.Santa Clara，USA，1990:516－519.

［56］HAGEN L，ANDREW B K.New spectral methods for ratio cut partitioning and clustering［J］.IEEE Transactions on Computer－Aided Design of Intergrated Circuits and Systems，1992，11(9):1074－1085.

［57］YU S，SHI J B.Multiclass spectral clustering［C］//Proceedings of the Ninth IEEE International Conference on Computer Vision.Nice，France，2003，2:313－319.

［58］DING C，HE X，ZHA H，et al.A min－max cut algorithm for graph partitioning and data clustering［C］//Proceedings of the 2001 IEEE International Conference on Data Mining.Washington，DC，USA:IEEE Computer Society，2001:107－114.

［59］SARKAR S，SOUNDARARAJAN P.Supervised learning of large perceptual organization:graph spectral partitioning and learning automata［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22(5):504－525.

［60］ZHA Hongyuan，HE Xiaofeng，DING C H Q，et al.Spectral relaxation for k－means clustering［C］//DIETTERICH T G，BECKER S，GHAHRAMANI Z.Advances in Neural Information Processing Systems.Cambridge，USA:MIT Press，2002，14:1057－1064.

［61］WU Z，LEAHY R.Tissue classification in MR images using hierarchical segmentation［C］//1990 IEEE Nuclear Science Symposium Conference Record，Including Sessions on Nuclear Power Systems and Medical Imaging Conference.Piscataway，USA:IEEE Service Center，1990:1410－1414.

［62］FORD L R，FULKERSON D R.Flows in networks［M］.Princeton，USA:Princeton University Press，1962.

［63］DHILLON I S，KULIS Y B.A unified view of kernel kmeans，spectral clustering and graph partitioning，UTCS Technical Report#TR－04－25［R］.Austin，USA:Department of Computer Science，The University of Texas at Austin，2005.

［64］DHILLON I S，GUAN Y，KULIS B.Kernel k－means:spectral clustering and normalized cuts［C］//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York，USA:ACM Press，2004:551－556.

［65］JEBARA T，WANG J，CHANG S.Graph construction and b－matching for semi－supervised learning［C］//Proceedings of the 26th Annual International Conference on Machine Learning.New York，USA:ACM，2009:441－448.

［66］DAITCH S I，KELNER J A，SPIELMAN D A.Fitting a graph to vector data［C］//Proceedings of the 26th Annual International Conference on Machine Learning.New York，USA:ACM，2009:201－208.

［67］XUE F，KUMAR P R.The number of neighbors needed for connectivity of wireless networks［J］.Wireless Networks，2004，10(2):169－181.

［68］BALISTER P，BOLLOBAS B，SARKAR A，et al.Connectivity of random k－nearest－neighbour graphs［J］.Advances in Applied Probability，2005，37(1):1－24.

［69］BRITO M R，CHFIVEZ E L，QUIROZ A J，et al.Connectivity of the mutual k－nearest－neighbor graph in clustering and outlier detection［J］.Statistics ＆ Probability Letters，1997，35(1):33－42.

［70］POLITO M，PERONA P.Grouping and dimensionality reduction by locally linear embedding［C］//DIETTERICH T G，BECKER S，GHAHRAMANI Z.Advances in Neural Information Processing Systems.Cambridge，USA:MIT Press，2001:1255－1262.

［71］田錚，李小斌，句彥偉.譜聚類的擾動分析［J］.中國科學 E 輯:信息科學，2007，37(4):527－543.

TIAN Zheng，LI Xiaobin，JU Yanwei.Perturbation analysis of spectral clustering［J］.Science in China Series E:Technological Sciences，2007，37(4):527－543.

［72］HERNANDEZ V，ROMAN J，TOMAS A，et al.A survey of software for sparse eigenvalue problems［EB/OL］.［2010－10－05］.http://www.grycap.upv.es/slepc/documentation/reports/str6.pdf.

［73］FOWLKES C，BELONGIE S，CHUNG F，et al.Spectral grouping using the Nystrom method［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26(2):214－225.

［74］DHILLON I S，GUAN Y，KULIS B.Weighted graph cuts without eigenvectors:a multi－level approach［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29(11):1944－1957.

［75］YAN D H，HUANG L，JORDAN M I.Fast approximate spectral clustering［C］//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York，USA:ACM Press，2009:907－915.

［76］MASCHHOFF K J，SORENSEN D C.A portable implementation of ARPACK for distributed memory parallel architectures［EB/OL］. ［2010－10－05］.http://www.caam.rice.edu/_kristyn/parpack home.html.

［77］BACH F R，JORDAN M I.Learning spectral clustering，Technical Report No.UCB/CSD－03－1249［R］.Berkeley，USA:Computer Science Division，University of California，2003.

［78］王玲，薄列峰，焦李成.密度敏感的半監督譜聚類［J］.軟件學報，2007，18(10):2412－2422.

WANG Ling，BO Liefeng，JIAO Licheng.Density－sensitive semi－supervised spectral clustering［J］.Journal of Software，2007，18(10):2412－2422.

［79］KAMVAR S D，KLEIN D，MANNING C D.Spectral learning［C］//Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence.Acapulco，Mexico，2003:561－566.

［80］FISCHER I，POLAND I.New methods for spectral clustering，Technical Report No.IDSIA－12－04［R］.Manno，Switzerland:Dalle Molle Institute for Artificial Intelligence，2004.

［81］ROWEIS S，SAUL L.Nonlinear dimensionality reduction by locally linear embedding［J］.Science，2000，290(5550):2323－2326.

［82］CHENG B，YANG J，YAN S，et al.Learning with L1－graph for image analysis［J］.IEEE Transactions on Image Processing，2010，19(4):858－866.

李建元，男，1979年生，講師，博士研究生，CCF及ACM學生會員，主要研究方向為數據挖掘、機器學習、遙感與GIS等.

周腳根，男，1978年生，副研究員，博士，主要研究方向為空間數據挖掘和空間統計等.

關佶紅，女，1969年生，教授，博士生導師，博士，主要研究方向為分布計算、數據庫、數據挖掘、生物信息學等.

周水庚，男，1966年生，教授，博士生導師，博士，主要研究方向為網絡數據管理與搜索、海量數據挖掘與學習、生物信息學等.

A survey of clustering algorithms based on spectra of graphs

LI Jianyuan1，ZHOU Jiaogen2，GUAN Jihong1，ZHOU Shuigeng3

(1.Department of Computer Science＆ Technology，Tongji University，Shanghai 201804，China;2.Center of Information Technology in Agriculture，Shanghai Academy of Agricultural Sciences，Shanghai 201106，China;3.Shanghai Key Lab of Intelligent Information Processing，Fudan University，Shanghai 200433，China)

Over the past decade，a huge amount of research has covered the clustering algorithms that are based on the spectra of graphs.It is essential to analyze the relationships among those works so as to reveal the research tendencies.In this paper，the typical works on topics ranging from cost functions to spectral relaxation solutions were investigated and compared in an effort to clearly reveal the essence of these algorithms.Furthermore，the focus was concentrated on several crucial technical issues，including the construction of similarity graphs，the estimation of the clusters’number，the complexity and scalability，and semi－supervised spectral learning.Finally，some open issues were highlighted for future studies，e.g.，finding more theoretical interpretations of spectral clustering，constructing better similarity graphs，selecting features via learning，and the instantiations of concrete fields.

spectral clustering;graph－cut objectives;method of spectral relaxation;construction of similarity graphs;semi－supervised learning

TP301.6

A

1673－4785(2011)05－0405－10

10.3969/j.issn.1673－4785.2011.05.004

2010－10－12.

國家自然科學基金資助項目(60873040).

李建元.E－mail:lijy79@gmail.com.