# Hierarchical Clustering

Building a tree of nested clusters by successively merging or splitting, visualised as a dendrogram.

**Rests on:** Binary Tree Traversal

*Machine Learning · Unsupervised Learning*


## Why learn this

This lets you find natural groupings in data without guessing how many groups exist ahead of time. Imagine you have a list of customer profiles and you want to segment them for marketing, but you do not know if there are 3, 5, or 10 distinct types of customers. This method builds a complete map of relationships, allowing you to explore the structure of the data first and decide on the number of groups only after seeing how tightly everything connects. You can then move on to other techniques that require a fixed number of groups, like k-means, with a clearer understanding of your data.


## The intuition

Imagine a scattered collection of points on a map. Hierarchical clustering starts by treating each point as its own tiny group. Then, it repeatedly finds the two groups that are closest together and merges them. Each merge creates a larger group. You repeat this until everything is one big group. The result is a tree diagram, which we will call a dendrogram, that shows every merge from the bottom (where every point is alone) to the top (where everyone is together). This tree is the product, not just a flat list of groups. You can 'cut' this tree at any height to get a specific number of clusters: cut low near the bottom and you get many small groups; cut high up and you get a few large ones. You never need to decide the number of groups in advance. For example, if you have 10 points, you might cut the tree to get 3 groups after seeing which natural separations exist. The same idea works in reverse: starting with one big group and splitting it, but the merging version is most commonly used.


## An analogy

You are organizing a large extended family for a reunion. You begin with every person as their own separate unit. Then you look for the two people who are closest — say, two siblings who both live in the same town — and you group them. Now you have a new unit: that sibling pair. Next, you find the closest pair among all your units, which might be the sibling pair and a cousin who lives nearby, so you merge again. Over many steps, you merge the closest units until the whole extended family is one tree. The key is that you never said 'I want five families' at the start. You just kept merging the closest. The resulting family structure lets you decide later, after seeing the whole layout, that you want to group at the level of immediate households, or at the level of the whole clan. Caveat: unlike real families where connections are fixed by blood, these clusters are formed purely by the distance metric you choose.


## Definition

Hierarchical clustering is a method that builds a nested tree of groups by repeatedly merging the two closest groups based on a rule for measuring distance between sets, resulting in a dendrogram that visualizes all possible groupings at once.


## How it connects

This sits beside k-means clustering, which also groups data but requires you to fix the number of groups beforehand and assumes groups are roughly spherical. It differs from DBSCAN, which labels some points as noise rather than placing every point in a nested structure. Both methods fall under Unsupervised Learning, where there is no predefined label to predict, making validation more challenging because you lack ground truth.


## The mathematics

Hierarchical clustering builds a tree of groups by repeatedly joining the two closest groups. It starts with each data point as its own group and ends with one big group containing all points. The key mathematical task is defining what "closest" means when comparing two groups that contain multiple points.

To compare any two individual points, we use Euclidean distance. If you have two points in space, the distance between them is the length of the straight line connecting them. For a point with coordinates (x1, x2, ..., xn) and another with (y1, y2, ..., yn), the distance d is calculated by taking the difference in each coordinate, squaring those differences, adding them all up, and then taking the square root of that sum.

d(point1, point2) = sqrt( (x1-y1)^2 + (x2-y2)^2 + ... + (xn-yn)^2 )

When we have two groups of points, let's call them Group A and Group B, we need a rule to turn all the distances between every point in A and every point in B into a single number. This number is called the linkage distance.

There are three common rules:

1. Single Linkage (Nearest Neighbor)
This rule looks at every possible pair of points where one point is in Group A and the other is in Group B. It picks the smallest distance among all those pairs. Imagine two clouds of dots; single linkage measures the shortest gap between any dot in the first cloud and any dot in the second cloud.

d(A, B) = the minimum value of d(p, q) for all p in A and all q in B

2. Complete Linkage (Furthest Neighbor)
This rule also looks at every possible pair of points between Group A and Group B. But instead of picking the smallest distance, it picks the largest distance. This ensures that no point in one group is too far from any point in the other group.

d(A, B) = the maximum value of d(p, q) for all p in A and all q in B

3. Average Linkage (Group Average)
This rule calculates the average distance between all pairs of points across the two groups. It takes every possible pair (p from A, q from B), finds the distance for each pair, adds them all together, and divides by the total number of pairs.

d(A, B) = (sum of d(p, q) for all p in A and all q in B) divided by (number of points in A times number of points in B)

The algorithm works like this:
1. Start with N groups, each containing one data point.
2. Calculate the linkage distance between every pair of existing groups using your chosen rule.
3. Find the two groups with the smallest linkage distance.
4. Merge those two groups into a single new group.
5. Repeat steps 2-4 until only one group remains.

This process creates a hierarchy. We can visualize it as a dendrogram, which is a tree diagram. The bottom of the tree shows the individual points. As you move up, branches merge. The height of each merge point on the vertical axis represents the linkage distance at which the two sub-groups were joined. To get a final set of clusters, you draw a horizontal line across the tree at a chosen height. Any branch that crosses this line becomes a separate cluster.

Note on Choice of Linkage:
Single linkage tends to produce long, chain-like clusters because it only cares about one close connection between groups. Complete linkage tends to produce compact, spherical clusters because it forces all points in a group to be close to each other. Average linkage is a compromise between these two extremes.


## A worked example

Let us cluster five points located on a single number line (1D space). Because they are on a line, the Euclidean distance between any two points is simply the absolute difference between their values.

The points are:
A at position 1
B at position 2
C at position 5
D at position 6
E at position 9

We will use Single Linkage. This means the distance between two groups is the smallest distance between any point in the first group and any point in the second group.

Step 1: Calculate distances between all individual points.
The distance between A and B is |1 - 2| = 1.
The distance between B and C is |2 - 5| = 3.
The distance between C and D is |5 - 6| = 1.
The distance between D and E is |6 - 9| = 3.
All other pairs (like A to C) are larger than these. The smallest distances in the entire dataset are 1, occurring between (A,B) and (C,D).

Step 2: Merge the closest pair.
We have a tie for the smallest distance (1). Let's merge A and B first because they appear first in our list. 
New Group AB contains {A, B}. Its positions are {1, 2}.
The remaining groups are {AB}, {C}, {D}, {E}.

Step 3: Calculate distances from the new group AB to the others.
Distance between Group AB and Group C:
We check all pairs between {A,B} and {C}.
Distance(A, C) = |1 - 5| = 4.
Distance(B, C) = |2 - 5| = 3.
The single linkage distance is the minimum of these: min(4, 3) = 3.

Distance between Group AB and Group D:
We check all pairs between {A,B} and {D}.
Distance(A, D) = |1 - 6| = 5.
Distance(B, D) = |2 - 6| = 4.
The single linkage distance is min(5, 4) = 4.

Distance between Group AB and Group E:
We check all pairs between {A,B} and {E}.
Distance(A, E) = |1 - 9| = 8.
Distance(B, E) = |2 - 9| = 7.
The single linkage distance is min(8, 7) = 7.

Current distances from AB: to C is 3, to D is 4, to E is 7.
Distances between remaining singletons: C to D is 1, D to E is 3.

Step 4: Merge the next closest pair.
The smallest distance in the current set of groups is 1, between C and D. 
Merge C and D into Group CD. Positions are {5, 6}.
The remaining groups are {AB}, {CD}, {E}.

Step 5: Calculate distances from the new group CD to the others.
Distance between Group AB and Group CD:
We check all pairs between {A,B} and {C,D}.
Pairs are: (A,C), (A,D), (B,C), (B,D).
Distances: |1-5|=4, |1-6|=5, |2-5|=3, |2-6|=4.
The single linkage distance is min(4, 5, 3, 4) = 3.

Distance between Group CD and Group E:
We check all pairs between {C,D} and {E}.
Pairs are: (C,E), (D,E).
Distances: |5-9|=4, |6-9|=3.
The single linkage distance is min(4, 3) = 3.

Current distances: AB to CD is 3. CD to E is 3. 

Step 6: Merge the next closest pair.
We have a tie for the smallest distance (3). Let's merge AB and CD first.
New Group ABCD contains {A, B, C, D}. Positions are {1, 2, 5, 6}.
The remaining groups are {ABCD}, {E}.

Step 7: Calculate distance between the final two groups.
Distance between Group ABCD and Group E:
We check all pairs between {A,B,C,D} and {E}.
Distances: |1-9|=8, |2-9|=7, |5-9|=4, |6-9|=3.
The single linkage distance is min(8, 7, 4, 3) = 3.

Step 8: Final Merge.
Merge ABCD and E into the final group {A,B,C,D,E}. The merge height is 3.

Summary of Merges (Heights):
1. A and B merged at height 1.
2. C and D merged at height 1.
3. Group AB and Group CD merged at height 3.
4. Group ABCD and Group E merged at height 3.

Interpreting the Clusters:
The dendrogram has merges at heights 1, 1, 3, and 3.
If you cut the tree horizontally at a height of 1.5, you slice through the branches above the first two merges but below the next ones. The clusters remaining are {A,B}, {C,D}, and {E}.
If you cut the tree horizontally at a height of 2.5, you slice through the branches above all merges up to height 1, but below the merges at height 3. The clusters remaining are {A,B,C,D} and {E}.


## From scratch, in Python

```python
# Hierarchical clustering with single linkage, from scratch

def distance(p, q):
    """Euclidean distance between two points."""
    # p and q are lists of numbers, e.g. [1, 2]
    # We'll compute the sum of squared differences, then take the square root.
    sum_sq = 0
    for i in range(len(p)):
        sum_sq += (p[i] - q[i]) ** 2
    return sum_sq ** 0.5

# Example points (1D for simplicity, but works for any dimension)
points = {
    'A': [1],
    'B': [2],
    'C': [5],
    'D': [6],
    'E': [9],
}

# We'll build a list of clusters, each cluster is a set of point labels.
clusters = [{label} for label in points]  # each point starts in its own cluster

# Loop until all points are in one cluster
while len(clusters) > 1:
    # Find the closest pair of clusters under single linkage
    best_pair = None
    best_dist = float('inf')
    for i in range(len(clusters)):
        for j in range(i + 1, len(clusters)):
            # Single linkage: minimum distance between any point in cluster i and any in cluster j
            min_dist = float('inf')
            for a in clusters[i]:
                for b in clusters[j]:
                    d = distance(points[a], points[b])
                    if d < min_dist:
                        min_dist = d
            if min_dist < best_dist:
                best_dist = min_dist
                best_pair = (i, j)

    # Merge the two closest clusters
    i, j = best_pair
    merged = clusters[i] | clusters[j]  # set union
    # Remove the two old clusters (note: remove j first to not shift indices)
    if i > j:
        del clusters[i]
        del clusters[j]
    else:
        del clusters[j]
        del clusters[i]
    clusters.append(merged)
    print(f"Merged at distance {best_dist:.2f}: {merged}")

print("Final cluster:", clusters[0])
```


## The same thing, with a framework

```python
# Using scikit-learn
from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_blobs
import numpy as np

# Generate some example data
X, _ = make_blobs(n_samples=30, centers=3, random_state=42)

# Create the model with 3 clusters (we could also cut the dendrogram)
model = AgglomerativeClustering(n_clusters=3, linkage='ward')
labels = model.fit_predict(X)
print(labels)

# For a dendrogram, use scipy
from scipy.cluster.hierarchy import dendrogram, linkage
Z = linkage(X, method='ward')
# You would plot this with: dendrogram(Z)
```


## What the code does

The from-scratch code implements single-linkage hierarchical clustering. It starts by defining a `distance` function that computes Euclidean distance between two points, using a loop over each coordinate. Then it creates a set of clusters, each containing one point label. The main loop runs while there is more than one cluster. Inside, it iterates over all pairs of clusters, and for each pair it computes the minimum distance between any point in the first cluster and any point in the second — that's single linkage. It remembers the closest pair and, after the search, merges them using set union. It then deletes the two old clusters and appends the new one. The loop continues until one cluster remains. The framework version uses scikit-learn's `AgglomerativeClustering` with the `ward` linkage (a variance-based method), which is common for balanced clusters. It returns labels directly. For the dendrogram, scipy's `linkage` function computes the tree, which you can then plot. The library is doing exactly the same kind of merging, but optimised with efficient data structures.


## Common misconceptions

**The dendrogram height is a number of clusters.** — The vertical axis on the dendrogram counts clusters, like '3 means 3 clusters'.

The vertical axis represents the distance (dissimilarity) at which clusters merged. The number of clusters is the number of branches you see when you cut horizontally at that height, which depends on the data. In fact: The height is a distance value. To get k clusters, you cut the tree at a height that leaves exactly k branches.

**There is one correct clustering.** — Once I run the algorithm, I have found the one true grouping of my data.

Different distance metrics and linkage criteria will produce different trees. Moreover, the choice of cut level changes the number of clusters. Clustering is exploratory, not ground truth. In fact: The dendrogram is a hypothesis about structure; the analyst chooses the cut based on domain knowledge.

**Single linkage is always the best.** — The simplest linkage (single) is the most accurate.

Single linkage can create long, chain-like clusters where distant points become connected through a series of close neighbours, which may not reflect the true structure. In fact: Linkage choice matters: single for irregular shapes, complete for compact clusters, average as a compromise, Ward for variance-balanced clusters.

**Clusters are always spherical.** — Hierarchical clustering will find the same shape as k-means, just with a tree.

No. The shape depends on the distance metric and linkage. With single linkage, you can find elongated and arbitrarily shaped clusters, unlike k-means' spherical assumption. In fact: Hierarchical clustering, especially with single linkage, does not impose a spherical shape.

**Every point belongs to some cluster.** — In hierarchical clustering, all points end up in a cluster, even if they are outliers.

Yes, the tree always merges all points into one cluster at the top, but you might need to cut it so that outliers form their own singleton clusters, which is a valid but sometimes unwanted choice. In fact: You can choose a cut that isolates outliers, but the standard algorithm does not label any point as noise; DBSCAN does.


## In short

Hierarchical clustering builds a tree of nested clusters by repeatedly merging the closest pair, using a chosen linkage criterion. You never need to know k in advance — you cut the dendrogram later. The choice of linkage shapes the clusters: single for chains, complete for compact, average in between, Ward for variance. It is a greedy, deterministic algorithm for a given distance and linkage, but the result is a hypothesis, not ground truth. It is used in RAG, agent tool selection, and exploratory data analysis, often on embeddings after dimensionality reduction.


## Where this is used

**Large Language Models (LLMs)**: Hierarchical clustering is not a core training component, but it is used for analysing and organising the representations (embeddings) of tokens, sentences, or documents. For instance, to group similar prompts or responses for efficient retrieval, you might build a tree of clusters and then use that tree to speed up search. In model interpretability, you can cluster the attention heads or neurons to find groups that behave similarly. The tree gives you a sense of hierarchy — which types of text are most similar at a fine level, and which are similar at a coarse level.

**Small models on devices**: On a phone or laptop, you often need to run a small model that can classify or retrieve items locally. You might pre-cluster the embedding space of your small model using hierarchical clustering to build a retrieval index. When a user makes a query, you search the nearest cluster and then within that cluster, rather than scanning the whole database. The dendrogram lets you choose the granularity of clusters based on the device's memory and speed limits — cut high, few clusters, fast but broad; cut low, many clusters, slower but precise.

**Retrieval-Augmented Generation (RAG)**: RAG systems retrieve relevant documents to feed into an LLM. A common approach is to embed documents into vectors and then use clustering to organise them. Hierarchical clustering can build a tree of document clusters, and at query time you navigate this tree to find a small set of candidate documents. The tree structure is more flexible than flat clusters because you can dynamically decide how deep to go based on the query. If the query is vague, you might search a higher level of the tree; if it's specific, you go deeper. This cuts down the search space drastically.

**Agentic systems**: Agents that plan and call tools need to decide which tool to use for a given task. If you have a library of past tasks and their successful tools, you can cluster those tasks hierarchically. The agent can then, when a new task arrives, find the cluster of similar tasks and suggest a set of tools to try. The hierarchy lets the agent reason at different levels: broad intent (top of the tree) versus specific action (leaves).

**Everyday applied machine learning**: Recommendation systems use clustering to group users or items; hierarchical clustering lets you explore natural groups without specifying k in advance, useful for segmenting customers. In computer vision, clustering image embeddings can reveal fine-grained classes. Forecasting often uses clustering to find similar time-series patterns. Fraud detection can group transactions into normal vs anomalous clusters, where the dendrogram helps identify small outlying groups that may represent fraud. In speech, clustering different speakers or dialects is done with embeddings and then a hierarchy.

**What a developer actually writes**: In Python, they reach for `scipy.cluster.hierarchy.linkage` to compute the linkage matrix, and `dendrogram` to draw it. They choose a distance metric (Euclidean, cosine) and a linkage method (single, complete, average, ward). They then choose a threshold by looking at the dendrogram and cutting it. They often combine hierarchical clustering with a dimensionality reduction (PCA or t-SNE) on the features first to speed it up and remove noise. The main thing that breaks when done badly is misinterpreting the dendrogram: cutting too high or too low changes the number of clusters drastically, and the linkage choice can create undesired chain-like clusters (with single linkage) or overly rigid evenly-sized ones (with complete linkage).

**Honest absence**: Hierarchical clustering is not used in the core transformer forward pass, and it is not the main method for training LLMs. It is a data-analysis tool, applied before or alongside model training, not during the backpropagation pass.


---

Read this on the web: https://basavapurushottam.com/learn-ai/hierarchical-clustering
