Hello! Welcome to your next lesson in the Unsupervised Learning & Dimensionality Reduction module.
In our last lesson, we explored partitioning clustering algorithms like K-Means and K-Medoids. We saw how they are effective at grouping data but require us to specify the number of clusters, , in advance. This can be a significant limitation when you don't have prior knowledge about your dataset.
Today, we'll tackle that limitation by exploring a different family of clustering algorithms. This lesson addresses the learning outcome: Explain hierarchical clustering and how to interpret dendrograms. Instead of creating a single flat set of clusters, this method builds a multi-level hierarchy, giving us a much richer view of the data's structure. This is a fundamental concept for your GATE exam preparation, offering a powerful alternative to partitioning methods.
1. Two Approaches to Building a Hierarchy
Hierarchical clustering builds a tree-like structure of nested clusters. There are two main strategies for doing this:
- Agglomerative (Bottom-Up): This is the most common approach. It starts by treating each data point as its own cluster and then iteratively merges the two closest clusters until only one cluster (containing all data points) remains.
- Divisive (Top-Down): This approach is less common. It starts with all data points in a single, massive cluster and recursively splits it into smaller clusters until every data point is in its own cluster.
The following video provides an excellent overview of this concept, contrasting hierarchical clustering with the "flat" clustering we saw in the previous lesson (like K-Means).
Flat and Hierarchical Clustering | The Dendrogram Explained
This video, 'Flat and Hierarchical Clustering', introduces the core idea of a cluster hierarchy and explains the difference between the 'bottom-up' (agglomerative) and 'top-down' (divisive) methods.
Watch from the beginning to 03:06. Focus on the animal kingdom analogy to understand the concept of a hierarchy and grasp the fundamental difference between the agglomerative and divisive processes.
For the rest of this lesson, we will focus on agglomerative clustering, as it is the most widely used and tested method.
2. The Agglomerative Clustering Process
Let's break down the "bottom-up" approach. The algorithm is conceptually straightforward:
- Start: Treat each of your N data points as N separate clusters.
- Find Closest Pair: Calculate the distance between every pair of clusters.
- Merge: Combine the two closest clusters into a single new cluster.
- Repeat: Repeat steps 2 and 3 until all data points have been merged into one single cluster.
The StatQuest video below provides a fantastic visual walkthrough of this iterative merging process.
StatQuest: Hierarchical Clustering
Let's watch a segment from 'StatQuest: Hierarchical Clustering' to see this merging process in action. It provides a great visual intuition for how the algorithm progressively builds clusters.
Watch from 01:34 to 04:38. Pay attention to how, after two genes are merged into a cluster, that new cluster is treated as a single entity for future comparisons.
3. Visualizing the Hierarchy: The Dendrogram
The real power of hierarchical clustering comes from its output: a tree-like diagram called a dendrogram. This diagram visualizes the entire merging process, showing which clusters were merged and at what distance.
A dendrogram has two main axes:
- The x-axis lists the individual data points.
- The y-axis represents the distance or dissimilarity. The height of the horizontal line connecting two clusters shows the distance between them when they were merged.
A taller line means the clusters were more dissimilar (further apart) when they were joined.
Interpreting the Dendrogram
The video below gives a clear, practical example of how to read a dendrogram and extract insights about the similarity between clusters.
Flat and Hierarchical Clustering | The Dendrogram Explained
Let's return to the 'Flat and Hierarchical Clustering' video. This section explains how to interpret the branches and heights of a dendrogram using a real-world example with countries.
Watch from 03:06 to 05:52. Focus on how the vertical distance between merges indicates dissimilarity. For example, notice how Germany and France merge at a low height (very similar), while Australia joins the main group at a very large height (very different).
Choosing the Number of Clusters from a Dendrogram
Unlike K-Means, you don't need to specify the number of clusters beforehand. Instead, you decide after running the algorithm by "cutting" the dendrogram.
You can determine the number of clusters by drawing a horizontal line across the dendrogram. The number of vertical lines your horizontal line intersects is the number of clusters you will have.
The following video segment demonstrates this cutting process.
Flat and Hierarchical Clustering | The Dendrogram Explained
This final clip from 'Flat and Hierarchical Clustering' shows exactly how to use this 'cutting' technique to choose an optimal number of clusters.
Watch from 05:52 to 07:02. The key takeaway is the general rule: find the largest vertical 'jump' where no merges happen, and cut your dendrogram in that space.
4. Key Parameters: Distance and Linkage Methods
To decide which clusters to merge, the algorithm needs two things: a way to measure the distance between points and a way to measure the distance between clusters. These are critical choices that can significantly change your results.
Distance Metrics
This measures the distance between two individual data points. The most common is Euclidean distance (a straight line), but others like Manhattan distance ("city blocks") can also be used.
Linkage Criteria
This defines how to measure the distance between two clusters (which may contain multiple points). This is a crucial concept for the GATE exam.
The StatQuest video you saw earlier also explains these different methods for comparing clusters. Let's revisit it to understand the common linkage criteria.
StatQuest: Hierarchical Clustering
This section of the StatQuest video provides excellent visual intuitions for different linkage methods.
Watch from 08:41 to 10:48. Focus on understanding the difference between: Single Linkage: distance between the closest points. Complete Linkage: distance between the farthest points. Centroid/Average Linkage: distance between the cluster averages.
In addition to the methods in the video, another very popular and important method is Ward's Linkage. For a quick and clear definition, please read the following text.
Hierarchical Clustering Explained: Building Clusters Step-by-Step
The article 'Hierarchical Clustering Explained' provides clear, concise definitions of the different linkage methods. Let's focus on its definition of Ward's linkage, which is often a default in software and performs well in practice.
Read just the small section under '2. Linkage Method: How Close are Clusters?'. Pay special attention to the explanation of Ward's Linkage. Unlike the others, it doesn't just look at distance; it merges clusters that cause the minimum increase in the total variance within all clusters.
Here is a summary of the key linkage methods for your notes:
| Linkage Method | How it Measures Cluster Distance | Tends to Produce |
|---|---|---|
| Single | The distance between the closest pair of points. | Long, "chained" clusters. Sensitive to outliers. |
| Complete | The distance between the farthest pair of points. | Compact, spherical clusters. Less sensitive to outliers. |
| Average | The average distance between all pairs of points. | A balance between single and complete. |
| Ward's | Merges clusters to minimize the increase in total within-cluster variance. | Compact, spherical clusters. Often a good default choice. |
Conclusion
In this lesson, we explored hierarchical clustering, a powerful unsupervised method that builds a nested tree of clusters instead of a single flat partition. This approach frees us from having to choose the number of clusters in advance.
Key Takeaways:
- Hierarchical Clustering creates a tree-like structure of clusters, most commonly using an agglomerative (bottom-up) approach.
- The output is visualized as a dendrogram, where branch height represents the dissimilarity at which clusters were merged.
- We can choose the final number of clusters by "cutting" the dendrogram at an appropriate height, often across the longest vertical line.
- The algorithm's behavior is determined by two key choices: a distance metric (e.g., Euclidean) and a linkage criterion (e.g., Ward's, Complete, Average).
- The main advantage is not needing to pre-specify . The main disadvantage is its high computational cost, making it less suitable for very large datasets compared to K-Means.
Preview of the Next Lesson:
So far in this module, we have focused on finding groups in our data. But what if our data is too complex, with hundreds or thousands of features? In our next lesson, we will address this by learning about a fundamental technique for simplifying data: Describe Principal Component Analysis (PCA) for dimensionality reduction. PCA helps us reduce the number of variables while preserving as much of the important information as possible.