Hierarchical Clustering

By the end of this lesson, you will understand how hierarchical clustering builds a tree of nested clusters and be able to implement it using Python's scikit-learn library.

What it is

Hierarchical clustering is an unsupervised learning method that builds a hierarchy of clusters. Unlike K-Means, which requires you to specify the number of clusters beforehand, hierarchical clustering creates a tree-like structure called a dendrogram. This allows you to visualize relationships between data points at various levels of granularity. The two main approaches are agglomerative (bottom-up), where each point starts as its own cluster and pairs merge successively, and divisive (top-down), where all points start in one cluster and splits occur recursively. Agglomerative is far more common in practice. Key terms include linkage criteria (how distance between clusters is calculated) and cut height (where you slice the dendrogram to form final clusters).

Why it matters

• No need to pre-specify K: You can explore different numbers of clusters after fitting the model.
• Interpretability: The dendrogram provides a visual summary of the data structure and similarities.
• Flexibility with shapes: It can capture non-spherical cluster structures better than centroid-based methods like K-Means.
• Small datasets: It performs exceptionally well on smaller datasets where computational cost is manageable.

Syntax or steps

The process involves three main steps: 1. Compute Distance Matrix: Calculate pairwise distances between all samples. 2. Linkage: Merge the closest pair of clusters based on a linkage criterion (e.g., Ward, Complete, Average). 3. Cut: Stop merging when a desired number of clusters is reached or a specific distance threshold is met. In code, we typically use `AgglomerativeClustering` from `sklearn.cluster`. We define the `n_clusters` parameter to determine how many groups to extract from the hierarchy.

Example

import numpy as np
from sklearn.cluster import AgglomerativeClustering
import matplotlib.pyplot as plt

# Generate sample data
np.random.seed(42)
X = np.vstack([
    np.random.randn(50, 2) + [2, 2],
    np.random.randn(50, 2) + [-2, -2],
    np.random.randn(50, 2) + [2, -2]
])

# Initialize and fit the model
clustering = AgglomerativeClustering(n_clusters=3, linkage='ward')
labels = clustering.fit_predict(X)

# Visualize results
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', s=50)
plt.title("Hierarchical Clustering Result")
plt.show()

Explanation: We create three distinct blobs of data. The `AgglomerativeClustering` object is initialized with `n_clusters=3`, telling the algorithm to stop merging once three clusters remain. The `linkage='ward'` minimizes the variance within merged clusters, often producing compact, spherical clusters. `fit_predict` returns an array of integer labels corresponding to the cluster assignment for each data point.

Common mistakes

• Ignoring scalability: Hierarchical clustering has O(N^3) complexity (or O(N^2 log N) with optimizations). Do not use it on datasets with tens of thousands of points without subsampling.
• Choosing inappropriate linkage: 'Single' linkage can cause chaining effects where distant points join prematurely. 'Ward' is generally safer for spherical clusters, while 'Average' is robust for general cases.
• Forgetting normalization: If features have different scales, distance calculations will be biased toward larger-scale features. Always scale your data before clustering.
• Over-interpreting the dendrogram: The vertical axis represents distance, not cluster quality. A large jump in distance suggests a natural split, but small variations may be noise.

When to use it

Compare hierarchical clustering with K-Means to choose the right tool.

Feature	Hierarchical Clustering	K-Means
Data Size	Small to Medium (< 10k)	Large (Millions)
Cluster Shape	Arbitrary / Non-spherical	Spherical / Convex
Parameter Tuning	Flexible (cut later)	Rigid (must know K)
Speed	Slow	Fast

Use hierarchical clustering when you need to explore data structure visually or when K is unknown. Use K-Means for speed and large datasets with clear spherical boundaries.

Practice

Guided Exercise: Modify the example above to use `linkage='average'` instead of `'ward'`. Observe if the cluster boundaries change. Challenge: Implement a simple dendrogram visualization using `scipy.cluster.hierarchy.dendrogram` on the same dataset. Hint: You will need to compute the linkage matrix first using `scipy.cluster.hierarchy.linkage`.

Quick check

Question: Why is feature scaling critical before applying hierarchical clustering? Answer: Because hierarchical clustering relies on distance metrics (like Euclidean). If one feature has a much larger range than others, it will dominate the distance calculation, skewing the resulting clusters regardless of the other features' importance.

Summary

Hierarchical clustering builds a tree of merges, offering flexibility in determining cluster count post-analysis. While computationally expensive for large datasets, it provides valuable insights into data structure through dendrograms and handles complex cluster shapes effectively.