Title: Accelerating spectral clustering with partial supervision
Authors: MAVROEIDIS DIMITRIOS
Citation: DATA MINING AND KNOWLEDGE DISCOVERY vol. 21 no. 2 p. 241-258
Publisher: SPRINGER
Publication Year: 2010
JRC Publication N°: JRC62667
ISSN: 1384-5810
URI: http://www.springerlink.com/content/m3x0123023572300/
http://publications.jrc.ec.europa.eu/repository/handle/JRC62667
DOI: 10.1007/s10618-010-0191-9
Type: Articles in Journals
Abstract: Spectral Clustering is a popular learning paradigm that employs the eigenvectors and eigenvalues of an appropriate input matrix for approximating the clustering objective. Albeit its empirical success in diverse application areas, spectral clustering has been criticized for its inefficiency when dealing with large-size datasets. This is mainly due to the fact that the complexity of most eigenvector algorithms is cubic with respect to the number of instances and even memory efficient iterative eigensolvers (such as the Power Method) may converge very slowly to the desired eigenvector solutions. In this paper, inspired from the relevant work on Pagerank we propose a semisupervised framework for spectral clustering that provably improves the efficiency of the Power Method for computing the Spectral Clustering solution. The proposed method is extremely suitable for large and sparse matrices, where it is demonstrated to converge to the eigenvector solution with just a few Power Method iterations. The proposed framework reveals a novel perspective of semi-supervised spectral methods and demonstrates that the efficiency of spectral clustering can be enhanced not only by data compression but also by introducing the appropriate supervised bias to the input Laplacian matrix. Apart from the efficiency gains, the proposed framework is also demonstrated to improve the quality of the derived cluster models.
JRC Institute:Institute for the Protection and Security of the Citizen

Files in This Item:
There are no files associated with this item.


Items in repository are protected by copyright, with all rights reserved, unless otherwise indicated.