Clustering

The three families, formally#

Centroid-based. Minimise within-cluster sum of squares. The objective, Lloyd's algorithm, k-means++ seeding, the O(nkdi) cost and the NP-hardness result are covered in the researcher block of unsupervised learning and are not repeated here.

Hierarchical (agglomerative). Start with n singleton clusters and repeatedly merge the closest pair under a linkage function d(A, B). The merge sequence forms a dendrogram; any horizontal cut yields a partition.

Density-based. Define clusters as maximal connected regions of high density, with low-density points labelled noise.

Linkage functions#

The linkage function is the entire content of hierarchical clustering. Each one implies a different cluster geometry.

single    d(A,B) = min_{a in A, b in B} ||a - b||
complete  d(A,B) = max_{a in A, b in B} ||a - b||
average   d(A,B) = (1/(|A||B|)) * SUM_{a,b} ||a - b||          (UPGMA)
centroid  d(A,B) = ||mean(A) - mean(B)||
Ward      d(A,B) = ( |A||B| / (|A|+|B|) ) * ||mean(A) - mean(B)||^2

• A, B — two candidate clusters; |A| is the number of points in A
• ||.|| — Euclidean norm

Single linkage computes the minimum spanning tree of the data and cuts its largest edges (Gower & Ross, 1969). That gives it the ability to follow arbitrarily shaped connected structures, and the chaining pathology demonstrated in the Developer section, where a thin bridge of 14 points merges two well-separated groups. The two behaviours are the same property.

Ward's criterion (Ward, 1963) merges the pair that increases total within-cluster variance least. It is the closest hierarchical analogue of k-means and inherits the same preference for spherical, similarly-sized clusters. In scikit-learn, linkage="ward" requires metric="euclidean" for exactly this reason.

All five fit the Lance-Williams recurrence (Lance & Williams, 1967), which updates distances after a merge in O(1) without revisiting the raw points:

d(A ∪ B, C) = α_A d(A,C) + α_B d(B,C) + β d(A,B) + γ |d(A,C) − d(B,C)|

Each linkage is one setting of (α_A, α_B, β, γ). This recurrence is why a naive implementation costs O(n^3) time and O(n^2) memory. SLINK (Sibson, 1973) and CLINK (Defays, 1977) achieve O(n^2) for single and complete linkage; nearest-neighbour chain gives O(n^2) for any reducible linkage, which includes Ward, complete and average but excludes centroid and median linkage, whose dendrograms can contain inversions.

The O(n^2) memory requirement is the practical ceiling. A full pairwise distance matrix for n = 100{,}000 in float64 is 80 GB.

DBSCAN#

Ester, Kriegel, Sander & Xu (1996) define clusters through two parameters, eps and minPts:

N_eps(p)   = { q in D : dist(p,q) <= eps }              the eps-neighbourhood
core point : |N_eps(p)| >= minPts
q is directly density-reachable from p  if  p is core and q in N_eps(p)
q is density-reachable from p           if  a chain of such steps exists
p and q are density-connected           if  some core o reaches both
cluster    : a maximal density-connected set
noise      : any point in no cluster

Properties worth stating precisely:

• k is discovered, not supplied. The number of clusters follows from the density structure.
• Border points are ambiguous. A non-core point within eps of two different core points is assigned to whichever cluster reaches it first. The result depends on data ordering. HDBSCAN removes this.
• Complexity is O(n log n) with a spatial index (R*-tree, ball tree, k-d tree) and O(n^2) without one. Index performance degrades above roughly 15–20 dimensions, at which point DBSCAN becomes quadratic.
• Memory is O(n), not O(n^2), which is its main advantage over hierarchical methods at scale.

The single global eps is DBSCAN's real limitation: it cannot represent clusters of substantially different density. HDBSCAN (Campello, Moulavi & Sander, 2013) fixes this by building a hierarchy over the mutual reachability distance

d_mreach(a,b) = max( core_k(a), core_k(b), d(a,b) )

where core_k(x) is the distance from x to its k-th nearest neighbour. It then extracts a flat clustering by maximising cluster stability, defined as the persistence of a branch across the density hierarchy. This replaces eps with min_cluster_size, a parameter with a meaning practitioners can actually reason about.

OPTICS (Ankerst et al., 1999) is the intermediate step: it produces a reachability plot that encodes the clustering for all eps simultaneously.

Spectral clustering#

When clusters are connected but not compact, embed before you partition. Build an affinity matrix W, typically W_ij = exp(−||x_i − x_j||^2 / (2σ^2)), and form the graph Laplacian:

L      = D − W                      unnormalised,   D_ii = SUM_j W_ij
L_sym  = D^{−1/2} L D^{−1/2}        Ng, Jordan & Weiss (2002)
L_rw   = D^{−1} L                   Shi & Malik (2000)

Take the eigenvectors of the k smallest eigenvalues, treat their rows as an embedding of the points, and run k-means there. The theoretical grounding is the Cheeger inequality relating the second eigenvalue of L to the normalised cut of the graph.

The relevant fact for the rings dataset: spectral clustering recovers it, because in the eigenvector embedding each ring collapses to a compact region. Cost is O(n^3) for a dense eigendecomposition, or O(n k) per iteration with Lanczos on a sparse k-nearest-neighbour graph. The result is highly sensitive to σ. von Luxburg (2007), A Tutorial on Spectral Clustering, remains the reference treatment.

Kleinberg's impossibility theorem#

Kleinberg (2002), An Impossibility Theorem for Clustering, proves that no clustering function f mapping a distance function on a finite set to a partition can satisfy all three of:

1. Scale invariance — f(αd) = f(d) for all α > 0.
2. Richness — every partition of the set is achievable by some d.
3. Consistency — shrinking within-cluster distances and stretching between-cluster distances leaves f(d) unchanged.

Any two are satisfiable; all three are not. Single linkage cut at k clusters gives up richness. Cut at a fixed distance threshold, it gives up scale invariance. K-means with fixed k gives up richness.

The practical reading is the point this lesson makes with data: there is no algorithm-independent notion of "the correct clustering". Ackerman & Ben-David (2008) show the impossibility relaxes when applied to clustering quality measures rather than clustering functions, which is why evaluation is a more tractable formal object than the algorithm itself.

Evaluation#

With ground truth. The Rand index counts agreeing pairs; the adjusted version corrects for chance agreement:

ARI = ( RI − E[RI] ) / ( max(RI) − E[RI] )

RI is the fraction of point pairs that two partitions agree about, either by placing both points together in each, or by separating them in each. E[RI] is its expectation under the generalised hypergeometric model of random partitions with fixed cluster sizes (Hubert & Arabie, 1985). The correction matters: an unadjusted Rand index rises towards 1 as k grows, purely by chance.

Adjusted mutual information (Vinh, Epps & Bailey, 2010) applies the same chance correction to normalised mutual information. Their recommendation is AMI when clusters are unbalanced and small, ARI when they are large and roughly equal.

Without ground truth. Silhouette (Rousseeuw, 1987), Davies-Bouldin (1979) and Calinski-Harabasz (1974) all encode a compactness-and-separation prior under a chosen metric. The Developer section measures the consequence: silhouette rates a k-means partition with ARI = −0.005 above a DBSCAN partition with ARI = 1.000. These indices are valid only for comparing partitions produced under the same geometric assumption they encode.

For density-based results, DBCV (Moulavi et al., 2014) scores clusterings using density rather than centroid distance and does not penalise non-convex shapes.

Current practice#

Three shifts matter.

Cluster in a learned space. Raw features rarely make Euclidean distance meaningful. Standard practice is to learn a representation first — self-supervised, or via an autoencoder — and cluster the embedding. Deep clustering methods such as DEC (Xie, Girshick & Farhadi, 2016) and SCAN (Van Gansbeke et al., 2020) fold the two steps together.

HDBSCAN over DBSCAN. For exploratory work on real data, min_cluster_size is a parameter people can set from domain knowledge; eps is not. This is now the pragmatic default for density-based work.

Stability as the selection criterion. Rather than optimising an internal index, resample the data, cluster each subsample, and measure how often pairs of points co-cluster (Ben-Hur, Elisseeff & Guyon, 2002; Von Luxburg, 2010). A grouping that survives resampling is evidence of structure. An internal index optimum is evidence about the index.

The honest summary for practice: decide what a group means in your problem, pick the algorithm whose assumptions match that meaning, and validate by resampling rather than by an index.

Key references#

• Ward, J. H. (1963). Hierarchical Grouping to Optimize an Objective Function. JASA 58(301).
• Lance, G. N. & Williams, W. T. (1967). A General Theory of Classificatory Sorting Strategies. Computer Journal 9(4).
• Sibson, R. (1973). SLINK: An Optimally Efficient Algorithm for the Single-Link Cluster Method. Computer Journal 16(1).
• Ester, M., Kriegel, H.-P., Sander, J. & Xu, X. (1996). A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. KDD.
• Ankerst, M. et al. (1999). OPTICS: Ordering Points To Identify the Clustering Structure. SIGMOD.
• Shi, J. & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE TPAMI 22(8).
• Ng, A., Jordan, M. & Weiss, Y. (2002). On Spectral Clustering: Analysis and an Algorithm. NeurIPS.
• Kleinberg, J. (2002). An Impossibility Theorem for Clustering. NeurIPS.
• Hubert, L. & Arabie, P. (1985). Comparing Partitions. Journal of Classification 2(1).
• Vinh, N. X., Epps, J. & Bailey, J. (2010). Information Theoretic Measures for Clusterings Comparison. JMLR 11.
• von Luxburg, U. (2007). A Tutorial on Spectral Clustering. Statistics and Computing 17(4).
• Campello, R., Moulavi, D. & Sander, J. (2013). Density-Based Clustering Based on Hierarchical Density Estimates. PAKDD.
• Moulavi, D. et al. (2014). Density-Based Clustering Validation. SDM.

What to learn next#

• Unsupervised learning — k-means in full, and why scaling decides the answer.
• Decision trees — back to labelled data, and a model you can read aloud.
• Autoencoders — learning the space you should be clustering in.