Hierarchical Clustering

K-Means asks you to decide how many clusters you want before you see the data. Hierarchical clustering does not. It builds the full merge tree — a dendrogram — that shows you every possible grouping from n individual points down to 1 giant cluster. You look at the tree, decide where to cut, and the clusters fall out. This exploratory quality makes it invaluable when you genuinely do not know how many groups exist.

---

Learning Objectives

• Explain agglomerative (bottom-up) clustering step by step
• Distinguish between linkage methods and choose the right one for the data
• Read a dendrogram and make a principled cut to select number of clusters
• Understand when hierarchical clustering is the right tool (and when it is not)
• Implement hierarchical clustering with both sklearn and scipy

---

The Core Idea: Agglomerative Clustering

Agglomerative means "building by addition." Start with every point as its own cluster. At each step, merge the two clusters that are closest together. Repeat until everything is in one cluster.

Divisive (top-down) does the reverse — start with one cluster and recursively split. It is less common in practice and computationally expensive, so we focus on agglomerative.

Step 0: [A] [B] [C] [D] [E]     — each point is a cluster
Step 1: [A,B] [C] [D] [E]       — A and B were closest
Step 2: [A,B] [C,D] [E]         — C and D were next closest
Step 3: [A,B] [C,D,E]           — merged E into nearest cluster
Step 4: [A,B,C,D,E]             — all merged

The merge order and merge distances are recorded. That record is the dendrogram.

Info

Agglomerative clustering is a greedy algorithm — at each step it makes the locally optimal merge. It cannot undo a merge, which means early mistakes persist through the tree. This is one reason the linkage method (how "distance between clusters" is defined) matters so much.

---

Linkage Methods: How to Measure Distance Between Clusters

When you merge two clusters into one, future merges depend on how you measure the distance from this new merged cluster to all remaining clusters. There are four main methods:

Linkage	Distance definition	Behaviour
single	Minimum distance between any two points across clusters	Can create long, chain-like clusters (chaining effect)
complete	Maximum distance between any two points across clusters	Produces compact, similarly-sized clusters
average	Mean distance between all pairs of points across clusters	Balanced — less sensitive to outliers than single
ward	Minimise total within-cluster variance when merging	Usually best for compact, well-separated clusters

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

X, _ = make_blobs(n_samples=20, centers=3, random_state=42)
X_scaled = StandardScaler().fit_transform(X)

fig, axes = plt.subplots(2, 2, figsize=(12, 8))
linkage_methods = ["single", "complete", "average", "ward"]

for ax, method in zip(axes.flat, linkage_methods):
    linked = linkage(X_scaled, method=method)
    dendrogram(linked, ax=ax, color_threshold=0)
    ax.set_title(f"Linkage: {method}")
    ax.set_xlabel("Sample index")
    ax.set_ylabel("Merge distance")

plt.tight_layout()
plt.savefig("linkage_comparison.png", dpi=150)
plt.show()
# Ward typically produces the most balanced, interpretable dendrogram

Tip

Start with ward linkage. It minimises variance and tends to produce compact, roughly equal-sized clusters that are easy to interpret. Use complete when you suspect outliers, since single linkage is notoriously sensitive to them (a single bridge point can chain two large clusters together).

---

Reading a Dendrogram

The dendrogram is a tree where: - Leaves (bottom): individual data points - Vertical lines: merges — the height of the join indicates how dissimilar the merged clusters were - Horizontal cut: drawing a horizontal line across the dendrogram at a given height tells you how many clusters exist at that level of similarity

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

X, true_labels = make_blobs(n_samples=30, centers=3, random_state=42, cluster_std=0.8)
X_scaled = StandardScaler().fit_transform(X)

linked = linkage(X_scaled, method="ward")

plt.figure(figsize=(10, 5))
dendrogram(linked, color_threshold=4.0, above_threshold_color="grey")
plt.axhline(y=4.0, color="red", linestyle="--", label="Cut at height 4.0 → 3 clusters")
plt.xlabel("Sample index")
plt.ylabel("Merge distance (Ward)")
plt.title("Dendrogram — cut where the vertical lines are longest")
plt.legend()
plt.tight_layout()
plt.savefig("dendrogram_with_cut.png", dpi=150)
plt.show()

# The longest vertical lines before the cut indicate the most distinct merges.
# Cut through those long lines to get the most meaningful grouping.

How to find the cut: Look for the longest vertical lines in the dendrogram — these represent the most distinct merges. Draw a horizontal cut just below the top of the longest lines. The number of vertical lines the cut crosses is the number of clusters.

Warning

Dendrograms become unreadable beyond ~100–200 samples. If you have thousands of rows, hierarchical clustering on the full dataset is both slow (O(n² log n) time, O(n²) memory) and visually uninterpretable. In that case, cluster a representative sample (~500 points) to inform k, then use K-Means on the full dataset.

---

sklearn Implementation

import pandas as pd
from sklearn.cluster import AgglomerativeClustering
from sklearn.preprocessing import StandardScaler
from sklearn.datasets import make_blobs

# Simulate customer data
X, _ = make_blobs(n_samples=200, centers=3, random_state=42)
feature_names = ["annual_spend", "purchase_frequency"]

df = pd.DataFrame(X, columns=feature_names)
X_scaled = StandardScaler().fit_transform(df)

# Fit with ward linkage — sklearn handles the clustering
model = AgglomerativeClustering(
    n_clusters=3,       # specify after inspecting dendrogram
    linkage="ward"      # use ward for compact clusters
)

df["cluster"] = model.fit_predict(X_scaled)

# Profile the clusters
profile = df.groupby("cluster").agg(
    avg_spend=("annual_spend", "mean"),
    avg_frequency=("purchase_frequency", "mean"),
    count=("annual_spend", "count")
).round(2)

print(profile)
# Output:
#          avg_spend  avg_frequency  count
# cluster
# 0            -0.83          -0.72     67   <- lower spend, lower frequency
# 1             0.91           0.87     67   <- higher spend, higher frequency
# 2            -0.01           0.01     66   <- middle group

Info

sklearn's AgglomerativeClustering requires you to specify n_clusters in advance. If you want to determine the cut from a dendrogram, use scipy's linkage and dendrogram to visualise, decide on a cut height, then pass that k to sklearn. Alternatively, use scipy's fcluster to cut by height directly.

---

Cutting the Tree by Height with scipy

from scipy.cluster.hierarchy import linkage, fcluster
from sklearn.preprocessing import StandardScaler
from sklearn.datasets import make_blobs
import pandas as pd

X, _ = make_blobs(n_samples=150, centers=4, random_state=42)
X_scaled = StandardScaler().fit_transform(X)

linked = linkage(X_scaled, method="ward")

# Cut by height — returns cluster labels
labels_by_height = fcluster(linked, t=4.0, criterion="distance")
print(f"Unique clusters from height cut: {set(labels_by_height)}")
# Output: Unique clusters from height cut: {1, 2, 3, 4}

# Or cut by specifying the number of clusters directly
labels_by_k = fcluster(linked, t=4, criterion="maxclust")
print(f"Unique clusters from k cut: {set(labels_by_k)}")
# Output: Unique clusters from k cut: {1, 2, 3, 4}

---

When to Use Hierarchical Clustering

Good fit: - Dataset has fewer than 5,000 rows (memory and speed stay manageable) - You do not know how many clusters to expect - The hierarchy itself carries meaning (e.g., gene families, product taxonomies, geographic regions) - You want to visually explore cluster structure before committing to a k

Not a good fit: - Large datasets (>10k rows) — O(n²) memory means a 50k-row dataset needs ~20 GB - When you already know k and the data is large — use K-Means instead - When clusters are non-spherical and nested — DBSCAN handles this better

Success

Hierarchical clustering's superpower is the dendrogram — it shows you the full range of possible clusterings in a single picture. Use it as an exploratory tool: inspect the tree, identify a natural cut, then confirm with silhouette score. If the data is large, use the dendrogram on a sample to inform the k for K-Means on the full dataset.

---

Comparison Table

Feature	K-Means	Hierarchical
Requires specifying k	Yes	No (cut later)
Scales to large data	Yes	No (O(n²))
Produces hierarchy	No	Yes
Cluster shape	Spherical only	More flexible (depends on linkage)
Deterministic	No (random init)	Yes
Interpretability	Centroid profiles	Dendrogram

---

---

What's Next

You've covered agglomerative clustering's bottom-up merge process, the four linkage strategies and their geometric effects, dendrogram reading and cutting, the cophenetic correlation coefficient for cluster quality, and the comparison table between K-Means and hierarchical clustering. Next up: 04-dbscan — where you'll learn the density-based algorithm that finds arbitrarily shaped clusters, natively identifies outliers as noise, and requires no k specification — the algorithm that succeeds precisely where K-Means fails.

Optional Deep Dive

Read "Data Clustering: 50 Years Beyond K-Means" by Jain (2010, available as a free PDF) — it surveys 50 years of clustering research, explains why no algorithm is universally best, and provides the theoretical grounding for understanding when K-Means, hierarchical clustering, and density-based methods each have the advantage.

← K-Means | Next: DBSCAN →