Hierarchical Clustering and Dendrograms
Merge the two closest clusters, repeat, and keep the whole tree. Choose how many clusters you want afterwards.
Overview
The algorithm
Agglomerative clustering is almost trivially simple:
- Every point starts as its own cluster.
- Find the two closest clusters and merge them.
- Repeat until one cluster remains.
Recording the distance at each merge gives a dendrogram — the chart above plots exactly that: merge number against the distance at which it happened.
Hierarchical Clustering and Dendrograms
Worth knowing
Hierarchical Clustering and Dendrograms
Building the whole tree once, and choosing how many clusters you want after seeing it.
The point: k comes last
K-means and DBSCAN both need a decision before they run — how many clusters, or how dense. Hierarchical clustering needs neither. It builds one tree, and a horizontal cut through it produces a clustering.
Drag the cut height and watch the count change. A cut low down leaves many small clusters, a cut high up leaves few, and the tree itself never changed. That is genuinely useful when you do not know what structure to expect, because you can look at the merge distances before committing.
Large jumps in the curve are informative: a merge that costs much more than the one before it joined two things that were not really close. Cutting just below a big jump is the dendrogram equivalent of the [elbow](choosing_k.html).
Linkage changes everything
The algorithm needs a distance between two *clusters*, not two points, and there is no single right answer. Switch the control and the shape of the curve changes substantially.
Single linkage — distance between the nearest pair. Merges cheaply whenever any two members are close, so it can follow elongated shapes. Its failure mode is chaining: two well-separated blobs joined by a thin bridge of points merge into one, because the bridge provides a short hop at every step.
Complete linkage — distance between the furthest pair. A merge is only cheap if *every* member of one cluster is close to every member of the other, so clusters come out compact and roughly equal in diameter. It breaks up elongated structures that genuinely belong together, and is sensitive to outliers, since one distant member sets the whole distance.
Average linkage — the mean over all cross-pairs. Between the two, and the usual default.
Ward linkage, not offered here, merges the pair that increases within-cluster variance least. It behaves much like k-means and is the most common choice for roughly spherical clusters.
| Linkage | Produces | Fails at |
|---|---|---|
| Single | elongated, chain-following | bridges between clusters |
| Complete | compact, similar sized | genuinely elongated clusters |
| Average | a compromise | nothing dramatic |
| Ward | spherical, balanced | non-convex shapes |
Reading a real dendrogram
A conventional dendrogram draws each merge as a bracket at its height, with the leaves at the bottom. Two things are worth knowing about reading one.
Height is meaningful; horizontal position is not. The left-to-right order is chosen to keep the drawing untangled and carries no information. Two adjacent leaves are not necessarily similar.
The tree is greedy and permanent. Once two clusters merge they never separate, so an early mistake — two points joined because of noise — propagates all the way up. Hierarchical clustering does not revisit decisions.
Cost
The naive algorithm is O(n³), and careful implementations reach O(n² log n) with O(n²) memory for the distance matrix. That memory is usually the binding constraint: 100,000 points is a matrix of ten billion distances.
This is why hierarchical clustering is a small-to-medium-data method. Above a few tens of thousands of points, k-means or a sampled variant is the practical choice.
Linkage, on two little clusters
"There is no single right answer" for the distance between two clusters is easiest to see on numbers. Cluster A = {0, 1}, cluster B = {5, 9}. The four cross-pair distances are 5, 9, 4, 8, and each linkage reads a different one:
| linkage | cluster distance | from |
|---|---|---|
| single (nearest pair) | 4 | 1 to 5 |
| complete (furthest pair) | 9 | 0 to 9 |
| average (mean of all four) | 6.5 | (5+9+4+8)/4 |
Single linkage merges as soon as *any* two members are close, which lets it follow an elongated shape but also lets a thin bridge of points chain two separate blobs into one. Complete linkage merges only when *every* member is close, giving compact clusters but breaking genuinely stretched ones and taking its distance from a single furthest outlier. Average sits between them and is the usual default. The same three points would cut the tree at three different heights, which is why the dendrogram's shape — and any k read off it — changes completely with the linkage rule, before the data has changed at all. And the whole thing carries an O(n²) distance matrix: 100,000 points is ten billion distances, which is the memory wall that keeps this a small-to-medium-data method.
Two more properties are worth carrying. The tree is *greedy and permanent*: once two clusters merge they never separate, so a mistake made early — two points joined because of noise — rides all the way up the dendrogram, because the algorithm never revisits a decision. And the left-to-right order of the leaves carries no information; it is chosen only to keep the drawing untangled, so two adjacent leaves are not necessarily similar. Height in the diagram is meaningful — it is the distance at which a merge happened, and a large vertical jump means two things that were not really close were forced together — but horizontal position is decoration.
Ward linkage, not among the three above, merges the pair that increases within-cluster variance least; it behaves much like k-means and is the usual choice for roughly spherical clusters, which rounds out the rule of thumb — single for elongated shapes, complete for compact ones, average as a safe middle, Ward when the clusters are blobs.
Where it goes wrong
Not scaling the features. As with every distance-based method.
Using single linkage on data with any bridge between clusters. Chaining will merge them.
Reading meaning into leaf order. It is a drawing convention.
Trying it on a large dataset. The distance matrix will not fit.
Cluster without choosing k first
Agglomerative clustering merges the two closest groups over and over, so you get every k at once. The linkage rule decides what "closest" means, and it changes the answer completely.
Check yourself
0 of …Answer without scrolling back up.
What is the advantage of building the whole tree?
What is chaining, and which linkage causes it?
Why is hierarchical clustering impractical for large datasets?
Hierarchical Clustering and Dendrograms
Recording the distance at each merge gives a dendrogram — the chart above plots exactly that: merge number against the distance at which it happened.