DBSCAN and density-based clustering

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) (Ester et al., 1996) defines a cluster as a maximal set of density-connected points, i.e. a dense region separated from other clusters by regions of low density. It can find clusters of arbitrary shape and marks noise.

Parameters and terms

• ε (eps): radius of the neighbourhood of a point.
• MinPts: minimum number of points in an ε-neighbourhood for the point to be dense.
• Core point: has at least MinPts points (including itself) within ε.
• Border point: fewer than MinPts in its ε-neighbourhood but lies inside the neighbourhood of a core point.
• Noise (outlier): neither core nor border.
• Directly density-reachable: q is within ε of a core point p. Density-reachable: reachable by a chain of directly reachable points. Density-connected: both points are density-reachable from a common core point.

Algorithm

1. Mark all points unvisited.
2. Pick an unvisited point p; mark it visited.
3. If p is a core point: create a new cluster C, add p, and add all
   points in its eps-neighbourhood to a candidate set N.
     For each point q in N:
        if q is unvisited: mark visited; if q is core, add its
        eps-neighbourhood to N
        if q is not in any cluster, add q to C
   else mark p as noise (it may later become a border point).
4. Repeat until all points are visited.

Advantages of density-based clustering

• Finds clusters of arbitrary shape (not only spherical).
• Does not need the number of clusters in advance.
• Handles noise and outliers explicitly.
• Needs only one scan of the data; with a spatial index the cost is O(n log n).
• The result is not dependent on the order of the points (except for border points).
• Disadvantages: sensitive to ε and MinPts; struggles with clusters of very different densities and with high-dimensional data.