Abstract Spectral clustering is able to find the nonlinear low-rank structure of data, and it is widely applied to pattern recognition.Besides,spectral clustering has some internal relations with graph models, manifold embedding and integral operator theory from the theoretical view.However, it is lack of systematically theoretical research in these aspects. The general model of spectral clustering is introduced from the latest research outcomes, that is, eigenfunctions learning of integral operators inreproducing kernel Hilbert space(RKHS). Subsequently, the internal relations of spectral clustering with KPCA, kernel k-means,Laplacian eigenmap, manifold learning, and discriminant analysis are discussed. Then, some classical spectral clustering algorithms are introduced, such as NJW algorithm, Ncut, spectral clustering based on Nystrm method, multiscale spectral clustering algorithm. At last, trends and possible difficulties in spectral clustering are summarized.
[1] Filippone M, Camastra F, Masulli F, et al. A Survey of Kernel and Spectral Methods for Clustering. Pattern Recognition, 2008, 41(1): 176-190 [2] De la Torre F. A Least-Squares Unified View of PCA, LDA, CCA, and Spectral Graph Methods. Technical Report, CMU-RI-TR-08-29. Pittsburgh, USA: Carnegie Mellon University, 2008 [3] Yan S C, Xu D, Zhang B Y, et al. Graph Embedding and Extensions: A General Framework for Dimensionality Reduction. IEEE Trans on Pattern Analysis and Machine Intelligence, 2007, 29(1): 40-51 [4] De la Torre F. A Least-Squares Framework for Component Analysis. IEEE Trans on Pattern Analysis and Machine Intelligence, 2012, 34(6): 1041-1055 [5] Ham J H, Lee D D, Mika S, et al. A Kernel View of the Dimensionality Reduction of Manifolds. Technical Report, TR-110. Tubingen, Germany: Max Planck Institute for Biological Cybernetics, 2003 [6] Von Luxburg U, Belkin M, Bousquet O. Consistency of Spectral Clustering. The Annals of Statistics, 2008, 36(2): 555-586 [7] Von Luxburg U. A Tutorial on Spectral Clustering. Statistics and Computing, 2007, 17(4): 395-416 [8] Ng A Y, Jordan M I, Weiss Y. On Spectral Clustering: Analysis and an Algorithm // Dietterich T G, Becker S, Ghahramani Z. Advances in Neural Information Processing Systems 14. Cambridge, USA: MIT Press, 2001: 849-856 [9] Weiss Y. Segmentation Using Eigenvectors: A Unifying View // Proc of the 7th IEEE International Conference on Computer Vision. Kerkyra, Greece, 1999, II: 975- 982 [10] Bach F R, Jordan M I. Learning Spectral Clustering. Technical Report. UCB/CSD-03-1249. Berkeley, USA: University of California Berkeley, 2003 [11] Meila M, Shi J B. Learning Segmentation by Random Walks // Proc of Advances in Neural Information Processing Systems: Natural and Synthetic.Vancouver, Canada, 2000: 873-879 [12] Meila M, Shi J B. A Random Walks View of Spectral Segmentation // Proc of the 8th International Workshop on Artifical Intelligence and Statistics. San Francisco, USA, 2001: 193-199 [13] Rosasco L, Belkin M, de Vito E. On Learning with Integral Operators. Journal of Machine Learning Research, 2010, 11(3): 905-934 [14] Von Luxburg U, Belkin M, Bousquet O.Consistency of Spectral Clustering. The Annals of Statistics, 2008, 36(2): 555-586 [15] Dhillon I S, Guan Y Q, Kulis B. Weighted Graph Cuts without Eigenvectors: A Multilevel Approach. IEEE Trans on Pattern Analysis and Machine Intelligence, 2007, 29(11): 1944-1957 [16] Kong T F. Multilevel Spectral Clustering: Graph Partitions and Image Segmentation. Master Dissertation. Boston, USA: Massachusetts Institute of Technology, 2008 [17] Zhang X R, Qian X X, Jiao L C. Immune Spectral Clustering Algorithm for Image Segmentation. Journal of Software, 2010, 21(9): 2196-2205 (in Chinese) (张向荣,骞晓雪,焦李成.基于免疫谱聚类的图像分割.软件学报, 2010, 21(9): 2196-2205) [18] Li X B, Tian Z. Multiscale Stochastic Hierarchical Image Segmentation by Spectral Clustering. Science in China Series E: Information Science, 2007, 37(8): 1073-1085 (in Chinese) (李小斌,田 铮.基于谱聚类的图像多尺度随机树分割.中国科学E辑:信息科学, 2007, 37(8): 1073-1085) [19] Bengio Y, Vincent P, Paiement J F, et al. Spectral Clustering and Kernel PCA are Learning Eigenfunctions. Technical Report, 1239. Montréal, Canada: Université de Montréal, 2004 [20] Fowlkes C, Belongie S, Chung F, et al. Spectral Grouping Using the Nystrm Method. IEEE Trans on Pattern Analysis and Machine Intelligence, 2004, 26(2): 214-225 [21] Baker C T H. The Numerical Treatment of Integral Equations. Oxford, UK: Oxford University Press, 1978 [22] Williams C, Seeger M. Using the Nystrm Method to Speed up Kernel Machines // Leen T K, Dietterich T G, Tresp V. Advances in Neural Information Processing Systems 13. Cambridge, USA: MIT Press, 2001: 682-688 [23] Williams C, Seeger M. The Effect of the Input Density Distribution on Kernel-Based Classifiers // Proc of the 17th International Conference on Machine Learning. Stanford, USA, 2000: 1159-1166 [24] Reade J B, Barbey K, Pao C V. Eigenvalues of Positive Definite Kernels. SIAM Journal on Mathematical Analysis, 1983, 14(1): 152-157 [25] Bengio Y, Vincent P, Paiement J F. Learning Eigenfunctions of Similarity: Linking Spectral Clustering and Kernel PCA. Technical Report, No. 1232. Montréal, Canada: Université de Montréal, 2003 [26] Girolami M. Mercer Kernel-Based Clustering in Feature Space. IEEE Trans on Neural Networks, 2002, 13(3): 780-784 [27] Zha H Y, He X F, Ding C, et al. Spectral Relaxation for K-means Clustering // Dietterich T G, Becker S, Ghahramani Z. Advances in Neural Information Processing Systems 14, Cambridge, USA: MIT Press, 2001: 1057-1064 [28] Welling M. Kernel K-means and Spectral Clustering [EB/OL]. [2013-03-15]. http://www.ics.uci.edu/~welling/teaching/273ASpring09/SpectralClustering.pdf [29] Schlkopf B, Smola A J, Müller K R. Nonlinear Component Analysis as a Kernel Eigenvalue Problem. Neural Computation, 1998, 10(5): 1299-1319 [30] Roweis S T, Saul L K. Nonlinear Dimensionality Reduction by Locally Linear Embedding. Science, 2000, 290(5500): 2323-2326 [31] Tenenbaum J B, de Silva V, Langford J C. A Global Geometric Framework for Nonlinear Dimensionality Reduction. Science, 2000, 290(5500): 2319-2323 [32] Belkin M., Niyogi P. Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering // Dietterich T G, Becker S, Ghahramani Z. Advances in Neural Information Processing Systems 14. Cambridge, USA: MIT Press, 2001: 585-591 [33] Chen H T, Chang H W, Liu T L. Local Discriminant Embedding and Its Variants // Proc of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Diego, USA, 2005, II: 846-853 [34] Cai D, He X F, Han J W. SRDA: An Efficient Algorithm for Large-Scale Discriminant Analysis. IEEE Trans on Knowledge and Data Engineering, 2008, 20(1): 1-12 [35] He X F, Yan S C, Hu Y X, et al. Face Recognition Using Laplacianfaces. IEEE Trans on Pattern Analysis and Machine Intelligence, 2005, 27(3): 328-340 [36] Yan S C, Xu D, Zhang B Y, et al. Graph Embedding and Extensions: A General Framework for Dimensionality Reduction. IEEE Trans on Pattern Analysis and Machine Intelligence, 2007, 29(1): 40-51 [37] Tian Z, Li X B, Ju Y W. Spectral Clustering Based on Matrix Perturbation Theory. Science in China Series E: Information Sciences, 2007, 37(4): 527-543 (in Chinese) (田 铮,李小斌,句彦伟.谱聚类的扰动分析.中国科学:信息科学E辑, 2007, 37(4): 527-543) [38] Duan Y, Guan T, Liu L. Self-Organizing Map Based Multiscale Spectral Clustering for Image Segmentation // Proc of the International Conference on Computer Science and Electronics Engineering. Hangzhou, China, 2012, I: 329- 333 [39] Guan T, Yu Y L, Xue T. An Online Multiscale Clustering Algorithm for Irregular Data Sets // Proc of the International Conference on Future Computer Sciences and Application. Hong Kong, China, 2011: 209-211 [40] Shi J B, Malik J. Normalized Cuts and Image Segmentation. IEEE Trans on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905 [41] Xing E P, Jordan M I. On Semidefinite Relaxation for Normalized k-Cut and Connections to Spectral Clustering. Technical Report, UCB/CSD-03-1265. Berkeley, USA: University of California at Berkeley, 2003 [42] Zelnik-Manor L, Perona P. Self-Tuning Spectral Clustering // Saul L K, Weiss Y, Bottou L. Advances in Neural Information Processing Systems 17. Cambridge, USA: MIT Press, 2004: 1601-1608 [43] Chan P K, Schlag M D F, Zien J Y. Spectral K-Way Ratio-Cut Partitioning and Clustering. IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems, 1994, 13(9): 1088-1096 [44] Kumar S, Mohri M, Talwalkar A. Sampling Methods for the Nystrm Method. Journal of Machine Learning Research, 2012, 13: 981-1006 [45] Drineas P, Mahoney M W. On the Nystrm Method for Approximating a Gram Matrix for Improved Kernel-Based Learning. Journal of Machine Larning Research, 2005, 6: 2153-2175 [46] Frieze A, Kannan R, Vempala S. Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. Journal of the ACM, 2004, 51(6): 1025-1041 [47] Frieze A M, Kannan R. Quick Approximation to Matrices and Applications. Combinatorica, 1999, 19(2): 175-220 [48] Vlachos M, Domeniconi C, Gunopulos D, et al. Non-linear Dimensionality Reduction Techniques for Classification and Visualization // Proc of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Edmonton, Canada, 2002: 645-651 [49] Chung F R K. Spectral Graph Theory. Providence, USA: American Mathematical Society Press, 1997 [50] Kannan R, Vempala S, Vetta A. On Clusterings: Good, Bad and Spectral. Journal of the ACM, 2004, 51(3): 497-515 [51] Han Y B. The Eigenvalues of Positive Integral Operators. Chinese Science Bulletin, 1986, 30(17): 1357-1357 (in Chinese) (韩彦彬.正定积分算子的本征值.科学通报, 1986, 30(17): 1357-1357) [52] Han Y B. The Eigenvalues of High Dimension Positive Definite Kernels. Acta Mathematica Sinica, 1993, 32(2): 188-194 (in Chinese) (韩彦彬.高维正定核的本征值.数学学报, 1993, 32(2): 188-194) [53] Zhang J X. The Theory and Applications of Reproducing Kernels. Beijing, China: Science Press, 2010 (in Chinese) (张建新.再生核的理论与应用.北京:科学出版社, 2010) [54] Sonnenburg S, Rtsch G, Schfer C, et al. Large Scale Multiple Kernel Learning. Journal of Machine Learning Research, 2006, 7: 1531-1565
2014, Vol. 27 
