Density-Based Methods

Density-Based Methods

1. Motivation

Partitioning and hierarchical methods find spherical/convex clusters. Density-based methods instead grow clusters in regions where the density of objects exceeds a threshold, so they can discover arbitrary-shaped clusters and, importantly, they are robust to noise (noise points are explicitly identified, not forced into a cluster).

Key idea: for each point in a cluster, the neighbourhood of a given radius $\varepsilon$ must contain at least a minimum number of points $MinPts$ — i.e. the neighbourhood density is above a threshold.

2. Core Definitions (DBSCAN)

Concept	Definition
$\varepsilon$-neighbourhood $N_\varepsilon(p)$	$\{q \in D \mid dist(p,q) \le \varepsilon\}$
Core point (core object)	A point with $\|N_\varepsilon(p)\| \ge MinPts$ — the interior of a dense region
Border point	A non-core point lying inside the $\varepsilon$-neighbourhood of a core point — on the cluster edge
Noise / outlier	A point that is neither core nor border
Directly density-reachable	$p$ is directly density-reachable from $q$ if $p \in N_\varepsilon(q)$ and $q$ is core
Density-reachable	There is a chain $q = p_1, p_2, \dots, p_n = p$ where each $p_{i+1}$ is directly density-reachable from $p_i$
Density-connected	$p$ and $q$ are density-connected if there exists $o$ such that both $p$ and $q$ are density-reachable from $o$

Density-reachability is asymmetric (a border point cannot reach its core point back) and not transitive-closed in both directions, therefore a cluster is defined via density-connectivity (which is symmetric):

3. DBSCAN Algorithm

DBSCAN(D, eps, MinPts):
  C = 0
  for each unvisited point p in D:
      mark p visited
      N = regionQuery(p, eps)
      if |N| < MinPts:
          label p as NOISE                  (may later become a border point)
      else:
          C = C + 1                         (start a new cluster)
          expandCluster(p, N, C, eps, MinPts)

expandCluster(p, N, C, eps, MinPts):
  add p to cluster C
  for each p' in N (growing seed list):
      if p' is unvisited:
          mark p' visited
          N' = regionQuery(p', eps)
          if |N'| >= MinPts:  N = N ∪ N'    (p' is core -> keep expanding)
      if p' is not yet a member of any cluster:
          add p' to cluster C

4. Worked Example (2-D points, $\varepsilon = 1.5$, $MinPts = 3$)

Point	Coordinates	Count in $\varepsilon$-Nbh	Type
P1	(1, 2)	3	core
P2	(2, 2)	3	core
P3	(1, 1)	3	core
P4	(8, 8)	3	core
P5	(9, 8)	3	core
P6	(8, 9)	3	core
P7	(5, 5)	1	noise
P8	(1, 7)	1	noise

Result: cluster C1 = {P1, P2, P3}, cluster C2 = {P4, P5, P6}, noise = {P7, P8} — two dense regions correctly separated, with the isolated points rejected as noise.

5. Parameter Selection

Parameter	Effect	Advice
$\varepsilon$ (eps)	Too small → most points become noise, clusters fragment; too large → clusters merge	$k$-distance graph (elbow) — sort the distance to the $k$-th nearest neighbour, choose $\varepsilon$ at the "knee" (use $k = MinPts$)
$MinPts$	Too small → noise becomes clusters; too large → real clusters shrink	Rule of thumb $MinPts \ge \dim+1$, commonly $MinPts = 2 \times \dim$ or 4 for 2-D

6. Complexity and Properties

• Time: $O(n \log n)$ with a spatial index (R*-tree / k-d tree / grid), $O(n^2)$ in the worst case without indexing.
• Space: $O(n)$.
• Number of clusters is not required in advance; finds arbitrary shapes (rings, spirals, elongated); explicitly handles noise.
• Weakness: clusters of different densities and varying $\varepsilon$ cannot be handled by a single global $\varepsilon$ (hence OPTICS, which orders points by reachability distance).

OPTICS builds a reachability plot whose "valleys" reveal clusters of widely differing densities.

7. Related Density-Based Methods

Method	Characteristic
DBSCAN	Classic density-based clustering; single $\varepsilon$, $MinPts$; noise-aware
OPTICS	Ordering points to identify clustering structure; produces a reachability plot; handles multiple densities; parameter $\varepsilon$ becomes a maximum radius
DENCLUE	Models the overall point density as a sum of influence functions (usually Gaussian) and finds local maxima ("density attractors")
Mean-shift	Kernel density-based mode seeking; iteratively shifts points to the closest density peak
CLIQUE (see grid methods)	Density threshold on a grid; combines grid and density ideas for high dimensions

DENCLUE influence function/density:

A local maximum $\hat f(x^*)\ge\xi$ is a density attractor; clusters are formed by assigning each point to the attractor it climbs to (density-attracted), and merging attractors connected by a density ridge.

8. Exam Points

• Define core/border/noise, density-reachability and density-connectivity; hence explain why a cluster must be defined by density-connectivity — 7-10 marks.
• Write the DBSCAN algorithm (pseudo-code) and run it on given points with $\varepsilon$ and $MinPts$ — 10 marks (very frequent).
• Compare DBSCAN with k-means (shape, noise, parameters, complexity) — 5 marks.
• Explain how $\varepsilon$ and $MinPts$ are chosen ($k$-distance plot) — 5 marks.
• Short notes on OPTICS and DENCLUE — 3-5 marks.