DBSCAN

Also known as: Density-based spatial clustering of applications with noise

On this page 7

DBSCAN, short for density-based spatial clustering of applications with noise, is an unsupervised clustering algorithm in machine learning that groups points lying in dense regions and marks points in sparse regions as noise. Introduced in 1996 by Ester, Kriegel, Sander and Xu, it remains one of the most widely used clustering methods in artificial intelligence and data mining.

Unlike centroid-based methods, DBSCAN does not need the number of clusters in advance, finds clusters of arbitrary shape, and treats outliers as a separate category instead of forcing them into a group. Its behavior is governed by only two parameters: a neighborhood radius and a minimum point count.

How DBSCAN grows clusters from dense neighborhoods

DBSCAN builds clusters by connecting points whose neighborhoods are dense enough. For every point, the algorithm counts how many points fall within the radius eps (often written as epsilon). If that count, including the point itself, reaches minPts, the point is a core point and becomes the seed of a cluster.

From each core point, the cluster expands through a chain of neighbors. A point is directly density-reachable from a core point when it lies within eps of it, and density-reachable when a chain of core points links the two. Two points are density-connected when both are reachable from a common core point; a cluster is a maximal set of density-connected points.

The algorithm assigns every point one of three point roles, and these roles explain most of its behavior, including why results can change slightly with the processing order.

Point roleConditionEffect on clustering
Core pointAt least minPts points within epsStarts or extends a cluster
Border pointFewer than minPts neighbors, but within eps of a core pointJoins a cluster without extending it
Noise pointNot within eps of any core pointLeft unassigned, labeled as an outlier
Point roles in DBSCAN

Core points and noise are assigned deterministically, but a border point within eps of core points from two clusters goes to whichever cluster reaches it first. This order dependence affects only border points and is usually minor in practice.

The eps and minPts parameters

The quality of a DBSCAN result depends almost entirely on choosing eps and minPts well. The radius defines what counts as nearby, while minPts defines how many neighbors make a region dense. Both interact with the distance metric and with feature scaling, because eps is measured in the units of the feature space.

ParameterToo smallToo largeCommon heuristic
epsMost points become noiseClusters merge into oneKnee of the sorted k-distance plot
minPtsNoise forms tiny spurious clustersSmall genuine clusters vanishAt least dimensions + 1; often 2 x dimensions
Distance metricNot applicableNot applicableEuclidean for scaled numeric data, cosine for embeddings
Parameter effects and common starting values

The standard tuning procedure is the k-distance plot: for every point, compute the distance to its k-th nearest neighbor with k set to minPts, sort these distances, and look for the sharp bend where they rise steeply. The distance at that bend is a reasonable eps. For two-dimensional data, the original authors suggested minPts of 4; noisy or high-dimensional data usually needs larger values.

How DBSCAN compares with other clustering methods

DBSCAN differs from neighboring methods mainly in how it defines a cluster. k-means clustering defines a cluster by distance to a centroid, hierarchical clustering by a merge tree, and a Gaussian mixture model by a probability distribution, whereas DBSCAN defines it by contiguous density.

MethodNumber of clustersCluster shapeOutlier handling
DBSCANDiscovered automaticallyArbitraryExplicit noise label
k-means clusteringSet in advanceRoughly sphericalEvery point is assigned
Hierarchical clusteringChosen by cutting the treeDepends on linkageNo dedicated outlier class
Gaussian mixture modelSet in advanceEllipticalLow likelihood, not labeled
HDBSCANDiscovered automaticallyArbitrary, varying densityExplicit noise with membership scores
DBSCAN and related clustering approaches

OPTICS and HDBSCAN extend the idea to datasets where density varies between clusters. OPTICS produces a reachability ordering that can be cut at several density levels, while HDBSCAN builds a density hierarchy and keeps the most stable clusters, which removes the need to pick a single eps.

Computational cost and implementation

The cost of DBSCAN is dominated by neighborhood queries, one for each point. With a spatial index such as a k-d tree or ball tree, average complexity is close to O(n log n) on low-dimensional data. Without an index, or when the index degrades in high dimensions, the worst case is O(n squared) in time.

Memory use depends on the implementation. Some libraries precompute all neighborhoods, which can require large amounts of memory when eps is generous and the data are dense. Approximate nearest-neighbor indexes and grid-based variants reduce the cost for millions of points, at the price of slightly different cluster boundaries.

When DBSCAN works well and where it fails

DBSCAN performs best on low-dimensional data with clear density gaps, such as geographic coordinates, sensor readings or reduced embeddings. It struggles when clusters have very different densities, because a single eps cannot fit both a tight cluster and a diffuse one.

SymptomLikely causeRemedy
One giant clustereps too large or unscaled featuresStandardize features, lower eps
Almost everything is noiseeps too small or minPts too highRecheck the k-distance plot
Dense and sparse clusters both failVarying density across clustersSwitch to HDBSCAN or OPTICS
Meaningless clusters in many dimensionsCurse of dimensionality flattens distancesApply PCA or UMAP first
Typical problems, causes and remedies

A common misconception is that DBSCAN is parameter-free. It removes the need to choose the number of clusters, but the eps choice is often harder than choosing k, and in high-dimensional spaces distances concentrate so strongly that no eps separates the data well. Practitioners therefore apply dimensionality reduction before clustering text or image embeddings.

The simple explanation

Imagine looking down at a park from a high window. People who stand close together in groups form crowds, and a few people wander alone. DBSCAN finds the crowds by checking, for each person, how many others stand within a few steps.

If enough people are nearby, that spot belongs to a crowd, and the crowd grows as long as the chain of close neighbors continues. People standing alone are simply labeled as loners. The key idea is that groups are defined by closeness, not by a number you decide beforehand, so the method can find a long winding queue as easily as a round huddle.

How it is used in practice

A ride-hailing analytics team wants to find where passengers actually wait for pickups across a city. It collects about 500,000 GPS pickup points from one month and runs DBSCAN with the haversine distance, an eps equal to roughly 50 meters and minPts set to 20, using a ball tree index.

The algorithm returns several hundred pickup hotspots, including long, curved clusters along station entrances that k-means would have split into circles. Roughly 8 percent of points are labeled as noise, mostly isolated pickups and GPS errors. The team uses the hotspot centers to place recommended pickup zones in the app, which shortens average driver search time and removes the noisy points from the planning data.