譜聚類算法研究

徐天順

摘要：近年來(lái)，譜聚類因其深厚的理論基礎(chǔ)而在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域中引起了廣泛的關(guān)注，該算法應(yīng)用簡(jiǎn)單且聚類性能優(yōu)于傳統(tǒng)的聚類算法，比如k-means算法等。該文旨在對(duì)譜聚類算法進(jìn)行綜述，總結(jié)了不同的圖劃分準(zhǔn)則及其性能，介紹了經(jīng)典的譜聚類算法，最后分析總結(jié)了譜聚類算法的優(yōu)缺點(diǎn)。

關(guān)鍵詞：譜聚類；圖劃分準(zhǔn)則；聚類算法

中圖分類號(hào)：TN923文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2012)16-3948-03

Research on Spectral Clustering

XU Tian-shun

（Deputy to the Signal Corps Army, Zhengzhou 450002,China）

Abstract: In recent years, Spectral analysis approaches have received much attention in machine learning and data mining areas, due to their rich theoretical foundations. It is simple to implement, and outperforms traditional clustering algorithms such as the k-means algo? rithm. The goal of this paper is to give some intuition on spectral clustering. We describe different graph cut criterion and their basic prop? erties, present the most common spectral clustering algorithms. Advantages and disadvantages of the spectral clustering algorithms are also discussed.

Key words: Spectral Clustering; graph cut criterion; Clustering Algorithm

譜聚類的思想來(lái)源于譜圖劃分理論[1]。該算法利用譜松弛的方法將圖分割問(wèn)題轉(zhuǎn)化為譜分解問(wèn)題，最后得到數(shù)據(jù)的劃分，非常適用于許多實(shí)際應(yīng)用問(wèn)題，包括VLSI設(shè)計(jì)、圖像分割[2]、語(yǔ)音識(shí)別、網(wǎng)頁(yè)劃分和文本挖掘等領(lǐng)域。典型的SC算法包括Shi和Malik[3]的Ncut算法，以及Ng等人提出NJW算法[4]。其中NJW算法穩(wěn)定性較好，是最常用的SC算法之一。

譜聚類可以在任意形狀的樣本空間上聚類，且收斂于全局最優(yōu)解，因此在處理復(fù)雜高維數(shù)據(jù)方面有著明顯的優(yōu)勢(shì)。總的說(shuō)來(lái)，該算法的不足之處表現(xiàn)在：1)算法要求在聚類之前設(shè)置適于具體應(yīng)用的尺度參數(shù)，通常選用一些經(jīng)驗(yàn)值；2)初始聚類中心的選擇對(duì)算法的影響很大，存在初始值敏感問(wèn)題；3)圖劃分準(zhǔn)則的優(yōu)化問(wèn)題，即很難得到圖切準(zhǔn)則的優(yōu)化解；4)聚類數(shù)目的確定很大程度上影響了算法的性能。

參考文獻(xiàn):

[1] Von Luxburg U. A Tutorial on Spectral Clustering [J]. Statistics and Computing,2007, 17(4):395-416.

[2] Sarkar S, Soundararajan P. Supervised Learning of Large Perceptual Organization: G-raph Spectral Partitioning and Learning Automata[C]. IEEE Trans on Pattern Analysis and Machine Intelligence. Washington, USA, 2000, 22(5):504-525.

[3] Meila M, Xu L. Multiway Cuts and Spectral Clustering [C]. Dept. of Statistics Tec-hnical Report, Dayton, USA, 2003.

[4] Ng Jordan M.On Spectral Clustering: Analysis and an Algorithm [C]. Advances in NIPS. Columbia, British, 2001:849-856.

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

[6] Shi J, Malik J. Normalized Cuts and Image Segmentation [J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905.

[7] Wu Z, Leahy R. An Optimal Graph Theoretic Approach to Data Clustering: Theory and its Application to Image Segmentation [C]. IEEE Trans on Pattern Analysis and Machine Intelligence, New York, USA, 1993, 15(11):1101-1113.

[8]司文武,錢(qián)濤.一種基于譜聚類的半監(jiān)督聚類算法[J].計(jì)算機(jī)應(yīng)用, 2005, 25(6):1347-1349.

[9] Chang H, Yeung DY. Robust path-based spectral clustering [J]. Pattern Recognition, 2008, 41(1):191-203.

[10] Huazhong Ning,Wei Xu. Incremental Spectral Clustering by Efficiently Updating the Eigensystem [J]. Pattern Recognition, 2010, 43(1): 113-127.

[11] Lu Z, Perpinan M A. Constrained Spectral Clustering through Affinity Propagation [C]. Proceedings of the Computer Vision and Pattern Recognition, Alaska, USA, 2008.

[1] Tian Xia, Juan Cao. On Definition Affinity Graph for Spectral Clustering through Ranking on Manifold [J]. Neurocomputing, 2009, 72(13):3203-3211.

[12]王會(huì)青,陳俊杰,郭凱.遺傳優(yōu)化的譜聚類方法研究[J].計(jì)算機(jī)工程與應(yīng)用, 2007, 47(11):143-145.

[13]王玲,薄列峰,焦李成.密度敏感的半監(jiān)督譜聚類[J].軟件學(xué)報(bào), 2007, 18(10):2412-242.