4.4 Hierarchical linkages and dendrograms

From one partition to a hierarchy

A partition gives one grouping of the observations. Often we want to examine several resolutions: two broad groups, then smaller groups within each one. Hierarchical clustering records such nested decisions in a tree. Its leaves are the individual observations, and an internal node records a group formed from its children. Cutting the tree selects a partition without fitting a new model for every requested number of groups.

The central choice is how to measure separation between groups. The closest pair of observations, the furthest pair, and the average over all pairs answer different questions. None of these quantities is the same as the distance between two means. A hierarchical method becomes precise only after its point distance, group linkage, and tie rule have been specified.

We use a finite dataset $x_1,\ldots,x_n$, with $n\ge2$. A cluster is a nonempty set of observation indices. Different observations retain different indices even when their feature vectors coincide. At each stage, the active clusters form a partition: they are disjoint and together contain every index.

Four linkage criteria

Definition

Single, complete and average linkage

For disjoint nonempty clusters $A,B$ and point distance $d$, define

$$L_{\mathrm{single}}(A,B)=\min_{i\in A,j\in B}d(x_i,x_j),\qquad L_{\mathrm{complete}}(A,B)=\max_{i\in A,j\in B}d(x_i,x_j),$$$$L_{\mathrm{average}}(A,B)=\frac1{|A||B|} \sum_{i\in A}\sum_{j\in B}d(x_i,x_j).$$

Single linkage asks whether the groups have a nearby connection. Complete linkage asks whether every cross-pair is close. Average linkage measures the mean separation over all cross-pairs, with every observation pair receiving the same weight.

These criteria can be applied to a supplied symmetric dissimilarity matrix. Their algorithmic definitions do not require Euclidean coordinates. Metric properties matter when making additional geometric conclusions. With ordinary Euclidean distance, a chain of short gaps can join a group whose endpoints are far apart under single linkage. Complete linkage resists this particular effect because a distant cross-pair makes its linkage large.

Ward linkage instead measures an increase in squared error. Here the feature vectors lie in $\mathbb R^d$, and the norm is Euclidean. Write

$$\mu_A=\frac1{|A|}\sum_{i\in A}x_i,\qquad W(A)=\sum_{i\in A}\|x_i-\mu_A\|_2^2.$$

Proposition

The Ward merge cost

For disjoint nonempty $A,B$,

$$\Delta(A,B)=W(A\cup B)-W(A)-W(B) =\frac{|A||B|}{|A|+|B|}\|\mu_A-\mu_B\|_2^2.$$

Ward's method chooses an active pair minimizing $\Delta(A,B)$.

Proof

Separate within-group variation from mean displacement

Let $a=|A|$, $b=|B|$ and $\mu=(a\mu_A+b\mu_B)/(a+b)$. Expanding $x_i-\mu=(x_i-\mu_A)+(\mu_A-\mu)$ and summing over $A$ removes the cross term because $\sum_{i\in A}(x_i-\mu_A)=0$. The corresponding identity holds for $B$. Thus

$$W(A\cup B)=W(A)+W(B)+a\|\mu_A-\mu\|_2^2 +b\|\mu_B-\mu\|_2^2.$$

Since $\mu_A-\mu=\frac b{a+b}(\mu_A-\mu_B)$ and $\mu_B-\mu=-\frac a{a+b}(\mu_A-\mu_B)$, the two remaining terms add to $ab\|\mu_A-\mu_B\|_2^2/(a+b)$.

The size factor is essential. Two pairs with the same distance between their means can have different merge costs because their cluster sizes differ. For a Ward dendrogram we use $\Delta$ itself as the height. A convention such as $\sqrt{2\Delta}$ gives the same merge ordering but different height values; state the convention before interpreting a plotted height as an error.

Worked example

Four answers for the same two groups

Take $A=\{0,2\}$ and $B=\{5,9\}$ on the real line. The four cross-distances are $5,9,3,7$. Therefore

$$L_{\mathrm{single}}=3,\qquad L_{\mathrm{complete}}=9,\qquad L_{\mathrm{average}}=6,\qquad \Delta=36.$$

For the final number, both sizes are two and the means are $1$ and $7$. Also $W(A)=2$, $W(B)=8$ and $W(A\cup B)=46$, so the increase is $46-2-8=36$. The average pairwise distance is six, while the Ward cost is thirty-six: these criteria have different meanings and units.

Agglomeration and exact tree cuts

Agglomeration starts with $n$ singleton clusters. Compute the linkage of every active pair, merge a pair with the smallest value, and replace its two members by their union. Repeat until one cluster remains. Each merge reduces the number of active clusters by one, so there are exactly $n-1$ merges.

For reproducibility, break an exact tie using the lexicographic order of the sorted observation-index lists in the candidate pair. A different tie rule can produce another valid tree when minimum linkage values coincide. The tie rule is part of the procedure, rather than evidence of a numerical failure.

After $n-k$ merges, exactly $k$ clusters remain. This merge-count cut always exists for $1\le k\le n$. A horizontal height cut is a different operation: it merges everything below a chosen threshold. Equal-height merges can make the number of resulting groups jump, so a height threshold need not realize every integer $k$.

Worked example

Different linkages create different nested groups

Use the indexed points $0,3,4,6,8$, in that order. Apply the stated tie rule. The complete merge records for two criteria are:

Merge	Single linkage	Height	Complete linkage	Height
1	$\{3\},\{4\}$	$1$	$\{3\},\{4\}$	$1$
2	$\{3,4\},\{6\}$	$2$	$\{6\},\{8\}$	$2$
3	$\{3,4,6\},\{8\}$	$2$	$\{0\},\{3,4\}$	$4$
4	$\{0\},\{3,4,6,8\}$	$3$	$\{0,3,4\},\{6,8\}$	$8$

At the two-group cut, single linkage gives $\{0\}$ and $\{3,4,6,8\}$; complete linkage gives $\{0,3,4\}$ and $\{6,8\}$. The difference follows directly from the objectives. The single-link chain can grow through gaps of two, whereas complete linkage must account for the distance from three to eight.

Updating linkage values

Recomputing every point pair after each merge hides useful structure. For a third active cluster $C$, let $a=|A|$ and $b=|B|$. Then

$$L_{\mathrm{single}}(A\cup B,C) =\min\{L_{\mathrm{single}}(A,C),L_{\mathrm{single}}(B,C)\},$$ $$L_{\mathrm{complete}}(A\cup B,C) =\max\{L_{\mathrm{complete}}(A,C),L_{\mathrm{complete}}(B,C)\},$$ $$L_{\mathrm{average}}(A\cup B,C) =\frac a{a+b}L_{\mathrm{average}}(A,C) +\frac b{a+b}L_{\mathrm{average}}(B,C).$$

The average formula follows by splitting the double sum into pairs from $A$ and pairs from $B$. Taking the unweighted average of two old linkage values would assign the same total weight to groups of different sizes. That defines a different method. The minimum and maximum formulas follow by taking the extremum over the union of the two cross-pair sets.

These updates also explain nondecreasing merge heights for these three criteria. When a pair is merged at the current minimum $h$, every remaining pair value is at least $h$. The new minimum, maximum or weighted average of old values is also at least $h$. Repeating the argument proves that the height sequence cannot decrease.

Proposition

Single-link cuts are graph components

Fix a threshold $t\ge0$. Construct the graph whose vertices are observation indices, with an edge $i,j$ whenever $d(x_i,x_j)\le t$. The single-link hierarchy cut after all merges of height at most $t$ gives exactly the connected components of this graph.

Proof

A crossing edge is exactly an available merge

If an edge of length at most $t$ joins two active groups, their single linkage is at most $t$, so the algorithm cannot finish the threshold cut while leaving those groups separate. All vertices on a graph path therefore end in the same group. Conversely, every merge of height at most $t$ joins groups containing a cross-edge of length at most $t$. Starting from singletons, such a merge stays inside a graph component. Both inclusions follow.

A component can have a large diameter despite containing only short edges along a connecting path. The graph description makes the chaining effect precise. It also explains why deleting one bridge may split a large single-link group while hardly changing most pairwise distances.

A small executable merge record

This direct implementation uses complete linkage. It keeps indices separate from coordinates, and uses tuple ordering for exact ties. It computes the criterion from its definition, which is convenient for checking a short hand calculation.

import numpy as np

x = np.array([0., 3., 4., 6., 8.])
clusters = [(i,) for i in range(len(x))]
while len(clusters) > 1:
    candidates = []
    for i in range(len(clusters)):
        for j in range(i + 1, len(clusters)):
            a, b = clusters[i], clusters[j]
            height = np.abs(x[list(a), None] - x[list(b)]).max()
            candidates.append((float(height), a, b, i, j))
    height, a, b, i, j = min(candidates)
    print(a, b, height)
    clusters = [c for k, c in enumerate(clusters) if k not in (i, j)]
    clusters.append(tuple(sorted(a + b)))
    clusters.sort()

The printed heights are $1,2,4,8$. The tuples are zero-based observation indices: the first merge $(1,),(2,)$ refers to the coordinates three and four. A linkage record should preserve this distinction so that duplicate feature vectors do not lose their observation identities.

Divisive hierarchies

A top-down hierarchy starts with the full dataset and splits one active cluster at a time. For a concrete procedure, choose an active cluster with the largest number of observations, break size ties by its index list, and split that cluster by two-means. Specify the two-means initialization and tie handling as well. Once a split is made, later operations occur inside its children. They do not transfer observations across the earlier boundary.

Worked example

Splitting the largest group

Start with $0,1,8,9,20$. A two-means split initialized at zero and twenty stabilizes at the groups $\{0,1,8,9\}$ and $\{20\}$, with means $4.5$ and $20$. The first group is larger. Splitting it with initial means zero and nine gives $\{0,1\}$ and $\{8,9\}$. The resulting three groups have total within-group squared error $1/2+1/2+0=1$, compared with $65$ just before the second split. The later split refines its parent; it does not undo or reconsider the isolated group containing twenty.

Divisive and agglomerative methods make different irreversible decisions. A sequence of two-means splits is consequently not the reverse of a Ward merge sequence. Both produce nested partitions, but their search procedures and local decisions differ. A tree records those decisions; it does not establish that every cut minimizes a global clustering objective.

Interpreting merge heights

A height has meaning only through its linkage. For complete linkage, a group formed by merges of height at most a threshold has diameter at most that threshold. This follows by induction: singleton diameters are zero; when two groups merge, every cross-distance is at most their complete linkage, while distances inside each child already satisfy the bound. Thus the threshold controls every pair in the resulting group, not just its last connection.

For single linkage, the threshold instead controls the largest edge needed along a connecting path. The endpoints of a long chain can be much farther apart. For average linkage, the height is an average over the current cross-pairs. The earlier groups at zero and two versus five and nine have average linkage six, although the merged diameter is nine. A statement about an average does not turn into a uniform bound on every member pair.

Ward heights accumulate differently. At each merge the total within-group squared error increases by exactly its recorded cost. Starting from singletons, whose error is zero, adding all the Ward costs up to a particular merge-count cut gives the total squared error of that partition. This supplies a direct numerical check on a merge record. The relation uses the raw squared-error heights defined here; adding their square roots would not recover that total.

Choosing a cut therefore requires a substantive question. A complete-link threshold can express a maximum within-group dissimilarity. A Ward cut can be compared using its total reconstruction error. A large jump in successive heights suggests that the next merge joins more separated groups under the chosen criterion. The interpretation remains conditional on the feature geometry and linkage rather than being a universal test for a unique number of natural groups.

Feature geometry in image grouping

For an image example, regard each pixel as an indexed observation. Let $I_i$ be its grayscale intensity and $(r_i,c_i)$ its row and column. One possible feature vector is $x_i=(I_i,\alpha r_i,\alpha c_i)$, where $\alpha\ge0$ fixes the relative spatial scale. Then

$$\|x_i-x_j\|_2^2=(I_i-I_j)^2 +\alpha^2\big((r_i-r_j)^2+(c_i-c_j)^2\big).$$

With zero spatial weight, pixels with similar intensities can belong to the same group even if they are far apart in the image. A positive weight adds a cost for spatial separation. Its magnitude must be interpreted relative to the intensity units: multiplying every intensity by a constant changes that balance unless the spatial weight is adjusted as well. Ward linkage then measures increased squared error in this chosen feature space.

A spatially connected segmentation requires explicit adjacency constraints on admissible merges. Including pixel coordinates as features alone does not impose such a constraint. This illustrates a general modeling distinction: the feature map defines similarity, whereas allowed merges define which partitions the algorithm is permitted to construct. Both choices affect the resulting tree and should be held fixed when comparing cuts.

Exercises

Checkpoint

1. Updating an average linkage

Suppose $|A|=2$, $|B|=1$, $L_{\mathrm{average}}(A,C)=6$ and $L_{\mathrm{average}}(B,C)=3$. Find the linkage from $A\cup B$ to $C$.

Solution · Exercise 1 solution

The weights are $2/3$ and $1/3$, so the answer is $\frac23(6)+\frac13(3)=5$. The unweighted average $4.5$ gives too much total influence to the smaller group $B$.

Checkpoint

2. Ward height versus Euclidean distance

For the singleton groups at zero and four, calculate their Euclidean distance and their Ward merge cost under the height convention used here.

Solution · Exercise 2 solution

The distance is four, whereas $\Delta=(1\cdot1/2)(0-4)^2=8$. The merged mean is two and its squared error is $4+4=8$.

Checkpoint

3. A cut with tied merge heights

The points $0,1,2,3$ use single linkage. Explain why a merge-count cut can give two groups even though a horizontal height threshold cannot.

Solution · Exercise 3 solution

All three merges occur at height one. Two completed merges leave exactly two groups, with their membership depending on the stated tie order. A threshold below one leaves four singletons; a threshold at least one joins the whole connected chain. Neither threshold gives two groups.

Checkpoint

4. What a divisive refinement can change

After a divisive split produces $A$ and $B$, a later split divides $A$ into $A_1,A_2$. Can an observation in $B$ move into $A_1$ during that step?

Solution · Exercise 4 solution

No. A hierarchical refinement requires $A_1\cup A_2=A$ and disjoint children. Moving an observation from $B$ would violate that nesting. Reassigning all observations by new centers would define a different, non-hierarchical update.

Related notes

• Center objectives and Lloyd updates derives the squared-error updates used in a two-means split.
• Density connectivity and mean shift distinguishes core-point connectivity from unrestricted single-link chains.
• Course reading list collects the recommended books.