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

邢潔清　符傳誼

摘要：譜聚類具有良好的理論基礎(chǔ)，被廣泛應(yīng)用于科學(xué)研究與工程應(yīng)用的各個(gè)領(lǐng)域，成為聚類分析領(lǐng)域重要的新興分支，受到越來(lái)越多的研究者的重視。然而，國(guó)內(nèi)相關(guān)文獻(xiàn)較少，該文從譜聚類算法的產(chǎn)生、研究進(jìn)展、基礎(chǔ)理論及代表算法等方面對(duì)譜聚類算法作簡(jiǎn)要綜述，有望使讀者對(duì)該領(lǐng)域形成初步認(rèn)識(shí)。

關(guān)鍵詞：譜聚類；聚類；圖劃分

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）19-0159-03

Spectral Clustering and its Research Progress

XING Jie-qing， FU Chuan-yi

（Department of Modern Education Technology， Qiongtai Normal College， Haikou 571100， China）

Abstract：Spectral clustering has good theoretic foundation， and has been applied in various science research and engineering fields. It becomes an important new popular tool for clustering analysis. With its development， spectral clustering attracts much more attention from researchers. However， there are few literatures on it. This paper gives a brief review about the creation， development， theoretic analysis and classical methods of spectral clustering.

Key words： spectral clustering； clustering； graph partition

聚類作為無(wú)監(jiān)督學(xué)習(xí)方法，廣泛地應(yīng)用于統(tǒng)計(jì)科學(xué)、計(jì)算機(jī)科學(xué)、生物學(xué)、社會(huì)學(xué)以及心理學(xué)等，成為應(yīng)用最多的數(shù)據(jù)分析技術(shù)之一。其中，基于譜圖劃分理論的聚類方法——譜聚類，是目前研究較多、有深厚理論基礎(chǔ)、應(yīng)用廣泛的聚類方法。與傳統(tǒng)的方法（如k-means，EM等）相比，它不對(duì)樣本空間的整體結(jié)構(gòu)做任何假設(shè)，能夠識(shí)別樣本點(diǎn)在空間上的非凸分布。因此，譜聚類方法適用于具有任何分布形狀的樣本空間，從而求解到全局最優(yōu)解。此外，譜聚類使得聚類算法的研究得到很大的拓展，適用于許多現(xiàn)實(shí)應(yīng)用問(wèn)題，已成功地應(yīng)用于文本分析、語(yǔ)音分析、圖像分割、機(jī)器視覺(jué)、商業(yè)分析、市場(chǎng)營(yíng)銷、計(jì)算生物學(xué)等等[1-3]。目前，譜聚類方法的應(yīng)用還擴(kuò)展到醫(yī)學(xué)診斷[6]、DNA和蛋白質(zhì)等生物信息挖掘[5]、文本主題分析[4]等領(lǐng)域。對(duì)譜聚類算法的研究具有科學(xué)意義和現(xiàn)實(shí)意義。同時(shí)，譜聚類算法在實(shí)現(xiàn)上僅涉及標(biāo)準(zhǔn)的線性代數(shù)方法，易于實(shí)現(xiàn)。

譜聚類算法是以圖論當(dāng)中的譜圖理論為基礎(chǔ)，重點(diǎn)在于設(shè)計(jì)合適的距離度量，計(jì)算待聚類的數(shù)據(jù)點(diǎn)之間的距離或相似性，構(gòu)造鄰接圖，最后將聚類任務(wù)轉(zhuǎn)化為鄰接有向圖的最優(yōu)劃分問(wèn)題。本文旨在從基礎(chǔ)理論、代表算法、比較分析等方面向讀者介紹這種新型的聚類算法。

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

譜聚類的誕生可以追溯到1973年，Donath和Hoffman 首次基于鄰接矩陣構(gòu)造了圖的劃分[7]。在同一年，F(xiàn)ieldler發(fā)現(xiàn)圖的二劃分與Laplacian圖的第二小特征向量有密切關(guān)系，并且建議使用該特征向量進(jìn)行圖的劃分[8]。從此以后，許多研究者加入到譜聚類方法的研究隊(duì)伍中，例如，Pothen， Simon， and Liou [9]、Bolla [10]、Hagen and Kahng [11]、Hendrickson and Leland [12]、Van Driessche and Roose[13]和Guattery and Miller[14]等。

譜聚類逐漸成為流行的聚類方法[1-6]。在算法擴(kuò)展和理論分析方面涌現(xiàn)了大量的研究成果。Dhillon等人將譜聚類應(yīng)用于聯(lián)合聚類問(wèn)題[14]，并分析了譜聚類與加權(quán)k-means的關(guān)系[19]。Bach等人利用譜聚類輔助學(xué)習(xí)相似性函數(shù)[9]。Kempe等人分析了再分布式環(huán)境下的譜聚類[21]。Perez等人提出了稀疏核譜聚類并應(yīng)用于大尺度數(shù)據(jù)集[17]。Jia等人將集成學(xué)習(xí)方法應(yīng)用于譜聚類[22]。Zhang等人設(shè)計(jì)了基于邊界的多路譜聚類方法[14]。最近，王春騰等分析了維數(shù)約簡(jiǎn)與譜聚類的關(guān)系，提出了基于維數(shù)約簡(jiǎn)的譜聚類方法：基于非負(fù)約束的譜聚類算法（NMFSC）[15]和基于獨(dú)立成分分析的譜聚類（ICASC）[16]。

特別地，聚類方法在圖像分割任務(wù)的應(yīng)用中，傳統(tǒng)的做法提取各像素點(diǎn)的特征向量，利用k-means等聚類方法對(duì)像素點(diǎn)進(jìn)行聚類。這類方法固有的缺陷是對(duì)樣本點(diǎn)的分布假設(shè)，例如k-means方法假定樣本點(diǎn)的分布服從高斯分布。然而，在現(xiàn)實(shí)應(yīng)用中該假設(shè)未必成立。譜聚類方法的優(yōu)勢(shì)在于不需要事先假定樣本服從某種特定的分布，計(jì)算像素點(diǎn)樣本之間的相似性，構(gòu)造相似性矩陣，通過(guò)對(duì)相似性矩陣的譜圖劃分達(dá)到劃分樣本空間的目的，從而避免了對(duì)樣本空間分布假設(shè)的依賴，使得譜聚類方法在理論上能夠適應(yīng)任意分布形狀的樣本空間。

2 理論基礎(chǔ)

2.1 相似圖

為說(shuō)明譜聚類的基本理論，本節(jié)首先引入有關(guān)的基本記號(hào)和相似圖概念。已知一個(gè)給定的數(shù)據(jù)集，根據(jù)已設(shè)計(jì)的距離公式可計(jì)算出樣本點(diǎn)兩兩之間相似度，構(gòu)造出相似性矩陣。以每個(gè)數(shù)據(jù)點(diǎn)為頂點(diǎn)，頂點(diǎn)與連通，給其連接邊賦予非負(fù)權(quán)值，即數(shù)據(jù)點(diǎn)與之間的相似性。此時(shí)，基于相似性矩陣構(gòu)造出無(wú)向圖，其中，是頂點(diǎn)集合，是邊集合。聚類的直接目標(biāo)是將相似的點(diǎn)盡量放在同一簇中，而不相似的點(diǎn)盡量歸入到不同簇中。至此，聚類問(wèn)題可以轉(zhuǎn)化為該無(wú)向圖上的劃分問(wèn)題，找到圖的某個(gè)分割，使得同一簇中點(diǎn)點(diǎn)間的邊權(quán)值之和最大，而不同簇之間的點(diǎn)點(diǎn)間邊權(quán)值之和最小。

無(wú)向圖稱為給定數(shù)據(jù)集的相似圖，其中，頂點(diǎn)集，邊集。在邊上賦予權(quán)值，構(gòu)成無(wú)向加權(quán)圖，頂點(diǎn)與之間賦予非負(fù)權(quán)值，則有加權(quán)鄰接矩陣，。特別地，當(dāng)，表示兩頂點(diǎn)間不連通。

2.2 譜圖劃分理論

譜聚類算法的思想來(lái)源于譜圖劃分理論[19]。無(wú)向加權(quán)圖構(gòu)造完成后，就可以尋找圖的最優(yōu)劃分，需要建立圖的最優(yōu)劃分準(zhǔn)則。圖論中常用的劃分準(zhǔn)則有M-cut， Mbmax-cut， N-cut， Average-cut，Ratio-cut等。限于篇幅，本文僅對(duì)常用的劃分準(zhǔn)則——規(guī)范割集準(zhǔn)則（Normalized-cut或N-cut）作簡(jiǎn)要介紹。

N-cut是由Shi和Malik提出的，其目標(biāo)函數(shù)的公式如下：

其中。以Ncut函數(shù)作為最小化目標(biāo)函數(shù)，稱為規(guī)范割集準(zhǔn)則。從該準(zhǔn)則的目標(biāo)函數(shù)可以看出，不僅可以度量同簇樣本間的相似性，還可以度量不同簇間樣本的相異性。Shi和Malik對(duì)上述目標(biāo)函數(shù)進(jìn)行了拓展，提出規(guī)范關(guān)聯(lián)目標(biāo)函數(shù)（Nassoc）：

其中，與分別是在子圖，內(nèi)各自所有頂點(diǎn)間連接權(quán)值的總和。該準(zhǔn)則衡量了同一簇內(nèi)的樣本間的緊湊程度。進(jìn)一步的推導(dǎo)，可以得出Ncut函數(shù)與Nassoc函數(shù)之間的線性關(guān)系：。所以，最小化Ncut函數(shù)與最大化Nassoc函數(shù)是等價(jià)的，兩個(gè)目標(biāo)函數(shù)可以任選其一。在實(shí)際應(yīng)用中，Ncut函數(shù)更常用。

3 譜聚類算法

選用不同的劃分準(zhǔn)則，可以構(gòu)造出不同的譜聚類算法，大致可以將譜聚類算法分為兩類：迭代譜聚類和多路譜聚類。

就迭代譜聚類而言，Peron與Freeman合作提出PF算法，其主要思想是構(gòu)造樣本集的相似圖，計(jì)算相似性矩陣的最大特征值及其對(duì)應(yīng)的特征向量，以特征向量中零元素對(duì)應(yīng)的數(shù)據(jù)點(diǎn)為中心生成一個(gè)簇類，其余點(diǎn)生成另外一個(gè)類，由此迭代，得到最終聚類結(jié)果[25]。其他具有代表性的迭代譜聚類算法有SM算法[1]、SLH算法[6]和KVV[26]算法等。

就多路譜聚類而言，Ng和Jordan等人提出NJW算法，其基本思想是計(jì)算相似性矩陣的拉普拉斯矩陣，尋找該矩陣的前k個(gè)最大特征值及其對(duì)應(yīng)的特征向量，將原數(shù)據(jù)點(diǎn)投影到k個(gè)特征向量構(gòu)造的新的特征空間中，最后在新的k維空間中實(shí)施k-means，得到最終聚類結(jié)果[2]。Meila對(duì)NJW算法進(jìn)行的拓展，將NJW中的k維特征空間再實(shí)施了一個(gè)線性旋轉(zhuǎn)，構(gòu)造出新的投影空間，然后在該空間中實(shí)施聚類[28]。

不管是上述哪一類方法，譜聚類算法的步驟大致可以歸納為如下三步：

Step1：構(gòu)造無(wú)向圖，其中，頂點(diǎn)集，邊集。根據(jù)樣本點(diǎn)與之間的相似性，賦予邊權(quán)值，得到加權(quán)鄰接矩陣，。此時(shí)，將聚類問(wèn)題轉(zhuǎn)化為圖的最優(yōu)劃分問(wèn)題。最優(yōu)劃分準(zhǔn)則的選取直接影響譜聚類算法的效果，也是譜聚類算法研究的集中關(guān)注點(diǎn)。譜聚類算法改進(jìn)大多集中在相似性度量函數(shù)和最優(yōu)劃分目標(biāo)函數(shù)的設(shè)計(jì)上。

Step2：計(jì)算相似性矩陣的前k個(gè)特征值及其對(duì)應(yīng)的特征向量，構(gòu)造新的k維特征空間，將原始樣本點(diǎn)投影到新的k維空間中。

Step3：在新的k維特征空間中實(shí)施傳統(tǒng)的聚類算法，例如k-means等。

4 結(jié)論

譜聚類在理論和應(yīng)用上都具有突出優(yōu)勢(shì)，近年來(lái)在學(xué)術(shù)界得到越來(lái)越多的重視，使聚類分析的研究得到延伸，適應(yīng)更多的現(xiàn)實(shí)應(yīng)用問(wèn)題，已成為聚類分析中一個(gè)重要的新興分支。本文從譜聚類的產(chǎn)生、發(fā)展、基本理論和代表算法等方面比較系統(tǒng)的總結(jié)了譜聚類算法及其研究進(jìn)展，可望使讀者對(duì)譜聚類形成基本的初步認(rèn)識(shí)，由此將該方法應(yīng)用到科學(xué)研究與工程應(yīng)用的各種實(shí)際問(wèn)題中。

參考文獻(xiàn)：

[1] Ahn I， Kim C. Face and Hair Region Labeling Using Semi-Supervised Spectral Clustering Based Multiple Segmentations[J]. IEEE Transactions on Multimedia， 2016：1-1.

[2] Petkos G， Schinas M， Papadopoulos S， et al. Graph-based multimodal clustering for social multimedia[J]. Multimedia Tools & Applications， 2016：1-23.

[3] 崔麗，陳睿，李華. 拓?fù)鋱D格獨(dú)立分量分析和譜聚類支持的紋理探測(cè)[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005，17（5）：，935-940.

[4] Hou H X， Yuan M M， Liu C X. Indirect spectral clustering towards large text datasets[J]. Journal of Computer Applications， 2013， 32（12）：3274-3277.

[5] Huang L， Liao L， Wu C H. Inference of protein-protein interaction networks from multiple heterogeneous data[J]. Eurasip Journal on Bioinformatics & Systems Biology， 2016， 2016（1）：1-9.

[6] Wang D， Gu J. Integrative clustering methods of multi-omics data for molecule-based cancer classifications[J]. Quantitative Biology， 2016：1-10.

[7] Donath W E， Hoffman A J. Lower bounds for the partitioning of graphs. IBM J. Res. Develop. 1973（17）：420-425.

[8] Fiedler M. Algebraic connectivity of graphs. Czech， Math. J.， 1973（23）：298-305.

[9] Pothen A， Simon H D， Liou K P. Partitioning sparse matrices with eigenvectors of graphs. SIAM Journal of Matrix Anal. Appl.， 1990（11）：430-452.

[10] Simon， H. Partitioning of unstructured problems for parallel processing. Computing Systems Engineering， 1991（2）：135-148.

[11] Hagen L， Kahng A B. New spectral methods for ratio cut partitioning and clustering. IEEE Transactions on Computer-aided Design， 1992（9）：1074-1085.

[12] Hendrickson， B. and Leland， R. An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM J. on Scientic Computing， 1995（16）：452-469.

[13] Van Driessche， R. and Roose， D. An improved spectral bisection algorithm and its application to dynamic load balancing. Parallel Comput.， 1995，21（1）：29-48.

[14] Dhillon， I. Co-clustering documents and words using bipartite spectral graph partitioning. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining， New York： ACM Press， 2001， pp.269–274.

[15] 王春騰，符傳誼.基于非負(fù)約束的譜聚類算法[J].電腦知識(shí)與技術(shù)，2011，17（41）：65.

[16] 王春騰，符傳誼.基于獨(dú)立成分分析的譜聚類方法[J].安徽電子職業(yè)技術(shù)學(xué)院學(xué)報(bào)2011，6（42）：51.

[17] Perez A， Andres C， and Johan S. Sparse Kernel spectral clustering models for large-scale data analysis， Neurocomputing， 2011， v74（9）， p1382-1390

[18] Zhang Z and Jordan M. I.， Multiway Spectral Clustering： A Margin-Based Perspective， V23（3）， 2008， p383-403

[19] Dhillon， I.， Guan， Y.， and Kulis， B. A unied view of kernel k-means， spectral clustering， and graph partitioning. University of Texas at Austin， 2005

[20] Bach， F. and Jordan， M. Learning spectral clustering. In S. Thrun， L. Saul， and B. Sch?lkopf （Eds.）， Advances in Neural Information Processing Systems. Cambridge， MA： MIT Press， 2004.

[21] Kempe， D. and McSherry， F. A decentralized algorithm for spectral analysis. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing . New York， NY， USA： ACM Press， 2004， pp. 561–568.

[22] Jia J， Xiao X， Liu B and Jiao L， Bagging-based spectral clustering ensemble selection， Pattern Recognition Letter， v32（10）， 2011.

[23] Ding C， He X， Zha H， et al. A min-max cut algorithm for graph partitioning and data clustering. In Proceedings of therst IEEE International Conference on Data Mining， Washington， DC， USA： IEEE Computer Society， 2001：107-114

[24] Guattery S， Miller G L. On the quality of spectral separators. SIAM Journal of Matrix Anal. Appl.， 1998，19（3）：701-719.

[25] Perona P，F(xiàn)reeman W T.A factorization approach to grouping， Proc. ECCV，1998：655-670.

[26] Kannan R， Vempala S， Vetta A. On clusterings good， bad and spectral. In FOCS， 2000：367-377.

[27] Meila M， Shi J. Learning segmentation by random walks. In NIPS， 2000：873-879.