What you’ll learn

• the definitions of core, border and noise, and the reachability relations built on them
• the full algorithm traced by hand on ten points on a line
• why DBSCAN needs no $k$ — and why it cannot be asked for one
• how to choose epseps from the k-distance plot instead of guessing
• the measured eps sweep: 21 clusters, then 2, then 2, then 1
• DBSCAN against k-means on two datasets: ARI 1.00 vs 0.24, and 0.57 vs 0.94
• the varying-density failure, and why HDBSCAN exists

Intuition

k-means asks “which centre is this point nearest?” DBSCAN asks a different question entirely: “is this point in a crowd, and can I walk from crowd to crowd without leaving one?”

A cluster, in this view, is a connected region of high density. It has whatever shape the dense region has — a ring, a crescent, a branching filament. And crucially, points in the sparse gaps between clusters belong to nothing. DBSCAN is the only algorithm in this phase that can say “I don’t know” about a point.

Two parameters define “crowd”:

• epseps ($\varepsilon$) — the radius of the neighbourhood.
• min_samplesmin_samples — how many points must be inside that radius to count as dense.

Everything else follows mechanically.

  flowchart TD
  P["A point p"] --> Q{"At least min_samples points
within eps of p
(counting p itself)?"}
  Q -->|"yes"| C["CORE point.
Start or extend a cluster;
absorb the whole neighbourhood."]
  Q -->|"no"| R{"Is p within eps
of some core point?"}
  R -->|"yes"| B["BORDER point.
Joins that core point's cluster
but does not expand it."]
  R -->|"no"| N["NOISE.
Label -1. Belongs to nothing."]

The math

Write $N_\varepsilon(p)$ for the $\varepsilon$-neighbourhood of $p$:

Note that $p \in N_\varepsilon(p)$ — scikit-learn counts the point itself, so min_samples=5min_samples=5 means four neighbours plus the point.

Core point. $p$ is a core point if

Directly density-reachable. $q$ is directly density-reachable from $p$ if $p$ is a core point and $q \in N_\varepsilon(p)$. This relation is not symmetric: a border point is directly reachable from a core point, but not the other way round.

Density-reachable. $q$ is density-reachable from $p$ if there is a chain $p = p_1, p_2, \dots, p_m = q$ where each $p_{i+1}$ is directly density-reachable from $p_i$. Every link except possibly the last must be a core point. This is the transitive closure, and it is what lets a cluster snake around a crescent.

Density-connected. $p$ and $q$ are density-connected if some core point $o$ reaches both. This is symmetric, and it is the relation that actually defines a cluster.

A cluster is a maximal set $C$ satisfying:

1. Maximality: if $p \in C$ and $q$ is density-reachable from $p$, then $q \in C$.
2. Connectivity: every pair in $C$ is density-connected.

Anything in no cluster is noise.

One consequence of these definitions catches people out: a border point can be within $\varepsilon$ of core points from two different clusters. It joins whichever one reaches it first, so its label depends on iteration order. Core points are deterministic; border points are not.

Worked example by hand

Ten points on a line, with $\varepsilon = 0.6$ and min_samples = 3min_samples = 3:

Step one is to count each neighbourhood, remembering to include the point itself.

Now walk the algorithm:

1. Start at 1.0. Only 2 neighbours, not core — set aside for now.
2. Move to 1.4. Core. Open cluster 0 and absorb $N_\varepsilon(1.4) = \{1.0, 1.4, 1.8\}$. 1.0 joins as a border point.
3. 1.8 is in cluster 0 and is itself core, so absorb $\{1.4, 1.8, 2.1\}$ — 2.1 joins.
4. 2.1 is core, so absorb $\{1.8, 2.1, 2.5\}$ — 2.5 joins as a border point.
5. 2.5 is not core, so the expansion stops. Cluster 0 is $\{1.0, 1.4, 1.8, 2.1, 2.5\}$.
6. 6.0 has one neighbour (itself) and is within $\varepsilon$ of no core point. Noise, label -1.
7. 9.3 is core. Open cluster 1, absorb $\{9.0, 9.3, 9.7\}$; 9.7 is core, so absorb $\{9.3, 9.7, 10.1\}$. Cluster 1 is $\{9.0, 9.3, 9.7, 10.1\}$.

Final labels, in input order:

Two clusters and one noise point, and at no stage did anything ask how many clusters there should be. The gap at 6.0 is what separates them, and the gap is a property of the data.

figureThe three point types, with their neighbour countsmatplotlib

See it move

The next sketch makes the reachability chain explicit — click anywhere to drop a seed and watch the cluster flood outward, one core point at a time.

Seed inside one crescent and the flood traces it end to end, then stops — the gap to the other crescent is wider than epseps, so no chain of core points crosses it. Seed on an isolated noise point and nothing happens at all: it is not core, so it never expands.

eps is the whole ballgame

min_samplesmin_samples is forgiving. epseps is not. Here is one dataset — 320 points forming two crescents plus 40 scattered noise points — under four values:

Too small and the crescents shatter into fragments while a quarter of the data becomes noise. Too large and everything — including the scattered clutter — fuses into a single cluster. The useful range here is roughly 0.15 to 0.35.

figureOne parameter, four completely different answersmatplotlib

By contrast, min_samplesmin_samples barely moves the answer at eps = 0.16:

Stable until it isn’t: at 20, no point in this dataset has 19 neighbours within 0.16, so everything is noise. The usual heuristic is min_samplesmin_samples $\ge p + 1$, and $2p$ is a common default for $p$ features.

Choosing eps from the data

Do not guess. For each point, compute the distance to its $k$-th nearest neighbour (with $k =$ min_samplesmin_samples), sort those distances, and plot them. Points inside a cluster have small $k$-distances; noise points have large ones. The knee of the curve — where it turns sharply upward — separates the two populations, and its height is a good epseps.

On the dataset above, with $k = 5$, the median 5-distance is 0.0818 and the knee sits around 0.1408 — right in the working range the sweep identified.

figureThe k-distance plot picks eps for youmatplotlib

import numpy as np
from sklearn.neighbors import NearestNeighbors
 
k = 5                                     # same as min_samples
nn = NearestNeighbors(n_neighbors=k).fit(X)
distances, _ = nn.kneighbors(X)
k_dist = np.sort(distances[:, -1])        # distance to the kth neighbour, sorted
 
import matplotlib.pyplot as plt
plt.plot(k_dist)
plt.ylabel(f"distance to {k}th nearest neighbour")
plt.xlabel("points, sorted")
plt.show()                                # read eps off the knee

import numpy as np
from sklearn.neighbors import NearestNeighbors
 
k = 5                                     # same as min_samples
nn = NearestNeighbors(n_neighbors=k).fit(X)
distances, _ = nn.kneighbors(X)
k_dist = np.sort(distances[:, -1])        # distance to the kth neighbour, sorted
 
import matplotlib.pyplot as plt
plt.plot(k_dist)
plt.ylabel(f"distance to {k}th nearest neighbour")
plt.xlabel("points, sorted")
plt.show()                                # read eps off the knee

DBSCAN against k-means

figureEach one wins where the other losesmatplotlib

Both results follow directly from the assumptions. k-means draws straight boundaries, which is wrong for crescents and right for separated blobs. DBSCAN follows density, which traces crescents perfectly and cannot separate two blobs whose densities merge where they touch.

The failure mode: varying density

DBSCAN has exactly one global epseps. If one genuine cluster is dense and another is sparse, no single value serves both: pick a small eps and the sparse cluster becomes noise; pick a large one and the dense clusters merge.

You saw this on the intro page’s third column — the wide cluster dissolved into noise while the tight ones survived.

HDBSCAN fixes this by running DBSCAN at every eps simultaneously and extracting the clusters that persist over the widest range of scales. It replaces epseps with min_cluster_sizemin_cluster_size, which is a far more interpretable question (“what is the smallest group I care about?”). It is in scikit-learn from version 1.3 as sklearn.cluster.HDBSCANsklearn.cluster.HDBSCAN.

from sklearn.cluster import DBSCAN, HDBSCAN
 
db = DBSCAN(eps=0.16, min_samples=5).fit_predict(X)     # 2 clusters, 29 noise
hd = HDBSCAN(min_cluster_size=15).fit_predict(X)        # 2 clusters, 28 noise

from sklearn.cluster import DBSCAN, HDBSCAN
 
db = DBSCAN(eps=0.16, min_samples=5).fit_predict(X)     # 2 clusters, 29 noise
hd = HDBSCAN(min_cluster_size=15).fit_predict(X)        # 2 clusters, 28 noise

On this well-behaved dataset HDBSCAN matches DBSCAN almost exactly — which is the point: you got the same answer without having to find eps first. On varying-density data it wins outright.

OPTICS takes a related approach, producing a reachability plot from which clusterings at many eps values can be extracted. It is slower and its output takes practice to read; on the same dataset with default xi=0.05xi=0.05 it returned 21 clusters and 140 noise points, which is a fair warning that it needs tuning of its own.

In code

import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons
 
X, y = make_moons(n_samples=300, noise=0.06, random_state=4)
 
db = DBSCAN(eps=0.25, min_samples=5).fit(X)
 
labels = db.labels_
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
print("clusters", n_clusters)                    # 2
print("noise   ", int((labels == -1).sum()))     # 0
 
# Which points are core? DBSCAN tells you directly.
core_mask = np.zeros(len(X), dtype=bool)
core_mask[db.core_sample_indices_] = True
print("core   ", int(core_mask.sum()))
print("border ", int(((labels != -1) & ~core_mask).sum()))

import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons
 
X, y = make_moons(n_samples=300, noise=0.06, random_state=4)
 
db = DBSCAN(eps=0.25, min_samples=5).fit(X)
 
labels = db.labels_
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
print("clusters", n_clusters)                    # 2
print("noise   ", int((labels == -1).sum()))     # 0
 
# Which points are core? DBSCAN tells you directly.
core_mask = np.zeros(len(X), dtype=bool)
core_mask[db.core_sample_indices_] = True
print("core   ", int(core_mask.sum()))
print("border ", int(((labels != -1) & ~core_mask).sum()))

Three things to know about the API:

Noise is label -1-1. Never call len(set(labels))len(set(labels)) and assume that is the cluster count; use the subtraction above. And never feed -1-1 into silhouette_scoresilhouette_score without deciding what it means — the usual choice is to score only the clustered points.

There is no predictpredict. DBSCAN defines clusters relative to the training set. To label a new point, the standard workaround is to assign it to the cluster of its nearest core sample, if one is within eps:

import numpy as np
from sklearn.neighbors import NearestNeighbors
 
def dbscan_assign(db, X_train, X_new, eps):
    """Assign new points to the cluster of the nearest core sample, else noise."""
    cores = X_train[db.core_sample_indices_]
    core_labels = db.labels_[db.core_sample_indices_]
    dist, idx = NearestNeighbors(n_neighbors=1).fit(cores).kneighbors(X_new)
    out = core_labels[idx[:, 0]]
    out[dist[:, 0] > eps] = -1
    return out

import numpy as np
from sklearn.neighbors import NearestNeighbors
 
def dbscan_assign(db, X_train, X_new, eps):
    """Assign new points to the cluster of the nearest core sample, else noise."""
    cores = X_train[db.core_sample_indices_]
    core_labels = db.labels_[db.core_sample_indices_]
    dist, idx = NearestNeighbors(n_neighbors=1).fit(cores).kneighbors(X_new)
    out = core_labels[idx[:, 0]]
    out[dist[:, 0] > eps] = -1
    return out

Scale first, and use an index. With a ball tree or KD tree, DBSCAN runs in $O(n \log n)$; without one it degrades to $O(n^2)$. scikit-learn picks an index automatically for low-dimensional Euclidean data, but in high dimensions the index stops helping and you are back to quadratic.

Pitfalls

Guessing eps. The sweep above went 21 → 2 → 2 → 1 clusters over a four-fold range. Always plot the k-distance curve first.

Forgetting -1-1 in the cluster count. len(set(labels))len(set(labels)) counts noise as a cluster. It also breaks any code that indexes an array by label.

Not scaling. eps is a single radius in the raw feature space. If one column runs to 50,000 and another to 1, eps is entirely determined by the first.

Expecting predictpredict. It does not exist, and the nearest-core-sample workaround above is an approximation you should test before relying on.

Using it in high dimensions. Beyond roughly 10 to 20 features, the distance to the nearest neighbour and to the farthest converge, the k-distance plot flattens out, and there is no knee to read. Reduce dimensions with PCA first — or accept that density-based clustering is the wrong tool.

Treating border-point labels as stable. A border point reachable from two clusters joins whichever the iteration reaches first. Core points are deterministic; border assignments are not.

Applying it to clusters of different density. This is the built-in limitation, not a tuning problem. Reach for HDBSCAN.

Compare

🧪 Try It Yourself

Exercise 1 – Core, border and noise by hand

Exercise 2 – Confirm it against sklearn

Exercise 3 – Sweep eps and watch it break

Exercise 4 – Read eps off the k-distance curve

Exercise 5 – Where each algorithm wins

Recap

• A point is core if its eps-neighbourhood (including itself) holds at least min_samplesmin_samples points, border if it is inside a core point’s disc, noise otherwise.
• A cluster is a maximal density-connected set. That definition needs no $k$ and imposes no shape.
• The hand trace on ten points gave labels [0 0 0 0 0 -1 1 1 1 1][0 0 0 0 0 -1 1 1 1 1] — two clusters, one noise point.
• epseps is the model: 21 clusters at 0.08, 2 at 0.16 and 0.30, 1 at 0.60 on identical data. min_samplesmin_samples is stable from 3 to 10 and then collapses everything to noise at 20.
• Choose eps from the k-distance knee: 0.1408 here, and the sweep confirmed the range.
• DBSCAN beat k-means 1.00 to 0.24 on moons and lost 0.57 to 0.94 on touching blobs.
• One global eps cannot serve clusters of different density. HDBSCAN removes that limitation and replaces eps with min_cluster_sizemin_cluster_size.
• There is no predictpredict, noise is label -1-1, and high dimensions destroy the notion of density.

Exercise 6 – Sweep eps and watch the model change species

Next

Anomaly Detection with Isolation Forests — DBSCAN found outliers as a side effect of clustering. The next page makes finding them the whole objective, and does it in a way that gets faster as the data gets bigger.