谱聚类的算子理论研究进展

计算机科学 ›› 2013, Vol. 40 ›› Issue (Z6): 153-156.

谱聚类的算子理论研究进展

管涛,王杰

郑州航空工业管理学院计算机科学与应用系郑州450015;郑州航空工业管理学院计算机科学与应用系郑州450015

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金项目(41171341),教育部新世纪优秀人才支持计划(NCET-09-0126),河南省科技厅项目(122102210227,10140,102102210447),河南省教育厅项目(2011B520038,0B520032),郑州市科技局项目(112PPTGY248-6)资助

Operator Theory Frontier of Spectral Clustering

GUAN Tao and WANG Jie

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 谱聚类来源于算子理论研究成果,在大数据降维和分类中发挥着重要的作用,但是目前国内的研究多注重应用算法设计,很少见到谱聚类理论方面的研究。为弥补这方面的一些不足,较为系统地总结了这些理论,侧重于阐述与谱聚类的算子理论紧密相关的最新理论研究成果,并简要介绍了一些具体的谱聚类算法、原理及其性能。从积分算子、图谱理论、流形学习出发,评述和分析了谱聚类的最新理论原理、收敛性结论、发展现状以及与流形学习的内在联系,最后指出了理论研究的一些方向。

关键词: 谱聚类,积分算子,流形学习,Laplacian特征映射(LEM),算子收敛性

Abstract: Spectral clustering comes from operator theory and is able to efficiently decrease data dimension and classify data．However,current domestic researches pay more attention to applied algorithm design,and there is lack of theoretical outcome．In order to make up the shortcomings in theory,this paper systematically summaries the theory of spectral clustering,pays more attention to study the newest foreign operator theory research achievements．Besides,we briefly discuss and analyze some specific spectral clustering algorithms．We introduce and analyze the principle,convergence,current status of spectral clustering and its inherent association with manifold learning in terms of integral operator,spectral graph theory and manifold learning．At last,we suggest some possible directions.

Key words: Spectral clustering,Integral operator,Manifold learning,Laplacian eigenmap(LEM),Convergence of operator

管涛,王杰. 谱聚类的算子理论研究进展[J]. 计算机科学, 2013, 40(Z6): 153-156. https://doi.org/

GUAN Tao and WANG Jie. Operator Theory Frontier of Spectral Clustering[J]. Computer Science, 2013, 40(Z6): 153-156. https://doi.org/

参考文献

[1] von Luxburg U．A tutorial on spectral clustering [J]．Statistics and Computing,2007,7(4):1-32
[2] Bath F R,Jordan M I．Learning spectral clustering[R].Technical report,UC Berkeley,2003
[3] Ng A,Jordan M,Weiss Y．On spectral clustering:analysis and an algorithm[C]∥Neural Information Processing Systems,2001,4:849-856
[4] 盛宝怀,等.核学习中的非光滑分析法[M].北京:科学出版社,2012
[5] Fowlkes C,Belongie S,Chung F,et al．Spectral grouping using the Nystrm method[J]．IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,6(2):214-225
[6] Williams C K I,Seeger M．The effect of the input density distribution on kernel-based classifiers[C]∥Proceedings of the 17th International Conference on Machine Learning．2000:1159-1166
[7] Drineas P,Mahoney M W．On the Nystrm method for approximating a Gram matrix for improved kernel-based learning[J]．Journal of Machine Learning Research,2005,6:2153-2175
[8] 李小斌,田铮．基于谱聚类的图像多尺度随机树分割[J].中国科学E辑:信息科学,2007,7(8):1073-1085
[9] Zhang K,Tsang I W,Kwok J T．Improved Nystrm low-rank approximation and error analysis[C]∥Proceedings of the 25th International Conference on Machine Learning．2008:1232-1239
[10] Shi Tao,Belkin M,Yu Bin．Data spectroscopy:eigenspaces of convolution operators and clustering[J]．The Annals of Statistics,2009,37(6B):3960-3984
[11] Kumar S,Mohri M,Talwalkar A．Sampling methods for theNystrm method[J]．Journal of Machine Learning Research,2012(13):981-1006
[12] 韩彦彬.高维正定核的本征值[J].数学学报,1993,32(2):188-194
[13] von Luxberg U,Belkin M,Bousquet O．Consistency of spectral clustering[J]．The Annals of Statistics,2008,6:555-586
[14] Rosasco L,Belkin M,Vito E D．On learning with integral operators[J].Journal of Machine Learning Research,2010,11:905-934
[15] Pelletier B,Pudlo P．Operator norm convergence of spectralclustering on level sets[J]．Journal of Machine Learning Research,2011,12:385-416
[16] Belkin M,Niyogi P．Laplacian eigenmaps and spectral techniques for embedding and clustering[C]∥Neural Information Proces-sing Systems．2001,4:585-591
[17] Belkin M,Niyogi P．Convergence of Laplacian eigenmaps[C]∥Neural Information Processing Systems．2006:129-136
[18] Lafon S S．Diffusion Maps and Geometric Harmonics[D]．PhD thesis,Yale University,2004
[19] Hein M,Audibert J-Y,von Luxburg U．From graphs to manifolds-weak and strong pointwise consistency of graph Laplacians[C]∥18th Annual Conference on Learning Theory．2005:470-485
[20] Singer A．From graph to manifold Laplacian:the convergence rate[J]．Applied and Computational Harmonic Analysis,2006,1(1):135-144
[21] Bengio Y,et al．Spectral clustering and kernel PCA are learning eigenfunctions[R]．Technical Report 1239,Département d’Informatique et Recherche Opérationnelle,Universitéde Montréal,Montréal,2004
[22] 张振跃,查宏远.线性低秩逼近与非线性降维[J].中国科学A辑,数学,2005,5(3):273-285
[23] Frieze A,Kannan R,Vempala S．Fast Monte-Carlo algorithm for finding low-rank approximations [J]．Journal of the ACM,2004,1(6):1025-1041
[24] Frieze A,Kannan R．Quick approximation to matrices and applications[J]．Combinatorica,1999,9(2):175-220
[25] Filippone M,Camastra F,Masulli F,et al．A survey of kerneland spectral methods for clustering[J].Pattern Recognition,2008,1:176-190
[26] De la Torre F．A least-squares unified view of PCA,LDA,CCA,and spectral graph methods[R]．CMU-RI-TR-08-29,Robotics Institute,Carnegie Mellon University,2008
[27] Yan S,Xu D,Zhang B,Zhang H．Graph embedding and extensions:A general framework for dimensionality reduction[J].IEEE Transactions Pattern Analysis and Machine Intelligence,2007,29(1):40-51
[28] Cai D,He X,Han J．SRDA:An efficient algorithm for large-scale discriminant analysis[J]．IEEE Transactions on Knowledge and Data Engineering,2008,20(1):1-12
[29] Belkin M,Sinha K．Toward learning Gaussian mixtures with arbitrary separation[C]∥COLT．2010:407-419

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed