Why build a hierarchy?
A clustering need not begin with a fixed number of groups. If we merge nearby observations step by step, we obtain a nested family of partitions. A dendrogram records those decisions and lets us inspect several resolutions of the same data. It is a summary of distances, not a proof that nature contains a particular number of groups. Scaling the features or changing the distance may change the entire tree.
Definitions and algorithm
Definition 22.1.1
(Agglomeration and linkage)
Let be a finite nonempty data set with symmetric nonnegative dissimilarities and . Distinct observations may have zero dissimilarity; the triangle inequality is not required here. Start with one cluster per observation. For nonempty disjoint clusters , define
These are single and complete linkage. At each step merge a pair minimizing the chosen linkage, record that value as the merge height, and recompute distances between the new cluster and all others. Continue until one cluster remains. If there is a tie, state a deterministic tie rule; different tied binary trees can encode the same partition at a given height.
For either rule, old distances between unchanged clusters remain unchanged. If and is another cluster, the update is
These follow by splitting the pairs between and into those starting in and those starting in . No center or mean needs to be calculated.
Definition 22.1.2
(Dendrogram and horizontal cut)
The dendrogram of a run is the binary tree of its merges, each drawn at its merge height. The horizontal cut at height is the partition obtained by performing every merge of height at most , including all tied merges at height , and no others.
Proposition 22.1.3
(Merge heights never decrease)
For single and complete linkage, successive merge heights form a nondecreasing sequence. Consequently the cut at height is well defined: the merges of height at most are exactly an initial segment of the run.
Proof
(Why every later distance is at least the last merge height)
Suppose and are merged at height , the smallest current intercluster distance. Before the merge, every distance between two current clusters is at least . After it, distances between unchanged clusters are still at least , and each new distance is the minimum or the maximum of two old distances that are both at least , so it is at least as well. Every distance available at the next step is therefore at least , and the next merge height is at least .
A graph theorem for single linkage
Theorem 22.1.4
(Threshold components)
Fix . Form a graph whose vertices are the observations, joining and exactly when . The clusters produced by single linkage after all merges at height at most are exactly the connected components of this graph, irrespective of tie-breaking.
Proof
(Both inclusions)
Every single-link merge at height at most has an edge of the threshold graph between its two clusters. Inductively each resulting cluster lies within a graph component. Conversely, after no such merge remains, an edge between two distinct clusters would make their single-link distance at most , a contradiction. Along any graph path every consecutive pair must therefore lie in the same cluster, so the whole component lies in one cluster. The two inclusions prove equality.
Proof X-ray
Where chaining enters
The theorem uses paths, not pairwise closeness: the endpoints of a path may be far apart even though each edge is short. Complete linkage controls the largest cross-cluster distance at each merge and answers a different question. A threshold graph alone does not generally recover the complete-link partition.
Worked examples
Worked example 22.1.5
(Single and complete linkage on four points)
Take the real-line observations with absolute distance. The unique first merge is at height . For single linkage, the distances from to and are and ; the distance from to is . Merge next at , then merge at . For complete linkage the corresponding distances are and ; merge at , then merge at . Thus at cut single linkage has clusters and , whereas complete linkage has , and . The same observations can give different trees because linkage is part of the model.
Worked example 22.1.6
(Zero dissimilarities and the cut at height zero)
Take the real-line observations with absolute distance, so the first two observations are distinct but have dissimilarity zero. At height they merge, so the cut at is for both linkages, and the threshold graph at has the same components. Under either linkage the distances from to and are and , and , so and merge at height . The last merge differs: single linkage uses and complete linkage uses . The cut at is therefore one cluster under single linkage but under complete linkage. Zero is a legitimate merge height, and the cut at zero need not be the partition into singletons.
Worked example 22.1.7
(A tie that matters for complete linkage but not for single linkage)
Take with absolute distance. The pairs and tie at distance . Under single linkage, after either first merge the other tied pair is still at distance : for example . So both merges occur at height and the cut at is in either order, as the threshold-graph theorem says. Under complete linkage, merging first gives , and merging first gives . Hence the cut at is or depending on the tie rule, while the cut at is one cluster in both cases. A complete-link result at a tied height is only reproducible if the tie rule is stated.
Counterexample mode
A connected chain is not a compact cluster
For on the line, at threshold single linkage produces one cluster: the edges –, –, and – form a path. Yet its diameter is , not . Thus a cut height bounds the edges needed to connect a single-link cluster, not every pairwise distance. For complete linkage, in contrast, every cluster at a nonnegative cut has diameter at most the cut height: prove this inductively, using the maximum cross-distance at a merge.
Using the hierarchy responsibly
A dendrogram is built from the same sample being interpreted. A large vertical gap can suggest a cut to investigate, but does not establish statistical significance or predict performance on future data. Standardizing variables can be sensible when their measurement units differ, but may also remove meaningful scale information. Missing values require an explicit treatment before distances are computed. A new observation is not automatically placed by the old tree: recomputing the hierarchy can even change earlier merges. For large data sets the pairwise distance matrix takes quadratic storage; implementations may exploit special structure, but should not be assumed to do so.
Concept lensCombinatorial
Single linkage as a minimum spanning tree
Single-link merge heights are exactly the edge weights of a minimum spanning tree of the complete graph with weights , sorted increasingly: each merge adds the cheapest edge joining two current clusters. On the tree has edges –, – and – of weights , the merge heights found above.
Common mistake
(The left-to-right order of leaves carries no distance information)
Swapping the two children of any merge gives another valid drawing of the same tree. For single linkage on the leaves may be drawn in the order or, after swapping the two children of the last merge, . In the second drawing sits next to although is the largest dissimilarity. Only the height at which two observations first lie in one cluster is meaningful, not how close their leaves are drawn.
Exercises
Quick check
(On with absolute distance, calculate the complete-link merge heights and the clusters at cut .)
Compute all six pairwise distances first.
Solution · Answer
First merge at . The distances from to and are and , while . Merge at ; the maximum cross-distance between the two resulting pairs is , the last height. At cut the clusters are and .
Exercise 22.1.8
(For dissimilarities as defined above and , prove that every complete-link cluster in the cut at has diameter at most .)
CoreProof
Hint(1)
Use induction over the merges of height at most , and split the pairs inside a merged cluster.
Solution(3)
- 1
Start the induction with singletons
Singleton clusters have diameter , because .
- 2
Bound the cross-distances at a merge
If and merge at height , then for all and . By the inductive hypothesis, pairs inside and pairs inside also have distance at most .
Because: A complete-link merge height equals the maximum cross-distance.
- 3
Conclude for the merged cluster
∎Two points of lie both in , both in , or one in each, and in every case their distance is at most . The cut contains only merges of height at most , so every cluster in it has diameter at most .
Quick check
(Suppose all off-diagonal dissimilarities of four observations equal . Does tie-breaking change the clusters at cuts and under single linkage?)
Compare with the threshold graph.
Solution · Answer
Below there are four singleton clusters. At and above all four are in one cluster. The binary order of tied merges can differ, but the threshold graph is complete at , so its component partition is unique.