Linkage Properties of Agglomerative Clustering

Why the linkage criteria of hierarchical agglomerative clustering behave as they do, with proofs. The distance-update rules, monotonic merge heights for single, complete and average linkage, the group-average vector-sum formula, centroid inversions, single linkage as a minimum spanning tree, the priority-queue algorithm and best-merge persistence, and three exercises of the course text solved in full.

Hierarchical clustering traced four linkage criteria on six points on a line and drew their trees. In every tree each merge sat higher than the one before. Is that guaranteed, and what else about a tree follows from the linkage alone? For single, complete and average linkage it is guaranteed, and this article proves it from the rules that update cluster distances after a merge. The same rules explain why centroid linkage can invert a tree, why single linkage builds a minimum spanning tree, and why single linkage alone can be computed in quadratic time.

The linkage is the rule that turns distances between documents into a distance between clusters. Hierarchical clustering defines the four used here: single (the closest cross pair), complete (the farthest cross pair), average (the mean over cross pairs, with the textbook's group-average variant taken over all pairs of the merged cluster) and centroid. This article holds the proofs of their properties, and that article uses the results.

Here is the route. First come the update rules, and from them the proof that merge heights never decrease, the vector-sum formula for group-average similarity, and the centroid rule with its inversions. Then single linkage is shown to make the same choices as Kruskal's minimum spanning tree algorithm. Next the cost of the priority-queue algorithm is counted, and best-merge persistence brings single linkage down to $O(N^2)$. Three exercises of the course text close the article. It follows Manning, Raghavan, and Schütze (2008, chapter 17).

The running example is the one of hierarchical clustering: six points on a line at $a = 0$, $b = 1$, $c = 2.5$, $d = 4.5$, $e = 5.7$ and $f = 9.5$, with the distance between two points the difference of their positions. "The example" and "the worked example" below mean those six points, and "the table" of merges is the one in that article. Its single-link merges are $a + b$ at 1, $d + e$ at 1.2, then $c$ at 1.5, then $\{a, b, c\}$ with $\{d, e\}$ at 2, and $f$ last at 3.8. Complete linkage instead joins $f$ to $\{d, e\}$ at 5.

Updating cluster distances

After a merge, HAC needs the distance from the new cluster $i \cup j$ to every other cluster $k$. Recomputing it from all document pairs would be slow, but each linkage has a rule that uses only the distances already known (sizes are written $n_i$, $n_j$):

Linkage Distance from $k$ to the merged cluster $i \cup j$
Single $\min(D_{ki}, D_{kj})$
Complete $\max(D_{ki}, D_{kj})$
Average $\dfrac{n_i D_{ki} + n_j D_{kj}}{n_i + n_j}$

The single and complete rules hold because the cross pairs between $k$ and $i \cup j$ are the cross pairs with $i$ together with those with $j$. The smallest of all of them is the smaller of the two minima, and the largest is the larger of the two maxima. The average rule holds for the same reason: $k$ has $n_k n_i$ cross pairs with $i$ and $n_k n_j$ with $j$, so the mean over all of them is the size-weighted mean of the two averages. In the example, the average distances from $f$ to $\{a, b, c\}$ and to $\{d, e\}$ are 8.33 and 4.4. After $\{a, b, c\}$ and $\{d, e\}$ merge, the distance from $f$ to the new cluster is $(3 \times 8.33 + 2 \times 4.4) / 5 = 6.76$, matching the last merge in the table. Rules of this kind, which give the new distance from $D_{ki}$, $D_{kj}$, $D_{ij}$ and the cluster sizes alone, were put in one general form by Lance and Williams (1967).

Why merge heights never decrease

Here is the idea in one sentence: each of the three rules returns a value between $D_{ki}$ and $D_{kj}$, and both of those were at least the height of the merge just made.

Claim. Under single, complete or cross-pair average linkage, the merge heights satisfy $h_1 \le h_2 \le \dots \le h_{N-1}$.

Proof. Suppose a step merges clusters $i$ and $j$ at height $h = D_{ij}$. HAC merges the closest pair, so $h$ is the smallest distance between any two clusters present at that step. In particular $D_{ki} \ge h$ and $D_{kj} \ge h$ for every other cluster $k$, and $D_{k\ell} \ge h$ for every pair of other clusters $k$ and $\ell$.

After the merge, the distances between clusters are of two kinds. Those between two clusters that took no part in the merge are unchanged, so they are still at least $h$. Those from a cluster $k$ to the new cluster $i \cup j$ come from the update rule:

  • single: $\min(D_{ki}, D_{kj}) \ge h$, because both arguments are at least $h$;
  • complete: $\max(D_{ki}, D_{kj}) \ge \min(D_{ki}, D_{kj}) \ge h$;
  • average: a weighted mean with positive weights $n_i / (n_i + n_j)$ and $n_j / (n_i + n_j)$ that add to 1 is at least the smaller of the two values, so it is at least $\min(D_{ki}, D_{kj}) \ge h$.

So every distance present after the merge is at least $h$. The next merge takes place at the smallest of them, so its height is at least $h$. Applying this at every step gives the chain of inequalities. $\blacksquare$

The script confirms it on the six points and, with a library implementation, on 30 random sets of 25 points for each linkage. It also runs the three update rules themselves on 30 random sets of 12 points each, checking every updated distance against its definition and every sequence of heights. The proof used only one property of a rule: the new distance is never below $\min(D_{ki}, D_{kj})$. The centroid rule derived below subtracts a term and lacks that property.

Group-average similarity from vector sums

For group-average clustering with dot-product similarity, the textbook gives an even cheaper form than an update rule. Here is the idea in one sentence: the squared length of a cluster's vector sum already contains every pairwise dot product, so one vector sum per cluster is enough.

The formal version. Let the documents be unit vectors, so each has dot product 1 with itself. Let clusters $\omega_i$ and $\omega_j$ hold $N_i$ and $N_j$ documents, and write $n = N_i + N_j$ for the size of the merged cluster $\omega = \omega_i \cup \omega_j$. It has $n(n - 1)$ ordered pairs of distinct documents. The group-average similarity is the mean dot product over those pairs:

$$\text{SIM-GA}(\omega_i, \omega_j) = \frac{1}{n(n - 1)} \sum_{\vec{d}_m \in \omega} \; \sum_{\substack{\vec{d}_\ell \in \omega \\ \ell \ne m}} \vec{d}_m \cdot \vec{d}_\ell .$$

Counting each pair in both orders does not change the mean, because $\vec{d}_m \cdot \vec{d}_\ell = \vec{d}_\ell \cdot \vec{d}_m$. Now let $\vec{s} = \sum_{\vec{d}_m \in \omega} \vec{d}_m$ be the vector sum of the merged cluster. Expanding its dot product with itself, term by term, gives every ordered pair, including each document paired with itself:

$$\vec{s} \cdot \vec{s} = \sum_{m} \sum_{\ell} \vec{d}_m \cdot \vec{d}_\ell = \sum_{m} \sum_{\ell \ne m} \vec{d}_m \cdot \vec{d}_\ell + \sum_{m} \vec{d}_m \cdot \vec{d}_m = \sum_{m} \sum_{\ell \ne m} \vec{d}_m \cdot \vec{d}_\ell + n .$$

The last step uses the unit lengths: the $n$ self-similarities are 1 each. Solving for the double sum and dividing by $n(n - 1)$:

$$\text{SIM-GA}(\omega_i, \omega_j) = \frac{\lvert \vec{s} \rvert^2 - n}{n(n - 1)}, \qquad \vec{s} = \vec{s}_i + \vec{s}_j ,$$

where $\vec{s}_i$ and $\vec{s}_j$ are the vector sums of the two clusters. This is the formula of the textbook's §17.3 (Manning, Raghavan, and Schütze, 2008). Keeping one vector sum per cluster gives each cluster similarity in time that does not depend on the cluster sizes, in place of $N_i N_j$ dot products.

Example (three unit vectors). For $\vec{d}_1 = (1, 0)$, $\vec{d}_2 = (0.6, 0.8)$ and $\vec{d}_3 = (0, 1)$, the formula gives the group-average similarity $0.467$, the same as averaging the three pairs directly. The pairwise dot products are 0.6, 0.8 and 0, with mean $1.4 / 3 \approx 0.467$. The vector sum is $(1.6, 1.8)$, with squared length $2.56 + 3.24 = 5.8$, and $(5.8 - 3) / (3 \times 2) = 2.8 / 6 \approx 0.467$.

Example (a common misstatement). "Group-average similarity is the squared length of the centroid" is true only of the variant that counts self-similarities. Dividing $\vec{s} \cdot \vec{s}$ by all $n^2$ ordered pairs gives $\lvert \vec{s} / n \rvert^2$, the squared length of the centroid. For the three vectors above that is $5.8 / 9 \approx 0.644$, not 0.467. The textbook defines both and prefers the version without self-similarities. It gives two reasons (§17.3). The $n$ self-similarities are a larger share of the $n^2$ pairs in a small cluster, which favors small clusters. And with self-similarities, two documents with similarity $s$ get cluster similarity $(1 + s)/2$ and not $s$, unlike the other three methods.

The derivation needs vectors, unit lengths and the dot product. Single and complete linkage need only a table of similarities, however it was computed.

Centroid linkage and inversions

The rule for centroid linkage, with squared Euclidean distances between centroids, is the one place where something surprising happens. Here is the idea in one sentence: the update rule is a weighted average like average linkage's, minus a term that grows with how far apart the two merged clusters were.

The formal version. Write $\vec{\mu}_i$, $\vec{\mu}_j$, $\vec{\mu}_k$ for the centroids and $n = n_i + n_j$. The merged centroid is $\vec{m} = (n_i \vec{\mu}_i + n_j \vec{\mu}_j)/n$, so

$$\vec{\mu}_k - \vec{m} = \frac{n_i}{n} (\vec{\mu}_k - \vec{\mu}_i) + \frac{n_j}{n} (\vec{\mu}_k - \vec{\mu}_j).$$

Squaring, and writing the cross term with $\vec{u} = \vec{\mu}_k - \vec{\mu}_i$ and $\vec{w} = \vec{\mu}_k - \vec{\mu}_j$ as $2\,\vec{u} \cdot \vec{w} = \lvert \vec{u} \rvert^2 + \lvert \vec{w} \rvert^2 - \lvert \vec{u} - \vec{w} \rvert^2$, where $\vec{u} - \vec{w} = \vec{\mu}_j - \vec{\mu}_i$, gives

$$\lvert \vec{\mu}_k - \vec{m} \rvert^2 = \frac{n_i}{n} \lvert \vec{\mu}_k - \vec{\mu}_i \rvert^2 + \frac{n_j}{n} \lvert \vec{\mu}_k - \vec{\mu}_j \rvert^2 - \frac{n_i n_j}{n^2} \lvert \vec{\mu}_i - \vec{\mu}_j \rvert^2.$$

The first two terms are a weighted average, like the average-linkage rule. The third is subtracted, and it is large when the two clusters just merged were far apart. That can make the new cluster closer to $k$ than $i$ and $j$ were to each other.

Three points show it. Put $d_1 = (0, 0)$, $d_2 = (4, 0)$ and $d_3 = (2, 3.6)$. The closest pair is $d_1$, $d_2$ at distance 4 ($d_3$ is $\sqrt{2^2 + 3.6^2} \approx 4.12$ from each). Their centroid is $(2, 0)$, which is only 3.6 from $d_3$. By the formula, $\tfrac{1}{2}(16.96) + \tfrac{1}{2}(16.96) - \tfrac{1}{4}(16) = 12.96 = 3.6^2$. So the second merge happens at a smaller distance, 3.6, than the first, 4.

This is an inversion. In the dendrogram the second merge line is drawn below the first, and the tree no longer says that clusters merged later are less alike (Manning, Raghavan, and Schütze, 2008, §17.4, give an example of the same shape).

A centroid-linkage inversion. Left: d1 and d2 are the closest pair, 4 apart, but their centroid (the cross) is only 3.6 from d3. Right: the dendrogram; notice that the second merge, at 3.6, sits below the first, at 4.
A centroid-linkage inversion. Left: d1 and d2 are the closest pair, 4 apart, but their centroid (the cross) is only 3.6 from d3. Right: the dendrogram; notice that the second merge, at 3.6, sits below the first, at 4.

Example (the same three points under single linkage). Single linkage produces no inversion on these three points. It also merges $d_1$ and $d_2$ first, at 4. It then scores $d_3$ against $\{d_1, d_2\}$ by the nearer of the two points, about 4.12, so the second merge sits above the first. Complete and average linkage give the same 4.12 here, since $d_3$ is equally far from both points.

That fits the monotonicity of single, complete and average linkage proved above. With dot-product similarity, centroid linkage coincides with cross-pair average linkage, by the identity proved under the list of linkages in hierarchical clustering. The proof of monotonicity carries over to similarities with every inequality reversed, so centroid linkage in that form is monotone. The inversion belongs to centroids compared by Euclidean distance.

Example (a common misstatement). "Centroid clustering is not monotonic" needs its measure stated. With centroids compared by Euclidean distance the three points above invert, at heights 4 and then 3.6. With centroids compared by dot product, the similarity of two clusters is the average over cross pairs, and no inversion can occur.

Single linkage and the minimum spanning tree

Single linkage's chains, the weakness that hierarchical clustering calls chaining, have an exact description. Treat the documents as the points of a graph, with an edge between every two documents whose weight is their distance. A spanning tree is a set of $N - 1$ edges that connects all $N$ points. A minimum spanning tree is one whose weights add up to the least possible total.

Kruskal's (1956) algorithm builds one. It goes through the edges from lightest to heaviest and keeps an edge whenever its two ends are not yet connected by the edges already kept. Here is the idea of the equivalence in one sentence: the groups of points connected by Kruskal's kept edges are the single-link clusters, and the next edge Kruskal keeps is the next single-link merge.

Claim. Single-link HAC and Kruskal's algorithm, breaking ties the same way, make the same choices. The $m$-th single-link merge joins the two clusters containing the ends of the $m$-th edge Kruskal keeps, at a height equal to that edge's weight.

Proof. By induction on $m$, we show that after $m$ steps the single-link clusters are the connected groups of Kruskal's kept edges. Before any step, both are the $N$ single points. Suppose the two agree after $m$ steps.

Kruskal's next kept edge is the lightest edge whose ends are not yet connected. Every lighter edge was already kept or skipped, and an edge is skipped only when its ends are already connected. Ends that are connected stay connected, so a skipped edge is never kept later. By the induction hypothesis, "not yet connected" means "in two different clusters". So Kruskal keeps the lightest edge that runs between two different clusters.

Single linkage merges the two clusters at the smallest single-link distance. The single-link distance of two clusters is the weight of the lightest edge between them. So the smallest single-link distance over all pairs of clusters is the weight of the lightest edge between any two different clusters. That is the same edge, and the merge height is its weight. Keeping the edge connects exactly the two groups that the merge joins, so the two still agree after $m + 1$ steps. $\blacksquare$

It remains to see that Kruskal's $N - 1$ kept edges form a minimum spanning tree, which is the classical correctness proof of the algorithm.

Claim. At every step, the edges Kruskal has kept are contained in some minimum spanning tree.

Proof. With no edges kept, the claim holds for any minimum spanning tree. Suppose the kept edges $F$ are contained in a minimum spanning tree $T$, and Kruskal next keeps the edge $e$, which joins the connected groups $A$ and $B$ of $F$. If $e$ is in $T$, we are done. Otherwise, adding $e$ to $T$ closes a cycle, because $T$ already connects the ends of $e$. The cycle leaves $A$ along $e$, so it must return to $A$ along another edge $e'$ with one end in $A$ and one outside. The edge $e'$ is not in $F$, because no edge of $F$ leaves the group $A$. Its ends are in different groups, so Kruskal could have kept it, and Kruskal chose $e$ as the lightest such edge. So the weight of $e$ is at most that of $e'$. Replacing $e'$ by $e$ in $T$ gives a set of $N - 1$ edges that still connects every point, since any path that used $e'$ can go round the rest of the cycle. Its total weight is no larger than that of $T$. It is therefore a minimum spanning tree, and it contains $F$ and $e$. $\blacksquare$

At the end Kruskal has kept $N - 1$ edges contained in a minimum spanning tree, which has only $N - 1$ edges, so they are that tree. Two consequences follow. The single-link merge heights are the weights of a minimum spanning tree's edges in increasing order. Cutting the single-link dendrogram into $K$ clusters is the same as deleting the $K - 1$ heaviest edges of the tree, because that undoes the last $K - 1$ merges. Gower and Ross (1969) showed that a minimum spanning tree holds everything needed for the single-link clustering. The course text poses the connection as its Exercise 17.5.

Example (the six points). The minimum spanning tree of the six points is the path $a$–$b$–$c$–$d$–$e$–$f$, with total weight 9.5. Kruskal keeps $a$–$b$ at 1, $d$–$e$ at 1.2, $b$–$c$ at 1.5, $c$–$d$ at 2 and $e$–$f$ at 3.8, and skips every other edge. Those five weights are the single-link merge heights of the worked example, in the same order. Deleting the heaviest edge, $e$–$f$, leaves $\{a, b, c, d, e\}$ and $\{f\}$, the two-cluster cut of the single-link tree. The script checks the tree against SciPy's minimum-spanning-tree routine, here and on 30 random sets of 20 points.

Cost

Naive HAC computes all $N^2$ document similarities, then at each of $N - 1$ merges scans every pair of clusters for the most similar. With $m$ clusters left, a scan looks at about $m^2/2$ pairs. Adding this up for $m = N, N - 1, \dots, 2$ gives about $N^3/6$ comparisons, $O(N^3)$ in total.

The priority-queue algorithm avoids the repeated scans (Manning, Raghavan, and Schütze, 2008, §17.2.1). Each cluster keeps its similarities to all other clusters in a priority queue, so its best partner is always at the front.

  1. Build one queue per document, holding its similarities to the other $N - 1$ documents: $O(N^2 \log N)$ in all, or $O(N^2)$ with a heap built in linear time.
  2. To find the next merge, look at the front of each of the at most $N$ queues and take the best: $O(N)$.
  3. After merging $i$ and $j$, go through every other cluster $k$: delete its entries for $i$ and $j$, compute the distance to the new cluster with the update rule above, and insert it. That is a constant number of queue operations for each of up to $N$ clusters. With a priority queue that supports deleting any entry in $O(\log N)$, such as an indexed heap or a balanced search tree, the cost is $O(N \log N)$ per merge. The new cluster gets a fresh queue built from the same values.

With $N - 1$ merges, the total is $O(N^2 \log N)$. In the example, $c$'s queue starts as $b$ 1.5, $d$ 2, $a$ 2.5, $e$ 3.2, $f$ 7, nearest first. When $a$ and $b$ merge, the entries for $a$ and $b$ are deleted and one for $\{a, b\}$ is inserted. Under single linkage it is inserted at 1.5 and goes to the front. Under complete linkage it is inserted at 2.5 and goes behind $d$.

Single linkage can be done in $O(N^2)$. It has a property the others lack, which the textbook calls best-merge persistence: if $j$ is the best partner of $k$, and $j$ then merges with some other cluster, the merged cluster is still the best partner of $k$. It is therefore enough to remember one best partner per cluster instead of a whole queue (Manning, Raghavan, and Schütze, 2008, §17.2.1).

Claim. Under single linkage, let $j$ be a nearest cluster to $k$, so that $D_{kj} \le D_{k\ell}$ for every other cluster $\ell$. If $j$ merges with a cluster $i \ne k$, then $i \cup j$ is a nearest cluster to $k$, at the same distance $D_{kj}$.

Proof. The single-link update rule gives $D_{k, i \cup j} = \min(D_{ki}, D_{kj})$. Since $j$ is nearest to $k$, $D_{kj} \le D_{ki}$, so the minimum is $D_{kj}$. The distance from $k$ to every cluster $\ell$ other than $i$ and $j$ is unchanged by the merge, and it was at least $D_{kj}$. So no cluster is nearer to $k$ than $i \cup j$. $\blacksquare$

Two other cases complete the bookkeeping. A merge of two clusters $i$ and $\ell$, both different from $j$ and $k$, produces a cluster at distance $\min(D_{ki}, D_{k\ell}) \ge D_{kj}$ from $k$, so $j$ stays nearest. When $k$ itself merges with a cluster $i$, the distance from the new cluster to each other cluster $\ell$ is $\min(D_{k\ell}, D_{i\ell})$, one minimum of two stored values per cluster. Its nearest cluster is then found by scanning those $N$ or fewer new values. In every case the work is $O(N)$ per merge: one pass to update the merged row, and one scan for the merged cluster's best partner. Every other cluster keeps its stored best partner, or replaces it by the merged cluster, by the claim and the case above. Over $N - 1$ merges that is $O(N^2)$ (Manning, Raghavan, and Schütze, 2008, Figure 17.9).

Example (complete linkage loses its best partner). In the worked example, the first complete-link merge changes $c$'s best partner from $b$ to $d$. Before any merge, $c$'s nearest point is $b$, at 1.5; $d$ is second, at 2. Then $a$ and $b$ merge, at height 1. Under complete linkage the distance from $c$ to $\{a, b\}$ is $\max(2.5, 1.5) = 2.5$, which is more than the 2 from $c$ to $d$. So the cluster that absorbed $c$'s best partner is no longer $c$'s best partner. Under single linkage the distance from $c$ to $\{a, b\}$ is $\min(2.5, 1.5) = 1.5$, and $\{a, b\}$ remains nearest, as the claim says. Complete linkage therefore needs the whole queue: after a merge, a cluster's new best partner can be any cluster. Problem 2 of the worked problems gives a counterexample for group-average and centroid clustering.

Worked problems

The three problems are Exercises 17.11, 17.6 and 17.10 of the course text (Manning, Raghavan, and Schütze, 2008), numbered as in the printed book and restated in our own words. The solutions are ours, and the script checks every number in them. Exercise 17.9 is solved in hierarchical clustering.

Problem 1 (Exercise 17.11). Prove that single-link, complete-link and group-average clustering are monotonic: the similarities $s_1, s_2, \dots, s_{N-1}$ of successive merges satisfy $s_1 \ge s_2 \ge \dots \ge s_{N-1}$.

The exercise is stated with similarities, so HAC merges the pair of clusters with the largest similarity. Write $S_{k\ell}$ for the similarity of clusters $k$ and $\ell$. Suppose a step merges $i$ and $j$ at similarity $s = S_{ij}$, the largest similarity between any two clusters present. It is enough to show that every similarity present after the merge is at most $s$, because the next merge takes place at the largest of them. Similarities between two clusters that took no part in the merge are unchanged, so they are at most $s$. That leaves the similarity of each other cluster $k$ to $i \cup j$.

Single link. The new similarity is the largest over all cross pairs, $\max(S_{ki}, S_{kj})$. Both arguments are at most $s$, so the maximum is at most $s$.

Complete link. The new similarity is the smallest over all cross pairs, $\min(S_{ki}, S_{kj}) \le S_{ki} \le s$.

Group average. Here the similarity of two clusters is the mean dot product over all pairs of distinct documents in their union. It is not a function of $S_{ki}$ and $S_{kj}$ alone, so a different argument is needed. For a set of documents $\omega$, write $p(\omega)$ for its number of unordered pairs of distinct documents and $\Sigma(\omega)$ for the sum of the dot products of those pairs. Then $\text{SIM-GA}(\omega_k, \omega_\ell) = \Sigma(\omega_k \cup \omega_\ell) / p(\omega_k \cup \omega_\ell)$. For a single document, $p = 0$ and $\Sigma = 0$.

We prove more than is asked, by induction over the merges. The statement $(\ast)$ is: at every stage, each cluster $\omega$ present satisfies $\Sigma(\omega) \ge t \, p(\omega)$ for every similarity $t$ between two clusters present. In words, every cluster's internal average is at least as large as any merge still on offer. At the start every cluster is a single document, and $(\ast)$ reads $0 \ge 0$.

Suppose $(\ast)$ holds and the step merges $i$ and $j$ at the largest similarity $s$. Take another cluster $k$. Every pair of documents in $i \cup j \cup k$ lies within one of the three clusters or crosses between two of them. Adding the pairs of $i \cup j$, $i \cup k$ and $j \cup k$ counts each crossing pair once and each pair within a cluster twice. So

$$\Sigma(i \cup j \cup k) = \Sigma(i \cup j) + \Sigma(i \cup k) + \Sigma(j \cup k) - \Sigma(i) - \Sigma(j) - \Sigma(k),$$

and the same identity holds with $p$ in place of $\Sigma$. Now bound each term. First, $\Sigma(i \cup j) = s \, p(i \cup j)$ by the definition of $s$. Next, $\Sigma(i \cup k) \le s \, p(i \cup k)$ and $\Sigma(j \cup k) \le s \, p(j \cup k)$, because $s$ is the largest similarity present. Finally, $\Sigma(i) \ge s \, p(i)$, $\Sigma(j) \ge s \, p(j)$ and $\Sigma(k) \ge s \, p(k)$ by $(\ast)$. Therefore

$$\Sigma(i \cup j \cup k) \le s \, \big[ p(i \cup j) + p(i \cup k) + p(j \cup k) - p(i) - p(j) - p(k) \big] = s \, p(i \cup j \cup k).$$

Dividing by $p(i \cup j \cup k)$ gives $\text{SIM-GA}(i \cup j, k) \le s$. So every similarity present after the merge is at most $s$, and the next merge has $s' \le s$.

It remains to check that $(\ast)$ still holds after the merge. Let $t$ be any similarity now present, so $t \le s$. A cluster $\omega$ that took no part in the merge had $\Sigma(\omega) \ge s \, p(\omega)$, and $s \, p(\omega) \ge t \, p(\omega)$ because $p(\omega) \ge 0$. The new cluster has $\Sigma(i \cup j) = s \, p(i \cup j) \ge t \, p(i \cup j)$. So $(\ast)$ holds at the next stage, and the induction is complete. $\blacksquare$

The script runs group-average clustering on 30 random sets of 12 unit vectors and finds no increase in any sequence of merge similarities. It also checks the identity for $\Sigma$ on random sets of vectors, and the statement $(\ast)$ at every stage of those runs.

Problem 2 (Exercise 17.6). Show that single-link clustering is best-merge persistent and that group-average and centroid clustering are not.

Single link is best-merge persistent by the claim proved under Cost, read with similarities. If $S_{kj} \ge S_{k\ell}$ for every other cluster $\ell$, and $j$ merges with $i \ne k$, the new similarity is $\max(S_{ki}, S_{kj}) = S_{kj}$. Every other similarity of $k$ is unchanged and at most $S_{kj}$, so $i \cup j$ is a best partner of $k$.

For the other two methods, one counterexample serves both. Take four unit vectors in the plane at angles of 0°, 28°, 58° and 89° from the first axis, and call them $v_1$, $v_2$, $v_3$, $v_4$. The dot product of two unit vectors is the cosine of the angle between them:

$v_2$ $v_3$ $v_4$
$v_1$ 0.8829 0.5299 0.0175
$v_2$ 0.8660 0.4848
$v_3$ 0.8572

Between single documents every method uses the dot product itself. The largest entry is $v_1 \cdot v_2 = 0.8829$, so the first merge joins $v_1$ and $v_2$ under every method. Before that merge, the best partner of $v_3$ is $v_2$, at 0.8660, ahead of $v_4$ at 0.8572. After it, the similarity of $v_3$ to the merged cluster $\{v_1, v_2\}$ is:

  • single link: $\max(0.5299, 0.8660) = 0.8660$, still ahead of $v_4$;
  • group average: the mean over the three pairs of $\{v_1, v_2, v_3\}$, $(0.8829 + 0.8660 + 0.5299) / 3 \approx 0.7596$;
  • centroid: the dot product of $v_3$ with the centroid of $v_1$ and $v_2$, which is the mean over the two cross pairs, $(0.5299 + 0.8660) / 2 \approx 0.6980$.

Both 0.7596 and 0.6980 are below $v_3 \cdot v_4 = 0.8572$. Under group-average and centroid clustering the best partner of $v_3$ is now $v_4$, not the cluster that absorbed its former best partner. So neither method is best-merge persistent. The cause is the distant $v_1$: averaging brings its low similarity to $v_3$ into the score, while single link ignores it.

Problem 3 (Exercise 17.10). For single-link clustering of $N$ points on a line, show that only about $N$ similarities need to be computed, and find the overall complexity.

Only the $N - 1$ distances between neighboring points are needed, and the whole clustering costs $O(N \log N)$. We work with distances and assume the points are distinct.

Claim. At every step, the closest two points that lie in different clusters are neighbors on the line: no other point lies between them.

Proof. Let $x < z$ be points in different clusters with a point $y$ strictly between them. The point $y$ cannot be in the cluster of $x$ and also in the cluster of $z$, since those differ. If $y$ is not in the cluster of $x$, then $x$ and $y$ are in different clusters at distance $y - x < z - x$. Otherwise $y$ is not in the cluster of $z$, and $y$ and $z$ are in different clusters at distance $z - y < z - x$. Either way $x$ and $z$ are not the closest such pair. $\blacksquare$

The single-link distance between two clusters is the distance of their closest cross pair. So each merge joins the clusters of two neighboring points, at a height equal to the gap between them. After the merge those two neighbors share a cluster, so that gap is never used again. There are $N - 1$ merges and $N - 1$ gaps, so every gap is used exactly once. Single-link merge heights never decrease, as proved above, so the merges are the gaps in increasing order.

The algorithm follows. Sort the points, $O(N \log N)$. Compute the $N - 1$ gaps between neighbors, $O(N)$, in place of the $N(N - 1)/2$ distances of the general case. Sort the gaps, $O(N \log N)$, and report them in that order as the merges. Equal gaps may be taken in any order, as a tie rule decides. The merge for a gap joins the clusters that contain the two points on either side of it. A union-find structure names those clusters in near-constant time per merge, so the total stays within the bound. The total is $O(N \log N)$, against $O(N^2)$ for single linkage in general.

On the six points the gaps are 1, 1.5, 2, 1.2 and 3.8, from left to right. Sorted, they are 1, 1.2, 1.5, 2 and 3.8, the single-link merge heights of the worked example. Five distances were needed, not all 15. The script confirms the same on 30 random sets of 40 points. In the terms of the minimum spanning tree, the claim says that the tree of points on a line is the path through them in order.

What we have learned

The properties of a hierarchical clustering follow from how its linkage updates distances after a merge. Single, complete and average linkage return a value that is never below the smaller of the two old distances, so merge heights never decrease. Group-average similarity needs only one vector sum per cluster. Centroids compared by Euclidean distance subtract a term and can invert the tree, while centroids compared by dot product cannot. Single-link merges are the edges of a minimum spanning tree taken in order of weight. Priority queues bring the cost of HAC down to $O(N^2 \log N)$, and best-merge persistence brings single linkage down to $O(N^2)$.

Hierarchical clustering uses these results to read dendrograms, to explain chaining, and to decide when the method is affordable, and it compares the linkages with k-means on Reuters. The next unit begins with what a web crawler does.

The update rules, the proofs' numerical checks, the inversion, the minimum spanning tree and the three worked problems are recomputed by tools/experiments/clustering/hac_toy.py in the site repository, the script shared with hierarchical clustering.

References

  • Gower, J. C., and Ross, G. J. S. (1969). Minimum spanning trees and single linkage cluster analysis. Applied Statistics, 18(1), 54–64. record
  • Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1), 48–50. record
  • Lance, G. N., and Williams, W. T. (1967). A general theory of classificatory sorting strategies: 1. Hierarchical systems. The Computer Journal, 9(4), 373–380. record
  • Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapter 17. Cambridge University Press. record · 93 pages