Intermediate 13 min read Clustering

Hierarchical Clustering

A family tree of clusters

Agglomerative clustering merges the closest groups bottom-up into a dendrogram — no k needed upfront, giving nested cluster views and a fully interpretable merge history.

hierarchical clusteringagglomerativedendrogramlinkagenestedWard

Prerequisites: Clustering Basics

Before we start

What you will learn

Explain bottom-up merging and the dendrogram cut
Contrast single/complete/average/Ward linkage
Read a dendrogram to pick a k and detect outliers

Introduction

What is this?

Agglomerative clustering starts with each row its own cluster and repeatedly merges the two closest clusters per a linkage rule: single (min distance), complete (max), average (mean), Ward (minimum-variance). Output is a dendrogram — a merge tree you can cut at any height to get the clustering for that k, which makes the nesting visible and the choice of k a decision, not a mystery.

Motivation

Why do you need it?

The dendrogram explains WHY a partition was chosen — great for stakeholder reviews.
Nested outputs let you show 3, 5, or 9 clusters from ONE hierarchy.
Ward's variance criterion is statistically clean for numeric features.
It's the conceptual bridge to phylogenetics, org trees and taxonomy tools.

Think about it

Mental model

Imagine

Building a family tree bottom-up until one ancestor tops it

Think of

Agglomerative merging

Start with individuals; join the closest kin pairs; keep joining until one family tree dominates. Each merger's height = how similar the two branches were. Cut the tree short and you keep more, smaller families.

Mechanics

How it works

Compute pairwise distances (usually Euclidean).
For each row: a singleton cluster; pick link rule; find the two clusters with min linkage
Merge and recompute linkage distances (Lance-Williams updates).
Repeat until one cluster remains; record merge heights in a dendrogram.
Cut the dendrogram at the desired height/k to produce the partition.

Merge tree (dendrogram) and cut.

Singletonsn leaves

Mergenearest pair by linkage

Heightsmerge distance recorded

Cutchoose k by height / knee

Hands-on

Examples

Dendrogram heights reveal k

import numpy as np
from scipy.cluster.hierarchy import linkage, fcluster
from sklearn.preprocessing import StandardScaler
 
rng = np.random.RandomState(0)
X = StandardScaler().fit_transform(np.vstack([
    rng.normal([0, 0], 0.3, (40, 2)),
    rng.normal([4, 4], 0.3, (40, 2)),
    rng.normal([8, 0], 0.3, (40, 2)),
]))
 
Z = linkage(X, method="ward")
print("top-3 merge heights:", np.round(Z[-3:, 2], 3))
 
for k in [3, 6, 12]:
    lab = fcluster(Z, k, criterion="maxclust")
    print(f"k={k:>2} sizes:", np.bincount(lab).tolist())

The three tallest merge heights mark the three true blobs; cutting below preserves more, smaller clusters — the nesting that a single k can't show.

Real world

In production

Org/channel taxonomy: hierarchy reviews let execs see sub-segments under each macro group.
Gene/trait trees: nested grouping is the domain-natural output.
Anomaly triage: short merge branches identify exotic singletons that never join naturally.

Guidelines

Best practices

Scale features; prefer Ward for numeric variance-sensible merges; read the dendrogram, not just maxclust numbers; beware O(n^2) memory on large n — cap or sample.

Watch out

Common mistakes

Single linkage chain-building (long chains instead of shapes); equating dendrogram branch length with cluster 'size'; using correlation-based 'distances' without scaling; memory blow-ups at n in the 100ks.

When things break

Debugging tips

A chain of points (single-link) => switch to complete/Ward.
Two clusters always merging late => real separation; early merges = noise.
Cut heights inconsistent with business intent => inspect the dendrogram, don't force k.

Interviews

Interview checkpoint

Test yourself

Quick quiz

0/2

The final k is chosen on a dendrogram by:

Ward's linkage minimizes:

Go deeper

Official documentation

AgglomerativeClustering (sklearn)

docs

scipy.cluster.hierarchy linkage/fcluster