Hierarchical Clustering: (unsupervised learning algorithm)

Hierarchical clustering is an unsupervised machine learning technique that groups related data points without requiring labeled data. It builds a hierarchy (tree-like structure) of clusters based on similarity or distance. First, more similar data points are grouped together. Gradually, clusters are formed. The result is shown as a dendrogram, or tree diagram.

Types of Hierarchical Clustering

Agglomerative (Bottom-Up) – Most common
-Each data point starts as its own cluster
Closest clusters are merged step by step

Divisive (Top-Down)
All data points start in one cluster
Clusters are split recursively

Let’s compute the distances,

A to B = 1
A to C= 1.414
B to C= 1
D to E= 1.414
D to F= 2
E to F= 1.414


Step 2 — First Merge (Closest Points)

Merge A and B (distance = 1)
Cluster 1: {A, B}
Other clusters: {C}, {D}, {E}, {F}
Because A and B have the smallest distance

Step 3 — Second Merge

Now compare clusters to points
Hierarchical clustering usually does not assign new coordinates to merged clusters.
To compute distance between {A,B} and C
Compute the centroid of A,B.
A(1,1) ----●---- B(2,1)
↑ Centroid (1.5,1)

Now, distance between {A,B} and C is:
Distance between (1.5,1) and (2,2) = 1.11
(using single linkage = minimum distance)
Distance between {A,B} and C = 1
Distance between D and E = 1.41
Merge {A,B} and C

Cluster 1: {A, B, C}
Clusters left: {D}, {E}, {F}
Left-side points form a tight cluster

Step 4 — Third Merge
Right-side points:
D–E ≈ 1.41
E–F ≈ 1.41
Merge D and E
Cluster 2: {D, E}
Remaining: {F}

Step 5 — Fourth Merge
Merge {D,E} with F
Cluster 2: {D, E, F}
Final Step — Merge the Two Big Clusters
Now only two clusters remain:
Cluster 1: {A, B, C}
Cluster 2: {D, E, F}
Distance between them is large, so they merge last.




Machine Learning • Worked Example

Hierarchical Clustering

A complete step-by-step example using 10 customers, 4 independent variables, Euclidean distance, single linkage, and K = 3 clusters.

10 Customers4 VariablesEuclidean DistanceSingle LinkageK = 3

1

Customer Data

Variables: annual income, annual spending, number of visits, and age.

Customer	Income	Spending	Visits	Age
C1	10	20	30	40
C2	11	21	29	41
C3	12	19	31	39
C4	50	60	70	80
C5	51	59	71	79
C6	49	61	69	81
C7	90	100	110	120
C8	91	99	111	119
C9	89	101	109	121
C10	92	98	112	118

2

Euclidean Distance

For customers i and j:

d(i,j) = √[(X₁ᵢ−X₁ⱼ)² + (X₂ᵢ−X₂ⱼ)² + (X₃ᵢ−X₃ⱼ)² + (X₄ᵢ−X₄ⱼ)²]

Example: C1 and C2

d(C1,C2) = √[(10−11)²+(20−21)²+(30−29)²+(40−41)²]
= √(1+1+1+1) = 2

Example: C1 and C3

d(C1,C3) = √[(10−12)²+(20−19)²+(30−31)²+(40−39)²]
= √(4+1+1+1) = √7 ≈ 2.646

3

Distance Matrix

	C1	C2	C3	C4	C5	C6	C7	C8	C9	C10
C1	0	2.000	2.646	80.000	80.025	80.025	160.000	160.012	160.012	160.050
C2	2.000	0	3.606	79.019	79.070	79.019	159.009	159.035	159.009	159.085
C3	2.646	3.606	0	79.542	79.505	79.630	159.521	159.502	159.565	159.509
C4	80.000	79.019	79.542	0	2.000	2.000	80.000	80.025	80.025	80.100
C5	80.025	79.070	79.505	2.000	0	4.000	80.025	80.000	80.100	80.025
C6	80.025	79.019	79.630	2.000	4.000	0	80.025	80.100	80.000	80.225
C7	160.000	159.009	159.521	80.000	80.025	80.025	0	2.000	2.000	4.000
C8	160.012	159.035	159.502	80.025	80.000	80.100	2.000	0	4.000	2.000
C9	160.012	159.009	159.565	80.025	80.100	80.000	2.000	4.000	0	6.000
C10	160.050	159.085	159.509	80.100	80.025	80.225	4.000	2.000	6.000	0

4

Single-Linkage Rule

The distance between two clusters is the minimum distance between any pair of observations across those clusters.

D(A,B) = min { d(i,j) : i ∈ A, j ∈ B }

5

Agglomerative Merging

Merge 1C1 + C2 → {C1,C2}Distance = 2.000 • 9 clusters

Merge 2C4 + C5 → {C4,C5}Distance = 2.000 • 8 clusters

Merge 3C7 + C8 → {C7,C8}Distance = 2.000 • 7 clusters

Merge 4{C4,C5} + C6min(2,4) = 2.000 • 6 clusters

Merge 5{C7,C8} + C9min(2,4) = 2.000 • 5 clusters

Merge 6{C7,C8,C9} + C10min(4,2,6) = 2.000 • 4 clusters

Merge 7 • K = 3{C1,C2} + C3min(2.646,3.606) = 2.646 • 3 clusters

Why stop? The hierarchy goes 10 → 9 → … → 4 → 3 → 2 → 1. We stop when exactly three clusters remain.

6

Final K = 3 Clusters

Cluster 1

Lower-value group

C1, C2, C3

Cluster 2

Middle-value group

C4, C5, C6

Cluster 3

Higher-value group

C7, C8, C9, C10

Customer	Cluster
C1	1
C2	1
C3	1
C4	2
C5	2
C6	2
C7	3
C8	3
C9	3
C10	3

7

Dendrogram Concept

The branch height represents the distance at which clusters are merged.

Distance
  |
80+                         ┌──────── Cluster 1
  |                    ┌────┤
  |                    │    └────────
  |                    │
  |                    │       ┌──── Cluster 2
  |                    └───────┤
  |                            └────
  |
  |                              ┌── C7
  |                         ┌────┤
  |                         │    └── C8
  |                    ┌────┤
  |                    │    └──── C9
  |               ┌────┤
  |               │    └──── C10
  |
  |---- 2.646 ---- C1,C2,C3
  |---- 2.000 ---- C1,C2
  |---- 2.000 ---- C4,C5,C6
  |---- 2.000 ---- C7,C8,C9,C10
  +----------------------------------------

Key observation: there is a large jump from about 2.646 to about 79.019, supporting the three-cluster solution in this illustrative dataset.

8

Final Summary

Method: Hierarchical Agglomerative Clustering

Distance: Euclidean

Linkage: Single linkage

Observations: 10 customers

Variables: 4 independent variables

K: 3

---

Cluster 1: C1, C2, C3

Cluster 2: C4, C5, C6

Cluster 3: C7, C8, C9, C10

Note: For real data, standardization is usually appropriate when variables have substantially different scales. Different linkage methods can also produce different cluster structures.

USE CASE 1: Use Hierarchical Clustering for customer segmentation in Market Basket Analysis. Instead of finding which products are purchased together (like Apriori or FP-Growth), use Hierarchical Clustering to group customers based on their purchasing behavior. Once customers are clustered, you can create targeted promotions and personalized recommendations for each segment.

import pandas as pd
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import AgglomerativeClustering
from scipy.cluster.hierarchy import dendrogram, linkage
import matplotlib.pyplot as plt


# ----------------------------------
# Step 1: Sample Market Basket Data
# ----------------------------------

data = pd.DataFrame({
    'Customer': ['C001','C002','C003','C004','C005','C006','C007','C008'],
    'Bread': [12,10,11,1,0,2,6,5],
    'Milk': [10,8,9,2,1,1,5,6],
    'Eggs': [8,7,6,1,2,0,4,5],
    'Beer': [0,1,0,10,12,9,4,5],
    'Chips': [1,0,1,8,10,7,3,4]
})


#Load data
#You can also download from
#https://www.pythonplaza.com/sample_customer_shopping.html
data= pd.read_csv("customer_shopping.csv")

print("Original Data")
print(data)



# ----------------------------------
# Step 2: Select Features
# ----------------------------------

X = data[['Bread', 'Milk', 'Eggs', 'Beer', 'Chips']]


# ----------------------------------
# Step 3: Scale Features
# ----------------------------------

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)


# ----------------------------------
# Step 4: Dendrogram (optional but recommended)
# ----------------------------------


plt.figure(figsize=(8,5))
linked = linkage(X_scaled, method='ward')

dendrogram(linked,
           labels=data['Customer'].values)

plt.title("Dendrogram (Hierarchical Clustering)")
plt.xlabel("Customers")
plt.ylabel("Distance")
plt.show()


# ----------------------------------
# Step 5: Train Hierarchical Clustering Model
# ----------------------------------

hc = AgglomerativeClustering(
    n_clusters=3,
    linkage='ward'
)

data['Cluster'] = hc.fit_predict(X_scaled)

print("\nCluster Assignments")
print(data[['Customer', 'Cluster']])


# ----------------------------------
# Step 6: Cluster Profiles (mean of original data)
# ----------------------------------

print("\nCluster Profiles (Original Scale Means)")

cluster_profiles = data.groupby('Cluster')[['Bread','Milk','Eggs','Beer','Chips']].mean()

print(cluster_profiles.round(2))


# ----------------------------------
# Step 7: Test New Customer
# ----------------------------------

new_customer = pd.DataFrame({
    'Bread': [11],
    'Milk': [9],
    'Eggs': [7],
    'Beer': [1],
    'Chips': [1]
})

new_customer_scaled = scaler.transform(new_customer)

# NOTE: AgglomerativeClustering has no direct predict()
# So we assign manually using nearest cluster centroid

centroids = data.groupby('Cluster')[['Bread','Milk','Eggs','Beer','Chips']].mean()
centroids_scaled = scaler.transform(centroids)

import numpy as np

distances = np.linalg.norm(centroids_scaled - new_customer_scaled, axis=1)
predicted_cluster = np.argmin(distances)

print("\nNew Customer")
print(new_customer)
print(f"\nPredicted Cluster: {predicted_cluster}")


# ----------------------------------
# Step 8: Recommendation Logic
# ----------------------------------


if predicted_cluster == 0:
    print("Recommendation: Bread, Milk, Eggs promotions")
elif predicted_cluster == 1:
    print("Recommendation: Beer and Chips promotions")
else:
    print("Recommendation: Mixed basket offers")

import pandas as pd
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import AgglomerativeClustering
import numpy as np


# Load data
# download from:
# https://www.pythonplaza.com/healthcare_patient_dataset.html


df = pd.read_csv("patients_data.csv")

# Features used for clustering


X = df[['Age',
        'BMI',
        'Blood_Pressure',
        'Cholesterol',
        'Hospital_Visits']]


# Scale data


scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)


# Train Hierarchical Clustering model


hc = AgglomerativeClustering(n_clusters=3, linkage='ward')
df['Cluster'] = hc.fit_predict(X_scaled)


# New patient

new_patient = [[33, 28.0, 139, 210, 4]]

# Apply SAME scaling
new_patient_scaled = scaler.transform(new_patient)

# ---------------------------------------
# NOTE:
# Hierarchical clustering has NO .predict()
# So we assign cluster by nearest centroid
# ---------------------------------------


# Compute cluster centroids (in original scale)


centroids = df.groupby('Cluster')[['Age','BMI','Blood_Pressure','Cholesterol','Hospital_Visits']].mean()


# Scale centroids using same scaler

centroids_scaled = scaler.transform(centroids)

# Find nearest cluster


distances = np.linalg.norm(centroids_scaled - new_patient_scaled, axis=1)
cluster = np.argmin(distances)

print("Patient belongs to Cluster:", cluster)