← chapter

Hierarchical clustering

k-means made you pick k. This doesn't.

Build the whole tree of groupings, from every point alone to one big group — then cut it wherever the structure tells you to.

The whole algorithm

Start with every point as its own cluster. Then repeat until one is left:

Twenty-nine merges for thirty points. No k, no centroids, no seed.

The data

30 points, three blobs from make_blobs, no labels. Small on purpose — a dendrogram draws one leaf per point.

The one real choice: linkage

How far apart are two clusters? Pick a rule:

dsingle(A,B)=min⁡a∈A,  b∈B∥xa−xb∥d_{\text{single}}(A, B) = \min_{a \in A,\; b \in B} \lVert x_a - x_b \rVert dcomplete(A,B)=max⁡a∈A,  b∈B∥xa−xb∥d_{\text{complete}}(A, B) = \max_{a \in A,\; b \in B} \lVert x_a - x_b \rVert daverage(A,B)=1∣A∣ ∣B∣∑a∈A∑b∈B∥xa−xb∥d_{\text{average}}(A, B) = \frac{1}{|A|\,|B|} \sum_{a \in A} \sum_{b \in B} \lVert x_a - x_b \rVert

Single chains, complete makes tight balls, average is the safe first try.

Watch it agglomerate

Points condense on top; the dendrogram builds bar by bar below. Every frame is one real merge. Red links the two clusters fusing this step.

Low merges happen inside blobs; then the tree jumps a big gap to fuse them. That gap is where k=3 comes from — you didn't pick it, the heights announced it.

Cut the tree at k

The dendrogram, colored by the k=3 clusters, gray between-blob merges above, the cut line dropped into the empty gap (height 3.92, between 1.90 and 5.94):

Scratch vs. library

Our cut at k=3 vs sklearn.cluster.AgglomerativeClustering. Merge heights match scipy to machine epsilon; flat labels match sklearn; both recover the true blobs. Every adjusted Rand index is 1.0.

Takeaways

1 / 8