DBSCAN finds clusters as dense regions separated by sparse ones. It discovers the number of clusters itself, follows arbitrary shapes, and labels outliers as noise. This page covers the definitions, parameter selection, code, and when to switch to HDBSCAN.
DBSCAN (Density-Based Spatial Clustering of Applications with Noise, Ester et al. 1996) defines clusters as regions of high point density separated by regions of low density. It has two parameters: a radius eps and a count minPts. A point with at least minPts neighbors (itself included) within eps is a core point. Points reachable from a core point but not dense themselves are border points. Everything else is noise.
A cluster is the set of points density-connected through chains of core points. The algorithm visits each unvisited point, checks its neighborhood, and if it is core, expands a cluster by breadth-first search over core neighbors. With a spatial index (k-d tree or ball tree), the average cost is around O(n log n) in low dimensions, degrading toward O(n2) in high dimensions or with large eps.
k required — the number of clusters falls out of the density structure.-1 rather than forced into a cluster, which also makes DBSCAN a simple anomaly detector.A common rule of thumb is minPts ≥ d + 1, often 2·d for dimension d, with larger values for noisier data. Then pick eps from the knee of the sorted k-distance plot. Always scale features first: eps is a single radius in every direction.
import numpy as np
from sklearn.datasets import make_moons
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import NearestNeighbors
from sklearn.cluster import DBSCAN, HDBSCAN # HDBSCAN is in sklearn >= 1.3
X, _ = make_moons(n_samples=600, noise=0.07, random_state=0)
X = np.vstack([X, np.random.default_rng(0).uniform(-1.5, 2.5, size=(30, 2))])
X = StandardScaler().fit_transform(X)
# k-distance plot data for eps
min_pts = 5
dist, _ = NearestNeighbors(n_neighbors=min_pts).fit(X).kneighbors(X)
kdist = np.sort(dist[:, -1])
print("candidate eps (95th pct):", np.percentile(kdist, 95).round(3))
db = DBSCAN(eps=0.3, min_samples=min_pts).fit(X)
labels = db.labels_
print("clusters:", len(set(labels)) - (-1 in labels), "noise:", (labels == -1).sum())
# HDBSCAN: no eps, handles varying densities
hdb = HDBSCAN(min_cluster_size=15).fit(X)
print("HDBSCAN clusters:", labels.max() + 1, "->", hdb.labels_.max() + 1)eps cannot fit both a tight cluster and a diffuse one. HDBSCAN builds a hierarchy over all eps values and extracts the most stable clusters, needing only min_cluster_size. It is usually the better default today. OPTICS is a related ordering-based approach.predict for new points in scikit-learn's DBSCAN; assign new points to the cluster of their nearest core point within eps yourself, or use HDBSCAN's approximate predict in the standalone hdbscan package.eps on big data can materialize huge neighbor lists.Take eight points on a line at positions 1, 2, 3, 3.8, 7, 9.9, 10.5 and 11, with eps = 1.0 and minPts = 3 (counting the point itself). Count each point's neighbourhood within distance 1.0:
The result is two clusters, {A, B, C, D} and {F, G, H}, plus one noise point. Notice what changes with the parameters: with eps = 0.7, B and C would no longer be core and the left group would dissolve into noise; with minPts = 2, every point with any neighbour becomes core, and E would remain noise only because it has no neighbour at all. This sensitivity is why the k-distance plot and a small grid search are worth the effort.
HDBSCAN (Campello, Moulavi & Sander, 2013; with the widely used implementation by McInnes, Healy & Astels, 2017) runs DBSCAN conceptually at every possible eps at once. It first computes a core distance for each point, the distance to its k-th nearest neighbour, which is small in dense regions and large in sparse ones. It then defines the mutual reachability distance between two points as the maximum of their two core distances and their actual distance. This pushes sparse points away from everything while leaving dense regions unchanged.
A minimum spanning tree over mutual reachability distances is built, and removing edges from longest to shortest yields a hierarchy of clusters. The tree is condensed by ignoring splits that shed fewer than min_cluster_size points (those points just "fall out" as noise). Finally, clusters are selected by stability, roughly how long a cluster persists across density levels, weighted by its size. The output includes labels, per-point membership probabilities and outlier scores (GLOSH), which are more informative than DBSCAN's hard labels.
The practical difference: one global density threshold is replaced by a search over all of them, so a tight cluster and a diffuse cluster can both be found in the same run. The main parameter, min_cluster_size, has a direct meaning ("the smallest group I care about"), and min_samples controls how conservative the noise labelling is.
| Method | Needs k | Shapes | Noise handling | Scales to |
|---|---|---|---|---|
| K-Means | Yes | Convex, similar size | None; outliers pull centroids | Millions of points (mini-batch) |
| Gaussian mixture | Yes | Ellipses | Low likelihood can flag outliers | Moderate |
| DBSCAN | No | Arbitrary | Explicit noise label | Large in low dimensions with an index |
| HDBSCAN | No | Arbitrary, varying density | Noise plus outlier scores | Large in low to moderate dimensions |
| Agglomerative | Cut level | Depends on linkage | Single linkage chains through noise | Tens of thousands (quadratic memory) |
DBSCAN was designed for spatial databases and remains a natural fit for geographic data: grouping GPS pings into stops and places, finding hotspots of incidents, or clustering delivery locations. Use the haversine metric on latitude and longitude in radians, where eps is then an angle (kilometres divided by the Earth's radius, about 6371 km). Other common uses include grouping log or alert events, detecting dense regions in point clouds from lidar (see perception and SLAM), and clustering text or image embeddings after dimensionality reduction.
Evaluation without labels needs care. Silhouette score assumes compact convex clusters and penalises exactly the shapes DBSCAN is good at, and it is undefined for noise points, which must be excluded. Density-based validity indices such as DBCV are a better match. Always report the noise fraction alongside the cluster count: a configuration that labels 60% of the data as noise may score well internally and still be useless. Check stability by perturbing eps by about 10% in each direction; if the cluster count swings wildly, the structure is fragile.
For production, fix the preprocessing (scaler parameters, reduction model) together with the clustering parameters, because a re-fitted scaler silently changes what eps means. Cluster IDs are arbitrary and change between runs, so match clusters across refits by overlap or centroid distance before reporting trends.
Further reading: Ester, Kriegel, Sander & Xu, "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise" (KDD 1996); Schubert et al., "DBSCAN Revisited, Revisited" (ACM TODS, 2017); Ankerst et al., "OPTICS" (1999); Campello, Moulavi & Sander, "Density-Based Clustering Based on Hierarchical Density Estimates" (2013); McInnes, Healy & Astels, "hdbscan: Hierarchical density based clustering" (JOSS, 2017).