Understanding DBSCAN: A Guide to Density-Based Clustering in Python

Welcome to our introduction to Density-Based Clustering and the DBSCAN (Density-Based Spatial Clustering of Applications with Noise) algorithm! Clustering techniques group data based on given measures, with traditional techniques like K-Means focusing on distances between data points. However, Density-Based Clustering seeks areas of high density separated by areas of low density, making it adaptive to a variety of cluster shapes and sizes.

Today, we'll look into DBSCAN's workings and apply it to Python. By the end, you'll be proficient in Density-Based Clustering and be ready to use DBSCAN on a real-world clustering problem.

DBSCAN is a density-based clustering algorithm that groups together points based on their density. It has two main parameters: eps (epsilon) and MinPts. Here's a brief overview of the algorithm:

1. Initialize: Assign each point a label of 0 (unvisited) and create an empty list of clusters.
2. Iterate over points: For each point, check if it's visited. If not, mark it as visited and find its neighbors within eps distance.
3. Expand clusters: If a point has more than MinPts neighbors, it's a core point. Expand the cluster by adding all reachable points to the cluster.
4. Repeat: Continue until all points are visited.

DBSCAN classifies points into three categories: core points, border points, and noise points. Core points have at least MinPts neighbors within eps distance, border points are within eps distance of a core point, and noise points are neither core nor border points.

To demonstrate clustering with DBSCAN, we'll first generate some synthetic data using the make_blobs function from sklearn.datasets. This function generates isotropic Gaussian distributions, which are perfect for forming distinct 'blobs,' or clusters, of data.

from matplotlib import pyplot as plt
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs

# Generate synthetic data with two cluster centers and 180 samples
num_samples_total = 180
cluster_centers = [(3,3), (7,7)]
num_classes = len(cluster_centers)
epsilon = 1.0
min_samples = 13

data, y = make_blobs(n_samples = num_samples_total, centers = cluster_centers, n_features = num_classes, center_box=(0, 1), cluster_std = 0.5, random_state = 1)

Next, we'll implement the DBSCAN algorithm itself, along with some necessary helper functions. Specifically, we'll be creating a distance function, a function to perform a region query, and a function to grow a cluster.

The region_query function returns all points within a given radius eps from a point P. This helps DBSCAN identify densely populated areas.

def region_query(D, P, eps):
    neighbors = []
    for i in range(D.shape[0]):
        if calculate_distance(D[i], P) < eps:
            neighbors.append(i)
    return neighbors

The grow_cluster function expands discovered clusters by checking the eps neighbors and including those that meet the MinPts condition.

def grow_cluster(D, labels, P, NeighborPts, C, eps, MinPts):
    labels[P] = C
    i = 0
    while i < len(NeighborPts):
        Pn = NeighborPts[i]
        if labels[Pn] == -1 or labels[Pn] == 0:
            labels[Pn] = C
            PnNeighborPts = region_query(D, D[Pn], eps)
            if len(PnNeighborPts) >= MinPts:
                NeighborPts += [p for p in PnNeighborPts if labels[p] == 0]
        i += 1

Next, we will use our helper functions as building blocks for DBSCAN implementation.

def DBSCAN(D, eps, MinPts):
    C = 0
    labels = np.zeros(D.shape[0])
    for P in range(D.shape[0]):
        if labels[P] != 0:
            continue
        NeighborPts = region_query(D, D[P], eps)
        if len(NeighborPts) < MinPts:
            labels[P] = -1
        else:
            C += 1
            grow_cluster(D, labels, P, NeighborPts, C, eps, MinPts)
    return labels

Finally, we apply DBSCAN to our dataset with defined eps and MinPts.

labels = DBSCAN(D=data, eps=0.5, MinPts=5)

We represent grouped and non-grouped (Noise) data points using the matplotlib library. Here, '-1' marks Noise and is colored black

# Separating noise points
noise_points = data[labels == -1]

# Visualizing the clusters
colors = plt.cm.rainbow(np.linspace(0, 1, len(np.unique(labels))))

for i in range(len(data)):
    plt.plot(data[i][0], data[i][1], 'o', color=colors[int(labels[i] % len(colors))])
    
# Visualizing the noise points
plt.plot(noise_points[:, 0], noise_points[:, 1], 'o', color='black')
plt.title('Noise points')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')

plt.show()

Each color here represents a different cluster, helping us visualize the result of our DBSCAN run:

And we're done! You dove deep into Density-Based Clustering, implemented DBSCAN, and glimpsed the mathematical equations powering DBSCAN. As we move to the next set of exercises, apply DBSCAN to a variety of datasets and experiment with eps and MinPts parameters to observe their impact. Enjoy exploring clusters!