Why Merge Heights Matter
In agglomerative hierarchical clustering, each step joins two current clusters, and the dissimilarity at which they join is their merge height. A dendrogram represents these steps by placing each join at its height. For many familiar linkage rules, each successive merge occurs at least as high as the preceding one. This is the monotonicity property: it keeps the vertical ordering of the dendrogram consistent with the order in which clusters were formed.
Monotonicity is not guaranteed for every linkage rule. In particular, centroid linkage can merge two clusters at a lower dissimilarity than an earlier merge. Such a downward step is called an inversion. Understanding which rules guarantee monotonic heights helps prevent a misleading reading of a dendrogram, especially when a requested cut is defined by a height threshold.
Why Several Linkage Rules Are Monotone
Suppose clusters \(A\) and \(B\) are the pair selected at a step, and their dissimilarity is \(h\). Because the algorithm selects a pair with the smallest current linkage dissimilarity, every other pair of current clusters has dissimilarity at least \(h\). After merging \(A\) and \(B\), the key question is whether the new cluster \(A\cup B\) can be closer to some other cluster \(C\) than \(h\).
For single, complete, and average linkage, the update itself answers that question. Write \(d(A,B)\) for the linkage dissimilarity between two clusters. Their distances to a third cluster update as follows:
Here \(n_A\) and \(n_B\) are the numbers of observations in clusters \(A\) and \(B\). These formulas correspond to nearest-pair distance, farthest-pair distance, and the mean of all cross-cluster pairwise distances, respectively. Since the selected pair has the current minimum height \(h\), both \(d(A,C)\) and \(d(B,C)\) are at least \(h\). Their minimum is therefore at least \(h\), their maximum is at least \(h\), and their weighted average is at least \(h\). No newly updated distance can be below the last merge height. All pairs not involving the new cluster were already at least \(h\), so the next selected merge is also at height at least \(h\).
This argument is a short proof of monotonicity for all three rules. It depends on the rules’ update formulas and the algorithm’s choice of a globally closest current pair; it is not a claim that every possible clustering dissimilarity must be monotone.
Worked Example: Comparing Three Linkage Heights
A hypothetical clustering has three singleton clusters \(A\), \(B\), and \(C\), with pairwise dissimilarities \(d(A,B)=2\), \(d(A,C)=3\), and \(d(B,C)=4\). Determine the two merge heights under single, complete, and average linkage.
Method. For all three rules, \(A\) and \(B\) are the unique closest pair, so the first merge height is \(2\). The second merge joins \(A\cup B\) to \(C\).
Single linkage: \(d_{\mathrm{single}}(A\cup B,C)=\min(3,4)=3\). Its merge heights are \(2\) and \(3\).
Complete linkage: \(d_{\mathrm{complete}}(A\cup B,C)=\max(3,4)=4\). Its merge heights are \(2\) and \(4\).
Average linkage: both clusters being merged at the first step have size one, so \(d_{\mathrm{average}}(A\cup B,C)=(1\cdot3+1\cdot4)/(1+1)=3.5\). Its merge heights are \(2\) and \(3.5\).
Each second height is at least \(2\), as the monotonicity argument requires. The common mistake is to assume all three rules give the same new distance: they use a minimum, maximum, and size-weighted mean, respectively.
Ward Linkage and Its Merge Cost
Ward linkage selects the merge that causes the smallest increase in within-cluster sum of squares. For a cluster \(A\), let \(\bar{x}_A\) be its mean feature vector, and let \(n_A\) be its size. The merge cost is
This is an increase in squared variation, not an ordinary Euclidean distance. Some conventions report a monotone rescaling such as \(\sqrt{2\Delta(A,B)}\); such a rescaling preserves the order of merge heights.
For Ward’s merge cost, the updated cost to a third cluster \(C\) satisfies the Lance–Williams identity
If \(A\) and \(B\) are selected at the current minimum cost \(h=\Delta(A,B)\), then \(\Delta(A,C)\ge h\) and \(\Delta(B,C)\ge h\). Substituting these bounds into the identity gives
Thus Ward merge costs are nondecreasing under this definition. The negative term in the update does not break the result: the two positive terms, together with the fact that the chosen merge has minimum cost, are sufficient to establish the lower bound.
Worked Example: Checking a Ward Merge Schedule
A hypothetical one-dimensional data set has observations at \(0\), \(2\), \(5\), and \(10\). Use Ward’s merge cost \(\Delta\) to find the first two merges and their heights. Then calculate the final merge height to check the schedule.
Method. For singleton observations \(x\) and \(y\), the cost is \(\Delta=\frac{1}{2}(x-y)^2\). The six initial costs are: \(\Delta(0,2)=2\), \(\Delta(0,5)=12.5\), \(\Delta(0,10)=50\), \(\Delta(2,5)=4.5\), \(\Delta(2,10)=32\), and \(\Delta(5,10)=12.5\). Therefore the first merge is \(\{0,2\}\), at height \(2\).
The new cluster has size \(2\) and mean \(1\). Its costs to the remaining singleton clusters are \(\Delta(\{0,2\},5)=\frac{2\cdot1}{3}(1-5)^2=\frac{32}{3}\), and \(\Delta(\{0,2\},10)=\frac{2\cdot1}{3}(1-10)^2=54\). The cost between the remaining singletons is still \(\Delta(5,10)=12.5\). Since \(\frac{32}{3}\approx10.6667<12.5<54\), the second merge joins \(\{0,2\}\) with \(5\), at height \(\frac{32}{3}\).
The resulting cluster has size \(3\) and mean \(\frac{0+2+5}{3}=\frac{7}{3}\). Its cost to \(10\) is \[ \Delta(\{0,2,5\},10)=\frac{3\cdot1}{4}\left(\frac{7}{3}-10\right)^2 =\frac{3}{4}\left(\frac{23}{3}\right)^2 =\frac{529}{12}\approx44.0833. \] The heights are \(2\), \(\frac{32}{3}\), and \(\frac{529}{12}\), in increasing order. The common mistake is to substitute ordinary distances for Ward costs; Ward’s criterion here is the increase in within-cluster sum of squares.
Centroid Linkage Can Produce an Inversion
Centroid linkage defines the dissimilarity between two clusters as the Euclidean distance between their means. After merging \(A\) and \(B\), the mean of \(A\cup B\) is weighted by the cluster sizes:
This mean can lie closer to another cluster’s mean than either of the original clusters did. In the corresponding squared-distance update, a negative term appears:
Unlike the updates for single, complete, and average linkage, this expression is not just a minimum, maximum, or weighted average of distances to \(C\). The subtraction means that the new distance is not guaranteed to be at least the last merge height.
Worked Example: Finding a Centroid-Linkage Inversion
Three hypothetical observations have Euclidean coordinates \(A=(-1,0)\), \(B=(1,0)\), and \(C=(0,1.9)\). Use centroid linkage to determine both merge heights and decide whether an inversion occurs.
Method. First calculate all initial distances. The distance from \(A\) to \(B\) is \(\sqrt{(1-(-1))^2}=2\). The distances from \(A\) to \(C\) and from \(B\) to \(C\) are each \(\sqrt{1^2+1.9^2}=\sqrt{4.61}\approx2.1471\). Thus \(A\) and \(B\) are the unique closest pair, and their first merge height is \(2\).
Their centroid is \(\bar{x}_{A\cup B}=(({-1}+1)/2,(0+0)/2)=(0,0)\). The distance from this centroid to \(C\) is \(\sqrt{(0-0)^2+(1.9-0)^2}=1.9\). The second merge height is therefore \(1.9\), which is less than the first height of \(2\). This is an inversion. The calculation avoids a common mistake: assuming the distance from a new cluster to \(C\) must be at least the previous merge height simply because the clustering process only joins clusters.
Interpreting Heights Carefully
For single, complete, average, and Ward linkage under the definitions above, successive merge heights do not decrease. Centroid linkage has no such guarantee, and the example shows that its heights can decrease. An inversion concerns the numerical heights assigned to successive joins; the clustering still proceeds by merging two current clusters at each step.
When reading a dendrogram, check the linkage rule and its height convention before interpreting a vertical cut. For monotone heights, the height of each join follows the merge order. With an inversion, a later join can be drawn below an earlier one, so the visual vertical order alone does not represent a nondecreasing sequence of merge steps. Also keep the scale in view: Ward’s increase in squared variation and a distance-based height are not numerically interchangeable, even when a particular software convention applies a monotone transformation.
Check Your Understanding
For each problem, calculate the requested height or identify the monotonicity conclusion.
- Three singleton clusters have dissimilarities \(d(A,B)=1.8\), \(d(A,C)=2.6\), and \(d(B,C)=3.4\). Find the second merge height under single, complete, and average linkage. (Answer: single \(2.6\); complete \(3.4\); average \(3.0\).)
- Ward linkage uses \(\Delta(A,B)=\frac{n_An_B}{n_A+n_B}(\bar{x}_A-\bar{x}_B)^2\). For observations \(1\), \(4\), and \(8\), find the first merge, its cost, and the second merge cost. (Answer: first merge \(\{1,4\}\) at \(4.5\); second merge cost \(121/6\approx20.1667\), so the heights are nondecreasing.)
- Under centroid linkage, \(A=(-1,0)\), \(B=(1,0)\), and \(C=(0,1.9)\). Find the two merge heights and classify the result. (Answer: first height \(2\), second height \(1.9\); an inversion occurs.)
- At a current step, \(d(A,B)=2\), \(d(A,C)=2.5\), and \(d(B,C)=5\), with each cluster a singleton. If \(A\) and \(B\) merge first, find the distance from \(A\cup B\) to \(C\) under average linkage and state whether it falls below the first height. (Answer: \(3.75\); no, it is above the first height \(2\).)
- A Ward implementation reports heights \(\sqrt{2\Delta}\) instead of \(\Delta\), where \(\Delta\) is the increase in within-cluster sum of squares. Does that transformation alone change whether the merge heights are nondecreasing? (Answer: no; \(\sqrt{2\Delta}\) is an increasing function of nonnegative \(\Delta\), so it preserves the ordering.)