Hierarchical clustering builds a hierarchy of clusters rather than a single partition.
Two Approaches
- Agglomerative (bottom-up): start with each point as its own cluster and repeatedly merge the closest pair.
- Divisive (top-down): start with one cluster and repeatedly split.
Agglomerative is far more common.
Linkage Criteria
How is the distance between clusters measured?
- Single: closest pair of points — can create long chains.
- Complete: farthest pair — compact clusters.
- Average: mean distance between all pairs.
- Ward: merges that least increase within-cluster variance — often a good default.
Dendrograms
The result is shown as a tree. Cutting the tree at a height gives a set of clusters; large vertical gaps suggest natural cut points.
Strengths
- No need to choose the number of clusters in advance.
- Reveals structure at several levels.
Limitations
- Computation grows quickly with data size, so it suits thousands rather than millions of points.
- Merges can't be undone.
- Sensitive to scaling and distance choice.