DBSCAN: Core, Border, Noise Classification
DBSCAN (Density-Based Spatial Clustering of Applications with Noise) finds clusters as dense connected regions without requiring 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 .
The two parameters
- (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 , let be its -neighborhood, which includes itself.
| Type | Condition | Role |
|---|---|---|
| Core | Anchor of a cluster | |
| Border | but core with | Fringe of a cluster |
| Noise | Not core, not reachable from any core point | Outlier, labeled |
min_samples counts the point itself
A point is core when including itself. With min_samples=3, a core point needs 2 other neighbors within , not 3. This off-by-one is the most common DBSCAN mistake.
The steps of the clustering algorithm
- For each unvisited point : mark it visited; compute .
- If : tentatively label as noise.
- Otherwise: start a new cluster ; add all points in to .
- For each newly added point that is itself core: expand by adding all of .
- Continue expanding until no more points can be added; then restart from step 1.
- Any point initially labeled noise that was added to a cluster during expansion becomes a border point.
Watch it run
Nine points, , min_samples = 3. Each point's -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
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.
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. 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 .
- The last step raises to 5 and changes nothing else. 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 set slightly too high.
A 9-point worked example
Here and min_samples = 3.
Points in two tight blobs plus one isolated point:
- Blob 1: , , ,
- Blob 2: , , ,
- Isolated:
Distance check within Blob 1: the largest within-blob distance is . So every pair in the blob is a neighbor. The nearest cross-blob distance is . Blob 2 is self-contained by symmetry.
table (including self):
| Point | Neighbors within | Type | |
|---|---|---|---|
| 4 ≥ 3 | core | ||
| 4 ≥ 3 | core | ||
| 4 ≥ 3 | core | ||
| 4 ≥ 3 | core | ||
| 4 ≥ 3 | core | ||
| 4 ≥ 3 | core | ||
| 4 ≥ 3 | core | ||
| 4 ≥ 3 | core | ||
| only | 1 < 3 | noise |
Cluster assignment:
- Visit : → start Cluster 0; add , , . Each is also core but adds no new points → Cluster 0 = .
- Visit : start Cluster 1; expand to , , → Cluster 1 = .
- Visit : ; no reachable core → noise (label ).
Result: Cluster 0 = , Cluster 1 = , Noise = .
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 -th nearest neighbor (where = min_samples − 1). The elbow (the point where distance starts increasing sharply) is a good estimate for :
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
- Hierarchical Clustering & DBSCAN: the full lesson with parameter tuning and comparison with K-Means
- Hierarchical Clustering Linkage Methods: the agglomerative alternative that also avoids pre-specifying
- K-Means: Full Algorithm: the centroid-based alternative