Hierarchical Clustering: An In-Depth Guide with Python Implementation

Introduction

Hello and welcome! This lesson serves as your introduction to Hierarchical Clustering, a crucial part of unsupervised machine learning. Hierarchical Clustering is a powerful tool for grouping data based on inherent patterns and shared characteristics. By visually representing the hierarchy of clusters, it provides deep insights into the intricacies and overlapping structures of our data. Let's commence this journey into Hierarchical Clustering!

Agglomerative vs. Divisive Approaches

Hierarchical Clustering operates broadly through two approaches — Agglomerative and Divisive. The Agglomerative technique, also known as 'bottom-up,' begins by treating every data point as a distinct cluster and then merges them until only one cluster remains. Conversely, the Divisive methodology, termed 'top-down,' begins with all data points in a single cluster and splits them progressively until each point forms its cluster.

Agglomerative Clustering Algorithm

One of the most common forms of Hierarchical Clustering is Agglomerative Hierarchical Clustering. It starts with every single object in a single cluster. Then, in each successive iteration, it merges the closest pair of clusters and updates the similarity (or distance) between the newly formed cluster and each old cluster. The algorithm repeats this process until all objects are in a single remaining cluster. The Agglomerative Hierarchical Clustering involves the following major steps: Compute the similarity (or distance) matrix containing the distance between each pair of objects in the dataset. Represent each data object as a singleton cluster. Repeat steps 4 and 5 until only one cluster remains. Merge the two closest clusters based on the distances from the distance matrix. Update the similarity (or distance) matrix to reflect the distance of the newly formed cluster with the remaining clusters in the forest. The output is a tree-like diagram named dendrogram which represents the order and distances (similarity) of merges during the algorithm execution.

Understanding the Distance Matrix

D = \begin{bmatrix} 0 & d_{12} & d_{13} & \cdots & d_{1n} \\ d_{21} & 0 & d_{23} & \cdots & d_{2n} \\ d_{31} & d_{32} & 0 & \cdots & d_{3n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ d_{n1} & d_{n2} & d_{n3} & \cdots & 0 \end{bmatrix}

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Custom Agglomerative Clustering implementation in Python with the Iris dataset

Let's proceed to the hands-on implementation of Agglomerative Clustering in Python (using the Iris dataset for our example). We'll use some standard Python libraries — numpy for numerical computations and matplotlib and seaborn for data visualization.

We first setup our environment and initiate our Iris dataset:

Python

# Utilizing the Iris dataset
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn import datasets

iris = datasets.load_iris()
X = iris.data

# Utilizing the Iris dataset
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn import datasets

iris = datasets.load_iris()
X = iris.data

Next, we plot our dataset with Seaborn, a library built on matplotlib, which aids in drawing more attractive and informative statistical graphics:

Python

# Pairplot for the Iris dataset
sns.pairplot(sns.load_dataset("iris"), hue="species")
plt.show()

# Pairplot for the Iris dataset
sns.pairplot(sns.load_dataset("iris"), hue="species")
plt.show()

The resulting plot will look like this:

Let's understand the plot:

The diagonal plots show the distribution of each feature in the dataset — for example, the plot at index (0, 0) shows the distribution of sepal length, meaning the x-axis represents the sepal length and the y-axis represents the frequency of the sepal length values.
The scatter plots show the relationship between each pair of features, with different colors representing different species of Iris flowers — for example, the plot at index (0, 1) shows the relationship between the sepal length and sepal width and so on

Having that, we can now formulate our Agglomerative Hierarchical Clustering function. Our function will begin by placing each data point in a separate cluster, calculating the distances between clusters, merging the nearest clusters, and proceeding until one or more specified clusters remain:

For that, let's define a function to calculate the Euclidean distance between two points:

Python

import numpy as np

# Function to compute Euclidean Distance
def euc_dist(a, b):
    return np.sqrt(np.sum((a - b)**2))

import numpy as np

# Function to compute Euclidean Distance
def euc_dist(a, b):
    return np.sqrt(np.sum((a - b)**2))

Now we can define a separate function that computes the distance matrix:

Python

# Function to calculate the distance matrix
def calculate_distance_matrix(X, clusters):
    # Initialize distance matrix
    dist_matrix = np.zeros((len(clusters), len(clusters)))
    # Compute the distance between each pair of clusters
    for i in range(len(clusters)):
        for j in range(i+1, len(clusters)):
            dists = []
            for k in clusters[i]:
                for l in clusters[j]:
                    dists.append(euc_dist(X[k], X[l]))
            dist_matrix[i, j] = dist_matrix[j, i] = np.mean(dists)
    return dist_matrix

# Function to calculate the distance matrix
def calculate_distance_matrix(X, clusters):
    # Initialize distance matrix
    dist_matrix = np.zeros((len(clusters), len(clusters)))
    # Compute the distance between each pair of clusters
    for i in range(len(clusters)):
        for j in range(i+1, len(clusters)):
            dists = []
            for k in clusters[i]:
                for l in clusters[j]:
                    dists.append(euc_dist(X[k], X[l]))
            dist_matrix[i, j] = dist_matrix[j, i] = np.mean(dists)
    return dist_matrix

Finally, we define the main function for Agglomerative Clustering:

Python

def agglomerative_clustering(X, n_clusters):
    # Initialize each data point as its own cluster
    clusters = [[i] for i in range(len(X))]
    # Continue clustering until the desired number of clusters is reached
    while len(clusters) > n_clusters:
        dist_matrix = calculate_distance_matrix(X, clusters) # Calculate the distance matrix
        # Find the pair of clusters with the minimum distance without np
        min_dist = float('inf')
        for i in range(len(clusters)):
            for j in range(i+1, len(clusters)):
                if dist_matrix[i, j] < min_dist:
                    min_dist = dist_matrix[i, j]
                    idx1, idx2 = i, j
        clusters[idx1].extend(clusters[idx2]) # Merge these two closest clusters
        clusters.pop(idx2) # Remove the merged cluster from the list of clusters
    # Create an array to hold the cluster labels for each data point
    labels = np.empty(len(X), dtype=int)
    for label, cluster in enumerate(clusters):
        for i in cluster:
            labels[i] = label
    return labels

def agglomerative_clustering(X, n_clusters):
    # Initialize each data point as its own cluster
    clusters = [[i] for i in range(len(X))]
    # Continue clustering until the desired number of clusters is reached
    while len(clusters) > n_clusters:
        dist_matrix = calculate_distance_matrix(X, clusters) # Calculate the distance matrix
        # Find the pair of clusters with the minimum distance without np
        min_dist = float('inf')
        for i in range(len(clusters)):
            for j in range(i+1, len(clusters)):
                if dist_matrix[i, j] < min_dist:
                    min_dist = dist_matrix[i, j]
                    idx1, idx2 = i, j
        clusters[idx1].extend(clusters[idx2]) # Merge these two closest clusters
        clusters.pop(idx2) # Remove the merged cluster from the list of clusters
    # Create an array to hold the cluster labels for each data point
    labels = np.empty(len(X), dtype=int)
    for label, cluster in enumerate(clusters):
        for i in cluster:
            labels[i] = label
    return labels

Notice that we perform the clustering until the number of clusters reaches the desired value. The function agglomerative_clustering returns an array of cluster labels for each data point.

Now, let's scale our data and apply the Agglomerative Clustering function to the Iris dataset:

Python

from sklearn.preprocessing import StandardScaler

# Standardizing the features
scaler = StandardScaler()
X_std = scaler.fit_transform(X)

from sklearn.preprocessing import StandardScaler

# Standardizing the features
scaler = StandardScaler()
X_std = scaler.fit_transform(X)

Python

# Perform agglomerative clustering
y_agg = agglomerative_clustering(X_std, n_clusters=3)

# Visualize the clustering
plt.scatter(X[:, 0], X[:, 1], c=y_agg, cmap='viridis')
plt.show()

# Perform agglomerative clustering
y_agg = agglomerative_clustering(X_std, n_clusters=3)

# Visualize the clustering
plt.scatter(X[:, 0], X[:, 1], c=y_agg, cmap='viridis')
plt.show()

We will see the following result:

Introduction

Agglomerative vs. Divisive Approaches

Agglomerative Clustering Algorithm

Understanding the Distance Matrix

Join the 1M+ learners on CodeSignal

Custom Agglomerative Clustering implementation in Python with the Iris dataset

Sklearn's Hierarchical Clustering

Lesson Summary and Practice