Definition
DBSCAN (Density-Based Spatial Clustering of Applications with Noise, Ester et al., 1996) calls a point core if at least points lie within distance of it, links core points that are within 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 and a distance → a label per point: cluster or noise ()
- Learns
- which points are core / border / noise, and the connected groups of core points; no centroids or parameters
- Training
- range queries: brute force; roughly with a k-d / ball tree in low dimensions and small
- Prediction
- not defined by the algorithm; the usual rule is one range query: join the cluster of a core point within , else noise
- Hyperparameters
- (neighbourhood radius), (
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 around every point and count who is inside it (the point itself included). If the count reaches , 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
- : all points within distance of , including (scikit-learn's convention, used throughout this article)
- minPts
- the density threshold: how many points an -ball must contain to count as dense (scikit-learn:
min_samples) - Core point
- — the interior of a cluster
- Border point
- not core, but inside the -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
- from : is core and . Not symmetric — a border point is reachable from a core point but not vice versa
- Density-reachable
- there is a chain where each is directly density-reachable from (all links except the last start at core points)
- Density-connected
- and are both density-reachable from some common point . This is the symmetric relation that defines a cluster
- k-distance
- distance from a point to its -th nearest point (itself counted first). A point is core exactly when its -distance is
The math
Fix a dataset , a distance , a radius and an integer . Everything follows from one set:
- the dataset (n points)
- the distance between points p and q — usually Euclidean
- neighbourhood radius
- the -neighbourhood of (contains itself)
- minimum neighbourhood size for a point to be core
- is directly density-reachable from
- a chain of one or more steps (density-reachability)
- and are density-connected
- a core point from which both are reachable
A cluster is a non-empty set that is maximal (if and then ) and connected (every satisfy ). Noise is whatever belongs to no cluster.
Deriving the algorithm from the definition
- 1Restrict to core points. Between two core points is symmetric: if both are core and , then and . So on core points, is "connected by a path of edges of length " — an equivalence relation.
- 2Clusters are graph components. Build the graph whose nodes are core points and whose edges join core points within . Two core points are density-connected iff they lie in the same connected component of (a common 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 is the number of components.
- 3Attach the borders. A non-core point is reachable only in the last hop of a chain, so it joins the cluster of any core point with — 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.
- 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 range queries the search is linear in the number of neighbour pairs.
What each hyperparameter does, mathematically
- ε up
- every grows, so more points become core and the graph gains edges: components merge, noise shrinks. In the limit one cluster, no noise.
- ε down
- loses edges: components split, then core points disappear and everything becomes noise. The density threshold scales as , so in high dimensions tiny changes in ε swing it enormously.
- minPts up
- raises 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, and (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) | 4 | core |
| P2 | (2, 1) | P1 (1.00), P3 (1.41), P4 (1.00) | 4 | core |
| P3 | (1, 2) | P1 (1.00), P2 (1.41), P4 (1.00), P5 (1.41) | 5 | core |
| P4 | (2, 2) | P1 (1.41), P2 (1.00), P3 (1.00), P5 (1.00) | 5 | core |
| P5 | (2, 3) | P3 (1.41), P4 (1.00), P6 (1.34) | 4 | core |
| P6 | (3.2, 3.6) | P5 (1.34) | 2 | border of A |
| P7 | (6, 5) | P8 (1.00), P9 (1.00), P10 (1.41) | 4 | core |
| P8 | (7, 5) | P7 (1.00), P9 (1.41), P10 (1.00), P11 (1.41) | 5 | core |
| P9 | (6, 6) | P7 (1.00), P8 (1.41), P10 (1.00) | 4 | core |
| P10 | (7, 6) | P7 (1.41), P8 (1.00), P9 (1.00), P11 (1.00), P12 (1.20) | 6 | core |
| P11 | (8, 6) | P8 (1.41), P10 (1.00) | 3 | border of B |
| P12 | (7, 7.2) | P10 (1.20) | 2 | border of B |
| P13 | (4.5, 1) | — (nearest: P2 at 2.50) | 1 | noise |
| P14 | (5, 7.5) | — (nearest: P9 at 1.80) | 1 | noise |
DBSCAN by hand
- 1Neighbourhoods. Compute all pairwise distances and count, for each point, how many lie within 1.5 (itself included) — the column. Example: P5 = (2, 3) reaches P4 at 1.00, P3 at and P6 at , so .
- 2Core test. for P1–P5 and P7–P10: 9 core points. P11 has 3, P6 and P12 have 2, P13 and P14 have only themselves.
- 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.
- 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.
- 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.
- 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.
- 7A new point. DBSCAN has no centroids, so a new is assigned the cluster of a core point within . is 1.118 from both P4 and P5 (core) → cluster A. : the nearest core point is P7 at 1.581 > 1.5 → noise.
| ε | minPts | Core points | Clusters | Noise | What changed |
|---|---|---|---|---|---|
| 1.0 | 4 | 2 | 2 | 6 | only P4 and P10 are core; P1, P6, P7, P12, P13, P14 become noise |
| 1.5 | 3 | 10 | 2 | 2 | P11 (3 points) becomes core |
| 1.5 | 4 | 9 | 2 | 2 | the worked example |
| 1.5 | 5 | 4 | 2 | 3 | only P3, P4, P8, P10 core; P6 is now noise |
| 2.0 | 4 | 11 | 2 | 1 | P14 joins B (1.80 from P9) |
| 2.5 | 4 | 12 | 2 | 0 | P13 joins A (2.50 from P2) — nothing is noise |
- 1for p in D: N(p) ← {q : d(p,q) ≤ ε}
- 2 core(p) ← |N(p)| ≥ minPts
- 3for p in D, core and unlabelled:
- 4 C ← C+1; label(p) ← C; Q ← [p]
- 5 while Q: p ← pop(Q)
- 6 if not core(p): continue
- 7 for q ∈ N(p), unlabelled:
- 8 label(q) ← C; push(q)
- 9unlabelled → noise
- 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.
The algorithm, step by step
DBSCAN(D, ε, minPts)
- 1Range queries. For every point , find — with a spatial index (k-d tree, ball tree) or a precomputed distance matrix.
- 2Mark core points: .
- 3Scan. For each point in order: skip it if it is labelled or not core. Otherwise create a new cluster , label with and put it in a queue.
- 4Expand. Pop from the queue. If is core, every unlabelled point in gets label and is pushed. If is a border point, do nothing more. Repeat until the queue is empty.
- 5Finish. Points still unlabelled are noise (−1).
Cost
- Range queries
- brute force time; with a tree index about each in low dimensions, so overall — but this degrades to per query when ε is large or is high
- Expansion
- : every point is queued once, every core point scans its list once
- Memory
- if neighbourhoods are recomputed on the fly; scikit-learn stores all neighbour lists, which is and can reach 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 , with 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 -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.
| Setting | Effect | Advice |
|---|---|---|
eps | radius of the neighbourhood; the main scale knob | read it off the k-distance knee after scaling features; small changes can merge or split clusters |
min_samples | density threshold and smoothing | start at 2·d (at least d+1); raise it for noisy data |
metric | what “close” means | Euclidean for scaled numeric data; cosine for embeddings / text; haversine for lat-lon (in radians) |
algorithm | neighbour search: auto, ball_tree, kd_tree, brute | trees for low d; brute with a precomputed sparse radius graph for high d |
sample_weight | a point of weight w counts w times toward min_samples | compress duplicate rows instead of repeating them |
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
1import numpy as np23def dbscan(X, eps, min_pts):4 n = len(X)5 D = np.sqrt(((X[:, None] - X[None]) ** 2).sum(-1)) # pairwise distances6 nbrs = [np.flatnonzero(D[i] <= eps) for i in range(n)] # N_eps(i), includes i7 core = np.array([len(nb) >= min_pts for nb in nbrs])8 labels = np.full(n, -1) # -1 = noise / unvisited9 c = -110 for i in range(n):11 if labels[i] != -1 or not core[i]:12 continue # only an unlabelled core starts a cluster13 c += 114 labels[i] = c15 queue = [i]16 while queue: # breadth-first flood fill17 p = queue.pop(0)18 if not core[p]:19 continue # border point: joins, never expands20 for q in nbrs[p]:21 if labels[q] == -1:22 labels[q] = c23 queue.append(q)24 return labels, core2526X = 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 noise1import numpy as np2from sklearn.cluster import DBSCAN3from sklearn.neighbors import NearestNeighbors45X = 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]])89db = DBSCAN(eps=1.5, min_samples=4).fit(X) # min_samples counts the point itself10print("labels:", db.labels_) # -1 = noise11print("core: ", db.core_sample_indices_ + 1) # 1-based point names1213# 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))1617# DBSCAN has no predict(): attach a new point to a core point within eps, else noise18core = 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))2324# 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]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 -ball holds at least points (itself included); border if it is within 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 , 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.