On Spectral Clustering: Analysis and an algorithm

TLDR

Spectral clustering methods, which use eigenvectors of data‑derived matrices, have shown empirical success but face unresolved issues, including a wide variety of algorithmic variations and a lack of proofs guaranteeing reasonable clustering. The authors propose a simple spectral clustering algorithm that can be implemented in a few lines of Matlab. They analyze the algorithm using matrix perturbation theory and provide conditions under which it is expected to perform well. Experimental results demonstrate surprisingly good performance on several challenging clustering problems. First.

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.