DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

DBSCAN (density-based spatial clustering of applications with noise) is an unsupervised learning algorithm that groups points packed closely together into clusters and labels points in sparse regions as noise. Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu introduced it at the KDD conference in 1996. It needs no preset number of clusters, follows clusters of any shape, such as rings, crescents, or winding roads, and its noise label doubles as a simple form of anomaly detection. The whole algorithm is controlled by two parameters: a neighborhood radius and the number of points that make a neighborhood dense.

Core Points, Border Points, and Noise#

DBSCAN looks at the neighborhood of every point, the set of points within a distance eps, and counts its members:

• Core point: Has at least min_samples points in its neighborhood, counting itself in scikit-learn's implementation. Core points form the dense interior of a cluster.
• Border point: Has too few neighbors to be a core point but lies within eps of one. Border points form a cluster's edges.
• Noise point: Is neither, so it belongs to no cluster and receives the label -1.

A cluster grows from any unvisited core point. DBSCAN adds every point in its neighborhood, then repeats from each newly added core point until no more points are reachable, so a chain of overlapping dense neighborhoods becomes one cluster however it bends. Border points join a cluster without extending it. The result is deterministic for a given input order, but a border point within reach of two clusters joins whichever cluster reaches it first, so shuffling the data can move border points between clusters.

Choosing eps and min_samples#

The radius eps matters most and depends on the scale of the data, which is why features are usually standardized first. Too small a radius leaves most points as noise, and too large a radius merges neighboring clusters into one. The usual heuristic sorts each point's distance to its k-th nearest neighbor, with k equal to min_samples, and picks eps at the knee of that curve, where distances start to climb steeply. Larger min_samples values make clustering more tolerant of noise and are common on large or noisy datasets. In high-dimensional spaces such as image embeddings, distances between points become similar to one another, so practitioners often apply dimensionality reduction such as principal component analysis (PCA) before running DBSCAN.

DBSCAN vs. K-Means and HDBSCAN#

K-means clustering needs the number of clusters in advance, assigns every point to its nearest centroid, and therefore favors compact, round clusters and pulls outliers into some group. DBSCAN discovers the number of clusters from density and leaves outliers out. Its weak spot is a single global eps: when clusters have very different densities, no one radius separates the sparse clusters from the noise and the dense clusters from each other. HDBSCAN addresses this by effectively running DBSCAN across all values of eps and keeping the most stable clusters, and both algorithms ship in the scikit-learn clustering module alongside the related OPTICS.

This example clusters two interleaving crescents with 20 added random outliers and scores each result against the true groups with the adjusted Rand index, where 1.0 is a perfect match:

import numpy as np
from sklearn.cluster import DBSCAN, KMeans
from sklearn.datasets import make_moons
from sklearn.metrics import adjusted_rand_score

# Two interleaving crescents plus 20 scattered outliers (true label -1)
X, y = make_moons(n_samples=300, noise=0.05, random_state=0)
rng = np.random.default_rng(0)
X = np.vstack([X, rng.uniform(-1.5, 2.5, size=(20, 2))])
y = np.concatenate([y, np.full(20, -1)])

# DBSCAN infers clusters from density; k-means is told there are 2
db_labels = DBSCAN(eps=0.2, min_samples=5).fit_predict(X)
km_labels = KMeans(n_clusters=2, random_state=0).fit_predict(X)

print(f"DBSCAN: {db_labels.max() + 1} clusters, {(db_labels == -1).sum()} noise points")
print(f"ARI: DBSCAN {adjusted_rand_score(y, db_labels):.2f}, k-means {adjusted_rand_score(y, km_labels):.2f}")

The script prints 2 clusters and 15 noise points for DBSCAN, and adjusted Rand indexes of 0.97 for DBSCAN and 0.20 for k-means. DBSCAN traces both crescents and sets aside the outliers that landed away from them, while k-means cuts across the crescents with a straight boundary even though it was given the correct number of clusters.

Real-World Applications#

• LiDAR perception: Autonomous vehicle and robotics pipelines remove ground points from a LiDAR scan and then cluster the remaining 3D points into separate obstacles, with density-based clustering as a common choice because the number of objects is unknown.
• Detection post-processing: The box centers of YOLO26 detections, available as result.boxes.xywh, can be clustered with DBSCAN to find groups of people in a crowd or recurring defect locations on a production line, where isolated detections fall out as noise.
• Fraud and sensor monitoring: Transactions or readings labeled -1 sit far from every dense group of normal behavior and become candidates for review.
• Geospatial analysis: Delivery and ride-hailing companies cluster GPS points to find frequent stops and pickup hotspots. Scikit-learn's DBSCAN accepts metric="haversine" for latitude and longitude in radians, in which case eps is an angle on the unit sphere, so a 100-meter radius becomes eps = 0.1 / 6371, using the Earth's mean radius of 6,371 km.