Hierarchical Clustering

In the ever-evolving realm of machine learning, where data-driven insights shape industries and innovations, there exists a versatile technique that enables us to uncover patterns, groupings, and relationships hidden within complex datasets. This technique, known as clustering, stands as a cornerstone in the foundation of machine learning's prowess. Clustering empowers computers to unravel intricate patterns within data points, allowing us to make informed decisions, uncover valuable insights, and even untangle the mysteries of the universe on a digital canvas.

What is Clustering?#

There are two main types of clustering algorithms:

Partitional clustering seeks to partition data points into distinct, non-overlapping clusters. Every point is allocated to a single cluster, and the goal is to optimize a specific criterion, such as minimizing the sum of squared distances within clusters. k-means clustering is a widely used partitioning algorithm that divides data into $k$ clusters by considering the proximity of data points to the cluster centroids. It repetitively assigns data points to the nearest centroid and updates the centroid position until the process converges.

Density-based clustering (under partitional clustering) is a technique in machine learning that identifies clusters based on the density of data points. Density-based algorithms uncover clusters of varying shapes and sizes. They work by grouping together data points that are densely packed while separating sparser regions. One of the most notable algorithms in this category is A type of diagram used to visualize hierarchical relationships or clustering of dataDBSCANDensity-Based Spatial Clustering of Applications with Noise, which effectively detects clusters in noisy and complex datasets, making it a valuable tool for uncovering hidden patterns in real-world data.

In this blog, our focus will be mostly on agglomerative clustering within the hierarchical clustering domain.

Hierarchical Clustering#

Hierarchical clustering can further be classified into two main types: agglomerative clustering and divisive clustering.

Agglomerative clustering, referred to as bottom-up clustering, begins by considering each data point as an individual cluster. It then proceeds to iteratively merge the closest clusters until a specified stopping criterion is reached. During each iteration, the two closest clusters are combined into a larger cluster, leading to a hierarchical structure of clusters. Eventually, all data points belong to a single cluster, and the clustering outcome can be visualized as a dendrogram.

Divisive clustering, also known as top-down clustering, takes the opposite approach of agglomerative clustering. The process commences with all data points grouped into one cluster and subsequently proceeds to recursively divide the clusters into smaller ones until a specified stopping criterion is achieved. In each iteration, the algorithm selects a cluster and divides it into two or more smaller clusters based on a specified criterion. This process continues recursively until each data point is assigned to its own individual cluster.

Agglomerative Clustering#

As discussed previously, agglomerative clustering initiates with each data point considered as an individual cluster and gradually merges the closest clusters iteratively until all data points belong to a single cluster. It forms a hierarchy of clusters, which can be visualized as a dendrogram.

There are several types of strategies within agglomerative clustering:

• Single linkage: This strategy measures the distance between two clusters by considering the minimum distance between any pair of points within them. It tends to create long, elongated clusters and is sensitive to noise and outlier data points.

• Complete linkage: This strategy measures the distance between two clusters based on the greatest distance between any pair of points within the clusters. It focuses on the farthest points, potentially resulting in compact, spherical clusters.

• Average linkage: This strategy calculates the mean distance between all pairs of points in two clusters. It aims to balance the effect of outliers and tends to produce clusters of relatively equal size.

• Ward’s algorithm: This strategy aims to minimize the increase in the sum of squared distances when merging clusters, merging the closest clusters based on the within-cluster variance.

The following table discusses the main differences, advantages, and disadvantages of these different strategies:

The main differences in calculation between the different strategies (i.e., single, average, and complete) in agglomerative clustering lie in measuring the minimum distance, maximum distance, and average distance between points in different clusters, respectively. Below, we will see the single linkage method algorithm in more detail with an example.

Single Linkage Algorithm#

1. Start with each data point as an individual cluster.

2. Calculate the distance matrix, which represents the pairwise distances between each pair of clusters based on the minimum distance between any two points in the clusters.

3. Determine the pair of clusters exhibiting the smallest distance in the distance matrix.

4. Merge the two closest clusters into a new cluster.

5. Update the distance matrix by recalculating the distances between the new cluster and the remaining clusters using the minimum distance criterion.

6. Repeat steps 2–5 until all data points belong to a single cluster or until a desired number of clusters is achieved.

7. The final result is a dendrogram or a set of clusters obtained based on the merging order.

Example#

Let’s walk through an example of the single linkage method step by step. Suppose we have the following data points in a two-dimensional space:

• Step 1: Start by considering each data point as an individual cluster. Clusters: $[A]$, $[B]$, $[C]$, $[D]$, $[E]$

• Step 2: Calculate the distance between every cluster pair using the single linkage method, which is based on the shortest distance between any two points within the clusters.

• Step 3: Determine the pair of clusters with the smallest distance between them and combine them together to form a new cluster. From the above table, we see that the distance between points $A$ and $B$ is 1.414, which is also the distance between points $D$ and $E$. Therefore, we can do the following:

  • Merge $[A]$ and $[B]$ into $[A, B]$

  • Merge $[D]$ and $[E]$ into $[D, E]$

  • Updated clusters: $[A, B]$, $[C]$, $[D, E]$

• Step 4: Recalculate the distances between the new cluster $[A, B]$, $[C]$, and $[D, E]$:

  • Distance between $[A, B]$ and $[C]$= $min(dist(A, C), dist(B, C))$ = $min(sqrt((5-2)^2 + (8 - 5)^2), sqrt((5-3)^2 + (8-4)^2))$ = 4.243

  • Distance between $[A, B]$ and $[D, E]$= Minimum distance between any point in $[A, B]$ and any point in $[D, E]$ = $min(dist(A, D), dist(A, E), dist(B, D), dist(B, E)$ = $min(sqrt((6 - 2)^2 + (2 - 5)^2), sqrt((7 - 2)^2 + (3 - 5)^2, sqrt((6 - 3)^2 + (2 - 4)^2), sqrt((7 - 3)^2 + (3 - 4)^2))$= 3.162

  • Distance between $[C]$ and $[D, E]$= $min(dist(C, D), dist(C,E)$ = $min(sqrt((5 - 6)^2 +(8 - 2)^2), sqrt(5 - 7)^2, sqrt(8 - 3)^2))$= 5.385

• Step 5: Identify the pair of clusters with the minimum distance and combine them to form a new cluster:

  • Merge $[A, B]$ and $[D, E]$ into $[[A, B], [D, E]]$

  • Updated clusters: $[[A, B], [D, E]]$, $[C]$

• Step 6: Recalculate the distances between the new cluster $[[A, B], [D, E]]$ and $[C]$:

  • Distance between $[[A, B], [D, E]]$ and $[C]$= Minimum distance between any point in $[[A, B], [D, E]]$ and $[C]$ = 4.243

• Step 7: Identify the cluster pair with the smallest distance and amalgamate them into a new cluster:

  • Merge $[[A, B], [D, E]]$ and $[C]$ into $[[[A, B], [D, E]], [C]]$

  • Final cluster: $[[[A, B], [D, E]], [C]]$

Note that the other methods, namely complete linkage and average linkage methods, will essentially follow the same steps. The difference is only when the distances are recalculated. For example, in the complete linkage method, instead of min, the max method is used.

Let’s have a quick look at Ward’s algorithm.

Ward's Algorithm#

Ward’s algorithm falls under the category of “centroid-based” linkage methods. It is related to the average linkage method.

In Ward’s algorithm, at every iteration, the two clusters with the smallest increase in the Ward’s criterion (sum of squared distances within clusters) are merged into a new cluster. The Ward’s criterion measures the increase in variance when two clusters are merged. It aims to minimize the increase in variance within the newly formed cluster after merging.

Example#

Suppose we have the following dataset with three data points (A, B, and C) in a one-dimensional space:

$A(3), B(7), C(10)$

• Step 1: Start with each data point as an individual cluster: $[A], [B], [C]$

• Step 2: Calculate the distance for every combination of cluster pairs:

  • Distance between $[A]$ and $[B]$= |3 - 7| = 4

  • Distance between $[A]$ and $[C]$= |3 - 10| = 7

  • Distance between $[B]$ and $[C]$= |7 - 10| = 3

• Step 3: Merge the two clusters that lead to the smallest increase in the Ward’s criterion. Since the minimum distance is 3 between $[B]$ and $[C]$, we merge them into a new cluster ${[B, C]}$.

  • Updated clusters: ${[A]}$, ${[B, C]}$

• Step 4: Recalculate the distance between the new clusters and the remaining cluster(s):

  • Distance between $[A]$ and ${[B, C]}$= |3 - 8.5| = 5.5

  • Final cluster: $[[A,[B,C]]$

Conclusion and Next Steps#

The single linkage method has the advantage of being computationally efficient and capable of detecting elongated and irregularly shaped clusters. However, it is sensitive to noise and outliers, as it tends to create long, chaining clusters. This sensitivity can lead to the formation of false connections between distant points.

Ward’s algorithm is a powerful technique used in data analysis and machine learning to group similar data points together based on their distance or dissimilarity. The algorithm aims to minimize the variance within clusters as it merges data points into clusters, leading to a hierarchical structure of clustered data.

For a much deeper dive into clustering and machine learning, we recommend exploring the following courses: