Hierarchical Clustering

Clustering Algorithms - Hierarchical Clustering

Introduction to Hierarchical Clustering

Hierarchical clustering is an unsupervised learning technique that builds a hierarchy of clusters. Unlike K-Means, it doesn’t require specifying the number of clusters beforehand. Instead, it creates a tree-like structure called a dendrogram, which visualizes the merging or splitting process.

There are two main types of hierarchical clustering:

• Agglomerative (Bottom-Up): Starts with each data point as its own cluster and iteratively merges the closest pair of clusters until only one cluster (containing all points) remains.
• Divisive (Top-Down): Starts with all data points in a single cluster and recursively splits clusters until each data point is its own cluster (less common than agglomerative).

This chapter focuses on Agglomerative Hierarchical Clustering, the more widely used approach.

Agglomerative Hierarchical Clustering: The Process

The agglomerative algorithm proceeds as follows:

1. Initialization: Treat each data point as a separate cluster (N clusters for N data points).
2. Iteration: Repeat the following steps until only one cluster remains:
3. a. Calculate Proximity: Compute the distance (or similarity) between all pairs of current clusters. This requires defining both a distance metric (e.g., Euclidean, Manhattan) and a linkage criterion.
4. b. Merge: Combine the two closest clusters into a single new cluster.
5. Result: A dendrogram representing the sequence of merges.

Linkage Criteria

The linkage criterion defines how the distance between two clusters (not just points) is calculated:

• Ward (Common Default): Minimizes the variance within each cluster. Merges clusters that result in the minimum increase in the total within-cluster sum of squares.
• Complete (Maximum Linkage): Distance between clusters is the maximum distance between any point in the first cluster and any point in the second.
• Average Linkage: Distance between clusters is the average distance between all pairs of points (one from each cluster).
• Single (Minimum Linkage): Distance between clusters is the minimum distance between any point in the first cluster and any point in the second. Can be sensitive to outliers and lead to ‘chaining’.

The choice of linkage criterion significantly impacts the shape and composition of the resulting clusters.

The Role of Dendrograms

The dendrogram is the primary output of hierarchical clustering. It visualizes how clusters are merged (agglomerative) or split (divisive).

• The Y-axis typically represents the distance (or dissimilarity) at which clusters were merged.
• The X-axis represents the individual data points or clusters.
• Horizontal lines connect merged clusters. The height of the horizontal line indicates the distance between the clusters when they were merged.
• Longer vertical lines suggest that the clusters merged at that point are more distinct (further apart).

By ‘cutting’ the dendrogram horizontally at a certain distance threshold, you can obtain a specific number of clusters. A cut that intersects K vertical lines yields K clusters.

Example: Visualizing a Dendrogram

Let’s create a simple dataset and visualize its dendrogram using Scipy and Matplotlib.

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

# Sample data (two distinct groups)
X = np.array([
    [7, 8], [10, 8], [9, 11], [12, 9], # Group 1 approx
    [25, 30], [28, 35], [32, 31], [30, 28] # Group 2 approx
])

# Optional but recommended: Scale the data
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# --- Generate the linkage matrix using Ward linkage ---
# 'ward' minimizes the variance of the clusters being merged.
linked = linkage(X_scaled, method='ward')

# --- Plot the dendrogram ---
plt.figure(figsize=(10, 7))
dendrogram(linked,
            orientation='top', # Show tree growing upwards
            # labels=range(1, len(X) + 1), # Optional: Label leaves 1 to N
            distance_sort='descending', # Sort links by distance
            show_leaf_counts=True) # Show # points in leaves (if node represents > 1 point)

plt.title('Hierarchical Clustering Dendrogram (Ward Linkage)')
plt.xlabel('Data Points (or Cluster Index)')
plt.ylabel('Distance (Ward)')
plt.grid(axis='y', linestyle='--')

# Optional: Add a horizontal line to suggest a cut for k=2 clusters
# Find the largest distance jump to suggest a cut, or choose based on desired k
# This is often done by visual inspection or specific criteria
# plt.axhline(y=..., color='r', linestyle='--')

plt.show()

This code generates a dendrogram for the sample data. You would observe two main branches merging at a relatively large distance, indicating the presence of two distinct clusters. (The plot shows a tree diagram where leaves at the bottom represent individual points, and branches merge upwards. The height of merges indicates the distance/dissimilarity).

Obtaining Cluster Labels with Scikit-learn

While the dendrogram is insightful, we often need the actual cluster assignments for each data point. Scikit-learn’s AgglomerativeClustering class allows us to perform hierarchical clustering and get labels directly, usually by specifying the desired number of clusters (n_clusters).

Example: Applying Agglomerative Clustering

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

# Sample data (same as before)
X = np.array([
    [7, 8], [10, 8], [9, 11], [12, 9],
    [25, 30], [28, 35], [32, 31], [30, 28]
])

# Scale the data
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# --- Apply Agglomerative Clustering ---
# Specify number of clusters (e.g., k=2 based on dendrogram inspection)
# Use 'ward' linkage, often a good default
# 'affinity' is the distance metric ('euclidean' is default for Ward)
cluster_model = AgglomerativeClustering(n_clusters=2, linkage='ward', affinity='euclidean')

# Fit the model and predict cluster labels
# Note: fit_predict is convenient but separates fitting and predicting
labels = cluster_model.fit_predict(X_scaled)

print("Cluster Labels:", labels)

# --- Visualize the clusters ---
plt.figure(figsize=(8, 6))
plt.scatter(X_scaled[:, 0], X_scaled[:, 1], c=labels, cmap='viridis', s=50)
plt.title('Agglomerative Clustering Results (k=2)')
plt.xlabel('Feature 1 (Scaled)')
plt.ylabel('Feature 2 (Scaled)')
plt.grid(True)
plt.show()

Output (Illustrative)

Cluster Labels: [1 1 1 1 0 0 0 0]

The output shows the assigned cluster label (0 or 1) for each data point. The plot visually confirms the two distinct groups found by the algorithm, colored according to their assigned cluster. (The plot would show the 8 points, with the first 4 colored differently from the last 4).

Example 2: Clustering Real Data (Iris Dataset)

Let’s apply hierarchical clustering to the Iris dataset (using only petal length and width for 2D visualization).

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

# Load Iris dataset
iris = load_iris()
X = iris.data[:, 2:4] # Use only petal length (index 2) and petal width (index 3)
y_true = iris.target # True labels for comparison (not used for clustering)
feature_names = iris.feature_names[2:4]

# Scale the features
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# --- Dendrogram ---
linked = linkage(X_scaled, method='ward')
plt.figure(figsize=(12, 7))
dendrogram(linked,
            orientation='top',
            distance_sort='descending',
            show_leaf_counts=True)
plt.title('Iris Dataset Dendrogram (Petal Features, Ward Linkage)')
plt.xlabel('Sample Index')
plt.ylabel('Distance')
plt.show()

# --- Agglomerative Clustering (k=3, based on domain knowledge or dendrogram) ---
cluster_model = AgglomerativeClustering(n_clusters=3, linkage='ward', affinity='euclidean')
labels = cluster_model.fit_predict(X_scaled)

# --- Visualize Clusters ---
plt.figure(figsize=(8, 6))
plt.scatter(X_scaled[:, 0], X_scaled[:, 1], c=labels, cmap='viridis', s=50)
plt.title('Hierarchical Clustering on Iris Petals (k=3)')
plt.xlabel(f'{feature_names[0]} (Scaled)')
plt.ylabel(f'{feature_names[1]} (Scaled)')
plt.grid(True)
plt.show()

# Optional: Compare with true labels (if available)
from sklearn.metrics import adjusted_rand_score
ari = adjusted_rand_score(y_true, labels)
print(f"\nAdjusted Rand Index (vs true labels): {ari:.4f}")

This example first shows the dendrogram for the Iris petal features, which typically suggests three main groups. Then, it applies AgglomerativeClustering with n_clusters=3 and visualizes the resulting clusters. The Adjusted Rand Index (ARI) provides a quantitative measure of how well the clustering matches the true species labels (requires true labels, not used during clustering itself).

Advantages and Disadvantages

Advantages

• No Need to Specify K: The number of clusters doesn’t need to be pre-specified; the dendrogram provides insights.
• Intuitive Visualization: Dendrograms offer a clear visualization of the merging process and cluster relationships.
• Hierarchy: Captures the hierarchical structure potentially present in the data.
• Flexibility: Works with various distance metrics and linkage criteria.

Disadvantages

• Computationally Expensive: Typically has a time complexity of O(N³) and memory complexity of O(N²), making it slow for very large datasets (N=number of data points). Scikit-learn’s implementation uses optimizations, but it can still be demanding.
• No Corrections: Merges are final; points cannot be reassigned once merged (unlike K-Means).
• Sensitivity to Linkage/Metric: The results can vary significantly based on the chosen distance metric and linkage criterion.
• Dendrogram Interpretation: Deciding where to ‘cut’ the dendrogram to get the optimal number of clusters can be subjective.

Applications

Hierarchical clustering is useful in various fields:

• Biology: Creating taxonomies of species (phylogenetic trees).
• Social Network Analysis: Identifying communities or hierarchies.
• Market Research: Segmenting customers based on similarity hierarchies.
• Image Analysis: Grouping similar image regions.

Further Resources

• Scikit-learn Hierarchical Clustering: https://scikit-learn.org/stable/modules/clustering.html#hierarchical-clustering
• SciPy Hierarchy Clustering: https://docs.scipy.org/doc/scipy/reference/cluster.hierarchy.html
• StatQuest: Hierarchical Clustering: https://statquest.org/video-index/ (Search for Hierarchical Clustering)