Definition
A biologist sorting animals does not start with "make exactly four groups". Cats join lions, dogs join wolves, then cats and dogs join as mammals, and so on up a family tree. Hierarchical clustering builds such a tree from data, and you decide afterwards where to cut it.
Hierarchical clustering groups data into a tree of nested clusters. The common agglomerative (bottom-up) version starts with every point as its own cluster and repeatedly merges the two closest clusters until only one remains. How "closest" is measured between groups is set by the linkage: single (nearest pair of points), complete (farthest pair), average (mean of all pairs) or Ward (the merge that least increases within-cluster variance). The merge history is drawn as a dendrogram, and cutting it at a chosen height gives a flat set of clusters.
In simple words
Imagine every student in a hall standing alone. The two who live closest to each other pair up. Then the next closest pair or group joins, and so on, until the whole hall is one big group. A drawing of who joined whom, and when, is the dendrogram.
Overview
- Hierarchical clustering builds a tree of nested clusters called a dendrogram.
- Agglomerative clustering starts with single points and repeatedly merges the closest clusters.
- The linkage rule decides how distance between clusters is measured.
- Cutting the dendrogram at a chosen height gives flat clusters, so k need not be fixed in advance.
- It stores all pairwise distances, so it suits thousands rather than millions of points.
- It is widely used in biology, for example to build trees of related species or genes.
Why it matters
You often do not know how many groups exist. Hierarchical clustering shows structure at every scale at once, which is why it is used to group genes with similar activity, organise documents into topics and subtopics, build family trees of species and segment customers.
Key terms
- Agglomerative clustering
- Bottom-up: start with single points and keep merging the closest clusters.
- Divisive clustering
- Top-down: start with one cluster and keep splitting it.
- Linkage
- The rule for measuring distance between two clusters: single, complete, average or Ward.
- Dendrogram
- A tree diagram showing which clusters merged and at what distance.
- Cut height
- The distance at which the dendrogram is cut to produce flat clusters.
- Chaining
- A weakness of single linkage: long, straggly clusters formed by links between neighbours.
Types
Hierarchical clustering comes in two directions and several linkage types. These are the types to know.
1. Agglomerative (bottom-up) clustering
Starting with every point alone and merging step by step.
- How it works: After n − 1 merges everything is in one cluster; each merge is recorded at its distance in the dendrogram.
- Example: AgglomerativeClustering or scipy's linkage grouping ten cities by climate.
- When to use it: Use it as the standard form of hierarchical clustering.
2. Divisive (top-down) clustering
Starting with one cluster and splitting it repeatedly.
- How it works: At each step a cluster is split in two, often with k-means (bisecting k-means), until clusters are small enough.
- Example: Splitting a product catalogue into departments, then categories, then sub-categories.
- When to use it: Use it when the top-level split matters most and data is large.
3. Single and complete linkage
Single linkage uses the nearest pair of points; complete linkage the farthest pair.
- How it works: Single linkage follows chains and finds long shapes but can merge clusters through one bridge point; complete linkage makes compact clusters.
- Example: Points at 1, 2, 4, 8, 9 merge at heights 1, 1, 2, 4 with single linkage and 1, 1, 3, 8 with complete linkage.
- When to use it: Use single linkage for elongated shapes and complete linkage for tight, round groups.
4. Average linkage
Using the mean distance between all pairs of points in the two clusters.
- How it works: It balances the chaining of single linkage and the outlier sensitivity of complete linkage.
- Example: Building gene-expression trees in bioinformatics (UPGMA).
- When to use it: Use it as a middle-ground choice when unsure. It is often a sensible choice for non-Euclidean distances too.
5. Ward linkage
Merging the pair of clusters that least increases total within-cluster variance.
- How it works: Ward's method (1963) behaves like k-means and produces round, similar-sized clusters; it needs Euclidean distance.
- Example: Grouping Mumbai, Chennai and Kolkata together as hot, wet and humid cities.
- When to use it: Use it as the default for numeric, scaled data.
Explained in detail
How agglomerative clustering works
With n points, the algorithm begins with n clusters and computes the distance between every pair. It merges the closest pair, recomputes distances between the new cluster and the rest using the chosen linkage, and repeats. After n − 1 merges, everything is in one cluster. The dendrogram records each merge as a horizontal bar at the height of the merge distance. Long vertical gaps in the dendrogram, where no merges happen over a wide range of distances, suggest natural cut points: cutting there gives clusters that are well separated. Unlike k-means, you do not need to choose k in advance, and the result does not depend on random starting centres, so the same data always gives the same tree.
Choosing a linkage
| Linkage | Distance between clusters | Typical behaviour |
|---|---|---|
| Single | Closest pair of points | Finds long, irregular shapes; prone to chaining |
| Complete | Farthest pair of points | Compact, similar-sized clusters; sensitive to outliers |
| Average | Mean distance over all pairs | A balance between single and complete |
| Ward | Increase in within-cluster variance | Round clusters similar to k-means; a good default |
Practical points
Standardise features first, because distances are dominated by the feature with the largest numbers: rainfall in millimetres would swamp temperature in degrees. The algorithm stores all pairwise distances, so memory grows with n², which makes plain hierarchical clustering practical for thousands of points but not millions; for large data, cluster a sample or use k-means first. Merges are never undone, so an early bad merge caused by noise stays in the tree. Always check the result by looking at the members of each cluster and asking whether the grouping makes sense to someone who knows the domain. In the code below, Ward linkage with four clusters groups Mumbai, Chennai and Kolkata (hot, wet and humid), pairs Jaipur with Jaisalmer (dry), leaves Leh alone as a cold desert, and puts Delhi, Shimla, Srinagar and Bengaluru in one mixed middle group, which a geographer might want to split further.
Real-world scenarios: biologists build family trees of species from DNA similarity; news sites group thousands of articles into topics and then subtopics, such as sport, then cricket, then a particular series; and retailers use dendrograms to decide how many customer segments are worth separate campaigns. In each case the tree is useful because people can choose the level of detail that suits their decision.
How it works
- Choose and standardise the features to compare.
- Pick a distance (usually Euclidean) and a linkage (Ward is a good start).
- Build the tree with scipy's linkage function and draw the dendrogram.
- Cut where there is a big gap between merge heights, or at a chosen number of clusters.
- Inspect and name each cluster.
The maths
Five points lie on a line at A = 1, B = 2, C = 4, D = 8 and E = 9. The closest pairs are A–B and D–E, both at distance 1, so they merge first. Next, C joins {A, B}: with single linkage the distance is |4 − 2| = 2; with complete linkage it is |4 − 1| = 3; with average linkage it is (3 + 2) ÷ 2 = 2.5. Finally {A, B, C} merges with {D, E}: single linkage gives 8 − 4 = 4, while complete linkage gives 9 − 1 = 8. Cutting the dendrogram between heights 2 and 4 (single linkage) gives two clusters, {A, B, C} and {D, E}.
In code
import numpy as np
import pandas as pd
from scipy.cluster.hierarchy import dendrogram, fcluster, linkage
import matplotlib.pyplot as plt
# The worked example: five points on a line
pts = np.array([[1], [2], [4], [8], [9]])
for method in ["single", "complete", "average"]:
print(method.ljust(8), "merge heights:", linkage(pts, method=method)[:, 2].round(2))
# Approximate yearly climate figures for ten places (rounded, for illustration)
cities = pd.DataFrame({
"temp_c": [25, 26, 27, 29, 27, 15, 14, 24, 27, 6],
"rain_mm": [790, 650, 2200, 1400, 1600, 1500, 720, 970, 210, 100],
"humidity_pc": [60, 50, 77, 70, 75, 60, 60, 65, 40, 35],
}, index=["Delhi", "Jaipur", "Mumbai", "Chennai", "Kolkata", "Shimla", "Srinagar", "Bengaluru", "Jaisalmer", "Leh"])
z = (cities - cities.mean()) / cities.std()
tree = linkage(z, method="ward")
groups = fcluster(tree, t=4, criterion="maxclust")
for g in sorted(set(groups)):
print(f"Cluster {g}:", ", ".join(cities.index[groups == g]))
fig, ax = plt.subplots(figsize=(6, 3))
dendrogram(tree, labels=list(cities.index), ax=ax, leaf_rotation=60)
ax.set_title("Cities clustered by climate (Ward linkage)"); ax.set_ylabel("Merge distance")
plt.tight_layout()Output
single merge heights: [1. 1. 2. 4.] complete merge heights: [1. 1. 3. 8.] average merge heights: [1. 1. 2.5 6.17] Cluster 1: Mumbai, Chennai, Kolkata Cluster 2: Jaipur, Jaisalmer Cluster 3: Delhi, Shimla, Srinagar, Bengaluru Cluster 4: Leh
Try it yourself
Build a dendrogram
Put the agglomerative steps in order.
- 1Update distances with the chosen linkage
- 2Repeat until one cluster remains, then cut the tree
- 3Treat every point as its own cluster
- 4Merge the two closest clusters
- 5Compute distances between all clusters
Match the linkage
Which linkage uses each distance?
- Single
- Complete
- Average
- Ward
Common mistakes
- Clustering unscaled features so one unit dominates.
- Running plain hierarchical clustering on hundreds of thousands of rows.
- Treating the cut as the one true answer instead of checking the clusters.
Check yourself
Summary
- Agglomerative clustering merges the closest clusters step by step into a tree.
- The linkage defines cluster distance; Ward is a good default, single can chain.
- Read the dendrogram, cut at a large gap, and check that the clusters make sense.
Finished reading?
Sources: SciPy: hierarchical clustering (scipy.cluster.hierarchy) · scikit-learn: clustering (k-means, hierarchical, DBSCAN)