Hierarchical Clustering
Hierarchical Clustering is an unsupervised machine learning
technique used to group similar data points into clusters.
Instead of directly producing only one partition, it builds a hierarchy
of clusters.
There are two main approaches:
- Agglomerative Clustering – Bottom-Up approach
- Divisive Clustering – Top-Down approach
1.
a ) Agglomerative Hierarchical Clustering
Agglomerative clustering starts by treating every data point as an
individual cluster. The closest clusters are then repeatedly merged
until all observations belong to one large cluster.
This is therefore called a Bottom-Up approach.
b ) Divisive Clustering
Divisive Clustering is known as top-down approach.
In this approach we take on huge cluster and starts breaking it up into smaller clusters until it reaches individual data points (or single point clusters).
2. Basic Working
-
Initially, every data point is considered as a separate cluster.
-
Calculate the distance between clusters.
-
Find the two closest clusters.
-
Merge those two clusters.
-
Recalculate the distances between the new cluster and the remaining
clusters.
-
Continue the process until one large cluster remains.
-
Represent the merging process using a Dendrogram.
-
Choose the desired number of clusters by cutting the dendrogram at
an appropriate height.
3. Distance Calculation
Euclidean Distance:
d(P₁,P₂) =
√[(X₁ − X₂)² + (Y₁ − Y₂)²]
Example:
If P₁ = (170,56) and P₂ = (168,60)
d = √[(170−168)² + (56−60)²]
d = √(4 + 16)
d = √20 ≈ 4.47
4. Linkage Methods
Single Linkage
Distance between two clusters is based on the closest pair of points.
Complete Linkage
Distance is based on the farthest pair of points between two clusters.
Average Linkage
Distance is calculated using the average distance between points of
two clusters.
Ward Linkage
Merges clusters while minimizing the increase in within-cluster
variance.
5. Example Dataset
We will use a small Height and Weight dataset similar to the example
described in the reference article.
| Point |
Height |
Weight |
| P0 |
165 |
55 |
| P1 |
170 |
56 |
| P2 |
168 |
60 |
| P3 |
178 |
70 |
| P4 |
166 |
55 |
| P5 |
180 |
72 |
6. Python Implementation
Google Colab / Python Code
# ============================================
# HIERARCHICAL CLUSTERING
# AGGLOMERATIVE APPROACH
# ============================================
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.cluster import AgglomerativeClustering
from scipy.cluster.hierarchy import dendrogram, linkage
# --------------------------------------------
# 1. Create Dataset
# --------------------------------------------
data = {
"Height": [165, 170, 168, 178, 166, 180],
"Weight": [55, 56, 60, 70, 55, 72]
}
df = pd.DataFrame(data)
print("Dataset:")
print(df)
# --------------------------------------------
# 2. Select Features
# --------------------------------------------
X = df[["Height", "Weight"]]
# --------------------------------------------
# 3. Create Dendrogram
# --------------------------------------------
linked = linkage(
X,
method="single",
metric="euclidean"
)
plt.figure(figsize=(10,6))
dendrogram(
linked,
labels=["P0","P1","P2","P3","P4","P5"]
)
plt.title("Hierarchical Clustering Dendrogram")
plt.xlabel("Data Points")
plt.ylabel("Euclidean Distance")
plt.show()
# --------------------------------------------
# 4. Agglomerative Clustering
# --------------------------------------------
model = AgglomerativeClustering(
n_clusters=2,
metric="euclidean",
linkage="single"
)
labels = model.fit_predict(X)
# --------------------------------------------
# 5. Add Cluster Labels
# --------------------------------------------
df["Cluster"] = labels
print("\nClustered Dataset:")
print(df)
# --------------------------------------------
# 6. Visualize Clusters
# --------------------------------------------
plt.figure(figsize=(8,6))
plt.scatter(
df["Height"],
df["Weight"],
c=df["Cluster"],
s=120
)
plt.xlabel("Height")
plt.ylabel("Weight")
plt.title("Agglomerative Hierarchical Clustering")
plt.grid(True)
plt.show()
7. Dendrogram
A dendrogram is a tree-like diagram that shows the
sequence in which clusters are merged.
The vertical axis represents the distance at which clusters are merged.
A horizontal cut through the dendrogram can be used to determine the
number of clusters.
8. How to Select Number of Clusters?
- Generate the dendrogram.
- Look for the largest vertical gap that does not intersect another
horizontal cluster line.
- Draw a horizontal line through that gap.
- Count the number of vertical branches crossed by the line.
- The number of branches represents the selected number of clusters.
9. Using Different Linkage Methods
Compare Single, Complete, Average and Ward Linkage
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import linkage, dendrogram
methods = [
"single",
"complete",
"average",
"ward"
]
plt.figure(figsize=(16,10))
for i, method in enumerate(methods):
plt.subplot(2,2,i+1)
linked = linkage(
X,
method=method,
metric="euclidean"
)
dendrogram(
linked,
labels=["P0","P1","P2","P3","P4","P5"]
)
plt.title(method.capitalize() + " Linkage")
plt.xlabel("Data Points")
plt.ylabel("Distance")
plt.tight_layout()
plt.show()
10. Complete Agglomerative Clustering Code
Single Google Colab Code
# ============================================
# COMPLETE HIERARCHICAL CLUSTERING
# ============================================
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.cluster import AgglomerativeClustering
from scipy.cluster.hierarchy import dendrogram, linkage
# Dataset
data = pd.DataFrame({
"Height": [165,170,168,178,166,180],
"Weight": [55,56,60,70,55,72]
})
print("Original Dataset")
print(data)
# Features
X = data[["Height","Weight"]]
# --------------------------------------------
# Dendrogram
# --------------------------------------------
Z = linkage(
X,
method="single",
metric="euclidean"
)
plt.figure(figsize=(10,6))
dendrogram(
Z,
labels=["P0","P1","P2","P3","P4","P5"]
)
plt.title("Hierarchical Clustering Dendrogram")
plt.xlabel("Data Points")
plt.ylabel("Distance")
plt.show()
# --------------------------------------------
# Agglomerative Model
# --------------------------------------------
hc = AgglomerativeClustering(
n_clusters=2,
metric="euclidean",
linkage="single"
)
data["Cluster"] = hc.fit_predict(X)
# --------------------------------------------
# Display Result
# --------------------------------------------
print("\nFinal Cluster Result")
print(data)
# --------------------------------------------
# Visualization
# --------------------------------------------
plt.figure(figsize=(8,6))
for cluster in sorted(data["Cluster"].unique()):
subset = data[data["Cluster"] == cluster]
plt.scatter(
subset["Height"],
subset["Weight"],
s=150,
label="Cluster " + str(cluster)
)
for index, row in subset.iterrows():
plt.annotate(
"P" + str(index),
(row["Height"], row["Weight"]),
xytext=(5,5),
textcoords="offset points"
)
plt.xlabel("Height")
plt.ylabel("Weight")
plt.title(
"Agglomerative Hierarchical Clustering"
)
plt.legend()
plt.grid(True)
plt.show()
11. Advantages
No Need to Start With K
The hierarchy can be examined before deciding how many clusters to
retain.
Dendrogram
The dendrogram provides a visual representation of the merging process.
Different Linkages
Single, complete, average and Ward linkage can be used depending on
the data and objective.
Hierarchical Structure
The algorithm provides information about clusters at multiple levels.
12. Limitations
- Computational cost can become high for very large datasets.
- The result can depend strongly on the selected linkage method.
- Once clusters are merged, the basic agglomerative process does not
normally undo that merge.
- Different distance measures can produce different clustering
structures.
13. Summary
Hierarchical Clustering builds a hierarchy of clusters.
In the Agglomerative approach, every observation starts
as its own cluster and the closest clusters are repeatedly merged.
A dendrogram records this merging process and can be
used to select a desired number of clusters.
The reference article demonstrates this process using Euclidean
distance and single linkage, including the formation of the distance
matrix, successive merging of clusters, dendrogram construction and
selection of two clusters.
