Interview Bite

Introduction to Hierarchical Clustering

Hierarchical clustering is a powerful unsupervised learning technique that builds nested clusters through either a bottom-up (agglomerative) or top-down (divisive) approach. Unlike flat clustering methods like K-Means, hierarchical clustering creates a tree-like structure of clusters called a dendrogram that reveals relationships at multiple levels of granularity.

In this definitive guide, you’ll discover:

• How agglomerative and divisive hierarchical clustering work
• Step-by-step Python implementation
• Dendrogram interpretation techniques
• Distance metrics and linkage methods compared
• Real-world applications across industries
• Advantages over other clustering approaches

Did You Know? Hierarchical clustering is widely used in bioinformatics for gene expression analysis and in business for customer segmentation strategies!

---

How Hierarchical Clustering Works

Two Main Approaches

1. Agglomerative (Bottom-Up):
   • Starts with each point as its own cluster
   • Merges most similar clusters iteratively
   • More commonly used in practice
2. Divisive (Top-Down):
   • Starts with all points in one cluster
   • Splits clusters recursively
   • Computationally more expensive

The Algorithm Steps (Agglomerative)

1. Compute distance matrix between all points
2. Merge two closest clusters
3. Update distance matrix
4. Repeat until one cluster remains

# Pseudocode
def agglomerative_clustering(data):
    clusters = [[point] for point in data]
    while len(clusters) > 1:
        ci, cj = find_closest_clusters(clusters)
        clusters.append(merge(ci, cj))
        clusters.remove(ci)
        clusters.remove(cj)
    return dendrogram

---

Key Components of Hierarchical Clustering

1. Distance Metrics

• Euclidean: Standard straight-line distance
• Manhattan: Sum of absolute differences
• Cosine: Angle between vectors
• Mahalanobis: Accounts for covariance

2. Linkage Methods

• Single Linkage: Minimum distance between clusters
• Complete Linkage: Maximum distance between clusters
• Average Linkage: Mean distance between all points
• Ward’s Method: Minimizes variance when merging

3. Dendrogram

The tree diagram that records the sequence of merges/splits:

• Y-axis shows distance between merging clusters
• X-axis shows data points
• Height indicates similarity level

---

Python Implementation

Step 1: Import Libraries

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

Step 2: Generate Sample Data

X, y = make_blobs(n_samples=300, centers=4, random_state=42)
plt.scatter(X[:,0], X[:,1])
plt.title("Original Data")
plt.show()

Step 3: Perform Clustering

# Using scikit-learn
cluster = AgglomerativeClustering(
    n_clusters=4, 
    affinity='euclidean', 
    linkage='ward'
)
clusters = cluster.fit_predict(X)

# Visualize clusters
plt.scatter(X[:,0], X[:,1], c=clusters)
plt.title("Agglomerative Clustering Results")
plt.show()

Step 4: Create Dendrogram

# Using SciPy
Z = linkage(X, method='ward')

plt.figure(figsize=(12,6))
dendrogram(Z, truncate_mode='lastp', p=12)
plt.axhline(y=15, color='r', linestyle='--')
plt.title("Dendrogram")
plt.xlabel("Cluster Size")
plt.ylabel("Distance")
plt.show()

---

Determining Optimal Clusters

1. Dendrogram Cutting

• Draw horizontal line across branches
• Count intersections with vertical lines
• Choose where distance increases sharply

2. Cophenetic Correlation

Measures how well the dendrogram preserves original distances:

from scipy.cluster.hierarchy import cophenet
from scipy.spatial.distance import pdist

c, coph_dists = cophenet(Z, pdist(X))
print(f"Cophenetic Correlation: {c:.3f}")
# > 0.7 is generally good

3. Inertia Analysis

inertia = []
for k in range(1,10):
    model = AgglomerativeClustering(n_clusters=k)
    model.fit(X)
    inertia.append(sum(np.min(
        cdist(X, model.cluster_centers_, 'euclidean'), axis=1)) / X.shape[0])
    
plt.plot(range(1,10), inertia)
plt.title("Elbow Method")
plt.xlabel("Number of Clusters")
plt.ylabel("Inertia")

---

Real-World Applications

1. Customer Segmentation:
   Group customers by purchasing behavior at multiple hierarchy levels
2. Document Clustering:
   Organize similar articles into topic hierarchies
3. Bioinformatics:
   Analyze gene expression patterns and phylogenetic trees
4. Image Processing:
   Segment images into hierarchical regions
5. Supply Chain Optimization:
   Cluster products by demand patterns and categories

---

Advantages Over Other Methods

Feature	Hierarchical	K-Means	DBSCAN
Cluster Shape	Any	Spherical	Any
Hierarchy	Yes	No	No
Cluster Count	Determined later	Specified upfront	Automatic
Outlier Handling	Moderate	Poor	Excellent
Scalability	O(n³)	O(n)	O(n log n)

---

Best Practices

1. Data Preprocessing:
   • Scale features (StandardScaler)
   • Handle missing values
   • Consider dimensionality reduction for high-D data
2. Algorithm Selection:
   • Use agglomerative for most cases
   • Consider divisive for small datasets (<1000 points)
3. Parameter Tuning:
   • Experiment with linkage methods
   • Try different distance metrics
   • Validate with cophenetic correlation
4. Visualization:
   • Always plot dendrogram
   • Use t-SNE/PCA for high-D visualization
   • Color code clusters in scatter plots

---

Advanced Techniques

1. Handling Large Datasets

# Use approximate methods
from sklearn.cluster import FeatureAgglomeration
agglo = FeatureAgglomeration(n_clusters=10)
X_reduced = agglo.fit_transform(X)

2. Categorical Data Clustering

python

Copy

# Use Gower distance
from gower import gower_matrix
dist_matrix = gower_matrix(X_mixed)
Z = linkage(dist_matrix, method='complete')

3. Dynamic Tree Cutting

python

Copy

from scipy.cluster.hierarchy import cut_tree
clusters = cut_tree(Z, height=15) # Cut at distance 15

---

Conclusion: Why Hierarchical Clustering Matters

Hierarchical clustering provides unique advantages that make it indispensable for:
✅ Understanding data relationships at multiple levels
✅ Exploring data without predefined cluster counts
✅ Visualizing complex clustering structures
✅ Applications requiring hierarchical taxonomies

Your Next Steps:

1. Experiment with different linkage methods
2. Apply to real datasets from UCI Machine Learning Repository
3. Combine with other techniques like t-SNE for visualization
4. Explore implementations in R (hclust) and Python

python

Copy

# Complete workflow example
from sklearn.preprocessing import StandardScaler
from scipy.cluster.hierarchy import linkage, dendrogram, fcluster

# Preprocess
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# Cluster
Z = linkage(X_scaled, method='ward', metric='euclidean')

# Extract clusters
clusters = fcluster(Z, t=3, criterion='maxclust')

# Evaluate
from sklearn.metrics import silhouette_score
print(f"Silhouette Score: {silhouette_score(X_scaled, clusters):.2f}")

For more machine learning insights, explore our Machine Learning.