Distance Metrics in Clustering

What Are Distance Metrics?

Distance metrics are mathematical formulas used to measure how far apart two points are. In clustering, these metrics help us determine how similar or different data points are from each other. The choice of distance metric can significantly affect the clustering results.

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

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

Similarity = \frac{A \cdot B}{||A|| \cdot ||B||}

The distance metric you choose determines how the clustering algorithm groups data points. Let’s see how to use these metrics in a hierarchical clustering algorithm by first creating a flexible distance matrix function. Distance Matrix Function: Rcalculate_distance_matrix <- function(X, clusters, distance_metric) { n <- length(clusters) dist_matrix <- matrix(0, nrow = n, ncol = n) for (i in seq_along(clusters)) { if (is.null(clusters[[i]])) next for (j in seq_along(clusters)) { if (j <= i || is.null(clusters[[j]])) next dists <- c() for (k in clusters[[i]]) { for (l in clusters[[j]]) { dists <- c(dists, distance_metric(X[k, ], X[l, ])) } } dist_matrix[i, j] <- dist_matrix[j, i] <- mean(dists) } } return(dist_matrix) }

Now, let’s use the distance matrix in an agglomerative clustering function that accepts any distance metric. Agglomerative Clustering Function: Ragglomerative_clustering <- function(X, n_clusters, distance_metric) { clusters <- lapply(1:nrow(X), function(i) i) while (length(Filter(Negate(is.null), clusters)) > n_clusters) { dist_matrix <- calculate_distance_matrix(X, clusters, distance_metric) dist_matrix[lower.tri(dist_matrix, diag = TRUE)] <- Inf min_idx <- which(dist_matrix == min(dist_matrix), arr.ind = TRUE)[1, ] idx1 <- min_idx[1] idx2 <- min_idx[2] clusters[[idx1]] <- c(clusters[[idx1]], clusters[[idx2]]) clusters[[idx2]] <- NULL } labels <- rep(NA, nrow(X)) valid_clusters <- Filter(Negate(is.null), clusters) for (label in seq_along(valid_clusters)) { for (i in valid_clusters[[label]]) { labels[i] <- label } } return(labels) }

Let’s use the Iris dataset and scale it for clustering. R library(datasets) library(scales) dataset <- as.matrix(iris[, 1:4]) dataset <- scale(dataset) Scaling the data before clustering is important because some distance metrics, like Euclidean and Manhattan, are sensitive to the scale of the variables. If features are measured on different scales, those with larger ranges can dominate the distance calculations, leading to biased clustering results. Scaling ensures that each feature contributes equally to the distance computation. In contrast, cosine distance is less affected by the scale of the variables, as it measures the angle between vectors rather than their magnitude.

Now, cluster the data using each distance metric. R n_clusters <- 3 labels_euc <- agglomerative_clustering(dataset, n_clusters, euclidean_distance) labels_man <- agglomerative_clustering(dataset, n_clusters, manhattan_distance) labels_cos <- agglomerative_clustering(dataset, n_clusters, cosine_distance)

Let’s visualize how the choice of distance metric affects clustering. Prepare Data for Plotting: R library(ggplot2) library(dplyr) library(tidyr) plot_data <- as.data.frame(dataset) plot_data$Sepal.Length <- iris$Sepal.Length plot_data$Sepal.Width <- iris$Sepal.Width plot_data$Euclidean <- as.factor(labels_euc) plot_data$Manhattan <- as.factor(labels_man) plot_data$Cosine <- as.factor(labels_cos) plot_data_long <- plot_data %>% select(Sepal.Length, Sepal.Width, Euclidean, Manhattan, Cosine) %>% pivot_longer(cols = c(Euclidean, Manhattan, Cosine), names_to = "Metric", values_to = "Cluster") Plot with ggplot2: R ggplot(plot_data_long, aes(x = Sepal.Length, y = Sepal.Width, color = Cluster)) + geom_point(size = 2, alpha = 0.8) + facet_wrap(~ Metric, nrow = 1) + labs(title = "Hierarchical Clustering with Different Distance Metrics", x = "Sepal Length", y = "Sepal Width") + theme_bw() + scale_color_brewer(palette = "Set1")

You can also use R’s built-in functions for hierarchical clustering with different distance metrics. Euclidean and Manhattan: Rd_euc <- dist(dataset, method = "euclidean") hc_euc <- hclust(d_euc, method = "average") labels_euc <- cutree(hc_euc, k = n_clusters) d_man <- dist(dataset, method = "manhattan") hc_man <- hclust(d_man, method = "average") labels_man <- cutree(hc_man, k = n_clusters) Cosine Distance (Manual Calculation): Rcosine_distance_matrix <- function(X) { n <- nrow(X) dist_mat <- matrix(0, n, n) for (i in 1:(n-1)) { for (j in (i+1):n) { sim <- sum(X[i, ] * X[j, ]) / (sqrt(sum(X[i, ]^2)) * sqrt(sum(X[j, ]^2))) dist <- 1 - sim dist_mat[i, j] <- dist dist_mat[j, i] <- dist } } as.dist(dist_mat) } d_cos <- cosine_distance_matrix(dataset) hc_cos <- hclust(d_cos, method = "average") labels_cos <- cutree(hc_cos, k = n_clusters)

Prepare Data: R plot_data$Euclidean <- as.factor(labels_euc) plot_data$Manhattan <- as.factor(labels_man) plot_data$Cosine <- as.factor(labels_cos) plot_data_long <- plot_data %>% select(Sepal.Length, Sepal.Width, Euclidean, Manhattan, Cosine) %>% pivot_longer(cols = c(Euclidean, Manhattan, Cosine), names_to = "Metric", values_to = "Cluster") Plot: R ggplot(plot_data_long, aes(x = Sepal.Length, y = Sepal.Width, color = Cluster)) + geom_point(size = 2, alpha = 0.8) + facet_wrap(~ Metric, nrow = 1) + labs(title = "Hierarchical Clustering with Different Distance Metrics (hclust)", x = "Sepal Length", y = "Sepal Width") + theme_minimal() + scale_color_brewer(palette = "Set1")

Distance metrics define how similarity is measured in clustering. Euclidean, Manhattan, and Cosine distances each have unique properties and applications. The choice of metric can significantly change clustering results, as seen in the visualizations.

Excellent work! You've just mastered the concepts and the importance of distance metrics in hierarchical clustering. You've implemented these metrics in R and applied them in the agglomerative clustering algorithm. In the end, you studied the impact of these distance metrics on the clustering results using ggplot2 for clear and effective visualization. Next, get ready to solidify this knowledge through related exercises!