Abstract
In this paper we propose a new method for choosing the number of clusters and the most appropriate eigenvectors, that allow to obtain the optimal clustering. To accomplish the task we suggest to examine carefully properties of adjacency matrix eigenvectors: their weak localization as well as the sign of their values. The algorithm has only one parameter — the number of mutual neighbors. We compare our method to several clustering solutions using different types of datasets. The experiments demonstrate that our method outperforms in most cases many other clustering algorithms.
Chapter PDF
Similar content being viewed by others
References
Dhillon, I., Guan, Y., Kulis, B.: Weighted graph cuts without eigenvectors: a multilevel approach. IEEE Transactions on Pattern Analysis and Machine Intelligence 29(11), 1944–1957 (2007)
Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czechoslovak Mathematical Journal 25, 619–633 (1975)
Filoche, M., Mayboroda, S.: Universal mechanism for Anderson and weak localization. Proc. of the National Academy of Sciences 109(37), 14761–14766 (2012)
Fridlyand, J., Dudoit, S.: A prediction-based resampling method to estimate the number of clusters in a dataset. Genome Biology 3, 7 (2002)
Fischer, I., Poland, J.: Amplifying the Block Matrix Structure for Spectral Clustering. Technical Report No. IDSIA-03-05, Telecommunications Lab, pp. 21–28 (2005)
Hagen, L., Kahng, A.: New spectral methods for ratio cut partitioning and clustering. IEEE Transactions on Computer-Aided Design 11, 1074–1088 (1992)
Jain, A., Law, M.: Data clustering: A user’s dilemma. In: Pal, S.K., Bandyopadhyay, S., Biswas, S. (eds.) PReMI 2005. LNCS, vol. 3776, pp. 1–10. Springer, Heidelberg (2005)
Kannan, R., Vempala, S., Vetta, A.: On clusterings: good, bad and spectral. In: 41st Symposium on Foundations of Computer Science, FOCS (2000)
Lucińska, M.: A spectral clustering algorithm based on eigenvector localization. In: Rutkowski, L., Korytkowski, M., Scherer, R., Tadeusiewicz, R., Zadeh, L.A., Zurada, J.M. (eds.) ICAISC 2014, Part II. LNCS, vol. 8468, pp. 749–759. Springer, Heidelberg (2014)
Manning, C.D., Raghavan, P., Schtäuze, H.: Introduction to Information Retrieval. Cambridge University Press (2008)
Meila, M., Shi, J.: A random walks view of spectral segmentation. In: Proc. of 10th International Workshop on Artificial Intelligence and Statistics (2001)
Ng, A., Jordan, M., Weiss, Y.: On spectral clustering: Analysis and an algorithm. In: Dietterich, T.G., Becker, S., Ghahramani, Z. (eds.) Advances in Neural Information Processing Systems, vol. 14, pp. 849–856. MIT Press, Cambridge (2002)
Pentney, W., Meila, M.: Spectral clustering of biological sequence data. In: AAAI 2005, pp. 845–850 (2005)
Shang, F., Jiao, L.C., Shi, J., Wang, F., Gong, M.: Fast affinity propagation clustering: A multilevel approach. Pattern Recognition 45, 474–486 (2012)
von Luxburg, U.: A Tutorial on spectral clustering. Statistics and Computing 17(4), 395–416 (2007)
Yan, D., Huang, L., Jordan, M.: Fast approximate spectral clustering. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 907–916 (2009)
Zelnik-Manor, L., Perona, P.: Self-tuning spectral clustering. In: Proceedings of the Advances in Neural Information Processing Systems, vol. 17, pp. 1601–1608 (2005)
Zhang, K., Kwok, J.T.: Density-weighted Nyström method for computing large kernel eigen-systems. Neural Computation 21, 121–146 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 IFIP International Federation for Information Processing
About this paper
Cite this paper
Lucińska, M., Wierzchoń, S.T. (2014). Spectral Clustering Based on Analysis of Eigenvector Properties. In: Saeed, K., Snášel, V. (eds) Computer Information Systems and Industrial Management. CISIM 2015. Lecture Notes in Computer Science, vol 8838. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-45237-0_6
Download citation
DOI: https://doi.org/10.1007/978-3-662-45237-0_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-45236-3
Online ISBN: 978-3-662-45237-0
eBook Packages: Computer ScienceComputer Science (R0)