Abstract
Kernel spectral clustering is a model-based spectral clustering method formulated in a primal-dual framework. It has a powerful out-of-sample extension property and a model selection procedure based on the balanced line fit criterion. This paper is an improvement of a previous work which sparsified the kernel spectral clustering method using the line structure of the data projections in the eigenspace. However, the previous method works only in the case of well formed and well separated clusters as in other cases the line structure is lost. In this paper, we propose two highly sparse extensions of kernel spectral clustering that can overcome these limitations. For the selection of the reduced set we use the concept of angles between the data projections in the eigenspace. We show the effectiveness and the amount of sparsity obtained by the proposed methods for several synthetic and real world datasets.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ng, A.Y., Jordan, M.I., Weiss, Y.: On spectral clustering: analysis and an algorithm. In: Dietterich, T.G., Becker, S., Ghahramani, Z. (eds.) Proceedings of the Advances in Neural Information Processing Systems, pp. 849–856. MIT Press, Cambridge (2002)
Luxburg, U.: A tutorial on Spectral clustering. Statistics and Computing 17(4), 395–416
Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Intelligence 22(8), 888–905 (2000)
Alzate, C., Suykens, J.A.K.: Multiway spectral clustering with out-of-sample extensions through weighted kernel PCA. IEEE Transactions on Pattern Analysis and Machine Intelligence 32(2), 335–347 (2010)
Alzate, C., Suykens, J.A.K.: Highly Sparse Kernel Spectral Clustering with Predictive Out-of-sample extensions. In: ESANN, pp. 235–240 (2010)
Mall, R., Langone, R., Suykens, J.A.K.: Kernel Spectral Clustering for Big Data Networks. Entropy 15(5), 1567–1586 (2013)
Langone, R., Mall, R., Suykens, J.A.K.: Soft Kernel Spectral Clustering. IJCNN (2013)
Alzate, C., Suykens, J.A.K.: Sparse kernel spectral clustering models for large-scale data analysis. Neurocomputing 74(9), 1382–1390 (2011)
Suykens, J.A.K., Van Gestel, T., De Brabanter, J., De Moor, B., Vandewalle, J.: Least Squares Support Vector Machines. World Scientific, Singapore (2002)
Girolami, M.: Orthogonal series density estimation and the kernel eigenvalue problem. Neural Computation 14(3), 1000–1017 (2002)
Kenney, J.F., Keeping, E.S.: Linear Regression and Correlation. Mathematics of Statistics 3(1), ch. 15, 252–285
Rabbany, R., Takaffoli, M., Fagnan, J., Zaiane, O.R., Campello, R.J.G.B.: Relative Validity Criteria for Community Mining Algorithms. In: International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp. 258–265 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mall, R., Langone, R., Suykens, J.A.K. (2013). Highly Sparse Reductions to Kernel Spectral Clustering. In: Maji, P., Ghosh, A., Murty, M.N., Ghosh, K., Pal, S.K. (eds) Pattern Recognition and Machine Intelligence. PReMI 2013. Lecture Notes in Computer Science, vol 8251. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45062-4_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-45062-4_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45061-7
Online ISBN: 978-3-642-45062-4
eBook Packages: Computer ScienceComputer Science (R0)