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

1. Initially, every data point is considered as a separate cluster.
2. Calculate the distance between clusters.
3. Find the two closest clusters.
4. Merge those two clusters.
5. Recalculate the distances between the new cluster and the remaining clusters.
6. Continue the process until one large cluster remains.
7. Represent the merging process using a Dendrogram.
8. 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?

1. Generate the dendrogram.
2. Look for the largest vertical gap that does not intersect another horizontal cluster line.
3. Draw a horizontal line through that gap.
4. Count the number of vertical branches crossed by the line.
5. 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.

Created by Bijan Krishna Paul