Hierarchical clustering builds a full tree of nested clusters — from every point in its own cluster up to one giant cluster containing everything — letting you choose how many clusters you want after seeing the whole structure, rather than committing to \(k\) upfront.
Agglomerative vs Divisive
| Approach | Direction | How Common |
|---|---|---|
| Agglomerative | Bottom-up: start with every point as its own cluster, repeatedly merge the closest pair | The standard, widely-used approach — see Agglomerative Clustering |
| Divisive | Top-down: start with one cluster containing everything, repeatedly split | Rare in practice — computationally expensive |
The Dendrogram — Reading the Whole Tree at Once
Cutting the dendrogram at any height gives a different number of clusters — cutting below the final merge (at height 5) gives 2 clusters: {A,B} and {C,D}.
Worked Example
4 points: \(A(1,1)\), \(B(2,1)\), \(C(5,5)\), \(D(6,5)\).
| Pair | Distance |
|---|---|
| A-B | 1.0 |
| C-D | 1.0 |
| B-C | 5.0 |
| A-C | ≈ 5.66 |
| B-D | ≈ 5.66 |
| A-D | ≈ 6.40 |
Step 1: merge the closest pair, A-B (distance 1), into cluster {A,B}. Step 2: merge the next closest pair, C-D (distance 1), into cluster {C,D}. Step 3: merge {A,B} and {C,D} — using single linkage (the minimum distance between any pair across the two clusters), that's B-C at distance 5, so the final merge happens at height 5.
from scipy.cluster.hierarchy import dendrogram, linkage
import numpy as np
X = np.array([[1,1],[2,1],[5,5],[6,5]])
Z = linkage(X, method="single") # single linkage, matching the hand calculation
print(Z) # each row: [cluster1, cluster2, distance, num_points_in_new_cluster]
dendrogram(Z, labels=["A","B","C","D"])Linkage Criteria — How "Distance Between Clusters" Is Defined
| Linkage | Definition |
|---|---|
| Single | Minimum distance between any pair of points across the two clusters |
| Complete | Maximum distance between any pair — tends to produce more compact, evenly-sized clusters |
| Average | Average distance across all pairs |
| Ward | Minimizes the increase in total within-cluster variance from merging — often the most balanced default |
Practical Use Cases
- When you want to explore multiple possible numbers of clusters without re-running the algorithm — one dendrogram supports cutting at any height
- Gene expression analysis, document taxonomy building, and other domains where a natural hierarchy of groupings is meaningful
Common Mistakes
- Choosing single linkage by default without realizing it can produce long, straggly "chained" clusters — complete or Ward linkage often gives more intuitive, compact groupings.
- Running hierarchical clustering on very large datasets — it's \(O(n^2)\) or worse in both time and memory, impractical much beyond a few thousand points.
Interview Relevance
Q: "What's the main advantage of hierarchical clustering over K-Means?" You don't need to choose the number of clusters upfront — the dendrogram shows the full nested structure, and you can decide how many clusters to use by cutting at different heights, after seeing the whole picture.
Practice Question
Using the 4-point example, explain why complete linkage (using the maximum, not minimum, distance) would merge {A,B} and {C,D} at a different height than single linkage did.
