DBSCAN Distance Metrics

Welcome! Today, we'll delve deeper into Density-Based Spatial Clustering of Applications with Noise (DBSCAN) parameters. In particular, we'll explore one crucial yet often overlooked parameter — the distance metric, which defines the distance function used in clustering.

Let's start by generating some sample data for our experiment. We'll manually create two crescent-shaped (moon-shaped) clusters, a common example for demonstrating the capabilities of DBSCAN with non-linearly separable data.

# Set seed for reproducibility
set.seed(42)

# Generate two crescent-shaped (moon-shaped) clusters
n <- 200
theta <- runif(n, 0, pi)
x1 <- cbind(cos(theta), sin(theta)) + matrix(rnorm(2 * n, sd = 0.05), ncol = 2)
x2 <- cbind(1 - cos(theta), 1 - sin(theta) - 0.5) + matrix(rnorm(2 * n, sd = 0.05), ncol = 2)
moon_data <- as.data.frame(rbind(x1, x2))
colnames(moon_data) <- c("x", "y")

This code generates 400 data points forming two crescent-shaped groups. This type of data is often used to illustrate the capabilities of algorithms like DBSCAN that can capture complex cluster shapes.

Before applying DBSCAN, it's important to standardize the features, especially when using distance-based algorithms. Standardization ensures that each feature contributes equally to the distance calculations.

moon_scaled <- as.data.frame(scale(moon_data))

We'll fit DBSCAN to our standardized data using three popular distances: Euclidean, Manhattan, and Cosine.

First, install and load the required packages if you haven't already:

# install.packages("dbscan")
# install.packages("proxy")
# install.packages("ggplot2")
# install.packages("dplyr")
# install.packages("scales")

library(dbscan)
library(proxy)
library(ggplot2)
library(dplyr)
library(scales)

Now, let's compute the distance matrices and run DBSCAN with the updated eps values:

# DBSCAN with Euclidean distance (default)
db_eu <- dbscan(moon_scaled, eps = 0.18, minPts = 5)
moon_eu <- moon_scaled %>%
  mutate(cluster = as.factor(db_eu$cluster), method = "Euclidean")

# DBSCAN with Manhattan distance
dist_man <- dist(moon_scaled, method = "manhattan")
db_man <- dbscan(dist_man, eps = 0.3, minPts = 10, search = "dist")
moon_man <- moon_scaled %>%
  mutate(cluster = as.factor(db_man$cluster), method = "Manhattan")

# DBSCAN with Cosine distance
dist_cos <- proxy::dist(moon_scaled, method = "cosine")
db_cos <- dbscan(dist_cos, eps = 0.3, minPts = 5, search = "dist")
moon_cos <- moon_scaled %>%
  mutate(cluster = as.factor(db_cos$cluster), method = "Cosine")

• The Euclidean metric calculates the straight-line distance between two points.
• The Manhattan metric measures the sum of absolute differences.
• The Cosine metric calculates the cosine of the angle between two points.

Note: When using a precomputed distance matrix, set search = "dist" in the dbscan function.

Now that we have our models, let's visualize how different distance metrics affect the DBSCAN results. We'll use ggplot2 to create scatterplots, coloring each point by its assigned cluster and faceting by the distance metric.

# Combine results for plotting
all_data <- bind_rows(moon_eu, moon_man, moon_cos)

# Build color palette
unique_clusters <- sort(unique(all_data$cluster))
n_clusters <- length(unique_clusters)
palette <- c("0" = "gray80", hue_pal()(n_clusters - 1))
names(palette)[-1] <- as.character(setdiff(unique_clusters, "0"))

# Plot using facets
plot <- ggplot(all_data, aes(x = x, y = y, color = cluster)) +
  geom_point(size = 2.5, alpha = 0.9) +
  facet_wrap(~ method, nrow = 1) +
  scale_color_manual(values = palette, name = "Cluster") +
  labs(
    title = "DBSCAN with Scaled Features and Multiple Distance Metrics",
    subtitle = "Standardized features used for Euclidean, Manhattan, and Cosine distances",
    x = "X (standardized)", y = "Y (standardized)"
  ) +
  theme_minimal(base_size = 14) +
  theme(
    panel.background = element_rect(fill = "white", color = NA),
    plot.background = element_rect(fill = "white", color = NA),
    strip.background = element_rect(fill = "white", color = NA),
    strip.text = element_text(face = "bold", size = 15),
    plot.title = element_text(face = "bold", size = 18, hjust = 0.5),
    plot.subtitle = element_text(size = 13, hjust = 0.5),
    legend.position = "right"
  )

print(plot)

In these scatterplots, each point represents a sample, with the color indicating the cluster assigned by DBSCAN. Faceting allows you to compare the effect of each distance metric side by side.

After running the code above, you will see a faceted plot displaying the clustering results for each distance metric. Each facet corresponds to one of the distance metrics: Euclidean, Manhattan, and Cosine.

In R, the dbscan package primarily uses a straightforward approach for neighbor search and does not expose multiple algorithm options like some other libraries. The main way to influence the clustering is by choosing the distance metric, either by specifying it directly or by providing a precomputed distance matrix. For large datasets, consider using the kNN or frNN functions from the dbscan package for efficient neighbor search, but the choice of algorithm is not as configurable as in some other environments.

You've learned how different distance metrics influence the DBSCAN algorithm in R. By experimenting with Euclidean, Manhattan, and Cosine distances, you can observe how the choice of metric affects the clustering results. Keep exploring these parameters and see how they impact your own datasets.