Hierarchical Clustering

Why Does This Exist?

A seed bank holds 48 wheat varieties measured on grain length, protein, and disease scores. The curator does not want six groups. The question is which varieties are close relatives, which stand alone, and where two families stop being one family.

That is structure at every scale. K-means hands you one flat partition at the $k$ you picked before looking. Hierarchical clustering hands you every $k$ from 48 down to 1 in one tree, so you choose the count after seeing the gaps.

Two ideas make the rest click. A distance is one number saying how unlike two varieties are. A dendrogram is the recorded history: varieties along the bottom, one horizontal bar wherever two groups joined, and the bar height recording how far apart they were. This page covers the merging fix. How to score the result once you cut lives in clustering evaluation. The density alternative that labels stragglers as noise lives in DBSCAN.

Think of It Like This

How It Actually Works

Agglomerative clustering is the version people run. Start with $n$ clusters of one point each. Find the two closest clusters, merge them, and write down the distance $h$ they merged at. Repeat until one cluster is left. That gives $n - 1$ merges and $n - 1$ heights, and those heights are the whole output.

Because every step was kept, you choose $k$ afterwards. Draw a horizontal line across the tree at height $h$. The vertical lines it crosses count your clusters, and the groups below them are your answer. Lower for more, higher for fewer, from one fitted model.

Worked example: four points on a line

Put four points at $0$, $1$, $5$, and $6$. Call them $A$, $B$, $C$, $D$. Pairwise gaps are $AB = 1.0$, $CD = 1.0$, $BC = 4.0$, $AC = 5.0$, $BD = 5.0$, and $AD = 6.0$.

First merge: the closest pair is $1.0$. Both $AB$ and $CD$ sit at $1.0$, so $A$ joins $B$ at height $1.0$ and $C$ joins $D$ at height $1.0$. Two clusters remain: $\{A, B\}$ and $\{C, D\}$.

Second merge under single linkage, which uses the closest cross-pair:

The two pairs join at height $4.0$. A cut at any height between $1.0$ and $4.0$ crosses exactly two vertical lines, so it returns two clusters: $\{A, B\}$ and $\{C, D\}$. The empty band from $1.0$ to $4.0$ is $3.0$ tall with no merges, and that emptiness is the evidence the cut is real.

Linkage decides what closest means for groups

Closest is unambiguous for two single points and ambiguous the moment a cluster holds more than one. The rule you pick is the linkage criterion.

Single linkage uses the closest cross-pair and follows thin filaments. It chains distinct groups together through any bridge of intermediate points. Complete linkage uses the farthest cross-pair. On our four points that is $\max(5.0, 6.0, 4.0, 5.0) = 6.0$, so the final merge sits at $6.0$ instead of $4.0$. It favours compact round clusters and splits a long real group in half. Average linkage uses the mean over all cross-pairs, here $(5.0 + 6.0 + 4.0 + 5.0) / 4 = 5.0$, and sits between the two. Ward method uses no pair distance at all and merges whichever two clusters raise total within-cluster variance least, which makes it the closest relative of k-means on this page.

Reading the tree without fooling yourself

Merge height carries all the information. A long stretch of empty vertical space below a bar means those groups had nothing between them, so cut there. Horizontal position carries none. Every bar can flip left to right without changing a merge or a height, so two leaves drawn side by side may have joined only at the root.

The bill is quadratic. Every pair needs a distance, so $n$ rows need about $n^2 / 2$ values. Forty-eight varieties are nothing. A million rows do not fit.

Code

The point is the heights: same four points, three rules, three different final merges.

1def gap(a: float, b: float) -> float:2    return abs(a - b)3
4pts: dict[str, float] = {"A": 0.0, "B": 1.0, "C": 5.0, "D": 6.0}5pairs: dict[str, float] = {6    "AB": gap(pts["A"], pts["B"]),7    "CD": gap(pts["C"], pts["D"]),8    "BC": gap(pts["B"], pts["C"]),9    "AC": gap(pts["A"], pts["C"]),10    "BD": gap(pts["B"], pts["D"]),11    "AD": gap(pts["A"], pts["D"]),12}13cross: list[float] = [pairs["AC"], pairs["AD"], pairs["BC"], pairs["BD"]]14print(pairs["AB"], pairs["CD"])  # -> 1.0 1.015print(min(cross))  # -> 4.016print(sum(cross) / len(cross))  # -> 5.017print(max(cross))  # -> 6.0

The printout matches the hand computation: both tight pairs merge at $1.0$, then single linkage joins the pairs at $4.0$, average at $5.0$, and complete at $6.0$. Change $C$ from $5.0$ to $2.5$ and watch the gap between $1.0$ and the final merge shrink from $3.0$ to $1.5$.

Watch Out For

The Quick Version

• Every point starts alone. Merge the two closest groups, record the height, and repeat until one group is left.
• The output is a tree, not a partition. A horizontal cut at height $h$ chooses the cluster count after fitting.
• Linkage decides the answer on our four points: single linkage finishes at 4.0, average at 5.0, and complete at 6.0.
• Merge height carries all the information. A 3.0 tall empty band between 1.0 and 4.0 is the evidence for cutting there.
• Leaf order carries none. Any bar can flip without changing the history.
• The distance matrix grows with the square of the row count, so this stops being practical past tens of thousands of rows.

What to Read Next

• K-Means
• DBSCAN
• Clustering Evaluation: Scores Without Labels