Hierarchical Clustering: Linkage Methods

Hello! Let's continue our journey into unsupervised learning.

Introduction

In our previous lesson, we explored K-means clustering, a powerful algorithm for partitioning data into a predefined number of clusters, k. We learned that its goal is to minimize within-cluster variance and saw how to evaluate its performance using the silhouette score. However, a key limitation of K-means is the need to specify k beforehand. What if we don't know the natural number of groups in our data, or what if the relationships are more complex than simple, globular clusters?

This lesson introduces hierarchical clustering, a method that addresses this very issue. Instead of producing a single flat partition, it builds a tree of nested clusters, revealing the data's structure at multiple levels of granularity. This allows for a more exploratory analysis and provides a richer understanding of the relationships between data points.

Our focus today will be on understanding the core mechanism of hierarchical clustering and, most importantly, how different linkage methods—the rules for measuring distance between clusters—profoundly impact the final result.

By the end of this lesson, you will be able to:

Describe the process of agglomerative hierarchical clustering.
Understand and apply different linkage methods, including single, complete, average, and Ward's method.
Interpret the results using a dendrogram.

1. What is Hierarchical Clustering?

Hierarchical clustering creates a hierarchy of clusters, which can be visualized as a tree-like diagram called a dendrogram. There are two main approaches:

Agglomerative (Bottom-Up): This is the more common method. It starts by treating each data point as its own cluster. Then, in each step, it iteratively merges the two closest clusters until only one cluster (containing all data points) remains.
Divisive (Top-Down): This method starts with all data points in a single cluster and recursively splits it into smaller clusters until each data point is in its own cluster.

We will focus on the agglomerative approach, as it is more widely used and conceptually straightforward.

What is Hierarchical Clustering?

To get a formal introduction to these concepts, please read the initial section of the IBM article "What is Hierarchical Clustering?".

Read the introductory section titled "What is hierarchical clustering?". This will define the algorithm, distinguish between agglomerative and divisive types, and introduce the concept of the dendrogram.

2. The Agglomerative Clustering Algorithm

The bottom-up agglomerative algorithm follows a simple, deterministic process. Given your programming background, you can think of it as a loop that progressively builds up the cluster hierarchy.

The steps are as follows:

Initialization: Start by treating each of the N data points as its own cluster. You have N clusters.
Compute Dissimilarity Matrix: Calculate the distance (e.g., Euclidean distance) between every pair of data points. This forms an N×N matrix.
Merge: Find the two closest clusters in the dataset and merge them into a single new cluster.
Update Matrix: Update the dissimilarity matrix. The distance between the newly formed cluster and all other existing clusters must be calculated. This is the crucial step where linkage methods come into play.
Repeat: Repeat steps 3 and 4 until only one cluster remains.

The central question in this algorithm is: How do you define the distance between two clusters, especially when they contain multiple points? The answer lies in choosing a linkage criterion.

3. Linkage Methods: Defining Inter-Cluster Distance

The linkage method defines the distance between two clusters. The choice of linkage method is critical as it determines the shape of the clusters the algorithm will find. Let's explore the most common methods.

IAML19.5 Single-link, complete-link, Ward's method

This video provides an excellent and concise explanation of five different linkage methods with clear visual examples. Pay close attention to how each method defines the distance between clusters.

Watch the video from the beginning until 08:36. The video covers: Single-linkage (00:24): The distance is the minimum distance between any two points in the respective clusters. Complete-linkage (02:46): The distance is the maximum distance between any two points. Average-linkage (06:04): The distance is the average of all pairwise distances. Centroid-linkage (07:02): The distance is between the centroids of the two clusters. Ward's method (07:27): This method merges the two clusters that result in the minimum increase in the total within-cluster variance.

To summarize and formalize what you just watched:

Linkage Method	Description	Characteristics
Single (min)	Defines cluster distance as the shortest distance between any two points in the two clusters.	Good for non-elliptical shapes, but sensitive to noise and can create long "chains" (the chaining effect).
Complete (max)	Defines cluster distance as the furthest distance between any two points in the two clusters.	Less sensitive to noise and tends to produce compact, spherical clusters. Can struggle with elongated clusters.
Average	Defines cluster distance as the average of all pairwise distances between points in both clusters.	A robust compromise between single and complete linkage. Less sensitive to outliers than single linkage.
Ward's Method	Merges the pair of clusters that leads to the minimum increase in total within-cluster variance.	Tends to produce compact, equally sized clusters. It's a very popular default choice but can be sensitive to outliers.

These methods are not just abstract concepts; they produce visibly different results.

Comparison of Hierarchical Clustering Linkage Methods — This image demonstrates how single, average, complete, and Ward's linkage methods perform on datasets with different underlying structures. Notice how single linkage correctly identifies the nested circles and crescent moons, while Ward's and complete linkage are better for globular clusters but fail on the more complex shapes.

Test your understanding!

Looking at the image above, you are given a dataset that looks like two intertwined crescent moons (second row). You know that K-means would fail to separate these correctly.

Which linkage method would be the best choice for this dataset? Why?
Which linkage methods would likely perform poorly? Why?

Show answer

Single linkage would be the best choice. It defines cluster distance by the nearest points, allowing it to "follow" the elongated, non-globular shape of the moons and correctly identify them as two separate clusters. This is a classic example of where the "chaining" property of single linkage is beneficial.
Complete linkage and Ward's method would perform poorly. Both methods favor creating compact, spherical clusters. They would try to find round groups and would end up incorrectly splitting the crescents and merging parts of different crescents, as shown in the image.

4. Interpreting Results with the Dendrogram

The result of a hierarchical clustering is a single, rich structure: the dendrogram. Learning to read it is key to interpreting the output.

X-axis: Represents the individual data points.
Y-axis: Represents the distance or dissimilarity. The height of the horizontal line connecting two clusters indicates the distance at which they were merged.

The dendrogram shows the entire hierarchy of merges. To get a "flat" set of clusters (like in K-means), you can "cut" the dendrogram at a certain height. The number of vertical lines your horizontal cut intersects is the number of clusters you will have.

Feature Selection using Hierarchical Clustering | Python Tutorial

This video demonstrates the practical side of hierarchical clustering, including how to read and interpret a dendrogram to visualize the clustering process.

Watch the section on visualizing the clustering process using a dendrogram (09:15 - 10:54). Focus on how the height of the forks corresponds to the cluster distance and how this visualizes the entire merging process.

The choice of linkage method directly impacts the structure of the dendrogram.

A common heuristic for choosing the number of clusters is to find the longest vertical line in the dendrogram that is not intersected by any other cluster merges. A cut made there often corresponds to a natural separation in the data.

5. Practical Implementation with Python and SciPy

In practice, you will use libraries like SciPy or scikit-learn to perform hierarchical clustering. The SciPy library is particularly powerful because its functions map directly to the concepts we've discussed: calculating the linkage matrix and plotting the dendrogram.

Let's look at the key functions from scipy.cluster.hierarchy:

linkage(y, method='ward', metric='euclidean'): This is the core function. It takes your scaled data y and performs hierarchical clustering using the specified method (e.g., 'ward', 'single', 'complete'). It returns a linkage matrix, which encodes all the merge operations.
dendrogram(Z): This function takes the linkage matrix Z produced by linkage and plots the corresponding dendrogram.
fcluster(Z, t, criterion='maxclust'): This function is used to "cut" the tree and extract flat clusters. You can specify the number of clusters (t when criterion is 'maxclust') or a distance threshold (t when criterion is 'distance').

Mastering Hierarchical Clustering : From Basic to Advanced

The article "Mastering Hierarchical Clustering" provides a clear code example for implementing this with Python, SciPy, and Matplotlib.

Review the section "Practical implementation of Hierarchical Clustering..." to see the end-to-end workflow: Loading and scaling the data (using StandardScaler). Generating the linkage matrix with linkage(..., method='ward'). Visualizing the result with dendrogram(...). Extracting a specific number of clusters using fcluster(...) and analyzing their properties.

This Python implementation directly mirrors the theoretical steps we've discussed, making it a powerful way to experiment with different linkage methods and see their impact on a real dataset.

Conclusion

In this lesson, we moved beyond the fixed-k limitation of K-means and explored the flexible, exploratory power of hierarchical clustering. You learned how it builds a nested hierarchy of clusters and how the dendrogram provides a rich visualization of the data's structure.

Key Takeaways:

Hierarchical clustering creates a tree of nested clusters, which can be either agglomerative (bottom-up) or divisive (top-down).
The linkage method is the most critical choice, as it defines how distance between clusters is measured.
Single linkage is good for non-convex shapes but sensitive to noise, while Complete and Ward's methods prefer compact, spherical clusters. Average linkage offers a balance.
The dendrogram is the primary visualization tool, showing the entire sequence of merges and allowing you to choose a suitable number of clusters by "cutting" the tree.
Libraries like SciPy provide functions (linkage, dendrogram) that map directly to the core concepts of the algorithm.

Preview of the next lesson:
So far, we've focused on finding groups within our data. But what if the data has too many features (high dimensionality)? Working with hundreds or thousands of features can be computationally expensive and make it difficult for algorithms to find patterns (the "curse of dimensionality"). In the next lesson, we will tackle this by learning about Principal Component Analysis (PCA), a fundamental technique for dimensionality reduction that helps us find a more compact and informative representation of our data.