Abstract
Finding clusters in data is a challenging task when the clusters differ widely in shapes, sizes, and densities. We present a novel spectral algorithm Speclus with a similarity measure based on modified mutual nearest neighbor graph. The resulting affinity matrix reflex the true structure of data. Its eigenvectors, that do not change their sign, are used for clustering data. The algorithm requires only one parameter – a number of nearest neighbors, which can be quite easily established. Its performance on both artificial and real data sets is competitive to other solutions.
Chapter PDF
Similar content being viewed by others
References
Chen, Y., Jensen, C.D., Gray, E., Seigneur, J.M.: Risk Probability Estimating Based on Clustering, Technical Report No. TCD-CS-2003-17, Trinity College Dublin (2003)
Cvetković, D.: Signless Laplacians and line graphs. Bull. Acad. Serbe Sci. Arts, Cl. Sci. Math. Natur., Sci. Math. 131(30), 85–92 (2005)
Deepak, V., Meila, M.: Comparison of Spectral Clustering Methods. UW TR CSE-03-05-01 (2003)
Elon, Y.: Eigenvectors of the discrete Laplacian on regular graphs a statistical approach. J. Phys. A: Math. Theor. 41 (2008)
Fischer, I., Poland, J.: Amplifying the Block Matrix Structure for Spectral Clustering. Technical Report No. IDSIA-03-05, Telecommunications Lab (2005)
Jain, A., Murty, M., Flynn, P.: Data clustering: A review. ACM Computing Surveys 31, 264–323 (1999)
Jain, A.: Data clustering: 50 years beyond K-means. Pattern Recognition Letters 31, 651–666 (2010)
MacQueen, L.: Some methods for classification and analysis of multivariate observations. In: LeCam, L., Neyman, J. (eds.) 5th Berkeley Symposium on Mathematical Statistics and Probabilitz, vol. 1, pp. 281–297. University of California Press, Berkeley (1967)
Maier, M., Hein, M., von Luxburg, U.: Cluster Identification in Nearest-Neighbor Graphs. In: Hutter, M., Servedio, R.A., Takimoto, E. (eds.) ALT 2007. LNCS (LNAI), vol. 4754, pp. 196–210. Springer, Heidelberg (2007)
Meila, M., Shi, J.: A random walks view of spectral segmentation. In: Proc. of 10th International Workshop on Artificial Intelligence and Statistics (AISTATS), pp. 8–11 (2001)
Newman, M.E.J.: Detecting community structure in networks. European Physics J. B 38, 321–330 (2004)
Ng, A., Jordan, M., Weiss, Y.: On spectral clustering: Analysis and an algorithm. In: Advances in Neural Information Processing Systems 14, pp. 849–856 (2001)
Sanchez-Silva, M.: Applicability of Network Clustering Methods for Risk Analysis. In: Topping, B.H.V., Tsompanakis, Y. (eds.) Soft Computing in Civil and Structural Engineering, pp. 283–306. Saxe-Coburg Publications, Stirlingshire (2009)
Shi, T., Belkin, M., Yu, B.: Data spectroscopy: eigenspace of convolution operators and clustering. The Annals of Statistics 37(6B), 3960–3984 (2009)
von Luxburg, U.: A tutorial on spectral clustering. J. Statistics and Computing 17(4), 395–416 (2007)
Xia, T., Cao, J., Zhang, Y., Li, J.: On defining affinity graph for spectral clustering through ranking on manifolds. Neurocomputing 72(13-15), 3203–3211 (2008)
Xu, R., Wunsch II, D.: Survey on clustering algorithms. IEEE Trans. on Neural Networks 16(3), 645–678 (2005)
Zelnik-Manor, L., Perona, P.: Self-tuning spectral clustering. In: Proc. of NIPS 2004, pp. 1601–1608 (2004)
Zhang, J.: A Clustering Application in Portfolio Management. Lecture Notes in Electrical Engineering, vol. 60, pp. 309–321 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 IFIP International Federation for Information Processing
About this paper
Cite this paper
Lucińska, M., Wierzchoń, S.T. (2012). Spectral Clustering Based on k-Nearest Neighbor Graph. In: Cortesi, A., Chaki, N., Saeed, K., Wierzchoń, S. (eds) Computer Information Systems and Industrial Management. CISIM 2012. Lecture Notes in Computer Science, vol 7564. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33260-9_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-33260-9_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33259-3
Online ISBN: 978-3-642-33260-9
eBook Packages: Computer ScienceComputer Science (R0)