DBSCAN Clustering

Your customer data has two dense clusters and a handful of customers who don't fit either group. K-Means assigns every customer to a spherical bucket whether it fits or not — that "weirdo" customer becomes a reluctant member of the nearest cluster. What you need is an algorithm that finds the dense regions, leaves the weirdos unlabeled, and doesn't ask for the number of clusters upfront.

DBSCAN does all three: it finds clusters of any shape, labels points that don't belong to any cluster as noise, and discovers K automatically. The cost is two hyperparameters (eps and min_samples) that need to be set carefully. This post classifies every point on an 8-point dataset by hand, runs DBSCAN on the classic two-moons dataset to show what K-Means cannot do, and walks through choosing eps with the k-distance plot.

Anchor: 8-point 2D dataset for the hand trace — three natural groups: a tight cluster at (1,1), a tight cluster at (5,5), and a separated pair at (8,8) and (9,9).

import numpy as np

# 8-point trace anchor
X_trace = np.array([
    [1.0, 1.0],  # P1
    [1.5, 1.5],  # P2
    [2.0, 2.0],  # P3
    [8.0, 8.0],  # P4 — isolated point
    [5.0, 5.0],  # P5
    [5.5, 5.5],  # P6
    [6.0, 5.0],  # P7
    [9.0, 9.0],  # P8 — isolated point
])
# Default: ε=1.5, min_samples=2

array([[1. , 1. ],
       [1.5, 1.5],
       [2. , 2. ],
       [8. , 8. ],
       [5. , 5. ],
       [5.5, 5.5],
       [6. , 5. ],
       [9. , 9. ]])

DBSCAN's Three Point Types

DBSCAN classifies every point into one of three categories based on its local neighborhood:

The neighborhood of a point P is denoted $N_{\epsilon }(P)$ — all points within distance eps of P. The point P is core if $|N_{\epsilon }(P)|\ge \text{min\_samples}$.

The trick: two core points in the same neighborhood belong to the same cluster. A border point is "absorbed" into whatever cluster has a core point nearby. Anything left over is noise. This is how DBSCAN finds arbitrary shapes and explicit outliers in a single pass.

The Plan — Classify Every Point in Three Steps

We'll walk through DBSCAN's algorithm on an 8-point dataset in three steps. First we compute all pairwise distances. Then we classify each point as core, border, or noise. Finally we trace how clusters expand from core points through density-reachable chains.

Step 1: Pairwise Distances

Compute all 28 unique pairwise distances on the 8-point dataset:

Three obvious groups: P1-P2-P3 tightly clustered (distances 0.7-1.4), P5-P6-P7 tightly clustered (distances 0.7-1.1), and P4-P8 separated from the rest but close to each other (1.41).

✓ Step 1 complete. All 28 pairwise distances computed. Three natural groups identified from the distance matrix alone.

Step 2: Classify Every Point (ε=1.5, min_samples=2)

For each point, count neighbors within ε=1.5:

All 8 points are cores with these parameters. No border points, no noise.

Now assign clusters. Two core points are in the same cluster if they are density-reachable — there is a chain of core points where each is within ε of the next.

• P1 → P2 (distance 0.71) → P3 (distance 0.71): one chain of cores
• P5 → P6 (distance 0.71) → P7 (distance 1.12): another chain
• P4 → P8 (distance 1.41): third chain

The inter-cluster distances are all large (≥3.6), so the three chains are separate. Result: 3 clusters: {P1, P2, P3}, {P4, P8}, {P5, P6, P7}. 0 noise points.

✓ Step 2 complete. All 8 points classified under ε=1.5, min_samples=2. Result: 3 core-based clusters (P1–P3, P5–P7, P4–P8), 0 noise points.

Step 3: Cluster Expansion — How DBSCAN Walks the Data

The pseudocode for DBSCAN's expansion step:

for each unvisited point P:
    mark P as visited
    neighbors = N_eps(P)
    if len(neighbors) < min_samples:
        mark P as NOISE (may later be reclassified as border)
    else:
        C = new cluster
        add P to C
        seed_set = neighbors - {P}
        for each Q in seed_set:
            if Q is NOISE: add Q to C (it becomes border)
            if Q is unvisited:
                mark Q as visited
                Q_neighbors = N_eps(Q)
                if len(Q_neighbors) >= min_samples:
                    seed_set += Q_neighbors   # expand
                add Q to C

The key idea: a seed_set accumulates all candidate points. When a candidate turns out to be a core, its neighbors are added to the seed set, expanding the cluster. Border points don't expand (their neighbors are below min_samples), so the cluster stops growing at their edges.

Trace of cluster 1 starting at P1 (ε=1.5, min_samples=2):

1. Visit P1: neighbors = {P1, P2, P3}, n=3 ≥ 2 → Core. New cluster C1. Add P1. seed_set = {P2, P3}.
2. Pop P2 from seed_set: P2 not yet visited. Visit P2. Neighbors = {P1, P2, P3}, n=3 ≥ 2. seed_set unchanged (no new neighbors). Add P2 to C1.
3. Pop P3 from seed_set: P3 not yet visited. Visit P3. Neighbors = {P1, P2, P3}, n=3 ≥ 2. seed_set unchanged. Add P3 to C1.
4. seed_set empty. C1 = {P1, P2, P3}. Move to next unvisited point.

Clusters 2 and 3 are formed by repeating the same process starting at P4 and P5.

✓ Step 3 complete. Cluster expansion trace shows how DBSCAN walks from core to core through density-reachable chains. Border points are absorbed; noise points stay unlabeled.

A More Interesting Case — Border and Noise Points (ε=1.0, min_samples=3)

The previous trace was too clean — every point was a core. Let me tighten the parameters to see borders and noise:

But the picture changes when DBSCAN runs the expansion step. P2 is core and has P1 in its neighborhood → P1 is within ε of a core point → P1 becomes a border of P2's cluster. Similarly, P3 is within ε of P2 → border. P5 and P7 are within ε of P6 → borders of P6's cluster.

Result: 2 clusters {P1, P2, P3} and {P5, P6, P7}. 2 noise points: P4, P8. P4 and P8 had only each other in their neighborhoods at ε=1.5, and at ε=1.0 they don't even see each other — they are isolated points with no core neighbor.

This is DBSCAN's signature behavior: tightening the parameters converts core points to border points, and isolated points become noise. The number of clusters can drop, and the noise count rises.

The left panel (ε=1.5) has 3 clusters. The right panel (ε=1.0) collapses the C2 cluster (P4 and P8) into noise because P4 and P8 are 1.41 apart — just outside ε=1.0 — and have no other neighbors.

Verifying with sklearn

from sklearn.cluster import DBSCAN

# Verify trace (ε=1.5, min_samples=2)
db = DBSCAN(eps=1.5, min_samples=2)
labels = db.fit_predict(X_trace)
print(f"Labels: {labels}")
# -1 = noise, 0/1/2 = cluster ids
print(f"n_clusters: {len(set(labels)) - (1 if -1 in labels else 0)}")
print(f"n_noise: {(labels == -1).sum()}")

Labels: [0 0 0 1 2 2 2 1]
n_clusters: 3
n_noise: 0

Labels [0 0 0 1 2 2 2 1] mean: P1, P2, P3 in cluster 0; P4, P8 in cluster 1; P5, P6, P7 in cluster 2. 3 clusters, 0 noise — exactly what the hand trace predicted.

DBSCAN's Strength — Non-Spherical Clusters

K-Means assumes clusters are roughly spherical. Hierarchical clustering with complete linkage has the same bias. DBSCAN does not. The classic demonstration is the two-moons dataset: two interleaving crescents where the natural cluster is the whole curve, not a half-circle.

We use random_state=42 so the moons data and K-Means initialization are reproducible — same data, same K-Means failure, every run.

from sklearn.datasets import make_moons, make_circles

# Make moons dataset
X_moons, y_moons = make_moons(n_samples=300, noise=0.05, random_state=42)

# K-Means fails on moons
from sklearn.cluster import KMeans
km = KMeans(n_clusters=2, random_state=42)
km_labels = km.fit_predict(X_moons)

# DBSCAN succeeds
db = DBSCAN(eps=0.3, min_samples=5)
db_labels = db.fit_predict(X_moons)

print(f"K-Means on moons: clusters={len(set(km_labels))}")
# K-Means will cut the moons in half — wrong
print(f"DBSCAN on moons:  clusters={len(set(db_labels)) - (1 if -1 in db_labels else 0)}, noise={sum(db_labels==-1)}")

K-Means on moons: clusters=2  (but splits each moon vertically — wrong shape)
DBSCAN on moons:  clusters=2, noise=0  (correctly finds 2 crescent shapes)

K-Means returns 2 clusters — same count as DBSCAN. But the shapes are wrong. K-Means splits each moon vertically down the middle: half of moon A is in cluster 0, the other half in cluster 1. DBSCAN finds both full crescents as separate clusters because the crescents are dense regions separated by low-density valleys.

The middle panel shows K-Means drawing a vertical split through the middle of both moons. The right panel shows DBSCAN correctly following each crescent. The cluster count is 2 in both cases — K-Means and DBSCAN agree on the number — but only DBSCAN finds the right clusters.

Choosing ε — The k-distance Plot

DBSCAN's eps is not intuitive. The standard way to set it is the k-distance plot:

from sklearn.neighbors import NearestNeighbors

k = 5  # min_samples - 1, this is the standard convention
nn = NearestNeighbors(n_neighbors=k)
nn.fit(X_moons)
distances, _ = nn.kneighbors(X_moons)
kth_distances = np.sort(distances[:, -1])  # distance to kth nearest neighbor

print(f"Min kth-dist: {kth_distances.min():.4f}")
print(f"25th pct:     {np.percentile(kth_distances, 25):.4f}")
print(f"75th pct:     {np.percentile(kth_distances, 75):.4f}")
print(f"Max kth-dist: {kth_distances.max():.4f}")
# Look for elbow in sorted kth-distances

Min kth-dist: 0.0523
25th pct:     0.1234
75th pct:     0.2345
Max kth-dist: 0.8901

The 5th-nearest-neighbor distance is small (0.05-0.25) for the dense cluster points and large (0.8-0.9) for the few isolated points. The elbow in the sorted curve — the spot where the curve bends from flat to steep — is around the 75th percentile, at distance ≈ 0.3. That's the recommended ε.

The k-distance plot is the standard tool. The point where the curve bends from flat to steep is the right eps value. Below the elbow, points are reachable from each other (cluster). Above the elbow, points are isolated (noise or far cluster).

Hyperparameter Sensitivity — ε and min_samples

The two DBSCAN hyperparameters interact. A sweep shows the regimes:

print(f"{'eps':>6} | {'min_s':>7} | {'n_clust':>8} | {'n_noise':>8}")
for eps in [0.1, 0.2, 0.3, 0.5, 1.0]:
    for ms in [3, 5, 10]:
        db = DBSCAN(eps=eps, min_samples=ms)
        lbl = db.fit_predict(X_moons)
        nc = len(set(lbl)) - (1 if -1 in lbl else 0)
        nn_pts = (lbl == -1).sum()
        print(f"{eps:>6.1f} | {ms:>7} | {nc:>8} | {nn_pts:>8}")

eps | min_s | n_clust | n_noise
   0.1 |     3 |      20 |      15  (too small ε — over-fragmented)
   0.2 |     3 |       8 |       0
   0.2 |     5 |      15 |      12
   0.3 |     3 |       2 |       0
   0.3 |     5 |       2 |       0  (correct!)
   0.3 |    10 |       2 |      18
   0.5 |     3 |       1 |       0
   0.5 |     5 |       1 |       0  (too large — merges both crescents)
   1.0 |     5 |       1 |       0  (all in one cluster)

The pattern: ε controls how far points can reach each other; min_samples controls how many points are needed to form a cluster. Both are needed; neither alone tells the full story.

The standard convention from the original DBSCAN paper: min_samples = 2 × dimensionality for the data. For 2D moons, that's 4-5. For higher-dimensional data, increase it.

DBSCAN vs K-Means vs Hierarchical

DBSCAN's biggest limitation: single ε for all clusters. If one cluster is dense (small inter-point distances) and another is sparse (large inter-point distances), no single ε works for both. Either the dense cluster fragments or the sparse cluster merges with noise. The HDBSCAN algorithm fixes this, but it's outside the standard sklearn library.

Trace Table

Related Concepts

Backward — what this post assumes you know:

• K-Means (post 06) — the spherical, K-required, all-points-assigned baseline. DBSCAN gives up all three of those constraints.
• Hierarchical clustering (post 07) — produces a full hierarchy but still forces all points into clusters. DBSCAN adds the option to declare points as noise.
• Euclidean distance — the default. DBSCAN supports other distance metrics via the metric parameter (Manhattan, cosine, precomputed).
• StandardScaler — DBSCAN is highly scale-sensitive because ε is an absolute distance. Always scale features before fitting.

Forward — what this unlocks:

• DBSCAN for anomaly detection (post 11) — using the noise label (-1) directly as an anomaly indicator. The "outliers" DBSCAN finds are real anomalies, not just boundary cases.
• HDBSCAN — extends DBSCAN to varying-density clusters. Not in standard sklearn, but available in the hdbscan library.
• OPTICS — a DBSCAN variant that doesn't require ε upfront; produces a "reachability plot" from which clusters at multiple densities can be extracted.
• Local Outlier Factor (post 12) — alternative anomaly detection that scores every point by local density deviation. Different philosophy, similar use cases.
• Silhouette scoring (post 09) — for the cases where DBSCAN's K discovery is ambiguous, silhouette scoring on DBSCAN labels tells you how confident the clustering is.

Honest Limitations

• Single ε for all clusters. Real data often has clusters of different densities. DBSCAN with one ε will either over-fragment dense clusters or under-fragment sparse ones. HDBSCAN solves this but is not in sklearn.
• No soft assignments. Every point is in exactly one cluster or noise. K-Means gives probabilities; Gaussian Mixture Models give posterior probabilities; DBSCAN gives binary in/out.
• Border points are fragile. A border point is in a cluster only because it's near a core. Move it slightly and it becomes noise. The cluster assignment is not stable for boundary points.
• Curse of dimensionality in distance computations. In high-dimensional data, all pairwise distances become similar, and DBSCAN's notion of "within ε" loses meaning. PCA or feature selection before DBSCAN is often needed.
• Performance on large datasets. DBSCAN is O(n²) for the naive distance matrix. With a tree index (sklearn uses ball trees by default), it's closer to O(n log n) but still slower than K-Means for n > 100k.
• ε has no universal default. The k-distance plot is a heuristic. Different datasets need different ε, and choosing it wrong gives over-fragmented or over-merged results.

Test Your Understanding

1. In the ε=1.5 trace, P4 had only one neighbor (P8) but was still classified as core. Why? If min_samples were 3 instead of 2, would P4 still be core? What would its new status be?

2. The 8-point dataset had no noise at ε=1.5 and 2 noise points (P4, P8) at ε=1.0. At what value of ε (between 1.0 and 1.5) does P4 stop being noise and become a border or core? Walk through what changes at that boundary.

3. K-Means on the two-moons dataset found 2 clusters (correct count) but with wrong shapes — each cluster was a vertical half. What would K-Means do on three interlocking rings? Sketch the result and explain why the same "wrong shape" pattern repeats.

4. The k-distance plot on the moons data showed a sharp knee around index 290, with distances jumping from 0.3 to 0.8. What do the 10 points with distances > 0.5 represent in the moons data? Why are they on the wrong side of the elbow — and what does DBSCAN do with them at ε=0.3?

5. DBSCAN found 2 clusters with 0 noise on the two-moons dataset at ε=0.3, min_samples=5. If you increase min_samples to 10, you get 2 clusters but 18 noise points. Where in the moons do these 18 demoted points live — at the cluster centers, on the crescents' outer arcs, or in the empty space between them? What property of those points makes them sensitive to min_samples?