邢潔清 符傳誼
摘要:譜聚類(lèi)具有良好的理論基礎(chǔ),被廣泛應(yīng)用于科學(xué)研究與工程應(yīng)用的各個(gè)領(lǐng)域,成為聚類(lèi)分析領(lǐng)域重要的新興分支,受到越來(lái)越多的研究者的重視。然而,國(guó)內(nèi)相關(guān)文獻(xiàn)較少,該文從譜聚類(lèi)算法的產(chǎn)生、研究進(jìn)展、基礎(chǔ)理論及代表算法等方面對(duì)譜聚類(lèi)算法作簡(jiǎn)要綜述,有望使讀者對(duì)該領(lǐng)域形成初步認(rèn)識(shí)。
關(guān)鍵詞:譜聚類(lèi);聚類(lèi);圖劃分
中圖分類(lèi)號(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
聚類(lèi)作為無(wú)監(jiān)督學(xué)習(xí)方法,廣泛地應(yīng)用于統(tǒng)計(jì)科學(xué)、計(jì)算機(jī)科學(xué)、生物學(xué)、社會(huì)學(xué)以及心理學(xué)等,成為應(yīng)用最多的數(shù)據(jù)分析技術(shù)之一。其中,基于譜圖劃分理論的聚類(lèi)方法——譜聚類(lèi),是目前研究較多、有深厚理論基礎(chǔ)、應(yīng)用廣泛的聚類(lèi)方法。與傳統(tǒng)的方法(如k-means,EM等)相比,它不對(duì)樣本空間的整體結(jié)構(gòu)做任何假設(shè),能夠識(shí)別樣本點(diǎn)在空間上的非凸分布。因此,譜聚類(lèi)方法適用于具有任何分布形狀的樣本空間,從而求解到全局最優(yōu)解。此外,譜聚類(lèi)使得聚類(lèi)算法的研究得到很大的拓展,適用于許多現(xiàn)實(shí)應(yīng)用問(wèn)題,已成功地應(yīng)用于文本分析、語(yǔ)音分析、圖像分割、機(jī)器視覺(jué)、商業(yè)分析、市場(chǎng)營(yíng)銷(xiāo)、計(jì)算生物學(xué)等等[1-3]。目前,譜聚類(lèi)方法的應(yīng)用還擴(kuò)展到醫(yī)學(xué)診斷[6]、DNA和蛋白質(zhì)等生物信息挖掘[5]、文本主題分析[4]等領(lǐng)域。對(duì)譜聚類(lèi)算法的研究具有科學(xué)意義和現(xiàn)實(shí)意義。同時(shí),譜聚類(lèi)算法在實(shí)現(xiàn)上僅涉及標(biāo)準(zhǔn)的線性代數(shù)方法,易于實(shí)現(xiàn)。
譜聚類(lèi)算法是以圖論當(dāng)中的譜圖理論為基礎(chǔ),重點(diǎn)在于設(shè)計(jì)合適的距離度量,計(jì)算待聚類(lèi)的數(shù)據(jù)點(diǎn)之間的距離或相似性,構(gòu)造鄰接圖,最后將聚類(lèi)任務(wù)轉(zhuǎn)化為鄰接有向圖的最優(yōu)劃分問(wèn)題。本文旨在從基礎(chǔ)理論、代表算法、比較分析等方面向讀者介紹這種新型的聚類(lèi)算法。
1 譜聚類(lèi)算法研究進(jìn)展
譜聚類(lèi)的誕生可以追溯到1973年,Donath和Hoffman 首次基于鄰接矩陣構(gòu)造了圖的劃分[7]。在同一年,F(xiàn)ieldler發(fā)現(xiàn)圖的二劃分與Laplacian圖的第二小特征向量有密切關(guān)系,并且建議使用該特征向量進(jìn)行圖的劃分[8]。從此以后,許多研究者加入到譜聚類(lèi)方法的研究隊(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]等。
譜聚類(lèi)逐漸成為流行的聚類(lèi)方法[1-6]。在算法擴(kuò)展和理論分析方面涌現(xiàn)了大量的研究成果。Dhillon等人將譜聚類(lèi)應(yīng)用于聯(lián)合聚類(lèi)問(wèn)題[14],并分析了譜聚類(lèi)與加權(quán)k-means的關(guān)系[19]。Bach等人利用譜聚類(lèi)輔助學(xué)習(xí)相似性函數(shù)[9]。Kempe等人分析了再分布式環(huán)境下的譜聚類(lèi)[21]。Perez等人提出了稀疏核譜聚類(lèi)并應(yīng)用于大尺度數(shù)據(jù)集[17]。Jia等人將集成學(xué)習(xí)方法應(yīng)用于譜聚類(lèi)[22]。Zhang等人設(shè)計(jì)了基于邊界的多路譜聚類(lèi)方法[14]。最近,王春騰等分析了維數(shù)約簡(jiǎn)與譜聚類(lèi)的關(guān)系,提出了基于維數(shù)約簡(jiǎn)的譜聚類(lèi)方法:基于非負(fù)約束的譜聚類(lèi)算法(NMFSC)[15]和基于獨(dú)立成分分析的譜聚類(lèi)(ICASC)[16]。
特別地,聚類(lèi)方法在圖像分割任務(wù)的應(yīng)用中,傳統(tǒng)的做法提取各像素點(diǎn)的特征向量,利用k-means等聚類(lèi)方法對(duì)像素點(diǎn)進(jìn)行聚類(lèi)。這類(lèi)方法固有的缺陷是對(duì)樣本點(diǎn)的分布假設(shè),例如k-means方法假定樣本點(diǎn)的分布服從高斯分布。然而,在現(xiàn)實(shí)應(yīng)用中該假設(shè)未必成立。譜聚類(lèi)方法的優(yōu)勢(shì)在于不需要事先假定樣本服從某種特定的分布,計(jì)算像素點(diǎn)樣本之間的相似性,構(gòu)造相似性矩陣,通過(guò)對(duì)相似性矩陣的譜圖劃分達(dá)到劃分樣本空間的目的,從而避免了對(duì)樣本空間分布假設(shè)的依賴,使得譜聚類(lèi)方法在理論上能夠適應(yīng)任意分布形狀的樣本空間。
2 理論基礎(chǔ)
2.1 相似圖
為說(shuō)明譜聚類(lèi)的基本理論,本節(jié)首先引入有關(guān)的基本記號(hào)和相似圖概念。已知一個(gè)給定的數(shù)據(jù)集
無(wú)向圖
2.2 譜圖劃分理論
譜聚類(lèi)算法的思想來(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ù)的公式如下:
其中
其中,
3 譜聚類(lèi)算法
選用不同的劃分準(zhǔn)則,可以構(gòu)造出不同的譜聚類(lèi)算法,大致可以將譜聚類(lèi)算法分為兩類(lèi):迭代譜聚類(lèi)和多路譜聚類(lèi)。
就迭代譜聚類(lèi)而言,Peron與Freeman合作提出PF算法,其主要思想是構(gòu)造樣本集的相似圖,計(jì)算相似性矩陣的最大特征值及其對(duì)應(yīng)的特征向量,以特征向量中零元素對(duì)應(yīng)的數(shù)據(jù)點(diǎn)為中心生成一個(gè)簇類(lèi),其余點(diǎn)生成另外一個(gè)類(lèi),由此迭代,得到最終聚類(lèi)結(jié)果[25]。其他具有代表性的迭代譜聚類(lèi)算法有SM算法[1]、SLH算法[6]和KVV[26]算法等。
就多路譜聚類(lèi)而言,Ng和Jordan等人提出NJW算法,其基本思想是計(jì)算相似性矩陣的拉普拉斯矩陣,尋找該矩陣的前k個(gè)最大特征值及其對(duì)應(yīng)的特征向量,將原數(shù)據(jù)點(diǎn)投影到k個(gè)特征向量構(gòu)造的新的特征空間中,最后在新的k維空間中實(shí)施k-means,得到最終聚類(lèi)結(jié)果[2]。Meila對(duì)NJW算法進(jìn)行的拓展,將NJW中的k維特征空間再實(shí)施了一個(gè)線性旋轉(zhuǎn),構(gòu)造出新的投影空間,然后在該空間中實(shí)施聚類(lèi)[28]。
不管是上述哪一類(lèi)方法,譜聚類(lèi)算法的步驟大致可以歸納為如下三步:
Step1:構(gòu)造無(wú)向圖
Step2:計(jì)算相似性矩陣
Step3:在新的k維特征空間中實(shí)施傳統(tǒng)的聚類(lèi)算法,例如k-means等。
4 結(jié)論
譜聚類(lèi)在理論和應(yīng)用上都具有突出優(yōu)勢(shì),近年來(lái)在學(xué)術(shù)界得到越來(lái)越多的重視,使聚類(lèi)分析的研究得到延伸,適應(yīng)更多的現(xiàn)實(shí)應(yīng)用問(wèn)題,已成為聚類(lèi)分析中一個(gè)重要的新興分支。本文從譜聚類(lèi)的產(chǎn)生、發(fā)展、基本理論和代表算法等方面比較系統(tǒng)的總結(jié)了譜聚類(lèi)算法及其研究進(jìn)展,可望使讀者對(duì)譜聚類(lèi)形成基本的初步認(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ú)立分量分析和譜聚類(lèi)支持的紋理探測(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ù)約束的譜聚類(lèi)算法[J].電腦知識(shí)與技術(shù),2011,17(41):65.
[16] 王春騰,符傳誼.基于獨(dú)立成分分析的譜聚類(lèi)方法[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.