Understanding Hierarchical Clustering
Agglomerative clustering starts with every observation as a cluster of one and repeatedly fuses the two least dissimilar clusters until a single cluster remains. The dissimilarity at which each fusion happens is recorded as its height, and the resulting record of fusions is the dendrogram.
Cutting the dendrogram horizontally produces a clustering, and the number of vertical lines the cut crosses is the number of clusters. A single tree therefore contains an answer for every k at once, which is the main practical advantage over k-means. The clusterings obtained this way are nested, each cut refining the one above it.
That nesting is an assumption rather than a bonus. The method insists that the clusters at one level sit inside the clusters at the level above, so if the true grouping is not nested - if the best split by one attribute cuts across the best split by another - no cut of the tree will recover it, and a hierarchy will be imposed on data that has none.
Fusing requires a dissimilarity between groups rather than between points, and there is no single correct way to extend one to the other. Complete linkage uses the largest distance between a point of one group and a point of the other, single linkage the smallest, average linkage the mean, and centroid linkage the distance between the two centroids. The choice changes the answer, not merely its presentation.
How to Calculate
complete: max d(a, b) single: min d(a, b) average: mean d(a, b), a ∈ A, b ∈ B
where
- A, B
- the two clusters whose dissimilarity is being measured
- d(a, b)
- the dissimilarity between an individual observation of A and one of B
- height
- the value of that group dissimilarity at the moment the two clusters fuse
Example of Hierarchical Clustering
Take ten points in the plane: a compact group of three on the left, a compact group of three on the right, and four evenly spaced points bridging them. Cut each dendrogram into two clusters and the linkages disagree. Complete and average linkage both split the data 5 and 5, down the middle of the bridge. Single linkage gives 3 and 7.
The reason is the definition rather than an implementation detail. Single linkage fuses on the smallest distance, so each bridge point attaches one at a time to the growing blob, and the chain drags an entire group along with it - a trailing cluster. Complete and average linkage consider the largest and mean distances, so they refuse to fuse groups that are far apart overall.
James and colleagues report this as the general pattern: single linkage tends to yield trailing clusters, while complete and average linkage produce more balanced dendrograms. Centroid linkage has a defect of its own, an inversion, in which two clusters fuse at a height below one of the individual clusters, making the tree hard to read.
Advantages and Disadvantages
Pros
- No need to commit to the number of clusters before fitting.
- The dendrogram is an interpretable summary of structure at every scale at once.
- Deterministic: unlike k-means there is no random initialization to restart from.
- Works from a dissimilarity matrix alone, so it applies wherever a sensible distance exists.
Cons
- Imposes a nested hierarchy whether or not the data has one.
- The linkage and dissimilarity choices change the result, and neither can be selected from the data.
- A fusion is never reconsidered, so an early mistake propagates to the whole tree.
- Cost grows quickly with the number of observations, which limits it on large datasets.
Frequently Asked Questions
How is a dendrogram read correctly?
Only by fusion height. Two observations that fuse low down are similar; two that fuse near the top are not. Horizontal position carries no information at all - the leaves can be reordered freely without changing the tree, so observations sitting side by side may join only at the very top.
Which linkage should be used?
Complete or average linkage by default, because they tend to give balanced dendrograms. Single linkage is worth avoiding unless chaining is genuinely what you want to detect, and centroid linkage can produce inversions that make the tree unreadable.
How is the number of clusters chosen?
By deciding where to cut, which is a judgement rather than a computation. There is no held-out error to validate against, so the honest practice is to try several sensible sets of choices and report the structure that appears under most of them.
The Bottom Line
Hierarchical clustering removes the need to fix k in advance and replaces it with the linkage, the dissimilarity measure, and the cut height - none of which the data can choose for you. Read similarity from fusion heights only, prefer complete or average linkage, and treat the tree as one hypothesis about structure rather than a finding.