Understanding Linkage Criteria in Hierarchical Clustering

Introduction

Welcome to our lesson on 'Understanding Linkage Criteria in Hierarchical Clustering'. We will delve into 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. Complementing these understandings, we will also be implementing these linkage criteria using Python with the help of the AgglomerativeClustering class in sklearn.cluster package. Without much ado, let's dive into the journey of hierarchical clustering.

What is linkage and why is it important

Hierarchical clustering is a popular choice for cluster analysis in data mining as it helps visualize the grouping of similar objects to form clusters. In each step of hierarchical clustering, some objects or clusters are linked. These linkages, or merges, are made based on a specific criterion known as 'Linkage Criteria'. Linkage Criteria determine the distance between clusters, and based on these distances, clusters are merged in each step of hierarchical clustering. Linkage methods define how the distance between clusters is measured, and different methods specify different definitions for the concept of cluster distance. Therefore, choosing the right linkage method can significantly influence the shape and size of the clusters. Sounds interesting? Let's explore each of these linkage methods!

Single Linkage

Single Linkage, or 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. In simpler words, single linkage looks for the shortest link or the nearest neighbor. If we think of each cluster represented as a network's node, single linkage corresponds to the shortest edge from node A to node B. Although single linkage can provide 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

On the other end of the spectrum from single linkage is Complete Linkage (or Maximum Intercluster Method). Complete Linkage computes the distance between two clusters as the largest distance from any point in one cluster to any point in another cluster. In other words, it focuses on the furthest points or the furthest neighbors in the clusters. This method works well with clusters compact in nature. It also tends to avoid 'chaining,' resulting in more balanced, even clusters than single linkage.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Comparing Different Linkage Methods

Finally, let's compare different linkage results using the sample code provided. In this code, we will generate synthetic data using the make_blobs function in sklearn.datasets. We then run Agglomerative Clustering using each linkage method and plot the results.

Python

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()

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()

You can compare the results in the following visualization:

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

Introduction

What is linkage and why is it important

Single Linkage

Complete Linkage

Join the 1M+ learners on CodeSignal

Average Linkage

Ward's Method

Comparing Different Linkage Methods

Choosing the Right Linkage Method

Lesson Summary and Practice