DBSCAN and Density-Based Clustering

Imagine plotting GPS locations of mobile-phone users in a city. People concentrate in markets, campuses and neighbourhoods of irregular shape, with scattered points everywhere in between. k-means would force every point into one of $k$ round clusters. What we really want is to find dense regions of any shape and to label isolated points as noise. That is exactly what DBSCAN (Density-Based Spatial Clustering of Applications with Noise, Ester et al., 1996) does.

Core idea#

A cluster is a maximal set of density-connected points. Density is measured with two parameters:

• $\varepsilon$ (eps): the radius of a neighbourhood;
• min_samples: the minimum number of points (including the point itself) required in that neighbourhood.

Every point becomes one of three types:

1. Core point — has at least min_samples points within distance $\varepsilon$.
2. Border point — not a core point, but within $\varepsilon$ of a core point.
3. Noise point — neither; labelled as an outlier (label −1).

The algorithm#

1. For each unvisited point, find its $\varepsilon$-neighbourhood.
2. If it is a core point, start a new cluster and expand it: add all density-reachable points — neighbours of core points, their core neighbours' neighbours, and so on.
3. Border points join the cluster of a neighbouring core point; points reachable from no core point are noise.

Formally, $q$ is directly density-reachable from core point $p$ if $q$ lies within $\varepsilon$ of $p$. Density-reachability is the transitive closure through chains of core points, and two points are density-connected if both are reachable from a common core point.

Why DBSCAN is useful#

• Arbitrary shapes — rings, crescents, winding streets.
• No need to choose $k$ — the number of clusters emerges from the data.
• Explicit noise detection — outliers are not forced into clusters.
• Deterministic for core points (border points may depend on processing order).

import numpy as np
from sklearn.datasets import make_moons
from sklearn.cluster import DBSCAN, KMeans
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import adjusted_rand_score

X, y = make_moons(n_samples=600, noise=0.07, random_state=0)
X = np.vstack([X, np.random.default_rng(0).uniform(-1.5, 2.5, (30, 2))])   # add scattered noise
y = np.r_[y, [-1] * 30]
Xs = StandardScaler().fit_transform(X)

km = KMeans(n_clusters=2, n_init=10, random_state=0).fit(Xs)
db = DBSCAN(eps=0.25, min_samples=8).fit(Xs)
print("k-means ARI:", round(adjusted_rand_score(y, km.labels_), 3))
print("DBSCAN  ARI:", round(adjusted_rand_score(y, db.labels_), 3),
      "| clusters:", len(set(db.labels_) - {-1}), "| noise points:", int((db.labels_ == -1).sum()))

DBSCAN recovers both crescents and flags most of the scattered points as noise; k-means slices the moons in half.

Choosing the parameters#

min_samples: a common heuristic is $2d$ for $d$-dimensional data (at least 3–5 even in 2-D). Larger values make clustering more conservative and more robust to noise.

eps: use the k-distance plot. For each point, compute the distance to its $k$-th nearest neighbour ($k$ = min_samples − 1), sort these distances, and plot them. Choose $\varepsilon$ at the "knee" where the curve bends sharply upward — points beyond the knee are in sparse regions.

from sklearn.neighbors import NearestNeighbors
k = 7
dist, _ = NearestNeighbors(n_neighbors=k + 1).fit(Xs).kneighbors(Xs)
kdist = np.sort(dist[:, -1])
print("suggested eps range (80th–95th percentile):", np.percentile(kdist, [80, 95]).round(3))

HDBSCAN: the modern upgrade#

HDBSCAN (Campello, Moulavi & Sander, 2013) removes the need to pick $\varepsilon$ and handles varying densities:

1. It builds a hierarchy of DBSCAN clusterings over all values of $\varepsilon$ (using a "mutual reachability" distance that smooths density estimates).
2. It condenses the hierarchy, keeping clusters that persist over a wide range of densities (stability).
3. It returns a flat clustering, noise labels, and a membership probability for each point.

Its main parameter, min_cluster_size, is intuitive. HDBSCAN is available in scikit-learn (sklearn.cluster.HDBSCAN) and is widely used to cluster text embeddings — for example, in topic-modelling pipelines that combine sentence embeddings, UMAP and HDBSCAN.

from sklearn.cluster import HDBSCAN
hdb = HDBSCAN(min_cluster_size=20).fit(Xs)
print("HDBSCAN ARI:", round(adjusted_rand_score(y, hdb.labels_), 3))

Complexity#

With a spatial index (KD-tree or ball tree), DBSCAN runs in roughly $O(n\log n)$ for low-dimensional data; the worst case is $O(n^2)$.

Comparing clustering algorithms#