Density-Based Clustering with a Focus on DBSCAN

Definition. Density-based clustering groups objects that are connected by regions of high point density, separated by regions of low density. DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is the classic algorithm of this family.

1. Key definitions

• $\varepsilon$-neighbourhood: $N_\varepsilon(p) = \{q \mid d(p,q) \le \varepsilon\}$, the set of all points within radius $\varepsilon$ of $p$ (the point $p$ itself is counted).
• Core point: $p$ is a core point if $|N_\varepsilon(p)| \ge \text{minPts}$.
• Border point: $p$ lies inside the $\varepsilon$-neighbourhood of at least one core point but is not itself a core point.
• Noise (outlier): $p$ is neither core nor border, so it is not assigned to any cluster.
• Reachability: $q$ is directly density-reachable from $p$ if $q \in N_\varepsilon(p)$ and $p$ is core; density-reachability is the transitive chain of such steps, and two points are density-connected when both are reachable from a common core point.

2. Parameters

• $\varepsilon$ (eps): the neighbourhood radius. Too small leaves everything as noise; too large merges distinct clusters. It is often chosen from the elbow of a k-distance plot.
• minPts: the minimum number of points required to form a dense region. A common rule of thumb is $\text{minPts} \ge d + 1$ for dimensionality $d$; values of 4 or $2d$ are typical.

3. Algorithm steps

DBSCAN(D, eps, minPts)
  for each point p in D:
    if p is already labelled: continue
    N = region_query(p, eps)            # all points within eps of p
    if |N| < minPts: label p as NOISE
    else:
      create new cluster C; move p from noise into C
      seeds = N minus p
      for each q in seeds:
        if q is labelled NOISE: relabel q as a border point of C
        if q is labelled UNVISITED: label q as a member of C
        Nq = region_query(q, eps)
        if |Nq| >= minPts:              # q is core, grow the cluster
          add Nq to seeds

4. Worked illustration

Points on a line, $\varepsilon = 1.5$, $\text{minPts} = 3$:

Point	Co-ordinate	Neighbourhood size	Type	Final cluster
p1	0	2 (p1, p2)	border	C1
p2	1	3 (p1, p2, p3)	core	C1
p3	2	3 (p2, p3, p4)	core	C1
p4	3	2 (p3, p4)	border	C1
p5	10	2 (p5, p6)	border	C2
p6	11	3 (p5, p6, p7)	core	C2
p7	12	2 (p6, p7)	border	C2
p8	20	1 (p8)	noise	none

Processing: p1 alone is too sparse and is first marked as noise; then p2 is found to be a core point, opens cluster C1 and pulls in p1, p3 and p4 (p1 is relabelled as a border point and p3, being core, brings in its neighbour p4). p5 is likewise first flagged as noise and only absorbed when core point p6 opens C2. p8 has no neighbours within $\varepsilon$ and remains noise.

Result: $C1 = \{p1, p2, p3, p4\}$, $C2 = \{p5, p6, p7\}$, noise $= \{p8\}$.

5. DBSCAN vs k-means

Criterion	DBSCAN	k-means
Cluster shape	Arbitrary, non-convex shapes	Spherical only
Number of clusters	Discovered automatically from density	Must be supplied as $k$
Outliers	Explicitly detected as noise	Forced into some cluster
Varying densities	Fails when cluster densities differ greatly	Copes better with unequal sizes
Parameters	$\varepsilon$, minPts	$k$, initialisation
Complexity	$O(n \log n)$ with a spatial index, $O(n^2)$ naively	$O(nkt)$
Main sensitivity	To $\varepsilon$ and minPts	To the choice of seeds

Extensions: OPTICS produces an ordering that removes the need to fix $\varepsilon$ in advance, and HDBSCAN handles clusters of differing density.