譜圖聚類算法研究進(jìn)展

李建元，周腳根，關(guān)佶紅，周水庚

(1.同濟(jì)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系，上海 201804;2.上海市農(nóng)業(yè)科學(xué)院 數(shù)字農(nóng)業(yè)與工程技術(shù)研究中心，上海 201106;3.復(fù)旦大學(xué)上海市智能信息處理重點(diǎn)實(shí)驗(yàn)室，上海 200433)

譜圖聚類算法研究進(jìn)展

李建元1，周腳根2，關(guān)佶紅1，周水庚3

(1.同濟(jì)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系，上海 201804;2.上海市農(nóng)業(yè)科學(xué)院 數(shù)字農(nóng)業(yè)與工程技術(shù)研究中心，上海 201106;3.復(fù)旦大學(xué)上海市智能信息處理重點(diǎn)實(shí)驗(yàn)室，上海 200433)

近10多年來(lái)，關(guān)于譜圖聚類的研究成果非常豐富，為了總結(jié)和理清這些工作之間的脈絡(luò)關(guān)系，揭示最新的研究趨勢(shì)，回顧和比較了典型的圖割目標(biāo)函數(shù)，以及這些目標(biāo)函數(shù)的譜寬松解決方法，總結(jié)了譜聚類算法的本質(zhì).另外，討論了譜圖聚類的幾個(gè)關(guān)鍵問(wèn)題:相似圖的構(gòu)建方法、復(fù)雜性與擴(kuò)充性、簇?cái)?shù)估計(jì)、半監(jiān)督譜學(xué)習(xí)等.最后，展望了譜圖聚類算法的主要研究趨勢(shì)，如探尋其理論解釋，構(gòu)建更貼切的相似圖，通過(guò)學(xué)習(xí)篩選特征，應(yīng)用實(shí)例化等.

譜圖聚類;圖割目標(biāo)函數(shù);譜寬松方法;相似圖構(gòu)建;半監(jiān)督學(xué)習(xí)

聚類技術(shù)是探測(cè)數(shù)據(jù)分析的關(guān)鍵步驟，具有非常重要的科學(xué)地位和應(yīng)用價(jià)值.傳統(tǒng)的聚類算法如K－means［1］和 EM［2］等，它們雖然簡(jiǎn)單，但缺乏處理復(fù)雜簇結(jié)構(gòu)的能力，并可能陷入局部解.近10余年來(lái)，譜聚類算法作為一種有競(jìng)爭(zhēng)力的技術(shù)，成為一個(gè)新的研究熱點(diǎn)，與之相關(guān)的研究成果也頗為豐富.

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

譜聚類技術(shù)可以從以下幾個(gè)角度進(jìn)行分類:1)從是否考慮樣本外擴(kuò)展的角度，可以將其分為離線譜聚類(如文獻(xiàn)［3，5，18－19］等)和增量譜聚類(如文獻(xiàn)［20－21］等);2)從是否具有約束條件或者先驗(yàn)知識(shí)的角度，可以將其分為無(wú)監(jiān)督譜聚類和約束譜聚類(如文獻(xiàn)［22］等);3)按優(yōu)化目標(biāo)的個(gè)數(shù)可以將其分為單目標(biāo)優(yōu)化(絕大多數(shù))和雙目標(biāo)優(yōu)化(如文獻(xiàn)［23］等);4)從運(yùn)行環(huán)境上，可將其分為串行譜聚類和并行譜聚類(如文獻(xiàn)［24］等).

迄今為止，譜聚類技術(shù)已經(jīng)得到長(zhǎng)足的發(fā)展，總結(jié)和理清已有研究之間的關(guān)系，揭示未來(lái)的研究方向是十分有必要的.已出現(xiàn)的綜述文章各有側(cè)重.Verma等人［25］主要從實(shí)驗(yàn)的角度比較了幾種典型的譜聚類算法的性能，并提出若干改進(jìn)算法.Luxburg等人［26］從統(tǒng)計(jì)學(xué)習(xí)的理論高度比較了典型的歸一化和非歸一化譜聚類算法，并總結(jié)了相似圖構(gòu)建方法和簇?cái)?shù)估計(jì)等問(wèn)題.Maurizio等人［27］調(diào)查了基于核的聚類方法和譜方法，并得出這2種方法的共同本質(zhì)是跡最優(yōu)化問(wèn)題.國(guó)內(nèi)方面，關(guān)于該領(lǐng)域較好的綜述如文獻(xiàn)［28］，其從算法層面上較為全面地進(jìn)行了比較.

本文盡管與上述綜述文獻(xiàn)在內(nèi)容上有一些重疊之處，但卻包含了一些新的內(nèi)容.一方面，涉及的內(nèi)容更全面、脈絡(luò)關(guān)系更清楚，如從圖論到代數(shù)分割特性的發(fā)展、從圖割目標(biāo)函數(shù)到譜圖聚類算法的演變、譜圖聚類算法的本質(zhì)等.另一方面，討論的問(wèn)題更深入，如圖的構(gòu)建、邊權(quán)的度量、簇?cái)?shù)的估計(jì)、復(fù)雜性與擴(kuò)充性、半監(jiān)督譜學(xué)習(xí).最后，總結(jié)了有待澄清的一些的理論和實(shí)際問(wèn)題，指出了譜圖聚類算法的研究趨勢(shì).

1 基本理論

1.1 圖論與代數(shù)圖論

圖論是數(shù)學(xué)的一個(gè)重要分支，是以1736年大數(shù)學(xué)家歐拉關(guān)于Konigsberg七橋問(wèn)題的論文為里程碑開(kāi)始發(fā)展的.它研究的是關(guān)于圖(graph)的理論和方法.簡(jiǎn)單來(lái)說(shuō)，圖是點(diǎn)集和邊集或弧集構(gòu)成的圖形，其中邊或弧用來(lái)表示一對(duì)節(jié)點(diǎn)間存在某種關(guān)系，邊或弧可以賦予權(quán)值，權(quán)值用來(lái)量化節(jié)點(diǎn)之間的關(guān)系.根據(jù)是否加權(quán)，圖可分為無(wú)權(quán)圖和加權(quán)圖;根據(jù)邊是否具有方向，可將圖分為有向圖和無(wú)向圖.

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

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

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

1.2 矩陣與譜

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

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

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

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

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

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

2 主要的圖割目標(biāo)函數(shù)

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

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

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

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

近10年來(lái)復(fù)雜網(wǎng)絡(luò)的研究快速崛起，Newman系統(tǒng)地研究了無(wú)權(quán)網(wǎng)絡(luò)、加權(quán)網(wǎng)絡(luò)乃至有向網(wǎng)絡(luò)中的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)譜算法，運(yùn)用了模塊度(modularity)函數(shù)進(jìn)行社團(tuán)發(fā)現(xiàn)［46－49］.模塊度準(zhǔn)則的思想較為新穎:以無(wú)權(quán)圖為例，當(dāng)各社團(tuán)中的邊的比例盡可能地超出“期望”的邊的比例時(shí)，才認(rèn)為是合理的分割.其中“期望”的邊數(shù)指的是根據(jù)配置模型得到的一種隨機(jī)圖模型.這顯然與傳統(tǒng)的圖割聚類方法的出發(fā)點(diǎn)不同，其目標(biāo)函數(shù)為

式中:Q表示模塊度;m表示圖中包含的邊數(shù);ki表示編號(hào)為i的節(jié)點(diǎn)的度(kj類似);vi和vj只可?。?或1，當(dāng)vi≠vj是表示將節(jié)點(diǎn)i和j劃分到不同社區(qū)，反之則屬于同一社區(qū).

3 譜寬松方法解決圖割問(wèn)題

最小化比率割、規(guī)范割、平均割以及最大化模塊度等，均為NP離散最優(yōu)化問(wèn)題.幸運(yùn)的是，譜方法可以為該最優(yōu)化問(wèn)題提供一種多項(xiàng)式時(shí)間內(nèi)的寬松解.這里的“寬松”指的是將離散最優(yōu)化問(wèn)題寬松到實(shí)數(shù)域，然后利用某種啟發(fā)式方法將其重新轉(zhuǎn)換為離散解.下面簡(jiǎn)要介紹從目標(biāo)函數(shù)到譜方法的演變［39，46，56］.

3.1 圖的二分割問(wèn)題

3.1.1 比率割

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

令E表示一個(gè)包含n個(gè)元素的常向量，其每個(gè)元素均設(shè)為1.因?yàn)槔暇仃嘗的各特征向量正交，而E又是L的一個(gè)特征向量，故可得x·E=0.若eij是連接N和M2個(gè)點(diǎn)集的邊，則有xi－xj=q－(－p)=1;相反，若eij不是連接N和M2個(gè)點(diǎn)集的邊，則有xi－xj=0.從而可得

又因?yàn)?/p>

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

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

3.1.2 平均割

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

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

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

3.1.3 規(guī)范割

令指示向量x滿足:

則有

又因?yàn)閤TDx=vol(V)，故可得

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

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

3.1.4 模塊度

對(duì)于任意無(wú)向加權(quán)圖，令w表示整個(gè)圖的總權(quán)值，di代表節(jié)點(diǎn)i與其他節(jié)點(diǎn)之間的總權(quán)值.令Bij=Aij－didj/2w，v為指示向量且僅可取1或－1，當(dāng)vi=vj時(shí)表示節(jié)點(diǎn)i與j屬于同一個(gè)簇，反之屬于不同的簇.用于聚類的模塊度函數(shù)可表達(dá)為

式中:w可寫(xiě)作w=vol(V)/2=∑ijAij，i＞j;di可寫(xiě)作di=vol(Vi)/=∑jAij.因?yàn)椤苅di=2w=∑jdj，故存在

于是可得

即矩陣的所有項(xiàng)之和等于0.進(jìn)一步有

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

另存在關(guān)系Bv=λv，故可得

若將v的取值寬松到實(shí)數(shù)域，則可得當(dāng)λi取最大特征值且v平行于其對(duì)應(yīng)的特征向量時(shí)，Q取最大值.但是網(wǎng)絡(luò)社區(qū)分割問(wèn)題仍為離散最優(yōu)化問(wèn)題，故依然需要離散化步驟.Newman的方法是使得v的各分量與ui的各分量符號(hào)一致，也就是使二者盡量平行.

3.2 圖的k分割

以平均割目標(biāo)函數(shù)為例，來(lái)說(shuō)明圖的k分割問(wèn)題的譜寬松解決方法［39］.

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

然后，令H是一個(gè)n行k列的矩陣，其列即為不同的指示向量.因?yàn)榫仃嘓的各列向量是相互正交的，即滿足HTH=I.于是有

并存在

綜上可得

即跡最小化問(wèn)題.取拉氏矩陣的前k個(gè)特征向量作為列便可得到矩陣H.然而此處H中的項(xiàng)在實(shí)數(shù)域中，需要離散化才能達(dá)到分類的目的.最簡(jiǎn)單的離散化方法是在實(shí)數(shù)域解H上采用K－means算法或者其他基準(zhǔn)算法進(jìn)行子空間上的聚類.

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

可見(jiàn)，這些最優(yōu)化問(wèn)題，均可運(yùn)用譜方法來(lái)解決.不同的是，比率割、最小最大割、平均割派生出非歸一化的譜聚類算法，而規(guī)范割派生出歸一化的譜聚類算法，模塊度派生出一種新的譜分割算法.然而，它們共同的本質(zhì)是約束條件下的跡最優(yōu)化問(wèn)題［63－64］，只不過(guò)針對(duì)的矩陣不同.

4 譜圖聚類中的幾個(gè)關(guān)鍵問(wèn)題

4.1 構(gòu)圖與加權(quán)

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

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

2)k近鄰圖:當(dāng)點(diǎn)i(或點(diǎn)j)是點(diǎn)j(或點(diǎn)i)的k個(gè)鄰近點(diǎn)之一時(shí)，相似度取wij，否則取0.

3)互為k近鄰圖:當(dāng)i點(diǎn)和j點(diǎn)互相落在對(duì)方的k鄰域時(shí)，相似度取wij，否則設(shè)為0.

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

5)擬合圖［66］:以重構(gòu)誤差為優(yōu)化目標(biāo)，節(jié)點(diǎn)加權(quán)度不小于1為約束條件，利用二次規(guī)劃求得的矩陣和圖.

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

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

σ是高斯核參數(shù)，許多研究者都將其設(shè)為一個(gè)全局值［3，5］，其取值范圍一般滿足‖xi－xj‖ ＞ σ ＞0，通過(guò)加入?yún)?shù)σ，將原始的相似關(guān)系映射到其他空間.考慮到機(jī)器的計(jì)算精度，過(guò)小的σ會(huì)導(dǎo)致相似圖不連通.然而，全局設(shè)定σ的值實(shí)際上在一些情況下并不是理想的方法.文獻(xiàn)［19］探討了自適應(yīng)設(shè)定局部參數(shù)的方式，能夠更加恰當(dāng)?shù)孛枋龉?jié)點(diǎn)間的鄰域關(guān)系.其表達(dá)式如下:

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

4.2 簇?cái)?shù)估計(jì)問(wèn)題

自動(dòng)估計(jì)簇?cái)?shù)的研究大體上可以分為2類.一種方法是通過(guò)分析特征值.文獻(xiàn)［3］分析了在理想狀況下(簇與簇之間的距離為無(wú)窮遠(yuǎn))的簇?cái)?shù)估計(jì)方法:對(duì)于歸一化相似矩陣，特征值為1的個(gè)數(shù)嚴(yán)格地對(duì)應(yīng)著簇?cái)?shù).然而實(shí)際的情況沒(méi)有這么簡(jiǎn)單，一種可選的方法是分析特征值缺口(eigen－gap)［70］，在部分應(yīng)用中，此方法是有效的，但是其缺乏理論根據(jù)，而且缺口往往可大可小，難以取舍.文獻(xiàn)［71］提出將相似矩陣的特征值大于1的個(gè)數(shù)作為簇?cái)?shù)的方法，實(shí)質(zhì)上就是一種特征值缺口法.另一種更好的方法是分析特征向量，如文獻(xiàn)［19］通過(guò)引入旋轉(zhuǎn)矩陣和一個(gè)優(yōu)化目標(biāo)來(lái)發(fā)現(xiàn)最佳簇?cái)?shù).實(shí)驗(yàn)表明，該方法在一些復(fù)雜的合成數(shù)據(jù)集和圖像分割應(yīng)用上是有效的.

值得注意的是，以上這些方法要么是基于譜來(lái)估計(jì)簇?cái)?shù)，要么是基于新的優(yōu)化目標(biāo)來(lái)估計(jì)簇?cái)?shù).而直接基于圖割優(yōu)化目標(biāo)來(lái)確定簇?cái)?shù)的研究尚少.雖然Newman［47］提出的重復(fù)二分譜算法具有這種能力，但其算法是應(yīng)用在網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問(wèn)題中的，在點(diǎn)集聚類問(wèn)題上，尚需推廣和驗(yàn)證.

4.3 復(fù)雜性與擴(kuò)充性問(wèn)題

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

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

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

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

4.4 半監(jiān)督譜學(xué)習(xí)

通常，與分類問(wèn)題本身無(wú)關(guān)的特征會(huì)使得大多數(shù)的譜聚類算法的性能大打折扣.幾乎所有譜聚類的應(yīng)用都是在某種相似性度量假設(shè)基礎(chǔ)之上進(jìn)行的，這些算法的成功依賴于度量方式的選擇.而已有的大多數(shù)譜聚類算法對(duì)于不相關(guān)的特征具有較差的魯棒性［77］.這種情況需要結(jié)合先驗(yàn)知識(shí)來(lái)解決，在許多情況下，某些先驗(yàn)知識(shí)是可以獲得的，如文獻(xiàn)［78］提及的空間一致性先驗(yàn)信息，文獻(xiàn)［79］在相似性度量時(shí)依靠結(jié)合知識(shí)來(lái)減輕不相關(guān)特征造成的影響，文獻(xiàn)［77，80］提出了從數(shù)據(jù)中自動(dòng)學(xué)習(xí)的方式來(lái)確定恰當(dāng)?shù)暮嘶蛘呦嗨菩远攘糠椒?，文獻(xiàn)［77］提供了一個(gè)基于實(shí)例的相似矩陣學(xué)習(xí)的總體框架，文獻(xiàn)［78］提出了一種從數(shù)據(jù)中學(xué)習(xí)先驗(yàn)知識(shí)的密度敏感的半監(jiān)督聚類算法等，均取得了較好的效果.

5 結(jié)論與展望

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

以下提出今后依然需要探討的幾點(diǎn)問(wèn)題.

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

2)如何更恰當(dāng)?shù)貥?gòu)建相似圖，相似圖構(gòu)建的好壞決定著譜聚類性能.近來(lái)提出的b－匹配圖和擬合圖就是非常有趣和有用的方法，盡管已有的構(gòu)建方法已經(jīng)不少，但關(guān)于該問(wèn)題依然需要推陳出新，最核心的一點(diǎn)是如何本質(zhì)地描述數(shù)據(jù)之間的關(guān)系.

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

4)如何將優(yōu)化目標(biāo)與簇?cái)?shù)估計(jì)相結(jié)合，已有的絕大多數(shù)譜算法并不能根據(jù)其圖割優(yōu)化目標(biāo)來(lái)決定簇?cái)?shù)，也就是說(shuō)在算法運(yùn)行之前簇?cái)?shù)是給定的.然而，在許多應(yīng)用場(chǎng)合中，事先知道簇?cái)?shù)是不現(xiàn)實(shí)的，如何在圖割優(yōu)化目標(biāo)的指導(dǎo)下發(fā)現(xiàn)簇?cái)?shù)是值得思考的.

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

6)如何在構(gòu)建相似圖的過(guò)程中進(jìn)行自動(dòng)特征篩選.例如:針對(duì)高維數(shù)據(jù)，L1圖的構(gòu)建可以有效地捕捉最稀疏的特征，從而得到非常高的聚類和分類準(zhǔn)確性［82］.

7)如何快速解決大規(guī)?；虺笠?guī)模的譜聚類問(wèn)題.隨著經(jīng)濟(jì)和社會(huì)的發(fā)展，在許多行業(yè)中，需要處理的數(shù)據(jù)規(guī)模與日俱增，雖然現(xiàn)有的研究已經(jīng)能夠解決10萬(wàn)數(shù)量級(jí)的問(wèn)題，但是解決更大規(guī)模的問(wèn)題仍然具有挑戰(zhàn)性.

8)應(yīng)用實(shí)例化.與各學(xué)科或應(yīng)用領(lǐng)域相結(jié)合，通過(guò)改進(jìn)典型的譜聚類算法切實(shí)解決實(shí)際問(wèn)題.例如，在網(wǎng)絡(luò)文檔分類中，如何恰當(dāng)?shù)乩萌忠恢滦孕畔?，如何增量地聚類?dòng)態(tài)更新的博客社區(qū)等.

［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］.計(jì)算機(jī)學(xué)報(bào)，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］.中文信息學(xué)報(bào)，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］.計(jì)算機(jī)科學(xué)，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，F(xiàn)rance，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，F(xiàn)ULKERSON 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］田錚，李小斌，句彥偉.譜聚類的擾動(dòng)分析［J］.中國(guó)科學(xué) E 輯:信息科學(xué)，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］王玲，薄列峰，焦李成.密度敏感的半監(jiān)督譜聚類［J］.軟件學(xué)報(bào)，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學(xué)生會(huì)員，主要研究方向?yàn)閿?shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、遙感與GIS等.

周腳根，男，1978年生，副研究員，博士，主要研究方向?yàn)榭臻g數(shù)據(jù)挖掘和空間統(tǒng)計(jì)等.

關(guān)佶紅，女，1969年生，教授，博士生導(dǎo)師，博士，主要研究方向?yàn)榉植加?jì)算、數(shù)據(jù)庫(kù)、數(shù)據(jù)挖掘、生物信息學(xué)等.

周水庚，男，1966年生，教授，博士生導(dǎo)師，博士，主要研究方向?yàn)榫W(wǎng)絡(luò)數(shù)據(jù)管理與搜索、海量數(shù)據(jù)挖掘與學(xué)習(xí)、生物信息學(xué)等.

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，F(xiàn)udan 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.

國(guó)家自然科學(xué)基金資助項(xiàng)目(60873040).

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