Hierarchical Clustering

Hierarchical clustering is an unsupervised machine learning algorithm that groups data points into a tree of nested clusters — without requiring you to specify the number of clusters upfront. This page explains how the algorithm works, the difference between agglomerative and divisive approaches, how to choose a linkage method, and how to implement and visualize hierarchical clustering in Python using both scikit-learn and SciPy.

What is Hierarchical Clustering?

Hierarchical clustering builds a hierarchy of clusters by iteratively merging or splitting groups of data points based on a distance (or similarity) measure. The result is represented as a dendrogram — a tree-like diagram where the y-axis shows the distance at which clusters are merged and the leaves represent individual data points.

Unlike K-Means, hierarchical clustering does not require you to choose the number of clusters before running the algorithm. You run the algorithm once and then "cut" the dendrogram at a chosen distance threshold to produce any number of clusters.

When to use hierarchical clustering

Use hierarchical clustering when:

• You do not know the number of clusters in advance and want to explore several options from a single run.
• Your dataset is small-to-medium sized (thousands of rows, not millions) — the algorithm's O(n²) memory cost makes it impractical for very large datasets.
• You need interpretable cluster relationships (the dendrogram reveals the merging history clearly).
• Your clusters may not be spherical — hierarchical methods with complete or average linkage handle non-globular shapes better than K-Means.

Agglomerative vs Divisive Clustering

There are two main strategies:

This page focuses on agglomerative clustering, which is what most practitioners mean when they say "hierarchical clustering."

How the Algorithm Works

Agglomerative clustering follows these steps:

1. Treat each of the n data points as its own cluster (n clusters total).
2. Compute the distance matrix — the pairwise distances between all clusters.
3. Merge the two clusters with the smallest distance into one new cluster.
4. Update the distance matrix to reflect the new cluster.
5. Repeat steps 3–4 until only one cluster remains.

The final output is a dendrogram encoding all n-1 merge steps.

Linkage Methods

The linkage method controls how the distance between two clusters is computed at each merge step. The choice significantly affects the shape and quality of the clusters.

Ward linkage is the most widely used starting point. If your clusters are elongated or non-convex, try average or single linkage.

Feature Scaling Before Clustering

Because hierarchical clustering relies on distance calculations, features with large numeric ranges dominate the distance matrix and skew the results. Always scale your features first.

from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

StandardScaler centers each feature to mean 0 and unit variance. See the Scale chapter for alternatives such as MinMaxScaler and RobustScaler.

Implementing Hierarchical Clustering with scikit-learn

The AgglomerativeClustering class in scikit-learn fits the model and assigns cluster labels in one step. It does not produce a dendrogram — use SciPy (shown in the next section) for that.

Step 1 — Generate and scale data

from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler

# 150 points in 3 natural clusters
X, y_true = make_blobs(n_samples=150, centers=3, cluster_std=0.6, random_state=42)

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

make_blobs creates a reproducible synthetic dataset, so this example runs without any CSV file.

Step 2 — Fit agglomerative clustering

from sklearn.cluster import AgglomerativeClustering

hc = AgglomerativeClustering(n_clusters=3, linkage='ward')
labels = hc.fit_predict(X_scaled)

print(labels[:10])
# e.g. [2 2 0 1 0 1 2 2 0 1]

fit_predict both fits the model and returns the cluster label (0, 1, or 2) for every data point in a single call.

Step 3 — Visualize the clusters

import matplotlib.pyplot as plt

colors = ['red', 'blue', 'green']
for cluster_id in range(3):
    mask = labels == cluster_id
    plt.scatter(X_scaled[mask, 0], X_scaled[mask, 1],
                s=60, label=f'Cluster {cluster_id + 1}')

plt.title('Agglomerative Clustering (Ward linkage, k=3)')
plt.xlabel('Feature 1 (scaled)')
plt.ylabel('Feature 2 (scaled)')
plt.legend()
plt.tight_layout()
plt.show()

Dendrograms with SciPy

The dendrogram is hierarchical clustering's most distinctive output. It lets you visually choose the number of clusters by cutting the tree at different heights. SciPy's scipy.cluster.hierarchy module provides both linkage (to build the tree) and dendrogram (to plot it).

Building and plotting a dendrogram

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

# Use a smaller dataset so the dendrogram is readable
X, _ = make_blobs(n_samples=30, centers=3, cluster_std=0.6, random_state=42)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# Build the linkage matrix
Z = linkage(X_scaled, method='ward')

# Plot
plt.figure(figsize=(12, 5))
dendrogram(Z, leaf_rotation=90, leaf_font_size=8)
plt.title('Dendrogram (Ward linkage)')
plt.xlabel('Sample index')
plt.ylabel('Merge distance')
plt.tight_layout()
plt.show()

Reading the dendrogram

• Leaves (bottom) represent individual data points.
• Horizontal lines represent merges. The height of a line equals the distance between the two clusters being merged.
• Cutting the tree at a given height gives you the number of clusters below that cut.

To choose k, look for the tallest vertical line that is not crossed by a horizontal line — that gap suggests the most natural number of clusters.

Cutting the dendrogram to assign labels

After building the linkage matrix Z, use fcluster to cut the tree at a desired number of clusters:

from scipy.cluster.hierarchy import linkage, fcluster
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
import numpy as np

X, _ = make_blobs(n_samples=150, centers=3, cluster_std=0.6, random_state=42)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

Z = linkage(X_scaled, method='ward')

# Cut the tree to get exactly 3 clusters
labels = fcluster(Z, t=3, criterion='maxclust')

print('Unique cluster IDs:', np.unique(labels))   # [1 2 3]  (1-indexed)
print('Sizes:', np.bincount(labels[labels > 0]))   # [50 50 50]

Note that fcluster labels are 1-indexed (start at 1), unlike scikit-learn's 0-indexed labels.

Comparing Linkage Methods

The linkage method changes the cluster shapes and sizes significantly. Here is how to compare all four methods on the same dataset:

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

X, _ = make_blobs(n_samples=150, centers=3, cluster_std=0.6, random_state=42)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

methods = ['ward', 'complete', 'average', 'single']
fig, axes = plt.subplots(1, 4, figsize=(16, 4))

for ax, method in zip(axes, methods):
    hc = AgglomerativeClustering(n_clusters=3, linkage=method)
    labels = hc.fit_predict(X_scaled)
    ax.scatter(X_scaled[:, 0], X_scaled[:, 1], c=labels, cmap='Set1', s=30)
    ax.set_title(f'{method.capitalize()} linkage')
    ax.set_xticks([])
    ax.set_yticks([])

plt.suptitle('Linkage method comparison (k=3)', y=1.02)
plt.tight_layout()
plt.show()

Hierarchical Clustering vs K-Means

Use hierarchical clustering for exploratory analysis on smaller datasets; switch to K-Means (or DBSCAN) when you have millions of rows or already know the number of clusters.

Common Pitfalls

Forgetting to scale features. Without feature scaling, a feature measured in thousands (e.g., income) dominates one measured in single digits (e.g., age rating), producing misleading clusters.

Using Ward linkage with non-Euclidean distances. Ward linkage is only valid with Euclidean distance. For other distance metrics (e.g., cosine, Manhattan), use complete or average linkage and pass metric= explicitly.

Interpreting dendrograms on very large datasets. A dendrogram with 10 000 leaves is unreadable. Use p= and truncate_mode='lastp' in SciPy's dendrogram() to show only the last p merges.

Treating cluster IDs as stable. Cluster IDs (0, 1, 2) are arbitrary labels. After comparing two runs, match clusters by content, not by number.

Conclusion

Hierarchical clustering is a flexible, interpretable algorithm that does not require choosing k upfront. You build the full dendrogram once and then cut it at any level. Ward linkage with StandardScaler preprocessing is the safest default. For very large datasets, prefer K-Means for performance.

Related chapters:

• Scale — why and how to standardize features before clustering
• K-Means — the flat clustering alternative for large datasets
• SciPy Tutorial — more on the SciPy scientific computing library
• Scatter Plot — visualizing multi-dimensional data with Matplotlib