Spectral Clustering: A Victory Lap

Math 123: Mathematical Aspects of Data Analysis — Fall 2026

Published

October 21, 2026

k-means can only return convex clusters, so it fails whenever the clusters are curved or wrapped around each other. Spectral clustering only asks that each cluster be well connected in a similarity graph. This page runs both through scikit-learn on three standard examples where k-means fails: concentric circles, two moons, and two interleaved spirals. For a slower look at the circles, see k-Means vs. Spectral Clustering on Two Circles.

import warnings

import numpy as np
import plotly.graph_objects as go
from plotly.subplots import make_subplots
from sklearn.cluster import KMeans, SpectralClustering
from sklearn.datasets import make_circles, make_moons
from sklearn.metrics import adjusted_rand_score

The data

scikit-learn has make_circles and make_moons built in. For the spirals, we put points on the curve $t\mapsto(t\cos t,\ t\sin t)$, reflect them through the origin to get the second arm, and add Gaussian noise. Each generator also returns the true group y of every point, which we only use for scoring.

def make_spirals(n_samples=600, noise=0.25, random_state=0):
    """Two interleaved spiral arms, each about one and a quarter turns long."""
    rng = np.random.default_rng(random_state)
    t_min, t_max = np.pi / 2, np.pi / 2 + 2.5 * np.pi
    # Taking the square root spreads the points evenly along the arm.
    t = t_max * np.sqrt(rng.uniform((t_min / t_max) ** 2, 1, n_samples // 2))
    arm = np.c_[t * np.cos(t), t * np.sin(t)]
    X = np.vstack([arm, -arm]) + noise * rng.standard_normal((n_samples, 2))
    y = np.repeat([0, 1], n_samples // 2)
    return X, y


datasets = {
    "circles": make_circles(n_samples=400, factor=0.4, noise=0.05, random_state=0),
    "moons": make_moons(n_samples=400, noise=0.06, random_state=0),
    "spirals": make_spirals(n_samples=600, noise=0.25, random_state=0),
}

Fit both methods

Both methods get the same instructions: find $2$ clusters. For spectral clustering, affinity="nearest_neighbors" builds the graph that joins each point to its $10$ nearest neighbours, and one setting works for all three datasets. On the circles that graph has no edges between the two rings, so scikit-learn warns that the graph is not fully connected; here the warning is good news, so we silence it.

def fit_both(X):
    kmeans = KMeans(n_clusters=2, n_init=10, random_state=0).fit_predict(X)
    with warnings.catch_warnings():
        warnings.simplefilter("ignore", UserWarning)
        spectral = SpectralClustering(n_clusters=2, affinity="nearest_neighbors",
                                      n_neighbors=10, random_state=0).fit_predict(X)
    return {"k-means": kmeans, "spectral": spectral}


labels = {name: fit_both(X) for name, (X, y) in datasets.items()}
for name, (X, y) in datasets.items():
    scores = "   ".join(f"{method} ARI {round(adjusted_rand_score(y, lab), 2) + 0.0:5.2f}"
                        for method, lab in labels[name].items())
    print(f"{name:8} {scores}")

circles  k-means ARI  0.00   spectral ARI  1.00
moons    k-means ARI  0.27   spectral ARI  1.00
spirals  k-means ARI  0.06   spectral ARI  1.00

The adjusted Rand index (ARI) is $1$ when the clusters match the true groups exactly and about $0$ for a random labelling. Spectral clustering scores a perfect $1$ on all three.

The pictures

Plot the grid

INK = "#7c7c78"                               # muted colors that read in light and dark mode
GRID = "rgba(128, 128, 128, 0.28)"
COLOR = np.array(["#2a78d6", "#eb6834"])


def align(lab, y):
    """Rename the two clusters so that cluster g matches true group g as well as possible."""
    return lab if np.mean(lab == y) >= 0.5 else 1 - lab


methods = ["k-means", "spectral"]
names = list(datasets)
titles = [f"<b>{method}</b> on {name}: ARI {round(adjusted_rand_score(datasets[name][1], labels[name][method]), 2) + 0.0:.2f}"
          for method in methods for name in names]
fig = make_subplots(rows=2, cols=3, subplot_titles=titles,
                    horizontal_spacing=0.05, vertical_spacing=0.1)
for row, method in enumerate(methods, start=1):
    for col, name in enumerate(names, start=1):
        X, y = datasets[name]
        lab = align(labels[name][method], y)
        fig.add_trace(go.Scatter(
            x=X[:, 0], y=X[:, 1], mode="markers", showlegend=False,
            marker=dict(size=6, color=COLOR[lab], line=dict(color="white", width=0.6)),
            text=[f"cluster {c}, true group {g}" for c, g in zip(lab, y)],
            hovertemplate="%{text}<extra></extra>"), row=row, col=col)

# Same scale on both axes of every panel, so circles look like circles.
for i in range(1, 7):
    suffix = "" if i == 1 else str(i)
    fig.layout[f"yaxis{suffix}"].scaleanchor = f"x{suffix}"
    fig.layout[f"xaxis{suffix}"].constrain = "domain"
fig.update_xaxes(showticklabels=False, gridcolor=GRID, linecolor=GRID, zerolinecolor=GRID)
fig.update_yaxes(showticklabels=False, gridcolor=GRID, linecolor=GRID, zerolinecolor=GRID)
fig.update_annotations(font=dict(color=INK, size=13))
fig.update_layout(template="simple_white", paper_bgcolor="rgba(0,0,0,0)",
                  plot_bgcolor="rgba(0,0,0,0)", font=dict(color=INK, size=13),
                  height=700, margin=dict(l=20, r=20, t=50, b=20), hovermode="closest")
fig.show()

Figure 1: k-means (top row) and spectral clustering with a $10$-nearest-neighbour graph (bottom row) on three datasets. Colors are the clusters found. Each panel title gives the adjusted Rand index (ARI) against the true groups.

In every top panel, k-means draws one straight cut, and each side of the cut holds pieces of both true groups. In every bottom panel, spectral clustering follows the shape of the data, because points on the same ring, moon, or arm are linked by a chain of near neighbours, and almost no edges cross between groups.

The spirals are the most delicate of the three. With $5$ neighbours the graph breaks into $6$ pieces, and spectral clustering separates pieces instead of arms; with $30$ neighbours there are enough edges between the arms that the ARI drops to about $0.2$. As always with spectral clustering, the graph is the real modelling choice (see the notes on choosing hyperparameters).

--- title: "Spectral Clustering: A Victory Lap" subtitle: "Math 123: Mathematical Aspects of Data Analysis — Fall 2026" date: 2026-10-21 number-sections: false jupyter: python3 format: html: toc: true toc-depth: 2 code-line-numbers: true code-tools: true out-width: "100%" column: page execute: echo: true draft: false --- [k-means](../../lectures/lecture-12.qmd#def-kmeans) can only return [convex](../../lectures/lecture-12.qmd#prp-voronoi-convex) clusters, so it fails whenever the clusters are curved or wrapped around each other. [Spectral clustering](../../lectures/lecture-14.qmd#alg-spectral-clustering) only asks that each cluster be well connected in a [similarity graph](../../lectures/lecture-13.qmd#from-point-clouds-to-graphs). This page runs both through scikit-learn on three standard examples where k-means fails: concentric circles, two moons, and two interleaved spirals. For a slower look at the circles, see [k-Means vs. Spectral Clustering on Two Circles](../kmeans-vs-spectral-circles/kmeans-vs-spectral-circles.qmd). ```{python} import warnings import numpy as np import plotly.graph_objects as go from plotly.subplots import make_subplots from sklearn.cluster import KMeans, SpectralClustering from sklearn.datasets import make_circles, make_moons from sklearn.metrics import adjusted_rand_score ``` ## The data {#sec-data} scikit-learn has [`make_circles`](https://scikit-learn.org/stable/modules/generated/sklearn.datasets.make_circles.html) and [`make_moons`](https://scikit-learn.org/stable/modules/generated/sklearn.datasets.make_moons.html) built in. For the spirals, we put points on the curve $t\mapsto(t\cos t,\ t\sin t)$, reflect them through the origin to get the second arm, and add Gaussian noise. Each generator also returns the true group `y` of every point, which we only use for scoring. ```{python} def make_spirals(n_samples=600, noise=0.25, random_state=0): """Two interleaved spiral arms, each about one and a quarter turns long.""" rng = np.random.default_rng(random_state) t_min, t_max = np.pi / 2, np.pi / 2 + 2.5 * np.pi # Taking the square root spreads the points evenly along the arm. t = t_max * np.sqrt(rng.uniform((t_min / t_max) ** 2, 1, n_samples // 2)) arm = np.c_[t * np.cos(t), t * np.sin(t)] X = np.vstack([arm, -arm]) + noise * rng.standard_normal((n_samples, 2)) y = np.repeat([0, 1], n_samples // 2) return X, y datasets = { "circles": make_circles(n_samples=400, factor=0.4, noise=0.05, random_state=0), "moons": make_moons(n_samples=400, noise=0.06, random_state=0), "spirals": make_spirals(n_samples=600, noise=0.25, random_state=0), } ``` ## Fit both methods {#sec-fit} Both methods get the same instructions: find $2$ clusters. For spectral clustering, `affinity="nearest_neighbors"` builds the graph that joins each point to its $10$ nearest neighbours, and one setting works for all three datasets. On the circles that graph has no edges between the two rings, so scikit-learn warns that the graph is not fully connected; here the warning is good news, so we silence it. ```{python} def fit_both(X): kmeans = KMeans(n_clusters=2, n_init=10, random_state=0).fit_predict(X) with warnings.catch_warnings(): warnings.simplefilter("ignore", UserWarning) spectral = SpectralClustering(n_clusters=2, affinity="nearest_neighbors", n_neighbors=10, random_state=0).fit_predict(X) return {"k-means": kmeans, "spectral": spectral} labels = {name: fit_both(X) for name, (X, y) in datasets.items()} for name, (X, y) in datasets.items(): scores = " ".join(f"{method} ARI {round(adjusted_rand_score(y, lab), 2) + 0.0:5.2f}" for method, lab in labels[name].items()) print(f"{name:8} {scores}") ``` The [adjusted Rand index](https://scikit-learn.org/stable/modules/generated/sklearn.metrics.adjusted_rand_score.html) (ARI) is $1$ when the clusters match the true groups exactly and about $0$ for a random labelling. Spectral clustering scores a perfect $1$ on all three. ## The pictures {#sec-pictures} ```{python} #| label: fig-victory-lap #| fig-cap: "k-means (top row) and spectral clustering with a $10$-nearest-neighbour graph (bottom row) on three datasets. Colors are the clusters found. Each panel title gives the adjusted Rand index (ARI) against the true groups." #| fig-alt: "A grid of six scatter plots, three columns for circles, moons, and spirals, and two rows for k-means and spectral clustering. In the top row, k-means splits each dataset with a straight cut, so each color contains pieces of both true groups. In the bottom row, spectral clustering colors the outer and inner rings, the two moons, and the two spiral arms each in a single color." #| code-fold: true #| code-summary: "Plot the grid" INK = "#7c7c78" # muted colors that read in light and dark mode GRID = "rgba(128, 128, 128, 0.28)" COLOR = np.array(["#2a78d6", "#eb6834"]) def align(lab, y): """Rename the two clusters so that cluster g matches true group g as well as possible.""" return lab if np.mean(lab == y) >= 0.5 else 1 - lab methods = ["k-means", "spectral"] names = list(datasets) titles = [f"<b>{method}</b> on {name}: ARI {round(adjusted_rand_score(datasets[name][1], labels[name][method]), 2) + 0.0:.2f}" for method in methods for name in names] fig = make_subplots(rows=2, cols=3, subplot_titles=titles, horizontal_spacing=0.05, vertical_spacing=0.1) for row, method in enumerate(methods, start=1): for col, name in enumerate(names, start=1): X, y = datasets[name] lab = align(labels[name][method], y) fig.add_trace(go.Scatter( x=X[:, 0], y=X[:, 1], mode="markers", showlegend=False, marker=dict(size=6, color=COLOR[lab], line=dict(color="white", width=0.6)), text=[f"cluster {c}, true group {g}" for c, g in zip(lab, y)], hovertemplate="%{text}<extra></extra>"), row=row, col=col) # Same scale on both axes of every panel, so circles look like circles. for i in range(1, 7): suffix = "" if i == 1 else str(i) fig.layout[f"yaxis{suffix}"].scaleanchor = f"x{suffix}" fig.layout[f"xaxis{suffix}"].constrain = "domain" fig.update_xaxes(showticklabels=False, gridcolor=GRID, linecolor=GRID, zerolinecolor=GRID) fig.update_yaxes(showticklabels=False, gridcolor=GRID, linecolor=GRID, zerolinecolor=GRID) fig.update_annotations(font=dict(color=INK, size=13)) fig.update_layout(template="simple_white", paper_bgcolor="rgba(0,0,0,0)", plot_bgcolor="rgba(0,0,0,0)", font=dict(color=INK, size=13), height=700, margin=dict(l=20, r=20, t=50, b=20), hovermode="closest") fig.show() ``` In every top panel, k-means draws one straight cut, and each side of the cut holds pieces of both true groups. In every bottom panel, spectral clustering follows the shape of the data, because points on the same ring, moon, or arm are linked by a chain of near neighbours, and almost no edges cross between groups. The spirals are the most delicate of the three. With $5$ neighbours the graph breaks into $6$ pieces, and spectral clustering separates pieces instead of arms; with $30$ neighbours there are enough edges between the arms that the ARI drops to about $0.2$. As always with spectral clustering, the graph is the real modelling choice (see the notes on [choosing hyperparameters](../../notes/choosing-hyperparameters.qmd)).