DBSCAN

DBSCAN finds clusters as regions where points are packed closely together. It works with any shape, decides the number of clusters for you, and labels isolated points as noise.

The idea

Picture a crowd at a festival seen from above. Groups of friends stand close together; a few people wander alone. If you can walk from person to person in small steps without crossing empty ground, those people belong to the same group.

Two settings define "close": the radius ε\varepsilon and the minimum number of neighbours inside it. A point with enough neighbours is a core point. Clusters grow outwards from core points, and anything unreachable is noise.

How it works

  1. For each point, count the points within radius ε\varepsilon (including itself).
  2. Mark points with at least Min neighbours as core points.
  3. Start a cluster at an unvisited core point and add everything within ε\varepsilon of it.
  4. Keep expanding through any core points you reach.
  5. Points reached but not core are border points; points never reached are noise.

Reading the picture

Each cluster gets its own colour, and noise points are shown in grey. The stats count clusters, core points and noise points.

Turn on Show ε\varepsilon around core points to see the circle each core point uses. Overlapping circles chain into one cluster; a gap wider than ε\varepsilon splits clusters apart.

Try this

  1. On Moons, use the defaults. Both crescents are found perfectly, something k-means cannot do.
  2. Shrink Radius (ε\varepsilon) to 0.05. Clusters fragment and most points turn grey.
  3. Grow Radius (ε\varepsilon) to 0.3. The gap between the moons gets bridged and everything merges into one cluster.
  4. On Circles, turn on Show ε\varepsilon around core points and tune Radius (ε\varepsilon) until the ring and the centre separate.

The maths

Neighbourhood

Nε(p)={ q:∥p−q∥≤ε }N_\varepsilon(p) = \{\, q : \lVert p - q \rVert \le \varepsilon \,\}

Core point

∣Nε(p)∣≥minPts\lvert N_\varepsilon(p) \rvert \ge \text{minPts}

Reachable

q is reachable from p if a chain of core points links them, each step ≤εq \text{ is reachable from } p \text{ if a chain of core points links them, each step } \le \varepsilon

Noise

points not reachable from any core point\text{points not reachable from any core point}

Strengths and weaknesses

Good at

  • Finds clusters of any shape.
  • No need to choose the number of clusters.
  • Flags outliers as noise automatically.

Struggles with

  • Struggles when clusters have different densities.
  • Sensitive to ε\varepsilon, which depends on the data's scale.
  • Distance becomes less meaningful in high dimensions.