DBSCAN

A cluster is a dense region grown from points with at least minPts neighbours within ε; points in no dense region are noise.

16 min read1581 wordscore6 viewsupdated 2026-10-07

Definition

DBSCAN (Density-Based Spatial Clustering of Applications with Noise, Ester et al., 1996) calls a point core if at least minPts\text{minPts} points lie within distance ε\varepsilon of it, links core points that are within ε\varepsilon of each other, and returns each linked group — plus the non-core points hanging on its edge — as a cluster. Everything else is labelled noise. The number of clusters is not an input; it falls out of the data.

At a glance

Task
Unsupervised clustering with built-in outlier detection
Input → output
points x1,…,xnx_1,\dots,x_n and a distance → a label per point: cluster 1…k1\dots k or noise (−1-1)
Learns
which points are core / border / noise, and the connected groups of core points; no centroids or parameters
Training
nn range queries: O(n2)O(n^2) brute force; roughly O(nlog⁡n)O(n\log n) with a k-d / ball tree in low dimensions and small ε\varepsilon
Prediction
not defined by the algorithm; the usual rule is one range query: join the cluster of a core point within ε\varepsilon, else noise
Hyperparameters
ε\varepsilon (neighbourhood radius), minPts\text{minPts} (min_samples), the distance metric
Assumes
clusters are regions of roughly one common density, separated by sparser gaps; distances are meaningful (features scaled)

The problem

k-means and Gaussian mixtures describe each cluster by a centre (and for GMMs a covariance). That builds in three assumptions that real data often breaks: clusters are blob-shaped, you know how many there are, and every point belongs somewhere. Give k-means two interleaved crescents and it cuts them with a straight line; give it a handful of sensor glitches and it drags a centroid toward them, because an outlier's squared distance is the most expensive thing in its objective.

Look at a scatter plot the way a person does and you see something different: clusters are places where points are crowded, separated by places where they are sparse. A crescent is a cluster because you can walk along it without ever crossing an empty gap. DBSCAN turns that picture into an algorithm: measure crowding locally, then connect the crowded points.

The idea

Draw a disc of radius ε\varepsilon around every point and count who is inside it (the point itself included). If the count reaches minPts\text{minPts}, the point sits in a dense spot: it is a core point. Two core points whose discs contain each other belong to the same cluster, and so does every chain of such links — a cluster is grown like a flood fill, hopping from core point to core point. Non-core points that sit inside some core point's disc are swept in as the border of that cluster, but the flood never continues through them. Points that no flood ever reaches are noise.

Vocabulary

ε-neighbourhood
Nε(p)N_\varepsilon(p): all points within distance ε\varepsilon of pp, including pp (scikit-learn's convention, used throughout this article)
minPts
the density threshold: how many points an ε\varepsilon-ball must contain to count as dense (scikit-learn: min_samples)
Core point
∣Nε(p)∣≥minPts|N_\varepsilon(p)|\ge\text{minPts} — the interior of a cluster
Border point
not core, but inside the ε\varepsilon-ball of at least one core point — the fringe of a cluster
Noise point
neither core nor border: not within ε of any core point. Gets label −1
Directly density-reachable
qq from pp: pp is core and q∈Nε(p)q\in N_\varepsilon(p). Not symmetric — a border point is reachable from a core point but not vice versa
Density-reachable
there is a chain p=p1,…,pm=qp=p_1,\dots,p_m=q where each pi+1p_{i+1} is directly density-reachable from pip_i (all links except the last start at core points)
Density-connected
pp and qq are both density-reachable from some common point oo. This is the symmetric relation that defines a cluster
k-distance
distance from a point to its kk-th nearest point (itself counted first). A point is core exactly when its minPts\text{minPts}-distance is ≤ε\le\varepsilon

The math

Fix a dataset DD, a distance dd, a radius ε>0\varepsilon>0 and an integer minPts≥1\text{minPts}\ge1. Everything follows from one set:

Nε(p)={ q∈D: d(p,q)≤ε },core(p)  ⟺  ∣Nε(p)∣≥minPtsN_\varepsilon(p)=\{\,q\in D:\ d(p,q)\le\varepsilon\,\},\qquad \text{core}(p)\iff |N_\varepsilon(p)|\ge \text{minPts}
DD
the dataset (n points)
d(p,q)d(p,q)
the distance between points p and q — usually Euclidean
ε\varepsilon
neighbourhood radius
Nε(p)N_\varepsilon(p)
the ε\varepsilon-neighbourhood of pp (contains pp itself)
minPts\text{minPts}
minimum neighbourhood size for a point to be core
p→q  ⟺  core(p) ∧ q∈Nε(p)p \rightarrow q \iff \text{core}(p)\ \wedge\ q\in N_\varepsilon(p)
p→qp\rightarrow q
qq is directly density-reachable from pp
p∼q  ⟺  ∃ o∈D: o→∗p  and  o→∗qp \sim q \iff \exists\, o\in D:\ o \rightarrow^{*} p\ \ \text{and}\ \ o\rightarrow^{*} q
→∗\rightarrow^{*}
a chain of one or more →\rightarrow steps (density-reachability)
p∼qp\sim q
pp and qq are density-connected
oo
a core point from which both are reachable

A cluster is a non-empty set C⊆DC\subseteq D that is maximal (if p∈Cp\in C and p→∗qp\rightarrow^* q then q∈Cq\in C) and connected (every p,q∈Cp,q\in C satisfy p∼qp\sim q). Noise is whatever belongs to no cluster.

Deriving the algorithm from the definition

  1. 1Restrict to core points. Between two core points →\rightarrow is symmetric: if both are core and d(p,q)≤εd(p,q)\le\varepsilon, then p→qp\rightarrow q and q→pq\rightarrow p. So on core points, →∗\rightarrow^* is "connected by a path of edges of length ≤ε\le\varepsilon" — an equivalence relation.
  2. 2Clusters are graph components. Build the graph GG whose nodes are core points and whose edges join core points within ε\varepsilon. Two core points are density-connected iff they lie in the same connected component of GG (a common oo exists exactly when there is a path). By maximality each component, with everything reachable from it, is one cluster — so the cores of different clusters never mix, and the number of clusters kk is the number of components.
  3. 3Attach the borders. A non-core point qq is reachable only in the last hop of a chain, so it joins the cluster of any core point pp with q∈Nε(p)q\in N_\varepsilon(p) — and adds no further edges. That is why the flood fill must not expand from a border point: doing so would glue together two clusters that merely touch the same fringe point.
  4. 4Search the components. Breadth-first search from each not-yet-labelled core point visits exactly one component plus its borders. Every point is enqueued at most once, so after the nn range queries the search is linear in the number of neighbour pairs.

What each hyperparameter does, mathematically

ε up
every NεN_\varepsilon grows, so more points become core and the graph GG gains edges: components merge, noise shrinks. In the limit one cluster, no noise.
ε down
GG loses edges: components split, then core points disappear and everything becomes noise. The density threshold scales as ε−d\varepsilon^{-d}, so in high dimensions tiny changes in ε swing it enormously.
minPts up
raises λ\lambda at fixed ε: fewer core points, more noise, thin bridges between clusters are cut. It also smooths: one stray point can no longer form or connect a cluster.
minPts = 1 or 2
every point is core (minPts = 1) or every pair within ε is linked (minPts = 2): DBSCAN reduces to single-linkage clustering cut at height ε (isolated points as noise), with its chaining problem.

Worked example: 14 points

Two groups of points, a couple of stragglers, Euclidean distance, ε=1.5\varepsilon=1.5 and minPts=4\text{minPts}=4 (the point itself plus at least 3 others).

Point(x, y)Others within ε = 1.5|N_ε|Type
P1(1, 1)P2 (1.00), P3 (1.00), P4 (1.41)4core
P2(2, 1)P1 (1.00), P3 (1.41), P4 (1.00)4core
P3(1, 2)P1 (1.00), P2 (1.41), P4 (1.00), P5 (1.41)5core
P4(2, 2)P1 (1.41), P2 (1.00), P3 (1.00), P5 (1.00)5core
P5(2, 3)P3 (1.41), P4 (1.00), P6 (1.34)4core
P6(3.2, 3.6)P5 (1.34)2border of A
P7(6, 5)P8 (1.00), P9 (1.00), P10 (1.41)4core
P8(7, 5)P7 (1.00), P9 (1.41), P10 (1.00), P11 (1.41)5core
P9(6, 6)P7 (1.00), P8 (1.41), P10 (1.00)4core
P10(7, 6)P7 (1.41), P8 (1.00), P9 (1.00), P11 (1.00), P12 (1.20)6core
P11(8, 6)P8 (1.41), P10 (1.00)3border of B
P12(7, 7.2)P10 (1.20)2border of B
P13(4.5, 1)— (nearest: P2 at 2.50)1noise
P14(5, 7.5)— (nearest: P9 at 1.80)1noise
The data, with each point's ε-neighbourhood (ε = 1.5, distances in brackets) and the resulting type. Highlighted: the core points.

DBSCAN by hand

  1. 1Neighbourhoods. Compute all pairwise distances and count, for each point, how many lie within 1.5 (itself included) — the ∣Nε∣|N_\varepsilon| column. Example: P5 = (2, 3) reaches P4 at 1.00, P3 at 2=1.41\sqrt{2}=1.41 and P6 at 1.22+0.62=1.8=1.34\sqrt{1.2^2+0.6^2}=\sqrt{1.8}=1.34, so ∣Nε(P5)∣=4|N_\varepsilon(\text{P5})|=4.
  2. 2Core test. ∣Nε∣≥4|N_\varepsilon|\ge4 for P1–P5 and P7–P10: 9 core points. P11 has 3, P6 and P12 have 2, P13 and P14 have only themselves.
  3. 3Cluster A. Scan in order: P1 is an unlabelled core point, so it seeds cluster A. Its neighbours P2, P3, P4 join and are queued. Popping P2 adds nothing new; popping P3 adds P5; P4 adds nothing; popping P5 (core) adds P6.
  4. 4Stop at the border. P6 is popped but is not core, so the search does not continue from it. Cluster A = {P1, …, P6} — 5 core points + 1 border point. Note the asymmetry: P6 is reachable from P5, but P5 is not reachable from P6.
  5. 5Cluster B. The scan continues to P7, the next unlabelled core point: it seeds B and brings in P8, P9, P10. P8 adds P11, P10 adds P12; both are border points and expand nothing. Cluster B = {P7, …, P12} — 4 core + 2 border.
  6. 6Noise. P13 and P14 were never reached: P13's nearest point is P2 at 2.50, and P14 is 1.80 from P9 — both farther than ε. Result: 2 clusters, 2 noise points, with no number of clusters ever specified.
  7. 7A new point. DBSCAN has no centroids, so a new xx is assigned the cluster of a core point within ε\varepsilon. x=(3,2.5)x=(3, 2.5) is 1.118 from both P4 and P5 (core) → cluster A. x=(4.5,4.5)x=(4.5, 4.5): the nearest core point is P7 at 1.581 > 1.5 → noise.
εminPtsCore pointsClustersNoiseWhat changed
1.04226only P4 and P10 are core; P1, P6, P7, P12, P13, P14 become noise
1.531022P11 (3 points) becomes core
1.54922the worked example
1.55423only P3, P4, P8, P10 core; P6 is now noise
2.041121P14 joins B (1.80 from P9)
2.541220P13 joins A (2.50 from P2) — nothing is noise
The same 14 points under other settings. Lower ε or higher minPts removes core points; ε = 1.5, minPts = 5 makes P5 non-core (only 4 points), which strands P6 as noise.
▸ DBSCAN · worked examplestep 1/32
0123456789012345678P1P2P3P4P5P6P7P8P9P10P11P12P13P14corebordernoise
ε = 1.5 · minPts = 4core: 0clusters: 0queue: —
  1. 1for p in D: N(p) ← {q : d(p,q) ≤ ε}
  2. 2 core(p) ← |N(p)| ≥ minPts
  3. 3for p in D, core and unlabelled:
  4. 4 C ← C+1; label(p) ← C; Q ← [p]
  5. 5 while Q: p ← pop(Q)
  6. 6 if not core(p): continue
  7. 7 for q ∈ N(p), unlabelled:
  8. 8 label(q) ← C; push(q)
  9. 9unlabelled → noise
  10. 10new x: C of a core within ε, else noise

14 points, ε = 1.5, minPts = 4 (a point counts itself). First, every point counts the points inside its ε-ball.

▸ density explorer162 points · drag the ✛ probe
ε = 0.10sorted 5-distance(self counts as 1st)0.00.10.20.3ε = 0.108 not corepoints, sorted →
clusters 2 · core 154 · border 2 · noise 6 (6 of 12 injected)
ARI vs true moons = 1.000
probe: 1 point within ε → joins cluster A
fig.Top: the worked example, step by step — each point's ε = 1.5 ball and neighbour count (9 come out core), then the breadth-first flood fill from P1 (cluster A, 6 points) and P7 (cluster B, 6 points), border points P6, P11 and P12 joining without expanding, P13 and P14 left as noise, and the two new points classified. Bottom: 150 two-moon points plus 12 uniform noise points. Drag the ε and minPts sliders: at the default ε = 0.10, minPts = 5 there are 154 core points, 2 clusters, 6 noise points and ARI 1.000 against the true moons; ε = 0.05 shatters them into 11 clusters with 15 noise points; at ε = 0.13 the moons merge into one. The right panel is the sorted 5-distance curve — every point above the dashed ε line is not core. Toggle k-means (k = 2) to see it score ARI 0.356 on the same moons. Drag the probe to see how a new point would be labelled.

The algorithm, step by step

DBSCAN(D, ε, minPts)

  1. 1Range queries. For every point pp, find Nε(p)N_\varepsilon(p) — with a spatial index (k-d tree, ball tree) or a precomputed distance matrix.
  2. 2Mark core points: core(p)←∣Nε(p)∣≥minPts\text{core}(p)\leftarrow|N_\varepsilon(p)|\ge\text{minPts}.
  3. 3Scan. For each point pp in order: skip it if it is labelled or not core. Otherwise create a new cluster CC, label pp with CC and put it in a queue.
  4. 4Expand. Pop qq from the queue. If qq is core, every unlabelled point in Nε(q)N_\varepsilon(q) gets label CC and is pushed. If qq is a border point, do nothing more. Repeat until the queue is empty.
  5. 5Finish. Points still unlabelled are noise (−1).

Cost

Range queries
brute force O(n2)O(n^2) time; with a tree index about O(log⁡n)O(\log n) each in low dimensions, so O(nlog⁡n)O(n\log n) overall — but this degrades to O(n)O(n) per query when ε is large or dd is high
Expansion
O(n+∑p∣Nε(p)∣)O(n + \sum_p|N_\varepsilon(p)|): every point is queued once, every core point scans its list once
Memory
O(n)O(n) if neighbourhoods are recomputed on the fly; scikit-learn stores all neighbour lists, which is O(∑p∣Nε(p)∣)O(\sum_p|N_\varepsilon(p)|) and can reach O(n2)O(n^2) for a large ε
Determinism
core points and noise are fully determined; only a border point within ε of two clusters can change label with the visiting order

Choosing ε and minPts

Pick minPts first. It is a smoothing level, not a scale: a common rule is minPts≥d+1\text{minPts}\ge d+1, with minPts=2d\text{minPts}=2d a good default (Sander et al., 1998) and larger values for noisy or duplicate-heavy data. Then pick ε from the k-distance plot: compute every point's distance to its minPts\text{minPts}-th nearest point (itself counted), sort, and plot. Points inside clusters have small k-distances; noise has large ones. Put ε at the knee, where the curve turns sharply upward. In the worked example the sorted 4-distances are 1.00, 1.00, 1.41 (×7), 1.56, 1.56, then jump to 2.50, 2.72, 2.91 — any ε from 1.56 up to just under 2.5 keeps those last three as non-core.

SettingEffectAdvice
epsradius of the neighbourhood; the main scale knobread it off the k-distance knee after scaling features; small changes can merge or split clusters
min_samplesdensity threshold and smoothingstart at 2·d (at least d+1); raise it for noisy data
metricwhat “close” meansEuclidean for scaled numeric data; cosine for embeddings / text; haversine for lat-lon (in radians)
algorithmneighbour search: auto, ball_tree, kd_tree, brutetrees for low d; brute with a precomputed sparse radius graph for high d
sample_weighta point of weight w counts w times toward min_samplescompress duplicate rows instead of repeating them
The knobs that matter in practice (scikit-learn names).

Variants and relatives

DBSCAN*
border points are treated as noise, so the result no longer depends on the visiting order (used inside HDBSCAN)
OPTICS
orders points by reachability distance once, so clusterings for every ε ≤ ε_max can be read off one plot — see the OPTICS article
HDBSCAN
builds the full hierarchy over all density levels and keeps the most stable clusters; handles clusters of different densities and needs only a minimum cluster size — see HDBSCAN
GDBSCAN / ST-DBSCAN
generalize the neighbourhood predicate and the density count, e.g. separate radii in space and time for trajectories
Mean shift
another density method, but it climbs to the modes of a smooth KDE instead of thresholding a flat one — see Mean Shift

In code

python
1import numpy as np
2
3def dbscan(X, eps, min_pts):
4 n = len(X)
5 D = np.sqrt(((X[:, None] - X[None]) ** 2).sum(-1)) # pairwise distances
6 nbrs = [np.flatnonzero(D[i] <= eps) for i in range(n)] # N_eps(i), includes i
7 core = np.array([len(nb) >= min_pts for nb in nbrs])
8 labels = np.full(n, -1) # -1 = noise / unvisited
9 c = -1
10 for i in range(n):
11 if labels[i] != -1 or not core[i]:
12 continue # only an unlabelled core starts a cluster
13 c += 1
14 labels[i] = c
15 queue = [i]
16 while queue: # breadth-first flood fill
17 p = queue.pop(0)
18 if not core[p]:
19 continue # border point: joins, never expands
20 for q in nbrs[p]:
21 if labels[q] == -1:
22 labels[q] = c
23 queue.append(q)
24 return labels, core
25
26X = np.array([[1, 1], [2, 1], [1, 2], [2, 2], [2, 3], [3.2, 3.6],
27 [6, 5], [7, 5], [6, 6], [7, 6], [8, 6], [7, 7.2],
28 [4.5, 1], [5, 7.5]])
29labels, core = dbscan(X, eps=1.5, min_pts=4)
30kind = np.where(core, "core", np.where(labels >= 0, "border", "noise"))
31for i, (l, k) in enumerate(zip(labels, kind), 1):
32 print(f"P{i:<2} cluster {l:>2} {k}")
33# P1-P5 cluster 0 core, P6 cluster 0 border, P7-P10 cluster 1 core,
34# P11, P12 cluster 1 border, P13, P14 cluster -1 noise
From scratch in NumPy: neighbourhoods, core test, breadth-first expansion. Prints the labels from the worked example.
python
1import numpy as np
2from sklearn.cluster import DBSCAN
3from sklearn.neighbors import NearestNeighbors
4
5X = np.array([[1, 1], [2, 1], [1, 2], [2, 2], [2, 3], [3.2, 3.6],
6 [6, 5], [7, 5], [6, 6], [7, 6], [8, 6], [7, 7.2],
7 [4.5, 1], [5, 7.5]])
8
9db = DBSCAN(eps=1.5, min_samples=4).fit(X) # min_samples counts the point itself
10print("labels:", db.labels_) # -1 = noise
11print("core: ", db.core_sample_indices_ + 1) # 1-based point names
12
13# Choosing eps: distance to the 4th nearest point (the point itself is the 1st)
14d4 = NearestNeighbors(n_neighbors=4).fit(X).kneighbors(X)[0][:, -1]
15print("sorted 4-distances:", np.sort(d4).round(3))
16
17# DBSCAN has no predict(): attach a new point to a core point within eps, else noise
18core = X[db.core_sample_indices_]
19nn = NearestNeighbors(n_neighbors=1).fit(core)
20dist, idx = nn.kneighbors([[3, 2.5], [4.5, 4.5]])
21new = np.where(dist[:, 0] <= db.eps, db.labels_[db.core_sample_indices_][idx[:, 0]], -1)
22print("new points:", new, "nearest-core distances:", dist[:, 0].round(3))
23
24# labels: [ 0 0 0 0 0 0 1 1 1 1 1 1 -1 -1]
25# core: [ 1 2 3 4 5 7 8 9 10]
26# sorted 4-distances: [1. 1. 1.414 1.414 1.414 1.414 1.414 1.414 1.414 1.562 1.562 2.5 2.72 2.907]
27# new points: [ 0 -1] nearest-core distances: [1.118 1.581]
scikit-learn on the same data, the k-distance values used to choose ε, and labelling new points via the core samples.

Use when

  • +Clusters have arbitrary shapes — crescents, rings, road networks, river bends.
  • +You do not know the number of clusters, and want it found from the data.
  • +The data contain outliers that should be flagged, not forced into a cluster.
  • +Clusters have similar density and a meaningful distance scale (e.g. metres on a map).

Avoid when

  • −Clusters differ a lot in density — use HDBSCAN or OPTICS.
  • −The data are high-dimensional without a good metric: ε cannot be chosen.
  • −Clusters touch through thin bridges of points: they get chained into one.
  • −You need a model that labels new points cheaply, or soft memberships — use a Gaussian mixture.

Where it's used

Geospatial hot spots

GPS fixes, crime reports or taxi pickups with the haversine metric and ε in metres: dense places become clusters, isolated pings become noise.

Anomaly and fraud screening

Transactions or log events that land in no dense region are the noise label — an outlier detector with no training labels.

Point clouds and imagery

Segmenting LiDAR scans into objects, and grouping detections or pixels in astronomy and microscopy where shapes are irregular.

Trajectories and sensors

Finding stay points in movement data and recurring operating modes in machine telemetry (with ST-DBSCAN for space + time).

Check yourself

With ε = 1.5 and minPts = 4, point P11 = (8, 6) has 3 points in its ε-ball (itself, P8, P10), and P10 is a core point. P11 is…

Check yourself

In the worked example, keep ε = 1.5 but raise minPts from 4 to 5. What happens to P6 = (3.2, 3.6)?

Check yourself

Why does the expansion step never continue from a border point?

Check yourself

On the two-moons explorer (minPts = 5), what happens as ε increases from 0.05 to 0.13?

Remember

  • ✓A point is core if its ε\varepsilon-ball holds at least minPts\text{minPts} points (itself included); border if it is within ε\varepsilon of a core point; otherwise noise.
  • ✓Clusters are the connected components of the graph of core points linked within ε, plus their border points — found by breadth-first search that never expands from a border point.
  • ✓The number of clusters is an output, shapes can be arbitrary, and outliers are labelled −1 rather than forced into a cluster.
  • ✓DBSCAN thresholds a flat-kernel density estimate at one level λ=minPts/(nVdεd)\lambda=\text{minPts}/(nV_d\varepsilon^d), so it cannot handle clusters of very different densities — that is what OPTICS and HDBSCAN fix.
  • ✓Choose minPts ≈ 2·d, then read ε off the knee of the sorted k-distance plot — after scaling features.
← back to ML Algorithms roadmap