Core ML

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.

A cluster is whatever shape a chain of dense neighbourhoods happens to make, so a crescent comes out whole and the points belonging to nothing get labelled noise

Why Does This Exist?

A bike-share operator has 200,000 GPS pings from bikes sitting still overnight. Where do bikes actually pile up, so the vans know where to go at 6am?

Try k-means and you get centres. One lands in the middle of the river, because bikes collect along a two-kilometre riverside path and the average of a long curve is off the curve. Every centre-based method has this problem: it describes a group by one point in the middle, which only works if the group has a middle.

DBSCAN throws that out and describes a group by whether its points are packed together, which needs no middle and no k. One word first: density here means how many other pings sit within a short distance of a given ping.

Think of It Like This

A rumour passed at arm's length

Ten thousand people at a street festival. You may only whisper to someone within arm's reach, and you'll only pass a rumour on if six people are within reach of you — fewer than that and you don't feel sure enough.

Start the rumour in the crush by the stage. It races through: everyone there has twenty people within reach. It travels the food-truck queue too, one arm's length at a time, so the whole queue hears it even though the queue is a hundred metres long and two wide. Whatever shape the crowd is, the rumour fills it.

At the thin edges someone hears it with three people nearby. They know it, they just never repeat it, so it stops. The couple on a picnic blanket forty metres out never hear it at all.

Three kinds of person: the ones who spread it, the ones who only receive it, the ones it never reaches. Core, border, noise. And notice the rule was one arm's length for the whole festival — the crush and the picnic field are nothing like the same density.

How It Actually Works

Core, border, noise

Two parameters. A radius, usually written $\varepsilon$ , and a count, min_samples. A ping with at least min_samples pings inside its radius is a core point. Any two core points within a radius of each other belong to the same cluster, and that chains: A joins B, B joins C, so A and C are one cluster even a kilometre apart.

A ping inside some core point's radius but without enough neighbours of its own is a border point. It joins that cluster and can't extend it. Everything left over is noise.

That last label is what no centroid method gives you. K-means assigns every row to something, so a bike abandoned in a car park two miles out lands in a cluster and drags its centre. DBSCAN says it belongs to nothing, which is often what you wanted — the same machinery turns up in outlier detection. You never state how many clusters to look for either; the count falls out of the data.

Picking the radius

The one parameter worth real effort. For every ping, measure the distance to its k-th nearest neighbour, with k set to min_samples. Sort those distances and plot them. Most pings sit in dense areas so their k-th neighbour is close and the curve stays flat, then it bends sharply upward as you reach the pings with nothing near them. Take the radius at the bend.

For min_samples, twice the column count is a common start — it's a smoothing dial, and raising it relabels thin structure as noise.

One radius, two densities

Here's the wall. Downtown, bikes sit metres apart; in the suburbs the same pile-up spreads over fifty metres. One radius cannot serve both, and that's the design. Small enough for downtown and every suburban cluster is noise; big enough for the suburbs and downtown fuses into one blob.

HDBSCAN is the fix, and it's the version to reach for now. Instead of one radius it builds the hierarchy across every radius at once, then keeps the clusters that survive the widest range of them. Dense clusters get found at small radii, sparse ones at large radii, same run. The radius disappears and you're left tuning min_samples, which is much easier to be wrong about.

Show Me the Code

Two clusters, same shape, one five times sparser. Noise means neither core nor within reach of a core point.

1import numpy as np2
3def scan(X: np.ndarray, eps: float, min_pts: int) -> tuple[float, float, bool]:4    near = np.sqrt(((X[:, None] - X[None]) ** 2).sum(-1)) <= eps5    core = near.sum(axis=1) >= min_pts             # the count includes the point itself6    noise = ~core & ~near[:, core].any(axis=1)     # not core, and touching no core point7    # any two core points within eps of each other end up in the same cluster8    joined = (near[:400, 400:] & core[:400, None] & core[None, 400:]).any()9    return float(noise[:400].mean()), float(noise[400:].mean()), bool(joined)10
11rng = np.random.default_rng(4)12# 400 downtown pings, then 100 suburban ones: same shape, a fifth of the density13X = np.vstack([rng.normal([0.0, 0.0], 0.30, (400, 2)), rng.normal([5.0, 0.0], 1.50, (100, 2))])14for eps in (0.40, 0.60, 0.90, 1.20):15    a, b, joined = scan(X, eps, 10)16    print(f"eps {eps:.2f}  downtown noise {a:4.0%}  suburb noise {b:4.0%}  merged: {joined}")17    # -> eps 0.40  downtown noise   0%  suburb noise 100%  merged: False18    # -> eps 0.60  downtown noise   0%  suburb noise  73%  merged: False19    # -> eps 0.90  downtown noise   0%  suburb noise  32%  merged: False20    # -> eps 1.20  downtown noise   0%  suburb noise  11%  merged: True

At 0.40 the suburb is entirely noise. By the time it's down to 11 percent, the two clusters have become one. No row in that table is shippable.

Watch Out For

One radius across clusters of different densities

The symptom is a noise fraction that swings wildly on a small radius change — all of one group at 0.40, a third of it at 0.90. If a twenty percent nudge moves the noise count by tens of points, the radius is doing the clustering, not the data.

Check it directly: split the noise fraction by region rather than reading one global number. Then switch to HDBSCAN, which finds each cluster at whichever radius it persists at. If you must keep a fixed radius, cluster the dense and sparse regions separately and say so, rather than shipping a run that quietly deleted a real group.

Running it on hundreds of columns

In high dimensions every pairwise distance drifts toward the same value, so the ratio between the nearest and farthest neighbour approaches one. The k-distance plot comes back nearly flat with no bend, and the radius that looked fine at 0.9 makes everything one cluster at 0.91 and everything noise at 0.89. That's distance concentration, not a bad parameter.

Reduce dimensions first — UMAP into ten or so columns, then cluster that — and be honest about what changed. Those clusters are now a property of the embedding as much as the data, and refitting the embedding with a new seed can move them.

The Quick Version

A point with min_samples neighbours inside radius $\varepsilon$ is a core point. Nearby core points chain into one cluster, points reachable from one are border points, the rest is noise.
No k, any cluster shape, and an explicit label for points belonging to nothing.
Pick the radius from the k-distance plot: sort every point's distance to its k-th neighbour, take the bend.
One global radius cannot handle clusters of different densities. Structural, not a tuning problem.
HDBSCAN builds the hierarchy over all radii and keeps the clusters that persist, leaving only min_samples.
In high dimensions distances concentrate and this stops working. Reduce first, then own the caveat.