DBSCAN Explained: Density-Based Clustering, Epsilon, MinPts, and Outliers

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) finds groups of points that sit in dense regions and labels sparse points as outliers. You do not choose the number of clusters $k$ in advance. You choose a neighborhood radius $\varepsilon$ (epsilon) and a minimum neighbor count MinPts. That is a better match than k-means when clusters are non-spherical or when the dataset is contaminated with noise.

This DBSCAN tutorial defines core, border, and noise points, explains how to pick $\varepsilon$, compares DBSCAN with k-means, and lists the scaling issues that appear in high dimensions.

Core points, border points, and noise

Fix a distance (usually Euclidean) and parameters $(\varepsilon,\mathrm{MinPts})$.

• A point is a core point if at least MinPts points (including itself) lie inside its $\varepsilon$-ball.
• A point is directly density-reachable from a core point if it lies in that ball.
• A cluster is built by chaining density-reachability from core points.
• A border point is not core but falls inside a core point’s neighborhood.
• A noise (outlier) point is neither core nor border.

Two moons, a ring, or a dense blob beside a sparse spray are classic DBSCAN pictures. K-means would cut moons with a straight Voronoi edge; DBSCAN can follow the density ridge.

The DBSCAN Calculator makes core versus noise labels visible as you drag $\varepsilon$ and MinPts.

How the algorithm runs

1. Mark all points unvisited.
2. Pick an unvisited point. If it is not core, mark it noise (it may later become a border point).
3. If it is core, start a new cluster and collect every point density-reachable from it (a region query plus a queue/stack).
4. Repeat until every point is visited.

Complexity is $O(n\log n)$ with a spatial index (KD-tree, R-tree) in low dimension, and $O(n^2)$ naive. High dimension hurts both runtime and the meaning of $\varepsilon$, for the same concentration-of-distance reasons that hurt k-NN.

Choosing epsilon and MinPts

MinPts. A common heuristic is $\mathrm{MinPts}\ge d+1$ for dimension $d$, and often $4$ or $5$ on 2D demos. Larger MinPts demands denser cores and labels more points as noise.

Epsilon. Plot a k-distance graph: for each point, the distance to its $k$th neighbor with $k=\mathrm{MinPts}$. Sort those distances. The “elbow” where distances jump is a candidate $\varepsilon$. Too small $\varepsilon$ shatters one cluster into fragments; too large $\varepsilon$ merges everything.

There is no universal pair. Scale features first. $\varepsilon=0.5$ on unscaled coordinates is meaningless.

DBSCAN versus k-means

If every point must belong to a segment and clusters are blob-like, start with k-means. If you need “these points are not in any group,” start with DBSCAN.

HDBSCAN (hierarchical DBSCAN) reduces the pain of a global $\varepsilon$ when densities vary across clusters.

Distance choice and preprocessing

DBSCAN is only as good as $d(\cdot,\cdot)$. Standardize continuous features. For mixed types, consider Gower or a custom metric — and know that spatial indexes may no longer apply. Cosine distance can be more natural for directional data, but then $\varepsilon$ is in cosine units, not meters.

Outlier scores from DBSCAN are discrete (noise vs not). If you need a continuous anomaly score, isolation forests or k-distance itself may be more informative.

Frequently asked questions

Does DBSCAN need the number of clusters?

No. That is the headline advantage. You still set density parameters, which indirectly control how many clusters appear.

Why did DBSCAN return one giant cluster?

$\varepsilon$ is too large or MinPts is too small, so density-reachability links separate groups. Decrease $\varepsilon$ or increase MinPts. Also check that two clusters are not connected by a thin dense bridge.

Why is everything noise?

$\varepsilon$ is too small or MinPts is too large for the scale of the data. Check feature scaling. Plot the k-distance elbow.

Is DBSCAN unsupervised?

Yes. Labels are invented from geometry, not from a target column. You can still evaluate clusters afterward with silhouette (awkward with noise) or domain checks.

Next steps

Generate two moons plus 10% uniform noise. Run k-means with $k=2$ and DBSCAN with a tuned $\varepsilon$. Compare how noise is handled. Then use the DBSCAN Calculator and the K-Means Calculator. For the distances underneath both algorithms, keep the vector norms article open.