DBSCAN Clustering - Unsupervised Learning

DBSCAN Clustering

What you'll build

dbscan(X, eps, min_samples): density-based clustering that returns a cluster id for every point, or -1 for noise, with the same labels as scikit-learn's DBSCAN(eps=eps, min_samples=min_samples) (Euclidean metric).

Background

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) finds clusters of any shape as regions where points are packed densely, and labels points in sparse regions as noise. Unlike k-means you don't choose the number of clusters, and outliers don't drag centroids around. It is a common choice for anomaly detection and geospatial data.

Definitions

• The eps-neighbourhood of point p: all points q with ||p - q|| <= eps, including p itself.
• p is a core point if its neighbourhood has at least min_samples points (counting p), as in scikit-learn.
• A border point is not core but lies in the neighbourhood of some core point.
• Everything else is noise (label -1).

Algorithm

labels = [-1] * n;  cluster = 0
for p in 0 .. n-1:                        # scan in index order
    if labels[p] != -1 or p is not core:  continue
    labels[p] = cluster;  queue = [p]
    while queue:
        q = queue.pop(0)                  # q is always a core point
        for each neighbour r of q:
            if labels[r] == -1:
                labels[r] = cluster
                if r is core: queue.append(r)
    cluster += 1

1. Only core points expand a cluster; border points join a cluster but don't spread it.
2. Clusters are numbered in order of discovery: cluster 0 contains the lowest-indexed core point, cluster 1 the lowest-indexed core point not in cluster 0, and so on.

Inputs

• X: data, shape (n, d)
• eps: neighbourhood radius (> 0); a distance exactly equal to eps counts
• min_samples: minimum neighbourhood size (point included) for a core point, >= 1

Expected Return Format

An int array of shape (n,): -1 for noise, otherwise the cluster id 0, 1, 2, ....

Edge cases and conventions

• A border point within reach of two clusters keeps the label of the first cluster that reached it (the one discovered earlier) and is never reassigned. This is also what scikit-learn does; it is the one order-dependent part of DBSCAN.
• min_samples = 1: every point is core, so isolated points become singleton clusters and nothing is noise.
• If no point is core, every label is -1.

Constraints

• NumPy only (no sklearn). Vectorise the distance matrix; the cluster expansion is a plain loop.

Follow-up

• How would you pick eps? (Plot each point's distance to its min_samples-th neighbour, sorted, and look for the knee.)
• The distance matrix is O(n^2) memory. How do spatial indexes (k-d trees, ball trees) help?

Input: dbscan(np.array([[0.0, 0.0], [0.0, 1.0], [1.0, 0.0], [10.0, 10.0], [10.0, 11.0], [11.0, 10.0], [50.0, 50.0]]), 1.5, 3)
Output: [0, 0, 0, 1, 1, 1, -1]

Input: dbscan(np.array([[0.0], [0.3], [0.6], [1.4], [2.2], [2.5], [2.8], [10.0]]), 0.9, 4)
Output: [0, 0, 0, 0, 1, 1, 1, -1]

import numpy as np

def dbscan(X, eps, min_samples):
    """
    DBSCAN clustering (Euclidean distance, same labels as sklearn).

    Args:
        X: Data, shape (n, d)
        eps: Neighbourhood radius (distance <= eps counts, the point itself included)
        min_samples: Minimum neighbourhood size for a core point

    Returns:
        Int array of shape (n,): -1 for noise, clusters numbered 0, 1, ...
        in order of discovery when scanning points by index
    """
    # Your code here
    pass