Understanding and Implementing Distance Metrics in Hierarchical Clustering

Introduction

Welcome to our lesson on distance metrics in hierarchical clustering! Today, we will delve into the definition and importance of distance metrics, particularly in hierarchical clustering. You will learn about various types of distance metrics such as Euclidean, Manhattan, and Cosine Distance, and how to implement these in Python. After this, we will examine the impact of these distance measures on the resulting hierarchical clustering.

Introduction to Distance Metrics

Distance metrics are essentially measures used in mathematics to calculate the 'distance' between two points. In the context of clustering, we're interested in the distance between data points in our dataset or the distance between clusters of points. We often use metrics like Euclidean distance, Manhattan distance, and Cosine Distance, each with its unique set of characteristics and application scenarios.

Implementing Distance Metrics in Python: Euclidean Distance

Distance = \sqrt{\sum_{i=1}^{n} (p_i - q_i)^2}

Implementing Distance Metrics in Python: Manhattan Distance

Distance = \sum_{i=1}^{n} |p_i - q_i|

Implementing Distance Metrics in Python: Cosine Distance

1 - \text{Cosine Similarity}

Join the 1M+ learners on CodeSignal

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

Python

import math

# Euclidean Distance Metric
def euclidean_distance(point1, point2):
    return math.sqrt(sum((point1 - point2)**2))

Python

# Manhattan Distance Metric
def manhattan_distance(point1, point2):
    return sum(abs(point1 - point2))

Python

import numpy as np

# Cosine Distance Metric
def cosine_distance(point1, point2):
    return 1 - np.dot(point1, point2) / (np.linalg.norm(point1) * np.linalg.norm(point2))

Python

# Function to calculate the distance matrix
def calculate_distance_matrix(X, clusters, distance_metric):
    # 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(distance_metric(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, distance_metric):
    # 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(distance_metric(X[k], X[l]))
            dist_matrix[i, j] = dist_matrix[j, i] = np.mean(dists)
    return dist_matrix

Python

def agglomerative_clustering(X, n_clusters, distance_metric):
    clusters = [[i] for i in range(len(X))]

    while len(clusters) > n_clusters:
        # Calculate the distance matrix using the method passed via distance_metric
        dist_matrix = calculate_distance_matrix(X, clusters, distance_metric)

        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])
        clusters.pop(idx2)

    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, distance_metric):
    clusters = [[i] for i in range(len(X))]

    while len(clusters) > n_clusters:
        # Calculate the distance matrix using the method passed via distance_metric
        dist_matrix = calculate_distance_matrix(X, clusters, distance_metric)

        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])
        clusters.pop(idx2)

    labels = np.empty(len(X), dtype=int)
    for label, cluster in enumerate(clusters):
        for i in cluster:
            labels[i] = label

    return labels

Python

import matplotlib.pyplot as plt
from sklearn.datasets import load_iris
from sklearn.preprocessing import StandardScaler

# Load the Iris dataset
dataset = load_iris().data

# Scale the dataset with StandardScaler
scaler = StandardScaler()
dataset = scaler.fit_transform(dataset)

import matplotlib.pyplot as plt
from sklearn.datasets import load_iris
from sklearn.preprocessing import StandardScaler

# Load the Iris dataset
dataset = load_iris().data

# Scale the dataset with StandardScaler
scaler = StandardScaler()
dataset = scaler.fit_transform(dataset)

Python

# Perform Agglomerative Clustering
n_clusters = 3

# Euclidean Distance
labels_euc = agglomerative_clustering(dataset, n_clusters, euclidean_distance)

# Manhattan Distance
labels_man = agglomerative_clustering(dataset, n_clusters, manhattan_distance)

# Cosine Distance
labels_cos = agglomerative_clustering(dataset, n_clusters, cosine_distance)

# Perform Agglomerative Clustering
n_clusters = 3

# Euclidean Distance
labels_euc = agglomerative_clustering(dataset, n_clusters, euclidean_distance)

# Manhattan Distance
labels_man = agglomerative_clustering(dataset, n_clusters, manhattan_distance)

# Cosine Distance
labels_cos = agglomerative_clustering(dataset, n_clusters, cosine_distance)

Python

# Plot the results in 3 subplots for each distance metric
fig, axs = plt.subplots(1, 3, figsize=(15, 5))

# Euclidean Distance
axs[0].scatter(dataset[:, 0], dataset[:, 1], c=labels_euc, cmap='viridis')
axs[0].set_title('Euclidean Distance')
axs[0].set_xlabel('Sepal Length')
axs[0].set_ylabel('Sepal Width')

# Manhattan Distance
axs[1].scatter(dataset[:, 0], dataset[:, 1], c=labels_man, cmap='viridis')
axs[1].set_title('Manhattan Distance')
axs[1].set_xlabel('Sepal Length')
axs[1].set_ylabel('Sepal Width')

# Cosine Distance
axs[2].scatter(dataset[:, 0], dataset[:, 1], c=labels_cos, cmap='viridis')
axs[2].set_title('Cosine Distance')
axs[2].set_xlabel('Sepal Length')
axs[2].set_ylabel('Sepal Width')

plt.show()

# Plot the results in 3 subplots for each distance metric
fig, axs = plt.subplots(1, 3, figsize=(15, 5))

# Euclidean Distance
axs[0].scatter(dataset[:, 0], dataset[:, 1], c=labels_euc, cmap='viridis')
axs[0].set_title('Euclidean Distance')
axs[0].set_xlabel('Sepal Length')
axs[0].set_ylabel('Sepal Width')

# Manhattan Distance
axs[1].scatter(dataset[:, 0], dataset[:, 1], c=labels_man, cmap='viridis')
axs[1].set_title('Manhattan Distance')
axs[1].set_xlabel('Sepal Length')
axs[1].set_ylabel('Sepal Width')

# Cosine Distance
axs[2].scatter(dataset[:, 0], dataset[:, 1], c=labels_cos, cmap='viridis')
axs[2].set_title('Cosine Distance')
axs[2].set_xlabel('Sepal Length')
axs[2].set_ylabel('Sepal Width')

plt.show()

Python

from sklearn.cluster import AgglomerativeClustering

# Agglomerative Clustering using sklearn with euclidean distance.
model_euc = AgglomerativeClustering(n_clusters=n_clusters, metric='euclidean')
labels_euc = model_euc.fit_predict(dataset)

# Agglomerative Clustering using sklearn with manhattan. Ignore the linkage parameter for now.
model_man = AgglomerativeClustering(n_clusters=n_clusters, metric='manhattan', linkage='average')
labels_man = model_man.fit_predict(dataset)

# Agglomerative Clustering using sklearn with cosine distance. Ignore the linkage parameter for now.
model_cos = AgglomerativeClustering(n_clusters=n_clusters, metric='cosine', linkage='average')
labels_cos = model_cos.fit_predict(dataset)

from sklearn.cluster import AgglomerativeClustering

# Agglomerative Clustering using sklearn with euclidean distance.
model_euc = AgglomerativeClustering(n_clusters=n_clusters, metric='euclidean')
labels_euc = model_euc.fit_predict(dataset)

# Agglomerative Clustering using sklearn with manhattan. Ignore the linkage parameter for now.
model_man = AgglomerativeClustering(n_clusters=n_clusters, metric='manhattan', linkage='average')
labels_man = model_man.fit_predict(dataset)

# Agglomerative Clustering using sklearn with cosine distance. Ignore the linkage parameter for now.
model_cos = AgglomerativeClustering(n_clusters=n_clusters, metric='cosine', linkage='average')
labels_cos = model_cos.fit_predict(dataset)

Python

# Function to calculate the distance matrix
def calculate_distance_matrix(X, clusters, distance_metric):
    # 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(distance_metric(X[k], X[l]))
            dist_matrix[i, j] = dist_matrix[j, i] = np.mean(dists)
    return dist_matrix

Python

def agglomerative_clustering(X, n_clusters, distance_metric):
    clusters = [[i] for i in range(len(X))]

    while len(clusters) > n_clusters:
        # Calculate the distance matrix using the method passed via distance_metric
        dist_matrix = calculate_distance_matrix(X, clusters, distance_metric)

        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])
        clusters.pop(idx2)

    labels = np.empty(len(X), dtype=int)
    for label, cluster in enumerate(clusters):
        for i in cluster:
            labels[i] = label

    return labels

Python

import matplotlib.pyplot as plt
from sklearn.datasets import load_iris
from sklearn.preprocessing import StandardScaler

# Load the Iris dataset
dataset = load_iris().data

# Scale the dataset with StandardScaler
scaler = StandardScaler()
dataset = scaler.fit_transform(dataset)

Python

# Perform Agglomerative Clustering
n_clusters = 3

# Euclidean Distance
labels_euc = agglomerative_clustering(dataset, n_clusters, euclidean_distance)

# Manhattan Distance
labels_man = agglomerative_clustering(dataset, n_clusters, manhattan_distance)

# Cosine Distance
labels_cos = agglomerative_clustering(dataset, n_clusters, cosine_distance)

Python

# Plot the results in 3 subplots for each distance metric
fig, axs = plt.subplots(1, 3, figsize=(15, 5))

# Euclidean Distance
axs[0].scatter(dataset[:, 0], dataset[:, 1], c=labels_euc, cmap='viridis')
axs[0].set_title('Euclidean Distance')
axs[0].set_xlabel('Sepal Length')
axs[0].set_ylabel('Sepal Width')

# Manhattan Distance
axs[1].scatter(dataset[:, 0], dataset[:, 1], c=labels_man, cmap='viridis')
axs[1].set_title('Manhattan Distance')
axs[1].set_xlabel('Sepal Length')
axs[1].set_ylabel('Sepal Width')

# Cosine Distance
axs[2].scatter(dataset[:, 0], dataset[:, 1], c=labels_cos, cmap='viridis')
axs[2].set_title('Cosine Distance')
axs[2].set_xlabel('Sepal Length')
axs[2].set_ylabel('Sepal Width')

plt.show()

Python

from sklearn.cluster import AgglomerativeClustering

# Agglomerative Clustering using sklearn with euclidean distance.
model_euc = AgglomerativeClustering(n_clusters=n_clusters, metric='euclidean')
labels_euc = model_euc.fit_predict(dataset)

# Agglomerative Clustering using sklearn with manhattan. Ignore the linkage parameter for now.
model_man = AgglomerativeClustering(n_clusters=n_clusters, metric='manhattan', linkage='average')
labels_man = model_man.fit_predict(dataset)

# Agglomerative Clustering using sklearn with cosine distance. Ignore the linkage parameter for now.
model_cos = AgglomerativeClustering(n_clusters=n_clusters, metric='cosine', linkage='average')
labels_cos = model_cos.fit_predict(dataset)

Introduction

Introduction to Distance Metrics

Implementing Distance Metrics in Python: Euclidean Distance

Implementing Distance Metrics in Python: Manhattan Distance

Implementing Distance Metrics in Python: Cosine Distance

Join the 1M+ learners on CodeSignal

Implementing Hierarchical Clustering

Studying the Impact of Distance Metrics

Configuring Distance Metrics with Sklearn

Lesson Summary and Practice