DBSCAN Clustering: Find Clusters of Any Shape

Contents

Figure 1: Dense shores, sparse water — clusters of any shape

From-scratch DBSCAN, eps sweeps, failure cases, and an honest HDBSCAN check

K-means draws circles. Give it two interleaved half-moons and it slices them in half with a straight line, then reports the result with total confidence.

DBSCAN works differently. It doesn't ask you for the number of clusters, it finds clusters of any shape, and it labels outliers as noise instead of forcing them into a group. That's three wins. It also has settings that can quietly wreck your results, and I'll show you exactly where. Below, we build DBSCAN from scratch, match it against scikit-learn, and stress-test it. Every number comes from a script run with scikit-learn 1.9.1.

How DBSCAN Works

DBSCAN stands for density-based spatial clustering of applications with noise. The idea: a cluster is a dense region separated from other dense regions by sparse space.

Two settings define "dense":

• eps: the radius of a point's neighborhood.
• min_samples: how many points (including itself) must sit within that radius.

Every point then falls into one of three roles:

• Core point: at least min_samples points within eps. The heart of a cluster.
• Border point: within eps of a core point, but not core itself. It joins the cluster's edge.
• Noise point: neither. DBSCAN labels it -1.

A cluster grows by chaining: start at a core point, absorb its neighbors, and keep expanding through any new core points.

DBSCAN From Scratch

Here's the whole algorithm:

import numpy as np

def dbscan(X, eps, min_samples):
    n = len(X)
    d = np.sqrt(((X[:, None, :] - X[None]) ** 2).sum(2))
    neighbors = [np.where(d[i] <= eps)[0] for i in range(n)]      # includes the point itself
    core = np.array([len(nb) >= min_samples for nb in neighbors])
    labels = np.full(n, -1)                                        # -1 = noise
    cluster = 0
    for i in range(n):
        if labels[i] != -1 or not core[i]:
            continue
        labels[i] = cluster                                        # new cluster at an unvisited core point
        queue = [i]
        while queue:
            j = queue.pop()
            if not core[j]:
                continue                                           # border points join but don't expand
            for nb in neighbors[j]:
                if labels[nb] == -1:
                    labels[nb] = cluster
                    queue.append(nb)
        cluster += 1
    return labels

It builds the full distance matrix, so it suits a few thousand points, not millions.

Checking Against Scikit-learn

from sklearn.cluster import DBSCAN

labels = DBSCAN(eps=0.2, min_samples=5).fit_predict(X)

I tested on two datasets. First, 500 points in two half-moons: both versions found 2 clusters and 0 noise, with an ARI of 1.0000 between them. But there's a catch. Every point was a core point, so there were no border points to disagree about. That's a weak test.

So I added a second: three blobs where eps=0.7 left 481 of 500 points as core. Both versions found 3 clusters and 8 noise points, with identical labels. Border handling matches too, on this data. FYI, the algorithm's border rule depends on processing order, so don't count on identical results everywhere.

Why Shape Matters: K-Means vs. DBSCAN

I scored both methods against the true labels, using ARI (1 is perfect, 0 is random). K-means got the true number of clusters, and DBSCAN got a hand-picked eps:

Shape	K-means	DBSCAN
Moons	0.2525	1.0000
Circles (one inside another)	-0.0020	1.0000
Blobs	1.0000	0.9758

On curved shapes, k-means failed outright, and DBSCAN was perfect. On plain round blobs, k-means won slightly, since DBSCAN flagged 8 points as noise. So DBSCAN isn't "better." It's different. Use it when clusters are oddly shaped or when noise is real — the k-means guide covers the other side of that trade.

The Hard Part: Choosing eps

DBSCAN's weak spot is eps. Here's what happened on the moons as I changed it (with min_samples=5):

eps	Clusters	Noise	ARI
0.05	31	215	0.0262
0.10	2	8	0.9682
0.15	2	1	0.9960
0.20	2	0	1.0000
0.30	2	0	1.0000
0.50	1	0	0.0000
0.80	1	0	0.0000

Too small, and the moons shatter into 31 pieces with 215 points labeled noise. Too large, and the two moons merge into one blob. There's a working window, about 0.15 to 0.3 here, and the cliffs on both sides are steep.

The k-Distance Curve

The standard trick is the k-distance plot. For each point, find the distance to its min_samples-th nearest neighbor, sort those distances, and look for the knee where they shoot up.

from sklearn.neighbors import NearestNeighbors

nn = NearestNeighbors(n_neighbors=5).fit(X)
kd = np.sort(nn.kneighbors(X)[0][:, -1])

On the moons, the 50th, 90th and 99th percentiles of this distance were 0.058, 0.092 and 0.136. I also estimated the knee automatically as the point farthest from the line joining the curve's ends, which gave eps ≈ 0.089.

Now the honest part. I ran DBSCAN at 0.089, and it did poorly: 4 clusters, 18 noise points, ARI 0.6710. The knee landed below the good window. So treat the k-distance curve as a starting range, not an answer. Sweep eps upward from the knee, as in the table above, and look for a plateau where the cluster count stops changing. In my experience the plateau is a far more reliable signal than the knee.

Choosing min_samples

With eps=0.2 fixed, here's what min_samples did:

min_samples	Clusters	Noise	ARI
3	2	0	1.0000
5	2	0	1.0000
10	2	0	1.0000
20	2	0	1.0000
40	0	500	0.0000

Anything from 3 to 20 worked. At 40, no neighborhood was dense enough, so every point became noise. A common rule of thumb is to start around twice the number of features, and go higher for noisy data. It's a guideline I didn't test here.

Gotcha: Feature Scale

DBSCAN uses distance, so it inherits the scaling problem — the same trap as k-NN. I stretched the moons' second axis by 100:

Setup	Clusters / noise	ARI
Stretched, eps = 0.2	0 / 500	0.0000
Stretched, eps = 20	1 / 0	0.0000
Standardized, eps = 0.3	2 / 0	1.0000

With raw stretched data, no single eps worked: 0.2 labeled everything noise, and 20 merged everything. After standardizing, it was perfect again. Scale your features first.

Gotcha: Varying Density

DBSCAN uses one eps for the whole dataset, so it struggles when clusters differ in density. I made one tight blob (spread 0.3) and one loose blob (spread 1.5), then swept eps:

eps	Clusters	Noise	Noise in loose blob	ARI
0.15	7	283	263	0.7646
0.30	12	119	117	0.6038
0.50	2	47	47	0.8676
1.00	3	5	5	0.9706

A small eps shreds the loose blob into fragments and noise. A bigger one rescues it. Here eps = 1.0 worked well, but only because my two blobs sit far apart, which is generous. If the dense blob had a close neighbor, the trade-off would bite harder.

HDBSCAN, which scikit-learn includes, handles varying density and needs no eps. On the same data (min_cluster_size=20), it found 2 clusters and 25 noise points, with an ARI of 0.9171. That's lower than the hand-tuned DBSCAN above. So HDBSCAN isn't an automatic upgrade. Its real benefit is that you don't have to tune eps, which matters when you can't see your data.

DBSCAN as an Outlier Detector

Noise labeling is a free outlier detector. I scattered 40 uniform random points around the moons and ran DBSCAN again:

• Injected outliers labeled noise: 24 of 40.
• Real points labeled noise: 0 of 500.

It never flagged a genuine point. But 16 outliers landed close enough to the moons to be absorbed into clusters. Noise means "in a sparse region," not "wrong."

A Practical Workflow

1. Scale your features.
2. Plot the k-distance curve to get a starting eps.
3. Sweep eps and look for a stable plateau in cluster count.
4. Inspect the noise. Is it outliers or just a bad eps?
5. Try HDBSCAN if densities vary or you can't tune eps.
6. Switch to k-means if clusters are round. It's simpler and faster.

Common Pitfalls

• Running DBSCAN on unscaled features and letting the widest feature decide every neighborhood.
• Trusting the k-distance knee as the final eps — it landed outside the good window here.
• Tuning eps on a single dataset split without checking whether the cluster count is stable.
• Setting min_samples too high and turning the whole dataset into noise.
• Expecting one eps to serve clusters of very different densities.
• Reading noise labels as "errors" — they only mean sparse region.
• Building the full distance matrix on large data, which blows up memory.
• Assuming HDBSCAN will beat a well-tuned DBSCAN without measuring.

Unlock AI That Actually Works

Get lifetime access to GPT-6 Astra, Claude Fable 5.1, Gemini 3.5, Grok 4.5, and more — all in one platform. Build websites, apps, videos, content, and digital products from a single command. No monthly fees. No tool-hopping.

Click here to get GPTAstra Max now — one-time payment, lifetime access.

Frequently Asked Questions

How do I choose eps for DBSCAN?

Start from the k-distance curve — the sorted distance to each point's min_samples-th nearest neighbor — and take the knee where distances shoot up, but treat it as a range, not an answer. In the experiments here the automatic knee gave eps ≈ 0.089, which produced 4 clusters and ARI 0.6710, well below the good window of 0.15 to 0.30. Sweep eps upward from the knee and look for a plateau where the cluster count stops changing; that plateau is a far more reliable signal than the knee itself.

What do core, border, and noise points mean?

A core point has at least min_samples points (including itself) within eps — it anchors a cluster. A border point sits within eps of a core point but doesn't meet the density threshold itself, so it joins a cluster's edge without expanding it. Anything else is noise, labeled -1. Because the border rule depends on processing order, two implementations can disagree on border assignment even when they agree on the core structure.

Why does DBSCAN fail after I stretch my features?

Because DBSCAN measures distance, so it inherits the scaling problem directly. Stretching the moons' second axis by 100 broke every setting: eps=0.2 labeled all 500 points as noise (0 clusters, ARI 0.0000) and eps=20 merged everything into one cluster (ARI 0.0000). After standardizing the features, eps=0.3 recovered both moons perfectly (ARI 1.0000). Always scale before DBSCAN, the same way you would before k-NN or k-means.

Should I use HDBSCAN instead of DBSCAN?

It depends on whether you can tune eps. HDBSCAN handles varying density and removes the eps setting entirely, which matters most when you can't visualize your data. But it isn't an automatic upgrade in quality: on the two-density test data, hand-tuned DBSCAN reached ARI 0.9706 while HDBSCAN scored 0.9171 with 25 noise points. Use HDBSCAN for convenience and robustness, and verify with ARI or inspection when you have ground truth.

Wrapping This Up

DBSCAN finds clusters of any shape, handles noise, and skips the "how many clusters" question. In exchange, it gives you eps and min_samples to tune, a single density setting for the whole dataset, and sensitivity to scale. The k-distance curve gives you a place to start. A sweep tells you where to land.

Next step: grab the script, load your own data, and sweep eps. Watching a clustering fall apart and re-form teaches more than reading about it.

Related Articles

• K-Means Clustering Tutorial: Choosing K and Evaluating Clusters
• K-Nearest Neighbors Tutorial: Simple Classification in Python
• Machine Learning Algorithms Explained: Complete Beginner's Guide
• Naive Bayes Classifier: Text and Tabular Examples in Python