Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Large Scale Spectral Clustering Using Resistance Distance and Spielman-Teng Solvers
verfasst von : Nguyen Lu Dang Khoa, Sanjay Chawla
Erschienen in: Discovery Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The promise of spectral clustering is that it can help detect complex shapes and intrinsic manifold structure in large and high dimensional spaces. The price for this promise is the computational cost
O
(
n
3
) for computing the eigen-decomposition of the graph Laplacian matrix - so far a necessary subroutine for spectral clustering. In this paper we bypass the eigen-decomposition of the original Laplacian matrix by leveraging the recently introduced Spielman and Teng near-linear time solver for systems of linear equations and random projection. Experiments on several synthetic and real datasets show that the proposed approach has better clustering quality and is faster than the state-of-the-art approximate spectral clustering methods.