I5 · Machine Learning Foundations

Hierarchical Clustering

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.

10 min Intermediate · Sublevel Intermediate Jump to the activity

What you need: The earlier topics of this module.

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

LinkageDistance between clustersTypical behaviour
SingleClosest pair of pointsFinds long, irregular shapes; prone to chaining
CompleteFarthest pair of pointsCompact, similar-sized clusters; sensitive to outliers
AverageMean distance over all pairsA balance between single and complete
WardIncrease in within-cluster varianceRound 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

  1. Choose and standardise the features to compare.
  2. Pick a distance (usually Euclidean) and a linkage (Ward is a good start).
  3. Build the tree with scipy's linkage function and draw the dendrogram.
  4. Cut where there is a big gap between merge heights, or at a chosen number of clusters.
  5. Inspect and name each cluster.

The maths

Single and complete linkage
Average linkage

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

hierarchical_cities.py
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.

  1. 1Update distances with the chosen linkage
  2. 2Repeat until one cluster remains, then cut the tree
  3. 3Treat every point as its own cluster
  4. 4Merge the two closest clusters
  5. 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

Question 1

1. What does a dendrogram show?

Question 2

2. Which linkage is most prone to chaining?

Question 3

3. An advantage over k-means is that hierarchical clustering…

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)