Agglomerative clustering

Start with every point alone and repeatedly merge the closest pair; the linkage — single, complete, average, Ward — defines 'closest'.

17 min read1495 wordscore20 viewsupdated 2026-10-07

Definition

Agglomerative clustering is bottom-up hierarchical clustering: start with nn singleton clusters, and n−1n-1 times merge the two clusters that are closest under a chosen linkage — a rule that turns point-to-point distances into a cluster-to-cluster distance. The sequence of merges and their heights is a tree (a dendrogram); cutting it gives a flat clustering with any number of clusters.

At a glance

Task
Unsupervised clustering (hard assignments), plus a full merge hierarchy
Input → output
nn points (or any n×nn\times n dissimilarity matrix) → n−1n-1 merges with heights; a cut gives labels 1,…,k1,\dots,k
Learns
nothing parametric — the merge order and merge heights are the model
Training cost
O(n2)O(n^2) memory for the distance matrix; O(n3)O(n^3) naive, O(n2log⁡n)O(n^2\log n) with a priority queue, O(n2)O(n^2) for single (SLINK) and for Ward / complete / average with the nearest-neighbour chain
Prediction cost
no native predict for new points — assign them by a rule (nearest member, nearest centroid) or train a classifier on the labels
Hyperparameters
linkage, distance metric, number of clusters kk or a distance threshold, optional connectivity graph
Assumes
the chosen distance is meaningful (scale features!); the linkage encodes the cluster shape you expect — compact (Ward, complete) or elongated (single)

The problem

k-means asks you for kk before it starts, picks random seeds, needs a mean (so only works with Euclidean-style features) and assumes round clusters of similar size. You often don't know kk; you may only have a dissimilarity matrix (edit distances between strings, 1 − correlation between genes); and you may care about structure at several scales — species inside genera inside families.

Agglomerative clustering removes all three restrictions. It is deterministic, needs only pairwise dissimilarities, and computes the clusterings for every kk in one run. The price is quadratic memory, greedy merges that can never be undone, and one design decision that changes everything: how to measure the distance between two groups of points. That decision — the linkage — is what this article is about. How to read a dendrogram and where to cut it is covered in the sibling article Hierarchical clustering.

The idea

Imagine every point as an island. Repeatedly build a bridge between the two closest islands, fusing them into one. After n−1n-1 bridges everything is one landmass. If you record how long each bridge was, you can later demolish the longest ones and recover the natural archipelago. The only question is what "closest" means once an island holds many points: the nearest shores (single), the farthest shores (complete), the average shore-to-shore distance (average), or how much the fused island would spread out (Ward).

Vocabulary

Proximity matrix
the n×nn\times n table DD of current cluster-to-cluster distances; it shrinks by one row and column per merge
Linkage
the function d(A,B)d(A,B) between two sets of points, built from point distances d(x,y)d(x,y)
Merge height
hh, the linkage distance at which two clusters were fused; the yy-coordinate of the join in the dendrogram
Dendrogram
binary tree of the merges; leaves are points, each internal node is one merge drawn at its height
Cophenetic distance
for two points, the height of the merge that first puts them in the same cluster; it is an ultrametric (d(x,z)≤max⁡(d(x,y),d(y,z))d(x,z)\le\max(d(x,y),d(y,z)))
Lance–Williams update
a one-line recurrence that gives d(k,i∪j)d(k, i\cup j) from d(k,i)d(k,i), d(k,j)d(k,j) and d(i,j)d(i,j), so the matrix is updated without revisiting points
Chaining
single linkage's tendency to join two groups through a thin line of intermediate points
Inversion
a merge whose height is lower than an earlier one; impossible for single, complete, average and Ward, possible for centroid and median linkage
Connectivity constraint
a sparse graph (e.g. kk-nearest neighbours, pixel adjacency); only clusters joined by an edge may merge

The math

Let AA and BB be clusters with nAn_A and nBn_B points, centroids μA,μB\mu_A,\mu_B, and let d(x,y)d(x,y) be the point distance (Euclidean unless stated). The four standard linkages are:

dsingle(A,B)=min⁡a∈A, b∈Bd(a,b)dcomplete(A,B)=max⁡a∈A, b∈Bd(a,b)d_{\text{single}}(A,B)=\min_{a\in A,\,b\in B} d(a,b)\qquad d_{\text{complete}}(A,B)=\max_{a\in A,\,b\in B} d(a,b)
min⁡\min
the closest pair across the two clusters — clusters are close if any members are close
max⁡\max
the farthest pair — clusters are close only if all members are close; bounds the diameter of the merged cluster
daverage(A,B)=1nAnB∑a∈A∑b∈Bd(a,b)d_{\text{average}}(A,B)=\frac{1}{n_A n_B}\sum_{a\in A}\sum_{b\in B} d(a,b)
nAnBn_A n_B
number of cross pairs; average linkage (UPGMA) is the mean of all of them

Ward's linkage is different in kind: it is not a distance between members but the cost of the merge — how much the total within-cluster sum of squares grows. Define SSE(S)=∑x∈S∥x−μS∥2\text{SSE}(S)=\sum_{x\in S}\lVert x-\mu_S\rVert^2. Then

Δ(A,B)=SSE(A∪B)−SSE(A)−SSE(B)=nAnBnA+nB ∥μA−μB∥2\Delta(A,B)=\text{SSE}(A\cup B)-\text{SSE}(A)-\text{SSE}(B)=\frac{n_A n_B}{n_A+n_B}\,\lVert\mu_A-\mu_B\rVert^2
Δ(A,B)\Delta(A,B)
increase in total within-cluster squared error caused by merging A and B
μA,μB\mu_A,\mu_B
centroids (means) of the two clusters
nAnBnA+nB\tfrac{n_A n_B}{n_A+n_B}
half the harmonic mean of the sizes: merging two big clusters costs more than absorbing one point

Deriving Ward's merge cost

  1. 1Expand the SSE: SSE(S)=∑x∈S∥x∥2−nS∥μS∥2\text{SSE}(S)=\sum_{x\in S}\lVert x\rVert^2-n_S\lVert\mu_S\rVert^2. The ∑∥x∥2\sum\lVert x\rVert^2 terms of AA, BB and A∪BA\cup B cancel in Δ\Delta, leaving Δ=nA∥μA∥2+nB∥μB∥2−(nA+nB)∥μAB∥2\Delta=n_A\lVert\mu_A\rVert^2+n_B\lVert\mu_B\rVert^2-(n_A+n_B)\lVert\mu_{AB}\rVert^2.
  2. 2The merged centroid is the size-weighted mean μAB=nAμA+nBμBnA+nB\mu_{AB}=\dfrac{n_A\mu_A+n_B\mu_B}{n_A+n_B}.
  3. 3Substitute: (nA+nB)∥μAB∥2=nA2∥μA∥2+2nAnB μA⊤μB+nB2∥μB∥2nA+nB(n_A+n_B)\lVert\mu_{AB}\rVert^2=\dfrac{n_A^2\lVert\mu_A\rVert^2+2n_An_B\,\mu_A^\top\mu_B+n_B^2\lVert\mu_B\rVert^2}{n_A+n_B}.
  4. 4Subtract and collect over the common denominator: Δ=nAnB(∥μA∥2−2μA⊤μB+∥μB∥2)nA+nB=nAnBnA+nB∥μA−μB∥2\Delta=\dfrac{n_An_B\left(\lVert\mu_A\rVert^2-2\mu_A^\top\mu_B+\lVert\mu_B\rVert^2\right)}{n_A+n_B}=\dfrac{n_An_B}{n_A+n_B}\lVert\mu_A-\mu_B\rVert^2. ■\blacksquare
  5. 5So Ward greedily makes the merge that least increases the k-means objective. scikit-learn and SciPy report the height h=2Δh=\sqrt{2\Delta}, which equals the plain Euclidean distance when two singletons merge.

Because each merge adds its Δ\Delta, the Ward costs of all n−1n-1 merges sum to the total SSE of the data around its grand mean, and the SSE of the kk-cluster cut is the sum of the first n−kn-k costs. That is why Ward is the hierarchical cousin of k-means.

One update rule for all linkages

Recomputing a linkage from the raw points after every merge would cost O(nAnB)O(n_A n_B) per pair. Lance and Williams (1967) showed that all the linkages above satisfy a single recurrence, so after merging ii and jj the new row of the proximity matrix comes straight from the old one:

d(k, i∪j)=αi d(k,i)+αj d(k,j)+β d(i,j)+γ ∣d(k,i)−d(k,j)∣d(k,\,i\cup j)=\alpha_i\,d(k,i)+\alpha_j\,d(k,j)+\beta\,d(i,j)+\gamma\,\lvert d(k,i)-d(k,j)\rvert
kk
any other cluster still active
αi,αj,β,γ\alpha_i,\alpha_j,\beta,\gamma
coefficients that define the linkage (table below); they may depend on the sizes ni,nj,nkn_i,n_j,n_k
dd
for Ward, the recurrence runs on squared distances d2d^2
Linkaged(k,i)d(k,j)d(i,j)|d(k,i)−d(k,j)|Clusters tend to be
Single½½0−½chain-like, any shape
Complete½½0+½compact, bounded diameter
Averagenini+nj\frac{n_i}{n_i+n_j}njni+nj\frac{n_j}{n_i+n_j}00in between; any metric
Ward (on d2d^2)ni+nkni+nj+nk\frac{n_i+n_k}{n_i+n_j+n_k}nj+nkni+nj+nk\frac{n_j+n_k}{n_i+n_j+n_k}−nkni+nj+nk\frac{-n_k}{n_i+n_j+n_k}0compact, similar sizes
Lance–Williams coefficients αi,αj,β,γ\alpha_i,\alpha_j,\beta,\gamma — each column is the coefficient of the term in its header. For single linkage, 12(a+b)−12∣a−b∣=min⁡(a,b)\tfrac12(a+b)-\tfrac12\lvert a-b\rvert=\min(a,b); for complete, the ++ sign gives max⁡(a,b)\max(a,b).

Monotonicity. For these four linkages, merging the closest pair i,ji,j can never bring the new cluster closer to any other cluster than the closer of its parts was (d(k,i∪j)≥min⁡(d(k,i),d(k,j))d(k,i\cup j)\ge\min(d(k,i),d(k,j)) whenever d(i,j)d(i,j) was the minimum), so merge heights never decrease and the dendrogram has no inversions. Centroid linkage (∥μA−μB∥\lVert\mu_A-\mu_B\rVert, with α=nini+nj\alpha=\tfrac{n_i}{n_i+n_j}, β=−αiαj\beta=-\alpha_i\alpha_j) violates this and can produce crossing dendrogram branches — one reason it is rarely used.

What each hyperparameter does, mathematically

linkage
changes the set function d(A,B)d(A,B): min, max, mean, or Δ\Delta — and therefore the merge order. Same data, different trees.
metric
changes the point distances d(x,y)d(x,y) every linkage is built from (Euclidean, Manhattan, cosine, precomputed). Ward requires Euclidean, because Δ\Delta is a squared-error identity.
n_clusters = k
keeps the first n−kn-k merges. Equivalent to cutting the tree between heights hn−kh_{n-k} and hn−k+1h_{n-k+1}.
distance_threshold = τ
keeps every merge with h<τh<\tau; kk then becomes an output. Use one or the other.
connectivity
sets d(A,B)=∞d(A,B)=\infty unless some edge of the graph joins AA and BB; enforces spatial contiguity and makes the search sparse and fast.

Worked example: nine points, four linkages

Two tight groups (A–C on the left, F–H on the right), a two-point "bridge" (D, E) between them, and one outlier I above the bridge. The question each linkage answers differently: does the bridge belong to the left group, to the outlier, or to nobody?

Pointx₁x₂Role
A1.01.0left group
B1.52.0left group
C2.01.2left group
D3.41.6bridge
E4.81.8bridge
F6.21.3right group
G6.62.4right group
H7.41.6right group
I4.24.2outlier
The nine points.
dABCDEFGH
B1.12
C1.020.94
D2.471.941.46
E3.883.312.861.41
F5.214.754.202.821.49
G5.775.124.753.301.901.17
H6.435.915.414.002.611.241.13
I4.533.483.722.722.473.523.004.12
Euclidean distances (lower triangle, 2 decimals). The smallest, d(B, C) = 0.94, is the first merge for every linkage.

By hand: the first five merges (all linkages agree on the order)

  1. 1Merge 1. The smallest entry is d(B,C)=0.94d(B,C)=0.94 → cluster BC at height 0.94. For Ward the cost is Δ=1⋅12(0.943)2=0.445\Delta=\tfrac{1\cdot1}{2}(0.943)^2=0.445, height 2Δ=0.94\sqrt{2\Delta}=0.94.
  2. 2Update row BC with Lance–Williams, e.g. for A: single min⁡(1.12,1.02)=1.02\min(1.12,1.02)=1.02; complete max⁡(1.12,1.02)=1.12\max(1.12,1.02)=1.12; average 12(1.12+1.02)=1.07\tfrac12(1.12+1.02)=1.07; Ward (2⋅1.1182+2⋅1.0202−0.9432)/3=1.11\sqrt{(2\cdot1.118^2+2\cdot1.020^2-0.943^2)/3}=1.11.
  3. 3Merge 2. The next-smallest entry is A–BC under every linkage (1.02 / 1.12 / 1.07 / 1.11), each below d(G,H)=1.13d(G,H)=1.13 → cluster ABC. Under complete linkage it wins by just 0.01.
  4. 4Merges 3 and 4. d(G,H)=1.13d(G,H)=1.13 → GH; then F joins: single min⁡(1.17,1.24)=1.17\min(1.17,1.24)=1.17, complete max⁡=1.24\max=1.24, average 1.20, Ward 1.23 → FGH.
  5. 5Merge 5. d(D,E)=1.41d(D,E)=1.41 → DE. We now have four clusters: ABC, DE, FGH and I.

Up to here the linkages differ only in heights. The sixth merge is where they disagree. Here are all six cluster-to-cluster distances at that moment:

PairSingle (min)Complete (max)Average (mean)Ward √(2Δ) (Δ)
ABC – DE1.46 (C–D)3.88 (A–E)2.654.05 (8.22)
DE – FGH1.49 (E–F)4.00 (D–H)2.684.08 (8.33)
DE – I2.47 (E–I)2.72 (D–I)2.602.89 (4.17)
FGH – I3.00 (G–I)4.12 (H–I)3.554.30 (9.25)
ABC – I3.48 (B–I)4.53 (A–I)3.914.76 (11.35)
ABC – FGH4.20 (C–F)6.43 (A–H)5.289.09 (41.28)
Linkage distances between the four clusters after merge 5. Bold = the minimum, i.e. the sixth merge. Ward's column is the height 2Δ\sqrt{2\Delta}, with Δ\Delta (the SSE increase) in brackets.

By hand: the last three merges

  1. 1Single linkage merges ABC + DE at 1.46 (the C–D gap), then ABCDE + FGH at 1.49 (the E–F gap): the bridge has chained both groups together. The outlier joins last at 2.47.
  2. 2Complete linkage refuses that chain: ABC–DE is judged by its farthest pair A–E = 3.88. Instead DE + I merges at 2.72; then DEI + FGH at 4.12; finally ABC at 6.43 (A–H, the diameter of the whole set).
  3. 3Average (2.60, 2.97, 4.18) and Ward (2.89, 4.70, 8.01) make the same merges as complete. Ward's three costs Δ=4.17, 11.02, 32.07\Delta=4.17,\,11.02,\,32.07 plus the first five (0.445+0.615+0.640+0.753+1.000=3.45)(0.445+0.615+0.640+0.753+1.000=3.45) add up to 50.7250.72 — exactly the total SSE of the nine points around their mean.
  4. 4Cut at k=3k=3 (keep the first 6 merges). Single: {A, B, C, D, E} · {F, G, H} · {I}. Complete, average, Ward: {A, B, C} · {D, E, I} · {F, G, H}. Ward's 3-cluster SSE is 3.45+4.17=7.633.45+4.17=7.63.
  5. 5A new point x=(5.5,,2.0)x=(5.5,,2.0). There is no predict, so choose a rule. Nearest member: E at 0.73 → Ward cluster DEI. Nearest centroid: FGH's centroid (6.73, 1.77) is 1.26 away versus 1.47 for DEI's (4.13, 2.53) → FGH. Under single linkage the nearest-member rule puts it in ABCDE.
MergeSingleCompleteAverageWard
1B+C 0.94B+C 0.94B+C 0.94B+C 0.94
2A+BC 1.02A+BC 1.12A+BC 1.07A+BC 1.11
3G+H 1.13G+H 1.13G+H 1.13G+H 1.13
4F+GH 1.17F+GH 1.24F+GH 1.20F+GH 1.23
5D+E 1.41D+E 1.41D+E 1.41D+E 1.41
6ABC+DE 1.46DE+I 2.72DE+I 2.60DE+I 2.89
7ABCDE+FGH 1.49DEI+FGH 4.12DEI+FGH 2.97DEI+FGH 4.70
8+I 2.47+ABC 6.43+ABC 4.18+ABC 8.01
All eight merge heights. Rows 6–8 are where the linkages part ways; the cophenetic correlation (how well tree heights reproduce the original distances) is 0.28 for single and 0.73–0.74 for the others.
▸ agglomerative · single linkagestep 1/19
linkage
12345671234ABCDEFGHIsingle: closest pairclusters: 9dendrogram · merge height0.01.22.5ABCDEFGHI
merges 0/8last height —
  1. 1C ← { {x₁}, …, {xₙ} }
  2. 2D ← all pairwise distances
  3. 3while |C| > 1:
  4. 4 (a, b) ← argmin D[a, b]
  5. 5 merge a, b at h = D[a, b]; update D
  6. 6cut the tree → k clusters

Start: each of the 9 points is its own cluster. Linkage = single (closest pair).

fig.The nine points merging, with the dendrogram growing below. Switch linkage at any step. On a search step the white segment shows what the linkage measures: the closest pair (single), the farthest pair (complete, dashed), every cross pair (average) or the gap between centroids (Ward, ✕). Single linkage chains ABC + DE at 1.46 and ABCDE + FGH at 1.49 and leaves the outlier I for last (2.47); complete, average and Ward instead merge DE + I at 2.72 / 2.60 / 2.89. The last step cuts the tree at k = 3.

The algorithm, step by step

Agglomerate(X, linkage)

  1. 1Initialise. Make nn singleton clusters. Compute the n×nn\times n distance matrix DD (squared for Ward). O(n2d)O(n^2 d) time, O(n2)O(n^2) memory.
  2. 2Find the closest pair. (a,b)=arg⁡min⁡i≠jDij(a,b)=\arg\min_{i\ne j}D_{ij} over active clusters.
  3. 3Merge. Record (a,b,h=Dab,  na+nb)(a,b,h=D_{ab},\;n_a+n_b) — one row of the SciPy linkage matrix ZZ.
  4. 4Update. Overwrite row aa with d(k,a∪b)d(k,a\cup b) for every active kk via Lance–Williams; deactivate row bb. O(n)O(n).
  5. 5Repeat steps 2–4 until one cluster remains (n−1n-1 merges).
  6. 6Cut. For a flat clustering, keep the first n−kn-k merges (or all with h<τh<\tau) and label the connected groups.

Complexity

Naive
a full scan for the minimum each round: nn rounds × O(n2)O(n^2) = O(n3)O(n^3) time
Priority queue
a heap of each row's nearest neighbour: O(n2log⁡n)O(n^2\log n) — the generic method for any Lance–Williams linkage
NN-chain
follow nearest neighbours until two clusters are mutual nearest neighbours, merge them: O(n2)O(n^2) for Ward, complete and average (any reducible linkage). SciPy and scikit-learn use it.
SLINK / MST
single linkage in O(n2)O(n^2) time and O(n)O(n) memory; with a connectivity graph or a k-NN graph it becomes near-linear
Memory wall
the condensed float64 distance matrix needs 8⋅n(n−1)/28\cdot n(n-1)/2 bytes: 40 GB at n=100,000n=100{,}000. Beyond ~10410^4–10510^5 points, use connectivity constraints, BIRCH or a sample.

Choosing a linkage

The worked example is not an accident: each linkage has a built-in idea of what a cluster looks like. Below, adjusted Rand index (1 = recovers the true groups exactly, 0 = chance) for scikit-learn's AgglomerativeClustering with the true kk on 300-point synthetic sets.

DatasetSingleCompleteAverageWard
Two moons, noise 0.051.000.300.430.24
Two moons, noise 0.120.000.380.430.53
3 equal blobs0.570.980.980.98
3 blobs, unequal spread (σ = 0.5, 1.5, 1.0)0.570.740.570.93
ARI by linkage. Single wins only on clean, well-separated non-convex shapes and collapses with a little noise; Ward is the best default for compact clusters, especially of unequal spread.

Practical tuning

Default
Ward on standardized features. It optimizes the same objective as k-means, but needs no seeds and gives every kk at once.
Non-Euclidean data
average linkage with metric="precomputed" (or cosine, Manhattan). Ward is undefined there.
Elongated / manifold clusters
single linkage — but only after removing noise, or use HDBSCAN, which is a robust single linkage.
Choosing k
look for a large jump between consecutive merge heights (here Ward: 1.41 → 2.89 → 4.70 → 8.01), then confirm with silhouette. On the example, silhouette at k = 3 is 0.45 for Ward and 0.40 for single.
Images, maps, time series
pass connectivity= (a grid or k-NN graph): clusters stay contiguous and run time drops dramatically.
Compare trees
cophenetic correlation between the tree's cophenetic distances and the original distances — higher means the tree is a more faithful summary (0.28 vs 0.73 here).

In code

python
1import numpy as np
2
3def lance_williams(method, ni, nj, nk):
4 """Coefficients (alpha_i, alpha_j, beta, gamma) for d(k, i∪j)."""
5 if method == "single": return 0.5, 0.5, 0.0, -0.5
6 if method == "complete": return 0.5, 0.5, 0.0, 0.5
7 if method == "average": return ni / (ni + nj), nj / (ni + nj), 0.0, 0.0
8 if method == "ward": # works on squared distances
9 t = ni + nj + nk
10 return (ni + nk) / t, (nj + nk) / t, -nk / t, 0.0
11 raise ValueError(method)
12
13def agglomerative(X, method="ward"):
14 n = len(X)
15 D = np.sqrt(((X[:, None] - X[None]) ** 2).sum(-1))
16 if method == "ward":
17 D = D ** 2
18 np.fill_diagonal(D, np.inf)
19 size = {i: 1 for i in range(n)} # active cluster id -> size
20 row = {i: i for i in range(n)} # active cluster id -> row of D
21 merges = []
22 for new in range(n, 2 * n - 1): # exactly n - 1 merges
23 ids = list(size)
24 R = [row[c] for c in ids]
25 sub = D[np.ix_(R, R)]
26 a, b = np.unravel_index(np.argmin(sub), sub.shape)
27 i, j = ids[a], ids[b]
28 ri, rj = row[i], row[j]
29 h = D[ri, rj]
30 for k in ids: # update row ri to hold d(k, i∪j)
31 if k in (i, j):
32 continue
33 rk = row[k]
34 ai, aj, be, ga = lance_williams(method, size[i], size[j], size[k])
35 D[ri, rk] = D[rk, ri] = (ai * D[ri, rk] + aj * D[rj, rk]
36 + be * D[ri, rj] + ga * abs(D[ri, rk] - D[rj, rk]))
37 D[rj, :] = D[:, rj] = np.inf # retire row rj
38 merges.append((i, j, np.sqrt(h) if method == "ward" else h))
39 size[new] = size.pop(i) + size.pop(j)
40 row[new] = ri
41 return merges
42
43def cut(merges, n, k):
44 """Replay the first n - k merges; return the k groups of point indices."""
45 groups = {i: [i] for i in range(n)}
46 for t, (i, j, _) in enumerate(merges[: n - k]):
47 groups[n + t] = groups.pop(i) + groups.pop(j)
48 return sorted(sorted(g) for g in groups.values())
49
50X = np.array([[1, 1], [1.5, 2], [2, 1.2], [3.4, 1.6], [4.8, 1.8],
51 [6.2, 1.3], [6.6, 2.4], [7.4, 1.6], [4.2, 4.2]])
52names = "ABCDEFGHI"
53for method in ["single", "complete", "average", "ward"]:
54 merges = agglomerative(X, method)
55 heights = " ".join(f"{h:.2f}" for _, _, h in merges)
56 groups = ["".join(names[i] for i in g) for g in cut(merges, len(X), 3)]
57 print(f"{method:8s} heights: {heights} k=3: {groups}")
From scratch: generic Lance–Williams agglomeration (O(n³), for learning). Prints the merge heights of the worked example and the k = 3 cut.
text
1single heights: 0.94 1.02 1.13 1.17 1.41 1.46 1.49 2.47 k=3: ['ABCDE', 'FGH', 'I']
2complete heights: 0.94 1.12 1.13 1.24 1.41 2.72 4.12 6.43 k=3: ['ABC', 'DEI', 'FGH']
3average heights: 0.94 1.07 1.13 1.20 1.41 2.60 2.97 4.18 k=3: ['ABC', 'DEI', 'FGH']
4ward heights: 0.94 1.11 1.13 1.23 1.41 2.89 4.70 8.01 k=3: ['ABC', 'DEI', 'FGH']
Output
python
1import numpy as np
2from sklearn.cluster import AgglomerativeClustering
3from scipy.cluster.hierarchy import linkage, cophenet
4from scipy.spatial.distance import pdist
5
6X = np.array([[1, 1], [1.5, 2], [2, 1.2], [3.4, 1.6], [4.8, 1.8],
7 [6.2, 1.3], [6.6, 2.4], [7.4, 1.6], [4.2, 4.2]])
8names = np.array(list("ABCDEFGHI"))
9
10for link in ["single", "complete", "average", "ward"]:
11 model = AgglomerativeClustering(n_clusters=3, linkage=link,
12 compute_distances=True).fit(X)
13 groups = [''.join(names[model.labels_ == c]) for c in np.unique(model.labels_)]
14 coph, _ = cophenet(linkage(X, link), pdist(X))
15 print(f"{link:8s} clusters={sorted(groups)} heights={np.round(model.distances_, 2)}"
16 f" cophenetic r={coph:.2f}")
17
18# A new point: agglomerative clustering has no predict(); use a rule.
19x_new = np.array([5.5, 2.0])
20ward = AgglomerativeClustering(n_clusters=3, linkage="ward").fit(X)
21nearest_member = ward.labels_[np.argmin(np.linalg.norm(X - x_new, axis=1))]
22cents = np.array([X[ward.labels_ == c].mean(0) for c in range(3)])
23nearest_centroid = np.argmin(np.linalg.norm(cents - x_new, axis=1))
24print("1-NN rule ->", ''.join(names[ward.labels_ == nearest_member]))
25print("centroid ->", ''.join(names[ward.labels_ == nearest_centroid]))
scikit-learn on the same points, plus the two rules for placing a new point.
text
1single clusters=['ABCDE', 'FGH', 'I'] heights=[0.94 1.02 1.13 1.17 1.41 1.46 1.49 2.47] cophenetic r=0.28
2complete clusters=['ABC', 'DEI', 'FGH'] heights=[0.94 1.12 1.13 1.24 1.41 2.72 4.12 6.43] cophenetic r=0.73
3average clusters=['ABC', 'DEI', 'FGH'] heights=[0.94 1.07 1.13 1.2 1.41 2.6 2.97 4.18] cophenetic r=0.74
4ward clusters=['ABC', 'DEI', 'FGH'] heights=[0.94 1.11 1.13 1.23 1.41 2.89 4.7 8.01] cophenetic r=0.73
51-NN rule -> DEI
6centroid -> FGH
Output

Use when

  • +You do not know kk, or want clusterings at several scales from one run.
  • +You only have a dissimilarity matrix (strings, sequences, correlations) — use average or complete linkage.
  • +You need a deterministic, explainable result: the dendrogram shows exactly why each group formed.
  • +Clusters must be spatially contiguous (image segments, regions) — add a connectivity graph.

Avoid when

  • −nn is beyond ~10410^4–10510^5 without constraints: the O(n2)O(n^2) distance matrix does not fit in memory.
  • −Data are noisy and you planned to use single linkage — chaining will merge clusters through noise.
  • −You need to cluster new points online: there is no predict, and merges cannot be revised.
  • −Clusters differ in density rather than separation — consider DBSCAN or HDBSCAN.

Where it's used

Phylogenetics

UPGMA (average linkage) on genetic distances builds species trees; the ultrametric heights are read as divergence times under a molecular-clock assumption.

Gene-expression heatmaps

Rows (genes) and columns (samples) are reordered by average linkage on 1 − correlation, so co-expressed genes appear as blocks next to their dendrogram.

Image segmentation

Ward with a pixel-grid connectivity merges neighbouring pixels into superpixels and regions without crossing object boundaries.

Document & customer taxonomies

Cosine distance with average linkage turns embeddings into a browsable topic or segment hierarchy that analysts can cut at the level they need.

Check yourself

Cluster {P, Q} is merged. For another cluster K, d(K, P) = 3 and d(K, Q) = 5. What is d(K, P∪Q) under single, complete and average linkage?

Check yourself

Ward's linkage merges two single points that are 2 units apart. By how much does the total within-cluster SSE increase?

Check yourself

In the worked example, why does single linkage cut {A, B, C, D, E} | {F, G, H} | {I} at k = 3 while Ward gives {A, B, C} | {D, E, I} | {F, G, H}?

Check yourself

Roughly how much memory does the condensed float64 distance matrix need for n = 100,000 points?

Remember

  • ✓Start from nn singletons and make n−1n-1 greedy merges of the closest pair; the merge heights form a dendrogram you can cut at any kk.
  • ✓The linkage defines 'closest': single = nearest pair (MST, chains), complete = farthest pair (compact), average = mean pair (UPGMA), Ward = smallest SSE increase.
  • ✓Ward's cost is Δ=nAnBnA+nB∥μA−μB∥2\Delta=\tfrac{n_An_B}{n_A+n_B}\lVert\mu_A-\mu_B\rVert^2; the costs of all merges sum to the total SSE, so Ward is greedy k-means.
  • ✓One Lance–Williams recurrence updates the proximity matrix for every standard linkage in O(n)O(n) per merge.
  • ✓Memory is O(n2)O(n^2) and merges are never undone; scale features, prefer Ward or average, avoid single on noisy data, and add connectivity for large or spatial data.
← back to ML Algorithms roadmap