Module 4 — Hierarchical clustering and dendrograms

k-means forced you to choose $k$ before seeing anything at all. Hierarchical clustering reverses the order: it first builds the entire tree of possible groupings, and you then decide where to cut it. You see the structure before committing — a considerable advantage in exploration.

The agglomerative principle: merging step by step

The dominant approach starts at the finest level and works upward:

1. each observation forms its own cluster;
2. the two nearest clusters are merged;
3. repeat until a single cluster contains everything.

The complete history of these merges — who joined whom, and at what distance — forms a tree: the dendrogram. Nothing is decided during construction; every granularity coexists in the tree.

The linkage criterion: the decision that changes everything

"The two nearest clusters" requires defining the distance between two clusters, not two points. This choice, the linkage criterion, determines the shape of the resulting clusters far more than anything else.

Criterion	Distance between clusters	Tendency
single linkage	between their two closest points	follows elongated shapes, but causes chaining
complete linkage	between their two farthest points	compact clusters, sensitive to outliers
average linkage	average over all pairs	balanced compromise
Ward	increase in inertia caused by the merge	homogeneous clusters of comparable size

Ward is the reasonable default: by minimizing the increase in inertia at each merge, it pursues the same compactness objective as k-means, with often similar results but accompanied by the full tree. Single linkage is the most distinctive: able to follow stretched shapes, it suffers from the chaining effect, where two distinct clusters end up linked by a thin bridge of intermediate points.

from scipy.cluster.hierarchy import linkage, dendrogram, fcluster

Z = linkage(X_s, method="ward")
dendrogram(Z, truncate_mode="lastp", p=30)   # readable tree on large volumes
groupes = fcluster(Z, t=4, criterion="maxclust")   # cut into 4 clusters

Reading a dendrogram and choosing the cut

On the dendrogram, each merge is a horizontal bar whose height indicates the distance at which it occurred. That is where the information lies: a very high merge means two clusters that were far apart have been joined — hence, in all likelihood, two genuinely distinct structures.

Hence the reading rule: cut the tree just below a large vertical jump. The branches thus separated correspond to well-distinguished clusters, and the number of cut branches gives $k$. This visual reading is the counterpart of module 3's elbow method, with one asset: you see every possible granularity at once, and the nesting of clusters (segments and sub-segments) reads directly.

Strengths, cost, and complementarity with k-means

The main asset is therefore exploration: no imposed $k$, a rich visualization, and the hierarchy of sub-clusters as a bonus. Add to that flexibility: hierarchical clustering accepts any distance matrix, including non-Euclidean ones — useful for text data or sequences, where k-means requires a computable mean.

The price is the computational cost, quadratic in both memory and time: beyond a few tens of thousands of observations, the distance matrix becomes impractical. Another fundamental difference: a merge is final, never revisited, whereas k-means reassigns points at every iteration.

The pairing that works in practice

On a large dataset, the effective approach combines both: hierarchical clustering on a sample of a few thousand points to read the structure and estimate $k$ from the dendrogram, then k-means with that $k$ on the full data. You get the readability of one and the processing capacity of the other.

Summary

• The agglomerative approach merges the nearest clusters step by step and produces a complete tree: the dendrogram.
• The linkage criterion decides cluster shape; Ward is the reasonable default, single linkage follows elongated shapes but chains.
• You choose $k$ by cutting below a large vertical jump in the dendrogram; every granularity and the nesting read at a glance.
• Excellent for exploration and compatible with any distance matrix, but quadratic cost and irreversible merges.

Next module: DBSCAN, which abandons the notion of a center to detect clusters of arbitrary shape and isolate noise.