Different linkage methods used in Agglomerative Clustering

Introduction

Agglomerative clustering is a bottom-up hierarchical clustering technique. It starts with each data point as its own cluster and repeatedly merges the two closest clusters until only one cluster remains (or a stopping criterion is met).

The key design choice in agglomerative clustering is how we define the distance between two clusters. This is known as the linkage method, and it strongly influences the final cluster shapes, robustness to noise, and interpretability.

This article explains the major linkage methods, compares them side by side, and dives deep into a known pitfall: inverted clusters in centroid linkage.

Step-by-Step Procedure to make Agglomerative Clusters

Agglomerative clustering follows a bottom-up process:

• Initialize clusters
  Begin with a collection C of n singleton clusters.
  Each data point is its own cluster:

• Iterative merging
  Repeat until one cluster remains or until a desired number of clusters or the distance threshold is reached:
  • Find the closest pair of clusters
    Identify the two clusters c_i​ and c_j​ that minimize the distance min_{i,j} D(c_i, c_j)
    where D(⋅,⋅) is a chosen distance function between clusters.
  • Merge the closest clusters
    Combine c_i and c_j​ into a new cluster:
    c_new = c_i ∪ c_j
  • Update the cluster set
    Remove c_i and c_j​​ from the collection C, and add the newly formed cluster c_new.

• Repeat until one cluster remains
  This produces a full hierarchy of clusters that captures how groups were formed at each stage.
  

Output: The Dendrogram

The result of agglomerative clustering is a dendrogram, which is a tree-like diagram representing the hierarchical merging of clusters.

• Leaves represent individual data points.
  
• Internal nodes represent merges between clusters.
  
• Height of a merge indicates the distance at which two clusters were joined.
  

By cutting the dendrogram at a chosen height, you can obtain any desired number of clusters.

What Is a Linkage Method?

A linkage method defines how to compute the distance between two clusters based on distances between their constituent points.

Formally, given two clusters ( A ) and ( B ), a linkage method specifies:

1. Single Linkage (Minimum Distance)

Single linkage defines the distance between two clusters as the minimum distance between any pair of points across the clusters:

This approach embodies the idea that two clusters should merge as soon as any two of their points are close. As a result, clusters tend to form based on connectivity rather than overall compactness. Single linkage is particularly effective at identifying arbitrarily shaped or elongated structures, making it well-suited for data with irregular geometries.

However, this same property makes it highly sensitive to noise and outliers. A single stray point can act as a “bridge” between otherwise distinct clusters, leading to the well-known chaining effect, where clusters grow through thin connections rather than cohesive groupings. For this reason, single linkage is best used when the notion of connectivity is important and when clusters are expected to have complex or non-convex shapes.

2. Complete Linkage (Maximum Distance)

Complete linkage takes the opposite approach by defining cluster distance as the maximum distance between any pair of points:

Here, two clusters merge only when all points in one cluster are close to all points in the other. This results in compact, well-separated clusters and largely avoids the chaining effect observed in single linkage. Because of its emphasis on tightness, complete linkage is well-suited for applications where clusters should be clearly bounded and internally cohesive.

The trade-off is increased sensitivity to outliers. A single extreme point can significantly inflate the distance between clusters, potentially delaying or preventing natural merges. Moreover, complete linkage may fragment large clusters that are otherwise meaningful. It is most appropriate when one desires spherical, tightly packed clusters and when outliers have been carefully handled.

3. Average Linkage (UPGMA)

Average linkage defines the distance between two clusters as the average of all pairwise distances between points in the clusters:

This method represents a compromise between single and complete linkage. By considering all point-to-point distances, average linkage smooths out the extremes that drive the behavior of minimum and maximum strategies. The result is a clustering structure that balances compactness with connectivity, often producing more stable and interpretable dendrograms.

While average linkage is less sensitive to outliers than complete linkage and less prone to chaining than single linkage, it is computationally more demanding and still dependent on the choice of distance metric. It is particularly useful when one seeks a middle ground between tightly packed clusters and flexible cluster shapes.

4. Centroid Linkage

Centroid linkage computes the distance between clusters using their centroids (means):

where μ_A​ is the mean of all points in cluster A.

This approach treats each cluster as a single representative point, making it intuitive and computationally efficient. It performs well when clusters are convex, well-separated, and roughly spherical.

However, centroid linkage introduces a significant conceptual issue known as inversions. An inversion occurs when a merge at a higher level of the dendrogram happens at a smaller distance than a merge that occurred earlier, violating the expected monotonic increase in merge distances. This phenomenon arises because merging two clusters can shift their centroid closer to a third cluster than either original centroid was. As a result, the dendrogram may become misleading, and cutting it to obtain a desired number of clusters becomes unreliable. For these reasons, centroid linkage should be used cautiously, particularly when hierarchical interpretability is important.

where μ_A​ is the mean of cluster A.

5. Ward’s Linkage (Variance Minimization)

Ward’s linkage differs fundamentally from the previous methods. Instead of directly using distances between points or centroids, it merges clusters in a way that minimizes the increase in total within-cluster variance. At each step, the pair of clusters whose merger results in the smallest rise in variance is selected.

This strategy tends to produce compact, well-balanced clusters and avoids both chaining and inversions. Because it directly optimizes a variance-based objective, Ward’s method is especially popular in practical applications and is often regarded as one of the most reliable hierarchical clustering techniques.

The primary limitation is its reliance on Euclidean distance and its implicit assumption that clusters are roughly spherical and similarly sized. Consequently, Ward’s method is best applied when features are numeric, well-scaled, and normalized.

Comparison Summary

Video Explanations

• In this short video, we learn the intuition with helpful diagrams about the different measuring distances between clusters (Runtime: ~18 secs)

• This video discusses, how to create clusters using Agglomerative Hierarchical Clustering for the given data point (Runtime: ~6 mins)

• In this video titled “Complete-Linkage Hierarchical Agglomerative Clustering” by Dr. Shaveta Arora, she provides a step by step solution to Complete-Linkage method. (Runtime: ~ 6 mins)

References

• Murtagh & Contreras (2012)
  Algorithms for Hierarchical Clustering: An Overview
  Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery
  https://onlinelibrary.wiley.com/doi/10.1002/widm.53
• Penn State STAT 505 Notes
  Hierarchical Clustering and Linkage Methods
  https://online.stat.psu.edu/stat505/lesson/14

• Scikit-learn Documentation https://scikit-learn.org/stable/modules/clustering.html

Related Articles and Quizzes:

• How does imposing connectivity constraints help with Agglomerative clustering?
• Clustering Quizzes