Definition
Hierarchical clustering builds a nested family of clusterings of the same data — from 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 gives an ordinary flat clustering, and every from 1 to 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
- points (or just an dissimilarity matrix) → a binary tree with merge heights; a cut turns it into labels
- Learns
- the order in which groups join and the height of each join
- Training
- agglomerative: to time and 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 groups — and asks you to pick 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 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 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 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 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 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 : every subtree hanging below it becomes one cluster. Cutting so that exactly subtrees remain gives a -clustering
- Cophenetic distance
- : the height of the lowest node that contains both and — the tree's own notion of how far apart they are
- Ultrametric
- a distance with ; 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:
- the partition after merges; it has clusters
- linkage: dissimilarity between two clusters, built from point dissimilarities
- height of merge ; the dendrogram draws node at this height
Because every partition refines the next, the clusterings for different are nested by construction — this is what a single run of k-means for each cannot promise.
One update rule for every linkage
Recomputing 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 and merge, the distance from the new cluster to any other cluster is
- current distance between clusters and
- coefficients that define the linkage (table below)
- cluster sizes
| Linkage | αᵢ | β | γ | Equivalent to |
|---|---|---|---|---|
| Single | ½ | 0 | −½ | — closest pair |
| Complete | ½ | 0 | +½ | — farthest pair |
| Average (UPGMA) | 0 | 0 | mean of all cross-cluster pairs | |
| Ward | 0 | increase in within-cluster sum of squares |
Check single linkage: with the rule is . With it becomes . 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 the least — the k-means objective, minimized greedily one merge at a time. The increase has a closed form. For any set and any point , (the cross term vanishes because ). Apply it to and to with :
- centroids of the two clusters
- their sizes
- increase in total within-cluster squared error caused by the merge
The last step uses and the symmetric expression for . 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 , which equals the plain Euclidean distance when two singletons merge (for B and C below, ).
Why a cut gives a clean partition: the ultrametric
For single, complete, average and Ward linkage the merge heights never decrease, (the linkage of a merged cluster to any is never smaller than the distance that triggered the merge). Define the cophenetic distance as the height of the node where and first meet. Take three points: the two that meet first, say , do so at , and joins their cluster later at a single height, so . Therefore
- cophenetic distance: height of the lowest dendrogram node containing both and
This strong triangle inequality says every triangle is isosceles with a short base. It implies that "" is an equivalence relation for each — which is exactly the statement that cutting at 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.
- original dissimilarity
- cophenetic distance from the tree
- Pearson correlation: how faithfully the tree preserves the input distances (1 = perfectly)
Where to cut
A cut at height keeps the merges with , giving clusters. Because heights are sorted, any in the open interval gives the same clusters; the length of that interval measures how robust the -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 : the clusters survive the widest range of thresholds
- Inconsistency
- for each link, where 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.
| Point | x₁ | x₂ |
|---|---|---|
| A | 1.0 | 2.5 |
| B | 2.5 | 1.5 |
| C | 3.5 | 2.0 |
| D | 6.0 | 4.0 |
| E | 7.5 | 7.0 |
| F | 10.0 | 4.5 |
| G | 4.0 | 8.5 |
| H | 4.5 | 10.0 |
| d | B | C | D | E | F | G | H |
|---|---|---|---|---|---|---|---|
| A | 1.80 | 2.55 | 5.22 | 7.91 | 9.22 | 6.71 | 8.28 |
| B | 1.12 | 4.30 | 7.43 | 8.08 | 7.16 | 8.73 | |
| C | 3.20 | 6.40 | 6.96 | 6.52 | 8.06 | ||
| D | 3.35 | 4.03 | 4.92 | 6.18 | |||
| E | 3.54 | 3.81 | 4.24 | ||||
| F | 7.21 | 7.78 | |||||
| G | 1.58 |
Seven merges by hand (average linkage: d(A,B) = mean of all cross pairs)
- 1Merge 1: B + C at 1.118, the smallest distance. Update with the size-weighted mean, e.g. and .
- 2Merge 2: G + H at 1.581, now the smallest entry. , .
- 3Merge 3: A + BC at 2.176. The new triple's distance to D is — the same as the Lance–Williams update .
- 4Merge 4: D + E at 3.354. The bottom-left triple and the top pair are already complete; the right-hand group starts forming. .
- 5Merge 5: F + DE at 3.783. Remaining clusters: , , with , , .
- 6Merge 6: GH + DEF at 5.691. Then , the mean of all 15 cross pairs.
- 7Merge 7: ABC + DEFGH at 6.946. One cluster; the tree is complete.
| Merge | Joins | Height | Gap to next | Clusters after |
|---|---|---|---|---|
| 1 | B + C | 1.118 | 0.463 | 7 |
| 2 | G + H | 1.581 | 0.595 | 6 |
| 3 | A + BC | 2.176 | 1.178 | 5 |
| 4 | D + E | 3.354 | 0.429 | 4 |
| 5 | F + DE | 3.783 | 1.908 | 3 |
| 6 | GH + DEF | 5.691 | 1.254 | 2 |
| 7 | ABC + DEFGH | 6.946 | — | 1 |
Reading the tree
- 1Cut at the largest gap, : merges 1–5 lie below it, so clusters , , . Silhouette: 0.546, higher than for (0.460) or (0.449).
- 2Other cuts are free. At only merges 1–3 apply → 5 clusters . At → 2 clusters vs the rest. No re-run needed.
- 3Cophenetic distances. A and F first meet in the root, so although ; D and G meet at merge 6, versus . Over all 28 pairs the cophenetic correlation is .
- 4A new point . 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 (its nearest single point is also D, at 1.803).
| Linkage | Merge heights | k = 2 split | Cophenetic r |
|---|---|---|---|
| Single | 1.12 1.58 1.80 3.20 3.35 3.54 3.81 | ABCDEF | GH | 0.716 |
| Complete | 1.12 1.58 2.55 3.35 4.03 7.78 9.22 | ABC | DEFGH | 0.805 |
| Average | 1.12 1.58 2.18 3.35 3.78 5.69 6.95 | ABC | DEFGH | 0.809 |
| Ward | 1.12 1.58 2.47 3.35 3.93 8.42 12.18 | ABC | DEFGH | 0.797 |
The algorithm, step by step
Agglomerative hierarchical clustering
- 1Distances. Compute the dissimilarity matrix ( entries). Scale features first if they use different units.
- 2Initialize singleton clusters, all active.
- 3Find the pair of active clusters with the smallest linkage distance; record the merge .
- 4Update the distance from the new cluster to every other active cluster with the Lance–Williams rule; deactivate and .
- 5Repeat steps 3–4 until one cluster remains — merges. The merge list is the dendrogram (SciPy's linkage matrix ).
- 6Cut at a height or a to get labels; evaluate several cuts if is unknown.
Complexity
- Naive
- scans of an matrix → time, memory
- Priority queue / nearest-neighbour chain
- time for Ward, complete and average linkage (SciPy and fastcluster use NN-chain); memory still
- Single linkage
- equals the minimum spanning tree: SLINK runs in time and memory
- Memory wall
- the condensed distance matrix for has entries — 40 GB of float64. Beyond roughly tens of thousands of points, summarize first (BIRCH) or use connectivity constraints
- Cutting
- per cut once the tree exists
Divisive clustering (DIANA)
The top-down route splits instead of merges. Trying every bipartition is , 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 vs — 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
| Choice | Options | Effect |
|---|---|---|
| Linkage | single · complete · average · Ward | Shapes the whole tree: single chains, complete and Ward favour compact balanced groups, average sits between. Ward requires Euclidean distances |
| Dissimilarity | Euclidean, Manhattan, cosine, correlation, Jaccard, edit distance, DTW… | Defines similarity; the only place domain knowledge enters. Correlation distance is standard for gene expression |
| Feature scaling | standardize, robust-scale, none | A feature in larger units dominates every distance and therefore every merge |
| Cut | k, height, largest gap, inconsistency, silhouette | Turns the tree into labels; can be changed after fitting at no cost |
| Connectivity constraint | k-NN graph, grid adjacency (connectivity=) | Only neighbours may merge: faster, and gives spatially contiguous clusters (image segmentation) |
| Direction | agglomerative · divisive (DIANA) · bisecting k-means | Bottom-up is exact for its linkage; top-down is greedy from the root |
| Scale-out | BIRCH pre-clustering, HDBSCAN | BIRCH builds the hierarchy on compact summaries; HDBSCAN builds a single-linkage tree on a density-based distance and extracts stable clusters automatically |
In code
1import numpy as np23def 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 clusters8 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 clusters13 for j in active[x + 1:]:14 if D[i, j] < best[0]:15 best = (D[i, j], i, j)16 h, i, j = best17 new = n + step18 ni, nj = size[i], size[j]19 for k in active:20 if k in (i, j):21 continue22 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: # ward27 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] = d29 size[new] = ni + nj30 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 merges3334def 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)3940def 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 break46 idx = members(merges, n, a) + members(merges, n, b)47 labels[idx] = labels[idx].min()48 return np.unique(labels, return_inverse=True)[1]4950def 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] = h56 return C5758X = 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))6566D = 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.8091import numpy as np2from scipy.cluster.hierarchy import linkage, fcluster, cophenet3from scipy.spatial.distance import pdist4from sklearn.cluster import AgglomerativeClustering5from sklearn.metrics import silhouette_score67X = 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]])89# 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, size11print(Z.round(3)) # heights 1.118 1.581 2.176 3.354 3.783 5.691 6.94612r, _ = cophenet(Z, pdist(X))13print(f"cophenetic correlation: {r:.3f}") # 0.8091415for 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.46019# 3 [1 1 1 3 3 3 2 2] silhouette=0.54620# 4 [1 1 1 3 3 4 2 2] silhouette=0.44921print("cut at h=4.737:", fcluster(Z, t=4.737, criterion="distance")) # [1 1 1 3 3 3 2 2]2223# 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 = 327print("merge heights:", model.distances_.round(3))2829# 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, FUse 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 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 — 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 memory and – time; scale features, and pre-cluster (BIRCH) for large data.