DBSCAN: Core, Border, and Noise

Two machine regimes form curved bands around a central operating state. K-Means cuts across the bands, because the means of the bands overlap. DBSCAN follows dense connected paths instead, and leaves sparse points unassigned. The improvement comes from a different structural rule: DBSCAN defines clusters through local density connectivity, not through proximity to one representative center.

The field has said so formally. In 2014 ACM SIGKDD gave its KDD Test of Time Award to the 1996 paper that introduced DBSCAN, and the awarding body's own citation reads: “It proposed the now well-known clustering algorithm DBSCAN, which finds clusters of arbitrary shape, is robust to noise, and scales well to large databases, if the intrinsic dimensionality is not too high so that spatial index structures can be effective in supporting range queries.”

Read it to the end. The arbitrary shapes and the robustness to noise arrive attached to a clause most summaries drop. The scaling holds if the intrinsic dimensionality is not too high, so that spatial index structures can be effective in supporting range queries. That caveat is why a method praised for shape can still disappoint on a wide feature table. The R dbscan authors record the same award in 2019, describing the paper “whose impact earned it the SIGKDD 2014's Test of Time Award”.

A point's role depends on how many observations fall inside its epsilon neighborhood. That count includes the point itself. This is not a convention the lesson is choosing; it is what the shipping implementations document. scikit-learn's API reference describes min_samples as “The number of samples (or total weight) in a neighborhood for a point to be considered as a core point. This includes the point itself.” The library ships eps=0.5 and min_samples=5. Under those defaults a core point needs four other points plus itself.

The R dbscan package states the same convention in its first definition: “Note that together with p ∈ D this definition implies that point p is always part of its own ϵ-neighborhood, i.e., p ∈ Nϵ(p) always holds.” The off-by-one this creates is not cosmetic. It changes which k you plot when you go looking for epsilon. Four of DBSCAN's authors, writing again in 2017, spelled it out in a footnote: “The k-nearest neighbors do not include the query point, but the RangeQuery does include the query point for density estimation. Therefore, k corresponds to minPts = k + 1”.

A core point clears that count. A border point sits inside a core point's neighborhood without clearing it itself. A noise point is reachable from no core region at all, under the parameters you chose.

Parameter search should stay tied to feature scale and to the smallest meaningful local group. Every step after the first has a published answer you can argue with. In two cases the published answers disagree with each other.

Step 1 — standardize the relation. Units, metric and feature scaling are decided before any neighborhood is inspected. Both parameters are measured in whatever space you hand the algorithm.

Step 2 — set density evidence. There is no settled rule for min-samples. Three peer-reviewed sources give three different answers. A 2017 follow-up, written by four of DBSCAN's original authors together with Erich Schubert, restates two of them: “Its purpose is to smooth the density estimate, and for many datasets it can be kept at the default value of minPts = 4 (for two-dimensional data) [16]. Sander et al. [40] suggest setting it to twice the dataset dimensionality, i.e., minPts = 2 · dim.” The R dbscan authors give a third in 2019: “The rule of thumb for setting minPts is to use at least the number of dimensions of the dataset plus one.” Four, 2 · dim, dim + 1. This parameter is a judgement call with named advocates. Pick one rule and say which.

Step 3 — inspect neighbor distances. The k-distance graph is a diagnostic, not an epsilon oracle, and its inventors said so in 1996: “In general, it is very difficult to detect the first "valley" automatically, but it is relatively simple for a user to see this valley in a graphical representation. Therefore, we propose to follow an interactive approach for determining the threshold point.” The R package describes the same manual step in 2019 — plot the kNN distances in decreasing order “and look for a knee in the plot”, with a horizontal reference line added by hand. The plot also degrades on real data. Run these heuristics on the UCI Household data and this is what the 2017 authors report: “This dataset has 5% duplicate records, and attributes have only 32 to 4,186 different values each, so it has a low numerical resolution. This causes artifacts (visible steps) in some of the plots due to tied distances.”

Step 4 — sweep plausible radii, and know what a bad sweep looks like in numbers. The 2017 paper gives two thresholds: “The desirable amount of noise will usually be between 1% and 30%. The size of the largest component (i.e., the largest cluster) can also be used to detect if a clustering has degenerated.” The passage continues: “If the largest component contains more than 20% to 50% of the clustered points, either a hierarchical approach such as OPTICS [3], or HDBSCAN* [13] should be used, or DBSCAN should be run again with a smaller ε radius.” The far end of the sweep has a name of its own. Gan and Tao defined it in 2015: “Every dataset has a unique collapsing radius, which is the smallest ǫ such that exact DBSCAN returns a single cluster.” They fixed MinPts at 100 and swept ǫ from 5,000 up to that radius.

Step 5 — review border cases. The instability is documented, not hypothetical. The scikit-learn user guide opens its implementation note on DBSCAN: “The DBSCAN algorithm is deterministic, always generating the same clusters when given the same data in the same order. However, the results can differ when data is provided in a different order.” Then it names the mechanism: “Second and more importantly, the clusters to which non-core samples are assigned can differ depending on the data order. This would happen when a non-core sample has a distance lower than eps to two core samples in different clusters.” The R dbscan package reports the same effect: “In the DBSCAN algorithm, core points are always part of the same cluster, independent of the order in which the points in the dataset are processed. This is different for border points.” So do DBSCAN's own authors in 2017: “The result of this DBSCAN algorithm is deterministic, but may change if the dataset is permuted.” The check is cheap. Shuffle the rows, refit, and list the points whose label moved.

DBSCAN and K-Means differ in cluster shape, assignment policy, and parameterization. There is a fourth axis, cost, and on it DBSCAN's own literature argues with itself in public.

In 2015 Gan and Tao opened their paper by attacking the founding performance claim: “The original KDD’96 paper claimed an algorithm with O(n log n) running time, where n is the number of objects. Unfortunately, this is a mis-claim; and that algorithm actually requires O(n2) time.” Their abstract also states a lower bound for d ≥ 3 and offers a ρ-approximate alternative in O(n) expected time. The paper won that year's ACM SIGMOD Best Paper Award, recorded on the official list as “DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation. Yufei Tao, Junhao Gan”.

Two years later the original authors answered. They accepted the bound and disputed the reading: “Calling even the worst-case complexity of O(n2) 'intractable' is a stretch of the terminology as used in theoretical computer science.” Both papers remain in print. Shape, assignment policy and parameterization are settled differences between the two methods. Cost is a documented dispute between two named groups, and a comparison table that leaves it out is quietly taking a side.

Moving a parameter alters which points provide density support and which regions connect. The published thresholds tell you when you have moved it too far.

Leaving some points as noise can be more honest than forcing every record into the nearest group. The noise set still depends on scale, density, sampling and row order. A non-core sample sitting within eps of two core samples in different clusters lands wherever the traversal reached it first.

Use DBSCAN when density connectivity matches the phenomenon and one neighborhood scale is defensible. When it is not, the 1999 OPTICS motivation already told you what you are looking at. The practical tests are numeric: a noise share outside 1% to 30%, a largest component over 20% to 50% of the clustered points, or labels that move when the rows are shuffled.