When would you use DBSCAN instead of k-means, and what are its main limitations?

How to think about it

The crisp answer

Use DBSCAN, short for Density-Based Spatial Clustering of Applications with Noise, when clusters have irregular shapes, the number of clusters is unknown, or sparse observations should be flagged as noise instead of forced into a group. Prefer k-means, a centroid-based method that assigns points to a chosen number of groups, when clusters are compact, roughly convex, and every point needs an assignment.

Why DBSCAN differs from k-means

The interviewer is usually testing whether you understand the geometry, not whether you can recite a list of algorithms.

K-means chooses k centroids and assigns every observation to its nearest centroid. It then moves each centroid to the mean of its assigned observations and repeats until the assignments stop changing. Its objective is to minimise the total squared distance from each point to its assigned centroid, written as sum of squared distances.

That creates a particular kind of partition. The boundary between two centroids is a straight dividing line, so k-means tends to produce compact, convex groups. It also has two consequences that matter in production:

• You must choose k before fitting the model.
• Every point belongs to some cluster, even a bizarre outlier 100 kilometres from the rest of the data.

An outlier can also pull a centroid toward itself because the mean is sensitive to extreme values.

DBSCAN takes a different view. It does not ask, “Which centre is this point closest to?” It asks, “Does this point live in a sufficiently crowded neighbourhood?” Density here means the number of nearby observations per unit of space. A dense region can bend, wrap around another region, or contain holes without violating DBSCAN’s definition of a cluster.

That is why DBSCAN can separate two crescent-shaped groups that k-means would slice with a straight boundary. It also discovers the number of groups as it explores the data rather than requiring k in advance.

How DBSCAN forms a cluster

DBSCAN has two main parameters:

• eps, pronounced “epsilon”, is the radius of the neighbourhood examined around each point.
• minPts, often called min_samples in libraries, is the minimum number of observations that must be in that neighbourhood for the point to count as dense.

Suppose eps is 150 metres and minPts is 12. A point is a core point if its 150-metre neighbourhood contains at least 12 observations, normally including the point itself. A border point is not dense enough to be core, but lies within the neighbourhood of a core point. A noise point is neither.

DBSCAN starts with a core point and expands its cluster. Any nearby core points join the same cluster, and their neighbours are examined too. This continues through a chain of connected core points. Border points are attached to the cluster, but they do not cause further expansion.

That last detail is important. A sparse line of border points does not connect two groups. A line of core points does. If a thin bridge contains enough observations to make its points core points, DBSCAN may merge two groups that a human would regard as separate.

DBSCAN has no centroids. The integer labels it returns, such as 0 and 1, are just IDs. They do not mean “better” and “worse”, and the numbering can change between runs or implementations. Noise is commonly represented by label -1.

A concrete example

Imagine 2,000 GPS pings from delivery vehicles in a city. Most pings form two curved, crescent-shaped service zones around different road systems. Thirty pings come from faulty GPS readings near an airport. The number of zones is not known beforehand, and the airport points should not become a third delivery zone.

Assume the latitude and longitude have first been converted into local projected coordinates, with both axes measured in kilometres. A plausible starting configuration might be:

from sklearn.cluster import DBSCAN

# X_km contains x and y coordinates, measured in kilometres
labels = DBSCAN(
    eps=0.15,
    min_samples=12
).fit_predict(X_km)

cluster_count = len(set(labels)) - (1 if -1 in labels else 0)
noise_count = int((labels == -1).sum())

Here, eps=0.15 means 150 metres in this particular coordinate system. It does not mean 0.15 in every dataset. If the coordinates were standardised first, the same number would mean 0.15 standard deviations in the scaled feature space.

With suitable parameters, DBSCAN could return two cluster IDs and label the isolated airport pings -1. It can follow each curved service zone because the zone is connected by a sequence of nearby core points.

K-means would need k=2. It would still assign the airport errors to one of the two clusters, and its centroid-based boundaries could cut across the crescents. It is not “wrong” mathematically; it is solving a different problem.

Choosing eps and minPts

Parameter choice is DBSCAN’s first practical difficulty.

A useful diagnostic is a k-distance plot. For each point, calculate the distance to its minPts-th nearest neighbour, sort those distances, and plot them. Dense-cluster points tend to have small values. Noise and sparse-region points tend to have larger values. A sharp bend in the sorted curve gives a candidate eps.

For example, suppose the 12th-neighbour distances for the dense GPS zones range from 0.04 to 0.09 kilometres, while the isolated readings begin around 0.35 kilometres. A bend near 0.15 kilometres would be a reasonable place to start. It is a diagnostic, not a law of nature.

Then inspect the result against the business problem:

• If eps is too small, many observations become noise and genuine groups break into tiny fragments.
• If eps is too large, nearby groups merge and almost nothing is labelled noise.
• If minPts is too high, smaller legitimate groups disappear.
• If minPts is too low, a handful of accidental nearby points can create fake clusters.

Always scale numeric features when their units differ. A feature measured in dollars can overwhelm one measured in counts simply because its numerical values are larger. For geographic data, do not casually apply Euclidean distance to raw latitude and longitude over a large area. Use an appropriate projection or a geographic distance metric.

The limitations and the senior-level nuance

The biggest limitation is that ordinary DBSCAN uses one global eps and one global density threshold.

Suppose one genuine cluster contains points every 20 metres in a city centre, while another contains points every 200 metres in a suburb. An eps large enough to retain the suburban group may merge several downtown groups. An eps small enough to separate downtown groups may label the suburb as noise. HDBSCAN or OPTICS can be better candidates when density changes substantially, but neither removes the need to validate the resulting clusters.

DBSCAN also becomes less reliable in high-dimensional data. As the number of dimensions grows, distances tend to become more similar: the nearest point is not much nearer than the average point. A fixed radius then stops representing a meaningful notion of neighbourhood. Feature selection, a domain-appropriate distance metric, or a carefully validated representation may help. Blindly projecting to two dimensions and clustering the picture can create a very attractive mistake.

There is also a computational consideration. DBSCAN repeatedly searches for neighbours. Spatial indexes can make this efficient in low-dimensional data, but neighbour searches become expensive as the dataset grows or the dimension increases. Some implementations can require quadratic memory in unfavourable settings, such as a very large radius that makes most points neighbours.

Finally, DBSCAN is awkward when new observations arrive. Standard DBSCAN does not learn a centroid or a simple decision function for out-of-sample prediction. Adding new points can change which old points are core points and can change cluster connectivity. If a production system needs a stable, low-latency assignment for every new event, k-means, a prototype model, or an explicitly designed nearest-core-point policy may be easier to operate.

One more subtlety: a border point that lies within eps of core points from two clusters can be assigned to either cluster, depending on the implementation and processing order. Core-connected clusters are the important stable structure; do not build a critical business rule around the exact label of an ambiguous border point.

Most importantly, DBSCAN’s noise label does not mean “this observation is definitely an anomaly.” It means “this observation is not part of a sufficiently dense region under these parameters.” A rare but valid customer, a GPS glitch, and a small legitimate niche can all receive -1.

What they’ll ask next

“How would you choose eps and minPts?”

I would scale the features and choose a meaningful distance metric first. Then I would use a k-distance plot to identify candidate eps values, try a small sensitivity range, and inspect cluster stability, noise rates, and domain usefulness. I would not select the value from a plot alone.

“What if the clusters have very different densities?”

A single DBSCAN configuration is usually a poor fit. I would consider HDBSCAN or OPTICS, which examine density across multiple scales, and compare the result with domain expectations. I would also check whether the apparent density difference is caused by sampling bias or feature scaling.

“Can DBSCAN classify a new point without retraining?”

Not in the same straightforward way as nearest-centroid assignment. A team can define a policy based on nearby core points, but it must decide what happens near overlapping clusters and whether the original clustering remains fixed. If online assignment is central to the product, that requirement may favour another algorithm.

Say this in the interview

“Use DBSCAN when I need density-based clusters with unknown cluster count, irregular shapes, and explicit noise handling; its trade-offs are parameter sensitivity, difficulty with varying densities and high-dimensional distances, and no simple native rule for assigning new points.”