Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Hierarchical Clustering › Example

Michael BrenndoerferAugust 14, 20255 min read

Machine Learning from ScratchAll chapters

Part 7 of 9Unsupervised Learning

Chapter 54Hierarchical Clustering › Example

Reading section 4 of 8 · Example · 5 minSection 4 of 8 · 5 min

Section 4 of 8 · 5 min read

Hierarchical Clustering › ExampleOne section · Sections in this chapter4 / 8 ↓

Sections in this chapter8

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

Let's work through a concrete example using a small dataset to demonstrate the step-by-step process of hierarchical clustering. We'll use a simple 2D dataset with 6 points to make the calculations manageable and easy to follow.

Out[3]:

Visualization

Scatter plot of 6 labeled data points. — Simple 6-point dataset used to demonstrate hierarchical clustering step-by-step. Each point is labeled (A-F) to track the clustering process. The dataset contains two natural groups: points A, B, C form one cluster, while points D, E, F form another. This simple example allows us to follow the algorithm''s decision-making process and understand how distances are calculated and clusters are merged at each step.

Dendrogram showing hierarchical clustering merges. — Dendrogram visualization of the hierarchical clustering process for the 6-point dataset. The dendrogram shows the complete merging sequence, with the height of each horizontal line representing the distance at which clusters were merged. The large gap between the final merge (distance 5.0) and previous merges (distance 1.0) clearly indicates that 2 clusters would be the natural choice for this dataset. This visualization makes it easy to understand the hierarchical structure and identify optimal cut points.

Out[4]:

Console

Initial Distance Matrix:
   A    B    C    D    E    F
A [0.         1.         1.         5.65685425 6.40312424 7.07106781]
B [1.         0.         1.41421356 5.         5.83095189 6.40312424]
C [1.         1.41421356 0.         5.         5.65685425 6.40312424]
D [5.65685425 5.         5.         0.         1.         1.41421356]
E [6.40312424 5.83095189 5.65685425 1.         0.         1.        ]
F [7.07106781 6.40312424 6.40312424 1.41421356 1.         0.        ]

Linkage Matrix (showing merge steps):
Step 1: Merge A and B (distance = 1.0)
Step 2: Merge AB and C (distance = 1.0)
Step 3: Merge D and E (distance = 1.0)
Step 4: Merge DE and F (distance = 1.0)
Step 5: Merge ABC and DEF (distance = 5.0)

Let's walk through the step-by-step process of hierarchical clustering with single linkage:

Step 1: Initial Setup We start with 6 clusters, each containing one point: {A}, {B}, {C}, {D}, {E}, {F}

Step 2: Calculate Initial Distances The distance matrix shows all pairwise Euclidean distances. For example, the distance between A(1,1) and B(1,2) is:

d(A,B) = \sqrt{(1-1)^2 + (1-2)^2} = \sqrt{0 + 1} = 1.0

where:

$d(A,B)$ : the Euclidean distance between points A and B
$A = (1, 1)$ : point A with coordinates $x_1 = 1$ , $x_2 = 1$
$B = (1, 2)$ : point B with coordinates $x_1 = 1$ , $x_2 = 2$
The calculation uses the Euclidean distance formula: $d(A,B) = \sqrt{(x_{A1} - x_{B1})^2 + (x_{A2} - x_{B2})^2}$

Step 3: First Merge The minimum distance is 1.0, which occurs between multiple pairs: (A,B), (A,C), (D,E), and (E,F). The algorithm chooses the first pair it encounters, so we merge A and B into cluster {A,B}.

Step 4: Update Distances Now we need to calculate distances from the new cluster $\{A,B\}$ to all other points. Using single linkage:

$d(\{A,B\}, C) = \min(d(A,C), d(B,C)) = \min(1.0, 1.41) = 1.0$
$d(\{A,B\}, D) = \min(d(A,D), d(B,D)) = \min(5.66, 4.47) = 4.47$

where:

$\{A,B\}$ : the merged cluster containing points A and B
$d(\{A,B\}, C)$ : the distance from cluster $\{A,B\}$ to point C using single linkage
$d(A,C)$ : the Euclidean distance between points A and C
$d(B,C)$ : the Euclidean distance between points B and C
$\min$ : the minimum operator (for single linkage, we take the minimum distance)
The values 5.66 and 4.47 are the Euclidean distances $d(A,D)$ and $d(B,D)$ respectively, rounded to two decimal places

Step 5: Continue Merging The process continues, merging the closest clusters at each step. Notice how the algorithm naturally identifies two main groups: {A,B,C} and {D,E,F}, which are separated by a single-linkage distance of 5.0.

The dendrogram visualization shows this process clearly, with the height of each horizontal line representing the distance at which clusters were merged. The large gap between the final merge (distance 5.0) and the previous merges (distance 1.0) suggests that 2 clusters would be a natural choice for this dataset.