Agglomerative Hierarchical Clustering

How a Dendrogram Is Built

Agglomerative hierarchical clustering turns a collection of observations into a nested sequence of groups. It begins with every observation in its own cluster, then repeatedly merges the two clusters judged closest under a specified linkage rule. The result is a dendrogram: a tree whose leaves are observations and whose internal branches record the merges and their heights. Unlike a method that asks for a fixed number of clusters at the outset, this procedure gives a hierarchy that can be cut at different levels.

The hierarchy is determined by both the dissimilarities between observations and the linkage rule used to define dissimilarity between clusters. The calculations below use small hypothetical data so that every merge can be checked. In genomic work, the observations might be profiles, but the tree alone does not establish that groups are biologically meaningful.

Definition: In agglomerative hierarchical clustering, the initial clusters are the individual observations. At each step, the pair of current clusters with the smallest intercluster dissimilarity is merged. The process continues until one cluster remains. A dendrogram represents this sequence; its leaves are observations, and the height of each internal node records the dissimilarity or merge cost at which its two child clusters joined.

The input is usually a symmetric matrix of pairwise dissimilarities \(d(i,j)\), with nonnegative entries and \(d(i,i)=0\). The algorithm does not require the dissimilarities to be Euclidean for single, complete, or average linkage, though the meaning of the result depends on how those dissimilarities were constructed. Ward linkage is different: its usual interpretation is as an increase in within-cluster sum of squares for Euclidean feature vectors. A reproducible analysis therefore specifies the observations, the dissimilarity, the linkage rule, and any restrictions on which clusters may merge.

Four Linkage Rules

Suppose \(A\) and \(B\) are two disjoint clusters, and \(d(i,j)\) is the dissimilarity between observations \(i\) and \(j\). Single, complete, and average linkage summarize the pairwise dissimilarities across the two clusters in different ways. Ward linkage instead measures the increase in within-cluster variation caused by merging them.

Definition: For clusters \(A\) and \(B\), the linkage dissimilarities are:

Single linkage: \(D_{\mathrm{single}}(A,B)=\min_{i\in A,\,j\in B}d(i,j)\), the closest cross-cluster pair.
Complete linkage: \(D_{\mathrm{complete}}(A,B)=\max_{i\in A,\,j\in B}d(i,j)\), the most distant cross-cluster pair.
Average linkage: \(D_{\mathrm{average}}(A,B)=\frac{1}{|A||B|}\sum_{i\in A}\sum_{j\in B}d(i,j)\), the mean of all cross-cluster dissimilarities.
Ward linkage: for feature vectors \(x_i\), choose the merge minimizing the increase in within-cluster sum of squares. For Euclidean vectors, that increase is \(\Delta(A,B)=\frac{|A||B|}{|A|+|B|}\lVert\bar{x}_A-\bar{x}_B\rVert^2\), where \(\bar{x}_A\) and \(\bar{x}_B\) are the cluster centroids.

The rules can select different merges even when they begin with the same pairwise distances. Single linkage can connect groups through a chain of near neighbors. Complete linkage considers the farthest cross-pair and tends to resist merges that would leave very distant members in the same group. Average linkage uses all cross-pairs. Ward linkage favors merges that add relatively little within-cluster sum of squares; unlike the first three rules, it is defined through feature-space variation, not just an arbitrary dissimilarity matrix.

Worked Example: Four Linkages on Four Observations

Consider four hypothetical one-dimensional profiles, represented by their values \(A=0\), \(B=2\), \(C=5\), and \(D=9\). Use absolute differences as pairwise dissimilarities. The six distances are \(d(A,B)=2\), \(d(A,C)=5\), \(d(A,D)=9\), \(d(B,C)=3\), \(d(B,D)=7\), and \(d(C,D)=4\). Each method begins by merging \(A\) and \(B\), since 2 is the smallest distance.

Single linkage. After merging \(A\) and \(B\), the distance from \(\{A,B\}\) to \(C\) is \(\min(5,3)=3\), so \(C\) joins. The distance from \(\{A,B,C\}\) to \(D\) is \(\min(9,7,4)=4\), so \(D\) joins. The merge heights are 2, 3, and 4.

Complete linkage. The distance from \(\{A,B\}\) to \(C\) is \(\max(5,3)=5\), and its distance to \(D\) is \(\max(9,7)=9\). Meanwhile, \(C\) and \(D\) have distance 4, so they merge next. The distance between \(\{A,B\}\) and \(\{C,D\}\) is \(\max(5,9,3,7)=9\). The merge heights are 2, 4, and 9.

Average linkage. The distance from \(\{A,B\}\) to \(C\) is \((5+3)/2=4\), and its distance to \(D\) is \((9+7)/2=8\). Since \(d(C,D)=4\), \(C\) and \(D\) merge next. The average distance between the two resulting clusters is \((5+9+3+7)/4=24/4=6\). The merge heights are 2, 4, and 6.

Ward linkage. The increase for merging the two singleton clusters \(A,B\) is \((1\cdot1/2)(0-2)^2=2\). The cost of merging \(C,D\) is \((1\cdot1/2)(5-9)^2=8\). Once \(\{A,B\}\) has formed, its centroid is 1, so merging it with \(C\) would cost \((2\cdot1/3)(1-5)^2=32/3\), about 10.67. Thus \(C,D\) merge next, at cost 8. Their centroid is 7; the final merge costs \((2\cdot2/4)(1-7)^2=36\). With merge cost \(\Delta\) used as the height, the heights are 2, 8, and 36.

The four trees differ because each rule defines “closest clusters” differently. Ward heights are increases in within-cluster sum of squares, so their numerical scale should not be mistaken for the distance heights reported by the other rules.

Why Ward’s Merge Cost Has This Form

The Ward formula follows from the way a cluster’s within-cluster sum of squares changes when two groups are combined. For a cluster \(C\), define its within-cluster sum of squares as \(W(C)=\sum_{i\in C}\lVert x_i-\bar{x}_C\rVert^2\). The increase from merging \(A\) and \(B\) is \(W(A\cup B)-W(A)-W(B)\).

W(A\cup B)-W(A)-W(B) =\frac{|A||B|}{|A|+|B|}\lVert\bar{x}_A-\bar{x}_B\rVert^2.

To see this, write \(a=|A|\), \(b=|B|\), and \(\bar{x}=(a\bar{x}_A+b\bar{x}_B)/(a+b)\) for the combined centroid. Expanding each squared deviation around its own cluster centroid gives the identity \(\sum_{i\in A}\lVert x_i-\bar{x}\rVert^2=W(A)+a\lVert\bar{x}_A-\bar{x}\rVert^2\), with the analogous expression for \(B\). The cross terms vanish because \(\sum_{i\in A}(x_i-\bar{x}_A)=0\), and likewise for \(B\). Therefore the increase is \(a\lVert\bar{x}_A-\bar{x}\rVert^2+b\lVert\bar{x}_B-\bar{x}\rVert^2\). Since \(\bar{x}_A-\bar{x}=\frac{b}{a+b}(\bar{x}_A-\bar{x}_B)\) and \(\bar{x}_B-\bar{x}=-\frac{a}{a+b}(\bar{x}_A-\bar{x}_B)\), substituting and collecting terms yields \(\frac{ab}{a+b}\lVert\bar{x}_A-\bar{x}_B\rVert^2\). This establishes the stated merge cost.

Reading and Cutting a Dendrogram

A cut is a horizontal line drawn across the dendrogram. At a specified height, merges below the line have occurred and merges above it have not. The connected branches intersected by the cut define the current clusters. Equivalently, start with singletons and perform all merges whose heights are at or below the cut level. A cut can produce different numbers of clusters under different linkage rules, and the chosen cut level is an analytical decision rather than a feature automatically supplied by the tree.

Worked Example: Interpreting Cut Levels

Use the single-linkage tree from the previous example, whose merges are \(A\) with \(B\) at height 2, then \(C\) with \(\{A,B\}\) at height 3, then \(D\) with \(\{A,B,C\}\) at height 4. At a cut of height 2.5, the first merge has occurred but the height-3 merge has not. The clusters are \(\{A,B\}\), \(\{C\}\), and \(\{D\}\): three clusters.

At a cut of height 3.5, the first two merges have occurred and the last has not. The clusters are \(\{A,B,C\}\) and \(\{D\}\): two clusters. At a cut of height 4, all three merges have occurred, leaving one cluster. If a cut falls exactly at a merge height, use a stated convention; here, merges at or below the cut are included. This matters especially when several merges are tied at the same height.

The vertical position of a merge represents the method’s merge dissimilarity or cost, not a probability that the two groups belong together. The horizontal arrangement of leaves is generally adjustable without changing the clustering; it should not be read as an additional quantitative scale. A large vertical gap between successive merges can make a range of cuts worth inspecting, but it does not by itself prove that a particular number of clusters is correct.

Assumptions, Diagnostics, and Limitations

For single, complete, and average linkage, the algorithm requires a defined dissimilarity for every relevant pair of observations. Those dissimilarities should be finite and symmetric, and they should be meaningful for the data and question. Ward’s method additionally requires feature vectors and a Euclidean within-cluster sum-of-squares interpretation. The data are not required to come from a particular probability distribution; hierarchical clustering is a deterministic procedure conditional on its inputs and tie-handling rule.

Before interpreting a tree, check that the input dissimilarities are valid and that the dendrogram reports the intended linkage and height definition. Look for ties, which can make the next merge non-unique, and for very different heights or a few observations that join only at unusually high levels. Such features are prompts to inspect the data and the consequences of alternative cuts, not automatic tests of validity. For Ward linkage, confirm that the calculation used Euclidean feature vectors and the intended scaling: a variable measured on a large numerical scale can dominate squared distances if variables have not been put on comparable scales where appropriate.

A dendrogram is not a unique description of the data. Changing the dissimilarity or linkage can change merge order and cluster membership. Single linkage may produce long chains; complete linkage can be sensitive to a distant pair; and average linkage still depends on the full set of pairwise dissimilarities. Ward’s method optimizes a local increase in within-cluster sum of squares at each step, but it does not generally find the globally best partition for every possible number of clusters. In contrast with a method that directly seeks a partition at a specified \(K\), agglomerative clustering preserves a nested tree, but early merges cannot be undone. These methods answer different questions; one should not treat a tree as proof of discrete, naturally separated populations.

Common Mistakes

Mixing up linkage rules. The closest pair defines single linkage; the farthest cross-pair defines complete linkage; average linkage averages every cross-pair. State the formula before calculating.
Reading a cut as a probability threshold. A cut height is a linkage dissimilarity or merge cost, not a probability or confidence level.
Assuming Ward accepts any dissimilarity matrix. Its usual merge cost is derived from Euclidean feature vectors and within-cluster sums of squares.
Treating the horizontal leaf order as meaningful. Leaf positions can often be rearranged while preserving the same merges.
Calling a cut objectively correct because it has a large gap. A gap can inform interpretation, but the choice should also reflect the analysis goal and the stability and usefulness of the resulting groups.

Key takeaway: Agglomerative clustering constructs a nested tree by repeatedly merging the closest current clusters under a chosen rule. Linkage determines what “closest” means; the cut level determines which groups are reported. Both choices must be stated and interpreted in context.

Check Your Understanding

Try each question, then compare your reasoning with the solutions below.

For clusters \(A=\{a_1,a_2\}\) and \(B=\{b_1,b_2\}\), suppose the four cross-dissimilarities are 2, 6, 4, and 8. Find single, complete, and average linkage.
A dendrogram has merges at heights 1.5, 2.5, and 5. At cut height 2, how many of the merges have occurred?
Why is Ward linkage not ordinarily defined merely by specifying an arbitrary symmetric dissimilarity matrix?
In the four-profile example, what clusters result from cutting the complete-linkage tree at height 5, using the convention that merges at or below the cut are included?

Solutions. (1) The minimum is 2, the maximum is 8, and the mean is \((2+6+4+8)/4=20/4=5\). Thus single, complete, and average linkage are 2, 8, and 5, respectively. (2) The merges at 1.5 have occurred, but those at 2.5 and 5 have not, so one merge has occurred. (3) Ward’s cost is the change in within-cluster sum of squares, derived from feature vectors and their Euclidean centroids; an arbitrary dissimilarity matrix does not necessarily define those quantities. (4) The complete-linkage merges at heights 2 and 4 have occurred, while the final merge at 9 has not, so the clusters are \(\{A,B\}\) and \(\{C,D\}\).