Hierarchical Clustering

Complete learning notes

1. Introduction

Unlike K-Means, which requires you to decide the number of clusters upfront, Hierarchical Clustering builds a complete tree of nested clusters — letting you decide afterward how many clusters you actually want, simply by choosing where to "cut" the tree.

2. What is Hierarchical Clustering?

Simple definition: Hierarchical Clustering builds a tree-like structure of clusters, progressively merging (or splitting) groups of data points, allowing you to view the data's clustering structure at any level of granularity.

Technical explanation: Agglomerative Hierarchical Clustering (the most common approach) starts with each data point as its own individual cluster, then repeatedly merges the two closest clusters together (based on a chosen linkage method) until all points belong to a single cluster, producing a tree structure called a dendrogram that can be "cut" at any height to yield a specific number of clusters.

3. Why is it Important?

It doesn't require specifying the number of clusters in advance, offering more flexibility than K-Means.
The resulting dendrogram provides rich visual insight into how clusters relate to each other at different levels of granularity.
It's especially useful when you want to explore nested or hierarchical relationships within your data.

4. Prerequisites

Comfort with Clustering fundamentals (Topic 1) and K-Means (Topic 2), since Hierarchical Clustering is often compared directly to it.

5. Core Concepts

Agglomerative (bottom-up) approach
Linkage methods (single, complete, average, ward)
Dendrograms
Cutting the dendrogram to choose a number of clusters

6. Detailed Explanation

a) Agglomerative (Bottom-Up) Approach

The most common form of Hierarchical Clustering starts with every single data point as its own cluster, then repeatedly merges the two closest clusters together, one merge at a time, until only one giant cluster remains.

b) Linkage Methods

Since clusters (not just individual points) need to be compared for "closeness" during merging, a linkage method defines how to measure distance between two clusters:

Single linkage: distance between the closest pair of points (one from each cluster).
Complete linkage: distance between the farthest pair of points.
Average linkage: average distance between all pairs of points across the two clusters.
Ward linkage: minimizes the increase in total within-cluster variance after merging (often produces balanced, compact clusters).

c) Dendrograms

A dendrogram is a tree diagram visually representing the entire merging process — the height at which two clusters merge represents how "far apart" they were when combined. Clusters that merge at low heights are very similar; clusters that only merge near the top of the tree are quite different.

d) Cutting the Dendrogram

To get an actual, specific set of clusters, you draw a horizontal line across the dendrogram at a chosen height — everything connected below that line becomes one cluster. Cutting at different heights gives different numbers of clusters, all from the same single hierarchical structure.

7. How It Works

Start with every data point as its own individual cluster.
Calculate the distance between every pair of clusters (using the chosen linkage method).
Merge the two closest clusters into one.
Repeat steps 2–3, recalculating distances after each merge, until only one cluster remains.
Visualize the entire process as a dendrogram, and cut it at whatever height gives the desired number of clusters.

8. Real-World Example

Biologists use hierarchical clustering-like thinking constantly when building the "tree of life" — individual species are grouped into genera, genera into families, families into orders, and so on, forming a nested hierarchy. Hierarchical Clustering applies this same nested, "closest-things-merge-first" logic to any dataset, not just biological classification.

9. Mathematical Explanation

Ward Linkage (Conceptual Formula):

Ward linkage selects the merge that produces the smallest possible increase in the total within-cluster sum of squares (similar in spirit to the WCSS/inertia concept from K-Means, Topic 2), rather than a simple distance calculation between individual points.

Simple Numerical Example (Single Linkage):

Cluster A = {[1,1]}, Cluster B = {[2,2]}, Cluster C = {[8,8]}

Distance(A, B) = √((2-1)² + (2-1)²) = √2 ≈ 1.41
Distance(A, C) = √((8-1)² + (8-1)²) = √98 ≈ 9.90
Distance(B, C) = √((8-2)² + (8-2)²) = √72 ≈ 8.49

Interpreting the Result: Since Distance(A, B) ≈ 1.41 is the smallest, Clusters A and B would merge first (at a low "height" in the dendrogram), while Cluster C would only join much later, at a much greater height — reflecting that it's clearly more distant from both A and B.

10. Python Example

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

X = np.array([
    [1, 1], [2, 2], [2, 3],
    [8, 8], [9, 8], [8, 9]
])

# Building and visualizing the dendrogram
linked = linkage(X, method="ward")
plt.figure(figsize=(8, 5))
dendrogram(linked)
plt.title("Dendrogram")
plt.xlabel("Data Points")
plt.ylabel("Distance")
plt.show()

# Cutting the tree to get exactly 2 clusters
model = AgglomerativeClustering(n_clusters=2, linkage="ward")
labels = model.fit_predict(X)
print("Cluster assignments:", labels)

Expected Output (approximate):

text
Cluster assignments: [0 0 0 1 1 1]

(A dendrogram also displays, visually showing the merging process and heights at which clusters combined.)

11. Code Explanation

linkage(X, method="ward") calculates the full merging sequence needed to build the dendrogram, using Ward linkage.
dendrogram(linked) visualizes this sequence as a tree diagram.
AgglomerativeClustering(n_clusters=2, ...) effectively "cuts" the tree at the height that produces exactly 2 clusters.
model.fit_predict(X) returns the final cluster assignment (0 or 1) for each data point — correctly grouping the two visually distinct sets of points.

12. Advantages

Doesn't require specifying the number of clusters upfront — you can decide after seeing the full dendrogram.
The dendrogram provides rich, interpretable visual insight into how data points and clusters relate at multiple levels.
Different linkage methods offer flexibility for different types of cluster structures.

13. Limitations

Computationally more expensive than K-Means, especially for larger datasets, since it must track distances between all cluster pairs at every merge step.
Once two clusters are merged, that decision cannot be undone (unlike some other algorithms that can reassign points later).
Choosing the right linkage method and cut height still requires some judgment.

14. Common Mistakes

Assuming Hierarchical Clustering scales as well as K-Means to very large datasets — it generally doesn't, due to higher computational cost.
Not experimenting with different linkage methods, which can produce meaningfully different clustering results.
Cutting the dendrogram at an arbitrary height without carefully considering the resulting cluster structure.

15. Best Practices

Visualize the dendrogram first to get an intuitive sense of your data's natural cluster structure before choosing a cut height.
Experiment with different linkage methods (ward, average, complete) to see which best fits your data.
Consider Hierarchical Clustering especially when you want to explore multiple possible numbers of clusters, or when nested relationships matter.

16. Real-World Applications

Biological taxonomy and phylogenetic tree construction.
Organizing documents or products into nested category hierarchies.
Exploratory data analysis where the "right" number of clusters isn't known in advance.

17. Interview-Oriented Points

Be ready to explain the agglomerative (bottom-up) merging process.
Understand what a dendrogram represents and how cutting it at different heights yields different numbers of clusters.
Be able to name and briefly describe the common linkage methods (single, complete, average, ward).

18. Exam-Oriented Points

Agglomerative Hierarchical Clustering starts with individual points and repeatedly merges the closest clusters.
Linkage methods (single, complete, average, ward) define how "distance" between clusters is measured.
A dendrogram visualizes the merging process; cutting it at a chosen height yields a specific number of clusters.

19. Comparison Table — K-Means vs Hierarchical Clustering

Aspect	K-Means	Hierarchical Clustering
Number of clusters	Must be specified upfront (k)	Can be decided after building the full tree
Scalability	Scales well to large datasets	Computationally more expensive for large datasets
Result structure	A flat set of k clusters	A full nested tree (dendrogram)
Reversibility of merges	Not applicable (reassigns each iteration)	Merges cannot be undone once made

20. Quick Revision

Agglomerative Hierarchical Clustering starts with individual points and repeatedly merges the closest clusters until one remains.
Linkage methods (single, complete, average, ward) define how distance between clusters is measured during merging.
A dendrogram visualizes this process; cutting it at a chosen height yields a specific number of clusters.
Hierarchical Clustering offers flexibility (no need to pre-specify cluster count) at the cost of higher computational expense on large datasets.