谱聚类算法研究

2012-04-29 16:54:01徐天顺
电脑知识与技术 2012年16期

徐天顺

摘要:近年来,谱聚类因其深厚的理论基础而在机器学习和数据挖掘领域中引起了广泛的关注,该算法应用简单且聚类性能优于传统的聚类算法,比如k-means算法等。该文旨在对谱聚类算法进行综述,总结了不同的图划分准则及其性能,介绍了经典的谱聚类算法,最后分析总结了谱聚类算法的优缺点。

关键词:谱聚类;图划分准则;聚类算法

中图分类号:TN923文献标识码:A文章编号: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

谱聚类的思想来源于谱图划分理论[1]。该算法利用谱松弛的方法将图分割问题转化为谱分解问题,最后得到数据的划分,非常适用于许多实际应用问题,包括VLSI设计、图像分割[2]、语音识别、网页划分和文本挖掘等领域。典型的SC算法包括Shi和Malik[3]的Ncut算法,以及Ng等人提出NJW算法[4]。其中NJW算法稳定性较好,是最常用的SC算法之一。

谱聚类可以在任意形状的样本空间上聚类,且收敛于全局最优解,因此在处理复杂高维数据方面有着明显的优势。总的说来,该算法的不足之处表现在:1)算法要求在聚类之前设置适于具体应用的尺度参数,通常选用一些经验值;2)初始聚类中心的选择对算法的影响很大,存在初始值敏感问题;3)图划分准则的优化问题,即很难得到图切准则的优化解;4)聚类数目的确定很大程度上影响了算法的性能。

参考文献:

[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].软件学报, 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]司文武,钱涛.一种基于谱聚类的半监督聚类算法[J].计算机应用, 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]王会青,陈俊杰,郭凯.遗传优化的谱聚……

登录APP查看全文