Hierarchical Clustering

A dendrogram is a rooted binary tree whose leaves are the individual data points and whose internal nodes represent merges of clusters, each internal node labeled with the distance (or dissimilarity) at which its two children were joined. Cutting the tree horizontally at any height $h$ induces a flat partition: all points connected below that cut belong to the same cluster. Because the tree is monotone (heights strictly increase, or at least do not decrease, as we move from leaves to root, under standard linkages), every horizontal cut yields a well-defined partition, and different cuts give a nested family of partitions ordered by refinement.

Agglomerative clustering starts with every point as its own singleton cluster and repeatedly merges the two clusters that are "closest" according to a chosen linkage criterion, until only one cluster remains. The linkage criterion extends a point-to-point distance metric (Euclidean, Manhattan, cosine, etc., as covered in Distance Metrics and Similarity Measures) into a cluster-to-cluster distance $D(A, B)$ between sets of points $A$ and $B$. The four standard choices are:

• Single linkage: $D(A,B) = \min_{a \in A, b \in B} d(a,b)$ — distance between the closest pair.
• Complete linkage: $D(A,B) = \max_{a \in A, b \in B} d(a,b)$ — distance between the farthest pair.
• Average linkage (UPGMA): $D(A,B) = \frac{1}{|A||B|} \sum_{a \in A, b \in B} d(a,b)$ — mean pairwise distance.
• Ward's method: merges the pair that produces the smallest increase in total within-cluster variance (sum of squared deviations from centroids).

Divisive clustering runs the opposite direction: start with all points in one cluster and recursively split the least homogeneous cluster into two, typically using a flat clustering subroutine like 2-means or a graph-cut criterion at each step, until every point is its own cluster (or a stopping rule fires). Divisive methods can, in principle, produce better top-level splits because they consider the global structure of the whole dataset before committing to a division, but the search space for the best split of a cluster of size $m$ is exponential ($2^{m-1}-1$ possible bipartitions), so practical divisive algorithms use heuristics and are far less common than agglomerative ones.

The agglomerative procedure is a greedy algorithm operating on a proximity matrix — the $n \times n$ matrix of pairwise distances between current clusters, updated after every merge. ``` ALGORITHM AgglomerativeClustering(X, n, linkage) Input: X = {x_1, ..., x_n} // n data points linkage // one of SINGLE, COMPLETE, AVERAGE, WARD Output: dendrogram as a sequence of n-1 merge records // 1. Initialize: each point is its own cluster clusters <- { {x_1}, {x_2}, ..., {x_n} } active <- {1, 2, ..., n} // ids of currently "live" clusters D <- n x n matrix, D[i][j] = pairwise_distance(x_i, x_j) size[i] <- 1 for all i // cluster cardinalities (for Ward/average) merges <- empty list next_id <- n + 1 // new clusters get fresh ids // 2. Repeat n-1 times: merge the closest pair, update distances for step = 1 to n - 1: (i, j) <- argmin over i < j in active of D[i][j] h <- D[i][j] // merge height record (i, j, h) in merges new_cluster <- next_id active <- active \ {i, j} // 3. Update distances from the new cluster to all remaining ones // using the Lance-Williams recurrence (see below) for k in active: D[new_cluster][k] <- lance_williams(linkage, D, i, j, k, size) size[new_cluster] <- size[i] + size[j] active <- active U { new_cluster } next_id <- next_id + 1 return merges // n-1 records fully describe the dendrogram ``` The heart of the update step is the Lance–Williams recurrence, a single formula that computes the distance from a newly merged cluster $A \cup B$ to any other cluster $C$ without recomputing all pairwise distances from scratch:

Each linkage rule is just a choice of the coefficients $\alpha_A, \alpha_B, \beta, \gamma$:

where $n_A, n_B, n_C$ are cluster sizes. This recurrence is what makes the algorithm practical: updating one row/column of the proximity matrix after a merge takes $O(n)$ time rather than $O(n^2)$, and it is provably equivalent to recomputing the linkage distance directly from the point sets (a short induction on each linkage's definition confirms this, e.g., for single linkage $\min(D(A,C), D(B,C)) = \frac{1}{2}D(A,C)+\frac{1}{2}D(B,C)-\frac{1}{2}|D(A,C)-D(B,C)|$ is just the identity $\min(x,y) = \frac{x+y}{2}-\frac{|x-y|}{2}$). The output — the sequence of $n-1$ merges, each with its height — is exactly enough information to draw the full dendrogram, since it specifies, in order, which two clusters merge and at what dissimilarity.

Time complexity. The naive implementation above scans the full $n \times n$ proximity matrix at every one of the $n-1$ steps to find the global minimum, costing $O(n^2)$ per step and $O(n^3)$ overall. This can be improved: maintaining a priority queue (e.g., a nearest-neighbor heap per cluster) reduces the search for the minimum to $O(\log n)$ amortized per merge, and the Lance–Williams update touches $O(n)$ entries per merge, giving an $O(n^2 \log n)$ algorithm; for single and complete linkage, the specialized SLINK and CLINK algorithms achieve the information-theoretic optimum of $O(n^2)$ time and $O(n)$ additional space beyond the input, by exploiting the fact that only nearest-neighbor chains need to be tracked. In practice, most general-purpose libraries implement the $O(n^2 \log n)$ or $O(n^3)$ variants because they support arbitrary linkages.

Space complexity. The proximity matrix requires $O(n^2)$ space regardless of the time-optimization used, since all pairwise cluster distances must be available for merging; this is the dominant practical bottleneck, making naive hierarchical clustering infeasible much beyond $n \sim 10^4$–$10^5$ points without approximations (e.g., first pre-clustering with a cheap method, or restricting to a sparse $k$-nearest-neighbor graph).

Why the algorithm is correct. "Correctness" here means the produced dendrogram faithfully represents the greedy nested-merge structure defined by the linkage rule — there is no separate ground truth to converge to, since hierarchical clustering is defined by the procedure. The key invariant is: at every step, the proximity matrix entry $D[i][j]$ for any two active clusters $i,j$ equals the true linkage distance between the point sets they represent. This holds by induction — the base case is trivial ($D$ initialized from the raw metric), and the Lance–Williams recurrence is constructed precisely so that the inductive step reproduces each linkage's definition exactly (as shown algebraically above for single linkage; analogous identities hold for complete, average, and Ward). Given this invariant, greedily picking the global minimum at each step is exactly "merge the two currently-closest clusters," which is the definition of agglomerative clustering — so the algorithm computes precisely what it claims to.

Monotonicity caveat. For single, complete, and average linkage, merge heights are guaranteed non-decreasing as the algorithm proceeds — a consequence of the fact that adding points to a cluster can only keep the min the same or smaller in one direction and never smaller in the relevant aggregate sense for these three rules — so the dendrogram never exhibits an "inversion" where a later merge occurs at a lower height than an earlier one. Ward's method is also monotone in practice for Euclidean data, though pathological centroid-based variants (centroid linkage, median linkage) can produce inversions, a known defect that makes those two linkages harder to interpret visually.

Tradeoffs across linkages.

• Single linkage is $O(n^2)$-computable exactly (via SLINK) and is invariant to monotone transformations of distance, but is notorious for chaining: a thin bridge of intermediate points can fuse two otherwise well-separated blobs into one elongated cluster.
• Complete linkage avoids chaining by penalizing the worst-case pair, producing compact, roughly equal-diameter clusters, but is sensitive to outliers (one distant point inflates $D(A,B)$ for the whole cluster) and tends to break large clusters apart.
• Average linkage is a compromise, less chain-prone than single and less outlier-sensitive than complete, but its results depend on the distance metric's scale in ways that are harder to reason about geometrically.
• Ward's method minimizes the increase in total within-cluster variance at each merge — the hierarchical analogue of k-Means Clustering's objective — and tends to produce balanced, spherical clusters; it implicitly assumes Euclidean geometry and squared distances, so it is not well-defined for arbitrary non-Euclidean dissimilarities.

Consider six points in 1-D for clarity of arithmetic: $A=1, B=2, C=4, D=5, E=9, F=10$. We use Euclidean distance and single linkage, and trace every merge.

Step 0 — initial distance matrix (absolute differences):

Step 1. Global minimum is $D(A,B)=1$ (tied with $D(C,D)=1$ and $D(E,F)=1$; ties broken by index order here). Merge $A,B \to G_1 = \{A,B\}$ at height $1$. Update, single linkage: $D(G_1, C) = \min(D(A,C), D(B,C)) = \min(3,2) = 2$; $D(G_1,D)=\min(4,3)=3$; $D(G_1,E)=\min(8,7)=7$; $D(G_1,F)=\min(9,8)=8$.

Step 2. Remaining minimum is $D(C,D)=1$. Merge $C,D \to G_2=\{C,D\}$ at height $1$. Update: $D(G_1,G_2)=\min(D(G_1,C),D(G_1,D))=\min(2,3)=2$; $D(G_2,E)=\min(D(C,E),D(D,E))=\min(5,4)=4$; $D(G_2,F)=\min(6,5)=5$.

Step 3. Remaining minimum is $D(E,F)=1$. Merge $E,F \to G_3=\{E,F\}$ at height $1$. Update: $D(G_1,G_3)=\min(7,8)=7$; $D(G_2,G_3)=\min(4,5)=4$.

Step 4. Remaining pairs: $D(G_1,G_2)=2$, $D(G_1,G_3)=7$, $D(G_2,G_3)=4$. Minimum is $D(G_1,G_2)=2$. Merge $G_1,G_2 \to G_4=\{A,B,C,D\}$ at height $2$. Update: $D(G_4,G_3) = \min(D(G_1,G_3), D(G_2,G_3)) = \min(7,4) = 4$.

Step 5. Only pair left: $D(G_4,G_3)=4$. Merge everything into the root at height $4$.

Final merge sequence (the dendrogram, in order):

Cutting this dendrogram at height $h=3$ (between step 4 and step 5) yields the 2-cluster partition $\{A,B,C,D\}$ and $\{E,F\}$ — exactly the two visually obvious blobs in the raw coordinates, confirming the algorithm recovered the correct structure. Cutting instead at $h=1.5$ recovers three clusters, $\{A,B\}, \{C,D\}, \{E,F\}$, matching the three tight pairs. This illustrates the central payoff of hierarchical clustering: one computation, many valid answers, chosen post hoc by where you cut.

Hierarchical clustering's roots lie less in computer science proper and more in numerical taxonomy and psychometrics, where researchers needed a principled way to group specimens or survey respondents from measured attributes alone. The method's popularity surged with the rise of microarray gene-expression analysis in the late 1990s and 2000s, where the clustered heatmap — rows and columns each reordered by their own dendrogram — became a near-universal visualization for exploring which genes and which samples behave similarly, cementing hierarchical clustering's place as a default first step in exploratory data analysis across biology, marketing analytics, and document clustering.

Bioinformatics pipelines use hierarchical clustering constantly: clustering genes by co-expression pattern, samples by similarity, or species by sequence divergence to build phylogenetic-style trees. Document and text-mining systems use it to build topic hierarchies without pre-specifying a topic count, often as a precursor to labeling clusters for search or recommendation. Market segmentation teams use it to explore customer bases at multiple granularities — broad segments for strategy, fine segments for targeted campaigns — using the same dendrogram. Image and signal processing pipelines use agglomerative merging for region-growing segmentation, where pixels or superpixels are merged based on color or texture similarity. Statistical software (R's `hclust`, Python's `scipy.cluster.hierarchy`, `scikit-learn`'s `AgglomerativeClustering`) ships hierarchical clustering as a default exploratory tool precisely because it needs no assumption about cluster count, complementing centroid-based methods like k-Means Clustering and forming the natural bridge to the practical question of Choosing the Number of Clusters once a dendrogram is in hand.

Ask the tutor: How does the choice of linkage criterion change which points get merged first when clusters have very different sizes?