Centroid clustering represents a group by a center. Hierarchical agglomerative clustering instead starts with one group per observation and repeatedly joins two groups. It records an entire sequence of nested groupings, so we can ask for a coarse or fine partition after the hierarchy has been built.
The instruction “join the closest groups” is incomplete until closeness between groups is defined. The closest pair of members, the farthest pair and the average of all cross-group distances answer different questions. We will derive those three linkage rules, trace their different merge heights and prove a precise graph interpretation for single linkage. A hierarchy is a model of the chosen dissimilarities, not evidence that the resulting groups are correct real-world labels.
Begin with observations and dissimilarities
Definition 10.1.1
(Finite symmetric dissimilarities)
Let the observation labels be , with . Assume finite numbers satisfying
We allow distinct observations to have dissimilarity zero. The triangle inequality is not required for the algorithms or proofs here. Euclidean distances are one possible input, but a symmetric dissimilarity matrix also suffices.
A cluster is a nonempty set of observation labels. At every stage, the active clusters form a partition: they are disjoint and cover all observations. Initially they are singletons. A merge replaces two active clusters by their union, so the algorithm never splits an earlier group.
We must also specify ties. In the implementation below, a cluster's key is the sorted tuple of its labels. Order a candidate pair by those keys, then choose the lexicographically smallest pair among those with minimum linkage. This makes a run reproducible for fixed labels. It does not make all possible tie resolutions equivalent.
Three meanings of distance between clusters
Definition 10.1.2
(Single, complete and pair-weighted average linkage)
For disjoint nonempty clusters , define
At each step, merge a pair minimizing the chosen . Its linkage value is that merge's height. Average linkage here means that every pair of observations across the two groups has equal weight.
Single linkage asks whether there is a close connection between the groups. Complete linkage asks how bad their most dissimilar cross-pair is. Average linkage measures the typical cross-pair under the uniform pair weighting. These are different criteria, rather than different implementations of one unspecified notion of closeness.
Counterexample mode
Average pair distance is not distance between means
Take one-dimensional clusters and with ordinary absolute distance. Average linkage is . Their means are both zero, so the distance between their means is zero.
Replacing average linkage by a distance between centroids changes the clustering rule. In particular, the monotonicity proof below is for the three displayed linkages, not an unrestricted claim about every centroid-based hierarchy.
Update distances from the merged cluster
Suppose are merged and is another active cluster. All cross-pairs between and come either from or from , so the three linkages update as follows.
Lemma 10.1.3
(Linkage updates after a merge)
Let be pairwise disjoint nonempty clusters. Then
Proof
(Splitting the cross-pairs between A and B)
The cross-pairs between and form the disjoint union of the cross-pairs between and and those between and . A minimum or maximum over a union is the smaller or larger of the two partial minima or maxima, which gives the first two formulas. For the average, the sum of the distances over all cross-pairs splits in the same way, and is exactly the sum of over the cross-pairs of and :
and likewise for .
Worked example 10.1.4
(Weighting an average update by cluster sizes)
Let , and on the real line. The old average distances are and . Joining and gives , which agrees with the direct computation over the three cross-pairs. The unweighted mean would give the two old groups equal weight instead of giving their observations equal weight. It agrees with the weighted mean only when the two clusters have equal sizes or the two old distances coincide.
Why these dendrograms have nondecreasing merge heights
Theorem 10.1.5
(Merge heights do not decrease)
For single, complete and average linkage, the sequence of merge heights is nondecreasing.
Proof
(A new distance cannot fall below the current minimum)
Suppose the current minimum linkage is , attained by the pair being merged. Every other active pair has linkage at least . Unchanged pairs keep their values. By the update lemma, a new distance to another cluster is the minimum, maximum or positive weighted average of two old distances, both at least , so it is at least .
Thus every candidate at the next step is at least , so the next merge height is at least . Repeating the argument at each step proves the claim.
Proof X-ray
Where the choice of linkage enters monotonicity
The proof uses nothing about the data. The only property it needs is that every updated distance lies between the two old distances it is built from, or equals one of them. That is a property of these three rules, not of hierarchical clustering in general. Centroid distance lacks it. In the plane with Euclidean distance, take , and . Then and , so merge first at height . The centroid of is the origin, at distance from , so the next merge height falls below the previous one.
A dendrogram draws each observation as a leaf and each merge as a parent at its recorded height. The parent contains the union of its children's observations. A height cut means performing all merges with height at most , including all ties at , and reading the remaining clusters. The monotonicity just proved makes this a consistent cut of the hierarchy.
Asking for exactly groups is a different convention: stop after binary merges. If several merges share one height, a horizontal height cut can skip some group counts. Stopping partway through a tied height uses the specified binary tie order.
Worked example 10.1.6
(The same observations give different merge heights)
Use observations and . The first merge is with , at distance one, for all three rules. The next merge joins to , but its height depends on the linkage.
| Merge, shown by observation values | Single | Complete | Average |
|---|---|---|---|
| with | |||
| with | |||
| with |
For the final merge, the cross-pair distances are 10, 8 and 7. Taking their minimum, maximum and average gives the final row. At cut height , single and average linkage have clusters ; complete linkage still has . Here the braces in the table and cut description show observation values; the implementation records their labels instead.
The explorer below recomputes the worked points 0, 2, 3, 10 under all three linkages, so you can check which merges a height cut performs, including ties, and compare it with stopping after a fixed number of binary merges.
Single linkage is connectivity at a distance threshold
Fix and draw a graph with one vertex per observation. Put an edge between distinct exactly when . A path can connect two vertices even if their direct dissimilarity exceeds .
Theorem 10.1.7
(Single-linkage cuts are threshold components)
Fix and let be the graph on the observations with an edge between distinct exactly when . After all single-linkage merges of height at most have been performed, the clusters are exactly the connected components of , however ties at that height were resolved.
Proof
(Clusters stay inside components, and no component stays split)
Every cluster lies inside one component. Singletons do. A single-linkage merge at height at most joins two clusters with a cross-pair at dissimilarity at most , that is, an edge of ; two clusters that each lie in a component and are joined by an edge lie in the same component, and so does their union.
Conversely, suppose all merges of height at most have been performed but one component still meets two active clusters. By the monotonicity theorem these merges form an initial segment of the run, so every pair of active clusters now has linkage greater than . Follow a path in between the two clusters. Some edge of the path crosses two active clusters, which gives them single linkage at most , a contradiction. Hence each component is one cluster.
Proof X-ray
Why both halves and the prefix are needed
The proof has two halves of different character. The first is an induction: a merge at height at most can only follow an edge of , so no cluster straddles two components. The second is a contradiction through a path, which turns a statement about a whole component into a statement about one pair of adjacent active clusters. Single linkage, a minimum over cross-pairs, is the only rule for which one short edge certifies a small linkage; complete linkage would need every cross-pair to be short, and the chain example below shows the conclusion fails for it. Monotone merge heights are used once, to know that when the cut stops every remaining pair has linkage above . The order of tied merges never enters, because both halves speak only about heights.
This theorem explains both the usefulness and the limitation of single linkage. It captures connected chains of nearby observations, but it does not demand that every pair within one group be close.
Counterexample mode
A chain can have large diameter
On points with absolute distance, threshold-one edges connect consecutive points. Single linkage therefore joins all four points by height one, although the endpoints are distance three apart.
Complete linkage cannot put all four into one cluster by height one. At a complete-linkage cut , every within-cluster pair has dissimilarity at most : this holds for singletons and remains true at every merge whose maximum cross-distance is at most . Average linkage has no such diameter guarantee; the three points already merge at height despite diameter three.
The hierarchy induces a new distance
Definition 10.1.8
(Cophenetic dissimilarity and the bottleneck path formula)
Set . For distinct observations, let be the height at which they first belong to one merged cluster. For any of the three monotone hierarchies above,
This is the strong triangle inequality. With zero dissimilarities allowed between distinct observations, is a pseudoultrametric; when all distinct input pairs have positive dissimilarity, it is an ultrametric.
To see the inequality, take . At cut , the same partition cluster contains and also , so it contains . Their common merge must therefore have occurred by . Symmetry and nonnegativity follow directly from the definition.
Proposition 10.1.9
(Single-linkage cophenetic distance is a bottleneck path value)
For single linkage and distinct observations ,
In particular .
Proof
(The smallest threshold that connects the two observations)
The right side is the smallest edge threshold for which has a path from to . Removing a repeated-vertex segment cannot increase a path's largest edge, so it suffices to consider simple paths. There are finitely many of those and a direct edge is available, so the minimum exists. By the threshold-connectivity theorem, lie in one cluster after the merges of height at most exactly when they lie in one component of , so the smallest such is the height at which they first join. The direct one-edge path is one candidate, so . The diagonal remains separately defined as .
Worked example 10.1.10
(Cophenetic distances for the four points)
Take single linkage on , whose merge heights are . The points join at height , so . The point joins at height , so . This agrees with the path formula: the path has edges of lengths and , hence largest edge , which is smaller than the direct distance . Finally for , because the cheapest bridge to is the edge of length . So can be strictly smaller than , and it never exceeds it.
An exact implementation that keeps the merge record
The teaching implementation takes a square matrix of integers or Fraction values. It rejects a negative, asymmetric or nonzero-diagonal matrix. Each record is (left_labels, right_labels, height). A record tells us both what merged and at which dissimilarity scale; recording only the final all-inclusive cluster would lose the hierarchy.
from fractions import Fraction
def agglomerative(matrix, linkage="single"):
if linkage not in ("single", "complete", "average"):
raise ValueError("choose single, complete or average linkage")
n = len(matrix)
if n == 0 or any(len(row) != n for row in matrix):
raise ValueError("a nonempty square matrix is required")
values = [[Fraction(value) for value in row] for row in matrix]
if any(values[i][i] != 0 for i in range(n)):
raise ValueError("diagonal entries must be zero")
if any(values[i][j] < 0 or values[i][j] != values[j][i]
for i in range(n) for j in range(n)):
raise ValueError("dissimilarities must be nonnegative and symmetric")
active = {i: (i,) for i in range(n)}
distances = {(i, j): values[i][j]
for i in range(n) for j in range(i + 1, n)}
records = []
next_id = n
def gap(i, j):
return distances[min(i, j), max(i, j)]
while len(active) > 1:
order = sorted(active, key=active.get)
pairs = ((i, j) for p, i in enumerate(order) for j in order[p + 1:])
i, j = min(pairs, key=lambda pair:
(gap(*pair), active[pair[0]], active[pair[1]]))
left, right = active[i], active[j]
height = gap(i, j)
for c in active:
if c == i or c == j:
continue
first, second = gap(i, c), gap(j, c)
if linkage == "single":
updated = min(first, second)
elif linkage == "complete":
updated = max(first, second)
else:
updated = (len(left) * first + len(right) * second) / (len(left) + len(right))
distances[c, next_id] = updated
records.append((left, right, height))
del active[i], active[j]
active[next_id] = tuple(sorted(left + right))
next_id += 1
return records
With points = [0, 2, 3, 10], build matrix = [[abs(x-y) for y in points] for x in points]. Every run first records ((1,), (2,), Fraction(1)). The height sequences are (1,2,7), (1,3,10) and (1,5/2,25/3) for single, complete and average linkage respectively. A one-observation matrix returns no merges; zero off-diagonal values produce legitimate zero-height merges.
This straightforward implementation scans all remaining pairs at every step, giving comparisons and arithmetic operations, with stored distances. Exact rational arithmetic has additional numerator/denominator bit costs, so this count is an operation count rather than a constant-bit runtime claim. Faster specialized algorithms exist; the purpose here is to expose the linkage invariant and preserve exact examples.
The result still depends on the input dissimilarities. Changing the units of one feature before calculating Euclidean distances can change merge choices. Nor does a low merge height establish a causal explanation, a correct class label or the optimality of a different global clustering objective.
Exercises and worked solutions
Quick check
(For the observations with the cluster already formed, compute all three linkages from it to the point , and all three linkages from the later cluster to the point .)
Use every cross-pair distance, not the distance between group means.
Solution · Answer
The first set of cross-distances is 2 and 3, giving single 2, complete 3 and average . The later distances are 10, 8 and 7, giving single 7, complete 10 and average . These are statistics of all cross-pairs, not merely distances between group means.
Quick check
(The clusters and are joined, and . Find the new average linkage to by the update formula and by direct computation, and say what the unweighted mean of the two old linkages gives.)
Count how many observations each old cluster contributes.
Solution · Answer
The old linkages are and , with and . The update formula gives . Directly, the three cross-distances are , whose mean is also . The unweighted mean gives the two old clusters equal weight and is a different rule.
Quick check
(For the points with single linkage, what partition does the height-one cut give? Is stopping after two binary merges the same thing?)
Recall that a height cut performs every merge of that height.
Solution · Answer
All four points lie in one component of the threshold-one graph, so the height-one cut has one group. Stopping after two of the three binary merges does leave two groups, but that is a fixed-group-count stop partway through tied merges, not the defined height-one cut. All three merges at height one must be included for that cut.
Quick check
(Why can single linkage put the chain in one group at height one, while complete linkage cannot? Give an average-linkage example showing that a cluster formed at height can have diameter larger than .)
Compare what each linkage bounds.
Solution · Answer
Consecutive chain edges have length one, so single-linkage connectivity joins the endpoints through intermediates even though their direct distance is three. Complete linkage bounds every cross-pair at each merge and thus every within-cluster pair at its cut height; it cannot include the endpoints at height one. For average linkage, merge at height but their diameter is three.
Quick check
(For the chain , compute the single-linkage cophenetic distance between the endpoints. Why is it never larger than the original endpoint distance, and what term applies if distinct observations may have dissimilarity zero?)
Use the bottleneck path formula.
Solution · Answer
The consecutive-edge path has maximum edge length one, and no path can connect distinct chain vertices using edges shorter than one, so the value is one. In general the direct edge is a candidate path, giving . A zero-height merger of distinct observations can give , so the fully general term is pseudoultrametric. Strictly positive off-diagonal input distances make it an ultrametric.
Quick check
(For complete linkage on , compare merging the tied pair first with merging first. Give the partition at height one in each case. Which single-linkage conclusion does not depend on such choices?)
Compute the complete-linkage distances after the first merge.
Solution · Answer
If merges first, can also merge at height one, giving those two pairs. If merges first, its complete-linkage distances to 0 and 3 are both two, while , giving at height one. Relabeling can induce different first choices under a lexicographic tie policy, so reproducibility for fixed labels is not invariance under relabeling. For single linkage, after all height-one merges the partition is always the threshold graph's connected components, here one group.