DBSCAN: Core, Border, Noise ClassificationOpen in Colab

DBSCAN: Core, Border, Noise Classification

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) finds clusters as dense connected regions without requiring KK in advance. Its key insight: a "cluster" is a maximal set of core points and their reachable neighbors, where a core point has at least min_samples points within radius ε\varepsilon.

The two parameters

  • ε\varepsilon (eps): radius of the neighborhood around each point
  • min_samples: minimum number of points (including the point itself) to form a dense region

Classifying points as core, border, or noise

For a point pp, let Nε(p)={q:d(p,q)≤ε}N_\varepsilon(p) = \{q : d(p,q) \le \varepsilon\} be its ε\varepsilon-neighborhood, which includes pp itself.

TypeConditionRole
Core∣Nε(p)∣≥min_samples\lvert N_\varepsilon(p)\rvert \ge \text{min\_samples}Anchor of a cluster
Border∣Nε(p)∣<min_samples\lvert N_\varepsilon(p)\rvert < \text{min\_samples} but ∃\exists core cc with d(p,c)≤εd(p,c) \le \varepsilonFringe of a cluster
NoiseNot core, not reachable from any core pointOutlier, labeled −1-1

min_samples counts the point itself

A point is core when ∣Nε(p)∣≥min_samples\lvert N_\varepsilon(p)\rvert \ge \text{min\_samples} including itself. With min_samples=3, a core point needs 2 other neighbors within ε\varepsilon, not 3. This off-by-one is the most common DBSCAN mistake.

The steps of the clustering algorithm

  1. For each unvisited point pp: mark it visited; compute Nε(p)N_\varepsilon(p).
  2. If ∣Nε(p)∣<min_samples\lvert N_\varepsilon(p)\rvert < \text{min\_samples}: tentatively label pp as noise.
  3. Otherwise: start a new cluster CC; add all points in Nε(p)N_\varepsilon(p) to CC.
  4. For each newly added point qq that is itself core: expand CC by adding all of Nε(q)N_\varepsilon(q).
  5. Continue expanding until no more points can be added; then restart from step 1.
  6. Any point initially labeled noise that was added to a cluster during expansion becomes a border point.

Watch it run

Nine points, ε=2\varepsilon = 2, min_samples = 3. Each point's ε\varepsilon-neighbourhood is drawn as it is visited, so you can see the radius that decides core-versus-noise rather than just reading the count:

DBSCAN — core points, expansion, and the ε that merges everything

1/14

Nine points: two tight 4-point blobs and one isolated point I. With ε = 2 and min_samples = 3, DBSCAN never needs to be told how many clusters to find — density decides.

python
1def dbscan(X, eps, min_samples):
2 labels = [UNVISITED] * len(X)
3 c = 0
4 for p in range(len(X)):
5 if labels[p] != UNVISITED:
6 continue
7 N = neighbours(p, eps) # includes p
8 if len(N) < min_samples:
9 labels[p] = NOISE # may be revised
10 continue
11 labels[p] = c # new cluster
12 queue = list(N - {p})
13 while queue: # expand
14 q = queue.pop(0)
15 if labels[q] == NOISE:
16 labels[q] = c # -> border
17 if labels[q] != UNVISITED:
18 continue
19 labels[q] = c
20 Nq = neighbours(q, eps)
21 if len(Nq) >= min_samples:
22 queue += list(Nq) # q is core
23 c += 1
24 return labels
state
the dataset
010100ABCDEFGHI

Within a blob the largest distance is √2 ≈ 1.41 < ε. The nearest cross-blob distance is √18 ≈ 4.24 > ε. So ε = 2 sees the blobs but not the gaps.

The full visit/expand loop on nine points at ε = 2, min_samples = 3: each point's ε-neighbourhood is drawn as you visit it, core points open and grow clusters, and the isolated point is refused a cluster entirely. The final step re-runs the same code at ε = 5, where that outlier becomes core and chains the two blobs into one cluster — the chaining failure mode, shown rather than described.

What to notice as you step:

  • Expansion only continues through core points. Every point in a cluster gets labelled, but only core points put their neighbours back on the queue. A border point joins and the frontier stops there.
  • Noise is provisional. II is labelled noise the moment it is visited, but that label could still be overwritten if a later expansion reached it. Nothing does, so it stays −1-1.
  • The last step raises ε\varepsilon to 5 and changes nothing else. II gains enough neighbours to become core, and a core point is a bridge — the expansion walks straight through it and the two blobs merge into one cluster. That chaining effect, not a few stray points, is the real risk of an ε\varepsilon set slightly too high.

A 9-point worked example

Here ε=2\varepsilon = 2 and min_samples = 3.

Points in two tight blobs plus one isolated point:

  • Blob 1: A(1,1)A(1,1), B(1,2)B(1,2), C(2,1)C(2,1), D(2,2)D(2,2)
  • Blob 2: E(8,8)E(8,8), F(8,9)F(8,9), G(9,8)G(9,8), H(9,9)H(9,9)
  • Isolated: I(5,5)I(5,5)

Distance check within Blob 1: the largest within-blob distance is d(A,D)=(2−1)2+(2−1)2=2≈1.41<2d(A,D) = \sqrt{(2-1)^2+(2-1)^2} = \sqrt{2} \approx 1.41 < 2. So every pair in the blob is a neighbor. The nearest cross-blob distance is d(D,I)=(5−2)2+(5−2)2=18≈4.24>2d(D,I) = \sqrt{(5-2)^2+(5-2)^2} = \sqrt{18} \approx 4.24 > 2. Blob 2 is self-contained by symmetry.

NεN_\varepsilon table (including self):

PointNeighbors within ε=2\varepsilon=2∣Nε∣\lvert N_\varepsilon\rvertType
A(1,1)A(1,1)A,B,C,DA, B, C, D4 ≥ 3core
B(1,2)B(1,2)A,B,C,DA, B, C, D4 ≥ 3core
C(2,1)C(2,1)A,B,C,DA, B, C, D4 ≥ 3core
D(2,2)D(2,2)A,B,C,DA, B, C, D4 ≥ 3core
E(8,8)E(8,8)E,F,G,HE, F, G, H4 ≥ 3core
F(8,9)F(8,9)E,F,G,HE, F, G, H4 ≥ 3core
G(9,8)G(9,8)E,F,G,HE, F, G, H4 ≥ 3core
H(9,9)H(9,9)E,F,G,HE, F, G, H4 ≥ 3core
I(5,5)I(5,5)II only1 < 3noise

Cluster assignment:

  1. Visit AA: ∣Nε(A)∣=4≥3\lvert N_\varepsilon(A)\rvert = 4 \ge 3 → start Cluster 0; add BB, CC, DD. Each is also core but adds no new points → Cluster 0 = {A,B,C,D}\{A,B,C,D\}.
  2. Visit EE: start Cluster 1; expand to FF, GG, HH → Cluster 1 = {E,F,G,H}\{E,F,G,H\}.
  3. Visit II: ∣Nε(I)∣=1<3\lvert N_\varepsilon(I)\rvert = 1 < 3; no reachable core → noise (label −1-1).

Result: Cluster 0 = {A,B,C,D}\{A,B,C,D\}, Cluster 1 = {E,F,G,H}\{E,F,G,H\}, Noise = {I}\{I\}.

Python
import numpy as np
from sklearn.cluster import DBSCAN

X = np.array([[1,1],[1,2],[2,1],[2,2],[8,8],[8,9],[9,8],[9,9],[5,5]])
labels = DBSCAN(eps=2, min_samples=3).fit_predict(X)
print(f"Labels: {labels}")  # [0 0 0 0 1 1 1 1 -1]
print(f"Core point mask: {DBSCAN(eps=2, min_samples=3).fit(X).core_sample_indices_}")

Choosing ε with the k-distance elbow plot

Sort points by their distance to the kk-th nearest neighbor (where kk = min_samples − 1). The elbow (the point where distance starts increasing sharply) is a good estimate for ε\varepsilon:

Python
from sklearn.neighbors import NearestNeighbors
import matplotlib.pyplot as plt

k = 2  # min_samples - 1
nn = NearestNeighbors(n_neighbors=k + 1)  # +1 to exclude self
nn.fit(X)
distances, _ = nn.kneighbors(X)
k_dists = np.sort(distances[:, -1])       # distance to kth neighbor, sorted ascending

plt.figure(figsize=(7, 4))
plt.plot(k_dists, 'o-', color='#6366f1')
plt.axhline(2.0, color='#f59e0b', ls='--', label='ε=2 (elbow)')
plt.xlabel('Points (sorted)'); plt.ylabel(f'{k}-NN distance')
plt.title('k-Distance plot — choose ε at the elbow')
plt.legend(); plt.tight_layout(); plt.show()

Rule of thumb for min_samples: ≥ dimensionality + 1 (use ≥ 3 for 2-D); ≥ 2 × dimensions for large datasets. Larger values → fewer but more stable clusters.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

RelatedReferenced by
DBSCAN: Core, Border, Noise Class…Hierarchical Clustering L…K-Means: Full AlgorithmHierarchical Clustering &…