DBSCAN, Density Reachability, and the Parameter Cliff

Centroid methods assume each group occupies a convex cell and require the number of groups in advance. DBSCAN assumes something weaker and more local: that a cluster is a connected region of the space where points are packed densely enough, and that anything outside such a region is noise. The model has two parameters, a radius and a minimum count, and it returns a partition plus an explicit set of unassigned points. The cost of that freedom is that the parameters are not comparable across datasets and their effect is discontinuous.

The core condition and where the density threshold comes from

The radius is written eps and the count minPts. The neighbourhood of a point p is the set of points within distance eps of it, written N_eps(p), and p counts as a member of its own neighbourhood. A point is a core point when

$$|N_{eps}(p)| \ge minPts$$

Reading that literally gives the density threshold: at least minPts points inside a ball of radius eps, which in d dimensions has volume proportional to eps^d. The threshold is therefore a minimum local density of roughly minPts / (eps^d) points per unit volume, and it is uniform over the whole dataset. Two clusters whose densities differ by more than a modest factor cannot both be described by one pair of parameters: the value of eps that makes the sparse cluster connected merges the dense one’s surroundings, and the value that fits the dense cluster makes the sparse one noise.

minPts has a scale-free reading as well. Setting it to one makes every point core, so chains of points within eps of one another connect freely and the clusters reduce to the connected components of the graph formed by all pairs at distance at most eps. Setting it to two requires each link of a chain to have at least one neighbour. Larger values require progressively stronger evidence that a region is dense, at the price of converting sparse regions entirely to noise.

Density reachability, and why a bridge does not merge clusters

Three relations build the clusters. A point q is directly density-reachable from p when q lies in the neighbourhood of p and p is a core point; the relation is asymmetric, since a non-core point cannot reach anything. A point q is density-reachable from p when there is a chain of points starting at p and ending at q in which each consecutive pair is directly density-reachable; this relation is transitive but still asymmetric. Two points are density-connected when some point o exists from which both are density-reachable, and only this relation is symmetric. A cluster is a maximal set of density-connected points, and a point belonging to no cluster is noise.

The requirement that every step of a chain start from a core point has a visible consequence. A sparse trail of points between two dense groups does not merge them, because the intermediate points fail the core test and cannot propagate reachability. This is exactly the failure that chaining produces in Agglomerative Clustering and the Lance-Williams Recurrence, where single linkage at the same threshold returns the connected components of the same graph and does join the groups. DBSCAN’s clusters are therefore not convex and not defined by any centroid, which is what allows crescent-shaped and ring-shaped groups to be recovered, and what makes the geometric criteria discussed in Cluster Validity, Stability, and Choosing the Number of Clusters misleading when applied to them.

Which points are order dependent

Core points partition uniquely: two core points that are density-connected always end in the same cluster, and the set of core points in each cluster does not depend on the order of processing. Border points, those inside a core point’s neighbourhood but not core themselves, are a different matter. A border point reachable from two different clusters is assigned to whichever cluster reaches it first in the traversal, so the assignment can change with the input order or the neighbour enumeration order. The number of clusters and the core sets do not change; only their fringe does.

The variant usually called DBSCAN* removes the ambiguity by treating non-core points as noise rather than assigning them: clusters are then defined by density reachability from core points only, and the result is fully deterministic. Because a point that is not core may still lie closer to one cluster, discarding it costs some coverage; because the assignment never depends on order, it makes comparisons between runs well defined. The OPTICS algorithm takes a different route, sorting points along an ordering that records, for each prefix, the smallest radius at which the growing cluster still had room, so that a single run describes the clustering for every value of eps at once. Hierarchical density methods extend that idea by selecting clusters across radii according to a persistence criterion, which is the answer to the sensitivity problem below.

Choosing the two parameters honestly

The radius is usually chosen from the sorted distances to the minPts - 1 nearest neighbour. The curve of those distances, taken in ascending order, is flat for points deep inside a dense region and rises steeply for points in sparse space, and the knee of that curve is a candidate for eps: it is the scale at which neighbourhoods stop being dense. With the common two-dimensional setting of minPts = 4, the curve uses the third nearest neighbour distance, which is what the original proposal demonstrated. The procedure is a heuristic, and the curve often has no unambiguous knee, in which case the parameter choice is a statement about what scale of structure is considered real.

minPts is easier to reason about. In d dimensions, a value of d + 1 or larger avoids declaring a cluster out of a couple of coincidences; two-dimensional experiments in the original work used minPts = 4. Raising it changes the result in a specific direction: it increases the number of noise points, keeps clusters only where the density is highest, and can split a region whose interior has varying density. Lowering it toward two makes almost everything cluster.

The discontinuity is the part that surprises. The number of clusters as a function of eps is a step function, not a smooth curve, because cluster membership changes when a single bridge crosses the core threshold. Unlike the within-cluster scatter of a centroid method, there is no objective to plot against the parameters, so the choice cannot be validated internally the way an elbow plot is used for Lloyd’s Algorithm and the Local Minima of k-Means. If the dataset contains groups of very different density, the honest conclusion is that one radius is insufficient, and the hierarchical density-based alternatives are the appropriate model.

import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.neighbors import NearestNeighbors

min_pts = 4                                  # heuristic for low-dimensional data
nn = NearestNeighbors(n_neighbors=min_pts - 1).fit(X)
d, _ = nn.kneighbors(X)
kdist = np.sort(d[:, -1])                    # knee of this curve suggests eps

labels = DBSCAN(eps=0.35, min_samples=min_pts).fit_predict(X)
n_noise = int((labels == -1).sum())          # label -1 marks unassigned points

Cost, indexing, and high-dimensional failure

Without an index, every point requires a scan of the dataset to find its neighbourhood, which is O(n^2) distance computations. With a spatial index that supports radius queries, such as an R-tree or a grid of fixed-size boxes, the neighbourhood of a core point is found in time proportional to the number of points actually within the radius plus a logarithmic term, and the whole run costs O(n log n) on typical inputs. The worst case remains quadratic: when eps is large enough that a ball contains a constant fraction of the dataset, no index helps, because the answer to the query is itself large. Memory is O(n) beyond the index, since the algorithm keeps only labels and the current frontier.

High dimension attacks the parameters directly. As dimensionality grows, the distance from a point to its nearest neighbour approaches the distance to its farthest neighbour, so the number of points inside a ball of radius eps becomes an all-or-nothing quantity determined by the overall extent of the data rather than by any local structure. The minPts test then either passes for nearly every point or for none, and there is no intermediate radius that separates dense regions from sparse ones. Methods that estimate density from a single global bandwidth, including the one described in Kernel Density Estimation and the Bandwidth Trade-off, share that limitation, which is why distance-based outlier scores computed from a fixed number of neighbours often replace radius-based density in high dimensions.