DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

Definition. DBSCAN is a density-based clustering algorithm that groups together points lying in densely populated regions of the data space and marks points lying in sparse regions as noise. Unlike K-means it does not require the number of clusters, it can discover clusters of arbitrary shape, and it handles outliers explicitly.

Key concepts

The algorithm takes two parameters:

• ε (eps) — the radius of a point's neighbourhood, $N_\varepsilon(p) = \{q \mid d(p,q) \le \varepsilon\}$.
• MinPts — the minimum number of points required inside that neighbourhood.

Every point is then classified as:

1. Core point if $|N_\varepsilon(p)| \ge MinPts$.
2. Border point if it lies within ε of a core point but has fewer than MinPts points in its own neighbourhood.
3. Noise point if it is neither core nor border.

A point is density-reachable from a core point if it falls inside that core point's ε-neighbourhood (directly or through a chain of core points). Two points are density-connected if both are density-reachable from some common core point. A cluster is a maximal set of density-connected points.

Algorithm

1. Label every point as unvisited.
2. Pick an unvisited point p and compute $N_\varepsilon(p)$.
3. If $|N_\varepsilon(p)| < MinPts$, label p as noise (it may be relabelled as a border point of a cluster formed later).
4. Otherwise p is a core point: create a new cluster and grow it — insert every point of $N_\varepsilon(p)$; for each newly added point that is itself a core point, expand its neighbourhood too, continuing through the queue until no more core points are reachable.
5. Mark all points added to a cluster as visited and repeat from step 2 until no unvisited points remain.

repeat until no unvisited point is left:
    pick unvisited p, compute N_eps(p)
    |N_eps(p)| <  MinPts --> label p noise (may become border later)
    |N_eps(p)| >= MinPts --> p is a core point: open a new cluster,
                             absorb N_eps(p), then expand through every
                             density-reachable core point
result: set of clusters + noise points

Properties

• Strengths: no need to pre-specify the number of clusters; finds arbitrarily shaped (non-convex) clusters; outliers are reported as noise instead of being forced into a cluster; with a spatial index the neighbourhood search costs about $O(n \log n)$.
• Limitations: one global (ε, MinPts) pair must suit every cluster, so clusters of strongly differing densities are handled poorly; the result is sensitive to the choice of ε and MinPts; effectiveness drops on high-dimensional data, where distances become less meaningful.