An Empirical Analysis of Similarity Matrix for Spectral Clustering

Abstract:

Constructing the similarity matrix is the key step for spectral clustering, and its goal is to model the local neighborhood relationships between the data points. In order to evaluate the influence of similarity matrix on performance of the different spectral clustering algorithms and find the rules on how to construct an appropriate similarity matrix, a system empirical study was carried out. In the study, six recently proposed spectral clustering algorithms were selected as evaluation object, and normalized mutual information, F-measures and Rand Index were used as evaluation metrics. Then experiments were carried out on eight synthetic datasets and eleven real word datasets respectively. The experimental results show that with multiple metrics the results are more comprehensive and confident, and the comprehensive performance of locality spectral clustering algorithm is better than other five algorithms on synthetic datasets and real word datasets.

• Periodical: Applied Mechanics and Materials (Volumes 433-435)
• Pages: 725-730
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.433-435.725
• Online since: October 2013
• Authors: Sheng Zhang, Xiao Qi He*, Yang Guang Liu, Qi Chun Huang
• Keywords: Evaluation Metrics, Similarity Matrix, Spectral Clustering

References

[1] M.I. Jordan and F.R. Bach. Learning spectral clustering, Advances in Neural Information Processing Systems 16, (2004), p.305–312.

[2] A.Y. Ng, M.I. Jordan and Y. Weiss. On spectral clustering: Analysis and an algorithm, Advances in Neural Information Processing Systems14, Vol. 2, ( 2002), pp.849-856.

[3] E. Hullermeier, M. Rifqi and S. Henzgen. Comparing fuzzy partitions: A generalization of the Rand index and related measures, Fuzzy Systems, IEEE Transactions on, Vol. 20, ( 2012) , pp.546-556.

DOI: 10.1109/tfuzz.2011.2179303

[4] N. Ye, K.M.A. Chai, W.S. Lee and H. L. Chieu. Optimizing F-Measures: A Tale of Two Approaches, In Proceedings of the International Conference on Machine Learning, Edinburgh, Scotland, UK, (2012).

[5] P.A. Estévez, M. Tesmer, C.A. Perez and J.M. Zurada. Normalized mutual information feature selection, Neural Networks, IEEE Transactions on, Vol. 20, (2009), pp.189-201.

DOI: 10.1109/tnn.2008.2005601

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

DOI: 10.1007/s11222-007-9033-z

[7] P. Perona and L. Zelnik-Mano. Self-tuning spectral clustering, Advances in Neural Information Processing Systems19, (2004), pp.1601-1608.

[8] R. J. Gu, B. Ye and W. B. Xu. An improved spectral clustering algorithm, Journal of Computer Research and Development, Vol. 44, (2007), pp.145-149.

[9] X. Y. Liu and J. W. Li et al. Adaptive Spectral Clustering Based on Shared Nearest Neighbors, Journal of Chinese Computer Systems, Vol. 32, (2011), pp.1876-1880.

[10] Y. C. Gong and C. Chen. Locality Spectral Clustering, AI 2008: Advances in Synthetic datasets Intelligence, Vol. 5360, (2008), pp.348-354.

DOI: 10.1007/978-3-540-89378-3_34

[11] H. Chang, D.Y. Yeung. Robust path-based spectral clustering, Pattern Recognition, Vol. 41, ( 2008) pp.191-203.

DOI: 10.1016/j.patcog.2007.04.010

[12] W. M. Rand. Objective criteria for the evaluation of clustering methods, Journal of the American Statistical Association, Vol. 66, (1971), pp.846-850.

DOI: 10.1080/01621459.1971.10482356

[13] D. Pfitzner and R. Leibbrandt et al. Characterization and evaluation of similarity measures for pairs of clusterings, Knowledge and Information Systems, Vol. 19, (2009), pp.361-394.

DOI: 10.1007/s10115-008-0150-6

[14] E. Amigó, J. Gonzalo, J. Artiles and F. Verdejo. A comparison of extrinsic clustering evaluation metrics based on formal constraints, Information retrieval, Vol. 12, ( 2009), pp.461-486.

DOI: 10.1007/s10791-008-9066-8

[15] T.M. Cover and J. A. Thomas. Elements of information theory, Wiley-interscience(2012).

[16] UCI Machine Learning Repository: http: /archive. ics. uci. edu/ml/datasets. html.