I5 · Machine Learning Foundations

DBSCAN: Density-Based Clustering

DBSCAN (Density-Based Spatial Clustering of Applications with Noise, 1996) defines clusters as dense regions separated by sparse ones. It has two settings: eps (ε), a neighbourhood radius, and min_samples, the minimum number of points within eps for a point to be a core point. Core points that are within eps of each other join the same cluster; border points are within eps of a core point but are not core themselves; all other points are labelled noise (−1). DBSCAN does not need the number of clusters in advance and can find clusters of arbitrary shape.

10 min Intermediate · Sublevel Intermediate Jump to the activity

What you need: The earlier topics of this module.

Definition

Look at a night photo of India from space. The bright patches are cities: some round, some stretched along rivers or coasts, with scattered lights between them. k-means would chop these into round blobs. DBSCAN finds crowded regions of any shape and leaves lonely points as noise.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise, 1996) defines clusters as dense regions separated by sparse ones. It has two settings: eps (ε), a neighbourhood radius, and min_samples, the minimum number of points within eps for a point to be a core point. Core points that are within eps of each other join the same cluster; border points are within eps of a core point but are not core themselves; all other points are labelled noise (−1). DBSCAN does not need the number of clusters in advance and can find clusters of arbitrary shape.

In simple words

Imagine a fair ground seen from above. Wherever people stand shoulder to shoulder, that is a crowd. A crowd can be any shape, a long queue or a big circle round a stage. People standing alone between crowds are not part of any crowd. DBSCAN finds the crowds and marks the loners.

Overview

  • DBSCAN (1996) finds clusters as dense regions separated by sparse ones.
  • It uses two settings: eps, a neighbourhood radius, and min_samples, the points needed to be a core point.
  • Points are core, border or noise; noise gets label −1.
  • It finds clusters of any shape and does not need the number of clusters.
  • A k-distance plot helps choose eps; features must be scaled.
  • It struggles when clusters have very different densities.

Why it matters

Real clusters are often not round, and real data contains noise. DBSCAN handles both, which is why it is used on GPS and map data, to find hot spots of accidents or disease cases, to group sensor readings and to separate genuine clusters from outliers before further analysis.

Key terms

eps (ε)
The radius that defines a point's neighbourhood.
min_samples
Points needed within eps (including the point itself) to be a core point.
Core point
A point with at least min_samples neighbours within eps.
Border point
A non-core point within eps of a core point; it joins that cluster.
Noise point
A point that is neither core nor border; labelled −1.
k-distance plot
A sorted plot of each point's distance to its k-th nearest neighbour, used to choose eps.

Types

DBSCAN labels points as three types and has several related algorithms. Both are explained here.

1. Core points

Points with at least min_samples neighbours within eps, counting themselves.

  • How it works: Core points start and grow clusters: any core point within eps of another joins the same cluster.
  • Example: With eps = 1.5 and min_samples = 3, point 2 among 1, 2, 3 is a core point.
  • When to use it: Recognise them as the dense heart of each cluster.

2. Border points

Non-core points within eps of a core point.

  • How it works: They join the cluster of a nearby core point but do not spread it further.
  • Example: Points 1 and 3 in the example join point 2's cluster.
  • When to use it: Recognise them as the edges of clusters; a border point near two clusters is assigned to whichever is found first.

3. Noise points

Points that are neither core nor border.

  • How it works: They are labelled −1 and belong to no cluster, which makes DBSCAN useful for spotting outliers.
  • Example: In the moons example, DBSCAN marked 7 scattered points as noise.
  • When to use it: Inspect them: they may be errors, rare events or a sign that eps is too small.

4. HDBSCAN

A hierarchical extension of DBSCAN that handles clusters of varying density.

  • How it works: It builds a hierarchy over all eps values and keeps the most stable clusters, so only min_cluster_size must be set.
  • Example: Finding both a dense city centre and sparse suburbs of taxi pick-ups in one run.
  • When to use it: Use it when one eps cannot fit every cluster; it is available in scikit-learn.

5. OPTICS

An ordering algorithm (1999) that records the density structure for all eps values at once.

  • How it works: It produces a reachability plot whose valleys are clusters; clusters can then be extracted at different density levels.
  • Example: Exploring nested clusters of earthquakes along a fault line.
  • When to use it: Use it to explore density structure before choosing parameters.

Explained in detail

How DBSCAN grows clusters

DBSCAN visits each point and counts how many points lie within distance eps. If the count reaches min_samples, the point is a core point and starts a cluster. The cluster then expands: every neighbour is added, and any neighbour that is itself a core point adds its own neighbours too, so the cluster spreads through chains of dense regions. Border points are added but do not spread the cluster further. When no more points can be reached, DBSCAN moves to the next unvisited point. Points never reached from any core point are noise. Because clusters spread along dense paths, DBSCAN can follow curved shapes such as two interleaving half-moons, a ring or a river, which k-means, with its round clusters around centres, cannot. In the code below, k-means splits two half-moons badly (adjusted Rand index 0.46), while DBSCAN recovers both moons exactly (1.00) and labels 7 scattered points as noise.

k-means compared with DBSCAN

k-meansDBSCAN
Number of clustersMust be chosen (k)Found automatically
Cluster shapeRoughly round, similar sizeAny shape
OutliersForced into a cluster; pull centresLabelled as noise
Settingskeps and min_samples
WeaknessNon-round shapesClusters of very different densities

Choosing eps and min_samples

A common rule is to set min_samples to about twice the number of features (at least 3 or 4), then draw a k-distance plot: for each point compute the distance to its min_samples-th nearest neighbour, sort these distances and plot them. The curve stays low for points inside clusters and rises sharply for outliers; the "elbow" where it bends upward is a good eps. Too small an eps labels most points as noise; too large merges separate clusters into one. Features must be scaled, because eps is a single distance used in every direction. DBSCAN struggles when clusters have very different densities, since one eps cannot fit both a dense city and a sparse village; HDBSCAN, an extension, handles varying density and is available in scikit-learn.

Real-world scenarios: city planners run DBSCAN on accident locations to find dangerous junctions, since accidents cluster along roads in long, irregular shapes; delivery companies group GPS pings into stops and treat isolated pings as noise; and astronomers find groups of stars in sky surveys. In each case the number of clusters is unknown in advance and the noise points are worth a second look.

How it works

  1. Scale the features.
  2. Choose min_samples, for example 4 for two features.
  3. Draw the k-distance plot and pick eps at the elbow.
  4. Run DBSCAN and count clusters and noise points.
  5. Inspect noise points: they may be errors or interesting anomalies.

The maths

eps-neighbourhood
Core point condition

Seven points lie on a line at 1, 2, 3, 7, 8, 9 and 15, with eps = 1.5 and min_samples = 3. Point 2 has neighbours 1, 2 and 3 within 1.5, which is 3 points, so it is a core point; points 1 and 3 have only 2 neighbours each, so they are border points that join point 2's cluster. In the same way 8 is core and 7 and 9 are border points. Point 15 has only itself within 1.5 and is not near any core point, so it is noise. Result: two clusters, {1, 2, 3} and {7, 8, 9}, plus one noise point. k-means with k = 2 would have had to put 15 into a cluster, dragging that centre towards it.

In code

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

# The worked example on a line
line = np.array([[1], [2], [3], [7], [8], [9], [15]])
print("Line labels:", DBSCAN(eps=1.5, min_samples=3).fit_predict(line))

# Two interleaving half-moons plus a few scattered noise points
X, y = make_moons(n_samples=300, noise=0.06, random_state=0)
rng = np.random.default_rng(1)
X = np.vstack([X, rng.uniform([-1.5, -1.0], [2.5, 1.5], size=(10, 2))])
y = np.concatenate([y, -np.ones(10, dtype=int)])
Xs = StandardScaler().fit_transform(X)

dist, _ = NearestNeighbors(n_neighbors=4).fit(Xs).kneighbors(Xs)
k_dist = np.sort(dist[:, -1])
print("4th-neighbour distance at the 50th, 90th and 99th percentile:", np.percentile(k_dist, [50, 90, 99]).round(2))

km = KMeans(n_clusters=2, n_init=10, random_state=0).fit_predict(Xs)
db = DBSCAN(eps=0.3, min_samples=4).fit_predict(Xs)
moons = y >= 0
print(f"k-means agreement with true moons: {adjusted_rand_score(y[moons], km[moons]):.2f}")
print(f"DBSCAN agreement with true moons:  {adjusted_rand_score(y[moons], db[moons]):.2f}")
print("DBSCAN found", len(set(db)) - (1 if -1 in db else 0), "clusters and", int((db == -1).sum()), "noise points")

Output

Line labels: [ 0  0  0  1  1  1 -1]
4th-neighbour distance at the 50th, 90th and 99th percentile: [0.1  0.15 0.69]
k-means agreement with true moons: 0.46
DBSCAN agreement with true moons:  1.00
DBSCAN found 2 clusters and 7 noise points

Try it yourself

Compare with k-means

Run k-means on the dots and notice that every dot, even a stray one, must join a centre. DBSCAN would leave strays as noise and follow curved crowds.

Core, border or noise?

With eps = 1 and min_samples = 3 on points at 0, 0.5, 1, 1.8 and 6:

  • Point 6

  • Point 1.8 (neighbours 1, 1.8)

  • Point 1 (neighbours 0, 0.5, 1, 1.8)

  • Point 0.5 (neighbours 0, 0.5, 1)

Common mistakes

  • Forgetting to scale features before choosing eps.
  • Using one eps when clusters have very different densities.
  • Discarding noise points without looking at them.

Check yourself

Question 1

1. What does DBSCAN label as −1?

Question 2

2. Which shape can DBSCAN find but k-means usually cannot?

Question 3

3. Raising eps a lot will usually…

Summary

  • DBSCAN finds dense regions of any shape and marks sparse points as noise.
  • Core, border and noise points follow from eps and min_samples.
  • Scale features, choose eps from a k-distance plot, and use HDBSCAN for varying densities.

Finished reading?

Sources: Ester, Kriegel, Sander and Xu (1996), A density-based algorithm for discovering clusters (DBSCAN), KDD-96 · scikit-learn: clustering (k-means, hierarchical, DBSCAN)