deltagradient: Hierarchical Clustering

Hierarchical Clustering

Hierarchical Clustering: An In-Depth Guide

Hierarchical clustering is another popular clustering technique used in unsupervised machine learning. Unlike K-means clustering, which partitions the data into k clusters, hierarchical clustering builds a hierarchy of clusters that can be represented in a tree-like structure known as a dendrogram.

Hierarchical clustering can be used for both agglomerative (bottom-up) and divisive (top-down) clustering. Agglomerative clustering is more commonly used, and this guide will focus primarily on it.

Types of Hierarchical Clustering

Agglomerative Hierarchical Clustering (Bottom-Up):
- Starts with each data point as its own cluster and then merges the closest clusters at each step until all data points belong to a single cluster or the desired number of clusters is reached.
Divisive Hierarchical Clustering (Top-Down):
- Starts with one large cluster containing all the data points and iteratively splits it into smaller clusters based on some criterion until each data point is in its own cluster or the desired number of clusters is achieved.

In practice, agglomerative clustering is much more common, as it is easier to compute and does not require an initial partitioning.

How Agglomerative Hierarchical Clustering Works

Agglomerative hierarchical clustering follows these general steps:

Start with Individual Points as Clusters: Treat each data point as a cluster.
Compute Pairwise Distances: Calculate the distances between all pairs of data points (or clusters). Common distance metrics include Euclidean distance, Manhattan distance, and Cosine similarity.
Merge the Closest Clusters: At each iteration, merge the two closest clusters (the clusters with the smallest distance between them).
Repeat Until One Cluster Remains: Continue merging clusters until all data points belong to a single cluster, or until a predefined number of clusters is reached.

Distance Metrics in Hierarchical Clustering

The key step in hierarchical clustering is calculating the distance between clusters. Several linkage methods can be used to define the distance between clusters:

Single Linkage:
- The distance between two clusters is defined as the shortest distance between any two points in the clusters (the closest pair).
- This method tends to produce "long and thin" clusters.
Complete Linkage:
- The distance between two clusters is defined as the longest distance between any two points in the clusters (the farthest pair).
- This method tends to produce more compact clusters.
Average Linkage:
- The distance between two clusters is the average distance between all pairs of points in the clusters.
Ward's Linkage:
- Aims to minimize the variance within clusters. It merges the clusters that result in the smallest increase in the total within-cluster variance.

Dendrogram: A Tree Representation of Clusters

One of the key outputs of hierarchical clustering is the dendrogram, a tree-like diagram that shows how clusters are merged at each step. The height of the branches indicates the distance at which clusters were merged. By cutting the dendrogram at a certain height, we can define the number of clusters.

Example of a Dendrogram:

Height: The y-axis of the dendrogram represents the distance (or dissimilarity) between clusters.
Branches: The branches show which clusters are merged at each step.

You can control how many clusters you want by cutting the dendrogram at a specific level.

Agglomerative Hierarchical Clustering Example (Python)

Let’s walk through an example of applying agglomerative hierarchical clustering to a synthetic dataset.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_blobs
import scipy.cluster.hierarchy as sch

# Generate synthetic data (1000 samples, 4 centers)
X, _ = make_blobs(n_samples=1000, centers=4, cluster_std=0.60, random_state=0)

# Apply Agglomerative Clustering
agg_clust = AgglomerativeClustering(n_clusters=4)
labels = agg_clust.fit_predict(X)

# Plot the clustered data points
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis')
plt.title("Agglomerative Clustering")
plt.show()

# Create a dendrogram
plt.figure(figsize=(10, 7))
sch.dendrogram(sch.linkage(X, method='ward'))
plt.title("Dendrogram")
plt.show()

Breakdown of the Code:

Data Generation: We generate a synthetic dataset with 1000 samples and 4 centers using make_blobs.
Agglomerative Clustering: We apply AgglomerativeClustering from sklearn to cluster the data into 4 clusters.
Plotting the Clusters: We plot the data points with colors corresponding to the cluster they belong to.
Dendrogram: We create a dendrogram to visualize the merging of clusters using scipy.cluster.hierarchy.

Advantages of Hierarchical Clustering

No Need to Specify k: Unlike K-means clustering, hierarchical clustering does not require you to specify the number of clusters in advance. You can decide the number of clusters by cutting the dendrogram at a particular height.
Dendrogram Visualization: The dendrogram provides a visual representation of the clustering process, making it easy to analyze and choose the appropriate number of clusters.
Works Well with Arbitrary Shapes: Hierarchical clustering is more flexible than K-means and can handle clusters of arbitrary shapes and sizes.
Handles Small Datasets Well: Hierarchical clustering can work well on small to medium-sized datasets, as the complexity of the algorithm increases quadratically with the number of data points.

Limitations of Hierarchical Clustering

Computational Complexity: The time complexity of agglomerative hierarchical clustering is $O(n^3)$ , where n is the number of data points. This makes it computationally expensive for large datasets.
Memory Usage: Storing all pairwise distances can be memory-intensive for large datasets.
Sensitive to Noise and Outliers: Hierarchical clustering can be sensitive to noise and outliers, which may distort the clustering results.
Difficulty with Large Datasets: Hierarchical clustering is not scalable to very large datasets (e.g., tens of thousands of data points) due to its high computational and memory complexity.

Applications of Hierarchical Clustering

Gene Expression Analysis: In bioinformatics, hierarchical clustering is often used to group genes that have similar expression patterns across different samples.
Document Clustering: Hierarchical clustering can be used to group similar documents or texts for information retrieval, such as clustering news articles or research papers by topics.
Image Segmentation: It can be applied to segment an image into regions based on color or texture.
Market Segmentation: Clustering customers or users into segments based on purchasing behavior, preferences, or demographics.

Choosing the Right Clustering Algorithm

K-Means: If you know or have a good estimate of the number of clusters in advance and the clusters are roughly spherical, K-means is a great choice.
Hierarchical Clustering: If you want to explore the dataset without specifying the number of clusters upfront or if you are interested in understanding the hierarchical structure of the data, hierarchical clustering is more suitable.

Conclusion

Hierarchical clustering is a powerful clustering technique that builds a hierarchy of clusters and provides a detailed tree structure (dendrogram) to visualize how clusters are merged or split. It has the advantage of not requiring the number of clusters to be specified upfront and works well with non-spherical clusters. However, it is computationally expensive and may not scale well with large datasets. Understanding its strengths and limitations will help you determine when hierarchical clustering is the right choice for your unsupervised learning tasks.

Search This Blog