When one number of groups is the wrong question
A county library service runs 180 branches and wants to know how they group by borrowing behaviour. The planning team cannot tell you how many groups they want, because the answer depends on the decision: four types for staffing rotas, maybe a dozen for stock buying, two for a budget paper. Hierarchical clustering answers all of those at once. Instead of returning a partition, it returns a tree, and you cut the tree wherever the decision requires.
Agglomerative clustering builds the tree from the bottom. Every branch starts as its own cluster, the closest two clusters merge, and that repeats until one cluster holds everything. The sequence of merges and the distance at which each happened is the whole output, usually drawn as a dendrogram. Divisive clustering goes the other way, splitting one big cluster downwards, and is rare in practice because the splitting step is expensive.
The feature set is borrowing mix plus two intensity measures. Four kinds of branch were planted.
import numpy as np, pandas as pd
rng = np.random.default_rng(93)
def branches(n, mix, loans, members):
raw = rng.dirichlet(np.array(mix) * 55, n)
return pd.DataFrame({
"share_childrens": raw[:, 0].round(3),
"share_fiction": raw[:, 1].round(3),
"share_nonfiction": raw[:, 2].round(3),
"share_digital": raw[:, 3].round(3),
"loans_per_member": rng.normal(loans, loans * 0.2, n).clip(1).round(2),
"members_per_1k_pop": rng.normal(members, members * 0.18, n).clip(5).round(1),
})
library = pd.concat([
branches(58, [0.42, 0.30, 0.16, 0.12], 11.0, 190), # suburban family branches
branches(46, [0.12, 0.24, 0.34, 0.30], 8.5, 120), # city centre reference
branches(44, [0.20, 0.49, 0.22, 0.09], 5.5, 240), # small rural branches
branches(32, [0.09, 0.18, 0.49, 0.24], 13.5, 95), # campus-adjacent branches
], ignore_index=True)
truth = np.repeat([0, 1, 2, 3], [58, 46, 44, 32])
print(library.shape)
# (180, 6)
How hierarchical clustering decides what to merge
The distance between two single branches is easy. The distance between two groups of branches is a choice, and that choice is the linkage criterion. It changes the answer more than anything else you control.
| Linkage | Distance between clusters | Tends to produce |
|---|---|---|
single |
closest pair of members | long chains, singletons |
complete |
furthest pair of members | compact, equal-diameter groups |
average |
mean over all cross pairs | a middle course |
ward |
increase in total within-cluster variance | balanced, k-means-like groups |
Ward is the one I reach for first on numeric data, because it optimises the same variance quantity as k-means while still giving you the tree. Single linkage is worth running precisely because it fails loudly, and the failure is diagnostic.
from scipy.cluster.hierarchy import linkage, fcluster, cophenet
from scipy.spatial.distance import pdist
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import adjusted_rand_score, silhouette_score
X = StandardScaler().fit_transform(library.to_numpy())
pair = pdist(X)
for method in ["ward", "complete", "average", "single"]:
Z = linkage(X, method=method)
lab = fcluster(Z, t=4, criterion="maxclust")
sizes = np.bincount(lab)[1:]
print(f"{method:9s} cophenetic={cophenet(Z, pair)[0]:.3f} "
f"ARI={adjusted_rand_score(truth, lab):.3f} "
f"sizes={sorted(sizes.tolist(), reverse=True)}")
# ward cophenetic=0.850 ARI=0.904 sizes=[57, 53, 45, 25]
# complete cophenetic=0.842 ARI=0.788 sizes=[55, 47, 44, 34]
# average cophenetic=0.858 ARI=0.894 sizes=[57, 54, 45, 24]
# single cophenetic=0.794 ARI=0.494 sizes=[100, 78, 1, 1]
Single linkage asked for four groups and produced two large ones plus two clusters containing a single branch each. This is chaining: a thin bridge of intermediate branches lets two genuinely different groups merge early, because only the closest pair of members counts, and the only thing left to split off at the top are isolated outliers. If a linkage returns singletons where you asked for groups, you are looking at chaining and not at an insight.
The cophenetic correlation is worth a closer look, because it is the index usually recommended for picking a linkage. It measures how well the merge heights in the tree reproduce the original pairwise distances. Average linkage scored highest at 0.858, yet Ward recovered the planted structure best at 0.904 against average linkage’s 0.894. The index that is supposed to choose your linkage chose the wrong one, by a small margin, on data where the right answer is known. Treat it as weak evidence rather than a verdict, exactly as with the internal indices in how clustering results are judged without labels.
Reading the dendrogram and cutting it
The merge heights are in the third column of the linkage matrix. Large gaps between consecutive heights are the honest version of the elbow heuristic you met in choosing k for k-means: a big jump means the next merge joined two groups that were far apart, so the structure below the jump is the natural one.
Z = linkage(X, method="ward")
print("last six merge heights:", np.round(Z[-6:, 2], 2))
print("gap before the final merge:", round(Z[-1, 2] - Z[-2, 2], 2))
# last six merge heights: [ 5.25 5.86 6.04 12. 18.63 34.34]
# gap before the final merge: 15.71
for t in [4.0, 6.0, 9.0, 13.0]:
lab = fcluster(Z, t=t, criterion="distance")
print(f"cut at height {t:>4}: {lab.max()} clusters, "
f"ARI={adjusted_rand_score(truth, lab):.3f}")
# cut at height 4.0: 12 clusters, ARI=0.435
# cut at height 6.0: 5 clusters, ARI=0.760
# cut at height 9.0: 4 clusters, ARI=0.904
# cut at height 13.0: 3 clusters, ARI=0.770
Three merges happen between heights 5.25 and 6.04, then nothing until 12. That flat stretch followed by a jump is where the four-group structure lives, and cutting at 9 recovers it. The same tree cut lower gives twelve groups for a stock buyer and cut higher gives three for a budget paper, with no refitting.
Scikit-learn exposes the same algorithm with a distance_threshold argument, which is the API to use if hierarchical clustering sits inside a pipeline with scaling and selection steps.
from sklearn.cluster import AgglomerativeClustering
model = AgglomerativeClustering(n_clusters=None, distance_threshold=9.0,
linkage="ward").fit(X)
print("clusters found:", model.n_clusters_)
print("silhouette:", round(silhouette_score(X, model.labels_), 3))
# clusters found: 4
# silhouette: 0.412
The cost that stops you
The tree needs every pairwise distance, and that is where the method runs out of road.
for n in [180, 5_000, 50_000]:
pairs = n * (n - 1) // 2
print(f"n={n:>6} pairwise distances={pairs:>14,} "
f"float64 memory={pairs * 8 / 1e9:.2f} GB")
# n= 180 pairwise distances= 16,110 float64 memory=0.00 GB
# n= 5000 pairwise distances= 12,497,500 float64 memory=0.10 GB
# n= 50000 pairwise distances= 1,249,975,000 float64 memory=10.00 GB
Ten gigabytes for fifty thousand rows, before any of the merging work. My rule is that under roughly twenty thousand rows this method is comfortable, and above that you either sample, cluster the sample, and assign the rest by nearest centroid, or you switch to a method that never materialises the distance matrix. Ward linkage in scikit-learn can also take a sparse connectivity matrix, which restricts merges to neighbouring rows and cuts the cost sharply when your data has a spatial or temporal adjacency to exploit. The implementation details are in the SciPy linkage reference.
One more property to keep in mind: merges are never reconsidered. Once two branches are joined the algorithm cannot separate them, so an early mistake propagates all the way to the root. That greediness is the price of getting a whole tree out of one fit, and it is why standardising the columns first matters as much here as it does anywhere else in distance-based grouping.
Frequently Asked Questions
Which linkage should I use by default?
Ward, for numeric features on a comparable scale, because it optimises within-cluster variance and produces balanced groups. Switch to average or complete linkage when you are working from a precomputed distance matrix that is not Euclidean, since Ward is only defined for Euclidean distances.
How do I pick where to cut the dendrogram?
Look for the largest gap between consecutive merge heights and cut inside it. On the library data three merges clustered around height 6 and the next one jumped to 12, which pointed straight at four groups. Then sanity-check that the resulting group sizes are usable.
Is hierarchical clustering better than k-means?
Different, not better. It gives you every level of granularity from one fit and handles non-spherical shapes a little more gracefully, but it costs quadratic memory and cannot revise a bad early merge. On large tabular datasets k-means remains the practical default.
Key Takeaways
- Hierarchical clustering returns a tree rather than a partition, so one fit answers the staffing question, the buying question and the budget question at different cut heights.
- The linkage criterion is the most consequential setting; Ward recovered the planted library structure at 0.904 while single linkage managed 0.494 and returned two singleton clusters.
- Singletons where you asked for groups mean chaining, which is a diagnostic about your data rather than a result to interpret.
- Cut the dendrogram inside the largest gap between consecutive merge heights, and check the cophenetic correlation only as weak supporting evidence, since it preferred average linkage here when Ward was the better fit.
- Budget for quadratic memory before you start, because fifty thousand rows need ten gigabytes just to hold the distances.