On Spectral Clustering: Analysis and an algorithm

Published 3 January 2001

Andrew Y. Ng, Michael I. Jordan, Yair Weiss

Citations7,751

TL;DR

A simple spectral clustering algorithm that can be implemented using a few lines of Matlab is presented, and tools from matrix perturbation theory are used to analyze the algorithm, and give conditions under which it can be expected to do well.

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

Computer Science

Neural ComputationNonlinear Component Analysis as a Kernel Eigenvalue Problem

8,078 Citations1998Bernhard Schölkopf, Alexander J. Smola +1 more

A new method for performing a nonlinear form of principal component analysis by the use of integral operator kernel functions is proposed and experimental results on polynomial feature extraction for pattern recognition are presented.

Regional conference series in mathematicsSpectral Graph Theory

5,722 Citations1996Fan Chung

Mathematics and Computers in SimulationMatrix perturbation theory

2,518 Citations1991

International Journal of Computer VisionContour and Texture Analysis for Image Segmentation

1,091 Citations2001Jitendra Malik, Serge Belongie +2 more

This paper provides an algorithm for partitioning grayscale images into disjoint regions of coherent brightness and texture, and introduces a gating operator based on the texturedness of the neighborhood at a pixel to facilitate cue combination.

Segmentation using eigenvectors: a unifying view

722 Citations1999Yaakov Weiss

A unified treatment of eigenvectors of block matrices based on eigendecompositions in the context of segmentation is given, and close connections between them are shown while highlighting their distinguishing features.

Spectral partitioning works: planar graphs and finite element meshes

406 Citations1996Daniel A. Spielman, Shang‐Hua Teng

It is proved that spectral partitioning techniques can be used to produce separators whose ratio of vertices removed to edges cut is O(/spl radic/n) for bounded-degree planar graphs and two-dimensional meshes and O(n/sup 1/d/) for well-shaped d-dimensional mesh.

On clusterings-good, bad and spectral

380 Citations2002Ramachandran Kannan, S. Vempala +1 more

Two results regarding the quality of the clustering found by a popular spectral algorithm are presented, one proffers worst case guarantees whilst the other shows that if there exists a "good" clustering then the spectral algorithm will find one close to it.

Learning Segmentation by Random Walks

370 Citations2000Marina Meilă, Jianbo Shi

This interpretation shows that spectral methods for clustering and segmentation have a probabilistic foundation and proves that the Normalized Cut method arises naturally from the framework.

Spectral partitioning

202 Citations1995Charles J. Alpert, So-Zen Yao

This work maps each graph vertex to a vector in d-dimensional space, where d is the number of eigenvectors, such that these vectors constitute an instance of the vector partitioning problem.

Discrete Applied MathematicsSpectral partitioning with multiple eigenvectors

171 Citations1999Charles J. Alpert, Andrew B. Kahng +1 more

This paper shows that when all the eigenvectors are used, graph partitioning reduces to a new vector partitioning problem, and motivates a simple ordering heuristic that is a multiple-eigenvector extension of SB.