DBSCAN: Core Points, Density Reachability and Explicit Noise

Replace representatives with neighbourhoods

K-means asks which centre is closest. DBSCAN asks whether a point has enough nearby observations to belong to a dense region. A curved chain of dense neighbourhoods can therefore form one cluster even when its mean lies outside the data.

This is useful for spatial observations, repeated operating regimes and groups separated by sparse gaps. It also introduces a scale: “nearby” means within a chosen radius under a specified metric. Converting metres to kilometres changes that radius numerically; adding irrelevant dimensions can make the neighbourhood concept much less useful.

Core, border and noise

Define the closed neighbourhood

Core points can propagate a cluster through other core points. Border points can be attached but do not propagate it further. This asymmetry is essential: if every nearby border observation could extend the chain, a thin sparse bridge could merge dense regions contrary to the intended density rule.

A useful implementation model is to form a graph on core points, connect pairs within the radius, and find its connected components. Attach eligible border points afterward. This separates the robust connectivity structure from ambiguous attachment decisions.

A complete one-dimensional example

Take \(0,0.1,0.2,1.0,1.1,1.2,3.0\) with \(\varepsilon=0.15\) and m=3, including self. Point 0.1 sees 0, 0.1 and 0.2, so it is core. The endpoints 0 and 0.2 see only two points each, so they are border. The same pattern occurs around 1.1. Point 3 sees only itself and is noise.

The result is two clusters, \(\{0,0.1,0.2\}\) and \(\{1.0,1.1,1.2\}\), plus noise. Notice that each cluster has only one core point. Counting neighbours with a convention that excludes self without adjusting m would change the result.

points = [0.0, 0.1, 0.2, 1.0, 1.1, 1.2, 3.0]
neighbours = [[j for j, y in enumerate(points) if abs(x-y) <= 0.15]
              for x in points]
core = [i for i, near in enumerate(neighbours) if len(near) >= 3]
assert core == [1, 4]
assert neighbours[-1] == [6]

This checks the neighbourhood calculation rather than reimplementing a full library. It is a useful unit-level diagnostic when a clustering result is surprising.

Border ambiguity and ordering

A non-core observation can lie within the radius of core points from two different components. Attaching it to one component need not connect the components because it cannot propagate density reachability. Some implementations assign such a point to the first discovered cluster, so input order can change a small number of border labels.

Core components are a more stable comparison target than arbitrary numeric cluster IDs. Noise labels may also change as the radius or minimum count changes. Do not interpret the label −1 as a probability that an observation is erroneous; it means unassigned under the chosen density rule.

Selecting the radius and minimum count

A sorted nearest-neighbour distance plot can reveal candidate density scales, but its bend is a heuristic. Choose m with regard to sample size, dimensionality and how much local support should be required. Very small values can turn random chains into clusters; very large values can erase small populations.

Inspect sensitivity across nearby settings. If a small radius change merges all groups, the evidence for a robust flat partition is weak. Report noise fraction, cluster sizes, representative members and stability rather than searching only for a visually attractive label plot.

Why varying density is difficult

A radius large enough to connect a sparse valid group may join two dense groups through intermediate observations. A smaller radius can preserve those dense groups while labelling the sparse one noise. A single global scale cannot always satisfy both requirements.

OPTICS represents density structure through an ordering and reachability values. HDBSCAN builds and condenses a hierarchy over density scales. Both offer different ways to inspect varying density; neither removes the need for a meaningful metric and adequate sampling.

Cost and use beyond the training sample

Neighbourhood search can be efficient with suitable spatial indexes in favourable low-dimensional settings. Worst-case work can be quadratic, and storing all neighbourhoods can require quadratic memory when the radius is large. High-dimensional distances often defeat tree-based search advantages.

A new observation does not automatically receive a label from the original fitted DBSCAN procedure. One may attach it to nearby core points, but that is an added prediction rule and can encounter multiple eligible groups. Rebuilding the clustering can instead change the original components. Choose the deployment interpretation explicitly.

Use DBSCAN when local density connectivity matches the task and explicit unassigned observations are useful. Evaluate in the original feature space; a two-dimensional embedding can manufacture neighbourhood gaps that were not present in the data.

References

1. Ester, Kriegel, Sander and Xu. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. KDD, 1996.
2. scikit-learn. Clustering user guide.