Computer Science ›› 2013, Vol. 40 ›› Issue (Z6): 153-156.

Previous Articles     Next Articles

Operator Theory Frontier of Spectral Clustering

GUAN Tao and WANG Jie   

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

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

[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

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!