Hierarchical clustering

Build a tree of nested clusters (a dendrogram); cutting it at any height gives a flat clustering.

17 min read1753 wordscore8 viewsupdated 2026-10-07

Definition

Hierarchical clustering builds a nested family of clusterings of the same data — from nn singletons up to one cluster containing everything — and records it as a tree called a dendrogram. Each internal node is a merge (or split) drawn at the height where it happened; cutting the tree with a horizontal line at height hh gives an ordinary flat clustering, and every kk from 1 to nn is available from the one tree.

At a glance

Task
Unsupervised clustering — and a summary of the data's structure at every scale
Input → output
nn points (or just an n×nn\times n dissimilarity matrix) → a binary tree with n−1n-1 merge heights; a cut turns it into labels
Learns
the order in which groups join and the height h1≤h2≤⋯≤hn−1h_1\le h_2\le\dots\le h_{n-1} of each join
Training
agglomerative: O(n2)O(n^2) to O(n3)O(n^3) time and O(n2)O(n^2) memory for the distance matrix; divisive: exponential if exact, so heuristics such as DIANA are used
Prediction
none built in — the tree describes the training points; a new point is assigned to the nearest cluster after cutting
Hyperparameters
dissimilarity metric, linkage (single / complete / average / Ward), and where to cut (height or k)
Assumes
that a meaningful nested structure exists, and that the chosen metric on your (scaled) features expresses similarity

The problem

A flat method such as k-means answers one question — split the data into exactly kk groups — and asks you to pick kk before you have looked. Change your mind and you re-run it, and the 4-cluster answer need not refine the 3-cluster one: a point can jump between groups as kk changes. Many real structures are not flat at all. Species nest into genera and families, products into sub-categories, documents into topics and sub-topics, genes into co-expressed modules within pathways.

We want a method that (1) does not need kk in advance, (2) produces clusterings at all granularities that are consistent with each other — the 4-cluster answer is the 3-cluster answer with one group split — and (3) gives a picture of how strongly groups are separated, so that the choice of kk can be made by looking. Hierarchical clustering delivers all three, and it needs only pairwise dissimilarities, so it works for strings, graphs or any objects you can compare.

The idea

Start with every point as its own cluster. Repeatedly merge the two closest clusters, writing down how far apart they were. After n−1n-1 merges everything is one cluster, and the log of merges is the tree. This bottom-up version is agglomerative clustering and is what almost everyone uses; the merge loop and the choice of linkage are covered in depth in the agglomerative clustering article. The top-down alternative, divisive clustering, starts with one cluster and repeatedly splits the least coherent one.

Either way, draw each merge as a ⊓-shaped link whose horizontal bar sits at the merge height. Tight groups join near the bottom; well-separated groups join only near the top, leaving a long vertical stretch with no merges. A horizontal line through that stretch cuts the tree into a stable flat clustering.

Vocabulary

Dendrogram
the tree of merges; leaves are data points along the bottom, the vertical axis is merge height
Merge height
the linkage distance hh between the two clusters at the moment they were joined
Linkage
the rule for the distance between two sets of points: single (closest pair), complete (farthest pair), average (mean pair), Ward (increase in within-cluster squared error)
Cut
a horizontal line at height hh: every subtree hanging below it becomes one cluster. Cutting so that exactly kk subtrees remain gives a kk-clustering
Cophenetic distance
c(x,y)c(x,y): the height of the lowest node that contains both xx and yy — the tree's own notion of how far apart they are
Ultrametric
a distance with c(x,z)≤max⁡{c(x,y),c(y,z)}c(x,z)\le\max\{c(x,y),c(y,z)\}; cophenetic distances from a monotone tree always satisfy it
Inversion
a merge lower than a merge below it — possible with centroid and median linkage, and it makes the dendrogram uncuttable at some heights
Leaf order
the left-to-right order of leaves; any subtree may be flipped without changing the tree, so only vertical heights carry information

The math

A hierarchy is a sequence of partitions, each obtained from the previous one by merging exactly two blocks:

P0={{x1},…,{xn}},Pt=Pt−1∖{At,Bt}∪{At∪Bt},(At,Bt)=arg⁡min⁡A≠B∈Pt−1d(A,B)\mathcal P_0=\{\{x_1\},\dots,\{x_n\}\},\qquad \mathcal P_{t}=\mathcal P_{t-1}\setminus\{A_t,B_t\}\cup\{A_t\cup B_t\},\qquad (A_t,B_t)=\arg\min_{A\ne B\in\mathcal P_{t-1}} d(A,B)
Pt\mathcal P_t
the partition after tt merges; it has n−tn-t clusters
d(A,B)d(A,B)
linkage: dissimilarity between two clusters, built from point dissimilarities
ht=d(At,Bt)h_t=d(A_t,B_t)
height of merge tt; the dendrogram draws node tt at this height

Because every partition refines the next, the clusterings for different kk are nested by construction — this is what a single run of k-means for each kk cannot promise.

One update rule for every linkage

Recomputing d(A,B)d(A,B) from all point pairs after every merge would be wasteful. Lance and Williams (1967) showed that the common linkages can all be updated from the old cluster distances alone. When ii and jj merge, the distance from the new cluster to any other cluster kk is

d(i∪j, k)=αi d(i,k)+αj d(j,k)+β d(i,j)+γ ∣d(i,k)−d(j,k)∣d(i\cup j,\,k)=\alpha_i\,d(i,k)+\alpha_j\,d(j,k)+\beta\,d(i,j)+\gamma\,\bigl|d(i,k)-d(j,k)\bigr|
d(i,k)d(i,k)
current distance between clusters ii and kk
αi,αj,β,γ\alpha_i,\alpha_j,\beta,\gamma
coefficients that define the linkage (table below)
ni,nj,nkn_i,n_j,n_k
cluster sizes
LinkageαᵢβγEquivalent to
Single½0−½min⁡(d(i,k),d(j,k))\min(d(i,k),d(j,k)) — closest pair
Complete½0+½max⁡(d(i,k),d(j,k))\max(d(i,k),d(j,k)) — farthest pair
Average (UPGMA)nini+nj\tfrac{n_i}{n_i+n_j}00mean of all cross-cluster pairs
Wardni+nkni+nj+nk\tfrac{n_i+n_k}{n_i+n_j+n_k}−nkni+nj+nk\tfrac{-n_k}{n_i+n_j+n_k}0increase in within-cluster sum of squares
Lance–Williams coefficients. For Ward the rule is applied to squared Euclidean distances d2d^2.

Check single linkage: with α=12,γ=−12\alpha=\tfrac12,\gamma=-\tfrac12 the rule is 12(a+b)−12∣a−b∣=min⁡(a,b)\tfrac12(a+b)-\tfrac12|a-b|=\min(a,b). With γ=+12\gamma=+\tfrac12 it becomes max⁡(a,b)\max(a,b). Which linkage to choose — chaining, compactness, outlier sensitivity — is the main subject of the agglomerative clustering article; here we care about what the resulting tree means.

Deriving Ward's merge cost

Ward's method merges the pair that increases the total within-cluster sum of squares SSE=∑C∑x∈C∥x−μC∥2\text{SSE}=\sum_{C}\sum_{x\in C}\lVert x-\mu_C\rVert^2 the least — the k-means objective, minimized greedily one merge at a time. The increase has a closed form. For any set CC and any point mm, ∑x∈C∥x−m∥2=∑x∈C∥x−μC∥2+nC∥μC−m∥2\sum_{x\in C}\lVert x-m\rVert^2=\sum_{x\in C}\lVert x-\mu_C\rVert^2+n_C\lVert\mu_C-m\rVert^2 (the cross term vanishes because ∑x∈C(x−μC)=0\sum_{x\in C}(x-\mu_C)=0). Apply it to AA and to BB with m=μA∪B=nAμA+nBμBnA+nBm=\mu_{A\cup B}=\tfrac{n_A\mu_A+n_B\mu_B}{n_A+n_B}:

Δ(A,B)=SSE(A∪B)−SSE(A)−SSE(B)=nA∥μA−μAB∥2+nB∥μB−μAB∥2=nAnBnA+nB ∥μA−μB∥2\Delta(A,B)=\text{SSE}(A\cup B)-\text{SSE}(A)-\text{SSE}(B)=n_A\lVert\mu_A-\mu_{AB}\rVert^2+n_B\lVert\mu_B-\mu_{AB}\rVert^2=\frac{n_A n_B}{n_A+n_B}\,\lVert\mu_A-\mu_B\rVert^2
μA,μB\mu_A,\mu_B
centroids of the two clusters
nA,nBn_A,n_B
their sizes
Δ(A,B)\Delta(A,B)
increase in total within-cluster squared error caused by the merge

The last step uses μA−μAB=nBnA+nB(μA−μB)\mu_A-\mu_{AB}=\tfrac{n_B}{n_A+n_B}(\mu_A-\mu_B) and the symmetric expression for BB. So Ward is a centroid distance weighted by a harmonic size factor: merging two big clusters costs more than merging a big one with a small one at the same centroid distance, which is why Ward produces balanced, compact clusters. SciPy and scikit-learn report the height 2Δ\sqrt{2\Delta}, which equals the plain Euclidean distance when two singletons merge (for B and C below, 2⋅12⋅1.1182=1.118\sqrt{2\cdot\tfrac12\cdot1.118^2}=1.118).

Why a cut gives a clean partition: the ultrametric

For single, complete, average and Ward linkage the merge heights never decrease, h1≤h2≤⋯≤hn−1h_1\le h_2\le\dots\le h_{n-1} (the linkage of a merged cluster to any kk is never smaller than the distance that triggered the merge). Define the cophenetic distance c(x,y)c(x,y) as the height of the node where xx and yy first meet. Take three points: the two that meet first, say x,yx,y, do so at c(x,y)c(x,y), and zz joins their cluster later at a single height, so c(x,z)=c(y,z)≥c(x,y)c(x,z)=c(y,z)\ge c(x,y). Therefore

c(x,z)≤max⁡{c(x,y), c(y,z)}for all x,y,zc(x,z)\le\max\{c(x,y),\,c(y,z)\}\quad\text{for all }x,y,z
c(x,y)c(x,y)
cophenetic distance: height of the lowest dendrogram node containing both xx and yy

This strong triangle inequality says every triangle is isosceles with a short base. It implies that "c(x,y)≤hc(x,y)\le h" is an equivalence relation for each hh — which is exactly the statement that cutting at hh yields a partition. A dendrogram is an ultrametric, and hierarchical clustering can be read as approximating your distances by an ultrametric. Centroid and median linkage break monotonicity (inversions), and then a cut is no longer well-defined.

rcoph=corr⁡(d(xi,xj), c(xi,xj))over all (n2) pairs i<jr_{\text{coph}}=\operatorname{corr}\bigl(d(x_i,x_j),\,c(x_i,x_j)\bigr)\quad\text{over all } \tbinom{n}{2}\text{ pairs } i<j
d(xi,xj)d(x_i,x_j)
original dissimilarity
c(xi,xj)c(x_i,x_j)
cophenetic distance from the tree
rcophr_{\text{coph}}
Pearson correlation: how faithfully the tree preserves the input distances (1 = perfectly)

Where to cut

A cut at height hh keeps the merges with ht≤hh_t\le h, giving k(h)=n−#{t:ht≤h}k(h)=n-\#\{t: h_t\le h\} clusters. Because heights are sorted, any hh in the open interval (hn−k,hn−k+1)(h_{n-k},h_{n-k+1}) gives the same kk clusters; the length of that interval measures how robust the kk-clustering is. The classic heuristics:

Choosing the cut

Fixed k
cut where exactly k subtrees remain (fcluster(Z, k, 'maxclust'), n_clusters=k)
Fixed height
cut at a distance with domain meaning, e.g. ≤ 3% sequence divergence (distance_threshold)
Largest gap
cut in the middle of the largest jump ht+1−hth_{t+1}-h_t: the clusters survive the widest range of thresholds
Inconsistency
for each link, (ht−hˉ)/s(h_t-\bar h)/s where hˉ,s\bar h,s are the mean and std of the link heights within a few levels below it; cut links that are unusually tall relative to their subtree
Internal scores
compute silhouette (or Calinski–Harabasz) for every k — cheap, because all cuts come from the same tree

Worked example: eight points, average linkage

Eight points in the plane that the eye sees as three groups: a tight triple at the bottom left, a looser triple on the right, and a pair at the top.

Pointx₁x₂
A1.02.5
B2.51.5
C3.52.0
D6.04.0
E7.57.0
F10.04.5
G4.08.5
H4.510.0
The data. Highlighted: the right-hand group D, E, F, the loosest of the three.
dBCDEFGH
A1.802.555.227.919.226.718.28
B1.124.307.438.087.168.73
C3.206.406.966.528.06
D3.354.034.926.18
E3.543.814.24
F7.217.78
G1.58
Euclidean distance matrix (upper triangle). Bold: the smallest entry, B–C = 1.118, which is the first merge.

Seven merges by hand (average linkage: d(A,B) = mean of all cross pairs)

  1. 1Merge 1: B + C at 1.118, the smallest distance. Update with the size-weighted mean, e.g. d(BC,A)=12(1.80+2.55)=2.176d(BC,A)=\tfrac12(1.80+2.55)=2.176 and d(BC,D)=12(4.30+3.20)=3.751d(BC,D)=\tfrac12(4.30+3.20)=3.751.
  2. 2Merge 2: G + H at 1.581, now the smallest entry. d(GH,E)=12(3.81+4.24)=4.025d(GH,E)=\tfrac12(3.81+4.24)=4.025, d(GH,D)=5.555d(GH,D)=5.555.
  3. 3Merge 3: A + BC at 2.176. The new triple's distance to D is 13(5.22+4.30+3.20)=4.241\tfrac13(5.22+4.30+3.20)=4.241 — the same as the Lance–Williams update 13d(A,D)+23d(BC,D)=13(5.22)+23(3.751)\tfrac13 d(A,D)+\tfrac23 d(BC,D)=\tfrac13(5.22)+\tfrac23(3.751).
  4. 4Merge 4: D + E at 3.354. The bottom-left triple and the top pair are already complete; the right-hand group starts forming. d(DE,F)=12(4.03+3.54)=3.783d(DE,F)=\tfrac12(4.03+3.54)=3.783.
  5. 5Merge 5: F + DE at 3.783. Remaining clusters: {A,B,C}\{A,B,C\}, {D,E,F}\{D,E,F\}, {G,H}\{G,H\} with d(DEF,GH)=5.691d(DEF,GH)=5.691, d(DEF,ABC)=6.525d(DEF,ABC)=6.525, d(ABC,GH)=7.576d(ABC,GH)=7.576.
  6. 6Merge 6: GH + DEF at 5.691. Then d(ABC,DEFGH)=6.946d(ABC,DEFGH)=6.946, the mean of all 15 cross pairs.
  7. 7Merge 7: ABC + DEFGH at 6.946. One cluster; the tree is complete.
MergeJoinsHeightGap to nextClusters after
1B + C1.1180.4637
2G + H1.5810.5956
3A + BC2.1761.1785
4D + E3.3540.4294
5F + DE3.7831.9083
6GH + DEF5.6911.2542
7ABC + DEFGH6.946—1
The merge log, which is the dendrogram. The jump after merge 5 (3.783 → 5.691, gap 1.908) is the largest.

Reading the tree

  1. 1Cut at the largest gap, h=12(3.783+5.691)=4.737h=\tfrac12(3.783+5.691)=4.737: merges 1–5 lie below it, so k=8−5=3k=8-5=3 clusters {A,B,C}\{A,B,C\}, {D,E,F}\{D,E,F\}, {G,H}\{G,H\}. Silhouette: 0.546, higher than for k=2k=2 (0.460) or k=4k=4 (0.449).
  2. 2Other cuts are free. At h=3h=3 only merges 1–3 apply → 5 clusters {A,B,C},{G,H},{D},{E},{F}\{A,B,C\},\{G,H\},\{D\},\{E\},\{F\}. At h=6h=6 → 2 clusters {A,B,C}\{A,B,C\} vs the rest. No re-run needed.
  3. 3Cophenetic distances. A and F first meet in the root, so c(A,F)=6.946c(A,F)=6.946 although d(A,F)=9.22d(A,F)=9.22; D and G meet at merge 6, c(D,G)=5.691c(D,G)=5.691 versus d(D,G)=4.92d(D,G)=4.92. Over all 28 pairs the cophenetic correlation is r=0.809r=0.809.
  4. 4A new point q=(5, 5.5)q=(5,\,5.5). Its mean distance to the three clusters of the cut is 4.508 to ABC, 3.272 to DEF and 3.845 to GH, so it joins {D,E,F}\{D,E,F\} (its nearest single point is also D, at 1.803).
LinkageMerge heightsk = 2 splitCophenetic r
Single1.12 1.58 1.80 3.20 3.35 3.54 3.81ABCDEF | GH0.716
Complete1.12 1.58 2.55 3.35 4.03 7.78 9.22ABC | DEFGH0.805
Average1.12 1.58 2.18 3.35 3.78 5.69 6.95ABC | DEFGH0.809
Ward1.12 1.58 2.47 3.35 3.93 8.42 12.18ABC | DEFGH0.797
Same data, four linkages. Average linkage preserves the distances best (highest cophenetic r); single linkage chains D, E, F onto the bottom-left group and splits off only {G, H} at k = 2.
data · click two points to comparedendrogram (average) · drag the cut00551010ABCDEFGH0.01.73.55.26.9heightABCGHFDEh = 4.74 → k = 3latest merge below the cut: F + DE at height 3.783d(A,F) = 9.220 · cophenetic = 6.946 (merge #7)
clusters k = 3 · merges below cut = 5/7 · silhouette = 0.546
cophenetic correlation (average) = 0.809 · largest gap 3.783 → 5.691
fig.The worked example as a live dendrogram. Drag the rose cut line: everything below it is coloured by flat cluster on both panels, and the scatter draws each merge as a link between the two children's centroids. It starts at the largest gap (h = 4.74, k = 3, silhouette 0.546, cophenetic r = 0.809 for average linkage). Press build to sweep the cut up one merge at a time; switch linkage to see single linkage's flat, chained tree (r = 0.716) or Ward's tall top merges (12.18). A and F are selected: distance 9.220 but cophenetic distance 6.946. The bridge dataset shows single linkage chaining two blobs through a line of points.

The algorithm, step by step

Agglomerative hierarchical clustering

  1. 1Distances. Compute the n×nn\times n dissimilarity matrix ((n2)\tbinom n2 entries). Scale features first if they use different units.
  2. 2Initialize nn singleton clusters, all active.
  3. 3Find the pair of active clusters (i,j)(i,j) with the smallest linkage distance; record the merge (i,j,h=d(i,j),ni+nj)(i,j,h=d(i,j),n_i+n_j).
  4. 4Update the distance from the new cluster i∪ji\cup j to every other active cluster with the Lance–Williams rule; deactivate ii and jj.
  5. 5Repeat steps 3–4 until one cluster remains — n−1n-1 merges. The merge list is the dendrogram (SciPy's linkage matrix ZZ).
  6. 6Cut at a height or a kk to get labels; evaluate several cuts if kk is unknown.

Complexity

Naive
n−1n-1 scans of an O(n2)O(n^2) matrix → O(n3)O(n^3) time, O(n2)O(n^2) memory
Priority queue / nearest-neighbour chain
O(n2)O(n^2) time for Ward, complete and average linkage (SciPy and fastcluster use NN-chain); memory still O(n2)O(n^2)
Single linkage
equals the minimum spanning tree: SLINK runs in O(n2)O(n^2) time and O(n)O(n) memory
Memory wall
the condensed distance matrix for n=100,000n=100{,}000 has ≈5×109\approx 5\times10^9 entries — 40 GB of float64. Beyond roughly tens of thousands of points, summarize first (BIRCH) or use connectivity constraints
Cutting
O(n)O(n) per cut once the tree exists

Divisive clustering (DIANA)

The top-down route splits instead of merges. Trying every bipartition is O(2n)O(2^{n}), so Kaufman and Rousseeuw's DIANA uses a splinter heuristic: in the cluster with the largest diameter, move out the point with the largest average dissimilarity to the others, then keep moving points that are on average closer to the splinter group than to the rest. On the worked example, F has the largest mean distance (6.688) and starts the splinter; E, D, H and G follow, and the first split is {D,E,F,G,H}\{D,E,F,G,H\} vs {A,B,C}\{A,B,C\} — the same top split as average linkage. Divisive methods get the top of the tree right first (decided on global information), while agglomerative methods get the bottom right first; use divisive when you only want a few large clusters.

Variants and tuning

ChoiceOptionsEffect
Linkagesingle · complete · average · WardShapes the whole tree: single chains, complete and Ward favour compact balanced groups, average sits between. Ward requires Euclidean distances
DissimilarityEuclidean, Manhattan, cosine, correlation, Jaccard, edit distance, DTW…Defines similarity; the only place domain knowledge enters. Correlation distance is standard for gene expression
Feature scalingstandardize, robust-scale, noneA feature in larger units dominates every distance and therefore every merge
Cutk, height, largest gap, inconsistency, silhouetteTurns the tree into labels; can be changed after fitting at no cost
Connectivity constraintk-NN graph, grid adjacency (connectivity=)Only neighbours may merge: faster, and gives spatially contiguous clusters (image segmentation)
Directionagglomerative · divisive (DIANA) · bisecting k-meansBottom-up is exact for its linkage; top-down is greedy from the root
Scale-outBIRCH pre-clustering, HDBSCANBIRCH builds the hierarchy on compact summaries; HDBSCAN builds a single-linkage tree on a density-based distance and extracts stable clusters automatically
The knobs that matter, in order of impact.

In code

python
1import numpy as np
2
3def hierarchical(X, linkage="average"):
4 """Agglomerative clustering with Lance-Williams updates. Returns merges (a, b, height, size)."""
5 n = len(X)
6 D = np.sqrt(((X[:, None, :] - X[None, :, :]) ** 2).sum(-1))
7 D = np.pad(D, ((0, n - 1), (0, n - 1))) # room for the n-1 new clusters
8 size = np.r_[np.ones(n), np.zeros(n - 1)]
9 active, merges = list(range(n)), []
10 for step in range(n - 1):
11 best = (np.inf, None, None)
12 for x, i in enumerate(active): # closest pair of active clusters
13 for j in active[x + 1:]:
14 if D[i, j] < best[0]:
15 best = (D[i, j], i, j)
16 h, i, j = best
17 new = n + step
18 ni, nj = size[i], size[j]
19 for k in active:
20 if k in (i, j):
21 continue
22 nk = size[k]
23 if linkage == "single": d = min(D[i, k], D[j, k])
24 elif linkage == "complete": d = max(D[i, k], D[j, k])
25 elif linkage == "average": d = (ni * D[i, k] + nj * D[j, k]) / (ni + nj)
26 else: # ward
27 d = np.sqrt(((ni + nk) * D[i, k]**2 + (nj + nk) * D[j, k]**2 - nk * h**2) / (ni + nj + nk))
28 D[new, k] = D[k, new] = d
29 size[new] = ni + nj
30 merges.append((min(i, j), max(i, j), h, int(ni + nj)))
31 active = [k for k in active if k not in (i, j)] + [new]
32 return merges
33
34def members(merges, n, node):
35 if node < n:
36 return [node]
37 a, b, _, _ = merges[node - n]
38 return members(merges, n, a) + members(merges, n, b)
39
40def cut(merges, n, h):
41 """Flat labels: apply every merge at height <= h."""
42 labels = np.arange(n)
43 for a, b, height, _ in merges:
44 if height > h:
45 break
46 idx = members(merges, n, a) + members(merges, n, b)
47 labels[idx] = labels[idx].min()
48 return np.unique(labels, return_inverse=True)[1]
49
50def cophenetic(merges, n):
51 C = np.zeros((n, n))
52 for a, b, h, _ in merges:
53 for i in members(merges, n, a):
54 for j in members(merges, n, b):
55 C[i, j] = C[j, i] = h
56 return C
57
58X = np.array([[1, 2.5], [2.5, 1.5], [3.5, 2], [6, 4], [7.5, 7], [10, 4.5], [4, 8.5], [4.5, 10]])
59names = "ABCDEFGH"
60merges = hierarchical(X, "average")
61for a, b, h, s in merges:
62 lab = lambda v: "".join(names[i] for i in members(merges, len(X), v))
63 print(f"merge {lab(a):>5} + {lab(b):<5} at {h:.3f} (size {s})")
64print("cut at h=4.737 ->", cut(merges, len(X), 4.737))
65
66D = np.sqrt(((X[:, None] - X[None]) ** 2).sum(-1))
67iu = np.triu_indices(len(X), 1)
68r = np.corrcoef(D[iu], cophenetic(merges, len(X))[iu])[0, 1]
69print(f"cophenetic correlation = {r:.3f}")
70# merge B + C at 1.118 (size 2)
71# merge G + H at 1.581 (size 2)
72# merge A + BC at 2.176 (size 3)
73# merge D + E at 3.354 (size 2)
74# merge F + DE at 3.783 (size 3)
75# merge GH + FDE at 5.691 (size 5)
76# merge ABC + GHFDE at 6.946 (size 8)
77# cut at h=4.737 -> [0 0 0 1 1 1 2 2]
78# cophenetic correlation = 0.809
From scratch: Lance–Williams agglomeration, cutting and cophenetic correlation in NumPy.
python
1import numpy as np
2from scipy.cluster.hierarchy import linkage, fcluster, cophenet
3from scipy.spatial.distance import pdist
4from sklearn.cluster import AgglomerativeClustering
5from sklearn.metrics import silhouette_score
6
7X = np.array([[1, 2.5], [2.5, 1.5], [3.5, 2], [6, 4], [7.5, 7], [10, 4.5], [4, 8.5], [4.5, 10]])
8
9# SciPy: build the whole tree once, then cut it as many ways as you like.
10Z = linkage(X, method="average") # (n-1) x 4: child, child, height, size
11print(Z.round(3)) # heights 1.118 1.581 2.176 3.354 3.783 5.691 6.946
12r, _ = cophenet(Z, pdist(X))
13print(f"cophenetic correlation: {r:.3f}") # 0.809
14
15for k in (2, 3, 4):
16 labels = fcluster(Z, t=k, criterion="maxclust")
17 print(k, labels, f"silhouette={silhouette_score(X, labels):.3f}")
18# 2 [1 1 1 2 2 2 2 2] silhouette=0.460
19# 3 [1 1 1 3 3 3 2 2] silhouette=0.546
20# 4 [1 1 1 3 3 4 2 2] silhouette=0.449
21print("cut at h=4.737:", fcluster(Z, t=4.737, criterion="distance")) # [1 1 1 3 3 3 2 2]
22
23# scikit-learn: same tree, cut by height (distance_threshold) or by k (n_clusters).
24model = AgglomerativeClustering(n_clusters=None, distance_threshold=4.737,
25 linkage="average", compute_distances=True).fit(X)
26print("sklearn labels:", model.labels_, "k =", model.n_clusters_) # [1 1 1 0 0 0 2 2] k = 3
27print("merge heights:", model.distances_.round(3))
28
29# Assign a new point to the cluster with the smallest average distance.
30q = np.array([5, 5.5])
31lab = fcluster(Z, 3, "maxclust")
32for c in np.unique(lab):
33 print(c, round(np.linalg.norm(X[lab == c] - q, axis=1).mean(), 3))
34# 1 4.508 (ABC)
35# 2 3.845 (GH)
36# 3 3.272 (DEF) <- q joins D, E, F
SciPy builds and cuts the tree; scikit-learn gives the same labels. Outputs as comments.

Use when

  • +You do not know k and want to inspect structure at every scale before committing.
  • +The data are genuinely nested (taxonomies, phylogenies, product or topic hierarchies).
  • +You only have a dissimilarity matrix — strings, sequences, graphs — not vectors in a feature space.
  • +n is up to a few tens of thousands, so the O(n²) distance matrix fits in memory.
  • +Results must be deterministic: there is no random initialization as in k-means.

Avoid when

  • −n is in the hundreds of thousands or more: O(n²) memory and at least O(n²) time rule it out without pre-clustering.
  • −You need to cluster new data repeatedly: there is no predict step; the tree must be rebuilt.
  • −Early mistakes matter: greedy merges are never undone, so one noisy point can misplace a whole branch.
  • −Clusters have very different densities or arbitrary shapes in noise — density methods such as DBSCAN or HDBSCAN handle this better.

Where it's used

Phylogenetics

UPGMA (average linkage) on genetic distances builds species trees; the cophenetic distance is the estimated divergence time.

Gene-expression heatmaps

Rows (genes) and columns (samples) are reordered by dendrograms on correlation distance to reveal co-expressed modules and patient subgroups.

Document and product taxonomies

Clustering embeddings of articles or catalogue items gives a browsable topic → sub-topic tree instead of a flat list.

Customer segmentation at several granularities

Marketing can work with 3 broad segments and drill into 12 sub-segments that nest exactly inside them.

Check yourself

In the worked example (average linkage), how many clusters does a cut at height h = 3.0 produce?

Check yourself

What is the cophenetic distance between A and F in the average-linkage tree?

Check yourself

Why can every cut of a single-, complete-, average- or Ward-linkage dendrogram be read as a valid partition?

Check yourself

Two clusters with 4 and 1 points have centroids 2 units apart. By how much does Ward's merge increase the within-cluster sum of squares?

Remember

  • ✓Hierarchical clustering produces one tree of nested partitions; cutting it at height h (or to k subtrees) yields a flat clustering, and every k comes from the same fit.
  • ✓Agglomerative: start from singletons and merge the closest pair n−1n-1 times; the Lance–Williams rule updates any standard linkage from old distances. Divisive (DIANA) splits from the top.
  • ✓Ward merges the pair with the smallest nAnBnA+nB∥μA−μB∥2\tfrac{n_An_B}{n_A+n_B}\lVert\mu_A-\mu_B\rVert^2 — the greedy k-means objective.
  • ✓Monotone merge heights make cophenetic distances an ultrametric; the cophenetic correlation measures how well the tree preserves the input distances.
  • ✓Choose the cut at a large gap in merge heights, by inconsistency, or by scoring each cut; on the example the largest gap gives k = 3 with silhouette 0.546.
  • ✓Cost is O(n2)O(n^2) memory and O(n2)O(n^2)–O(n3)O(n^3) time; scale features, and pre-cluster (BIRCH) for large data.
← back to ML Algorithms roadmap