Hierarchical Clustering

Hierarchical clustering is a Clustering approach that builds a tree of nested clusters (a dendrogram) instead of returning a single flat partition. The tree is built bottom-up (agglomerative, AGNES) by repeatedly merging the closest two clusters, or top-down (divisive) by repeatedly splitting the largest cluster.

Why It Is Useful

A dendrogram exposes structure at every granularity in one run. Cutting the tree at different heights gives different numbers of clusters, so you don’t need to commit to $k$ in advance the way k-means does. The cost is $O(n^2)$ memory or worse for the distance matrix, which makes it impractical above a few tens of thousands of points.

AGNES (Agglomerative)

1. Start with each point in its own cluster.
2. Compute pairwise distances using a chosen metric (Euclidean, cosine, Manhattan; see Distance Metrics And Similarity Measures).
3. Merge the two closest clusters, where “closest” is defined by the linkage criterion.
4. Repeat until everything is in one cluster.

The whole structure is recorded as the dendrogram; you read clusters off it by cutting at a chosen height.

Linkage Criteria

See Hierarchical Clustering - Linkage Criteria.

Divisive

Top-down: start with one cluster containing everything, then split recursively. Less common in practice because every split is itself a clustering problem, often solved by running k-means with $k=2$ at each level. Useful when the high-level structure matters more than fine-grained leaves.

Reading The Dendrogram

The y-axis of a dendrogram is the linkage distance at which clusters merge. A horizontal cut at height $h$ gives all clusters that were still separate at that distance — this is how you choose $k$ post-hoc. Large vertical gaps between merges suggest natural cluster boundaries; tight stacks suggest the data does not split cleanly there.

Failure Modes

• High-dimensional data: pairwise distances concentrate, making linkage choices noisy. Project or use cosine instead of Euclidean.
• Noise and outliers: single linkage chains them into existing clusters; complete linkage isolates them. Consider DBSCAN when noise points are common.
• Scalability: building the full distance matrix is $O(n^2)$ memory. For large $n$, sample first or switch to scalable alternatives.
• Cluster shape mismatch: Ward and complete linkage assume roughly convex clusters; non-convex shapes are better handled by DBSCAN.

One-line Interview Answer

Hierarchical clustering builds a dendrogram of nested clusters by repeatedly merging the two closest clusters under a chosen linkage criterion (single, complete, average, or Ward), letting you pick $k$ by cutting the tree at any height after the fact.

Run By Hand

The complete guide to clustering analysis: k-means and hierarchical clustering by hand and in R