Clustering

Definition

Clustering divides unlabeled data into groups whose members resemble each other more than they resemble anything outside the group, and the practical question — which algorithm — has a short answer. Reach for k-means when you expect a handful of compact, roughly equal-sized blobs and can name how many; DBSCAN or HDBSCAN when the groups may be irregularly shaped, unknown in number, or surrounded by junk you want excluded rather than assigned; hierarchical clustering when you would rather see the whole merge order than commit to one cut; Gaussian mixtures when groups overlap and you want a probability of membership instead of a hard label.

That list is short because the real difficulty is elsewhere. No algorithm finds the groups in your data; each finds the best groups of the shape it was built to look for, and it will return them whether or not such groups exist. On two concentric rings, k-means scores an adjusted Rand index of −0.001 against the true grouping — indistinguishable from random — while DBSCAN scores 1.000. Neither algorithm malfunctioned. They were asked different questions, and each answered its own correctly. Everything else on this page follows from that.

How It Works

Every clustering method is built from three separable choices: a distance that says what "similar" means, an objective or rule that says what a good grouping is, and a search that tries to find one. Most disappointing results trace to the first two, which people rarely think of as choices at all.

Distance is a modelling decision, usually made by accident

Take two people described by height in metres and weight in kilograms: (1.60 m, 80 kg) and (1.80 m, 60 kg). Their squared Euclidean distance is 0.20² + 20² = 0.04 + 400 = 400.04. Height contributes 0.01% of the distance and weight contributes the rest, so any algorithm using this metric is clustering on weight and quietly ignoring height. Now record height in centimetres instead of metres. The same two people, the same information, but the distance becomes 20² + 20² = 800, and height and weight now carry exactly half each. The clusters change because a unit changed.

This is the most common practical error in applied clustering, and the fix is boring: standardise every feature to zero mean and unit variance first. The subtler consequence is that standardising then gives every feature equal weight, which is also an assumption — one that ten redundant columns about price exploit by outvoting the single column about behaviour. What goes into the feature vector is part of the clustering; see feature selection and dimensionality reduction.

The objective cannot choose k, and here is the arithmetic

k-means minimises the within-cluster sum of squared distances to the cluster centroids, called inertia. Run it on the same 1,000-point dataset at increasing k and inertia falls monotonically: 584.82 at k=1, then 384.05, 246.56, 184.03, 153.05 — and 0.00 at k=1,000, where every point is its own centroid and its distance to itself is zero. The objective is minimised, perfectly, by the answer that groups nothing. "Pick the k that minimises the objective" is therefore not a criterion, and no amount of data will supply one.

The elbow heuristic is what people use instead: plot inertia against k and look for the bend where extra clusters stop buying much. It is a heuristic because it asks you to see a corner on a smooth curve. On that ring data, the successive drops are 201, 137, 63 and 31 — the sharpest bend sits between k=3 and k=4, while the true number of groups is 2. The elbow points at the wrong answer on a dataset where the right one is known.

Silhouette score is the more informative tool. For each point it compares a, the mean distance to the other members of its own cluster, with b, the mean distance to the members of the nearest other cluster, giving s = (b − a) / max(a, b). A point sitting at a = 0.8 inside a cluster whose nearest rival is b = 2.4 away scores (2.4 − 0.8) / 2.4 = 0.67; a point that is closer to the neighbouring cluster than to its own, a = 2.4 against b = 0.8, scores −0.67. Averaged over the dataset, silhouette measures separation relative to compactness — which is a real property, but as the Challenges section shows, not the same property as "these clusters exist".

The search is approximate, and that is not a bug you can fix

Finding the partition that truly minimises inertia is NP-hard, and the search space is why: the number of ways to split just 25 points into 5 non-empty groups is 2,436,684,974,110,751 — over 2.4 × 10¹⁵. Lloyd's algorithm, the thing everyone calls "k-means", sidesteps this by alternating two cheap steps — assign each point to its nearest centroid, move each centroid to the mean of its points — until nothing moves. It converges quickly, at cost roughly O(n × k × d × i) for n points, d dimensions and i iterations, and it converges to a local optimum that depends on where the centroids started. That is why libraries run it several times from different seeds (scikit-learn's n_init) and keep the best, and why k-means++ initialisation, which spreads the initial centroids apart with probability proportional to squared distance, is the default.

Types

The field's standard taxonomy sorts algorithms by what they assume a cluster is. Read it as four different definitions of the word, not four tools of equal generality.

Centroid-based methods define a cluster as the set of points nearest to a representative point. k-means is the archetype: minimising squared distance to a centroid means the boundary between any two clusters is a straight line equidistant from both, so the regions are convex and the clusters come out roughly spherical and similarly sized. Hand it two concentric rings and it slices them like a pie, because a pie slice genuinely is the lowest-inertia answer available. k-medoids and k-medians swap the objective for something more robust to outliers but keep the same geometry.

Density-based methods define a cluster as a connected region where points are packed more tightly than the surroundings. DBSCAN needs two parameters — a radius eps and a minimum neighbour count min_samples — and grows clusters by linking points that have enough neighbours within eps, leaving everything else labelled as noise. This buys three things k-means cannot offer: arbitrary shapes, a cluster count discovered rather than declared, and explicit outliers. It pays for them with a single global density threshold, so a dataset containing one dense group and one diffuse group cannot be handled at any eps. HDBSCAN removes that limitation by building the clustering across all density thresholds at once and extracting the most persistent groups.

Hierarchical methods refuse to pick one grouping and produce the whole nested family instead, usually agglomerative: start with every point as its own cluster and repeatedly merge the closest pair, recording the merge order as a dendrogram you can cut at any height. The linkage rule is the assumption in disguise. Single linkage measures cluster distance by the closest pair and so happily traces long chains and irregular shapes; complete linkage uses the farthest pair and produces compact balls; Ward's method merges the pair that increases total within-cluster variance least, which is the k-means objective in hierarchical clothing — and inherits the same bias toward spheres. The cost is scale: n points have n(n−1)/2 pairwise distances, so 100,000 points imply about 5 billion pairs and roughly 20 GB just to hold them at 4 bytes each.

Distribution-based methods assume the data was generated by a mixture of probability distributions and try to recover their parameters. A Gaussian mixture model fitted by expectation-maximisation gives each point a probability of belonging to each component rather than a hard assignment, and because each component has its own covariance matrix it can represent elongated and tilted ellipses that k-means cannot. Constrain every covariance to be spherical and equal and the algorithm degenerates into k-means, which is the cleanest statement of what k-means was assuming all along.

Real-World Applications

Customer segmentation is the textbook example and is covered under unsupervised learning; the deployments below are the ones where clustering is load-bearing infrastructure rather than an analysis step.

Searching a billion vectors without comparing to a billion vectors. Approximate nearest-neighbour indexes such as FAISS's IVF build their speed on k-means. The index clusters the corpus once into nlist cells, stores each vector under its nearest centroid, and at query time compares the query only against the nprobe nearest centroids' contents. With 4,096 cells and nprobe set to 16, a search touches 16/4096 — one 256th — of the database, and the recall you lose is the recall of answers that happened to fall in an unvisited cell. Every vector search and semantic search system at scale contains a clustering step of this kind, and the knob trading latency against recall is a clustering parameter.

Colour quantisation. Reducing a 24-bit image, which can address 2²⁴ = 16,777,216 distinct colours, to a 256-entry palette for GIF or PNG-8 is k-means in three-dimensional RGB space with k=256. Storage drops from 3 bytes per pixel to 1 byte plus a fixed 768-byte palette, a threefold reduction, and the visible quality of the result is exactly the quality of the clustering.

Codebooks inside neural audio codecs. Vector-quantised models — VQ-VAE, and the residual vector quantisation used by SoundStream and EnCodec in audio processing — represent a continuous embedding by the index of the nearest entry in a learned codebook. Those codebooks are initialised and maintained by k-means over the encoder's own activations, which is what turns a continuous signal into the discrete tokens a language model can consume.

Deduplicating training corpora. Web-scale text collections are full of near-duplicates, and removing them measurably improves the models trained on them. The standard pipeline hashes each document with MinHash, buckets the hashes with locality-sensitive hashing, and clusters the collisions into groups of near-identical documents, keeping one survivor per group — the only affordable way to ask which of a billion documents are the same document.

Key Concepts

• Adjusted Rand index needs labels you usually do not have: it compares a clustering against a known truth, corrected so that random agreement scores 0. Useful for benchmarking algorithms on data where the answer is known, useless on the data you actually care about.
• eps is a distance, so it is scale-dependent too: DBSCAN's radius has units. Rescale the features and every previously tuned eps is wrong.
• Soft assignment carries information hard assignment destroys: a point at 51%/49% between two Gaussian components and a point at 99%/1% get the same label from k-means and different, more honest, answers from a mixture model.

Challenges

There is no held-out test set. Every other part of supervised machine learning rests on comparing predictions against withheld answers, and clustering has no answers to withhold. This makes internal indices — silhouette, Calinski-Harabasz, Davies-Bouldin — dangerously reassuring, because they measure whether the partition is geometrically tidy, not whether the partition corresponds to anything. Run k-means on 1,000 points drawn uniformly at random from a square and the silhouette peaks at about 0.41 at k=4: a number routinely reported as evidence of well-separated structure, produced by data containing none at all. The algorithm did what it was asked. It divided a square into four boxes.

Stability is the right check, and it is necessary rather than sufficient. The honest question is whether the same structure reappears when the data or the seed changes: refit on bootstrap resamples, on reshuffled input order, and from different random initialisations, then measure the agreement between the resulting partitions. A grouping that dissolves under resampling was a property of your sample, not your population. But the uniform-noise example fails this test too — across 30 bootstrap resamples it reproduces its own four boxes at a mean adjusted Rand index of 0.94, because slicing a square into quadrants is an extremely stable thing to do. Stability detects clusterings that are accidental; it cannot certify that clusters exist.

What remains is the external check, and it is not a metric: does the clustering change a decision? A segmentation that produces a different email, a different intervention or a different research priority has been validated by the only evidence available. A clustering nobody acts on has not been validated by anything, whatever its silhouette says.

Distances stop discriminating as dimensions grow. In high-dimensional space the distances between all pairs of points converge, so "nearest" loses its meaning — and every method on this page is built on "nearest". Take 1,000 points drawn uniformly at random and measure the ratio of the largest pairwise distance to the smallest: in 2 dimensions it is about 1,942, in 10 dimensions 9.9, in 100 dimensions 1.69, and in 1,000 dimensions 1.19. By then the farthest point is barely 19% farther away than the closest one, and a clustering built on that gap is building on nothing. This is why practitioners run PCA or UMAP before clustering, and why clustering embeddings — where a trained encoder has already arranged the space so that distance means something — works better than clustering raw high-dimensional features.

Naming a cluster is not the same as validating it. A human reads the centroid, decides the group means "price-sensitive weekend shoppers", and acts on that — an interpretation laid on top of an arithmetic partition, and the step where confidence most exceeds evidence.

Future Trends

The durable shift is that clustering has moved off raw features and onto learned representations. Clustering documents by TF-IDF meant hand-designing what similarity meant; clustering their embeddings means the similarity was learned from data, so the metric problem moved into the encoder rather than disappearing. Deep clustering pushes this further by training the representation and the clustering jointly, shaping the space to be clusterable. The second movement is toward fewer knobs — HDBSCAN over DBSCAN, because a global eps was always the wrong thing to ask a user for — and toward constrained clustering, where a handful of must-link and cannot-link pairs from a domain expert steer an otherwise unsupervised search. That last one is an admission worth making explicit: a few labels resolve ambiguity that no amount of unlabeled data can.

Code Example

The failure that matters, in nine lines. make_circles generates two concentric rings, so the true answer is known; adjusted Rand index scores each algorithm against it, where 0 is chance and 1 is perfect.

from sklearn.cluster import KMeans, DBSCAN
from sklearn.datasets import make_circles
from sklearn.metrics import adjusted_rand_score

X, y = make_circles(n_samples=1000, factor=0.4, noise=0.05, random_state=0)

km = KMeans(n_clusters=2, n_init=10, random_state=0).fit(X)
db = DBSCAN(eps=0.2, min_samples=5).fit(X)

print("k-means agreement with the true rings:", round(adjusted_rand_score(y, km.labels_), 3))
print("DBSCAN  agreement with the true rings:", round(adjusted_rand_score(y, db.labels_), 3))
print("k-means within-cluster sum of squares:", round(km.inertia_, 1))

Output:

k-means agreement with the true rings: -0.001
DBSCAN  agreement with the true rings: 1.0
k-means within-cluster sum of squares: 383.9

k-means was given the correct k and still scored at chance, and the last line is the point: 383.9 is the lowest within-cluster sum of squares available for k=2 on this data. k-means solved its problem optimally. Its problem was the wrong one.