DBSCAN

Summary

DBSCAN (Density-Based Spatial Clustering of Applications with Noise; Ester et al., 1996) groups points by local density. A point with at least $\text{minPts}$ neighbors within distance $\epsilon$ is a core point. Connected core points and their nearby points form clusters; all other points are noise.

Unlike k-means, DBSCAN:

• Discovers the number of clusters automatically. No $k$ required.
• Handles arbitrary cluster shapes (concentric rings, elongated curves, anything connected).
• Identifies noise / outliers as a first-class concept.

Used in: anomaly detection, geospatial clustering (Uber, taxi data), molecule grouping, social network community detection.

The algorithm

Two parameters: $\epsilon$ (neighborhood radius) and $\text{minPts}$ (minimum points, including the point itself, to form a dense region).

For each unvisited point $p$:

1. Find $N_{\epsilon }(p)$ = all points within distance $\epsilon$.
2. If $|N_{\epsilon }(p)|<\text{minPts}$, label $p$ as noise (may later be reclassified as part of another cluster).
3. Otherwise, $p$ is a core point. Start a new cluster:
   • Add $p$ and all points in $N_{\epsilon }(p)$ to the cluster.
   • For each new core point in the cluster, expand by adding its $\epsilon$-neighbors.
   • Continue until no more points can be added.

Each non-noise point ends up in exactly one cluster.

Three types of points

• Core: its $\epsilon$-neighborhood contains $\ge \text{minPts}$ points, counting the point itself.
• Border: fewer than $\text{minPts}$ neighbors but within $\epsilon$ of a core point.
• Noise: neither. Sparsely located, far from any dense region.

Learning objective: trace how overlapping neighborhoods of core points expand one cluster, while a nearby non-core point becomes border and an isolated point remains noise.

Local density becomes a cluster

Which points let DBSCAN keep expanding?

Choosing $\epsilon$ and $\text{minPts}$

Heuristics:

• $\text{minPts}$: rule of thumb $\text{minPts}\ge d+1$ where $d$ is the data dimensionality; often $\text{minPts}=4$ for 2D, $2d$ for higher.
• $\epsilon$: plot the sorted distances to the $\text{minPts}$-th nearest neighbor for each point. Pick $\epsilon$ at the “knee” of the curve. Below it the region is dense, above it sparse.

Choosing these badly produces either one giant cluster (too large $\epsilon$) or all noise (too small $\epsilon$).

Strengths and weaknesses

Strengths:

• No $k$ to specify.
• Arbitrary cluster shapes.
• Robust to outliers (gets noise labels).
• Deterministic given parameters and order of points (mostly).

Weaknesses:

• One $\epsilon$ for all clusters: fails when clusters have very different densities.
• Curse of dimensionality: in high-d, all points become roughly equidistant, so $\epsilon$ becomes meaningless. Use HDBSCAN or alternative.
• Compute: naive $O(n^2)$ for distance computation; $O(n\log n)$ with a spatial index (KD-tree, ball tree) in low dimensions.

Variants

• HDBSCAN (Campello et al., 2013): extends DBSCAN to varying densities by building a hierarchy and extracting clusters from a stability-based selection. Often the better default in practice.
• OPTICS: similar idea, produces a reachability plot rather than discrete clusters.

When to use

Setting	DBSCAN vs. alternative
Geospatial clusters	DBSCAN (or HDBSCAN)
Outlier detection	DBSCAN gets it for free
Convex, similar-density clusters	k-means simpler
High-dimensional data	DBSCAN struggles; use embedding + clustering
Need cluster probability	GMM or HDBSCAN

Common pitfalls

• Picking $\epsilon$ without the k-distance plot. Almost always wrong by orders of magnitude.
• Running on raw high-dim data. Reduce dimension first (PCA, UMAP, learned embedding).
• Comparing DBSCAN and k-means on accuracy. They optimize different objectives; compare on what you actually care about (e.g., user-validated cluster purity).
• Re-running DBSCAN with the same parameters on different-density datasets. $\epsilon$ doesn’t transfer across datasets without normalization.