Definition
Agglomerative clustering is bottom-up hierarchical clustering: start with singleton clusters, and 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
- points (or any dissimilarity matrix) → merges with heights; a cut gives labels
- Learns
- nothing parametric — the merge order and merge heights are the model
- Training cost
- memory for the distance matrix; naive, with a priority queue, for single (SLINK) and for Ward / complete / average with the nearest-neighbour chain
- Prediction cost
- no native
predictfor 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 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 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 ; 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 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 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 table of current cluster-to-cluster distances; it shrinks by one row and column per merge
- Linkage
- the function between two sets of points, built from point distances
- Merge height
- , the linkage distance at which two clusters were fused; the -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 ()
- Lance–Williams update
- a one-line recurrence that gives from , and , 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. -nearest neighbours, pixel adjacency); only clusters joined by an edge may merge
The math
Let and be clusters with and points, centroids , and let be the point distance (Euclidean unless stated). The four standard linkages are:
- the closest pair across the two clusters — clusters are close if any members are close
- the farthest pair — clusters are close only if all members are close; bounds the diameter of the merged cluster
- 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 . Then
- increase in total within-cluster squared error caused by merging A and B
- centroids (means) of the two clusters
- half the harmonic mean of the sizes: merging two big clusters costs more than absorbing one point
Deriving Ward's merge cost
- 1Expand the SSE: . The terms of , and cancel in , leaving .
- 2The merged centroid is the size-weighted mean .
- 3Substitute: .
- 4Subtract and collect over the common denominator: .
- 5So Ward greedily makes the merge that least increases the k-means objective. scikit-learn and SciPy report the height , which equals the plain Euclidean distance when two singletons merge.
Because each merge adds its , the Ward costs of all merges sum to the total SSE of the data around its grand mean, and the SSE of the -cluster cut is the sum of the first 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 per pair. Lance and Williams (1967) showed that all the linkages above satisfy a single recurrence, so after merging and the new row of the proximity matrix comes straight from the old one:
- any other cluster still active
- coefficients that define the linkage (table below); they may depend on the sizes
- for Ward, the recurrence runs on squared distances
| Linkage | d(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 |
| Average | 0 | 0 | in between; any metric | ||
| Ward (on ) | 0 | compact, similar sizes |
Monotonicity. For these four linkages, merging the closest pair can never bring the new cluster closer to any other cluster than the closer of its parts was ( whenever was the minimum), so merge heights never decrease and the dendrogram has no inversions. Centroid linkage (, with , ) violates this and can produce crossing dendrogram branches — one reason it is rarely used.
What each hyperparameter does, mathematically
- linkage
- changes the set function : min, max, mean, or — and therefore the merge order. Same data, different trees.
- metric
- changes the point distances every linkage is built from (Euclidean, Manhattan, cosine, precomputed). Ward requires Euclidean, because is a squared-error identity.
- n_clusters = k
- keeps the first merges. Equivalent to cutting the tree between heights and .
- distance_threshold = τ
- keeps every merge with ; then becomes an output. Use one or the other.
- connectivity
- sets unless some edge of the graph joins and ; 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?
| Point | x₁ | x₂ | Role |
|---|---|---|---|
| A | 1.0 | 1.0 | left group |
| B | 1.5 | 2.0 | left group |
| C | 2.0 | 1.2 | left group |
| D | 3.4 | 1.6 | bridge |
| E | 4.8 | 1.8 | bridge |
| F | 6.2 | 1.3 | right group |
| G | 6.6 | 2.4 | right group |
| H | 7.4 | 1.6 | right group |
| I | 4.2 | 4.2 | outlier |
| d | A | B | C | D | E | F | G | H |
|---|---|---|---|---|---|---|---|---|
| B | 1.12 | |||||||
| C | 1.02 | 0.94 | ||||||
| D | 2.47 | 1.94 | 1.46 | |||||
| E | 3.88 | 3.31 | 2.86 | 1.41 | ||||
| F | 5.21 | 4.75 | 4.20 | 2.82 | 1.49 | |||
| G | 5.77 | 5.12 | 4.75 | 3.30 | 1.90 | 1.17 | ||
| H | 6.43 | 5.91 | 5.41 | 4.00 | 2.61 | 1.24 | 1.13 | |
| I | 4.53 | 3.48 | 3.72 | 2.72 | 2.47 | 3.52 | 3.00 | 4.12 |
By hand: the first five merges (all linkages agree on the order)
- 1Merge 1. The smallest entry is → cluster BC at height 0.94. For Ward the cost is , height .
- 2Update row BC with Lance–Williams, e.g. for A: single ; complete ; average ; Ward .
- 3Merge 2. The next-smallest entry is A–BC under every linkage (1.02 / 1.12 / 1.07 / 1.11), each below → cluster ABC. Under complete linkage it wins by just 0.01.
- 4Merges 3 and 4. → GH; then F joins: single , complete , average 1.20, Ward 1.23 → FGH.
- 5Merge 5. → 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:
| Pair | Single (min) | Complete (max) | Average (mean) | Ward √(2Δ) (Δ) |
|---|---|---|---|---|
| ABC – DE | 1.46 (C–D) | 3.88 (A–E) | 2.65 | 4.05 (8.22) |
| DE – FGH | 1.49 (E–F) | 4.00 (D–H) | 2.68 | 4.08 (8.33) |
| DE – I | 2.47 (E–I) | 2.72 (D–I) | 2.60 | 2.89 (4.17) |
| FGH – I | 3.00 (G–I) | 4.12 (H–I) | 3.55 | 4.30 (9.25) |
| ABC – I | 3.48 (B–I) | 4.53 (A–I) | 3.91 | 4.76 (11.35) |
| ABC – FGH | 4.20 (C–F) | 6.43 (A–H) | 5.28 | 9.09 (41.28) |
By hand: the last three merges
- 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.
- 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).
- 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 plus the first five add up to — exactly the total SSE of the nine points around their mean.
- 4Cut at (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 .
- 5A new point . 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.
| Merge | Single | Complete | Average | Ward |
|---|---|---|---|---|
| 1 | B+C 0.94 | B+C 0.94 | B+C 0.94 | B+C 0.94 |
| 2 | A+BC 1.02 | A+BC 1.12 | A+BC 1.07 | A+BC 1.11 |
| 3 | G+H 1.13 | G+H 1.13 | G+H 1.13 | G+H 1.13 |
| 4 | F+GH 1.17 | F+GH 1.24 | F+GH 1.20 | F+GH 1.23 |
| 5 | D+E 1.41 | D+E 1.41 | D+E 1.41 | D+E 1.41 |
| 6 | ABC+DE 1.46 | DE+I 2.72 | DE+I 2.60 | DE+I 2.89 |
| 7 | ABCDE+FGH 1.49 | DEI+FGH 4.12 | DEI+FGH 2.97 | DEI+FGH 4.70 |
| 8 | +I 2.47 | +ABC 6.43 | +ABC 4.18 | +ABC 8.01 |
- 1C ← { {x₁}, …, {xₙ} }
- 2D ← all pairwise distances
- 3while |C| > 1:
- 4 (a, b) ← argmin D[a, b]
- 5 merge a, b at h = D[a, b]; update D
- 6cut the tree → k clusters
Start: each of the 9 points is its own cluster. Linkage = single (closest pair).
The algorithm, step by step
Agglomerate(X, linkage)
- 1Initialise. Make singleton clusters. Compute the distance matrix (squared for Ward). time, memory.
- 2Find the closest pair. over active clusters.
- 3Merge. Record — one row of the SciPy linkage matrix .
- 4Update. Overwrite row with for every active via Lance–Williams; deactivate row . .
- 5Repeat steps 2–4 until one cluster remains ( merges).
- 6Cut. For a flat clustering, keep the first merges (or all with ) and label the connected groups.
Complexity
- Naive
- a full scan for the minimum each round: rounds × = time
- Priority queue
- a heap of each row's nearest neighbour: — the generic method for any Lance–Williams linkage
- NN-chain
- follow nearest neighbours until two clusters are mutual nearest neighbours, merge them: for Ward, complete and average (any reducible linkage). SciPy and scikit-learn use it.
- SLINK / MST
- single linkage in time and memory; with a connectivity graph or a k-NN graph it becomes near-linear
- Memory wall
- the condensed float64 distance matrix needs bytes: 40 GB at . Beyond ~– 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 on 300-point synthetic sets.
| Dataset | Single | Complete | Average | Ward |
|---|---|---|---|---|
| Two moons, noise 0.05 | 1.00 | 0.30 | 0.43 | 0.24 |
| Two moons, noise 0.12 | 0.00 | 0.38 | 0.43 | 0.53 |
| 3 equal blobs | 0.57 | 0.98 | 0.98 | 0.98 |
| 3 blobs, unequal spread (σ = 0.5, 1.5, 1.0) | 0.57 | 0.74 | 0.57 | 0.93 |
Practical tuning
- Default
- Ward on standardized features. It optimizes the same objective as k-means, but needs no seeds and gives every 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
1import numpy as np23def 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.56 if method == "complete": return 0.5, 0.5, 0.0, 0.57 if method == "average": return ni / (ni + nj), nj / (ni + nj), 0.0, 0.08 if method == "ward": # works on squared distances9 t = ni + nj + nk10 return (ni + nk) / t, (nj + nk) / t, -nk / t, 0.011 raise ValueError(method)1213def 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 ** 218 np.fill_diagonal(D, np.inf)19 size = {i: 1 for i in range(n)} # active cluster id -> size20 row = {i: i for i in range(n)} # active cluster id -> row of D21 merges = []22 for new in range(n, 2 * n - 1): # exactly n - 1 merges23 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 continue33 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 rj38 merges.append((i, j, np.sqrt(h) if method == "ward" else h))39 size[new] = size.pop(i) + size.pop(j)40 row[new] = ri41 return merges4243def 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())4950X = 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}")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']1import numpy as np2from sklearn.cluster import AgglomerativeClustering3from scipy.cluster.hierarchy import linkage, cophenet4from scipy.spatial.distance import pdist56X = 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"))910for 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}")1718# 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]))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.282complete clusters=['ABC', 'DEI', 'FGH'] heights=[0.94 1.12 1.13 1.24 1.41 2.72 4.12 6.43] cophenetic r=0.733average clusters=['ABC', 'DEI', 'FGH'] heights=[0.94 1.07 1.13 1.2 1.41 2.6 2.97 4.18] cophenetic r=0.744ward clusters=['ABC', 'DEI', 'FGH'] heights=[0.94 1.11 1.13 1.23 1.41 2.89 4.7 8.01] cophenetic r=0.7351-NN rule -> DEI6centroid -> FGHUse when
- +You do not know , 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
- − is beyond ~– without constraints: the 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 singletons and make greedy merges of the closest pair; the merge heights form a dendrogram you can cut at any .
- ✓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 ; 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 per merge.
- ✓Memory is and merges are never undone; scale features, prefer Ward or average, avoid single on noisy data, and add connectivity for large or spatial data.