Research on Spectral Clustering

Abstract:

Spectral clustering algorithm is a kind of clustering algorithm based on spectral graph theory. As spectral clustering has deep theoretical foundation as well as the advantage in dealing with non-convex distribution, it has received much attention in machine learning and data mining areas. The algorithm is easy to implement, and outperforms traditional clustering algorithms such as K-means algorithm. This paper aims to give some intuitions on spectral clustering. We describe different graph partition criteria, the definition of spectral clustering, and clustering steps, etc. Finally, in order to solve the disadvantage of spectral clustering, some improvements are introduced briefly.

• Periodical: Applied Mechanics and Materials (Volumes 687-691)
• Pages: 1350-1353
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.687-691.1350
• Online since: November 2014
• Authors: Li Li Fu*, Yong Li Liu, Li Jing Hao
• Keywords: Clustering, Graph Partition, Spectral Clustering

References

[1] J. Shi, J. Malik. Normalized cuts and image segmentation. Pattern Analysis and Machine Intelligence, IEEE Transactions on, Vol. 22(2000), pp.888-905.

DOI: 10.1109/34.868688

[2] A.Y. Ng, M.I. Jordan, Weiss Y. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, Vol. 2(2002), pp.849-856.

[3] M. MeilPa, J. Shi. Learning segmentation by random walks. Neural Information Processing Systems, (2001).

[4] U. Von Luxburg. A tutorial on spectral clustering. Statistics and computing, Vol. 17(2007), pp.395-416.

DOI: 10.1007/s11222-007-9033-z

[5] Z. Wu, R. Leahy. An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation. Pattern Analysis and Machine Intelligence, IEEE Transactions on, Vol. 15. 11(1993), pp.1101-1113.

DOI: 10.1109/34.244673

[6] S. Sarkar, K.L. Boyer. Quantitative measures of change based on feature organization: Eigenvalues and eigenvectors. In Computer Vision and Pattern Recognition, 1996. Proceedings CVPR'96, 1996 IEEE Computer Society Conference on. IEEE, (1996).

DOI: 10.1109/cvpr.1996.517115

[7] C.H.Q. Ding, X. He, H. Zha, M. Gu, H.D. Simon. A min-max cut algorithm for graph partitioning and data clustering. In Data Mining, 2001. ICDM 2001, Proceedings IEEE International Conference on. IEEE, (2001), pp.107-114.

DOI: 10.1109/icdm.2001.989507

[8] S. Wang, J.M. Siskind. Image segmentation with ratio cut. Pattern Analysis and Machine Intelligence, IEEE Transactions on, Vol. 25(2003), pp.675-690.

DOI: 10.1109/tpami.2003.1201819

[9] M. Meila, J. Shi. A random walks view of spectral segmentation. In Richardson T and Jaakkola T, editors, Workshop on Artificial Intelligence and Statistics, Society for Artificial Intelligence and Statistics, Key West, FL(2001).

[10] F. Zhao, H. Liu, L. Jiao. Spectral clustering with fuzzy similarity measure. Digital Signal Processing, Vol. 21(2011), pp.701-709.

DOI: 10.1016/j.dsp.2011.07.002

[11] A. Choromanska, T. Jebara, H. Kim, M. Mohan, C. Monteleoni. Fast spectral clustering via the nyström method. In Algorithmic Learning Theory. Springer Berlin Heidelberg (2013), pp.367-381.

DOI: 10.1007/978-3-642-40935-6_26

[12] T. Xiang, S. Gong. Spectral clustering with eigenvector selection. Pattern Recognition, Vol. 41(2008), pp.1012-1029.

DOI: 10.1016/j.patcog.2007.07.023

[13] S.A. Toussi, H.S. Yazdi, E. Hajinezhad, S. Effati. Eigenvector Selection in Spectral Clustering using Tabu Search. In 2011 1st International eConference on Computer and Knowledge Engineering, 2011. IEEE Computer Society, (2011), pp.75-80.

DOI: 10.1109/iccke.2011.6413328

[14] H. Ning, W. Xu, Y. Chi, Y. Gong, T.S. Huang. Incremental spectral clustering by efficiently updating the eigen-system. Pattern Recognition, Vol. 43(2010), pp.113-127.

DOI: 10.1016/j.patcog.2009.06.001