Hierarchical Clustering
Linkage criteria, dendrograms, when hierarchy beats flat clustering
You have 500 customer support tickets. You need to organize them into a hierarchy — broad themes (Product Bug, Billing, UX) and sub-themes (Product Bug: Login, Checkout, API). K-means gives you flat clusters and requires you to commit to K before seeing results. Hierarchical clustering builds a tree — the dendrogram — that you cut at any level to get the granularity you want. One run gives you every possible K simultaneously.
Agglomerative clustering (bottom-up): start with each point as its own cluster. Merge the two closest clusters. Repeat until all points are in one cluster. The merge history forms the dendrogram, where the y-axis records the distance at each merge.
The linkage criterion determines what "distance between clusters" means. Single linkage: distance between the closest pair of points across clusters — produces elongated "chaining" clusters. Complete linkage: distance between the farthest pair — produces compact clusters. Average linkage: average distance between all pairs. Ward's linkage: merges the pair that minimizes total within-cluster variance after merging. Ward produces compact, equal-variance clusters and is almost always the best default.
Reading the dendrogram: long vertical segments mark natural cluster boundaries — a large jump in merge distance means the two groups being merged were genuinely far apart. Draw a horizontal cut line; each branch it crosses is one cluster. If there are no long segments, the data probably does not have discrete structure.
Complexity: O(n²) space for the distance matrix, O(n³) time for the naive merge sequence. Infeasible for n > 10,000. For large datasets use HDBSCAN or approximate methods.
NOT-this: "You need to specify K before running hierarchical clustering." The whole point is you do not. You run once, get the full dendrogram, inspect it, and decide where to cut based on the structure. You can cut at different heights for different analysis needs without rerunning — that is the main advantage over K-means.
Key points
- Use hierarchical clustering with Ward linkage when you need interpretable nested structure and n < 10,000. The dendrogram gives you all granularity levels in one run — you can read off 3 clusters, 7 clusters, or 20 clusters without refitting. Product taxonomies, gene pathway hierarchies, and support ticket category trees are the right domain for this method.
- Trap: running hierarchical clustering on raw high-dimensional features. Pairwise distance computation in 1000 dimensions is dominated by noise — every pair looks roughly equidistant. Reduce to 20–50 PCA components first. Without this step, the distances driving the dendrogram are measuring noise, not structure.
- Diagnostic: if the dendrogram shows one large cluster absorbing all others at the last step, your data has one dominant cluster with outliers. Use DBSCAN to explicitly model noise points rather than forcing them into clusters. A dendrogram with no long vertical segments carries the same signal — discrete cluster structure is absent from this data under this algorithm.
The dendrogram encodes cluster structure at every granularity in one run — natural boundaries appear as long vertical segments, and the absence of those segments means discrete cluster structure is probably not there.
Recap
- Dendrogram = every K in one run: cut at any height, no need to commit K.
- Agglomerative (bottom-up): each point its own cluster → merge closest → repeat.
- Linkage = definition of cluster distance: single (chaining), complete (compact), average, Ward (min variance).
- Ward is the near-universal default — compact, equal-variance clusters.
- Read the tree: long vertical segments = natural boundaries; none = no discrete structure.
- Cost: $O(n^2)$ space, $O(n^3)$ time — infeasible past ~10,000 points; use HDBSCAN.
- Reduce to 20–50 PCA dims first — raw high-D distances measure noise.
Check your understanding
Q1. You are clustering genes based on expression profiles. Why might hierarchical clustering with Ward linkage be more appropriate than k-means?
- A) Hierarchical clustering is always preferred for biological data purely because gene expression features are non-Gaussian in distribution
- B) Ward linkage specifically handles the high dimensionality of gene expression data far better than k-means centroids ever could
- C) K-means is faster, but hierarchical clustering becomes strictly necessary once the dataset has more than 500 genes to cluster
- D) Genes have a natural pathway-module-process hierarchy — one run gives every granularity, and Ward gives compact co-expression groups
Q2. Two researchers use the same dataset but different linkage criteria. Researcher A uses single linkage and gets one large cluster containing 95% of the data. Researcher B uses Ward linkage and gets 5 balanced clusters. Which two statements correctly explain when each researcher is right?
- A) If the data is filamentary or chain-shaped, single linkage one large cluster can be the structurally correct answer here
- B) If the data is really five distinct blobs joined only by thin bridges, Ward linkage balanced clusters can be correct
- C) Single linkage always produces degenerate chaining results and should never be used on any real dataset whatsoever
- D) One large cluster from single linkage always proves the data has no true subgroup structure of any kind at all
Q3. How do you determine the optimal cut height on a dendrogram when there is no obvious long gap?
- A) Always cut at the median linkage height across the whole dendrogram, since this reliably maximises balance between the resulting clusters
- B) The absence of a long gap proves conclusively that the data has no cluster structure at all — stop and use a different algorithm entirely
- C) Use the acceleration plot, silhouette across cuts, domain knowledge, or a GMM BIC curve — no method is authoritative here alone
- D) Use complete linkage instead of Ward linkage — complete linkage always produces measurably clearer gaps in the resulting dendrogram
Q4. A colleague wants to run hierarchical clustering on 100,000 points. What do you tell them?
- A) Use single linkage — its SLINK implementation runs in O(n log n) time and handles 100,000 points easily without any real issue
- B) Hierarchical clustering is feasible up to 500,000 points with modern hardware; the O(n²) limit only applies to Ward linkage
- C) Subsample to 10,000 points, run hierarchical clustering on that subsample, then assign remaining points by nearest-centroid
- D) Naive clustering on 100,000 points needs ~40GB and months of O(n³) compute — use HDBSCAN, BIRCH+agglomerative, or subsample
Try it interactively
ML Systems Lab is a free interview-prep platform for ML engineers — work through the full interactive module, quizzes, and drills.
Open ML Systems Lab →