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
Learning Segmentation by Random Walks
We present a new view of image segmentation by pairwise similarities. We interpret the similarities as edge ows in a Markov random walk and study the eigenvalues and eigenvector...
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 the Equivalence of Nonnegative Matrix Factorization and Spectral Clustering
Current nonnegative matrix factorization (NMF) deals with X = FGT type. We provide a systematic analysis and extensions of NMF to the symmetric W = HHT, and the weighted W = HSH...
On clusterings-good, bad and spectral
We propose a new measure for assessing the quality of a clustering. A simple heuristic is shown to give worst-case guarantees under the new measure. Then we present two results ...
Unsupervised K-Means Clustering Algorithm
The k-means algorithm is generally the most known and used clustering method. There are various extensions of k-means to be proposed in the literature. Although it is an unsuper...
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.