Potholes do not form round blobs
A council receives 1,100 pothole reports over a winter, each with a grid reference. Most of them lie along two heavily used roads: an inner ring and an outer bypass, both of which curve. The rest are scattered across minor streets. Ask for three round groups and you will get three round groups, cutting each curved road into arbitrary segments, because that is what a centroid method is built to do.
DBSCAN clustering takes a different definition. A cluster is a region where points are packed closely together, whatever shape that region happens to be, and anything in a sparse region is not assigned to a cluster at all. Two parameters set what “closely” means. eps is the radius of the neighbourhood around a point, and min_samples is how many points must fall inside that radius for the point to count as a core point. Core points in each other’s neighbourhoods get chained into one cluster, points inside a core point’s radius but without enough neighbours of their own become border points, and everything else is labelled noise with the label minus one.
That noise label is the feature practitioners undervalue. You never have to pretend a scattered report belongs to a road.
import numpy as np, pandas as pd
rng = np.random.default_rng(94)
def arc(n, cx, cy, r, a0, a1, jitter):
t = rng.uniform(a0, a1, n)
return np.c_[cx + r * np.cos(t) + rng.normal(0, jitter, n),
cy + r * np.sin(t) + rng.normal(0, jitter, n)]
inner = arc(420, 0.0, 0.0, 3.0, 0.2, 3.1, 0.22) # inner ring road
outer = arc(480, 1.4, -0.9, 5.4, 3.3, 6.1, 0.26) # outer bypass
scatter = rng.uniform(-8, 8, size=(200, 2)) # reports on minor streets
reports = np.vstack([inner, outer, scatter])
truth = np.r_[np.zeros(420), np.ones(480), np.full(200, -1)]
print(reports.shape)
# (1100, 2)
The planted scatter is scored as its own class, so a method that correctly labels those 200 reports as noise is rewarded for it.
Choosing eps and min_samples for DBSCAN clustering
Pick min_samples first, from domain reasoning rather than search. A common starting point is twice the number of features, so four here, though for geographic data I prefer a slightly larger value to suppress accidental triples. Then derive eps from the data: compute each point’s distance to its min_samples minus one nearest neighbour, sort those distances, and look for the knee. Below the knee you are inside dense regions; above it you are in the sparse background.
from sklearn.neighbors import NearestNeighbors
nn = NearestNeighbors(n_neighbors=8).fit(reports)
d, _ = nn.kneighbors(reports)
k_dist = np.sort(d[:, -1])
for q in [50, 75, 90, 95, 99]:
print(f"{q}th percentile of 7th-neighbour distance: {np.percentile(k_dist, q):.3f}")
# 50th percentile of 7th-neighbour distance: 0.246
# 75th percentile of 7th-neighbour distance: 0.342
# 90th percentile of 7th-neighbour distance: 1.363
# 95th percentile of 7th-neighbour distance: 1.900
# 99th percentile of 7th-neighbour distance: 2.445
The jump from 0.342 at the 75th percentile to 1.363 at the 90th is the knee, and it is not subtle. Roughly three quarters of the reports sit in dense road corridors with neighbours within a third of a kilometre; the rest are isolated. Anything between 0.35 and 0.6 should work, so take 0.45.
from sklearn.cluster import DBSCAN, KMeans
from sklearn.metrics import adjusted_rand_score
db = DBSCAN(eps=0.45, min_samples=8).fit(reports)
lab = db.labels_
core = np.zeros(len(reports), dtype=bool)
core[db.core_sample_indices_] = True
print("clusters:", len(set(lab) - {-1}))
print(f"core={core.sum()} border={((lab != -1) & ~core).sum()} noise={(lab == -1).sum()}")
print("ARI DBSCAN :", round(adjusted_rand_score(truth, lab), 3))
print("ARI k-means:", round(adjusted_rand_score(
truth, KMeans(n_clusters=2, n_init=10, random_state=0).fit_predict(reports)), 3))
# clusters: 2
# core=890 border=44 noise=166
# ARI DBSCAN : 0.924
# ARI k-means: 0.603
Two roads found, 166 reports set aside as background, and 0.924 against 0.603 for a centroid method given the correct number of clusters. This is the case density methods were invented for, and it is worth contrasting with the overlapping bike-station blobs in the clustering fundamentals chapter, where DBSCAN scored 0.097 on data that suited the k-means objective perfectly. Neither result is a verdict on the algorithm.
How sensitive is it, honestly
Very. This is the part of the method that gets glossed over.
for eps in [0.25, 0.35, 0.45, 0.60, 0.90, 1.40]:
l = DBSCAN(eps=eps, min_samples=8).fit_predict(reports)
print(f"eps={eps:<5} clusters={len(set(l) - {-1}):<3} "
f"noise={(l == -1).sum():<4} ARI={adjusted_rand_score(truth, l):.3f}")
# eps=0.25 clusters=17 noise=302 ARI=0.274
# eps=0.35 clusters=4 noise=186 ARI=0.715
# eps=0.45 clusters=2 noise=166 ARI=0.924
# eps=0.6 clusters=2 noise=153 ARI=0.897
# eps=0.9 clusters=2 noise=124 ARI=0.841
# eps=1.4 clusters=3 noise=70 ARI=0.135
for ms in [4, 8, 16, 30]:
l = DBSCAN(eps=0.45, min_samples=ms).fit_predict(reports)
print(f"min_samples={ms:<3} clusters={len(set(l) - {-1}):<3} "
f"noise={(l == -1).sum():<4} ARI={adjusted_rand_score(truth, l):.3f}")
# min_samples=4 clusters=3 noise=158 ARI=0.913
# min_samples=8 clusters=2 noise=166 ARI=0.924
# min_samples=16 clusters=3 noise=182 ARI=0.722
# min_samples=30 clusters=5 noise=572 ARI=0.386
A radius of 0.25 shatters the two roads into seventeen fragments. A radius of 1.4 bridges the gap between them through the scattered reports and collapses the structure, scoring 0.135, worse than k-means. The usable window runs from about 0.35 to 0.9, and outside it the output is not a slightly worse clustering but a different and wrong account of the city. min_samples is gentler but not safe: at 30, more than half the reports became noise.
Scale matters doubly here, because eps is an absolute distance. Standardise or rescale your features and every previously tuned eps becomes meaningless, which is an easy way to break a pipeline you thought was working.
Where density clustering breaks
One radius has to serve the whole dataset, so a dataset containing both a tightly packed region and a sparse one has no good eps. Here a depot forecourt with 150 reports in a tight knot sits next to a sprawling estate with 150 spread thinly.
tight = rng.normal([3.2, 0.0], 0.20, size=(150, 2)) # a depot forecourt
diffuse = rng.normal([0.0, 0.0], 1.30, size=(150, 2)) # a sprawling estate
mixed = np.vstack([tight, diffuse])
mixed_truth = np.r_[np.zeros(150), np.ones(150)]
for eps in [0.25, 0.5, 1.0, 1.6]:
l = DBSCAN(eps=eps, min_samples=8).fit_predict(mixed)
print(f"eps={eps:<4} clusters={len(set(l) - {-1})} "
f"noise={(l == -1).sum():<3} ARI={adjusted_rand_score(mixed_truth, l):.3f}")
# eps=0.25 clusters=3 noise=133 ARI=0.850
# eps=0.5 clusters=5 noise=65 ARI=0.585
# eps=1.0 clusters=1 noise=7 ARI=0.002
# eps=1.6 clusters=1 noise=1 ARI=0.000
from sklearn.cluster import HDBSCAN
h = HDBSCAN(min_cluster_size=20, copy=True).fit_predict(mixed)
print("HDBSCAN clusters:", len(set(h) - {-1}),
"ARI:", round(adjusted_rand_score(mixed_truth, h), 3))
# HDBSCAN clusters: 2 ARI: 0.665
No value of eps recovers both groups. The 0.850 at 0.25 looks respectable but is misleading: it is earned by finding the dense forecourt and labelling most of the estate as noise, which is not the answer anyone asked for. Push the radius wider and the forecourt is swallowed into the estate.
HDBSCAN, available as sklearn.cluster.HDBSCAN since scikit-learn 1.3, is the standard fix. It runs DBSCAN across all radii and keeps the clusters that persist, so you set a minimum cluster size instead of a radius. It did recover two clusters, but at 0.665 it only partly untangled this case, so report that as a real improvement rather than a solution. The algorithm’s behaviour across parameters is documented in the DBSCAN estimator reference and the HDBSCAN user guide section.
Two further limits. DBSCAN has no predict method, because a new point’s cluster membership depends on the density around it, so scoring new data means refitting or writing your own nearest-core-point rule. And in high dimensions, distances concentrate and the knee in the k-distance curve flattens out, which is the same curse that complicates detecting outliers in high-dimensional data. Reduce dimensions first, or use a method built for the regime.
Frequently Asked Questions
What do the minus one labels mean?
They are noise points: rows that fell in no dense neighbourhood. They are not a failure, they are the output the method is designed to give. Check what fraction they represent, because a jump above roughly a third of your rows usually means eps is too small for the density present.
How do I choose eps without a chart?
Fit a NearestNeighbors model, take each point’s distance to its min_samples minus one neighbour, and print the percentiles. The radius sits where those percentiles start rising steeply, which on the pothole data was between the 75th at 0.342 and the 90th at 1.363.
Should I use DBSCAN or HDBSCAN?
Start with HDBSCAN unless you have a physically meaningful radius. Setting a minimum cluster size is an easier judgement than setting a distance, and it tolerates clusters of differing density, though as the example above shows it will not rescue every mixed-density dataset.
Key Takeaways
- Density-based clustering finds arbitrarily shaped groups and labels sparse rows as noise, which beat a centroid method 0.924 to 0.603 on curved road corridors.
- Derive
epsfrom a sorted k-distance curve rather than guessing, and treat the knee between the 75th and 90th percentile as your working range. - Expect real sensitivity: on identical data, radii of 0.25 and 1.4 gave seventeen clusters and a collapsed single structure respectively, scoring 0.274 and 0.135.
- Because
epsis an absolute distance, any change to feature scaling invalidates a tuned value, so pin the scaler and the radius together. - Reach for
HDBSCANwhen cluster densities differ, but verify the result rather than assuming it solves the problem, since it reached only 0.665 on the mixed-density example here.