On Spectral Clustering: Analysis and an Algorithm

Authors

Andrew Ng, Michael Jordan, Yair Weiss

Year

2001

Conference Paper

Algorithm

Ng-Jordan-Weiss Spectral Clustering

Source

Advances in Neural Information Processing Systems

Abstract¶

Despite many empirical successes of spectral clustering methods - algorithms that cluster points using eigenvectors of matrices derived from the data - there are several unresolved issues. First, there are 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.

Summary¶

Presents a simple spectral clustering algorithm based on eigenvectors of an affinity-derived matrix and analyzes conditions under which it recovers meaningful clusters. The paper helped standardize the normalized spectral clustering recipe and connected its empirical success to matrix perturbation arguments.