Hierarchical Clustering

Building a tree of nested clusters — either by merging (agglomerative) or splitting (divisive) — visualized as a dendrogram.

Hierarchical clustering — cut the dendrogram to choose K clusters

cut=0.42

Drag to cut the dendrogram — 2 clusters result

Definition

Hierarchical clustering builds a tree of nested clusters — a dendrogram — rather than a flat partition. You don't need to specify $K$ in advance; you cut the tree at the desired level to get any number of clusters.

Two strategies:

Agglomerative (bottom-up): start with each point as its own cluster, then repeatedly merge the two closest clusters
Divisive (top-down): start with one cluster containing all points, then recursively split

Agglomerative is far more common.

Linkage criteria define "distance between clusters" (since clusters contain multiple points):

Single linkage: distance = min pairwise distance (nearest neighbor)
Complete linkage: distance = max pairwise distance (farthest neighbor)
Average linkage: distance = mean pairwise distance
Ward linkage: minimize total within-cluster variance after merging

Key properties

Produces a full hierarchy of clusterings at once — any number of clusters can be read off by cutting at a different height
Merges are irreversible: once two clusters combine, they stay combined for the rest of the algorithm
Deterministic given a fixed linkage criterion — unlike k-means, there's no randomness from initialization
Doesn't require choosing $K$ in advance, only at the end (when cutting the dendrogram)

Common mistakes

Running it on very large datasets: naive agglomerative clustering's $O(n^2)$ memory and $O(n^3)$ time make it impractical past a few thousand points without specialized algorithms
Using single linkage when you expect compact clusters: the chaining effect can merge distinct dense groups through a thin bridge of intermediate points
Treating dendrogram structure as ground truth: greedy, irreversible merges mean an early suboptimal merge can never be undone later

Reading a dendrogram

A dendrogram has individual points as leaves. The height at which two branches merge indicates the distance at which those clusters were combined. Cut the dendrogram at height $h$ : any branches below $h$ are merged; any branches above $h$ stay separate. The number of cut lines you cross is the number of clusters.

Try it

Five points with pairwise distances: $d(A,B)=1$ , $d(C,D)=1.5$ , $d(A,C)=3$ , $d(B,C)=3.5$ , $d(A,D)=d(B,D)=4$ , $d(E,\cdot)=6$ for all others. Trace the first two merges under single-linkage clustering.

Solution

Merge 1: smallest distance is $d(A,B)=1$ . Merge $A$ and $B$ into cluster $\{A,B\}$ .

Merge 2: recalculate distances. $d(\{A,B\},C) = \min(d(A,C),d(B,C)) = \min(3, 3.5) = 3$ (single linkage). $d(C,D) = 1.5$ is still the smallest. Merge $C$ and $D$ into $\{C,D\}$ .

After these two merges we have: $\{A,B\}$ , $\{C,D\}$ , $\{E\}$ .

Related concepts

Needs first

K-Means Clustering Norms

DBSCAN Dimensionality Reduction

View in full concept graph →