DBSCAN Density Clustering

k-Means and Hierarchical Clustering both assign every point to a cluster. DBSCAN's founding move is refusing to: it asks whether a point lives in a dense region at all, and answers 'noise' when it does not. That single refusal is why DBSCAN finds arbitrarily shaped clusters and why its parameter names — eps, min_samples — read like a definition of density rather than a count of groups.

Two parameters, one definition each:

• The eps-neighborhood of p, N_eps(p), is every point within distance eps of p (DBSCAN's default metric is Euclidean, so eps is a radius).
• p is a core point if |N_eps(p)| >= min_samples — at least that many points (p included) live inside its eps-ball.

From there the labels fall out mechanically:

A cluster is then the maximal set of points that are density-connected: point q is density-reachable from core point p if a chain of core points links them, each within eps of the next. Border points get attached to whichever core region touches them first; noise points are density-reachable from nothing.

Trace it on a twelve-point grid with eps = 1.5 and min_samples = 3. Point p2 at (2, 2) has neighbors p1 (1, 2), p3 (3, 2), and p4 (2, 3) — four points including itself — so p2 is core, and p1/p3/p4 are at least border. Suppose p2–p3–p7 form a chain of core points, and p9 sits 1.2 from core point p7 but has only itself plus p7 in its eps-ball. p9 is border: attached to the cluster, but it could never have started or propagated one. Meanwhile p12 at (14, 14) has no neighbor within 1.5 and is not near any core point — noise, label -1.

The expansion algorithm mirrors that logic:

from sklearn.cluster import DBSCAN

cl = DBSCAN(eps=1.5, min_samples=3)   # min_samples INCLUDES the point itself
labels = cl.fit_predict(X_scaled)
cl.core_sample_indices_   # which rows were core points
set(labels)               # {0, 1, 2, -1} — note the -1

Two properties come straight from this mechanism and both are interview gold. First, the number of clusters is discovered, not specified — no k anywhere. Second, because cluster membership propagates through dense chains, clusters can be crescents, rings, spirals, or any connected dense shape; the two interleaving moons that k-Means slices in half come out perfectly labeled. The cost of the refusal-to-assign-everything contract: your downstream code must handle the -1 label, and a dataset with no dense regions returns nothing but noise — an answer, not an error.

For a point p, the epsilon-neighborhood contains observations no farther than eps under the selected metric. A point is core when that neighborhood has at least min_samples observations, with the point itself counted by scikit-learn. A border point is not dense enough to be core but lies within eps of a core point. Noise is neither. Core points connected through chains of neighboring core points form a density-connected cluster; border points can attach to such a cluster without joining the chain. This distinction explains why two border points near the same edge do not necessarily connect separate clusters. Use a small hand-checkable dataset to confirm how your library counts the point itself and handles metric settings.

DBSCAN has no k, but it has two knobs that determine everything, and choosing them is the skill the interview probes. The workhorse for eps is the k-distance plot, and its logic is worth stating precisely: for every point, compute the distance to its (min_samples - 1)-th nearest neighbor — the k-distance with k = min_samples - 1 — then sort all those distances ascending and plot them.

Why this curve has a knee: points comfortably inside clusters need only a small radius to enclose min_samples neighbors, so most of the sorted curve stays low and flat. Points out in sparse territory — the candidates for noise — have k-distances that blow up. The plot therefore rises gently then turns sharply upward, and the eps at that turning point is the largest radius that still separates 'dense' from 'sparse'.

from sklearn.neighbors import NearestNeighbors
from sklearn.cluster import DBSCAN
import numpy as np

min_samples = 5                      # so the k-distance uses k = 4
nn = NearestNeighbors(n_neighbors=min_samples).fit(X_scaled)
dists, _ = nn.kneighbors(X_scaled)
kdist = np.sort(dists[:, -1])         # distance to the 4th nearest neighbor

# knee by maximum second difference; or use the kneedle library
elbow = int(np.argmax(np.diff(kdist, 2))) + 2

db = DBSCAN(eps=kdist[elbow], min_samples=min_samples)
labels = db.fit_predict(X_scaled)
print(f"eps={kdist[elbow]:.2f}  clusters={len(set(labels)) - 1}  noise={(labels == -1).sum()}")

min_samples is the easier half. Two heuristics cover most cases: min_samples >= d + 1 (below that, in d dimensions almost every point qualifies as core in low-d data, and the notion of density loses meaning — this is the Hinssen bound), and the practical rule of thumb min_samples ≈ 2·d, with 4 as the sklearn-compatible floor for small datasets. Larger min_samples makes 'dense' mean denser: smoother clusters, more noise, more robustness to outliers.

Then the sweep, because one eyeballed knee is a hypothesis. Grid eps against min_samples, and score each run — but DBSCAN's noise label forces care in the metric:

from sklearn.metrics import silhouette_score

good = []
for eps in np.linspace(0.2, 1.2, 21):
    for ms in [4, 6, 8, 10]:
        lab = DBSCAN(eps=eps, min_samples=ms).fit_predict(X_scaled)
        n_clusters = len(set(lab)) - (1 if -1 in lab else 0)
        noise_frac = (lab == -1).mean()
        if n_clusters >= 2 and noise_frac < 0.5:
            s = silhouette_score(X_scaled, lab)   # -1 is treated as a cluster here
            good.append((round(s, 3), round(eps, 2), ms))
print(sorted(good, reverse=True)[:5])

Read the degenerate outcomes as diagnostics on the plot, not as random bad luck. Everything is noise (-1): eps is too small (or min_samples too large) — the knee was above where you cut. One giant cluster: eps is too large, so density never drops below the threshold between groups — the knee was below where you cut. And the whole pipeline depends on one non-negotiable carried over from every distance-based method in this phase: eps lives in the units of your features, so run StandardScaler first, or one unscaled column silently rescales the meaning of every radius you chose.

The k-distance plot is only a heuristic: calculate each point's distance to its min_samples-th nearest neighbor, sort those distances, and look for a change in slope. A flat section followed by a rise can suggest a useful radius, but the curve may have several knees or none. Select the metric before interpreting the plot; changing from Euclidean to Manhattan changes every distance and therefore the scale of eps. Try a narrow range around a plausible knee and compare cluster count, noise fraction, and whether known nearby records stay together. Do not select eps solely to maximize the number of clusters or minimize noise.

DBSCAN's strength — one global eps defines density everywhere — is also its failure mode, and the failure is silent. Consider a dataset with a tight cluster of 800 points in a radius-0.3 ball and a loose but real cluster of 800 points scattered across a radius-2.0 region. No single eps separates them from each other and from noise simultaneously. Set eps for the tight cluster and the loose one dissolves into -1 noise: points that belong somewhere are declared to belong nowhere. Set eps for the loose cluster and the tight one fuses with its neighbors. Density clustering assumes roughly uniform density across clusters; when it is violated, the noise label starts swallowing real structure.

The options, in order of practicality:

The -1 label deserves its own paragraph, because the reflex to df[df.label != -1] throws away DBSCAN's most interesting output. Noise is a claim, not garbage. Three readings of the same -1 set, and you should present at least two of them: (1) genuine anomalies — fraud rings, broken sensors, bot traffic, the exact use case where DBSCAN-as-anomaly-detector is the product; (2) a real but sparse segment — the underserved customer tier too thin to form a dense region; (3) victims of bad parameters or bad scaling, which you rule out by checking whether the noise fraction swings wildly across your eps grid. Profile the noise points against the clustered points before deleting anything — if their mean revenue is 4× the average, they were the story all along.

The degenerate extremes complete the picture. All noise means eps too small or min_samples too large — no point reaches core status, so nothing can propagate. One cluster means eps too large — density never falls between groups, so everything is connected. Label churn across seeds cannot happen (DBSCAN is deterministic given data and parameters, unlike k-Means), which is a nice contrast to bring up unprompted.

The comparison to carry into the interview:

Pick DBSCAN when the shape is unknown, noise is expected, dimensions are modest, and uniform density is plausible. Decline it when density varies sharply across clusters or d is large — and in those cases the honest next step is either HDBSCAN or the internal/stability evaluation you meet in Cluster Evaluation and Profiling.