Hierarchical Clustering

Hierarchical clustering is a powerful unsupervised machine learning algorithm used to group similar data points into clusters based on their similarity. Unlike partitioning algorithms like k-means, hierarchical clustering builds a hierarchy of clusters, resulting in a tree-like structure called a dendrogram. This approach allows for the exploration of relationships at different granularities.

Key Concepts

Hierarchical clustering is broadly categorized into two main approaches:

• Agglomerative Clustering (Bottom-Up):

  • This is the more common approach.
  • It begins with each data point as its own individual cluster.
  • In each step, the two closest clusters are merged based on a defined linkage criterion.
  • This process continues until all data points belong to a single, large cluster.

• Divisive Clustering (Top-Down):

  • This approach starts with a single cluster containing all data points.
  • In each step, the cluster is recursively split into smaller clusters until each data point forms its own cluster.
  • This method is less frequently used due to its computational complexity.

Essential Components

• Dendrogram: A tree-like diagram that visually represents the sequence of merges (in agglomerative clustering) or splits (in divisive clustering). Each merge or split is shown as a horizontal line connecting clusters, with the height of the line indicating the distance at which the merge/split occurred.
• Linkage Criteria: These criteria define how the distance between clusters is computed. The choice of linkage significantly impacts the shape of the clusters and the resulting dendrogram. Common linkage methods include:
  • Single Linkage (Minimum Linkage): The distance between two clusters is defined as the minimum distance between any point in the first cluster and any point in the second cluster. This method can suffer from the "chaining effect," where elongated clusters are formed.
  • Complete Linkage (Maximum Linkage): The distance between two clusters is defined as the maximum distance between any point in the first cluster and any point in the second cluster. This method tends to produce more compact, spherical clusters.
  • Average Linkage: The distance between two clusters is the average of all pairwise distances between points in the first cluster and points in the second cluster. This method offers a balance between single and complete linkage.
  • Ward's Method: This method aims to minimize the total variance within each cluster. At each step, it merges the pair of clusters that results in the smallest increase in the total within-cluster variance. This often leads to clusters of similar size and shape.

How Hierarchical Clustering Works (Agglomerative Example)

The most common implementation of hierarchical clustering is the agglomerative (bottom-up) approach:

1. Initialization: Treat each data point as an individual cluster.
2. Distance Calculation: Calculate the distance between all pairs of data points using a chosen distance metric (e.g., Euclidean distance).
3. First Merge: Identify the two closest clusters and merge them into a single new cluster.
4. Distance Recomputation: Recompute the distances between the newly formed cluster and all other remaining clusters using the selected linkage criterion.
5. Iterative Merging: Repeat steps 3 and 4. In each iteration, the two closest clusters (which could be individual points or previously merged clusters) are merged.
6. Termination: The process continues until all data points are part of a single cluster.

The sequence of merges is then recorded and can be visualized using a dendrogram.

Applications of Hierarchical Clustering

Hierarchical clustering finds applications across various domains:

• Bioinformatics: Analyzing gene expression data to identify groups of genes with similar expression patterns.
• Natural Language Processing (NLP): Clustering documents or text data to group similar topics or themes.
• Marketing: Customer segmentation to identify groups of customers with similar purchasing behaviors or demographics.
• Computer Vision: Image segmentation to group pixels with similar characteristics (color, texture).
• Social Network Analysis: Identifying communities or groups of users with similar connections and interactions.

Python Example: Hierarchical Clustering with Dendrogram

This example demonstrates how to perform hierarchical clustering using scipy and visualize the results with a dendrogram.

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

# 1. Generate synthetic data
# We create a dataset with 150 samples, 3 centers, and some noise.
X, _ = make_blobs(n_samples=150, centers=3, cluster_std=0.70, random_state=42)

# 2. Compute the linkage matrix
# 'ward' method minimizes the variance within clusters.
linked = linkage(X, method='ward')

# 3. Plot the dendrogram
plt.figure(figsize=(10, 7))
dendrogram(
    linked,
    truncate_mode='lastp',  # Show only the last p merged clusters
    p=30,                   # Number of clusters to display
    leaf_rotation=90.,      # Rotate the x-axis labels
    leaf_font_size=12.,     # Font size for the x-axis labels
    show_contracted=True    # To get a compressed dendrogram in roots of hierarchical tree
)
plt.title('Hierarchical Clustering Dendrogram')
plt.xlabel('Sample Index or Cluster Size')
plt.ylabel('Distance (Ward)')
plt.show()

# 4. Form clusters by cutting the dendrogram
# We specify the desired number of clusters (e.g., 3)
num_clusters = 3
labels = fcluster(linked, num_clusters, criterion='maxclust')

# 5. Plot the clustered data
plt.figure(figsize=(8, 6))
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='Set1', marker='o', edgecolor='k')
plt.title('Data Grouped by Hierarchical Clustering')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()

Choosing the Optimal Number of Clusters

Determining the "best" number of clusters is often subjective and depends on the analysis goal. Here are common approaches:

• Dendrogram Analysis:

  • Visually inspect the dendrogram. Look for the largest vertical distances between merges that do not intersect many horizontal lines. Cutting the dendrogram at a certain height or number of clusters can reveal natural groupings.
  • The truncate_mode and p parameters in the dendrogram function help visualize the top p merges.

• Cut-off Distance (t):

  • Select a distance threshold t. All clusters that are merged at a distance greater than t are considered distinct. The fcluster function can use a distance criterion (criterion='distance') with a specified threshold.

• Metrics (e.g., Silhouette Score, Davies-Bouldin Index):

  • While not shown in the basic example, external metrics can be used to evaluate the quality of clustering for different numbers of clusters. You would run the algorithm for a range of cluster numbers and choose the one that optimizes the chosen metric.

Advantages of Hierarchical Clustering

• No Prior Knowledge of Cluster Count: Unlike k-means, you don't need to specify the number of clusters beforehand. The dendrogram provides a visual means to decide on the number of clusters.
• Interpretable Visualization: The dendrogram offers a clear and intuitive visualization of the data's hierarchical structure and the merging/splitting process.
• Nested Patterns: It can capture nested patterns and relationships within the data, which might be missed by flat clustering methods.
• Effective for Smaller Datasets: It generally performs well on small to medium-sized datasets.

Disadvantages of Hierarchical Clustering

• Computational Complexity: Agglomerative hierarchical clustering typically has a time complexity of O(n³) or O(n² log n) depending on the implementation, making it computationally expensive for very large datasets.
• Sensitivity to Noise and Outliers: The merging process can be sensitive to outliers, which can disproportionately affect distances and linkage calculations.
• Irreversibility: Once a merge or split is made, it cannot be undone. This can lead to suboptimal clustering if an early decision is poor.
• Choice of Linkage: The final clustering structure can vary significantly depending on the chosen linkage criterion.

Summary

Hierarchical clustering is a versatile and interpretable clustering technique that builds a hierarchy of clusters. Its ability to reveal nested relationships and its lack of a requirement for pre-specifying the number of clusters make it valuable for exploratory data analysis and understanding complex data structures. However, its computational cost limits its scalability to large datasets, where alternative algorithms might be more suitable.