Concept30 minBefore this:k-Means Clustering

DBSCAN

How do you find curved clusters and flag the points that belong nowhere?

The situation

Your deliveries follow curved roads, and stray GPS pings land everywhere. k-means cuts straight across both roads. The interviewer asks:

How does DBSCAN find clusters, and what is its main weakness?

Running example: the same food-delivery app, now looking at where orders are delivered. Simulated GPS points (standardised): 200 deliveries along two curved roads that wrap around each other (the "two moons" shape), plus 20 stray pings scattered at random (GPS errors). A second map has a dense city-centre cluster beside a sparse suburb. We want the roads found as two clusters and the stray pings flagged.

Clusters that aren't round, and points that belong nowhere

Deliveries follow roads, so the clusters are long and curved, and a k-means centroid in the middle of a curve sits where nobody lives. k-means on the two roads scores ARI 0.21: it cuts straight across both (see the k-means lesson). It also forces every GPS error into some cluster. We need a method that follows dense regions wherever they go and is allowed to say "this point is noise".

The idea

Think of finding crowds at a fair. Wherever people stand packed together, you can walk from person to person and stay in the same crowd. Someone standing alone belongs to no crowd at all.

Illustrative, based on the lesson's two roads and stray GPS pings.

Play

Try to break it. Try eps at 0.25, 0.30 and 0.35. Watch how many clusters it finds and how many points become noise.

The two settings

eps is everything

eps min_samples

clusters found (true: 2 roads)

–

noise points

–

road deliveries matched (ARI)

–

Big dots: core points. Small dots: border points. Grey: noise. The circle (top left) shows eps to scale.

With min_samples = 10: eps = 0.30 finds both roads exactly (ARI 1.0) and flags 4 stray pings as noise; the other 16 strays lie close enough to a road to be absorbed as border points. eps = 0.25 breaks a road into pieces (3 clusters); eps = 0.35 merges both roads into one. A 20% change in eps flips the answer. scikit-learn: eps "is crucial to choose appropriately for the data set and distance function and usually cannot be left at the default value" clustering guide.

Now say why: why does such a small change in eps swing the result from fragments, to two roads, to one blob?

Maths

In one breath

DBSCAN says a cluster is a region where points are packed densely, separated from other clusters by sparse space. A point with at least min_samples neighbours within radius eps is a core point; core points within eps of each other join the same cluster, points near a core point join it as border points, and everything else is noise. So it finds clusters of any shape, figures out how many there are, and flags outliers, none of which k-means can do. Its weakness is one global density: eps is hard to set, and when clusters have different densities, no single eps works. HDBSCAN fixes that by trying all densities and keeping the most stable clusters.What you'll be able to do after this: classify points as core/border/noise by hand, pick eps with a k-distance plot, explain why DBSCAN finds curved clusters, and say when to switch to HDBSCAN.

cluster 1cluster 2cluster 3+noiseeps radius / numbersfailure

Core, border and noise

Swipe sideways to see the whole diagram.

Eight delivery points. Two settings: eps (a radius) and min_samples (how many points must be inside that radius).
Draw a circle of radius eps around a point. It contains 5 points including itself, at least min_samples = 4, so it's a core point: it's inside a dense region.
Check every point the same way: four more have at least 4 points within eps, so they are cores too. Core points within eps of each other are linked, and everything linked forms one cluster, whatever its shape.
These two points have too few neighbours to be cores (3 and 2 inside their circles), but each lies within eps of a core point, so they join the cluster as border points. Border points belong to a cluster but can't extend it.
The lone point has no core within eps. It's noise (label −1 in scikit-learn): DBSCAN refuses to force it into a cluster.

Definitions from scikit-learn: a core sample has "min_samples other samples within a distance of eps"; "Any sample that is not a core sample, and is at least eps in distance from any core sample, is considered an outlier by the algorithm" clustering guide. (scikit-learn's min_samples counts the point itself.) Original algorithm: Ester, Kriegel, Sander & Xu, KDD 1996.

One principle

A cluster is a connected dense region

A cluster is a maximal set of points that are density-connected through core points. The number of clusters comes out of the data; nobody sets k. The algorithm is a flood fill: pick an unvisited core point, start a cluster, and keep adding the neighbours of every core point you reach.

Choosing eps

The k-distance plot

For every point, compute the distance to its k-th nearest neighbour (k = min_samples − 1, so the circle around it holds min_samples points), sort those distances and plot them. Points inside clusters have small k-distances; noise points have large ones. The curve is flat, then bends sharply upward: eps near the bend separates "dense enough" from "noise". This heuristic is from the original DBSCAN paper.

k (min_samples − 1)

Sorted distance from each of the 220 points to its k-th nearest neighbour. The dashed line marks eps = 0.30, the value that worked above.

For k = 9 the curve is nearly flat up to about the 85th percentile (0.25), then climbs: 0.30 at the 90th, 0.36 at the 95th, 0.48 at the 99th. The bend sits close to the eps that separated the roads. It's a guide, not a guarantee: with clusters of different densities there is no single bend.

In practice

The density-based family

Method	Idea	Settings
DBSCAN (1996)	One density threshold; core/border/noise	eps, min_samples
OPTICS (1999)	Orders points by reachability; extract clusters at many eps	min_samples (max eps)
HDBSCAN (2013)	Hierarchy over all densities; keeps the most stable clusters	min_cluster_size, min_samples

All three are in scikit-learn (DBSCAN, OPTICS, HDBSCAN) clustering guide. Typical uses: geospatial data (pickup hotspots, store locations), anomaly detection (noise points are the anomalies), and clustering embeddings after UMAP (see t-SNE & UMAP).

Practicalities

Speed, scaling and determinism

Cost: one neighbourhood query per point. With a KD-tree or ball tree in low dimensions that's roughly O(n log n); otherwise O(n²). scikit-learn's implementation can build a full pairwise matrix that "will consume n² floats" when trees can't be used clustering guide.
Scale features: eps is one radius in every direction, so unscaled features make it meaningless. For GPS, use haversine distance in metres.
High dimensions: distances concentrate (see k-NN), so density is hard to define; reduce dimensions first.
Order: core points and noise are deterministic, but a border point within eps of two clusters goes to whichever reaches it first, so "results can differ when data is provided in a different order" clustering guide.

The whole recipe

Scale features or choose a meaningful distance (haversine for GPS, cosine for embeddings).
Set min_samples from domain sense (a common rule of thumb: about 2 × dimensions, at least 4 or 5); larger means fewer, denser clusters and more noise.
Pick eps at the bend of the k-distance plot; try a few values around it.
Inspect noise: is it really noise, or a sparse cluster? If densities differ, switch to HDBSCAN.

When to use it

Use DBSCAN / HDBSCAN when

Clusters have odd shapes (geography, trajectories)
You expect noise and want outliers flagged
You don't know how many clusters there are
HDBSCAN: densities vary

Reach for something else when

Clusters are round and k is known: k-means is simpler and faster
You need soft membership: GMM
Very high-dimensional raw features: reduce first

The answer that sounds right

The trap

"Link every pair of points closer than some distance"

Linking any two points within distance eps (single linkage cut at eps) follows curves too. But one chain of stray GPS pings between the two roads links them into one cluster, and isolated pings become their own tiny "clusters". DBSCAN's fix is the min_samples rule: only core points can extend a cluster, and a stray ping in a sparse area isn't a core, so it can't act as a bridge. Density, not just distance, decides what's connected.

One density for all

A dense centre and a sparse suburb

eps

clusters

–

suburb points called noise (of 60)

–

suburb points merged into the centre

–

120 deliveries packed in the city centre, 60 spread across a suburb next to it. min_samples = 5.

eps = 0.15 finds the centre but throws away 54 of the 60 suburb deliveries as noise. eps = 0.4 keeps the suburb but merges it with the centre into one cluster. The compromise, eps = 0.3, keeps them apart but hands 11 suburb deliveries to the centre and drops 7 as noise. scikit-learn: "DBSCAN assumes that the clustering criterion (i.e. density requirement) is globally homogeneous" and "may struggle to successfully capture clusters with different densities" clustering guide.

Go deeper: how HDBSCAN removes eps

HDBSCAN (Campello, Moulavi & Sander, PAKDD 2013) "explores all possible density scales": it replaces raw distance with a mutual reachability distance (the larger of the two points' core distances and their actual distance, which pushes sparse points apart), builds a single-linkage tree on it (via a minimum spanning tree), and condenses the tree, dropping splits smaller than min_cluster_size. It then keeps the clusters that persist longest as density changes (their stability). Each cluster effectively gets its own eps. scikit-learn: it "relies solely on the choice of min_samples, which tends to be a more robust hyperparameter" clustering guide. In practice it's the better default; use plain DBSCAN when you know the density scale (e.g. "a hotspot is ≥ 10 orders within 200 m").

Caveats

Strengths

Any cluster shape
No k: the number of clusters comes from the data
Built-in outlier detection (noise label)
Few parameters with physical meaning (a radius and a count)

Weaknesses

Very sensitive to eps
One global density: fails on clusters of different densities
Struggles in high dimensions
Border points between clusters are assigned arbitrarily

Say it

How does DBSCAN find clusters, and what is its main weakness?

Say your answer out loud

Aim for 30 seconds. It feels different from reading it, and that's the point.

Tick what you covered

A core point has at least min_samples neighbours within radius eps.
Clusters are core points reachable through eps-hops, plus nearby border points.
Everything else is noise.
It finds any shape, infers the number of clusters and flags outliers.
Results are very sensitive to eps, which you pick from a k-distance plot.
One global density fails when densities vary, and HDBSCAN fixes that.