Agglomerative Clustering

By the end of this lesson, you will be able to implement agglomerative clustering in Python using scikit-learn and understand how different linkage criteria affect cluster formation.

What it is

Agglomerative clustering is a hierarchical clustering method that builds clusters from the bottom up. It starts by treating every data point as its own individual cluster. Then, it iteratively merges the two closest clusters until a stopping criterion is met (usually a specific number of clusters). The result can be visualized as a dendrogram, a tree-like diagram showing the sequence of merges. Key related terms include linkage (the rule for measuring distance between clusters) and dendrogram.

Why it matters

• No need to specify K initially: Unlike K-Means, you don't always need to guess the number of clusters beforehand; you can inspect the dendrogram to decide where to cut.
• Handles non-spherical shapes: Depending on the linkage, it can identify clusters with irregular geometries that K-Means might miss.
• Deterministic results: Given the same input and parameters, the algorithm produces the exact same output every time, unlike K-Means which depends on random initialization.
• Interpretability: The hierarchy provides insight into the relationships between data points at multiple levels of granularity.

Syntax or steps

The core workflow involves importing the class, defining the number of desired clusters (n_clusters) and the linkage method, then fitting the model to your data. The most common linkage methods are:

1. Single: Minimum distance between any two points in the clusters. Can lead to "chaining."
2. Complete: Maximum distance between any two points. Produces compact clusters.
3. Average: Mean distance between all pairs of points. A good compromise.
4. Ward: Minimizes the variance increase when merging. Requires Euclidean distances.

Example

from sklearn.cluster import AgglomerativeClustering
import numpy as np

# Define simple 2D data points
X = np.array([[1, 1], [2, 1], [5, 5], [6, 5]])

# Initialize the model
# n_clusters=2 means we stop merging when we have 2 groups left
# linkage='ward' minimizes within-cluster variance
model = AgglomerativeClustering(n_clusters=2, linkage='ward')

# Fit and predict labels
labels = model.fit_predict(X)

print(labels)
# Output: [0 0 1 1]
# Points [1,1] and [2,1] form Cluster 0
# Points [5,5] and [6,5] form Cluster 1

Explanation: 1. We create an array X with four points. Two are close together near (1,1), and two are close together near (5,5). 2. We instantiate AgglomerativeClustering. Setting n_clusters=2 tells the algorithm to perform merges until only two distinct groups remain. 3. fit_predict(X) runs the algorithm and returns an array of integer labels corresponding to each row in X. 4. The output confirms that the first two points share label 0 and the last two share label 1.

Common mistakes

• Ignoring scale: Agglomerative clustering relies heavily on distance metrics. If features have different scales (e.g., age vs. income), normalize your data first using StandardScaler.
• Choosing Ward incorrectly: The ward linkage assumes Euclidean distance. Do not use it with cosine similarity or other non-Euclidean metrics unless explicitly supported by newer versions.
• Computational cost: This algorithm has $O(N^3)$ complexity (or $O(N^2)$ with optimizations). It becomes very slow for datasets with more than ~10,000 samples. Use DBSCAN or Mini-Batch K-Means for large data.
• Over-interpreting single linkage: Single linkage often creates long, thin chains of clusters due to outlier sensitivity. Avoid it if your data contains noise.

When to use it

Compare agglomerative clustering with K-Means, the most common alternative.

Feature	Agglomerative Clustering	K-Means
Scalability	Poor (slow on large N)	Excellent (fast on large N)
Cluster Shape	Flexible (depends on linkage)	Spherical only
Initialization	Deterministic	Random (requires restarts)
Output	Hierarchy (dendrogram)	Flat partition

Use Agglomerative when your dataset is small (<10k rows), you need a hierarchy, or clusters are non-spherical. Use K-Means for large datasets where speed is critical and clusters are roughly spherical.

Practice

Guided Exercise: Modify the example above to use linkage='single' instead of 'ward'. Does the output change? Why or why not? Hint: With well-separated clusters like these, the output likely remains [0 0 1 1], but the internal merge order differs. Challenge: Create a dataset with three clear groups of points. Run agglomerative clustering with n_clusters=3. Print the unique labels found. Solution Hint: Use np.random.randn(10, 2) + offset to generate three blobs.

Quick check

Question: Which linkage criterion is generally recommended for producing compact, spherical clusters similar to K-Means? Answer: Ward's method.

Summary

Agglomerative clustering offers a deterministic, hierarchical approach to grouping data, ideal for smaller datasets where understanding the structure of merges is valuable. While computationally expensive compared to K-Means, its flexibility with linkage criteria allows it to capture complex cluster shapes that other algorithms might miss.