Hierarchical Clustering: Agglomerative, Divisive, and Dendrograms

Learn Hierarchical Clustering in-depth. Understand Agglomerative vs. Divisive clustering, linkage criteria, dendrogram analysis, and Python implementation.

Introduction

Imagine organizing a folder structure on your computer. You start with individual files, group them into subfolders, group those subfolders into larger folders, and finally collect everything inside a single root folder. This tree-like structure is the essence of Hierarchical Clustering.

Unlike K-Means, which requires you to decide the number of clusters ($K$) upfront, Hierarchical Clustering builds a hierarchy of clusters. It is an intuitive unsupervised learning technique that shows the structural relationships between all data points.

What You Will Learn

  • The difference between Agglomerative (Bottom-Up) and Divisive (Top-Down) approaches.
  • How to measure cluster distances using Linkage Criteria (Single, Complete, Average, Ward's).
  • How to read and interpret a Dendrogram.
  • How to implement Hierarchical Clustering in Python using scipy and scikit-learn.

Why This Topic Matters

Hierarchical Clustering is vital when the relationships between objects are naturally hierarchical. For example, in taxonomy (naming species), evolutionary biology (building phylogenetic trees), and corporate structures, understanding how categories split or merge is just as important as the final clusters themselves.

Prerequisites

Detailed Explanation

Hierarchical Clustering creates a tree of clusters called a Dendrogram. There are two ways to build this tree:

graph TD
    A[Agglomerative: Bottom-Up <br> Start: Individual points <br> End: One giant cluster]
    B[Divisive: Top-Down <br> Start: One giant cluster <br> End: Individual points]

1. Agglomerative Clustering (Bottom-Up)

This is the most common approach.

  • Start: Treat each data point as a single-element cluster.
  • Iteration: Find the two closest clusters and merge them into a single cluster.
  • Repeat: Keep merging until all points are gathered into a single root cluster.

2. Divisive Clustering (Top-Down)

  • Start: Treat all data points as one single giant cluster.
  • Iteration: Partition the cluster into two least-similar sub-clusters.
  • Repeat: Recursively split sub-clusters until every point is its own cluster.

Linkage Criteria

To merge or split clusters, we need to define how to calculate the "distance" between two clusters ($A$ and $B$). We do this using Linkage Criteria:

| Linkage Type | Description | Formula / Behavior | | :--- | :--- | :--- | | Single Linkage | Distance between the two closest points. | $\min { d(x, y) : x \in A, y \in B }$ | | Complete Linkage| Distance between the two furthest points. | $\max { d(x, y) : x \in A, y \in B }$ | | Average Linkage | Average distance between all pairs of points. | $\frac{1}{|A| \cdot |B|} \sum_{x \in A} \sum_{y \in B} d(x, y)$ | | Ward's Linkage | Minimizes the variance within merged clusters. | Minimizes Sum of Squared Errors (SSE) |

Note: Ward's Linkage is the most common default for general-purpose clustering because it leads to clean, balanced clusters.

Reading a Dendrogram

A dendrogram is a tree diagram that records the history of merges (or splits).

  • The horizontal axis represents individual data points.
  • The vertical axis represents the distance (dissimilarity) at which clusters were merged.
  • To find the optimal number of clusters, you draw a horizontal line across the dendrogram. The number of vertical lines this horizontal line intersects is your cluster count ($K$). Choose the threshold line that cuts across the longest vertical distance without intersecting another merge point.

Visual Diagram (Mermaid)

graph TD
    subgraph Dendrogram Flow
    A[Point 1] & B[Point 2] --> AB[Cluster 12]
    C[Point 3] & D[Point 4] --> CD[Cluster 34]
    AB & CD --> ABCD[Root Cluster]
    end

Python Code Examples

We will build a dendrogram using SciPy and implement Agglomerative Clustering using Scikit-Learn.

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

# 1. Create dummy data
X, _ = make_blobs(n_samples=15, centers=3, random_state=42)

# 2. Compute Linkage Matrix (using Ward's method)
Z = linkage(X, method='ward')

# 3. Print the linkages (showing merge steps)
print("Linkage Matrix Z (first 5 steps):")
print(Z[:5])

# 4. Perform Agglomerative Clustering
cluster = AgglomerativeClustering(n_clusters=3, metric='euclidean', linkage='ward')
labels = cluster.fit_predict(X)

print("\nAssigned Labels for the 15 points:")
print(labels)

Industry Use Cases

  • Gene Expression Profiling: Grouping genes with similar behavior across different experimental conditions to understand biological pathways.
  • Market Research: Organizing brands or products into hierarchical groups (e.g., Luxury -> Premium -> Economy) based on features and consumer perceptions.
  • Social Network Analysis: Mapping communities to see how small groups merge into larger sub-communities.

Advantages & Limitations

Advantages

  • No need to predefine $K$: You can run the algorithm first, plot the dendrogram, and decide the number of clusters later.
  • Informative Hierarchy: The dendrogram provides an excellent way to visualize relationships.
  • Deterministic: K-Means can give different results depending on centroid initialization. Hierarchical clustering always yields the same result for a given linkage.

Limitations

  • High Complexity: Time complexity is $O(N^3)$ and space complexity is $O(N^2)$. It is extremely slow and RAM-intensive for datasets with more than a few thousand rows.
  • Irreversible merges: Once two clusters are merged, they cannot be unmerged in future iterations.

FAQs

Q: Can I use Hierarchical Clustering for a dataset of 1 million rows? A: No. Because of its $O(N^2)$ memory requirement, a matrix of $10^6 \times 10^6$ distances would require terabytes of RAM. You should use mini-batch K-Means or DBSCAN instead.

Q: What is the height of a link in a dendrogram? A: The height represents the distance between the two clusters being merged. A tall link means the two clusters were very different from each other before merging.

Summary

Hierarchical Clustering builds nested trees of clusters using either bottom-up (agglomerative) or top-down (divisive) strategies. By selecting an appropriate linkage criterion (such as Ward's or Complete) and studying the resulting dendrogram, you can identify hidden nested structures in data. However, due to its computational intensity, it should only be used on small to medium-sized datasets.

Next Topic

What if your clusters are not spherical, and you want to group points based on density rather than distance, while ignoring noisy data? Let's learn about: DBSCAN Clustering.

← Back to Syllabus