Unit 8, lesson 55

Hierarchical Clustering

How agglomerative clustering builds nested groups under single linkage, complete linkage or Ward's criterion, how to read and cut a dendrogram, and how cluster stability checks whether the groups of a cut persist.

  • Video 55
  • Distance and Clustering

Four constructed points A, B, C and D lie on a line in the plane, at (0,0)(0, 0), (1,0)(1, 0), (3,0)(3, 0) and (6,0)(6, 0). Should C go with the pair on the left or with the point on the right, and are there two groups or three? Hierarchical clustering does not commit to one answer. It builds a whole sequence of nested groupings, recorded as a tree, and the grouping at each level depends on how the distance between two groups is defined. This lesson builds that tree under single linkage, complete linkage and Ward’s criterion, reads it as a dendrogram, and tests how stable its groups are.

Key terms

Agglomerative clustering

Definition Fix a distance dd between observations and a linkage, a rule that gives a dissimilarity D(A,B)D(A, B) between any two disjoint nonempty clusters AA and BB. Agglomerative clustering of nn observations starts with nn clusters of one observation each. At every step it merges the two clusters with the smallest linkage value and records that value as the height of the merge. After n−1n - 1 merges a single cluster remains, and the result is a hierarchy of nested partitions with n,n−1,…,1n, n - 1, \dots, 1 clusters. Ties need a stated rule. On this page the members of each cluster are listed in alphabetical order, each candidate pair is listed with the earlier cluster first, and a tie goes to the pair that comes first in dictionary order.

In plain words Begin with every point alone and keep joining the two closest groups until everything is one group. The linkage decides what the closest groups are, so two linkages can build different trees from the same distances between points. Density-based methods, the subject of the next lesson, define clusters by dense neighborhoods instead and are a separate idea.

Example For A, B, C and D the distances are 1 between A and B, 2 between B and C, 3 between A and C and between C and D, 5 between B and D, and 6 between A and D. Every linkage on this page merges A and B first. For two single points, single and complete linkage both reduce to the distance between them, and Ward’s increase is half the squared distance, so the smallest distance gives the first merge.

Single linkage

Definition Single linkage measures the dissimilarity of two clusters by their closest pair of members,

Dsingle(A,B)=min⁡a∈A, b∈Bd(a,b).\begin{aligned} &D_{\text{single}}(A, B) \\[0.4em] &\quad = \min_{\mathbf{a} \in A,\ \mathbf{b} \in B} d(\mathbf{a}, \mathbf{b}) . \end{aligned}

Keeping only the merges of the single linkage tree at heights up to hh gives exactly the connected groups of the graph that joins two observations whenever their distance is at most hh. The height at which two observations first share a cluster is therefore the smallest possible value of the largest step in a chain of observations that leads from one to the other.

In plain words Two groups count as close when any one member of the first is close to any one member of the second. That lets single linkage follow long, thin or curved groups. It also causes chaining, where a few points in between join groups that look separate.

Example After A and B merge, single linkage gives min⁡(3,2)=2\min(3, 2) = 2 from the cluster AB to C, min⁡(6,5)=5\min(6, 5) = 5 from AB to D, and 3 from C to D. So AB joins C at height 2, and then ABC joins D at min⁡(6,5,3)=3\min(6, 5, 3) = 3, through the pair C and D. The merge heights are 1, 2 and 3. A and D are 6 apart, yet the chain from A through B and C to D, with steps of 1, 2 and 3, puts them in one cluster at height 3.

Complete linkage

Definition Complete linkage measures the dissimilarity of two clusters by their farthest pair of members,

Dcomplete(A,B)=max⁡a∈A, b∈Bd(a,b).\begin{aligned} &D_{\text{complete}}(A, B) \\[0.4em] &\quad = \max_{\mathbf{a} \in A,\ \mathbf{b} \in B} d(\mathbf{a}, \mathbf{b}) . \end{aligned}

The cluster formed by a merge at height hh has diameter exactly hh, where the diameter is the largest distance between two of its members. Average linkage, another common choice, uses the mean of all distances between members of the two clusters,

Daverage(A,B)=1nAnB∑a∈A∑b∈Bd(a,b),\begin{aligned} &D_{\text{average}}(A, B) \\[0.4em] &\quad = \frac{1}{n_A n_B} \sum_{\mathbf{a} \in A} \sum_{\mathbf{b} \in B} d(\mathbf{a}, \mathbf{b}) , \end{aligned}

where nAn_A and nBn_B are the cluster sizes.

In plain words Two groups count as close only when all of their members are close. Complete linkage favors compact groups of limited diameter and resists chaining. A single far member can keep two groups apart, and with rounded or integer data two candidate merges can easily share the same farthest distance, as in the example below.

Example After A and B merge, complete linkage gives max⁡(3,2)=3\max(3, 2) = 3 from AB to C, max⁡(6,5)=6\max(6, 5) = 6 from AB to D, and 3 from C to D, which is a tie. The tie rule of this page picks AB with C, and ABC then joins D at max⁡(6,5,3)=6\max(6, 5, 3) = 6. The merge heights are 1, 3 and 6. The opposite tie choice would merge C with D at 3 and then AB with CD at 6, with the same heights but the two clusters {A,B}\{A, B\} and {C,D}\{C, D\} instead of {A,B,C}\{A, B, C\} and {D}\{D\}. Average linkage merges AB with C at (3+2)/2=2.5(3 + 2)/2 = 2.5 and then ABC with D at (6+5+3)/3=14/3≈4.67(6 + 5 + 3)/3 = 14/3 \approx 4.67.

Ward’s criterion

Definition Ward’s criterion applies to observations that are vectors in Euclidean space. It merges the pair of clusters whose union increases the total within-cluster sum of squares the least. For disjoint clusters AA and BB with sizes nAn_A and nBn_B and centroids μA\boldsymbol{\mu}_A and μB\boldsymbol{\mu}_B, that increase is

Δ(A,B)=nAnBnA+nB⋅∥μA−μB∥22.\begin{aligned} \Delta(A, B) &= \frac{n_A n_B}{n_A + n_B} \\[0.4em] &\quad \cdot \lVert \boldsymbol{\mu}_A - \boldsymbol{\mu}_B \rVert_2^2 . \end{aligned}

The size factor means that Ward does not simply merge the nearest centroids. The total starts at 0 with single points and ends at the sum of squares of all points about their overall mean, so the increases along the hierarchy add up to that total. This meaning needs squared Euclidean distances between the original vectors. Running the same merge rule on an arbitrary dissimilarity matrix produces a tree, but its heights no longer measure a sum of squares. Software may plot a different height for Ward merges, such as 2Δ\sqrt{2\Delta}, which equals the Euclidean distance when two single points merge, so the axis has to say which quantity it shows.

In plain words Ward asks which merge would raise the k-means objective the least. It favors compact groups of similar size, and it judges every level of its tree by the same within-cluster sum of squares as k-means. Because each merge is chosen greedily, a cut need not be the best k-means partition with that number of clusters.

Example For A and B, Δ=12⋅12=0.5\Delta = \tfrac{1}{2} \cdot 1^2 = 0.5. The merged cluster has size 2 and centroid (0.5,0)(0.5, 0). Joining it with C costs 23⋅2.52=25/6≈4.167\tfrac{2}{3} \cdot 2.5^2 = 25/6 \approx 4.167, joining it with D costs 23⋅5.52=121/6≈20.17\tfrac{2}{3} \cdot 5.5^2 = 121/6 \approx 20.17, and joining C with D costs 12⋅32=4.5\tfrac{1}{2} \cdot 3^2 = 4.5, so AB joins C. The cluster ABC has centroid (4/3,0)(4/3, 0), and joining it with D costs

34(6−43)2=493≈16.333.\frac{3}{4}\Bigl(6 - \frac{4}{3}\Bigr)^2 = \frac{49}{3} \approx 16.333 .

The increases add up to 1/2+25/6+49/3=211/2 + 25/6 + 49/3 = 21. The four points have mean (2.5,0)(2.5, 0), and their sum of squares about it is 6.25+2.25+0.25+12.25=216.25 + 2.25 + 0.25 + 12.25 = 21, as it should be.

Dendrogram

Definition A dendrogram draws the hierarchy as a tree. The leaves are the observations, and each merge is drawn as a bar that joins the two merged clusters at the height of the merge. For single, complete, average and Ward linkage the merge heights never decrease, so no merge is drawn below an earlier one. Cutting the tree at a height hh between two consecutive merge heights keeps the merges below hh and gives the partition at that level. The left-to-right order of the leaves is a drawing choice, since swapping the two branches at any merge leaves the hierarchy unchanged. The height at which two observations first share a cluster is their cophenetic distance.

In plain words Read a dendrogram vertically. The height of the bar that joins two groups says how far apart they were under the linkage, and the horizontal gap between two leaves means nothing. A cut chooses a grouping scale under one linkage rule. It does not reveal the true number of groups.

Example Cutting the single linkage tree of A, B, C and D at height 2.5 keeps its merges at 1 and 2 and gives {A,B,C}\{A, B, C\} and {D}\{D\}. The same cut of the complete linkage tree keeps only its merge at 1 and gives {A,B}\{A, B\}, {C}\{C\} and {D}\{D\}. The cophenetic distance of A and D is 3 under single linkage and 6 under complete linkage, while their Euclidean distance is 6.

Cluster stability

Definition Cluster stability is the degree to which a clustering persists when the analysis is repeated under plausible perturbations, such as resampling the observations, adding small measurement noise, making other reasonable preprocessing choices or changing the tie rule. It is measured by comparing the clusterings, for example by the Rand index, the fraction of pairs of observations on which the two clusterings agree about being together or apart, or by the Jaccard similarity between each original cluster and its best match. Stability is evidence that a grouping is not an accident of one sample or one setting. It does not show that the groups are meaningful categories, because a stable grouping can come from a feature scale or a measurement convention.

In plain words If a small, reasonable change in the data or the settings moves points between groups, the groups are fragile and should be reported as such. Groups that survive such changes are at least reproducible, which is a weaker claim than being real. Labels such as “loyal customers” need evidence from outside the clustering.

Example Move C from (3,0)(3, 0) to (3.1,0)(3.1, 0). Complete linkage now merges C with D at 2.9, before AB can join C at 3.1, so its two-cluster cut becomes {A,B}\{A, B\} and {C,D}\{C, D\}. Single linkage still gives {A,B,C}\{A, B, C\} and {D}\{D\}, because the gap of 2.1 from B to C stays below the gap of 2.9 from C to D. Moving C to (2.9,0)(2.9, 0) instead leaves both methods at {A,B,C}\{A, B, C\} and {D}\{D\}. A stability check would flag C as a point whose group depends on a small change.

Check yourself

  1. On a line, cluster E contains the points 0 and 2 and cluster F contains 5 and 6. Find the single linkage, complete linkage and average linkage values between E and F, and Ward’s increase for merging them.
Show the answer

The four distances between members of E and members of F are 55, 66, 33 and 44. Single linkage takes the smallest, 3, complete linkage the largest, 6, and average linkage their mean, 18/4=4.518/4 = 4.5.

For Ward the cluster means are 1 and 5.5 and both sizes are 2, so the size factor is (2⋅2)/4=1(2 \cdot 2)/4 = 1 and

Δ=1⋅(5.5−1)2=20.25\Delta = 1 \cdot (5.5 - 1)^2 = 20.25

in squared units. A direct check agrees. The merged cluster has mean 3.25 and sum of squares 10.5625+1.5625+3.0625+7.5625=22.7510.5625 + 1.5625 + 3.0625 + 7.5625 = 22.75, while E and F have sums of squares 2 and 0.5, and 22.75−2.5=20.2522.75 - 2.5 = 20.25. The four numbers measure different things, so they are not interchangeable.

  1. Under single linkage on A, B, C and D, at what height do A and D first share a cluster, and is that their distance? Then cut the single linkage and complete linkage trees at height 4.
Show the answer

They first share a cluster at height 3, when ABC joins D. That is their cophenetic distance, not their Euclidean distance of 6. It equals the largest step in the best chain from A to D, the step of 3 from C to D.

At height 4 the single linkage tree has made all three merges, at 1, 2 and 3, so the cut gives one cluster with all four points. The complete linkage tree has made the merges at 1 and 3 but not the one at 6, so the cut gives {A,B,C}\{A, B, C\} and {D}\{D\}. The same height means different things under different linkages, and neither cut shows how many groups really exist.

  1. Move C to (3.1,0)(3.1, 0) and build the Ward hierarchy again. Give every merge and its increase, check the increases against the total sum of squares, and compare the two-cluster cut with the one for C at (3,0)(3, 0).
Show the answer

Among single points, A and B have the smallest increase, 12⋅12=0.5\tfrac{1}{2} \cdot 1^2 = 0.5, against 12⋅2.12=2.205\tfrac{1}{2} \cdot 2.1^2 = 2.205 for B and C. Next, joining AB, with centroid (0.5,0)(0.5, 0), to C costs 23⋅2.62≈4.507\tfrac{2}{3} \cdot 2.6^2 \approx 4.507, joining AB to D costs 23⋅5.52≈20.17\tfrac{2}{3} \cdot 5.5^2 \approx 20.17, and joining C to D costs 12⋅2.92=4.205\tfrac{1}{2} \cdot 2.9^2 = 4.205, so C and D merge. Their centroid is (4.55,0)(4.55, 0), and the last merge costs

2⋅24⋅(4.55−0.5)2=16.4025.\frac{2 \cdot 2}{4} \cdot (4.55 - 0.5)^2 = 16.4025 .

The increases add up to 0.5+4.205+16.4025=21.10750.5 + 4.205 + 16.4025 = 21.1075. The four points have mean 2.525 on the line, and their squared deviations 6.3756256.375625, 2.3256252.325625, 0.3306250.330625 and 12.07562512.075625 also add up to 21.107521.1075.

The two-cluster cut is now {A,B}\{A, B\} and {C,D}\{C, D\}, while with C at (3,0)(3, 0) it was {A,B,C}\{A, B, C\} and {D}\{D\}. A shift of 0.1 in one point moved C to the other group, so a report should present C’s group as unstable and should not attach meaning to either cut without further evidence.

How this lesson connects