Hierarchical Clustering
Introduction
Hierarchical clustering builds a whole hierarchy of clusters rather than a single flat partition. Instead of committing to a fixed number of clusters up front, it produces a tree — the dendrogram — that records how points and groups merge (or split) at every scale. You then read off whatever clustering you want by cutting the tree at a chosen height.
This is its headline advantage over k-means: you do not need to pick k before you start. The hierarchy also reveals nested structure — clusters within clusters — which a flat method hides.
Core intuition: treat every data point as its own tiny cluster, then keep gluing the two closest clusters together until everything is one big cluster. The order and the distances of those merges are the dendrogram.
Two directions: agglomerative vs divisive
Agglomerative (bottom-up)
Start with n singleton clusters. Repeatedly merge the two closest clusters until a single cluster remains. This is by far the most common approach and the one the demo below implements.
Each merge adds one node to the tree; after n − 1 merges you have the full dendrogram.
Divisive (top-down)
Start with all points in one cluster and recursively split the least-coherent cluster into two, working downward.
Considering every possible split is exponential, so divisive methods rely on heuristics (e.g. DIANA). They are far less common in practice than agglomerative clustering.
The dendrogram and cutting it
A dendrogram is the tree of merges. The horizontal axis lists the points; the vertical axis is the merge height — the linkage distance at which two clusters joined. Points that merge low are very similar; merges high up join already-distinct groups.
To get a concrete clustering, draw a horizontal line at some height and cut. Every vertical branch the line crosses becomes one cluster. Cut low and you get many small clusters; cut high and you get a few large ones — choosing the cut height is exactly equivalent to choosing the number of clusters, but you decide it after seeing the structure, not before.
A common heuristic: cut where there is a large vertical gap between consecutive merges. A big jump means the next merge would fuse two genuinely far-apart groups, so the clustering just below that gap is often the "natural" one.
Interactive: agglomerative clustering + dendrogram
The widget runs real agglomerative clustering on the 12 labeled points in JavaScript: it starts with every point as its own cluster and repeatedly merges the two closest clusters under your chosen linkage, recording each merge height. Switch the linkage criterion and drag the cut to watch the clusters and the dendrogram respond.
2D points, colored by the clustering at the current cut
Same color = same cluster. These groups are exactly what you get by slicing the dendrogram at the cut line.
Dendrogram (merge heights = real linkage distances)
Each inverted-U is one merge; its height is the actual linkage distance. The dashed line is your cut: every branch it crosses becomes a separate cluster.
Ward's method = merge the pair that increases total within-cluster variance the least. Tends to produce balanced, roughly spherical clusters; the usual default.
No k is chosen in advance. You build the full tree once, then pick the number of clusters afterward by sliding the cut. Try switching linkage to single and watch the merge heights compress as chaining sets in.
Linkage criteria: how "distance between clusters" is defined
The merge rule needs a notion of distance between two clusters, not just two points. That definition is the linkage criterion, and it dramatically changes the shapes of the clusters you get. Let d(a, b) be the distance between points, and A, B be two clusters.
| Linkage | Cluster distance | Behavior |
|---|---|---|
| Single | mina∈A, b∈B d(a, b) | Closest pair. Can capture long, non-convex shapes but chains: a string of intermediate points links distant groups into one straggly cluster. |
| Complete | maxa∈A, b∈B d(a, b) | Farthest pair. Produces compact, roughly equal-diameter clusters; sensitive to outliers. |
| Average | (1 / |A||B|) Σa∈A Σb∈B d(a, b) | Mean over all cross-pairs (UPGMA). A balance between single and complete. |
| Ward | Δ within-cluster variance from merging A, B | Merges the pair that increases total within-cluster squared error the least. Balanced, roughly spherical clusters; the usual default. |
Ward in symbols. The cost of merging clusters A and B is the increase in total within-cluster sum of squares, which equals:
Δ(A, B) = ( |A|·|B| / (|A| + |B|) ) · ‖μA − μB‖²
where μ_A, μ_B are the cluster centroids and |A| the cluster size. Ward therefore prefers merging small, nearby clusters — the same objective k-means minimizes, but built bottom-up.
Distance metrics
Linkage decides how to compare two clusters; the underlying distance metric decides how to compare two points. The two choices are independent — with one caveat: Ward is defined in terms of squared Euclidean distance, so it is normally used only with the Euclidean metric.
| Metric | Formula | Typical use |
|---|---|---|
| Euclidean | √Σ(xᵢ − yᵢ)² | Continuous, geometric data (default; required for Ward) |
| Manhattan | Σ|xᵢ − yᵢ| | Grid-like / high-dimensional data; less outlier-sensitive |
| Cosine | 1 − (A·B)/(‖A‖‖B‖) | Text / sparse vectors where direction matters, not magnitude |
As with k-means, features should usually be scaled / standardized first, since a feature on a larger numeric range would otherwise dominate the distance.
Cost, and hierarchical vs k-means
The price of building the whole hierarchy is computation. A naive agglomerative implementation rescans every cluster pair each step and runs in O(n³) time. With a priority queue / nearest-neighbor structure (and special-case algorithms like SLINK for single and CLINK for complete linkage) this drops to roughly O(n² log n), while the pairwise distance matrix alone costs O(n²) memory. That makes plain hierarchical clustering impractical for very large n (hundreds of thousands of points and up).
| Aspect | Hierarchical (agglomerative) | k-means |
|---|---|---|
| Need k up front? | No — choose by cutting the dendrogram afterward | Yes — k is an input |
| Output | Full nested hierarchy (dendrogram) | One flat partition into k clusters |
| Cluster shapes | Depends on linkage — single can capture non-convex shapes | Assumes roughly spherical, similar-size clusters |
| Determinism | Deterministic (no random init) | Depends on random initialization |
| Typical cost | O(n² log n) – O(n³) | O(n · k · i · d) |
Prefer hierarchical when the dataset is small-to-medium, you do not know how many clusters exist, you want to see nested structure (taxonomies, gene-expression groups, document hierarchies), or you need a deterministic result. Reach for k-means when n is large, you have a sensible k in mind, and the clusters are roughly blob-shaped.
Key Takeaways
- Hierarchical clustering builds a tree of merges (or splits), not a single partition — so you do not have to choose k in advance.
- Agglomerative (bottom-up, merge closest clusters) is the common form; divisive (top-down, recursively split) is rarer and heuristic.
- The dendrogram's merge heights are linkage distances; cutting it at a height yields a flat clustering, and the cut height plays the role of choosing the number of clusters.
- Linkage defines cluster-to-cluster distance: single (min, chains), complete (max, compact), average (mean), and Ward (minimizes within-cluster variance, the usual default).
- The distance metric (Euclidean, Manhattan, cosine…) is a separate choice; scale your features first. Ward assumes Euclidean distance.
- Cost is roughly O(n² log n) to O(n³) with O(n²) memory, so it suits small-to-medium data; prefer k-means when n is large and k is known.