On Spectral Clustering: Analysis and an algorithm
Andrew Ng, Michael I. Jordan, Yair Weiss · 2001
Despite many empirical successes of spectral clustering methods -- algorithms that cluster points using eigenvectors of matrices derived from the distances between the points -- there are several unresolved issues. First, there is a wide variety of algorithms that use the eigenvectors in slightly different ways. Second, many of these algorithms have no proof that they will actually compute a reasonable clustering. In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation theory, we analyze the algorithm, and give conditions under which it can be expected to do well. We also show surprisingly good experimental results on a number of challenging clustering problems.
Cited by 7,436 works.
Authors
References
- Nonlinear Component Analysis as a Kernel Eigenvalue Problem
- Spectral Graph Theory
- Segmentation using eigenvectors: a unifying view
- Contour and Texture Analysis for Image Segmentation
- Matrix perturbation theory
- Feature grouping by 'relocalisation' of eigenvectors of the proximity matrix
- On clusterings-good, bad and spectral
- Learning Segmentation by Random Walks
- Spectral partitioning works: planar graphs and finite element meshes
- Spectral partitioning