Why an Isolated Observation Matters
Hierarchical clustering builds groups by repeatedly merging the pair of clusters that are closest under a chosen linkage rule. An observation far from the main body of the data can therefore matter in two different ways: it can affect which merge happens next, and it can produce a large merge height when it finally joins a cluster. These effects depend on the linkage rule, not just on how far away the observation appears.
Here, an isolated observation means one whose distances from the other observations are large relative to distances within the main groups, using the distance measure already chosen for the analysis. “Isolated” describes its position in the data; it does not establish that the observation is an error or should be removed. The comparisons below use one-dimensional Euclidean distance, so the distance between values \(x\) and \(y\) is \(|x-y|\).
For Ward linkage, define the within-cluster sum of squares of a cluster \(C\) by \(W(C)=\sum_{x\in C}\|x-\bar{x}_C\|^2\), where \(\bar{x}_C\) is its mean vector. In this tutorial, the Ward merge criterion—and the reported Ward height—is the increase \(\Delta(A,B)=W(A\cup B)-W(A)-W(B)\). Some software reports a transformed height, such as \(\sqrt{2\Delta(A,B)}\); comparing Ward heights requires checking which convention is in use.
How the Linkages Respond to Distance
| Linkage | How the isolated observation affects a merge | Typical implication for its merge height |
|---|---|---|
| Single | Uses the nearest cross-cluster pair, so one short connection can determine the merge. | The observation can join through its nearest neighbor even if other cross-cluster pairs are far apart. |
| Complete | Uses the farthest cross-cluster pair, so the observation can make a proposed merge costly. | A merge involving the observation may occur at a high distance. |
| Average | Averages all cross-cluster pairs, balancing near and far pairs. | The height reflects the overall separation of the clusters. |
| Centroid | Compares means, so the cluster mean can shift as observations are added. | The height depends on the cluster means, not the most distant pair. |
| Ward | Balances mean separation with cluster sizes through the increase in within-cluster variation. | A distant observation often produces a substantial increase, with the cluster sizes affecting its size. |
These are tendencies, not guarantees that every data set will follow the same merge order. A linkage rule compares all currently available cluster pairs at each step. The isolated observation may merge with a nearby group before the main groups merge, or it may remain a singleton until later.
Worked Example: Comparing All Five Rules on a Small Data Set
Consider the hypothetical one-dimensional observations \(0,1,4,5,12\). The first two points merge at distance \(1\), and \(4\) and \(5\) also merge at distance \(1\). These two merges are tied, so their order is immaterial. At the next stage the clusters are \(A=\{0,1\}\), \(B=\{4,5\}\), and the isolated point \(O=\{12\}\). Find the next merge and the final height for each rule. For Ward linkage, report \(\Delta\).
Single linkage. The distance between \(A\) and \(B\) is the minimum of \(4,5,3,4\), which is \(3\). The distances from \(B\) to \(O\) and from \(A\) to \(O\) are \(7\) and \(11\), respectively. Thus \(A\) and \(B\) merge at height \(3\). The distance from their union to \(O\) is the smallest of \(12,11,8,7\), or \(7\). The final merge height is \(7\).
Complete linkage. The maximum cross-cluster distance between \(A\) and \(B\) is \(5\). The maximum distances from \(B\) and \(A\) to \(O\) are \(8\) and \(12\). Thus \(A\) and \(B\) merge at height \(5\). The largest distance from their union to \(O\) is \(12\), so the final height is \(12\).
Average linkage. The four distances between \(A\) and \(B\) sum to \(4+5+3+4=16\), giving a mean of \(16/4=4\). The mean distances from \(B\) and \(A\) to \(O\) are \((8+7)/2=7.5\) and \((12+11)/2=11.5\). Hence \(A\) and \(B\) merge at height \(4\). From their union to \(O\), the mean is \((12+11+8+7)/4=38/4=9.5\). The final height is \(9.5\).
Centroid linkage. The cluster means are \(0.5\), \(4.5\), and \(12\). The first two means are \(4\) apart, while their distances to \(12\) are \(7.5\) and \(11.5\). They therefore merge first. The resulting cluster mean is \((0+1+4+5)/4=2.5\), which is \(12-2.5=9.5\) from \(O\). The final height is \(9.5\).
Ward linkage. For singleton merges, \(\Delta\) is half the squared distance, so each pair at distance \(1\) merges with \(\Delta=(1/2)(1^2)=0.5\). For \(A\) and \(B\), each of size \(2\), the mean difference is \(4.5-0.5=4\). The Ward increase is \((2\cdot2/4)(4^2)=16\). The merged cluster has size \(4\) and mean \(2.5\); merging it with \(O\) gives \(\Delta=(4\cdot1/5)(12-2.5)^2=(4/5)(9.5^2)=72.2\). Thus the final Ward height, under the stated convention, is \(72.2\).
Check and method. Each rule joins the two main groups before adding \(12\), but their final heights differ: \(7\), \(12\), \(9.5\), \(9.5\), and \(72.2\) under the stated Ward convention. The method is to recompute distances between current clusters after every merge. A common mistake is to assume that “outlier” automatically means “joins last”; the actual merge order must be checked against every candidate pair.
Why Ward’s Formula Has a Cluster-Size Factor
Ward’s criterion is not simply the distance between two means. The cluster sizes matter because merging a large cluster with a small one changes the overall within-cluster variation differently from merging two small clusters. The formula follows by expanding the sum of squared deviations around the combined mean.
For clusters \(A\) and \(B\) of sizes \(n_A\) and \(n_B\), the mean of their union is \(\bar{x}_{A\cup B}=(n_A\bar{x}_A+n_B\bar{x}_B)/(n_A+n_B)\).
For any point \(x\in A\), write \(x-\bar{x}_{A\cup B}=(x-\bar{x}_A)+(\bar{x}_A-\bar{x}_{A\cup B})\). On summing squared norms over \(A\), the cross term is zero because \(\sum_{x\in A}(x-\bar{x}_A)=0\). The same argument applies to \(B\).
The two mean-shift terms are \(n_A\|\bar{x}_A-\bar{x}_{A\cup B}\|^2+n_B\|\bar{x}_B-\bar{x}_{A\cup B}\|^2\). Substituting the combined mean and collecting terms gives \(\Delta(A,B)=\frac{n_An_B}{n_A+n_B}\|\bar{x}_A-\bar{x}_B\|^2\).
The coefficient \(n_An_B/(n_A+n_B)\) explains why Ward linkage cannot be read as an ordinary centroid distance: the same separation between means can produce different increases in within-cluster variation when the cluster sizes differ. The squared distance also means that multiplying all coordinates by a constant multiplies Ward’s \(\Delta\) by the square of that constant.
Worked Example: An Outlier Near a Larger Cluster
Suppose a hypothetical data set has reached the clusters \(A=\{0,0.2,0.4,0.6\}\), \(B=\{4\}\), and \(O=\{10\}\). The four points in \(A\) can be formed by successive nearest-neighbor merges at distance \(0.2\). Compare the next merge and the final height under the five rules.
Single linkage. The smallest distance from \(A\) to \(B\) is \(4-0.6=3.4\). The distances from \(B\) to \(O\), and the smallest distance from \(A\) to \(O\), are \(6\) and \(9.4\). Thus \(A\) merges with \(B\) at \(3.4\). The nearest point in \(A\cup B\) to \(O\) is \(4\), so the final height is \(10-4=6\).
Complete linkage. The largest distance from \(A\) to \(B\) is \(4-0=4\); the distances from \(B\) to \(O\) and the largest distance from \(A\) to \(O\) are \(6\) and \(10\). Thus \(A\) merges with \(B\) at \(4\), and the final height is \(10\).
Average and centroid linkage. The four distances from \(A\) to \(B\) are \(4,3.8,3.6,3.4\), with mean \(14.8/4=3.7\). The cluster means are \(0.3\), \(4\), and \(10\), so the centroid distance from \(A\) to \(B\) is also \(3.7\). Both rules merge these clusters before considering the outlier, since the corresponding distances from \(B\) to \(O\) are \(6\). After the merge, the mean distance from \(A\cup B\) to \(O\) is \((10+9.8+9.6+9.4+6)/5=44.8/5=8.96\). The new centroid is \((0+0.2+0.4+0.6+4)/5=1.04\), also \(8.96\) from \(O\). Both final heights are \(8.96\).
Ward linkage. The means are \(0.3\), \(4\), and \(10\). The increase for merging \(A\) with \(B\) is \((4\cdot1/5)(4-0.3)^2=(4/5)(3.7^2)=10.952\). The increase for merging \(B\) with \(O\) is \((1\cdot1/2)(6^2)=18\), and for merging \(A\) with \(O\) it is \((4/5)(9.7^2)=75.272\). Therefore \(A\) and \(B\) merge first. Their union has size \(5\) and mean \(1.04\); its merge with \(O\) has increase \((5/6)(10-1.04)^2=(5/6)(8.96^2)=(5/6)(80.2816)=66.9013\) to four decimals.
Check and method. The final heights are \(6\), \(10\), \(8.96\), \(8.96\), and \(66.9013\), respectively. The Ward calculation includes the size factor, while the average calculation uses all five cross-cluster pairs after the first merge. Treating the original mean distance \(9.7\) as the final average height would be a mistake: the merged cluster now also contains \(4\), whose distance to \(10\) is only \(6\).
Interpreting a High Merge Height
A large final merge height indicates that the chosen linkage rule considers the remaining clusters substantially separated at that stage. It does not, by itself, identify a bad observation, establish a natural number of clusters, or show that one linkage is universally preferable. In the examples, the same isolated point has final height \(7\) under single linkage but \(12\) under complete linkage; these numbers answer different definitions of cluster separation.
Single linkage can be especially sensitive to a short connecting pair: once the closest point in a cluster is near the outlier, other, more distant pairs do not raise the single-linkage distance. Complete linkage reflects the farthest pair and can keep a distant observation separate until a comparatively high merge. Average linkage moderates these extremes by including every cross-cluster pair. Centroid linkage follows the cluster means, which can shift as clusters grow. Ward linkage measures the increase in within-cluster sum of squares and accounts for cluster sizes.
A practical reading of an unusually tall merge is therefore conditional: identify the linkage rule, check the distance convention, and inspect which clusters are being joined. If the analysis uses Ward linkage, also determine whether the plotted heights are \(\Delta\) or a transformation of \(\Delta\). A numerical height from one convention cannot be compared directly with a height from another.
Check Your Understanding
For each problem, assume one-dimensional Euclidean distance. Use the Ward increase \(\Delta\) as its height.
- Clusters \(A=\{1,2\}\) and \(B=\{6\}\) are candidates for a single-linkage merge. What is their distance? What is the complete-linkage distance? (Answer: single \(=4\); complete \(=5\).)
- Clusters \(A=\{0,2\}\) and \(B=\{5,7\}\) have been formed. Find their average-linkage distance and centroid-linkage distance. (Answer: average \(=5\); centroid \(=5\).)
- For the clusters in Question 2, calculate the Ward increase for merging \(A\) and \(B\). (Answer: \(\Delta=(2\cdot2/4)(6-1)^2=25\).)
- At a later stage, clusters \(C=\{0,1,2\}\) and \(O=\{9\}\) are candidates. Find their single-, complete-, and average-linkage distances. (Answer: single \(=7\); complete \(=9\); average \(=8\).)
- Clusters \(C=\{0,1,2\}\) and \(O=\{9\}\) are considered under Ward linkage. Calculate the increase and state the mean difference used. (Answer: means \(1\) and \(9\), difference \(8\); \(\Delta=(3\cdot1/4)(8^2)=48\).)