Full search page →

PR 07 · Clustering, Mixtures and EM

Pattern RecognitionAdvanced26 minUpdated Nov 5, 2026

Needs: PR 06 · Template Matching and Structured Recognition

Navigate: this page and this track: Navigate: this page and this track
Explore this chapter 1 interactive experiment

Step through Gaussian-mixture EM and observe responsibilities, likelihood and the symmetric-initialization trap.

What you’ll learn

  • What a clustering algorithm actually optimizes, and why the choice of features, scaling and distance decides the answer before any algorithm runs.
  • How Lloyd’s k-means works, why it always converges but only to a local optimum, and how k-means++ seeding gives a provable O(log⁡K)O(\log K) guarantee.
  • How hierarchical clustering (single, complete, average and Ward linkage), DBSCAN and spectral clustering encode different definitions of “a group”.
  • How to derive the E and M steps of expectation–maximization (EM) for a Gaussian mixture from scratch, why EM never decreases the likelihood, and where it can fail.
  • How to choose the number of clusters with BIC and AIC, and how to read internal indices (silhouette, Davies–Bouldin, Calinski–Harabasz), external indices (ARI, NMI) and stability.

The big picture

So far in this track every training example came with a label. Clustering removes the labels and asks: are there natural groups in the data? The answer is never fully determined by the data alone. The same collection of images can be grouped by object, by color, by background or by the camera that took them. Each grouping is “correct” under its own notion of similarity. A clustering algorithm is therefore a precise statement of which notion of similarity we mean, plus a search procedure for the best grouping under that notion.

Why it matters in recognition: clustering builds visual vocabularies (local image descriptors quantized with k-means into “visual words”), initializes and compresses models (vector quantization, color palettes), discovers sub-classes inside a labeled class, finds outliers, segments images (pixel clustering, see IP 10), and, in modern self-supervised learning, produces pseudo-labels for training deep networks. Gaussian mixtures are also the standard example of a latent-variable model, and EM is the template for many inference algorithms we will meet in PR 08.

This chapter follows the clustering part of Theodoridis and Koutroumbas (Chapters 11–16) [1] and Bishop’s Chapter 9 on mixtures and EM [2]. It organizes the main algorithm families, derives the two most important ones in full, and ends with how to decide whether a clustering is any good.

Similarity, scaling and what “a cluster” means

Plain version. Before choosing an algorithm, decide what “close” means. Change the features or their units and the clusters change.

Precise version. Most methods start from a dissimilarity d(x,x′)d(x, x') between feature vectors x,x′∈RDx, x' \in \mathbb R^D. Common choices are

d2(x,x′)=∥x−x′∥2,dM(x,x′)=(x−x′)⊤S−1(x−x′),dcos⁡(x,x′)=1−x⊤x′∥x∥ ∥x′∥,d_2(x,x')=\|x-x'\|_2,\qquad d_M(x,x')=\sqrt{(x-x')^\top S^{-1}(x-x')},\qquad d_{\cos}(x,x')=1-\frac{x^\top x'}{\|x\|\,\|x'\|},

where d2d_2 is the Euclidean distance, dMd_M is the Mahalanobis distance with a positive-definite matrix SS (often a covariance estimate), and dcos⁡d_{\cos} is the cosine dissimilarity, which ignores vector length and is popular for deep-network embeddings.

Three practical consequences follow.

  1. Scaling is a modeling decision. If one coordinate is measured in millimeters and another in kilometers, Euclidean distance is dominated by the first. Standardizing every feature to unit variance removes that, but it also removes any genuinely meaningful difference in spread. For classification we can let validation decide; for clustering there are no labels, so the choice must come from domain knowledge.
  2. Hard versus soft assignments. A hard partition assigns each point xnx_n to exactly one cluster zn∈{1,…,K}z_n \in \{1,\dots,K\}. A soft assignment stores degrees of membership rnk≥0r_{nk} \ge 0 with ∑krnk=1\sum_k r_{nk} = 1. In a Gaussian mixture these are posterior probabilities; in fuzzy clustering [1] they are memberships defined by an objective and should not be read as probabilities.
  3. Clusters are not classes. Labels are attached to clusters afterwards and arbitrarily. Cluster “3” in one run may be cluster “1” in the next, so any comparison with class labels must be invariant to permutations, which is exactly what ARI and NMI (below) are.

Theodoridis and Koutroumbas classify algorithms into sequential, hierarchical, objective-function-based (k-means, mixtures, fuzzy), and graph/density-based families [1]. We follow roughly that order.

K-means and Lloyd’s algorithm

Plain version. Choose KK centers. Repeat two steps: give every point to its nearest center, then move every center to the average of its points. Stop when nothing changes.

The objective

With one-hot indicators znk∈{0,1}z_{nk}\in\{0,1\} (znk=1z_{nk}=1 if point nn is in cluster kk, and ∑kznk=1\sum_k z_{nk}=1) and centers μ1,…,μK∈RD\mu_1,\dots,\mu_K\in\mathbb R^D, k-means minimizes the within-cluster sum of squares

J(z,μ)=∑n=1N∑k=1Kznk ∥xn−μk∥2.J(z,\mu)=\sum_{n=1}^{N}\sum_{k=1}^{K} z_{nk}\,\|x_n-\mu_k\|^2 .

Here NN is the number of points and DD their dimension. JJ is also called inertia or distortion.

Two alternating steps

Lloyd’s algorithm [3] (developed for quantizing signals in pulse-code modulation) minimizes JJ by block coordinate descent:

  • Assignment step. Fix μ\mu. Each term involves a single znz_n, so set znk=1z_{nk}=1 for k=arg⁡min⁡j∥xn−μj∥2k=\arg\min_j\|x_n-\mu_j\|^2.
  • Update step. Fix zz. JJ is a convex quadratic in each μk\mu_k; setting the gradient to zero,
∂J∂μk=−2∑nznk(xn−μk)=0⟹μk=∑nznkxn∑nznk,\frac{\partial J}{\partial\mu_k}=-2\sum_n z_{nk}(x_n-\mu_k)=0 \quad\Longrightarrow\quad \mu_k=\frac{\sum_n z_{nk}x_n}{\sum_n z_{nk}} ,

the mean of the points currently in cluster kk. The name “k-means” was coined by MacQueen [4], whose version updates a center immediately after each point arrives, μk←μk+(xn−μk)/Nk\mu_k\leftarrow\mu_k+(x_n-\mu_k)/N_k, where NkN_k is the running count of points in cluster kk.

Why it converges, and why only locally

Each step can only lower JJ or leave it unchanged: the assignment step picks the best zz for the current μ\mu, and the update step picks the best μ\mu for the current zz. There are finitely many partitions of NN points into KK groups, and (with a consistent tie-breaking rule) the algorithm never revisits a partition with a higher JJ, so it stops after finitely many iterations. The fixed point is a local minimum: a partition where no single step helps. Different initial centers can lead to very different fixed points.

Two implementation details matter. An empty cluster (no point assigned) has no mean; common rules keep the old center or re-seed it at the point with the largest current error. And every iteration costs O(NKD)O(NKD) distance computations, which motivates the mini-batch variant below.

What k-means assumes

Because the objective is a sum of squared Euclidean distances to a center, the boundary between two clusters is the perpendicular bisector of their centers: k-means partitions space into Voronoi cells. It works well for compact, roughly spherical groups of similar size. It splits elongated groups, merges small groups that are close to large ones, and cannot follow curved shapes (Figure 1, middle).

The same synthetic two-moon observations grouped by generating labels, k-means and DBSCAN.
Figure 1 — The same two-moons data grouped by the generating labels (left), k-means (middle) and DBSCAN (right). K-means and DBSCAN fit without labels. Colors are arbitrary cluster identifiers.

k-means++ seeding

Plain version. Start with one random center, then pick each new center far from the ones you already have, but randomly, so outliers do not always win.

Arthur and Vassilvitskii [5] proposed D² seeding:

  1. Pick the first center uniformly at random from the data.
  2. For every point compute D(xn)D(x_n), the distance to the nearest center chosen so far.
  3. Pick the next center as xnx_n with probability D(xn)2/∑mD(xm)2D(x_n)^2/\sum_m D(x_m)^2.
  4. Repeat steps 2–3 until KK centers are chosen, then run Lloyd’s algorithm.

Their main theorem states that the seeding alone already achieves, in expectation,

E[J]≤8(ln⁡K+2) JOPT,\mathbb E[J]\le 8(\ln K+2)\,J_{\mathrm{OPT}},

where JOPTJ_{\mathrm{OPT}} is the optimal k-means objective. Lloyd iterations can only lower JJ further. Uniform random seeding has no such guarantee. The bound is a worst-case statement; in practice the benefit shows up mostly as fewer catastrophic runs. Libraries combine k-means++ with several restarts (n_init in scikit-learn) and keep the run with the lowest JJ.

Code: k-means++ and Lloyd from scratch

Code · Python · 46 lines
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans

def kmeans_pp_init(X, k, rng):
    """D^2 seeding: each new center is drawn with probability proportional
    to the squared distance to the nearest center chosen so far."""
    centers = [X[rng.integers(len(X))]]
    for _ in range(k - 1):
        d2 = np.min(((X[:, None, :] - np.array(centers)[None]) ** 2).sum(-1), axis=1)
        centers.append(X[rng.choice(len(X), p=d2 / d2.sum())])
    return np.array(centers)

def lloyd(X, centers, max_iter=100):
    history = []
    for _ in range(max_iter):
        d2 = ((X[:, None, :] - centers[None]) ** 2).sum(-1)   # N x K
        z = d2.argmin(axis=1)                                 # assignment step
        history.append(d2[np.arange(len(X)), z].sum())        # objective J
        new = np.array([X[z == k].mean(axis=0) if np.any(z == k) else centers[k]
                        for k in range(len(centers))])        # update step
        if np.allclose(new, centers):
            break
        centers = new
    return centers, z, history

X, _ = make_blobs(n_samples=600, centers=4, cluster_std=1.8, random_state=7)
rng = np.random.default_rng(0)
best = None
for restart in range(10):                      # several seeds, keep the best J
    c, z, hist = lloyd(X, kmeans_pp_init(X, 4, rng))
    if best is None or hist[-1] < best[2][-1]:
        best = (c, z, hist)
c, z, hist = best
print("J per iteration:", np.round(hist, 1))
assert all(a >= b - 1e-9 for a, b in zip(hist, hist[1:]))   # monotone
ref = KMeans(n_clusters=4, n_init=10, random_state=0).fit(X)
print("from scratch J:", round(hist[-1], 2), " sklearn inertia:", round(ref.inertia_, 2))

# single runs (no restarts): uniform random seeding vs D^2 seeding, 15 clusters
X2, _ = make_blobs(n_samples=1500, centers=15, cluster_std=0.6, random_state=2)
for name, init in [("random", lambda r: X2[r.choice(len(X2), 15, replace=False)]),
                   ("k-means++", lambda r: kmeans_pp_init(X2, 15, r))]:
    finals = [lloyd(X2, init(np.random.default_rng(s)))[2][-1] for s in range(20)]
    print(f"{name:9s} final J over 20 runs: median {np.median(finals):7.1f}, "
          f"worst {np.max(finals):7.1f}")

Output (NumPy 2.0, scikit-learn 1.6):

Code · 4 lines
J per iteration: [5865.6 3633.4 3625. ]
from scratch J: 3625.0  sklearn inertia: 3625.0
random    final J over 20 runs: median  1305.1, worst  4750.8
k-means++ final J over 20 runs: median  1147.5, worst  1525.2

The from-scratch version reaches the same objective as scikit-learn, and JJ decreases monotonically. On the 15-cluster problem, uniform seeding sometimes puts two seeds in one blob and none in another; Lloyd’s algorithm cannot repair that, and the worst run is about three times worse. Figure 2 shows the two worst runs.

Left: a k-means result from random seeding where several centers crowd into a few blobs while one center sits between two far blobs. Middle: the worst k-means++ result, where a few nearby blobs are merged or split. Right: box plots of the final objective over 20 runs for each seeding.
Figure 2 — Seeding matters. Fifteen synthetic blobs, 20 single Lloyd runs per seeding rule (no restarts). Random seeding leaves some runs stuck with merged and split blobs; D² (k-means++) seeding gives lower and less variable objectives. Black crosses are final centers.

Mini-batch k-means

For millions of points, Sculley’s mini-batch k-means [6] updates the centers using small random batches: each center moves toward the batch points assigned to it with a per-center learning rate that decays as 1/(count of points seen)1/(\text{count of points seen}). It trades a slightly higher final objective for a large speed-up, and is available as MiniBatchKMeans in scikit-learn. It is the usual choice for building large visual vocabularies.

Hierarchical clustering

Plain version. Start with every point as its own group. Repeatedly merge the two closest groups. The record of merges is a tree; cut it at some height to get clusters.

Agglomerative algorithm and linkages

Agglomerative clustering needs a definition of the distance between two groups AA and BB. The four classical linkages are

dsingle(A,B)=min⁡a∈A, b∈Bd(a,b),dcomplete(A,B)=max⁡a∈A, b∈Bd(a,b),daverage(A,B)=1∣A∣ ∣B∣∑a∈A∑b∈Bd(a,b),ΔWard(A,B)=∣A∣ ∣B∣∣A∣+∣B∣ ∥aˉ−bˉ∥2,\begin{aligned} d_{\text{single}}(A,B)&=\min_{a\in A,\,b\in B} d(a,b),\\ d_{\text{complete}}(A,B)&=\max_{a\in A,\,b\in B} d(a,b),\\ d_{\text{average}}(A,B)&=\frac{1}{|A|\,|B|}\sum_{a\in A}\sum_{b\in B} d(a,b),\\ \Delta_{\text{Ward}}(A,B)&=\frac{|A|\,|B|}{|A|+|B|}\,\|\bar a-\bar b\|^2 , \end{aligned}

where ∣A∣|A| is the number of points in AA and aˉ,bˉ\bar a,\bar b are the group means. Ward’s criterion [7] is the increase of the within-cluster sum of squares JJ caused by merging AA and BB, so Ward agglomeration is a greedy, bottom-up way of keeping JJ small, the same objective as k-means.

Each linkage has a personality (Figure 3):

  • Single linkage merges whenever any two points are close. It follows arbitrary shapes, but a thin “bridge” of points can chain two groups together. It is equivalent to cutting the longest edges of a minimum spanning tree, one of the graph-based methods in [1].
  • Complete linkage requires all pairs to be close. It produces compact groups of similar diameter and is sensitive to outliers.
  • Average linkage sits between the two.
  • Ward produces compact, similarly sized, roughly spherical groups, much like k-means.
Three scatter plots of the same data (two blobs joined by a thin bridge, plus an elongated group above) clustered by single, complete and Ward linkage, and a Ward dendrogram with a dashed cut line.
Figure 3 — One data set, three linkages. Single linkage chains along the thin bridge, merges both blobs into one cluster and spends a cluster on four stray points; complete and Ward linkage keep the two blobs apart and split the bridge between them. Bottom right: the Ward dendrogram, where cutting at the dashed line yields three clusters.

The dendrogram

The merge history is a binary tree called a dendrogram; the height of each junction is the linkage value at which the merge happened. Cutting the tree at height hh yields the partition at that level, and a large gap between consecutive merge heights suggests a natural number of clusters. The cut height is still a choice.

Two practical limitations: merges are never undone, so an early mistake propagates; and the standard algorithm stores all pairwise distances, O(N2)O(N^2) memory, which limits it to tens of thousands of points. Divisive (top-down) hierarchical methods exist but are less common.

Density-based clustering: DBSCAN

Plain version. A cluster is a crowded region. Points in crowded places grow the cluster; points in empty places are labeled noise.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) [8] has two parameters, a radius ε\varepsilon and a count MinPts\text{MinPts}. Let Nε(x)={x′:d(x,x′)≤ε}N_\varepsilon(x)=\{x' : d(x,x')\le\varepsilon\} be the ε\varepsilon-neighborhood of xx (including xx itself). Then

  • xx is a core point if ∣Nε(x)∣≥MinPts|N_\varepsilon(x)|\ge\text{MinPts};
  • xx is a border point if it is not core but lies in the ε\varepsilon-neighborhood of some core point;
  • every other point is noise.

A point is density-reachable from a core point if there is a chain of core points, each within ε\varepsilon of the next, ending in its neighborhood. A cluster is a maximal set of mutually density-connected points. DBSCAN finds clusters of any shape, does not need KK, and explicitly refuses to assign isolated points.

Choosing ε\varepsilon. The original paper suggests the sorted k-distance graph: for each point compute the distance to its kk-th nearest neighbor with k=MinPtsk=\text{MinPts}, sort these values, and pick ε\varepsilon near the “knee” where the curve rises sharply (Figure 4, left). In the descending plot of Figure 4 the large values to the left of the knee are the candidates for noise. scikit-learn’s min_samples counts the point itself, which matches the definition above.

Left: sorted k-distance curve with a horizontal dashed line at eps 0.18 just above the knee. Right: two moons clustered by DBSCAN, with filled core points, hollow border points and gray crosses for noise.
Figure 4 — DBSCAN on two moons plus 25 uniform outliers. Left: the sorted 5-distance curve; the chosen ε = 0.18 sits where the curve starts to rise. Right: core points (filled), border points (hollow) and points rejected as noise (crosses).

Limitations. A single ε\varepsilon means a single density level. If one cluster is dense and another sparse, no ε\varepsilon separates both. In high dimensions, distances concentrate and the neighborhood counts lose contrast. HDBSCAN [9] addresses the first issue by building a hierarchy over all density levels and extracting the most stable clusters, replacing ε\varepsilon with a minimum cluster size; it is available as HDBSCAN in scikit-learn.

Spectral clustering in one page

Plain version. Build a graph that connects nearby points, then find the cuts that sever the fewest strong connections.

Given an affinity matrix WW (Wij≥0W_{ij}\ge 0, large for similar points, for example a kk-nearest-neighbor graph or Wij=exp⁡(−∥xi−xj∥2/2σ2)W_{ij}=\exp(-\|x_i-x_j\|^2/2\sigma^2)) and the diagonal degree matrix Dii=∑jWijD_{ii}=\sum_j W_{ij}, one normalized graph Laplacian is

Lsym=I−D−1/2WD−1/2.L_{\mathrm{sym}}=I-D^{-1/2}WD^{-1/2}.

If the graph has KK connected components, LsymL_{\mathrm{sym}} has eigenvalue 00 with multiplicity KK, and its eigenvectors indicate the components. For a nearly disconnected graph, the KK eigenvectors with the smallest eigenvalues still nearly indicate the groups. Spectral clustering stacks these eigenvectors as columns, normalizes the rows, and runs k-means on the rows [10]. The result can follow curved shapes that defeat k-means in the original space, because the eigenvectors measure connectivity, not distance to a center.

The graph is part of the model. The neighborhood size or bandwidth σ\sigma must be chosen; a graph that is accidentally disconnected (an isolated vertex, say) produces a trivial eigenvector that dominates the result. Von Luxburg’s tutorial [10] explains the graph-cut interpretation (ratio cut and normalized cut) and gives practical advice on choosing the graph.

Code: one geometry, different assumptions

The two-moons data set below is generated with labels, but the labels are used only to score each result afterwards with the adjusted Rand index (ARI, 1 = perfect agreement up to relabeling, about 0 = chance).

Code · Python · 30 lines
import numpy as np
from sklearn.datasets import make_moons
from sklearn.neighbors import NearestNeighbors
from sklearn.cluster import (KMeans, AgglomerativeClustering, DBSCAN,
                             HDBSCAN, SpectralClustering)
from sklearn.mixture import GaussianMixture
from sklearn.metrics import adjusted_rand_score

X, truth = make_moons(n_samples=320, noise=0.06, random_state=5)

# k-distance curve for choosing DBSCAN's eps (k = min_samples)
dist, _ = NearestNeighbors(n_neighbors=5).fit(X).kneighbors(X)
kdist = np.sort(dist[:, -1])                    # 5th neighbour, counting the point itself
print("k-distance quantiles 50/90/99%:", np.round(np.quantile(kdist, [0.5, 0.9, 0.99]), 3))

models = {
    "k-means": KMeans(n_clusters=2, n_init=10, random_state=5),
    "single linkage": AgglomerativeClustering(n_clusters=2, linkage="single"),
    "Ward linkage": AgglomerativeClustering(n_clusters=2, linkage="ward"),
    "Gaussian mixture": GaussianMixture(n_components=2, n_init=3, random_state=5),
    "DBSCAN": DBSCAN(eps=0.18, min_samples=5),
    "HDBSCAN": HDBSCAN(min_cluster_size=15),
    "spectral": SpectralClustering(n_clusters=2, affinity="nearest_neighbors",
                                   n_neighbors=20, assign_labels="kmeans",
                                   random_state=5),
}
for name, model in models.items():
    labels = model.fit_predict(X)
    print(f"{name:17s} ARI = {adjusted_rand_score(truth, labels):.3f}"
          f"   noise points = {int((labels == -1).sum())}")

Output

k-distance quantiles 50/90/99%: [0.079 0.11  0.144]
k-means           ARI = 0.260   noise points = 0
single linkage    ARI = 1.000   noise points = 0
Ward linkage      ARI = 0.242   noise points = 0
Gaussian mixture  ARI = 0.488   noise points = 0
DBSCAN            ARI = 1.000   noise points = 0
HDBSCAN           ARI = 0.988   noise points = 2
spectral          ARI = 1.000   noise points = 0

Figure 1 shows two of these results. Methods built on centers or ellipses (k-means, Ward, a two-component Gaussian mixture) cut each moon in half; connectivity-based methods (single linkage, DBSCAN, HDBSCAN, spectral) recover the moons. The chosen ε=0.18\varepsilon=0.18 lies above the 99th percentile of the k-distance, so no moon point is called noise. A kk-nearest-neighbor graph with too few neighbors can be disconnected, and scikit-learn then warns that the spectral embedding may be unreliable; 2020 neighbors avoids that here. None of this makes connectivity methods “better”: on overlapping Gaussian blobs single linkage chains everything together and k-means wins. Comparisons must vary geometry, density, noise and dimension.

Gaussian mixtures and the EM algorithm

Plain version. Pretend every point was produced by first rolling a KK-sided die to pick a cloud, then sampling from that Gaussian cloud. We never see the die. EM guesses, for every point, how likely each cloud produced it (E step), then refits each cloud using those guesses as weights (M step), and repeats.

The model

A Gaussian mixture model (GMM) with KK components has density

p(x∣θ)=∑k=1Kπk N(x∣μk,Σk),πk≥0,∑k=1Kπk=1,p(x\mid\theta)=\sum_{k=1}^{K}\pi_k\,\mathcal N(x\mid\mu_k,\Sigma_k), \qquad \pi_k\ge 0,\quad \sum_{k=1}^{K}\pi_k=1,

where πk\pi_k is the mixing weight (prior probability of component kk), μk∈RD\mu_k\in\mathbb R^D its mean, Σk\Sigma_k its D×DD\times D covariance, θ={πk,μk,Σk}k=1K\theta=\{\pi_k,\mu_k,\Sigma_k\}_{k=1}^K collects all parameters, and

N(x∣μ,Σ)=1(2π)D/2∣Σ∣1/2exp⁡ ⁣(−12(x−μ)⊤Σ−1(x−μ)).\mathcal N(x\mid\mu,\Sigma)=\frac{1}{(2\pi)^{D/2}|\Sigma|^{1/2}} \exp\!\Big(-\tfrac12(x-\mu)^\top\Sigma^{-1}(x-\mu)\Big).

Introduce a latent one-hot variable znz_n with p(znk=1)=πkp(z_{nk}=1)=\pi_k and p(xn∣znk=1)=N(xn∣μk,Σk)p(x_n\mid z_{nk}=1)=\mathcal N(x_n\mid\mu_k,\Sigma_k). Summing out znz_n gives back the mixture density. Given data X={x1,…,xN}X=\{x_1,\dots,x_N\}, the log-likelihood is

ln⁡p(X∣θ)=∑n=1Nln⁡∑k=1Kπk N(xn∣μk,Σk).\ln p(X\mid\theta)=\sum_{n=1}^{N}\ln\sum_{k=1}^{K}\pi_k\,\mathcal N(x_n\mid\mu_k,\Sigma_k).

The logarithm of a sum couples all the parameters, so setting its gradient to zero has no closed-form solution. EM is the standard way around this [11], [2].

Step 1: the complete-data log-likelihood

If we knew the assignments Z={zn}Z=\{z_n\}, the log-likelihood of (X,Z)(X,Z) would be

ln⁡p(X,Z∣θ)=∑n=1N∑k=1Kznk[ln⁡πk+ln⁡N(xn∣μk,Σk)].\ln p(X,Z\mid\theta)=\sum_{n=1}^{N}\sum_{k=1}^{K} z_{nk}\Big[\ln\pi_k+\ln\mathcal N(x_n\mid\mu_k,\Sigma_k)\Big].

The logarithm now acts on a single Gaussian, and the problem splits into KK separate weighted Gaussian fits: easy.

Step 2 (E step): the expected complete-data log-likelihood

We do not know ZZ, but with current parameters θold\theta^{\text{old}} we know its posterior. By Bayes’ rule,

rnk≡p(znk=1∣xn,θold)=πk N(xn∣μk,Σk)∑j=1Kπj N(xn∣μj,Σj),r_{nk}\equiv p(z_{nk}=1\mid x_n,\theta^{\text{old}}) =\frac{\pi_k\,\mathcal N(x_n\mid\mu_k,\Sigma_k)}{\sum_{j=1}^{K}\pi_j\,\mathcal N(x_n\mid\mu_j,\Sigma_j)},

evaluated at θold\theta^{\text{old}}. The number rnkr_{nk} is the responsibility of component kk for point nn; each row sums to one. Because the complete-data log-likelihood is linear in znkz_{nk}, its expectation under this posterior simply replaces znkz_{nk} by rnkr_{nk}:

Q(θ,θold)=∑n∑krnk[ln⁡πk−D2ln⁡2π−12ln⁡∣Σk∣−12(xn−μk)⊤Σk−1(xn−μk)].Q(\theta,\theta^{\text{old}})=\sum_{n}\sum_{k} r_{nk}\Big[\ln\pi_k-\tfrac{D}{2}\ln 2\pi-\tfrac12\ln|\Sigma_k|-\tfrac12(x_n-\mu_k)^\top\Sigma_k^{-1}(x_n-\mu_k)\Big].

Step 3 (M step): maximize QQ in closed form

Define the effective count Nk=∑nrnkN_k=\sum_n r_{nk}.

Mixing weights. Only ∑n∑krnkln⁡πk\sum_n\sum_k r_{nk}\ln\pi_k depends on π\pi, under the constraint ∑kπk=1\sum_k\pi_k=1. With a Lagrange multiplier λ\lambda,

∂∂πk[∑n,krnkln⁡πk+λ(∑kπk−1)]=Nkπk+λ=0  ⇒  πk=−Nkλ.\frac{\partial}{\partial\pi_k}\Big[\sum_{n,k} r_{nk}\ln\pi_k+\lambda\Big(\sum_k\pi_k-1\Big)\Big] =\frac{N_k}{\pi_k}+\lambda=0 \;\Rightarrow\;\pi_k=-\frac{N_k}{\lambda}.

Summing over kk gives λ=−N\lambda=-N, so πk=Nk/N\pi_k=N_k/N. (The constraint πk≥0\pi_k\ge0 is satisfied automatically.)

Means. The gradient with respect to μk\mu_k is ∑nrnkΣk−1(xn−μk)\sum_n r_{nk}\Sigma_k^{-1}(x_n-\mu_k). Setting it to zero and multiplying by Σk\Sigma_k,

μk=1Nk∑nrnk xn.\mu_k=\frac{1}{N_k}\sum_{n} r_{nk}\,x_n .

Covariances. Write Λk=Σk−1\Lambda_k=\Sigma_k^{-1}, so −12ln⁡∣Σk∣=12ln⁡∣Λk∣-\tfrac12\ln|\Sigma_k|=\tfrac12\ln|\Lambda_k| and the quadratic term is −12tr⁡(Λk(xn−μk)(xn−μk)⊤)-\tfrac12\operatorname{tr}\big(\Lambda_k(x_n-\mu_k)(x_n-\mu_k)^\top\big). Using ∂ln⁡∣Λ∣/∂Λ=Λ−1\partial\ln|\Lambda|/\partial\Lambda=\Lambda^{-1} and ∂tr⁡(ΛA)/∂Λ=A⊤\partial\operatorname{tr}(\Lambda A)/\partial\Lambda=A^\top for symmetric AA,

∂Q∂Λk=12∑nrnk[Σk−(xn−μk)(xn−μk)⊤]=0  ⇒  Σk=1Nk∑nrnk(xn−μk)(xn−μk)⊤.\frac{\partial Q}{\partial\Lambda_k}=\frac12\sum_n r_{nk}\Big[\Sigma_k-(x_n-\mu_k)(x_n-\mu_k)^\top\Big]=0 \;\Rightarrow\; \Sigma_k=\frac{1}{N_k}\sum_n r_{nk}(x_n-\mu_k)(x_n-\mu_k)^\top .

These are the familiar maximum-likelihood formulas for one Gaussian (see PR 02), with every point weighted by its responsibility. EM alternates the E step and the M step until the log-likelihood stops improving (Figure 5).

Five scatter plots of the same three-cluster data with one- and two-sigma ellipses of the three fitted Gaussian components at EM iterations 0, 2, 6, 12 and at convergence, with point colors blended by responsibility, plus a curve of mean log-likelihood rising and flattening.
Figure 5 — EM for a three-component Gaussian mixture. The components start at random data points with the overall covariance; point colors mix the component colors by responsibility. Right: the mean log-likelihood never decreases.

Why EM never decreases the likelihood

For any distribution q(Z)q(Z) over the latent assignments,

ln⁡p(X∣θ)=∑Zq(Z)ln⁡p(X,Z∣θ)q(Z)⏟L(q,θ)+∑Zq(Z)ln⁡q(Z)p(Z∣X,θ)⏟KL(q ∥ p(Z∣X,θ))  ≥  0.\ln p(X\mid\theta)=\underbrace{\sum_Z q(Z)\ln\frac{p(X,Z\mid\theta)}{q(Z)}}_{\mathcal L(q,\theta)} +\underbrace{\sum_Z q(Z)\ln\frac{q(Z)}{p(Z\mid X,\theta)}}_{\mathrm{KL}(q\,\|\,p(Z\mid X,\theta))\;\ge\;0}.

So L(q,θ)\mathcal L(q,\theta) is a lower bound on the log-likelihood, the evidence lower bound (ELBO). The E step sets q(Z)=p(Z∣X,θold)q(Z)=p(Z\mid X,\theta^{\text{old}}), which makes the KL term zero and the bound tight at θold\theta^{\text{old}}. The M step maximizes L\mathcal L over θ\theta; since L(q,θ)=Q(θ,θold)+const\mathcal L(q,\theta)=Q(\theta,\theta^{\text{old}})+\text{const}, this is the same as maximizing QQ. The new likelihood is at least the new bound, which is at least the old bound, which equals the old likelihood. Hence ln⁡p(X∣θnew)≥ln⁡p(X∣θold)\ln p(X\mid\theta^{\text{new}})\ge\ln p(X\mid\theta^{\text{old}}) [11], [2]. When the exact posterior is intractable, we restrict qq to a tractable family and get variational inference, the subject of PR 08.

Monotone does not mean globally optimal or safely convergent: under suitable regularity conditions EM can approach a stationary point, while an unconstrained Gaussian mixture can instead head toward the singularity described next. Practical implementations initialize from k-means and run several restarts.

Singularities and how to avoid them

The likelihood of an unconstrained GMM is unbounded. Put one component’s mean exactly on a data point, μj=xn\mu_j=x_n, with Σj=σ2I\Sigma_j=\sigma^2 I. That term contributes πj(2πσ2)−D/2\pi_j(2\pi\sigma^2)^{-D/2} to p(xn)p(x_n), which goes to infinity as σ→0\sigma\to0, while the other components keep the remaining points’ likelihood finite. The unrestricted maximum likelihood estimate therefore need not exist, and EM itself does not prevent collapse. Use a positive covariance floor (reg_covar in scikit-learn [26]), explicit variance constraints, or an appropriate prior. Diagonal or spherical covariance alone is not a cure: the collapsing covariance σ2I\sigma^2 I already has both forms. A simpler covariance reduces parameter count; it still needs protection against zero variance. Restarting a component is an operational response, not a proof that the unconstrained objective is bounded.

Identifiability and label switching

Permuting the component labels leaves the density unchanged, so there are K!K! equivalent maxima. “Component 2” has no inherent meaning, and comparing component indices with class labels requires a matching rule.

K-means as the limit of EM

Fix πk=1/K\pi_k=1/K and Σk=ϵI\Sigma_k=\epsilon I for all kk. The responsibilities become

rnk=exp⁡(−∥xn−μk∥2/2ϵ)∑jexp⁡(−∥xn−μj∥2/2ϵ).r_{nk}=\frac{\exp(-\|x_n-\mu_k\|^2/2\epsilon)}{\sum_j\exp(-\|x_n-\mu_j\|^2/2\epsilon)} .

As ϵ→0\epsilon\to0, the term with the smallest distance dominates, so rnk→1r_{nk}\to1 for the nearest center and 00 otherwise: the E step becomes the k-means assignment step and the M step for μk\mu_k becomes the k-means update [2]. A general GMM therefore extends k-means with soft assignments, unequal sizes (πk\pi_k) and elliptical shapes (Σk\Sigma_k).

Code: EM from scratch, checked against scikit-learn

Code · Python · 45 lines
import numpy as np
from scipy.special import logsumexp
from scipy.stats import multivariate_normal
from sklearn.mixture import GaussianMixture

rng = np.random.default_rng(3)
true_means = np.array([[0.0, 0.0], [4.0, 1.0], [1.0, 4.0]])
true_covs = [np.array([[1.0, 0.6], [0.6, 0.8]]),
             np.array([[0.5, -0.2], [-0.2, 1.2]]),
             np.array([[0.7, 0.0], [0.0, 0.3]])]
counts = [250, 150, 100]
X = np.vstack([rng.multivariate_normal(m, S, n)
               for m, S, n in zip(true_means, true_covs, counts)])
N, D = X.shape
K, reg = 3, 1e-6                               # reg: small covariance floor

# initialise with K random points, shared data covariance, equal weights
mu = X[rng.choice(N, K, replace=False)]
Sigma = np.array([np.cov(X.T) for _ in range(K)])
pi = np.full(K, 1.0 / K)
loglik = []
for it in range(200):
    # E step: log of pi_k N(x_n | mu_k, Sigma_k), normalised with log-sum-exp
    log_joint = np.column_stack([np.log(pi[k]) +
                                 multivariate_normal(mu[k], Sigma[k]).logpdf(X)
                                 for k in range(K)])
    log_norm = logsumexp(log_joint, axis=1)
    R = np.exp(log_joint - log_norm[:, None])     # responsibilities r_nk
    loglik.append(log_norm.sum())
    # M step: closed-form weighted updates
    Nk = R.sum(axis=0)
    pi = Nk / N
    mu = (R.T @ X) / Nk[:, None]
    for k in range(K):
        diff = X - mu[k]
        Sigma[k] = (R[:, k, None] * diff).T @ diff / Nk[k] + reg * np.eye(D)
    if it > 0 and loglik[-1] - loglik[-2] < 1e-8:
        break

assert np.all(np.diff(loglik) > -1e-6)           # EM never decreases log-likelihood
print("iterations:", len(loglik), " final mean log-lik:", round(loglik[-1] / N, 4))
print("weights:", np.round(np.sort(pi), 3))
gm = GaussianMixture(3, covariance_type="full", n_init=5, random_state=0).fit(X)
print("sklearn mean log-lik:", round(gm.score(X), 4))
print("sklearn weights:", np.round(np.sort(gm.weights_), 3))

Output

iterations: 40  final mean log-lik: -3.4032
weights: [0.202 0.299 0.499]
sklearn mean log-lik: -3.4033
sklearn weights: [0.203 0.3   0.497]

The E step works in log space: densities in high dimension underflow, and logsumexp computes ln⁡∑keak\ln\sum_k e^{a_k} stably. The recovered weights match the generating proportions 0.5,0.3,0.20.5, 0.3, 0.2 and scikit-learn’s solution; the tiny difference comes from scikit-learn’s own stopping tolerance.

Choosing the number of clusters

Plain version. More clusters always fit the training data better. A model-selection criterion charges a price for every extra parameter, and the best KK balances fit against that price.

BIC and AIC for mixtures

For a model with maximized likelihood L^\hat L, pp free parameters and NN data points,

BIC=−2ln⁡L^+pln⁡N,AIC=−2ln⁡L^+2p,\mathrm{BIC}=-2\ln\hat L+p\ln N,\qquad \mathrm{AIC}=-2\ln\hat L+2p ,

and smaller is better. The Bayesian information criterion (BIC) [12] comes from a large-sample approximation of the log marginal likelihood (model evidence, see PR 08); Akaike’s information criterion (AIC) [13] estimates expected predictive log-loss. Because ln⁡N>2\ln N>2 once N≥8N\ge 8, BIC penalizes complexity more and tends to choose fewer components.

For a full-covariance GMM in DD dimensions,

p=(K−1)⏟weights+KD⏟means+K D(D+1)2⏟covariances.p=\underbrace{(K-1)}_{\text{weights}}+\underbrace{KD}_{\text{means}}+\underbrace{K\,\tfrac{D(D+1)}{2}}_{\text{covariances}} .

The covariances dominate in high dimension: with D=128D=128 (a SIFT-like descriptor) each full covariance has 8,2568{,}256 free numbers, which is why diagonal covariances are standard for large descriptors. The covariance type is therefore part of model selection too.

Code · Python · 20 lines
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.mixture import GaussianMixture

X, _ = make_blobs(n_samples=600, centers=4, cluster_std=1.0, random_state=7)
X = X @ np.array([[1.0, 0.0], [0.6, 0.5]])        # shear: make clusters elliptical
results = []
for cov in ["spherical", "diag", "full"]:
    for K in range(1, 9):
        gm = GaussianMixture(K, covariance_type=cov, n_init=3, random_state=0).fit(X)
        results.append((gm.bic(X), gm.aic(X), cov, K))
for bic, aic, cov, K in sorted(results)[:5]:
    print(f"BIC={bic:8.1f}  AIC={aic:8.1f}  {cov:9s} K={K}")

# check the parameter count used by BIC for a full-covariance model
gm = GaussianMixture(4, covariance_type="full", random_state=0).fit(X)
D, K = X.shape[1], 4
p = (K - 1) + K * D + K * D * (D + 1) // 2
manual = -2 * gm.score(X) * len(X) + p * np.log(len(X))
print("free parameters:", p, " manual BIC:", round(manual, 1), " sklearn:", round(gm.bic(X), 1))

Output

BIC=  4301.1  AIC=  4200.0  full      K=4
BIC=  4320.7  AIC=  4193.2  full      K=5
BIC=  4357.6  AIC=  4203.7  full      K=6
BIC=  4388.4  AIC=  4208.2  full      K=7
BIC=  4414.9  AIC=  4243.4  diag      K=8
free parameters: 23  manual BIC: 4301.1  sklearn: 4301.1

BIC picks the true K=4K=4 with full covariances (the shear made the clusters elliptical, so spherical and diagonal models need extra components). AIC slightly prefers K=5K=5: its lighter penalty lets a fifth component buy a small likelihood gain. Neither criterion is “right” in general; both assume the model family is adequate, and for non-Gaussian clusters BIC will happily use several Gaussians to describe one curved group. If the goal is density estimation, that is fine; if each component is supposed to be one semantic group, it is not.

Other heuristics

The elbow method plots k-means JJ against KK and looks for a bend; JJ always decreases, so the bend is subjective. The silhouette and stability approaches in the next section give alternatives. A Bayesian treatment can also start with more components than needed and let a prior on the mixing weights switch the unnecessary ones off; Bishop works through this for a variational Gaussian mixture [2].

Left: BIC versus K for spherical, diagonal and full covariance mixtures, with the full curve lowest at K equal to 4. Middle: silhouette peaking and Davies-Bouldin reaching its minimum at K equal to 4. Right: bootstrap stability at 1.0 for K equal to 3 and 4 then dropping.
Figure 6 — Three ways to choose K on synthetic four-blob data. Left: BIC (sheared data). Middle: silhouette (higher is better) and Davies–Bouldin (lower is better) for k-means. Right: bootstrap stability is perfect for both K = 3 and K = 4, so stability alone cannot decide.

Cluster validity: is the clustering any good?

Plain version. Without labels, “good” has to be defined: tight and well separated (internal indices), agreeing with some trusted reference (external indices), or reproducible when the data are perturbed (stability). Theodoridis and Koutroumbas devote Chapter 16 to these questions [1]; PR 09 returns to validation in the supervised setting.

Internal indices

Silhouette [14]. For point ii in cluster CC, let a(i)a(i) be its mean distance to the other points in CC, and b(i)b(i) the smallest mean distance from ii to the points of any other cluster. Then

s(i)=b(i)−a(i)max⁡{a(i),b(i)}∈[−1,1].s(i)=\frac{b(i)-a(i)}{\max\{a(i),b(i)\}}\in[-1,1].

s(i)s(i) near 11 means ii sits well inside its cluster; near 00, on a boundary; negative, probably in the wrong cluster. The mean silhouette over all points summarizes a partition, and the per-point silhouette plot shows which clusters are weak.

Davies–Bouldin [15]. Let sis_i be the average distance of cluster ii‘s points to its centroid cic_i, and dij=∥ci−cj∥d_{ij}=\|c_i-c_j\|. Then

DB=1K∑i=1Kmax⁡j≠isi+sjdij,\mathrm{DB}=\frac{1}{K}\sum_{i=1}^{K}\max_{j\ne i}\frac{s_i+s_j}{d_{ij}} ,

the average “worst-case similarity” of each cluster to another. Lower is better.

Calinski–Harabasz [16]. With between-cluster scatter B=∑kNk(ck−xˉ)(ck−xˉ)⊤B=\sum_k N_k(c_k-\bar x)(c_k-\bar x)^\top and within-cluster scatter W=∑k∑n∈Ck(xn−ck)(xn−ck)⊤W=\sum_k\sum_{n\in C_k}(x_n-c_k)(x_n-c_k)^\top (xˉ\bar x is the overall mean),

CH=tr⁡(B)/(K−1)tr⁡(W)/(N−K),\mathrm{CH}=\frac{\operatorname{tr}(B)/(K-1)}{\operatorname{tr}(W)/(N-K)} ,

a variance-ratio statistic. Higher is better.

All three reward compact, convex, well-separated clusters in the chosen geometry. They will rate k-means’ wrong answer on the two moons higher than the correct curved answer. They measure agreement with an assumed cluster shape, not semantic correctness.

External indices

When reference labels exist (for benchmarking, or for a separate held-out annotation), compare partitions with permutation-invariant indices.

Adjusted Rand index (ARI) [17]. The Rand index counts the fraction of point pairs on which two partitions agree (both “same cluster” or both “different cluster”). ARI subtracts the value expected under random labelings with the same cluster sizes and rescales:

ARI=RI−E[RI]max⁡RI−E[RI],\mathrm{ARI}=\frac{\mathrm{RI}-\mathbb E[\mathrm{RI}]}{\max\mathrm{RI}-\mathbb E[\mathrm{RI}]} ,

so random partitions score about 00 and identical partitions (up to relabeling) score 11.

Normalized mutual information (NMI). Treat the two labelings UU and VV as random variables over points; then

NMI(U,V)=I(U;V)12(H(U)+H(V)),\mathrm{NMI}(U,V)=\frac{I(U;V)}{\tfrac12\big(H(U)+H(V)\big)} ,

with mutual information II and entropies HH (the arithmetic-mean normalization shown is scikit-learn’s default; other normalizations exist). Vinh, Epps and Bailey [18] showed that unadjusted NMI is biased upward when the number of clusters is large relative to NN, and recommend chance-adjusted versions such as adjusted mutual information (AMI).

If the reference labels were used to tune the algorithm or KK, they are no longer an independent check.

Stability

Refit the clustering on bootstrap samples or perturbed data and compare each new partition with the original on the same points, using ARI. A KK that gives unstable partitions is suspect. But stability is necessary, not sufficient: merging two nearby blobs is perfectly reproducible (Figure 6, right, K=3K=3), and a stable partition can still reflect an irrelevant factor such as the camera or the lighting.

Code: validity indices and stability

Code · Python · 30 lines
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
from sklearn.metrics import (silhouette_score, davies_bouldin_score,
                             calinski_harabasz_score, adjusted_rand_score,
                             normalized_mutual_info_score)

X, truth = make_blobs(n_samples=600, centers=4, cluster_std=1.0, random_state=7)
print(" K  silhouette(+)  Davies-Bouldin(-)  Calinski-Harabasz(+)")
for K in range(2, 8):
    z = KMeans(K, n_init=10, random_state=0).fit_predict(X)
    print(f"{K:2d}  {silhouette_score(X, z):12.3f}  {davies_bouldin_score(X, z):17.3f}"
          f"  {calinski_harabasz_score(X, z):20.1f}")

z = KMeans(4, n_init=10, random_state=0).fit_predict(X)
print("external ARI:", round(adjusted_rand_score(truth, z), 3),
      " NMI:", round(normalized_mutual_info_score(truth, z), 3))
perm = np.array([2, 0, 3, 1])[z]                       # relabel clusters
print("ARI after relabelling:", round(adjusted_rand_score(truth, perm), 3))

# stability: refit on bootstrap samples, compare on the original points
rng = np.random.default_rng(1)
for K in [3, 4, 5, 6]:
    base = KMeans(K, n_init=10, random_state=0).fit(X)
    scores = []
    for b in range(10):
        idx = rng.integers(0, len(X), len(X))
        boot = KMeans(K, n_init=10, random_state=b).fit(X[idx])
        scores.append(adjusted_rand_score(base.predict(X), boot.predict(X)))
    print(f"K={K}: bootstrap stability (mean ARI) = {np.mean(scores):.3f}")

Output

 K  silhouette(+)  Davies-Bouldin(-)  Calinski-Harabasz(+)
 2         0.588              0.796                 850.9
 3         0.762              0.343                2235.5
 4         0.811              0.270                7641.8
 5         0.680              0.603                6341.0
 6         0.577              0.821                5620.2
 7         0.446              0.988                5304.4
external ARI: 1.0  NMI: 1.0
ARI after relabelling: 1.0
K=3: bootstrap stability (mean ARI) = 1.000
K=4: bootstrap stability (mean ARI) = 1.000
K=5: bootstrap stability (mean ARI) = 0.858
K=6: bootstrap stability (mean ARI) = 0.699

On these well-separated blobs every internal index agrees on K=4K=4, and the external indices confirm a perfect match regardless of how the clusters are numbered. Real data are rarely this kind: indices frequently disagree, and the disagreement is informative, because it tells you the data do not have one unambiguous cluster structure at the chosen scale.

Modern view

Plain version. The algorithms in this chapter are decades old and still everywhere. What changed is the representation: today we usually cluster learned embeddings rather than raw pixels or hand-made descriptors, and deep networks are sometimes trained by clustering.

Surveys worth reading

  • Xu and Wunsch, “Survey of clustering algorithms” (2005) [19] is the classic broad survey from a pattern-recognition and neural-network viewpoint. It reviews proximity measures, then organizes algorithms into hierarchical, squared-error (k-means family), mixture-density, graph-theoretic, fuzzy, neural (self-organizing maps, adaptive resonance), kernel, sequential-data, large-scale and high-dimensional methods, and closes with cluster validity. It is a good map of the classical landscape.
  • Jain, “Data clustering: 50 years beyond K-means” (2010) [20] is a shorter, opinionated overview. Its main messages remain current: there is no universally best algorithm; the representation and the definition of a cluster matter more than the algorithm; the number of clusters and validity are open questions; and side information (pairwise constraints, semi-supervised clustering) and clustering ensembles are valuable directions.
  • Ikotun et al., “K-means clustering algorithms: A comprehensive review, variants analysis, and advances in the era of big data” (2023) [21] reviews the many k-means variants: initialization (including k-means++), automatic choice of KK, handling of mixed or high-dimensional data, and scalable and distributed implementations.
  • Zhou et al., “A comprehensive survey on deep clustering: Taxonomy, challenges, and future directions” (ACM Computing Surveys, 2024) [22] organizes deep clustering by how the representation-learning module and the clustering module interact: multi-stage methods (learn features, then cluster), iterative methods (alternate pseudo-labels and feature learning), generative methods (latent-variable models such as mixture-prior autoencoders), and simultaneous methods (optimize both jointly). It also discusses benchmarks, metrics and applications.
  • Ren et al., “Deep clustering: A comprehensive survey” (IEEE TNNLS, 2025) [23] organizes the field by data source and prior knowledge: single-view, semi-supervised, multi-view and transfer deep clustering. Read together with [22], it shows how wide the deep-clustering design space has become.

From visual words to self-labeling

Two influential vision papers show how classical clustering became a training signal. DeepCluster [24] alternates between running k-means on the features of a convolutional network and training that network to predict the cluster assignments as pseudo-labels; repeated over the whole data set, this learns useful features from unlabeled images. SCAN [25] separates representation learning from clustering: it first learns features with a self-supervised pretext task, then mines each image’s nearest neighbors in that feature space and trains a clustering head so that neighbors receive the same cluster, followed by a self-labeling refinement. Both are applications of the ideas in this chapter (k-means as quantization, neighborhoods as evidence of similarity) to learned representations; ML 06 explains where such representations come from.

State of practice (2023–2026) and open problems

In current practice, a common recipe for grouping images is: extract embeddings from a pretrained (often self-supervised) encoder, optionally reduce dimension, then run k-means, a Gaussian mixture or HDBSCAN, and validate on a labeled subset. The chapter’s warnings apply unchanged:

  • The representation defines similarity. Embeddings trained for one purpose may cluster by style, background or camera rather than by the category you care about.
  • KK and validity remain open. Information criteria assume the model family; internal indices assume a shape; external indices need labels. No survey above claims a general solution.
  • Evaluation of deep clustering usually relies on labeled benchmarks and permutation-invariant scores such as clustering accuracy after optimally matching clusters to classes, NMI and ARI [22]. Those scores measure agreement with one chosen labeling, not the “true” structure.
  • Scale and imbalance. Long-tailed data, many small clusters, and streaming data stress both classical and deep methods; [21] and [22] list these as active problems.

Key takeaways

  • Clustering is defined by its notion of similarity. Features, scaling and distance are modeling decisions made before any algorithm runs.
  • K-means (Lloyd) alternates nearest-center assignment and mean update; JJ decreases monotonically to a local minimum. k-means++ seeding gives E[J]≤8(ln⁡K+2)JOPT\mathbb E[J]\le 8(\ln K+2)J_{\mathrm{OPT}} and far fewer bad runs; use several restarts anyway.
  • Linkage defines hierarchical clustering: single linkage chains along thin bridges, complete and Ward prefer compact groups. The dendrogram must still be cut.
  • DBSCAN defines clusters as density-connected regions, finds arbitrary shapes and labels noise; ε\varepsilon comes from the k-distance curve, and HDBSCAN handles varying density.
  • EM for Gaussian mixtures follows from the complete-data log-likelihood: E step responsibilities, M step weighted means and covariances, πk=Nk/N\pi_k=N_k/N via a Lagrange multiplier. The ELBO decomposition proves monotone improvement; singularities and label switching need explicit care; k-means is the hard, isotropic limit.
  • BIC =−2ln⁡L^+pln⁡N=-2\ln\hat L+p\ln N and AIC =−2ln⁡L^+2p=-2\ln\hat L+2p trade fit against parameter count; covariance type is part of the choice.
  • Internal indices (silhouette, Davies–Bouldin, Calinski–Harabasz) reward an assumed geometry; external indices (ARI, NMI) need independent labels; stability is necessary but not sufficient.

Exercises

  1. Lloyd’s algorithm never increases JJ. Prove that both the assignment step and the update step cannot increase JJ, and use this to argue that the algorithm terminates. What goes wrong with the termination argument if ties are broken randomly?
Hint

The assignment step minimizes each term ∥xn−μzn∥2\|x_n-\mu_{z_n}\|^2 separately; the update step uses ∑n∈Ck∥xn−μ∥2=∑n∈Ck∥xn−xˉk∥2+Nk∥xˉk−μ∥2\sum_{n\in C_k}\|x_n-\mu\|^2=\sum_{n\in C_k}\|x_n-\bar x_k\|^2+N_k\|\bar x_k-\mu\|^2. There are at most KNK^N partitions. With random tie-breaking, two partitions of equal JJ could alternate forever; a fixed rule (for example, keep the current cluster on ties) prevents that.

  1. k-means++ by hand. One-dimensional data are {0,1,2,10,11}\{0,1,2,10,11\} and K=2K=2. The first seed is 00. Compute the probability that each point becomes the second seed. Then compare with uniform sampling of the second seed.
Hint

D2D^2 values are 0,1,4,100,1210,1,4,100,121, summing to 226226. So P(10)=100/226P(10)=100/226 and P(11)=121/226P(11)=121/226; together about 0.980.98. Under uniform sampling the second seed lands in the right-hand group with probability only 2/52/5 (or 2/42/4 if the first seed is excluded).

  1. The M step for a 1-D mixture. For a one-dimensional two-component mixture with variances σ12,σ22\sigma_1^2,\sigma_2^2, derive the M-step update of σk2\sigma_k^2 from QQ directly, without matrix calculus. Then show that if a component’s responsibilities concentrate on one point xnx_n (that is, rnk≈1r_{nk}\approx 1 for that point and ≈0\approx 0 for the others), the update drives σk2\sigma_k^2 toward 00. What does scikit-learn’s reg_covar do about it?
Hint

Differentiate ∑nrnk[−12ln⁡σk2−(xn−μk)2/(2σk2)]\sum_n r_{nk}\big[-\tfrac12\ln\sigma_k^2-(x_n-\mu_k)^2/(2\sigma_k^2)\big] with respect to σk2\sigma_k^2 to get σk2=∑nrnk(xn−μk)2/Nk\sigma_k^2=\sum_n r_{nk}(x_n-\mu_k)^2/N_k. With all weight on one point, μk=xn\mu_k=x_n and the sum is zero. reg_covar adds a small constant to the diagonal after each M step, so the variance stays bounded away from zero.

  1. Counting parameters. For local descriptors with D=64D=64 and K=32K=32 components, count the free parameters of a GMM with full, diagonal and spherical covariances. With N=105N=10^5 descriptors, how large is the BIC penalty pln⁡Np\ln N in each case?
Hint

Full: 31+32⋅64+32⋅64⋅65/2=31+2048+66560=68,63931+32\cdot64+32\cdot64\cdot65/2=31+2048+66560=68{,}639. Diagonal: 31+2048+2048=4,12731+2048+2048=4{,}127. Spherical: 31+2048+32=2,11131+2048+32=2{,}111. Multiply by ln⁡105≈11.51\ln 10^5\approx11.51. The full model has to improve −2ln⁡L^-2\ln\hat L by roughly 7.4×1057.4\times10^5 over the diagonal one just to break even.

  1. When indices mislead. Run k-means with K=2K=2 and DBSCAN on the two-moons data from the comparison code. Compute the silhouette score of each partition and their ARI against the generating labels. Explain the disagreement in terms of what each index measures.
Hint

Silhouette is computed from Euclidean distances and favors convex, separated groups, so the k-means cut usually scores higher than the two moons even though its ARI is about 0.26 versus 1.0 for DBSCAN. Internal indices encode a shape assumption; the “right” answer here is defined by connectivity.

  1. Stability is not truth. Generate four Gaussian blobs where two are very close (for example centers (0,0)(0,0) and (1.2,0)(1.2,0) with standard deviation 0.50.5). Compute bootstrap stability for K=3K=3 and K=4K=4. Which is more stable? Which matches the generating process? What extra information would settle it?
Hint

Merging the close pair is very reproducible, so K=3K=3 can be as stable as or more stable than K=4K=4. The generating process has four groups, but whether they should be separated depends on the task. Domain knowledge, a labeled subset, or a density-based criterion such as BIC on a GMM gives additional evidence.

References

  1. S. Theodoridis and K. Koutroumbas, Pattern Recognition, 4th ed., Academic Press, 2009, Ch. 11–16 (clustering basic concepts, sequential, hierarchical, function-optimization and graph-based algorithms, cluster validity). doi

  2. C. M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006, Ch. 9 (k-means, mixtures of Gaussians, EM, the general EM algorithm). book page

  3. S. P. Lloyd, “Least squares quantization in PCM,” IEEE Transactions on Information Theory, vol. 28, no. 2, pp. 129–137, 1982. doi

  4. J. MacQueen, “Some methods for classification and analysis of multivariate observations,” in Proc. Fifth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, pp. 281–297, 1967. Project Euclid

  5. D. Arthur and S. Vassilvitskii, “k-means++: The advantages of careful seeding,” in Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007, pp. 1027–1035. pdf

  6. D. Sculley, “Web-scale k-means clustering,” in Proc. 19th International Conference on World Wide Web (WWW), 2010, pp. 1177–1178. doi

  7. J. H. Ward, “Hierarchical grouping to optimize an objective function,” Journal of the American Statistical Association, vol. 58, pp. 236–244, 1963. doi

  8. M. Ester, H.-P. Kriegel, J. Sander and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise,” in Proc. 2nd International Conference on Knowledge Discovery and Data Mining (KDD), 1996. pdf

  9. R. J. G. B. Campello, D. Moulavi and J. Sander, “Density-based clustering based on hierarchical density estimates,” in Advances in Knowledge Discovery and Data Mining (PAKDD), LNCS, 2013, pp. 160–172. doi

  10. U. von Luxburg, “A tutorial on spectral clustering,” Statistics and Computing, vol. 17, pp. 395–416, 2007. doi

  11. A. P. Dempster, N. M. Laird and D. B. Rubin, “Maximum likelihood from incomplete data via the EM algorithm,” Journal of the Royal Statistical Society: Series B, vol. 39, no. 1, pp. 1–22, 1977. doi

  12. G. Schwarz, “Estimating the dimension of a model,” The Annals of Statistics, vol. 6, no. 2, 1978. doi

  13. H. Akaike, “A new look at the statistical model identification,” IEEE Transactions on Automatic Control, vol. 19, no. 6, pp. 716–723, 1974. doi

  14. P. J. Rousseeuw, “Silhouettes: A graphical aid to the interpretation and validation of cluster analysis,” Journal of Computational and Applied Mathematics, vol. 20, pp. 53–65, 1987. doi

  15. D. L. Davies and D. W. Bouldin, “A cluster separation measure,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-1, no. 2, pp. 224–227, 1979. doi

  16. T. Caliński and J. Harabasz, “A dendrite method for cluster analysis,” Communications in Statistics, vol. 3, no. 1, pp. 1–27, 1974. doi

  17. L. Hubert and P. Arabie, “Comparing partitions,” Journal of Classification, vol. 2, pp. 193–218, 1985. doi

  18. N. X. Vinh, J. Epps and J. Bailey, “Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance,” Journal of Machine Learning Research, vol. 11, pp. 2837–2854, 2010. JMLR

  19. R. Xu and D. Wunsch II, “Survey of clustering algorithms,” IEEE Transactions on Neural Networks, vol. 16, no. 3, pp. 645–678, 2005. doi

  20. A. K. Jain, “Data clustering: 50 years beyond K-means,” Pattern Recognition Letters, vol. 31, no. 8, pp. 651–666, 2010. doi

  21. A. M. Ikotun, A. E. Ezugwu, L. Abualigah, B. Abuhaija and J. Heming, “K-means clustering algorithms: A comprehensive review, variants analysis, and advances in the era of big data,” Information Sciences, vol. 622, pp. 178–210, 2023. doi

  22. S. Zhou, H. Xu, Z. Zheng, J. Chen, Z. Li, J. Bu, J. Wu, X. Wang, W. Zhu and M. Ester, “A comprehensive survey on deep clustering: Taxonomy, challenges, and future directions,” ACM Computing Surveys, vol. 57, no. 3, pp. 1–38, 2024 (arXiv:2206.07579). doi

  23. Y. Ren, J. Pu, Z. Yang, J. Xu, G. Li, X. Pu, P. S. Yu and L. He, “Deep clustering: A comprehensive survey,” IEEE Transactions on Neural Networks and Learning Systems, vol. 36, no. 4, pp. 5858–5878, 2025 (arXiv:2210.04142). doi

  24. M. Caron, P. Bojanowski, A. Joulin and M. Douze, “Deep clustering for unsupervised learning of visual features,” in Proc. European Conference on Computer Vision (ECCV), LNCS, 2018, pp. 139–156. doi

  25. W. Van Gansbeke, S. Vandenhende, S. Georgoulis, M. Proesmans and L. Van Gool, “SCAN: Learning to classify images without labels,” in Proc. European Conference on Computer Vision (ECCV), LNCS, 2020, pp. 268–285. doi

  26. scikit-learn developers, “GaussianMixture,” API documentation, accessed 2026-11-05. documentation

Check your understanding

This tutorial has 6 exercises. Can you solve them without opening the hints?

Go to the exercises ↑

Next PR 08 · Approximate Inference and Bayesian Model Complexity · 28 min