Clustering: k-means, GMMs/EM, DBSCAN and hierarchical

Structure without labels

Clustering asks: can these points be grouped so that members of a group are similar to each other and different from the rest? There is no ground truth, so every algorithm bakes in a definition of "group": a compact blob around a center (k-means), a probability distribution (mixture models), a dense region (DBSCAN) or a nested hierarchy (agglomerative). Pick the algorithm by which definition matches your data, and always look at the result.

k-means: the objective

Given points $\mathbf{x}_1,\dots,\mathbf{x}_n$ and a target number of clusters $K$, k-means seeks centroids $\boldsymbol\mu_k$ and an assignment of points to clusters $C_k$ that minimize the within-cluster sum of squares (the inertia):

Exact minimization is NP-hard, so we use Lloyd's algorithm: initialize $K$ centroids; then alternate (1) assign each point to its nearest centroid and (2) update each centroid to the mean of its points, until assignments stop changing.

Math check (why it converges). Step 1 cannot increase $J$: with centroids fixed, moving a point to a closer centroid lowers its term. Step 2 cannot increase $J$ either: with assignments fixed, $\sum_{i\in C_k}\|\mathbf{x}_i-\boldsymbol\mu\|^2$ is minimized by setting its gradient $-2\sum_{i\in C_k}(\mathbf{x}_i-\boldsymbol\mu)$ to zero, i.e. $\boldsymbol\mu=\frac{1}{|C_k|}\sum_{i\in C_k}\mathbf{x}_i$, the mean. $J$ decreases monotonically, is bounded below by 0, and there are finitely many assignments — so the algorithm terminates. It terminates at a local minimum, which is why we restart several times and keep the best $J$.

Worked example. Points on a line: $\{1,2,3,10,11,12\}$, $K=2$, initial centroids $\mu_1=1$, $\mu_2=2$. Assignment: $1\to\mu_1$; $2,3,10,11,12\to\mu_2$. Update: $\mu_1=1$, $\mu_2=(2+3+10+11+12)/5=7.6$. Assignment: $1,2,3\to\mu_1$ (3 is 2 away from 1 but 4.6 from 7.6); $10,11,12\to\mu_2$. Update: $\mu_1=2$, $\mu_2=11$. Nothing changes afterwards; $J=(1+0+1)+(1+0+1)=4$. A bad initialization (say $\mu_1=1,\mu_2=12$ is good; $\mu_1=10,\mu_2=11$ is bad) can end in a worse local minimum — hence k-means++ initialization, which picks each new centroid with probability proportional to $D(\mathbf{x})^2$, its squared distance to the nearest existing centroid, and guarantees an expected $O(\log K)$-competitive solution.

Choosing $K$: plot $J$ against $K$ and look for an elbow; or compute the silhouette of each point, $s_i=\frac{b_i-a_i}{\max(a_i,b_i)}$ with $a_i$ the mean distance to its own cluster and $b_i$ the mean distance to the nearest other cluster — values near 1 are well placed, near 0 are on a border. k-means assumes roughly spherical, similarly sized clusters, is sensitive to feature scaling and outliers, and must be told $K$. Scale features first (3.13 Feature engineering, data quality and data-centric ML); use PCA to denoise if $d$ is large (3.12 Dimensionality reduction: PCA, t-SNE and UMAP).

Gaussian mixtures and EM

A Gaussian mixture model describes the data as a weighted sum of Gaussians,

with a latent cluster variable $z_i$ for each point. Maximum likelihood has no closed form because of the sum inside the log, so we use Expectation–Maximization:

• E-step: compute responsibilities, the posterior probability that point $i$ came from component $k$ (Bayes' rule, 1.7 Probability II: Bayes, independence, MLE and MAP):

• M-step: re-estimate parameters with responsibility-weighted statistics, $N_k=\sum_i r_{ik}$:

Each iteration increases the log-likelihood (EM maximizes a lower bound on it — the same evidence lower bound a VAE optimizes, 8.8 Generative models I: VAEs and GANs). GMMs give soft assignments, elliptical clusters of different sizes, and a density you can use for anomaly scores. k-means is the limit of a GMM with shared covariance $\sigma^2\mathbf{I}$ as $\sigma\to0$: responsibilities become one-hot and the M-step becomes the mean update. Choose $K$ for a GMM with BIC/AIC rather than an elbow.

Density and hierarchy

DBSCAN needs no $K$. With a radius $\varepsilon$ and a minimum count minPts, a core point has at least minPts neighbours within $\varepsilon$; clusters are maximal sets of density-connected core points plus their border points; everything else is labelled noise. It finds arbitrary shapes (rings, crescents) and flags outliers, but one global $\varepsilon$ struggles when densities vary (HDBSCAN fixes this by building a hierarchy over $\varepsilon$).

Agglomerative clustering starts with every point as its own cluster and repeatedly merges the two closest clusters, where "closest" is defined by a linkage: single (nearest members; chains), complete (farthest members; compact), average, or Ward (merge that increases total within-cluster variance least; most k-means-like). The merge history is a dendrogram, which you cut at a height to get any number of clusters — useful when the hierarchy itself is the insight (taxonomies, document trees). Cost is $O(n^2\log n)$ time and $O(n^2)$ memory, so it is for thousands, not millions, of points.

Evaluating and using clusters

Without labels, use internal indices (silhouette, Davies–Bouldin) and stability (do clusters survive re-sampling and re-seeding?). With labels available for checking, use the adjusted Rand index or normalized mutual information (1.9 Information theory: entropy, cross-entropy and KL divergence). Always visualize with PCA or UMAP (3.12 Dimensionality reduction: PCA, t-SNE and UMAP) and read actual members of each cluster.

Clustering embeddings is a workhorse of the LLM era: cluster sentence embeddings (9.2 Embeddings deep dive) to discover topics (BERTopic = UMAP + HDBSCAN + class-based TF-IDF), to deduplicate near-identical training data, or to pick diverse examples for few-shot prompts. And the inverted-file index that makes vector search fast partitions the space with k-means centroids (9.3 Vector search and indexes).

Where this shows up later

• Dimensionality reduction before and after clustering — 3.12 Dimensionality reduction: PCA, t-SNE and UMAP; feature scaling — 3.13 Feature engineering, data quality and data-centric ML.
• EM's lower bound is the ELBO of variational autoencoders — 8.8 Generative models I: VAEs and GANs; soft assignments reappear as softmax responsibilities and as attention weights — 7.2 Scaled dot-product and multi-head attention, fully derived.
• Clustering embeddings for topics and dedup — 9.2 Embeddings deep dive; IVF indexes built on k-means — 9.3 Vector search and indexes; clustering agent trajectories for error analysis — 10.9 Evaluating agents.