Hierarchical Clustering
Build a tree of nested clusters — no need to pick k upfront.
🎯 Core Concept
Hierarchical clustering builds a hierarchy of groups rather than a flat partition. The agglomerative (bottom-up) version starts with every point as its own cluster and repeatedly merges the two closest clusters until one cluster remains. The full merge history is drawn as a dendrogram — a tree you can "cut" at any height to read off the clusters.
🌳 Mental model: A family tree grown backwards in time — start with individuals, keep pairing up the nearest relatives, and watch branches fuse until everyone shares one root. Where you slice the tree decides how many families you see.
🔑 Key Components
Distance Metric
How far apart two points are — usually Euclidean, sometimes cosine or Manhattan.
Linkage
How far apart two clusters are: single (nearest), complete (farthest), average, or Ward (min variance).
Dendrogram
The merge-history tree. Branch height = distance at which clusters joined.
Cut Line
A horizontal slice; the branches it crosses become your final clusters.
⚙️ How It Works
Start: each of the
n points is its own cluster.Compute pairwise distances between all clusters using the chosen linkage.
Merge the two closest clusters into one.
Repeat merging until a single cluster contains everything, recording each merge height.
Cut the dendrogram at a chosen height to extract the desired number of clusters.
🌎 Real-World Applications
Gene expression phylogenetics
Customer segmentation
Document taxonomy
Image region grouping
Social network communities
🧪 Checkpoint Questions
1. Why can hierarchical clustering be preferable to k-Means when you don't know how many groups exist?
Hint: think about what a dendrogram lets you decide after the algorithm runs.
2. Single linkage vs. complete linkage — which is prone to "chaining" long straggly clusters, and why?
Hint: single linkage merges on the nearest pair of points between clusters.
3. Agglomerative clustering is O(n²) or worse in memory. Why does this make it a poor fit for millions of points, and what would you reach for instead?
Hint: it needs a full pairwise distance structure; compare with k-Means / MiniBatch.