DBSCAN

A point with enough neighbours close by anchors a cluster, and clusters spread through those anchors, so shape is free and leftover points are called noise.

Four points inside radius 1.5 form one cluster while a border point hangs on and a far point stays noise

Why Does This Exist?

Bikes pile up along a riverside path, thin in one stretch and bunched at the landing. You want the piles, not one average point sitting in the river.

K-means gives you averages. It picks k centres and pulls every row to the nearest one, so a long curve gets chopped across its middle because the mean of a curve sits off the curve. You also have to state k up front, and every stray point still lands in some cluster and drags its centre along.

DBSCAN starts from packing instead. One phrase first: density here means how many other rows sit within a short walk of a given row, measured with straight-line distance (the usual choices). When enough rows pack together they chain into a group of any shape, and rows that belong to nothing get a label that says so.

This page builds that rule, counts one small six-point example by hand, and names where a single radius breaks. K-means is the centroid contrast you will compare against, hierarchical clustering is the other way to dodge k, and clustering evaluation is how you judge the grouping once you have one.

Think of It Like This

The festival rumour

You are in a crowd of thousands at a street festival. You can whisper only to someone within arm's reach, and you pass a rumour on only when six people stand within your reach. Fewer than that and you do not feel sure enough to repeat it.

Start the rumour in the crush by the stage. Everyone there has twenty people in reach, so it races. It also walks the food queue one arm's length at a time, so a line a hundred metres long and two wide hears it end to end. Whatever shape the crowd makes, the rumour fills it.

At the thin edge someone hears it with three people nearby. They know it but never repeat it, so the spread stops there. A couple on a blanket forty metres out never hears it at all.

The reach is the radius, the six is the minimum count, the spreaders are core points, the hear-only edge is border, and the couple outside it all is noise.

Where it stops: the festival uses one arm's length everywhere, so one setting cannot fit a crush and a picnic field at once. When densities differ that much the single reach either strands the loose group or fuses the tight one, and you need a method that lets the reach vary.

How It Actually Works

DBSCAN needs two settings you choose. The radius, written $\varepsilon$ and read epsilon, is how far you look around each point. The count, written $\text{minPts}$ and called minimum points, is how many points must sit inside that look to call it crowded. The count includes the point itself.

Core, border, and noise

For a point $p$ , write $N_{\varepsilon}(p)$ for its neighbourhood, meaning every point $q$ with straight-line distance $d(p, q) \le \varepsilon$ . Here $d$ is Euclidean distance and $\le$ means inside or on the edge.

A point is core when $|N_{\varepsilon}(p)| \ge \text{minPts}$ , meaning its neighbourhood holds at least that many points. The bars mean size of the set.
Two core points within $\varepsilon$ of each other join, and that joining chains. If A joins B and B joins C, then A and C land in one cluster even when A and C sit far apart. A cluster is a maximal chain of joined cores plus their attached edge points.
A point is border when it sits inside some core point's neighbourhood yet holds fewer than $\text{minPts}$ itself. It joins that cluster but cannot extend it.
A point is noise when it is neither core nor inside any core neighbourhood. It belongs to nothing, which centroid methods never say.

No cluster count appears anywhere. The number of groups falls out of the chaining.

Worked example: six points with radius 1.5

Take $\varepsilon = 1.5$ and $\text{minPts} = 4$ , and six points you can check by hand:

$A = (0.0, 0.0)$
$B = (1.0, 0.0)$
$C = (0.0, 1.0)$
$D = (1.0, 1.0)$
$E = (2.0, 0.5)$
$F = (5.0, 0.0)$

Straight-line distance is $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$ , the hypotenuse of the x and y gaps. The diagram draws these same six dots with one radius circle around $B$ .

Count from $B$ . It sits $1.0$ from $A$ , $1.0$ from $D$ , $1.41$ from $C$ because $\sqrt{1^2 + 1^2} = \sqrt{2} \approx 1.41$ , and $1.12$ from $E$ because $\sqrt{1^2 + 0.5^2} = \sqrt{1.25} \approx 1.12$ . All four sit inside $1.5$ , so with itself $B$ holds $5$ points. Five clears $4$ , so $B$ is core. The same check makes $A$ , $C$ , and $D$ core: $A$ holds $A$ , $B$ , $C$ , $D$ for $4$ , while $D$ holds $A$ , $B$ , $C$ , $D$ , $E$ for $5$ .

Now $E$ . Its distances to $B$ and $D$ are both about $1.12$ , inside $1.5$ , while $A$ and $C$ sit about $2.06$ away because $\sqrt{2^2 + 0.5^2} = \sqrt{4.25} \approx 2.06$ , outside $1.5$ . So $E$ holds $B$ , $D$ , and itself for $3$ . Three misses $4$ , yet $E$ sits inside $B$ 's neighbourhood, so $E$ is border. It joins the cluster and stops there.

$F$ sits $3.04$ from $E$ because $\sqrt{3^2 + 0.5^2} = \sqrt{9.25} \approx 3.04$ , outside $1.5$ , and farther from everything else. Its neighbourhood holds only itself for $1$ , so $F$ is noise.

One cluster, one hanger-on, one outsider: $\{A, B, C, D, E\}$ together with $E$ as border, and $F$ alone as noise. Shrink $\varepsilon$ to $1.0$ and $E$ drops out because $1.12$ no longer fits, which shows how the radius draws the line.

Picking the radius and the count

Sort every point by its distance to its $k$ -th nearest neighbour with $k$ set to $\text{minPts}$ , then read the curve from small to large. Dense points show small values and the curve stays flat, then it bends up where sparse points start. Take $\varepsilon$ at that bend. That plot is called the k-distance graph.

For $\text{minPts}$ , twice the column count is a common start. Raise it and thin structure turns to noise, lower it and dust joins clusters. Scale your columns first with feature scaling, because one wide column decides every distance when you do not.

Watch Out For

A single radius across mixed densities

Tight downtown piles sit a few metres apart while suburban piles spread tens of metres. One radius cannot serve both, and that is structural. Small enough for downtown and the suburb reads as noise. Large enough for the suburb and downtown fuses into one blob.

Symptom: a small nudge to the radius swings the noise share by tens of points, or one region stays whole while another vanishes. Fix: split the noise rate by region instead of reading one global number, then cluster the regions separately or move to a method that lets the radius vary across the data.

Clustering columns that were never on the same scale

Yearly spend runs into the thousands while visit count runs to tens. Square those gaps and spend decides nearly every distance, so inside or outside radius 1.5 means inside or outside in spend and nothing else.

Symptom: clusters that look like clean spend bands, with nearly identical visit means in every group, and a radius that only makes sense after you squint. Fix: standardise each column first with feature scaling, then pick the radius again on the scaled distances.

The Quick Version

DBSCAN calls a point core when its radius holds at least minPts points, including the point itself.
Nearby core points chain into one cluster of any shape, border points hang on without extending it, and the rest stays noise.
Our six-point check with radius 1.5 and minPts 4 gives four cores, one border with three neighbours, and one noise point alone.
No cluster count is chosen up front, and noise is an explicit label instead of forced membership.
One radius cannot fit tight and loose groups at once, and unscaled columns let the widest feature decide every distance.