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.
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.
code/ch14_unsupervised_learning_b.py (rings, similarity_graph, spectral_embedding, kmeans_js, fig_14_29); this page draws the same rings and runs the same computations.