Hierarchical clustering (linkage) in SciPy - Step-by-Step Execution

Concept Flow - Hierarchical clustering (linkage)

Start with each point as a cluster

↓

Calculate distances between clusters

↓

Find closest clusters

↓

Merge closest clusters

↓

Update distances

↓

More than one cluster?

No↓

Done

Start with each data point alone, then repeatedly merge the closest clusters until all points form one cluster.

Execution Sample

SciPy

from scipy.cluster.hierarchy import linkage
import numpy as np

points = np.array([[1,2],[2,3],[10,10],[11,11]])
Z = linkage(points, method='single')

This code groups 4 points step-by-step using single linkage hierarchical clustering.

Execution Table

Step	Clusters Merged	Distance	Clusters After Merge	Action
1	[0] and [1]	1.414	[[0,1]] [2] [3]	Merge closest points 0 and 1
2	[2] and [3]	1.414	[[0,1]] [[2,3]]	Merge closest points 2 and 3
3	[[0,1]] and [[2,3]]	12.728	[[0,1,2,3]]	Merge two clusters into one
4	-	-	[[0,1,2,3]]	Only one cluster left, stop

💡 All points merged into a single cluster, clustering complete

Variable Tracker

Variable	Start	After 1	After 2	After 3	Final
clusters	[0], [1], [2], [3]	[[0,1]], [2], [3]	[[0,1]], [[2,3]]	[[0,1,2,3]]	[[0,1,2,3]]
distances	calculated between all points	updated distances between clusters	updated distances between clusters	no distances left	no distances left

Key Moments - 3 Insights

Why do we merge points 0 and 1 first, not 0 and 2?

Because the distance between points 0 and 1 is smaller (1.414) than between 0 and 2 (about 12.04), as shown in step 1 of the execution_table.

What happens to distances after merging clusters?

Distances are recalculated between the new cluster and remaining clusters, as seen after step 1 and 2 in the execution_table where clusters and distances update.

When does the clustering stop?

When only one cluster remains, as shown in step 4 of the execution_table where no more merges happen.

Visual Quiz - 3 Questions

Look at the execution_table, which clusters merge at step 2?

A [2] and [3]

B [[0,1]] and [[2,3]]

C [0] and [1]

D [1] and [2]

💡 Hint

Check the 'Clusters Merged' column at step 2 in the execution_table.

At which step does the condition 'only one cluster left' become true?

A Step 1

B Step 3

C Step 4

D Step 2

💡 Hint

Look at the 'Action' column in the execution_table for when clustering stops.

If we used 'complete' linkage instead of 'single', how would the distance at step 3 change?

A It would be the same

B It would be larger

C It would be smaller

D It would be zero

💡 Hint

Complete linkage uses the farthest points distance, so check the 'Distance' column at step 3.

Concept Snapshot

Hierarchical clustering groups points stepwise.
Start: each point is its own cluster.
Find closest clusters by distance.
Merge them and update distances.
Repeat until one cluster remains.
Linkage method (single, complete) affects distance calculation.

Full Transcript

Hierarchical clustering starts with each data point as its own cluster. We calculate distances between all clusters and merge the closest two. After merging, distances are updated to reflect the new clusters. This repeats until all points form one cluster. The linkage method defines how distances between clusters are measured. In this example, single linkage merges clusters based on the shortest distance between points. The execution table shows each merge step, clusters involved, and distances. The process stops when only one cluster remains.

Practice

1. What does the linkage function in scipy.cluster.hierarchy do in hierarchical clustering?

easy

A. It calculates distances between clusters step-by-step to form a hierarchy.

B. It assigns data points to fixed clusters before clustering.

C. It visualizes the final clusters using a scatter plot.

D. It normalizes the data before clustering.

Solution

1. Step 1: Understand hierarchical clustering process

   Hierarchical clustering builds clusters step-by-step by merging closest groups.

2. Step 2: Role of linkage function

   The linkage function calculates distances between clusters at each step to decide which to merge next.

3. Final Answer:

   It calculates distances between clusters step-by-step to form a hierarchy. -> Option A

4. Quick Check:

   Linkage = stepwise cluster distance calculation [OK]

Hint: Linkage = stepwise cluster distance calculation [OK]

Common Mistakes:

• Thinking linkage assigns fixed clusters first
• Confusing linkage with visualization functions
• Assuming linkage normalizes data

2. Which of the following is the correct way to import the linkage function from scipy.cluster.hierarchy?

easy

A. from scipy.cluster import linkage

B. import linkage from scipy.cluster.hierarchy

C. import linkage from scipy.cluster

D. from scipy.cluster.hierarchy import linkage

Solution

1. Step 1: Identify correct module path

   The linkage function is inside the hierarchy submodule of scipy.cluster.

2. Step 2: Use correct Python import syntax

   Python import syntax for functions is from module import function. So, from scipy.cluster.hierarchy import linkage is correct.

3. Final Answer:

   from scipy.cluster.hierarchy import linkage -> Option D

4. Quick Check:

   Correct import = from scipy.cluster.hierarchy import linkage [OK]

Hint: Use 'from scipy.cluster.hierarchy import linkage' [OK]

Common Mistakes:

• Using wrong module path
• Wrong import syntax like 'import linkage from ...'
• Importing from scipy.cluster directly

3. What is the output of this code snippet?

from scipy.cluster.hierarchy import linkage
import numpy as np

X = np.array([[1, 2], [3, 4], [5, 6]])
Z = linkage(X, method='single')
print(Z.shape)

medium

A. (2, 3)

B. (3, 4)

C. (2, 4)

D. (3, 3)

Solution

1. Step 1: Understand linkage output shape

   For n data points, linkage returns a matrix with n-1 rows and 4 columns.

2. Step 2: Calculate shape for 3 points

   Here, n=3, so output shape is (2, 4).

3. Final Answer:

   (2, 4) -> Option C

4. Quick Check:

   Linkage shape = (n-1, 4) = (2, 4) [OK]

Hint: Linkage output shape = (n-1, 4) for n points [OK]

Common Mistakes:

• Expecting shape (n, 4) instead of (n-1, 4)
• Confusing columns count
• Miscounting number of data points

4. Identify the error in this code snippet:

from scipy.cluster.hierarchy import linkage
import numpy as np

X = np.array([[1, 2], [3, 4], [5, 6]])
Z = linkage(X, method='fast')
print(Z)

medium

A. The method 'fast' is not a valid linkage method.

B. The input array X must be 1-dimensional.

C. The linkage function requires a distance matrix, not raw data.

D. The print statement is missing parentheses.

Solution

1. Step 1: Check valid linkage methods

   Valid methods include 'single', 'complete', 'average', 'ward', etc. 'fast' is not valid.

2. Step 2: Confirm input data and syntax

   Input can be raw data array; print statement syntax is correct in Python 3.

3. Final Answer:

   The method 'fast' is not a valid linkage method. -> Option A

4. Quick Check:

   Invalid method name causes error [OK]

Hint: Check method names carefully; 'fast' is invalid [OK]

Common Mistakes:

• Assuming 'fast' is a valid method
• Thinking input must be 1D array
• Confusing linkage input requirements

5. You have a dataset with 5 points and want to perform hierarchical clustering using the 'ward' method. After computing linkage, how many merges will be recorded in the linkage matrix, and why?

hard

A. 3 merges, because only the closest points are merged.

B. 4 merges, because each merge reduces clusters by one until one cluster remains.

C. 6 merges, because the 'ward' method adds an extra merge step.

D. 5 merges, because there are 5 points to merge individually.

Solution

1. Step 1: Understand merges in hierarchical clustering

   For n points, hierarchical clustering performs n-1 merges to combine all points into one cluster.

2. Step 2: Apply to 5 points with 'ward' method

   With 5 points, the linkage matrix records 4 merges regardless of method.

3. Final Answer:

   4 merges, because each merge reduces clusters by one until one cluster remains. -> Option B

4. Quick Check:

   Merges = n-1 = 4 for 5 points [OK]

Hint: Number of merges = number of points minus one [OK]

Common Mistakes:

• Thinking merges equal number of points
• Assuming method changes merge count
• Confusing merges with cluster count