Module 5 — DBSCAN and clusters of arbitrary shape

The two previous modules shared one presupposition: a cluster is a compact cloud around a center. DBSCAN abandons that idea entirely and replaces it with density: a cluster is a region where points are packed together, whatever its shape. This change of definition fixes, in one stroke, the two main weaknesses of k-means — non-spherical shapes and outliers.

A cluster as a dense region

The intuition is one of contact from neighbor to neighbor. If two points are immediate neighbors, they belong to the same cluster; if my neighbor's neighbor has neighbors of its own, the cluster extends. By following dense zones this way, the cluster takes whatever shape the data give it: a crescent, a spiral, a ribbon.

Two parameters suffice to formalize this, and all of DBSCAN comes down to tuning them well:

• eps: the radius defining a point's neighborhood;
• min_samples: the number of neighbors required within that radius to call it a dense zone.

Three point statuses, one of them decisive

From these two parameters follows a classification of every point, and it is what makes the method distinctive:

Status	Definition	Role
core point	at least min_samples neighbors within eps	grows the cluster
border point	within a core point's neighborhood, without being one	attached, but does not propagate
noise	neither of the above	belongs to no cluster

The third row is the major contribution. k-means assigned every point, including outliers that dragged the centroids; DBSCAN explicitly labels them as noise, with the label -1. The clustering is thereby cleaned up, and the isolated points become natural candidates for the anomaly detection of module 8.

from sklearn.cluster import DBSCAN
db = DBSCAN(eps=0.5, min_samples=5).fit(X_s)
db.labels_                              # -1 denotes noise
(db.labels_ == -1).sum()                # noise volume: a tuning indicator
len(set(db.labels_)) - (1 if -1 in db.labels_ else 0)   # number of clusters found

Note that you do not supply the number of clusters: DBSCAN infers it from the structure. That is a real advantage, but it shifts the difficulty onto tuning eps.

Tuning eps without groping: the k-distance graph

An eps that is too small declares almost everything noise; too large, it merges all clusters into a single block. The standard way to calibrate it is graphical and reliable: for each point, compute the distance to its $k$-th nearest neighbor (with $k$ = min_samples), then plot these distances sorted in ascending order. The curve stays flat — dense points all have a close neighbor — then rises sharply once you reach the isolated points. The elbow of that curve is an excellent eps.

For min_samples, a common heuristic is to start from twice the number of variables. The higher it is, the more demanding the algorithm and the more noise it declares.

What DBSCAN does not solve

Honesty requires naming the limits, because they are real:

• varying densities: eps being global, a dataset containing one dense cluster and one diffuse cluster is handled poorly — a single radius cannot suit both;
• high dimensionality: DBSCAN rests on distances, so it suffers the curse of dimensionality (module 4 of the supervised course). In practice you reduce dimensionality first with PCA (module 6), then apply DBSCAN;
• no typical profiles: without centroids, interpretation requires summarizing each cluster yourself, for example by its means.

HDBSCAN, the natural sequel

The varying-density limit has a direct answer: HDBSCAN varies eps and keeps the clusters that remain stable across a range of densities. You then have only one intuitive parameter to supply — the minimum cluster size — and heterogeneous densities are handled. When DBSCAN gives a correct result on part of the data and an absurd one on the rest, this is the reflex to have.

Summary

• DBSCAN defines a cluster as a dense region, which lets it detect arbitrary shapes where k-means fails.
• Only two parameters: eps (neighborhood radius) and min_samples (required neighbors); the number of clusters is inferred, not imposed.
• Core, border and noise points: noise is explicitly set aside (label -1), which cleans up the clustering.
• You tune eps via the elbow of the k-distance graph; varying densities call for HDBSCAN, and high dimensionality for prior reduction.

Next module: principal component analysis, the first dimensionality reduction tool and an indispensable complement to everything above.