Why Centroid Linkage Can Produce an Inversion
A hierarchical dendrogram is easiest to read when every successive merge occurs at a height at least as large as the preceding merge. Centroid linkage does not guarantee this order. After a merge, the new cluster is represented by its centroid, and that centroid can be closer to another cluster than the height of the merge that created it. The resulting decrease in merge height is called an inversion.
This is more than a graphical curiosity. A dendrogram can still show the nested sequence of merges, but its vertical heights no longer behave like an ordinary increasing dissimilarity threshold. In particular, a horizontal cut may fail to recover a partition that did occur during the agglomeration process.
Assume the observations have numeric feature vectors and Euclidean distance is the chosen dissimilarity. For a cluster \(C\) with \(n_C\) observations \(x_1,\ldots,x_{n_C}\), its centroid is \(\bar{x}_C=(1/n_C)\sum_{j=1}^{n_C}x_j\). The linkage height for clusters \(C\) and \(D\) is \(d(C,D)=\|\bar{x}_C-\bar{x}_D\|_2\). Unless otherwise stated, heights below use ordinary Euclidean distance, not squared Euclidean distance.
The weighted update matters: a cluster containing more observations contributes more to the merged centroid. Centroid linkage is not the same as taking an unweighted average of the two cluster centroids unless the clusters have equal sizes. It is also distinct from Ward linkage, even though both methods use cluster summaries and may be associated with squared-Euclidean calculations under particular conventions.
Worked Example: A Three-Point Inversion
Worked Example: A Three-Point Inversion
A hypothetical portfolio analyst represents three customer segments by two standardized features. Their feature vectors are \(A=(-1,0)\), \(B=(1,0)\), and \(C=(0,1.9)\). Using Euclidean centroid linkage, find both merges and determine whether the dendrogram has an inversion.
Method. Initially each observation is its own cluster, so the first candidate heights are the three pairwise Euclidean distances.
\(\ d(A,B)=\sqrt{(1-(-1))^2+(0-0)^2}=\sqrt{4}=2.\)
\(\ d(A,C)=\sqrt{(0-(-1))^2+(1.9-0)^2}=\sqrt{1+3.61}=\sqrt{4.61}\approx2.1471.\)
\(\ d(B,C)=\sqrt{(0-1)^2+(1.9-0)^2}=\sqrt{1+3.61}=\sqrt{4.61}\approx2.1471.\)
The unique smallest distance is \(d(A,B)=2\), so \(A\) and \(B\) merge first at height 2. Their merged centroid is \(\bar{x}_{AB}=((-1+1)/2,(0+0)/2)=(0,0)\).
There is now one candidate merge, between cluster \(AB\) and observation \(C\): \(\ d(AB,C)=\sqrt{(0-0)^2+(1.9-0)^2}=1.9.\) Thus \(AB\) merges with \(C\) at height 1.9. The heights decrease from 2 to 1.9, so this is an inversion.
Check. The original nearest pair was uniquely \(A,B\), because \(2<2.1471\). The second height is the distance from the recomputed centroid \((0,0)\) to \(C\), namely 1.9. Both calculations use ordinary Euclidean distance. A common mistake is to reuse \(d(A,C)\) or \(d(B,C)\) after the first merge rather than calculate the distance from the new centroid.
Why the Decrease Is Geometrically Possible
The preceding configuration is not accidental. A short calculation gives the range of heights that produces an inversion. Place two observations at \(A=(-a,0)\) and \(B=(a,0)\), where \(a>0\), and a third at \(C=(0,h)\), where \(h>0\). The first pair has distance \(2a\), while each of the other two pairwise distances is \(\sqrt{a^2+h^2}\).
Require \(2a<\sqrt{a^2+h^2}\). Squaring both positive sides gives \(4a^2<a^2+h^2\), so \(h>\sqrt{3}a\).
The centroid of \(A,B\) is \((0,0)\). Its distance to \(C\) is \(h\).
The second height is below the first exactly when \(h<2a\).
Together, \(\sqrt{3}a<h<2a\) ensures that \(A,B\) form the first merge and that the next merge is lower. For the worked example, \(a=1\) and \(h=1.9\): since \(\sqrt{3}\approx1.732<1.9<2\), the condition holds. The geometry explains the mechanism: the merged centroid lies between \(A\) and \(B\), so it can be relatively close to \(C\), even though neither \(A\) nor \(B\) was close enough to \(C\) to merge first.
Worked Example: Recomputing Centroids in Two Dimensions
Worked Example: Recomputing Centroids in Two Dimensions
A hypothetical service team summarizes four regions by two scaled measurements: \(A=(0,0)\), \(B=(0,2)\), \(C=(4,0)\), and \(D=(4,3)\). Apply centroid linkage, list the merge heights, and decide whether an inversion occurs.
Method. First calculate all six singleton distances. They are \(d(A,B)=2\), \(d(A,C)=4\), \(d(A,D)=5\), \(d(B,C)=\sqrt{20}\approx4.4721\), \(d(B,D)=\sqrt{17}\approx4.1231\), and \(d(C,D)=3\). The smallest is 2, so \(A\) and \(B\) merge first.
Their centroid is \(\bar{x}_{AB}=(0,1)\). The remaining candidate distances are \(d(AB,C)=\sqrt{(0-4)^2+(1-0)^2}=\sqrt{17}\approx4.1231\), \(d(AB,D)=\sqrt{(0-4)^2+(1-3)^2}=\sqrt{20}\approx4.4721\), and \(d(C,D)=3\). Therefore \(C,D\) merge second, at height 3.
Now \(\bar{x}_{CD}=((4+4)/2,(0+3)/2)=(4,1.5)\). The final merge height is \(\ d(AB,CD)=\sqrt{(0-4)^2+(1-1.5)^2}=\sqrt{16.25}\approx4.0311.\) The full schedule is: \(A,B\) at 2; \(C,D\) at 3; \(AB,CD\) at approximately 4.0311. It is increasing, so this dataset has no inversion.
Check. The final centroid uses the mean of all four observations, equivalently the size-weighted mean of the two size-2 centroids. The final distance is greater than 3, as the computed value \(4.0311\) confirms. A common mistake is to compare only original point-to-point distances after the first merge; the linkage rule instead requires distances between the current cluster centroids.
Reading the Inverted Dendrogram and Cutting It
For the three-point example, the merge history is unambiguous: first \(A\) joins \(B\) at height 2; then \(C\) joins \(AB\) at height 1.9. After the first merge, the agglomeration schedule has the two-cluster partition \(\{A,B\},\{C\}\). The dendrogram records that history, but the parent merge is drawn lower than the \(AB\) merge. Its branch therefore descends from height 2 to height 1.9.
This creates a limitation for horizontal cuts. In a monotone dendrogram, increasing a cut height ordinarily moves through successive agglomeration stages. Here no horizontal threshold gives the intermediate two-cluster partition. For a threshold below 2, the first merge at height 2 has not yet occurred. For a threshold at or above 2, the first and second merge heights are both at or below the threshold, so all three observations have joined. In particular, a cut at 1.95 leaves three singletons, even though the agglomeration schedule has a two-cluster stage.
This distinction matters when interpreting a dendrogram for a risk-modeling application. If an analyst expects a cut to produce a specified number of clusters, the tree structure and the merge schedule should be checked rather than assuming that a height threshold will recover the same partition. A fixed-cluster-count procedure follows the agglomeration sequence; a threshold cut uses heights. With inversions, those procedures need not agree at every stage.
Worked Example: What a Threshold Can and Cannot Recover
Worked Example: What a Threshold Can and Cannot Recover
Use the three segments \(A=(-1,0)\), \(B=(1,0)\), and \(C=(0,1.9)\). An analyst wants two clusters and proposes a horizontal cut at height 1.95. Determine the partition from the threshold and compare it with the two-cluster stage in the merge schedule.
Method. The pairwise singleton distances are 2, \(\sqrt{4.61}\approx2.1471\), and \(\sqrt{4.61}\approx2.1471\). None is at most 1.95, so a threshold-based rule that joins clusters at heights at most 1.95 has not reached the first merge. The resulting partition is \(\{A\},\{B\},\{C\}\), with three clusters.
The schedule-based two-cluster stage occurs after \(A\) and \(B\) merge at height 2, giving \(\{A,B\},\{C\}\). The next scheduled merge is at 1.9. Since the target partition requires including the height-2 merge but excluding the later height-1.9 merge, no single threshold can do both: a threshold below 2 excludes the first merge, and a threshold of at least 2 includes both merges.
Check. The proposed 1.95 threshold gives three singletons, not the desired two clusters. The schedule does contain the desired two-cluster stage, but the decreasing heights prevent a horizontal cut from selecting it. The mistake to avoid is choosing a threshold solely by looking for a numerical gap without checking the order of the merges.
Common Mistakes and Practical Checks
- Assuming heights must increase. Centroid linkage can have an inversion. Check each new height against the preceding one instead of treating monotonicity as guaranteed.
- Using an old distance after a merge. Recompute the centroid of the merged cluster, then measure its distance to every remaining cluster centroid.
- Forgetting cluster sizes. The merged centroid is weighted by the number of observations in each cluster; it is not generally the midpoint of the two centroids.
- Confusing the linkage convention. If a calculation uses squared-Euclidean distances, report that convention and keep it consistent. Squaring nonnegative Euclidean heights preserves their ordering, so it does not remove an inversion.
- Expecting every threshold to match a schedule stage. With an inversion, a horizontal cut may skip an intermediate number of clusters. Use the agglomeration history when the required output is a fixed cluster count.
A reliable calculation therefore has three checks: identify the smallest current centroid distance at each step, update the centroid with the correct size weights, and compare the new merge height with the previous height. If a decrease appears, retain it as a feature of the result rather than silently rearranging the heights.
Check Your Understanding
For each problem, use ordinary Euclidean centroid linkage unless the question states otherwise.
- Let \(A=(-3,0)\), \(B=(3,0)\), and \(C=(0,5.4)\). Find the first and second merge heights and state whether there is an inversion. (Answer: \(A,B\) merge at 6; the next merge is at 5.4, so there is an inversion.)
- For \(A=(0,0)\), \(B=(0,2)\), \(C=(4,0)\), and \(D=(4,3)\), find the merge order and all three heights. (Answer: \(A,B\) at 2; \(C,D\) at 3; then \(AB,CD\) at \(\sqrt{16.25}\approx4.0311\); no inversion.)
- For the three-point data in Question 1, what partition results from a threshold of 5.7, and can that threshold recover the two-cluster stage? (Answer: \(\{A\},\{B\},\{C\}\); no, because the first merge is at 6.)
- For the three-point data in Question 1, use squared-Euclidean linkage heights instead. Give the two heights and say whether the inversion remains. (Answer: 36 and 29.16; the inversion remains.)
- Two existing clusters have sizes 2 and 3 and centroids \((1,2)\) and \((6,3)\). Find the merged centroid and its Euclidean distance from \((0,0)\). (Answer: the merged centroid is \((4,2.6)\), and its distance from \((0,0)\) is \(\sqrt{22.76}\approx4.7707\).)