DBSCAN: Finding Clusters of Any Shape by Density, Not Distance

A clustering algorithm that doesn't need to know k

K-means asks you to decide, before you've looked closely at the data, how many clusters exist. Hierarchical clustering defers that decision but still assumes clusters look roughly like blobs that merge sensibly as you climb a tree. DBSCAN (Density-Based Spatial Clustering of Applications with Noise) starts from a different premise entirely: a cluster is a region where points are packed closely together, separated from other regions by areas of low density. You never tell it how many groups to find. Instead you tell it how close points need to be to count as neighbours, and how many neighbours a point needs to be considered part of a crowd rather than sitting alone.

This matters more than it sounds. Take a dataset of customers described by income and spending, the kind of table used in customer personality analysis for retail and marketing teams. Run k-means on it and you get exactly the number of round, similarly sized groups you asked for, whether or not that structure is real. Some customers, though, don't belong to any coherent group at all: a handful of extremely high spenders, or a few rows with implausible values that survived cleaning. K-means is forced to assign every single one of them to whichever centroid happens to be nearest, which quietly drags that centroid toward the outlier and distorts the cluster it's supposed to represent. DBSCAN instead labels those points as noise, an explicit "does not belong anywhere" category, and leaves the real clusters alone.

How the algorithm actually walks through the data

DBSCAN classifies every point into one of three roles, using two parameters: eps, a radius, and min_samples, a minimum neighbour count.

• Core point: has at least min_samples other points within distance eps of it (including itself, depending on the implementation's convention). Core points are the interior of a cluster.
• Border point: doesn't have enough neighbours to be a core point itself, but falls within eps of a core point. It joins that core point's cluster but isn't a hub of its own.
• Noise point: neither a core point nor within eps of one. It gets no cluster label at all — in scikit-learn's output this shows up as label -1.

The algorithm builds clusters by picking an unvisited core point, collecting every point within eps of it, and then recursively expanding to any core points among those neighbours, absorbing their neighbourhoods too. This is why DBSCAN can trace out clusters shaped like crescents, spirals or elongated arcs: it's chaining together local neighbourhoods rather than measuring distance to a single fixed centre. Two points can end up in the same cluster even if they're far apart in straight-line distance, as long as there's an unbroken trail of dense neighbourhoods connecting them. K-means, which partitions space into convex Voronoi cells around centroids, structurally cannot do this — an elongated or curved group of points will always get sliced into pieces or merged with a neighbouring group.

The trade-off is that DBSCAN struggles when clusters have very different densities. A radius that correctly separates a dense cluster from the background will often swallow a sparser cluster whole, or shatter it into fragments and noise, because one fixed eps can't be simultaneously right for two different densities.

Choosing eps with a k-distance plot

Picking min_samples is the easier of the two decisions — a common rule of thumb is to set it to at least the number of dimensions in the data plus one, and to raise it for noisier or larger datasets. Picking eps is harder, and guessing it by trial and error wastes time. The standard technique is the k-distance plot:

1. For every point, compute the distance to its k-th nearest neighbour, where k equals your chosen min_samples.
2. Sort these distances in ascending order and plot them.
3. Look for the "elbow" — the point where the curve suddenly bends upward.

Most points sit in dense regions, so their k-th nearest neighbour is close and the sorted distances stay low and flat for a long stretch. Once you reach the sparser points and eventual outliers, the k-th nearest neighbour distance jumps sharply, because there simply isn't a crowd nearby. The elbow marks the natural boundary between "dense enough to be a cluster" and "too sparse, must be noise," and reading the y-value at that elbow gives a principled value for eps. This is a diagnostic plot, not an automatic answer — on real data the elbow is often a gentle curve rather than a sharp corner, and it's reasonable to test eps values from just below and just above the visual bend and compare the resulting cluster counts and silhouette scores.

Reading the output: clusters, noise, and what changes with scaling

Because DBSCAN measures distance directly, feature scaling changes its behaviour just as much as it changes k-means. On unscaled customer data, a feature like income (ranging over tens of thousands) will dominate the neighbourhood radius, while a feature like number of children (ranging from 0 to a handful) becomes nearly invisible. Standardising features first — so each one contributes comparably to the distance calculation — is close to mandatory before searching for eps, and the k-distance plot should always be built on the same scaled data that will go into the final fit.

Once fitted, DBSCAN's output is a set of cluster labels alongside a noise label. Two things are worth checking before trusting the result. First, how many points ended up as noise — if it's a tiny handful, they're plausibly genuine outliers worth investigating individually (in a marketing context, these are often either extremely high-value customers who don't fit the mould of any segment, or corrupted rows that slipped through cleaning). If it's a large fraction of the dataset, eps is probably too small and is treating normal variation as noise. Second, how many clusters were found and whether their sizes are reasonable — DBSCAN can happily return two clusters where you expected four, because it found only two genuinely dense regions and everything else was, in density terms, background.

Silhouette score still applies to whatever points DBSCAN did assign to a cluster (excluding noise), and it's a fair way to compare a DBSCAN result against a k-means or hierarchical result on the same standardised data. But the comparison should be read with the different objectives in mind: k-means is explicitly optimising for round, compact clusters and will often report a higher silhouette score for that reason alone, while DBSCAN is optimising for density-connectivity and reporting a lower score even on a segmentation that is, for a marketing team's purposes, more honest about which customers don't cleanly fit anywhere.

When density-based clustering earns its complexity

DBSCAN is not a universal replacement for k-means; it's a different tool for a different assumption about what a cluster is. It tends to win in three situations. When clusters are not roughly spherical — geographic clustering of delivery addresses, GPS trajectories, or any data where a group can be long and curved rather than round. When outliers are expected and their exclusion matters — fraud and anomaly detection workflows often run DBSCAN specifically because the noise label is the whole point, not a side effect. And when the true number of groups is genuinely unknown and shouldn't be forced by an analyst's guess, which is common in early-stage exploratory segmentation before a business has settled on how many customer archetypes it wants to design around.

It loses ground when clusters have noticeably different densities, when the dataset is very high-dimensional (distance becomes less meaningful as dimensions grow, a problem it shares with k-means but can't route around as gracefully), and when eps needs to be re-tuned every time new data arrives, which makes it less convenient than k-means for a segmentation that has to run automatically and repeatedly in a pipeline. In practice, teams doing serious segmentation work often run k-means, hierarchical clustering, and DBSCAN side by side on the same standardised, outlier-checked dataset, compare silhouette scores and cluster profiles, and pick whichever one produces groups that are both statistically coherent and make sense to the people who have to act on them.