Interactive demo · Statistical Learning: Theory and Methods · Chapter 14

Spectral clustering: why the smallest eigenvectors of the graph Laplacian find the rings

K-means looks for compact, convex groups and cannot separate concentric rings. Spectral clustering first joins each point to its k nearest neighbours with weights w = exp(−d2/c), then uses the eigenvectors of the graph Laplacian L = G − W with the smallest eigenvalues as new coordinates. Since fTLf = ½∑ wii′(fi − fi′)2, a small eigenvalue means a vector that is nearly constant along every edge: on a graph whose rings are almost disconnected, nearly constant on each ring. K-means on those coordinates is easy.

Data

Noise sd

Neighbours k (60 = fully connected)

Kernel scale c

Laplacian

Colour points by

Try these

The rings are drawn with a fixed seed (450 points, radii 1, 2.8 and 5, or 300 points with radii 1 and 3). K-means uses 10 random starts with a fixed seed, on the raw coordinates or on eigenvectors 2 to K. ARI is the adjusted Rand index against the true rings (1 = perfect, about 0 = chance). "Random walk" uses Lv = λGv, the Laplacian I − G−1W.

In the lecture notes