Abstract
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.
Keywords
Cluster analysisSpectral clusteringComputer scienceEigenvalues and eigenvectorsAlgorithmCURE data clustering algorithmCorrelation clusteringMATLABData miningTheoretical computer scienceArtificial intelligence
Affiliated Institutions
Related Publications
Model-Based Clustering, Discriminant Analysis, and Density Estimation
Cluster analysis is the automated search for groups of related observations in a dataset. Most clustering done in practice is based largely on heuristic but intuitively reasonab...
Learning Eigenfunctions Links Spectral Embedding and Kernel PCA
In this letter, we show a direct relation between spectral embedding methods and kernel principal components analysis and how both are special cases of a more general learning p...
Kernel k-means
Kernel k-means and spectral clustering have both been used to identify clusters that are non-linearly separable in input space. Despite significant research, these methods have ...
On clusterings
We motivate and develop a natural bicriteria measure for assessing the quality of a clustering that avoids the drawbacks of existing measures. A simple recursive heuristic is sh...
On the Quality of Spectral Separators
Computing graph separators is an important step in many graph algorithms. A popular technique for finding separators involves spectral methods. However, there has not been much ...
Publication Info
- Year
- 2001
- Type
- article
- Volume
- 14
- Pages
- 849-856
- Citations
- 7749
- Access
- Closed
External Links
Citation Metrics
7749
OpenAlex
Cite This
Andrew Y. Ng,
Michael I. Jordan,
Yair Weiss
(2001).
On Spectral Clustering: Analysis and an algorithm.
, 14
, 849-856.