Hierarchical Clustering

Think of how biologists organise life. Species join into families, families join into orders, and so on, in one great tree. Hierarchical clustering does the same for your data. It gives you a whole family tree, and lets you cut it at whatever level you like.

• Species, families, orders
• A tree of your data
• Cut it at any level

Reading a dendrogram

The method starts with every point as its own group. Then it repeatedly merges the two closest groups, until only one remains. A chart called a dendrogram shows the entire history. Run it. Each join shows two groups merging, and its height shows how far apart they were. Look for the long vertical stems, where a big jump happens. Cutting across there gives you natural groups. Here, there are three clear branches.

import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram, linkage
from sklearn.datasets import make_blobs

X, _ = make_blobs(n_samples=40, centers=3, cluster_std=0.8, random_state=2)

plt.figure(figsize=(10, 4.5))
dendrogram(linkage(X, method="ward"), no_labels=True, color_threshold=8)
plt.ylabel("Distance when merged")
plt.tight_layout()
plt.savefig("dendrogram.png", dpi=120)
print("Merges performed:", len(X) - 1)

Merges performed: 39

Linkage matters

How do we measure the distance between two groups? This choice is called linkage. Ward merges the pair that adds the least variance. Average uses the mean distance. And single uses the closest two points. We compare each to the true groups. An adjusted rand score of one means a perfect match. Run it. Ward and average match the truth almost perfectly, while single linkage does badly, because it chains groups together. Ward is usually the safest default.

import numpy as np
from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_blobs
from sklearn.metrics import adjusted_rand_score

X, truth = make_blobs(n_samples=300, centers=3, cluster_std=0.8, random_state=2)

for link in ["ward", "average", "single"]:
    labels = AgglomerativeClustering(n_clusters=3, linkage=link).fit_predict(X)
    print(f"{link:<8} match with truth {adjusted_rand_score(truth, labels):.3f}")

ward     match with truth 0.990
average  match with truth 0.990
single   match with truth 0.560

Summary