Hierarchical Clustering Explained: A Guide for Machine Learning Students

Introduction to Hierarchical Clustering

Hierarchical clustering is a fundamental unsupervised learning technique that organises data into a tree-like structure of nested clusters. Unlike K-Means, which requires you to pre-specify the number of clusters, hierarchical clustering builds a hierarchy that allows you to explore data at multiple levels of granularity. For your machine learning exams, understanding this method is crucial as it provides a deterministic way to visualise relationships between data points.

In this article, we will explore the two primary approaches: agglomerative (bottom-up) and divisive (top-down). We will focus primarily on the agglomerative approach, which is the standard in most machine learning libraries. By the end, you will be able to perform manual calculations, interpret dendrograms, and understand how different linkage criteria influence the final cluster shapes.

The Agglomerative Approach

Agglomerative hierarchical clustering follows a bottom-up strategy. It begins by treating each individual data point as its own cluster. At each step, the algorithm identifies the two closest clusters and merges them into a single, larger cluster. This process repeats until only one cluster remains, containing all original data points.

To perform this, we need a distance metric (such as Euclidean distance) and a linkage criterion to define the distance between clusters. The sequence of merges is recorded in a structure called a dendrogram, which acts as a visual history of the clustering process.

Linkage Criteria Explained

Linkage criteria determine how the distance between two clusters is calculated. Choosing the right linkage is vital as it dictates the geometry of the resulting clusters:

• Single Linkage (Nearest Neighbour): The distance between two clusters is the minimum distance between any single point in the first cluster and any single point in the second. This often leads to the 'chaining' effect.
• Complete Linkage (Farthest Point): The distance is the maximum distance between any point in the first cluster and any point in the second. This tends to produce compact, spherical clusters.
• Average Linkage: The distance is the average of all pairwise distances between points in the two clusters.
• Ward’s Method: This minimises the total within-cluster variance, often resulting in clusters of similar size.

Worked Example 1: Manual Agglomerative Clustering

Consider four points in 1D space: $A=0, B=1, C=4, D=5$. We will use single linkage and Euclidean distance.

1. Initial state: Clusters are {A}, {B}, {C}, {D}.
2. Step 1: Distances are $d(A,B)=1, d(B,C)=3, d(C,D)=1$. The minimum distance is 1. We can merge {A,B} or {C,D}. Let us merge {A,B} into cluster {AB}.
3. Step 2: New clusters are {AB}, {C}, {D}. Distances: $d(AB,C) = \min(d(A,C), d(B,C)) = \min(4, 3) = 3$. $d(C,D)=1$. We merge {C,D} into {CD}.
4. Step 3: Clusters are {AB}, {CD}. Distance $d(AB,CD) = \min(d(A,C), d(A,D), d(B,C), d(B,D)) = \min(4, 5, 3, 4) = 3$.
5. Final merge: Merge {AB} and {CD} at height 3.

Interpreting the Dendrogram

A dendrogram is a binary tree that represents the hierarchical structure. The x-axis represents the individual data points, while the y-axis represents the distance (or dissimilarity) at which clusters were merged.

To obtain a flat clustering from a dendrogram, you 'cut' the tree at a specific height. If you draw a horizontal line at a height $h$, the number of vertical lines the horizontal line intersects corresponds to the number of clusters. This allows you to choose the number of clusters post-hoc without re-running the algorithm.

Worked Example 2: Distance Matrix Update

Given points $P_1, P_2, P_3$ with distances $d(1,2)=2, d(2,3)=5, d(1,3)=6$.

1. Merge $P_1$ and $P_2$ (distance 2). New cluster $C_{12}$.
2. Update distance to $P_3$ using complete linkage: $d(C_{12}, P_3) = \max(d(1,3), d(2,3)) = \max(6, 5) = 6$.
3. The final merge occurs at height 6.

Common Mistakes

• Confusing Linkage with Distance: Remember that the distance metric (e.g., Euclidean) measures the gap between points, while the linkage criterion defines how to measure the gap between sets of points.
• Misinterpreting the Y-axis: Students often assume the y-axis is the number of clusters. It is the distance (dissimilarity) at which the merge occurred.
• Ignoring Scaling: Hierarchical clustering is sensitive to the scale of features. Always standardise your data (e.g., Z-score normalisation) before clustering.

FAQ

Q: Is hierarchical clustering computationally expensive? Yes, standard agglomerative clustering has a complexity of $O(n^3)$ or $O(n^2 \log n)$, making it unsuitable for very large datasets compared to K-Means.

Q: Can I use hierarchical clustering for non-Euclidean data? Yes, you can use any valid distance metric, such as Manhattan or Cosine distance, provided it satisfies the properties of a metric space.

Q: How do I decide the number of clusters? Look for the largest vertical gaps in the dendrogram. A long vertical line indicates that the clusters are well-separated at that level of the hierarchy.

Conclusion

Hierarchical clustering is a powerful tool for understanding the nested structure of your data. By mastering the linkage criteria and dendrogram interpretation, you gain a deeper insight into your dataset than flat clustering methods can provide. To see these concepts in action with interactive visualisations, generate a free animated lesson on this topic at MathInstructor AI.