Hierarchical and Agglomerative Clustering

K-Means requires you to fix K before you start. But what if you genuinely do not know how many clusters exist? Hierarchical clustering builds a tree of nested groupings — a dendrogram — that lets you choose K after the fact by 'cutting' the tree at any level. There are two flavours: agglomerative (bottom-up, merge small clusters into larger ones) and divisive (top-down, split a big cluster into smaller ones). Scikit-learn implements agglomerative clustering, which is the most practical and widely used.

Analogy🏏Cricket

🏏 Think of it like cricket: imagine the BCCI is trying to group all Indian cricketers into natural tiers. Agglomerative clustering starts by treating each player as their own cluster. Then the two most similar players are merged — say, two technically similar opening batters. Next, the closest remaining pair merges — perhaps a third opener joins them. This continues until everyone is in one big cluster. The resulting hierarchy (dendrogram) is like a selection committee tree: at any level you can see exactly which players are in the same group and why. Cutting the tree at a certain height gives you a meaningful grouping without committing to K upfront.

Linkage Criteria — How to Measure Cluster Distances

Once individual points are merged into clusters, we need a rule for the distance between two clusters. Linkage criteria differ in which pair of points they measure. Single linkage uses the minimum distance between any point in cluster A and any point in cluster B — this produces long, chain-like clusters and is susceptible to outlier noise. Complete linkage uses the maximum distance — clusters must be close across their entire extent, producing more compact, sphere-like groups. Average linkage uses the mean of all pairwise distances — a balanced compromise. Ward linkage (the scikit-learn default) minimises the total within-cluster variance when merging — it tends to produce equally sized, compact clusters and is usually the best starting choice.

Analogy🏏Cricket

🏏 Think of it like cricket: once you start merging individual players into squads, you need a rule for how 'far apart' two squads are — and cricket offers three natural rules. Just as you might judge two academies close if even their single most-similar pair of players match, single linkage uses the minimum distance between any two points — which chains groups together and is easily fooled by one outlier player. Just as a stricter selector judges two squads close only if even their most-different players are alike, complete linkage uses the maximum distance, forcing compact groups. And just as a fair panel averages every cross-squad comparison for a balanced verdict, average linkage uses the mean distance between all pairs. Just as your choice of comparison rule changes which academies get merged first, your linkage criterion reshapes the entire cluster hierarchy — so picking the rule that matches your data's shape is what makes the merging trustworthy.

💡 Linkage rule of thumb: Ward linkage works well for most tabular datasets and is the default in scikit-learn's AgglomerativeClustering. Single linkage is best for detecting outliers or elongated chains. Complete linkage is robust to outliers. Average linkage sits between the two extremes.

Reading a Dendrogram

A dendrogram plots individual samples on the x-axis and merge height (distance at which two clusters merged) on the y-axis. Two leaves joined low on the y-axis are very similar; branches joined high indicate merges between dissimilar groups. To choose K, draw a horizontal cut line at a height where the vertical lines it crosses are long — long vertical lines indicate a big jump in merge distance, suggesting that cutting there separates genuinely different groups. The number of vertical lines the cut crosses equals K.

Analogy🏏Cricket

🏏 Think of it like cricket: a dendrogram is the tournament bracket of your players read upside down. Just as two players who tie in an early first-round match are closely matched, two leaves joined low on the y-axis are very similar. Just as a final contested only at the very top of the bracket pits two very different regions against each other, branches merged high on the axis join dissimilar groups. Just as you'd carve the tournament into 'genuinely distinct pools' by cutting where the jump between rounds is biggest — a long gap where weak sides suddenly meet strong ones, you choose K by drawing a horizontal cut across the tallest uninterrupted vertical lines, since a long line means a big leap in merge distance. Just as counting the pools below your cut tells you how many real groups exist, counting the vertical lines the cut crosses gives you K. Reading merge heights this way lets the data's own structure, not a guess, decide the number of clusters.

python

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

# Simulated player stats dataset (small for dendrogram visibility)
X, _ = make_blobs(n_samples=30, centers=3, cluster_std=0.8, random_state=42)
X = StandardScaler().fit_transform(X)

# Compute linkage matrix using Ward method
Z = linkage(X, method='ward')

# Plot dendrogram
plt.figure(figsize=(14, 5))
dendrogram(Z, leaf_rotation=90, leaf_font_size=9, color_threshold=5.0)
plt.axhline(y=5.0, color='red', linestyle='--', label='Cut line (K=3)')
plt.title('Dendrogram — Agglomerative Clustering (Ward Linkage)')
plt.xlabel('Sample index')
plt.ylabel('Merge distance')
plt.legend()
plt.tight_layout()
plt.show()

print(f"Linkage matrix shape: {Z.shape}")
print(f"Last 5 merges (height):\n{Z[-5:, 2].round(3)}")

AgglomerativeClustering in Scikit-learn

Scikit-learn's `AgglomerativeClustering` follows the standard `fit/predict` API but with one quirk: it does not implement `predict` for new points by default (it is a transductive method — it labels the training points only). If you need to assign new points, you either refit on the full dataset or use a K-Means model initialised from the agglomerative cluster centres. Key parameters are `n_clusters` (K, required unless `distance_threshold` is set), `linkage` (`ward`, `complete`, `average`, `single`), and `metric` (distance measure, defaults to `euclidean`; `ward` requires Euclidean).

Analogy🏏Cricket

🏏 Think of it like cricket: AgglomerativeClustering is a selection panel that has ranked exactly this season's squad — and only this squad. Just as it follows the usual fit routine, it obeys scikit-learn's standard fit API. But just as that panel graded the current players and has no rule ready for a brand-new trialist who walks in, it's transductive — it labels only the training points and offers no predict for new data by default. Just as you'd either re-convene the whole panel with the newcomer included, or hand the newcomer to a quicker system anchored on the existing group centres, you either refit on the full dataset or seed a K-Means model from the agglomerative centres to place new points. Just as the panel needs to be told how many final squads to form and by which comparison rule, you set n_clusters and the linkage. Knowing this transductive quirk up front saves you from expecting a predict that simply isn't there.

python

from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score
import numpy as np

# Simulated IPL player performance data
X, _ = make_blobs(n_samples=150, centers=4, cluster_std=1.0, random_state=7)
X = StandardScaler().fit_transform(X)

# Agglomerative clustering with Ward linkage
agg = AgglomerativeClustering(n_clusters=4, linkage='ward')
labels = agg.fit_predict(X)

print(f"Cluster sizes  : {np.bincount(labels)}")
print(f"Silhouette     : {silhouette_score(X, labels):.4f}")

# Compare linkage methods
for method in ['ward', 'complete', 'average', 'single']:
    if method == 'ward':
        agg_tmp = AgglomerativeClustering(n_clusters=4, linkage=method)
    else:
        agg_tmp = AgglomerativeClustering(n_clusters=4, linkage=method,
                                           metric='euclidean')
    lbl = agg_tmp.fit_predict(X)
    sil = silhouette_score(X, lbl)
    print(f"  linkage={method:8s}  →  silhouette={sil:.4f}  sizes={np.bincount(lbl)}")

Distance Threshold Mode — Letting the Data Choose K

Instead of specifying `n_clusters`, you can set `distance_threshold` and leave `n_clusters=None`. The algorithm merges clusters only up to that threshold distance, so the final number of clusters is determined by the data rather than by your choice. This is useful in exploratory analysis when you want a data-driven cut. After fitting, `agg.n_clusters_` tells you how many clusters were formed. Combine this with a dendrogram to pick a sensible threshold visually.

Analogy🏏Cricket

🏏 Think of it like cricket: instead of ordering selectors to produce exactly four squads, you give them a single rule — 'only merge two groups of players if they're closer than this cut-off.' Just as the selectors then keep combining similar players and simply stop when the next merge would force together genuinely different types, setting distance_threshold with n_clusters=None merges clusters only up to that distance and lets the final count emerge naturally. Just as the number of squads you end up with is dictated by how the talent actually clusters rather than by a quota you imposed, the data — not your guess — decides how many clusters form. Just as you'd then count the squads that resulted, agg.n_clusters_ reports how many were created. This is the exploratory move: when you genuinely don't know how many natural groups exist, let a sensible distance rule reveal it instead of pinning a number in advance.

python

from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
import numpy as np

X, _ = make_blobs(n_samples=120, centers=4, cluster_std=0.9, random_state=42)
X = StandardScaler().fit_transform(X)

# Let distance_threshold decide K
agg = AgglomerativeClustering(n_clusters=None, linkage='ward',
                               distance_threshold=4.5,
                               compute_full_tree=True)
labels = agg.fit_predict(X)
print(f"Discovered K   : {agg.n_clusters_}")
print(f"Cluster sizes  : {np.bincount(labels)}")

Comparing K-Means vs Agglomerative

K-Means is faster (O(NKI) vs O(N² log N) for agglomerative) and scales to millions of rows. Agglomerative clustering needs no K upfront, produces an interpretable dendrogram, and handles non-Euclidean distances (with average/complete linkage). For large datasets (N > 10 K), K-Means or Mini-Batch K-Means is usually preferred. For small datasets (N < 5 K) where interpretability matters, agglomerative clustering with a dendrogram often gives better insight. Agglomerative also tends to form more natural-looking clusters when the data is not globular, though DBSCAN (Lesson 27) surpasses both for non-convex shapes.

Analogy🏏Cricket

🏏 Think of it like cricket: choosing between these two is like choosing how to sort players by squad size. Just as a fast, no-nonsense coach can bucket a hundred-thousand-strong academy into K zones in one brisk sweep, K-Means runs in roughly O(NKI) and scales to millions. Just as a meticulous selector who compares every player against every other builds a beautiful, readable family tree of the squad but bogs down badly as numbers grow, agglomerative clustering costs about O(N² log N) yet needs no K upfront, yields an interpretable dendrogram, and handles non-Euclidean distances via average or complete linkage. Just as you'd send the vast national talent pool to the fast coach and reserve the careful tree-builder for a small, precious group where you must understand every merge, prefer K-Means (or Mini-Batch) above ~10K rows and agglomerative below ~5K where interpretability rules. Matching algorithm to squad size is what keeps clustering both fast and insightful.

⚠️ Agglomerative clustering is O(N² log N) in memory and time. On a dataset of 50,000 rows the full linkage matrix alone requires ~10 GB RAM. Use it only for small-to-medium datasets, or subsample large ones before building the dendrogram.

Full Worked Example: Player Archetype Discovery

python

import numpy as np
import pandas as pd
from sklearn.cluster import AgglomerativeClustering
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score
from scipy.cluster.hierarchy import dendrogram, linkage
import matplotlib.pyplot as plt

# Simulated batting + bowling features for 60 T20 players
np.random.seed(99)
n = 60
df = pd.DataFrame({
    'batting_avg':     np.random.normal(28, 12, n).clip(0),
    'strike_rate':     np.random.normal(130, 25, n).clip(60),
    'bowling_economy': np.random.normal(8.0, 2.0, n).clip(4),
    'wickets_per_game':np.random.exponential(0.8, n),
    'fielding_rating': np.random.uniform(5, 10, n),
})

# Scale
scaler = StandardScaler()
X = scaler.fit_transform(df.values)

# Dendrogram to pick K
Z = linkage(X, method='ward')
plt.figure(figsize=(16, 4))
dendrogram(Z, leaf_rotation=90, color_threshold=6)
plt.axhline(6, color='red', ls='--', label='Cut → K=4')
plt.title('Player Archetype Dendrogram'); plt.legend(); plt.tight_layout(); plt.show()

# Fit chosen K
agg = AgglomerativeClustering(n_clusters=4, linkage='ward')
df['archetype'] = agg.fit_predict(X)

print("\nMean profile per archetype:")
print(df.groupby('archetype').mean().round(2))
print(f"\nSilhouette: {silhouette_score(X, df['archetype']):.4f}")

Agglomerative clustering builds a dendrogram by iteratively merging the two closest clusters — no K needed upfront.
Ward linkage (default) minimises total within-cluster variance and is the best general-purpose choice for tabular data.
Cut the dendrogram at a height where long vertical lines are crossed — the number of lines crossed equals K.
Use `distance_threshold` instead of `n_clusters` when you want the data to determine K automatically.
Agglomerative clustering does not natively predict new points — refit on full data or use K-Means for deployment.
Prefer K-Means for datasets > 10 K rows; agglomerative clustering suits smaller exploratory analyses where dendrograms add interpretability.