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

DBSCAN is a density-based clustering algorithm that groups points that are closely packed together, marking points in low-density regions as noise. It finds clusters of arbitrary shape and needs no predefined number of clusters $k$.

Key Concepts

• ε-neighbourhood (Eps): for a point $p$, the set of points within distance $\varepsilon$ of $p$.
• MinPts: minimum number of points required to form a dense region.
• A point $p$ is:
  • a core point if its ε-neighbourhood contains at least MinPts points (including itself);
  • a border point if it is within the ε-neighbourhood of a core point but is not itself a core point;
  • a noise point if it is neither core nor border.

Algorithm

DBSCAN(D, Eps, MinPts)
1. Mark all points as unvisited.
2. For each unvisited point p in D:
     a. find all points q within Eps of p (N_eps(p));
     b. if |N_eps(p)| < MinPts → mark p as noise (temporarily);
     c. else make p a new cluster C and expand:
          - for every point q in N_eps(p): if q is unvisited,
            mark q visited, find its neighbourhood,
            if q is a core point add its neighbours to the cluster,
            if q was labelled noise, add q to cluster C.
3. Repeat until all points are processed.

Expansion merges any overlapping dense neighbourhoods: cluster grows by absorbing every point reachable through a chain of core points.

Properties

• Detects clusters of arbitrary shape (e.g., donut/C shapes), unlike k-Means.
• Handles noise/outliers explicitly.
• Needs only two parameters (Eps, MinPts) — no $k$ in advance.
• Sensitivity: results depend strongly on a good choice of Eps and MinPts (often found via a k-distance graph).
• Complexity: O(n log n) with a spatial index (e.g., R-tree); O(n²) without.

    ● ● ●   (dense region = cluster)
  ● ● ● ● ●
    ● ● ●
         ●            ← noise point (isolated)

Here the dense blob forms one cluster and the isolated point is flagged as noise.