DBSCAN

Summary

DBSCAN connects dense neighborhoods. Core points continue expansion; border points join without continuing it. No cluster count is supplied, but the distance rule and density threshold still determine the result.

Consider six points on a line: $A = - 0.1$ , $B = 0$ , $C = 0.1$ , $D = 0.2$ , $E = 0.5$ , $F = 2$ . Use ordinary distance, radius $ε = 0.31$ and $minPts = 4$ , counting each point itself. Which points form a cluster, and which can extend it?

Three types of points

Define $N_{ε} (p) = {q : d (p, q) \leq ε}$ .

Core: $∣ N_{ε} (p) ∣ \geq minPts$ .
Border: non-core, but within the radius of a core point.
Noise: neither core nor border.

Draw edges between points within the radius. Only core nodes may pass expansion along those edges.

A border point joins the cluster but cannot expand it

Derivation

The shaded spans use the same distance scale and radius. D counts five, including itself. E counts two and cannot extend the cluster. F has no core neighbor.

Check: Why is E included as border but unable to continue the cluster expansion?

Read it this way: With minPts=4 including self, counts are D=5, E=2, and F=1. Only the core neighborhood can expand.
Can border E expand the cluster when its neighborhood count is only two?

Original graph construction follows Ester et al. (1996), also available from the original paper archive, and the scikit-learn DBSCAN documentation.

The algorithm

The inclusive neighborhood sizes are $[4, 4, 4, 5, 2, 1]$ for A through F. A, B, C and D are core. They form one connected core component. D reaches E at distance $0.3$ , but E has only two neighbors and cannot expand. F reaches no core.

The cluster contains A through E. Its diameter is $0.6$ , larger than the radius. The radius limits each expansion step, not the cluster’s overall diameter.

Operationally, visit a point and query its neighborhood. If it is core, start or continue expansion through its neighbors. Expand further only from newly found cores. An early noise label can later become a border label when a core reaches it.

Change the neighborhood rule

1. Require closer neighbors

New task: reduce the radius to $0.15$ while keeping the coordinates and minimum count.

Picture and change: remove edges that fail the new distance test, then recount every neighborhood.

Check: counts become $[2, 3, 3, 2, 1, 1]$ . There are no cores, so all six points are noise.

Use when: the meaningful proximity threshold is tighter, with the same density requirement.

2. Change coordinate units

New task: multiply every coordinate by ten without changing physical proximity.

Picture and change: multiply the radius by ten to $3.1$ . Keep the minimum count at four.

Check: counts and membership stay unchanged. Keeping radius $0.31$ instead would leave only self-neighbors.

Use when: a unit conversion changes numeric distances but not the intended neighborhood.

A border point cannot bridge core components

A non-core point may be close to cores from two disconnected components. It cannot merge them because it cannot continue expansion. Standard traversal may assign this shared border point to either cluster. Core components remain fixed for the chosen metric and parameters.

Try visiting E first

E is first labeled noise. Must that label remain?

Check your answer

No. D later reaches E and includes it as border. Non-core means E cannot expand, not that it can never join.

Choosing $ε$ and $minPts$

Inspect sorted neighborhood distances and parameter sensitivity. With four total points including self, the relevant distance is to the third other neighbor. An elbow can suggest a scale; it does not validate the resulting groups. Rules such as $minPts \geq d + 1$ are starting heuristics, not guarantees.

Strengths and weaknesses

Core paths can follow nonconvex shapes. Sparse points can receive noise labels, but noise is not a verified anomaly. A single radius can merge dense groups before admitting a sparser group. High-dimensional distance concentration can weaken neighborhood contrast; inspect the metric and representation. Naive neighborhood work is quadratic in point count. Spatial indexes can help, but do not guarantee $O (n lo g n)$ universally. Materializing every dense neighborhood can also require quadratic memory.

Variants

HDBSCAN (Campello et al., 2013) builds a density hierarchy and selects stable groups.
OPTICS orders points to expose reachability structure across neighborhood scales.

When to use

Setting	DBSCAN vs. alternative
Geospatial clusters	DBSCAN (or HDBSCAN)
Outlier detection	Treat noise as a candidate signal requiring validation
Convex, similar-density clusters	k-means simpler
High-dimensional data	DBSCAN struggles; use embedding + clustering
Need calibrated posterior probabilities	A probabilistic model needs explicit assumptions; HDBSCAN membership strength is not automatically calibrated

Common pitfalls

Validate useful groups, stability and noise against the application, not an unrelated clustering objective. Changing representation or coordinate scales changes distances and requires renewed checks.