Hierarchical Clustering: Complete Guide — Principles, Examples and Python Implementation

Summary

Hierarchical clustering is one of the oldest and most intuitive unsupervised classification methods in machine learning. Unlike K-Means, which partitions data into a fixed number of groups, hierarchical clustering builds a tree representation of all possible partitions, from the finest level (each observation forms its own cluster) to the coarsest level (all observations merge into a single group). This structure is called a dendrogram and is the characteristic element of the method.

This guide covers the complete mathematical principle, the different strategies for computing distance between clusters (Ward, single linkage, complete linkage, average), practical implementation with scipy and scikit-learn, as well as advantages, limitations, and concrete use cases.

Mathematical Principle

Hierarchical clustering comes in two fundamental approaches that differ in their construction direction.

Agglomerative Approach (Bottom-Up)

This is by far the most commonly used approach in practice. The process starts with each observation in its own cluster, meaning n clusters for n data points. At each step, the two closest clusters are identified and merged. This process is repeated until all observations are grouped into a single cluster. This produces exactly n − 1 merges and a complete dendrogram.

Algorithmically:

1. Initialization: each point xᵢ forms a singleton Cᵢ = {xᵢ}.
2. Compute the proximity matrix D between all pairs of clusters.
3. Find the pair (Cᵢ, Cⱼ) minimizing D(Cᵢ, Cⱼ).
4. Merge Cᵢ and Cⱼ into a new cluster.
5. Update the distance matrix.
6. Repeat from step 3 until a single cluster is obtained.

The naive complexity is O(n³) time and O(n²) memory, since an n × n distance matrix must be computed and maintained. Optimizations like the SLINK algorithm achieve O(n²) for single linkage.

Divisive Approach (Top-Down)

The divisive approach works in reverse: it starts with all observations in a single cluster and recursively divides the most heterogeneous cluster until n singleton clusters are obtained. This approach is much more expensive (exponential complexity in the general case) and requires heuristics to be practical, such as using K-Means with K=2 at each division step.

Distance Between Clusters: Linkage Methods

The central question of hierarchical clustering is: how do you measure the distance between two clusters? Each cluster potentially contains multiple points, and there are several ways to define this inter-cluster distance. These choices are called linkage methods.

Single Linkage

The distance between two clusters is the minimum distance between a pair of points, one in each cluster:

D_single(Cᵢ, Cⱼ) = min{ d(x, y) | x ∈ Cᵢ, y ∈ Cⱼ }

This method tends to create elongated and chained clusters, because a single bridge of close points linking two groups is enough to consider them as one cluster. This is called the chaining effect. It is sensitive to noise but excellent at detecting non-globular structures.

Complete Linkage

The distance between two clusters is the maximum distance between a pair of points:

D_complete(Cᵢ, Cⱼ) = max{ d(x, y) | x ∈ Cᵢ, y ∈ Cⱼ }

This approach favors compact clusters of reduced diameter, because two clusters only merge if all their mutual points are reasonably close. It is more robust to noise than single linkage, but can artificially separate natural elongated-shaped clusters.

Average Linkage (UPGMA)

The distance between two clusters is the average of all distances between pairs of points:

D_average(Cᵢ, Cⱼ) = (1 / |Cᵢ| × |Cⱼ|) × Σ d(x, y)  for x ∈ Cᵢ, y ∈ Cⱼ

This is a compromise between the two previous methods. It is often considered a good default choice because it avoids both the excessive chaining of single linkage and the excessive compactness of complete linkage.

Ward’s Method

Ward’s criterion is the most sophisticated of the four. Instead of directly measuring the distance between points, it minimizes the increase in intra-class inertia (the sum of squared deviations from the mean of each cluster) resulting from the merge:

D_ward(Cᵢ, Cⱼ) = (|Cᵢ| × |Cⱼ| / (|Cᵢ| + |Cⱼ|)) × ||μᵢ − μⱼ||²

where μᵢ and μⱼ are the respective centroids of the two clusters.

Ward always merges the pair of clusters whose union increases the overall intra-cluster variance the least. The result resembles a hierarchical K-Means: it produces globular clusters of balanced sizes. It is the default method in most modern implementations.

Distance Matrix and Dendrogram Construction

All these methods operate on an n × n distance matrix, where each entry D[i, j] represents the distance (Euclidean, Manhattan, cosine, etc.) between observations i and j.

As merges progress, the matrix is updated according to the formula of the chosen linkage method. Each merge step is recorded with:

• The indices of the two clusters merged;
• The distance at which the merge occurred;
• The number of elements in the new cluster.

The set of these records forms the dendrogram, a binary tree whose leaves are the individual observations and whose internal nodes represent successive merges. The height of each node corresponds to the merge distance.

Intuition: Understanding the Dendrogram

Imagine a reversed family tree. In a traditional tree, you start with distant ancestors and descend toward present generations. Hierarchical clustering does the opposite: it starts with each point alone (the most recent generation) and goes back in time by merging the closest groups, until finding a single common ancestor.

The dendrogram visualizes exactly this process. On the horizontal axis, you see the observations (or groups of observations). On the vertical axis, you read the distance or dissimilarity at which each merge occurred.

The decisive advantage of the dendrogram is that it doesn’t force you to choose a number of clusters in advance. You can cut the tree at any height:

• A high cut produces few, very general clusters.
• A low cut produces many, very specific clusters.
• You can visually observe height jumps: a large vertical gap between two merges suggests a natural boundary between macro-groups.

This flexibility is what makes hierarchical clustering so valuable for data exploration: even before choosing a number of clusters, you can see the hierarchical structure of your data.

Python Implementation

Let’s see how to implement hierarchical clustering in Python, using both scipy for dendrogram creation and scikit-learn for cluster assignment.

Dendrogram with scipy

The scipy library provides the linkage function to compute the hierarchical tree and dendrogram to visualize it:

import numpy as np
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import linkage, dendrogram, cut_tree
from sklearn.datasets import make_blobs

# Generate synthetic data
X, y_true = make_blobs(
    n_samples=200,
    n_features=2,
    centers=4,
    random_state=42
)

# Compute hierarchical clustering (Ward method)
Z = linkage(X, method='ward', metric='euclidean')

# Display the dendrogram
plt.figure(figsize=(12, 6))
dendrogram(
    Z,
    truncate_mode='level',
    p=10,
    leaf_font_size=9
)
plt.title('Dendrogram — Hierarchical Clustering (Ward)')
plt.xlabel('Observations')
plt.ylabel('Merge distance')
plt.axhline(
    y=15, color='red', linestyle='--',
    label='Cut threshold'
)
plt.legend()
plt.tight_layout()
plt.show()

The horizontal red line represents a cut threshold: any merge above this line is ignored, which determines the final number of clusters.

Assignment with scikit-learn

To get cluster labels directly, scikit-learn offers AgglomerativeClustering:

from sklearn.cluster import AgglomerativeClustering

# Ward method
agglo = AgglomerativeClustering(
    n_clusters=4,
    linkage='ward',
    metric='euclidean'
)
labels_ward = agglo.fit_predict(X)

# Result visualization
plt.figure(figsize=(10, 6))
scatter = plt.scatter(
    X[:, 0], X[:, 1],
    c=labels_ward, cmap='viridis',
    s=40, alpha=0.8, edgecolors='k'
)
plt.colorbar(scatter, label='Cluster')
plt.title('Hierarchical Clusters — Ward Linkage')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.tight_layout()
plt.show()

Comparing Linkage Methods

Here’s how to compare the four methods on the same data:

from sklearn.cluster import AgglomerativeClustering
import matplotlib.pyplot as plt

linkages = ['ward', 'complete', 'average', 'single']

fig, axes = plt.subplots(2, 2, figsize=(14, 10))
axes = axes.ravel()

for i, method in enumerate(linkages):
    if method == 'ward':
        agglo = AgglomerativeClustering(
            n_clusters=4, linkage=method
        )
    else:
        agglo = AgglomerativeClustering(
            n_clusters=4, linkage=method,
            metric='euclidean'
        )
    labels = agglo.fit_predict(X)

    axes[i].scatter(
        X[:, 0], X[:, 1],
        c=labels, cmap='viridis',
        s=35, alpha=0.8, edgecolors='k'
    )
    axes[i].set_title(f'Linkage: {method}')
    axes[i].set_xlabel('Feature 1')
    axes[i].set_ylabel('Feature 2')

plt.suptitle('Comparison of Linkage Methods')
plt.tight_layout()
plt.show()

You will observe that:

• Ward produces balanced, globular clusters, close to what K-Means would produce.
• Complete tends to create more compact clusters, sometimes more numerous in dense areas.
• Average offers a good compromise with smooth boundaries.
• Single is the most likely to create chained clusters, linking distant groups through bridges of isolated points.

Cutting the Dendrogram with scipy

If you work directly with scipy, the cut_tree function allows you to extract clusters at a given level:

from scipy.cluster.hierarchy import cut_tree

# Cut to get exactly 4 clusters
labels = cut_tree(Z, n_clusters=4).ravel()

# Or cut at a specific distance height
labels_threshold = cut_tree(Z, height=10).ravel()
print(f'Number of clusters at threshold 10: {len(np.unique(labels_threshold))}')

The height-based approach (rather than a fixed number) is consistent with the hierarchical philosophy: you define the desired level of granularity, and the algorithm automatically determines how many clusters this produces.

Hyperparameters

Hierarchical clustering has few hyperparameters, but each has a major impact on the results.

n_clusters (Number of Clusters)

This is the main parameter if you’re using scikit-learn’s AgglomerativeClustering. Alternatively: distance_threshold allows you to specify a cut height in the dendrogram instead of a fixed number. If you use distance_threshold, then n_clusters must be set to None.

linkage (Linkage Method)

The choice between ward, complete, average, and single is the most important structural determinant. In practice:

• Ward is the best default choice for numerical data without special structure.
• Average is a good second choice if Ward doesn’t converge (non-Euclidean metric).
• Complete and Single are mainly used for exploration to understand the structure of the data.

metric (Distance Metric)

The default metric is Euclidean distance, but others are possible depending on the context. For text, cosine is relevant. For geographic data, Haversine is appropriate. Note: Ward’s method is only valid with a Euclidean distance metric.

distance_threshold

Rather than setting a number of clusters, you can define a maximum merge distance. Two clusters only merge if they are within this distance of each other. This produces a number of clusters that depends on the natural structure of the data.

Advantages and Limitations

Advantages

• No need to specify K in advance: the dendrogram allows exploring all possible granularities.
• Deterministic result: unlike K-Means which depends on random initialization, hierarchical clustering always produces the same result on the same data.
• Superior interpretability: the dendrogram is a powerful visualization tool that reveals the natural structure of the data.
• Metric flexibility: works with any dissimilarity measure (Euclidean, Manhattan, cosine, correlation, etc.).
• Rich hierarchy: the result is not just a partition but a complete multi-level organization.
• Ideal for small datasets: produces excellent results on moderately sized datasets.

Limitations

• O(n³) complexity: the naive algorithm is very expensive on large data volumes. Optimized variants achieve O(n²), but this remains prohibitive beyond tens of thousands of points.
• Non-incremental: once the tree is built, adding a new data point requires recalculation (or the use of approximations).
• Sensitivity to noise and outliers: particularly true for single linkage.
• Irreversibility of merges: once two clusters are merged, the decision is final. An early error propagates (the cascade effect problem).
• Ward requires Euclidean: Ward’s method only works with Euclidean distance, which limits its flexibility.

4 Concrete Use Cases

1. Biological Taxonomy and Species Classification

Hierarchical clustering historically originated from systematic biology. Phylogeneticists use it to build evolutionary trees from genetic distances between species. The average linkage method (UPGMA) is particularly well suited as it provides an estimate of the divergence time between two groups.

2. Customer Segment Analysis in Marketing

Marketing teams use it to identify hierarchical segments: first the large customer families (individuals vs. professionals), then the sub-segments (young urban dwellers, families, retirees…). The dendrogram allows choosing the level of segmentation relevant to the business strategy.

3. Document Clustering and Thematic Organization

In natural language processing, hierarchical clustering allows organizing documents into themes and sub-themes. For example, a corpus of press articles can be structured into major categories (politics, economy, sport) and then into sub-categories (elections, financial markets, football…). Cosine similarity between TF-IDF vectors serves as the distance metric.

4. Medical Image Analysis

In medical imaging, hierarchical clustering is used for image segmentation. Pixels are grouped according to their intensity and spatial proximity, creating a hierarchy of regions that can be cut at different levels depending on the desired segmentation fineness. This multi-scale approach is particularly useful for detecting lesions of varying sizes.

See Also

• Master Triffle Numbers in Python: Complete Guide for Developers
• Demystify the ‘abc’ Module in Python: Complete Guide with Practical Examples