Linkage Criteria in Hierarchical Clustering: A Tutorial

Welcome to our tutorial on linkage criteria in hierarchical clustering! In this lesson, we will explore specific linkage criteria and their role in hierarchical clustering. Our main objective is to explain four types of linkage criteria: Single, Complete, Average linkage, and Ward’s method. We will also demonstrate how to implement these criteria using Python with the AgglomerativeClustering class from the sklearn.cluster package. Let’s dive into the journey of hierarchical clustering without further ado.

What is Linkage and Why is it Important?

Hierarchical clustering is a favored method for cluster analysis in data mining, as it helps visualize the grouping of similar objects into clusters. In each step of hierarchical clustering, some objects or clusters are linked based on a specific criterion known as Linkage Criteria.

Linkage Criteria determine the distance between clusters and dictate how clusters are merged at each step of hierarchical clustering. Different linkage methods define how the distance between clusters is measured, each providing a unique definition of cluster distance.

Choosing the right linkage method can significantly influence the shape and size of the clusters. Let’s explore each of these linkage methods in detail.

Single Linkage

Single Linkage, also known as the Minimal Intercluster Method, computes the distance between two clusters as the smallest distance from any point in one cluster to any point in the other cluster. This method looks for the shortest link or the nearest neighbor. Although single linkage can produce fine, detailed dendrograms and handle non-elliptical shapes, it can sometimes result in ‘chaining’, where clusters may be forced together due to a single close pair of points.

Complete Linkage

Complete Linkage, or Maximum Intercluster Method, computes the distance between two clusters as the largest distance from any point in one cluster to any point in another cluster. This method focuses on the furthest points or the furthest neighbors in the clusters and works well with clusters that are compact in nature. It also tends to avoid ‘chaining’, resulting in more balanced, even clusters than single linkage.

Average Linkage

The Average Linkage method computes the distance between two clusters as the average distance from all pairs of points, one point in each cluster. This method is less susceptible to noise and outliers and creates clusters of roughly equal diameters, though it may favor globally compact clusters over small local minima.

Ward’s Method

Ward’s Method, distinct from the other three, calculates the sum of squared Euclidean distances to the centroids of the clusters, aiming to create compact clusters of roughly equal size. The primary intention of Ward’s method is to minimize the total within-cluster variance, choosing the cluster pair to merge such that the increase in total within-cluster variance is the smallest possible.

Choosing the Right Linkage Method

The choice of linkage method in hierarchical clustering mainly depends on the problem domain, shape of data, and specific requirements of our clustering task.

Here are some factors to consider when choosing the right linkage method:

• Single Linkage: This method is a good option when we intend to capture insight into the data’s fine granularity. It works well when the clusters naturally have a chain-like or non-compact structure. However, it may produce elongated and less balanced clusters due to its sensitivity to outliers and noise.
• Complete Linkage: This method might be the choice when we want more balanced, compact, and well-separated clusters. It is less prone to chaining effects but may break large clusters, leading to less-optimal global solutions.
• Average Linkage: This method strikes a balance between single and complete linkage. It is less sensitive to noise and outliers and usually produces well-defined and balanced clusters. It works great when the clusters are relatively similar in terms of diameters.
• Ward’s Method: This method seeks to minimize the total within-cluster variance, so it usually generates more uniform-sized, tightly packed clusters. It is a nice choice when we expect clusters to have similar sizes or to be compact and isolated. However, Ward’s method could be biased towards globular clusters.

Remember, there’s no universal best choice for all datasets and scenarios. The choice of the linkage method should be based on the nature of the data, problem-specific requirements, and the results of our clustering, validated by domain knowledge. Experimenting with different linkage methods and evaluating their performances can also be helpful to find the right method.

Comparing Different Linkage Methods

Let’s compare different linkage results using the sample code provided. We will generate synthetic data using the make_blobs function from sklearn.datasets and run AgglomerativeClustering using each linkage method to plot the results.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import AgglomerativeClustering

# Generate synthetic data
X, _ = make_blobs(n_samples=150, centers=4, cluster_std=1.2, random_state=42)

# Define the different linkage methods to be compared
linkage_methods = ['single', 'complete', 'average', 'ward']

# Create subplots with 2 rows and 2 columns and flatten the axs array for easier indexing
fig, axs = plt.subplots(2, 2, figsize=(10, 10))
axs = axs.flatten()

# Loop through each linkage method and apply Agglomerative Clustering
for i, linkage in enumerate(linkage_methods):
    clustering = AgglomerativeClustering(n_clusters=4, linkage=linkage)
    labels = clustering.fit_predict(X)
    # Plot the clusters
    axs[i].scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', marker='o', edgecolor='k')
    axs[i].set_title(f'Linkage: {linkage}')
    axs[i].set_xlabel('Feature 1')
    axs[i].set_ylabel('Feature 2')
    axs[i].grid(True)
plt.tight_layout(pad=3.0)
plt.show()

This visual comparison can give you a clear understanding of how different linkage methods can lead to entirely different clustering results.

Lesson Summary and Practice

In this lesson, we dove deep into the four fundamental types of linkage criteria: Single, Complete, Average linkage, and Ward’s method. We learned their working mechanisms, implemented them in Python, and understood their distinct roles in hierarchical clustering. We observed the effects of these linkage methods in real time through a visual comparison.

Upcoming practice exercises will test and cement your newly gained wisdom about these crucial concepts in hierarchical clustering. Keep learning, and enjoy the journey!

For further reading, check out this Sklearn documentation on Agglomerative Clustering.