Density-Based Clustering with DBSCAN and HDBSCAN

GPS pings from a delivery fleet contain depots, customer clusters along streets, and pings from vehicles in transit that belong to nothing. K-means assigns every transit ping to some centroid and drags that centroid off the street. The analyst wants a method that can answer "none of the above", find however many dense regions exist, and follow a curved road. On 500 points of two interlocking crescents DBSCAN recovers the true labels exactly (adjusted Rand index 1.0) where k-means scores 0.25, in a small scikit-learn simulation.

DBSCAN's three kinds of point

DBSCAN takes two parameters, a radius \(\varepsilon\) and a count \(\text{minPts}\) (Ester, Kriegel, Sander and Xu, 1996, A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise, KDD). With \(N_\varepsilon(p) = \{q : d(p,q) \le \varepsilon\}\):

• \(p\) is a core point if \(|N_\varepsilon(p)| \ge \text{minPts}\), counting \(p\) itself.
• \(p\) is a border point if it is not core but lies within \(\varepsilon\) of a core point.
• Everything else is noise.

A cluster is a maximal set of chained core points plus their border points. Formally, \(q\) is density-reachable from core point \(p\) if a chain \(p = p_1, \dots, p_m = q\) exists with each \(p_{i+1} \in N_\varepsilon(p_i)\) and every \(p_i\) except possibly the last being core. Core-point membership is deterministic; only a border point within reach of two clusters can be assigned differently depending on processing order.

The number of clusters is an output and noise is a first-class label. The price is that \(\varepsilon\) and \(\text{minPts}\) define one density level, applied everywhere.

Choosing the parameters, and the argument about speed

\(\text{minPts}\) smooths the density estimate. The original authors used 4 for two-dimensional data, and a later heuristic sets \(\text{minPts} = 2 \cdot d\) for \(d\) dimensions. \(\varepsilon\) is harder: the standard tool is the sorted \(k\)-distance plot, each point's distance to its \(k\)-th nearest neighbour sorted in decreasing order, with \(\varepsilon\) read off a knee. On real data the knee is often invisible at first glance, which the heuristic's own advocates concede (Schubert, Sander, Ester, Kriegel and Xu, 2017, DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN, ACM TODS 42(3)).

That 2017 paper exists because of a genuine dispute. Gan and Tao's SIGMOD 2015 best paper showed that exact Euclidean DBSCAN in \(d \ge 3\) requires \(\Omega(n^{4/3})\) time unless a long-standing problem in computational geometry is solved, contradicting the often-repeated \(O(n \log n)\) claim, and proposed an approximate grid algorithm (Gan and Tao, 2015, DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation, SIGMOD). Schubert and colleagues, including the original DBSCAN authors, replied that the \(O(n \log n)\) figure had always been conditional on index query cost, that a linear scan gives \(\Theta(n^2)\), and that grid methods degrade exponentially with dimension. Both are right: the worst case is genuinely super-linear, and on low-dimensional data with sensible \(\varepsilon\) an index makes DBSCAN fast in practice.

HDBSCAN: every density level at once

A single \(\varepsilon\) cannot describe a dense city-centre cluster and a sparse suburban one. HDBSCAN removes \(\varepsilon\) by considering all of them (Campello, Moulavi and Sander, 2013, Density-Based Clustering Based on Hierarchical Density Estimates, PAKDD).

Define the core distance \(\text{core}_k(x)\) as the distance from \(x\) to its \(k\)-th nearest neighbour, a local inverse density. The mutual reachability distance is

which pushes sparse points away while leaving distances inside dense regions untouched. HDBSCAN builds the minimum spanning tree under \(d_{\text{mreach}}\) and removes edges from longest to shortest. That is single linkage on a transformed metric, and the transform cures chaining: a bridge of sparse noise points has large core distances, so its edges are long and break first.

The raw hierarchy is then condensed. Working with \(\lambda = 1/\text{distance}\), a split where one side has fewer than min_cluster_size points is treated as points falling out of the parent rather than a new cluster. Each surviving cluster \(C\) gets a stability score

where \(\lambda_{\text{birth}}\) is where \(C\) appears and \(\lambda_x\) is where point \(x\) leaves it. The final flat clustering picks the set of non-overlapping clusters that maximises total stability, so a large parent is kept only if it outlives the combined persistence of its children. Different branches are in effect cut at different density levels, which a horizontal dendrogram cut cannot do. The widely used Python implementation also provides soft membership and outlier scores (McInnes, Healy and Astels, 2017, hdbscan: Hierarchical density based clustering, JOSS 2(11)).

When it breaks

Density is meaningless in high dimensions. As \(d\) grows, nearest and farthest neighbour distances converge, so core distances flatten. Running HDBSCAN on raw 768-dimensional embeddings tends to label most points noise or merge everything. The common fix is to reduce dimension first, often with UMAP, but UMAP deliberately distorts density (see the UMAP concept on this track), so the clusters found are partly properties of the embedding.

Noise is a decision, not a discovery. Raising min_samples in HDBSCAN makes the density estimate more conservative and can move a large share of a dataset into the noise label without the underlying data changing. Metrics computed "excluding noise" inherit that setting.

DBSCAN merges clusters that touch. Two dense groups joined by a thin ridge above the threshold become one cluster. HDBSCAN handles this only if min_cluster_size is small enough to let the split register.

New points have no native assignment. Neither algorithm yields a model for unseen data. Refitting reshuffles labels, and approximate prediction against the stored tree degrades as data drift.

Scaling still matters. Every quantity above is a distance, so unscaled features distort density exactly as they distort k-means.