DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is a popular density-based clustering algorithm that groups data points based on their density in feature space. It’s beneficial for datasets with clusters of varying shapes, sizes, and densities, and can identify noise or outliers.

Step 1: Initialize Parameters

Define two important parameters:

• Epsilon (ε): The maximum distance between two points for them to be considered neighbors.
• Minimum Points (minPts): The minimum number of points required in an ε-radius neighborhood for a point to be considered a core point.

Step 2: Label Each Point as Core, Border, or Noise

For each data point $P$ in the dataset:

1. Find all points within the ε radius of $P$ (the ε-neighborhood of $P$).
2. Core Point: If $P$ has at least minPts points within its ε-neighborhood, it’s marked as a core point.
3. Border Point: If $P$ has fewer than minPts points in its ε-neighborhood but is within the ε-neighborhood of a core point, it’s labeled a border point.
4. Noise Point: If $P$ doesn’t satisfy either condition (not enough neighbors, not within a core point's neighborhood), it’s marked as noise.

Step 3: Form Clusters from Core Points

1. Start with an unvisited core point: A new cluster begins if the point is a core point.
2. Expand the cluster: Add all reachable points within ε of the core point to the cluster. Mark each added point as "visited."
3. For each new point added to the cluster:
   • If it’s also a core point, repeat the expansion process by adding all its reachable neighbors within ε to the cluster.
   • If it’s a border point, add it to the cluster but don’t expand further from it (since it doesn’t have enough density to expand).

Step 4: Mark Noise Points

Any points not assigned to any cluster during the expansion process are labeled as noise or outliers.

Step 5: Repeat for All Unvisited Points

Continue with the remaining unvisited points:

• If the next unvisited point is a core point, start a new cluster and expand it.
• If it's a border point or noise, mark it accordingly without forming a new cluster.

Step 6: Output the Clusters

When all points are visited, DBSCAN completes, resulting in clusters of core and border points, and isolated points marked as noise.

Implementation

# Import necessary libraries

import numpy as np

import matplotlib.pyplot as plt

from sklearn.cluster import DBSCAN

from sklearn.datasets import make_moons

# Generate synthetic data (e.g., with two moon-shaped clusters)

X, _ = make_moons(n_samples=300, noise=0.05, random_state=42)

# Define DBSCAN parameters

epsilon = 0.2  # Radius for neighborhood

min_samples = 5  # Minimum number of points for a core point

# Apply DBSCAN clustering

dbscan = DBSCAN(eps=epsilon, min_samples=min_samples)

labels = dbscan.fit_predict(X)

# Plotting the clusters and noise

unique_labels = set(labels)

colors = plt.cm.Spectral(np.linspace(0, 1, len(unique_labels)))

# Plot each cluster with a different color, mark noise as black

for label, color in zip(unique_labels, colors):

    if label == -1:  # Noise points have a label of -1

        color = "black"  # Mark noise as black

    class_members = (labels == label)

    plt.plot(X[class_members, 0], X[class_members, 1], "o", markerfacecolor=color, markeredgecolor="k", markersize=6)

plt.title("DBSCAN Clustering")

plt.xlabel("Feature 1")

plt.ylabel("Feature 2")

plt.show()