Linkage and Dendrograms

## The algorithm Agglomerative (bottom-up) hierarchical clustering begins with `n` clusters, one per observation, and then repeats one step: find the two clusters that are closest under a chosen linkage rule, merge them, and record the distance at which they merged. After `n - 1` merges everything sits in a single cluster and the run ends. The important consequence is that the output is not a partition. It is a nested family of partitions, from `n` singletons at the bottom to one all-inclusive group at the top, with the property that every cluster at one level is wholly contained in a cluster at the next. That nesting is what makes the result drawable as a tree. ## Reading the picture A dendrogram plots the observations as leaves along one axis and merge distance along the other (conventionally vertical). Each merge is drawn as a bracket joining two subtrees, and the bracket sits at the height equal to the linkage distance between the two clusters at the moment they were joined. From that, three readings are legitimate: - **Height of a join** = how far apart the two groups were when merged. Low joins are strong groupings; high joins are reluctant ones. - **Vertical gaps** = separation. If nothing merges between height 1.2 and height 4.0, the structure present just below 4.0 survived a wide range of thresholds, which is the visual signature of well-separated groups. - **Membership** = which leaves sit under a given bracket. That is the cluster the bracket defines. And one reading is illegitimate: **leaf order carries no information**. At every join you may swap the left and right subtree and the tree is unchanged, so there are `2^(n-1)` equally valid orderings of the leaves. Two leaves printed next to each other may be joined only at the very top of the tree. Plotting tools pick some ordering, and people routinely over-interpret it. ## Monotone heights For the standard rules — single, complete, average and Ward linkage — merge heights never decrease as you go up the tree, because merging two clusters can only push the next-nearest distance up or leave it the same. This is why the picture reads cleanly and why a horizontal line across it means something. Some less common rules (centroid and median linkage) are not monotone and can produce inversions, where a later merge is drawn *below* an earlier one. ## Agglomerative versus divisive The top-down mirror image is divisive clustering: start with one cluster containing everything and recursively split. It is far rarer in practice, and the reason is combinatorial. Splitting a group of `m` points optimally means searching `2^(m-1) - 1` possible two-way splits, so exact divisive clustering is intractable and practical versions (DIANA is the classic one) rely on heuristics for choosing what to split off. Agglomerative clustering, by contrast, only ever has to scan pairs of current clusters. The one theoretical argument for divisive methods is that the top of the tree — the coarse structure most people actually use — is decided by a global look at the data rather than by a long chain of local greedy merges. ## What you get out of it Because a hierarchy is not a clustering, using the result requires a second decision: cutting the tree at a height, or equivalently stopping the merge sequence after `n - k` merges to leave `k` clusters. That is a separate step with its own judgment. The compensating advantage is that a single run gives you every granularity at once — you can inspect a two-cluster view and a twelve-cluster view of the same data without refitting anything, which is why hierarchical clustering is so common in exploratory work where nobody has committed to a number yet. The costs are also structural. The method is greedy and has no undo: a merge made early is never revisited, even if later evidence shows it was wrong. And it needs the pairwise distances among all current clusters, which is why memory grows quadratically with the number of observations.