DBSCAN in machine learning, explained in 5 lines

Module 01 · Machine Learning · 55 concepts

In depth / 15 lines

DBSCAN, in more detail

DBSCAN thinks about crowding rather than distance to a centre.

A point sitting in a crowded area is called a core point.

Points near a core point join the same cluster, and clusters spread outward from there.

Points in empty regions belong to nothing and are marked as noise.

That is the big win, because outliers are not forced into a group.

You never tell it how many clusters to find, which is the other big win.

It can trace long, curved and awkward shapes that K-Means cannot.

It needs two settings instead of k, and both matter a great deal.

Eps is how close counts as near, and min samples is how many neighbours count as crowded.

Set eps too small and everything becomes noise.

Set it too large and separate clusters merge into one blob.

A common trick is to plot each point's distance to its neighbours and look for the bend.

It struggles when different clusters have very different densities.

One eps cannot describe a dense group and a sparse group at the same time.

Like anything based on distance, it needs scaled features to mean anything.

Want the full technical article? Wikipedia ↗

Deep dive

k-means asks which centre a point is closest to. DBSCAN asks how crowded the neighbourhood around a point is.

N_\varepsilon(\mathbf{p}) = \{ \mathbf{q} \in D : d(\mathbf{p}, \mathbf{q}) \leq \varepsilon \}

\mathbf{p} \text{ is a core point} \iff |N_\varepsilon(\mathbf{p})| \geq \mathrm{minPts}

A core point sits in a crowd. A border point is inside some core point's neighbourhood without being crowded itself. Everything else is noise.

Pick an unvisited point and find every point within $\varepsilon$ of it.
If there are fewer than $\mathrm{minPts}$ , mark it noise for now and move on.
If there are enough, open a new cluster and add all of them to it.
For each new member that is itself a core point, add its neighbourhood to the cluster too.
Stop expanding when no member adds anyone new, then start again from another unvisited point.

A point marked noise in step two can still be claimed later as a border point, because being inside somebody else's crowd is enough.

The number of clusters is an output rather than an input, which is the difference people notice first.

Clusters take any shape at all, because membership spreads point to point instead of radiating from a centre.

Noise is a first-class answer, so outliers are labelled as outliers rather than forced into the nearest cluster.

\mathrm{minPts} \geq d + 1

A common starting rule is twice the number of dimensions, with a floor at $d + 1$ , and higher on noisy data.

For $\varepsilon$ , compute each point's distance to its $k$ -th nearest neighbour where $k = \mathrm{minPts}$ , sort those distances and plot them.

The curve stays flat and then bends sharply upward. That bend is where points stop being in a crowd, and its height is a good $\varepsilon$ .

O(n \log n)

With a spatial index the run costs that much, and it degrades to $O(n^2)$ in high dimensions where the index stops helping.

One $\varepsilon$ is applied everywhere, so data with a dense cluster and a sparse one cannot be handled by any single value.

That case is what OPTICS and HDBSCAN exist for, and it is the standard reason to reach past DBSCAN.

Test yourself

One question on this card. Every option explains itself once you pick, right or wrong.

Question 1

What does DBSCAN do with a point sitting in a sparse region?

Machine Learning

55 concepts in this module, then a graded test with every answer explained.