skip to content

DBSCAN and HDBSCAN

3 roadmaps3 questions

Core, border and noise points defined by eps and minPts let DBSCAN find arbitrary shapes and refuse to cluster junk; HDBSCAN drops the single eps. Interviewers ask how you choose eps.

on this pageshow

explore

questions

3

In DBSCAN, what makes a point a core, border, or noise point?

level: juniorimportance: must knowfreq 68%

answer

  1. Two parameters, three labels
  2. Count neighbours inside a radius
  3. A threshold on that count
  4. Reachability from a dense point decides the rest

basics

~20 s

DBSCAN calls a point core when at least minPts points lie within radius eps of it. A non-core point that sits inside some core point's eps-radius is a border point. Anything else is noise and gets no cluster.

solid answer

~50 s

DBSCAN has two parameters: a radius `eps` and a count `minPts`. For every point you count how many points fall within `eps` of it. If that count reaches `minPts`, the point is a **core point** — it sits inside a dense region. A point that misses the threshold but still lies within `eps` of some core point is a **border point**: it joins that core point's cluster but cannot be used to grow the cluster further. A point that is neither is **noise**, and DBSCAN leaves it unassigned. Clusters are then the maximal groups of core points chained together through each other's neighbourhoods, plus the border points hanging off them. That chaining is why DBSCAN needs no cluster count and can trace a cluster of any shape — taxi pickups strung along a curved waterfront come out as one hotspot rather than being cut into round blobs.

code

python · 19 lines
python
import math

pts = [(0, 0), (0.4, 0.1), (0.2, 0.5), (0.8, 0.3),
       (-0.9, 0.2), (5.0, 5.0), (2.6, 2.6)]
eps, min_pts = 1.0, 3  # min_pts counts the point itself

def nbrs(i):
    return [j for j, q in enumerate(pts) if math.dist(pts[i], q) <= eps]

core = {i for i in range(len(pts)) if len(nbrs(i)) >= min_pts}

for i, p in enumerate(pts):
    if i in core:
        label = 'core'
    elif any(j in core for j in nbrs(i)):
        label = 'border'
    else:
        label = 'noise'
    print(p, len(nbrs(i)), label)

go deeper

for a junior

Be ready to name the two parameters and say which is a distance and which is a count, then define core, border and noise in one sentence each. Say plainly that DBSCAN is not told how many clusters to find.

for a middle

Explain the reachability chain: only core points extend a cluster, border points attach without extending, and a cluster is the maximal density-connected set. Then say what changes when you move eps up or minPts up.

for a senior

Show you know where the labels bite in practice: noise is a deliverable you have to act on, border assignment is order-dependent, and eps is meaningless until features are on a comparable scale. Tie the label counts back to a decision someone downstream makes.

for a principal

Own the framing question of whether a hard partition with an explicit noise bucket is the right output at all for the problem, versus a soft or hierarchical assignment. Argue the operational cost of a label that shifts run to run for points on cluster rims.

## The setup DBSCAN — Density-Based Spatial Clustering of Applications with Noise — clusters points by asking a purely local question of each one: *is it crowded around here?* It never computes a cluster centre, never assumes a cluster is round, and never asks you how many clusters exist. It asks you for two numbers instead. - **eps** (often written as the Greek epsilon) is a **distance**: the radius of the neighbourhood drawn around each point. - **minPts** is a **count**: how many points must fall inside that radius for the region to count as dense. The *eps-neighbourhood* of a point is the set of all points whose distance to it is at most `eps`. Everything below is a statement about the size of that set. ## The three labels **Core point.** A point whose eps-neighbourhood contains at least `minPts` points. It sits in the interior of a dense region. Conventions differ on whether the point itself counts toward the total — the original formulation includes it — so when you quote a `minPts` value in an interview, say which convention you are using. Core points are the only points that can *grow* a cluster. **Border point.** A point that fails the core test (fewer than `minPts` neighbours within `eps`) but lies within `eps` of at least one core point. It is on the rim of a dense region: close enough to belong, not dense enough to extend. Think of pickups on the outer edge of a taxi hotspot — clearly part of it, but the crowd thins out there. **Noise point.** A point that is neither core nor within `eps` of any core point. DBSCAN gives it no cluster at all. This is one of the algorithm's defining features: noise is a **first-class output**, not a failure. A lone pickup on a road shoulder between two hotspots is genuinely not part of either. ## How labels become clusters The glue is *reachability*. Point B is **directly density-reachable** from point A if A is a core point and B is inside A's eps-neighbourhood. B is **density-reachable** from A if you can walk from A to B through a chain of such steps, where every point in the chain except possibly the last is core. Two points are **density-connected** if some core point reaches both. A DBSCAN cluster is a maximal set of density-connected points. The practical consequence is the shape freedom. Because a cluster grows by hopping from core point to core point, its outline is whatever the dense region's outline happens to be. Two interlocking crescents stay two crescents; concentric rings stay separate rings — neither is recoverable by a method that assigns each point to the nearest of k centres, because such a method carves space into straight-edged, convex pieces and the crescent's own centre lies outside the crescent. ## Consequences worth knowing **Border points are the one soft spot.** A border point can sit within `eps` of core points belonging to two different clusters. It is density-reachable from both, but it can only be labelled once, so the classic algorithm gives it to whichever cluster reaches it first. Shuffle the input rows and that assignment can flip. Core-point and noise labels are stable; only border assignment is order-dependent. **The two parameters push in opposite directions.** Raising `eps` with `minPts` fixed enlarges every neighbourhood: more points clear the core test, clusters swell and eventually merge, and the noise count falls. Raising `minPts` with `eps` fixed makes the density test stricter: fewer core points, clusters shrink or split at their thin parts, and the noise count rises. Setting `minPts` to 1 degenerates the algorithm entirely — every point is core and every point is its own cluster. **eps is measured in the units of your feature space.** If one column runs in the thousands and another in the tenths, the large column dominates the distance and `eps` effectively measures only that column. Scale features before you begin. **Density must be roughly comparable across clusters.** One global `eps` and one global `minPts` encode a single notion of "dense enough". When one region is much tighter than another, no single pair of values serves both — that is DBSCAN's best-known limitation and the reason density-based hierarchies exist. ## What an interviewer is checking That you can state the two parameters and say which is a distance and which is a count; that you know noise is a deliberate label rather than a bug; that you do not confuse `minPts` with a number of clusters; and that you can explain, without hand-waving, why chaining through core points is what buys arbitrary cluster shapes.

  • Why can DBSCAN recover two interlocking crescent-shaped clusters when a centroid-based method cannot?
    Because a DBSCAN cluster grows by hopping from core point to core point through overlapping neighbourhoods, so its outline is just the outline of the dense region. A method that assigns each point to the nearest of k centres cuts space into convex pieces, and a crescent's own centre lies outside the crescent, so the two crescents get sliced across each other instead of separated.
  • Can the same border point end up in a different cluster if you shuffle the input rows?
    Yes. A border point can lie within eps of core points from two different clusters, and it can carry only one label, so the classic algorithm awards it to whichever cluster expands to it first — which depends on processing order. Core points and noise points are unaffected: those labels follow only from neighbourhood counts, so they are stable across runs.
  • What happens to the labels if you raise minPts and leave eps unchanged?
    The density test gets stricter, so fewer points clear the core threshold. Clusters shrink, thin low-density bridges between them break, some small clusters disappear entirely, and the share of points labelled noise rises. It is the usual knob for smoothing away spurious micro-clusters, at the cost of discarding genuinely sparse structure.

Picture taxi pickups dropped on a city map. A pickup surrounded by many others is deep inside a hotspot, one on the hotspot's fading rim still belongs to it, and a single fare on an empty road shoulder belongs to nothing at all.

saying these in an interview costs you the question

  • Says DBSCAN needs the number of clusters up front
  • Swaps the parameters: calls eps a count and minPts a distance
  • Treats noise points as errors to delete rather than a label
  • Claims every point ends up assigned to some cluster
  • Says border points can grow a cluster the same way core points do
  • Assumes DBSCAN clusters are round because a distance is involved

context

resolving links…

open as a page

How do you choose DBSCAN's eps parameter from a sorted k-distance curve?

level: middleimportance: should knowfreq 52%

basics

~20 s

Compute every point's distance to its minPts-th nearest neighbour, sort those distances, and plot them. The curve stays flat where points have close neighbours and turns sharply upward where they do not. Set eps at that knee.

open as a page

A dense core and a diffuse halo break DBSCAN's single eps — how does HDBSCAN fix that?

level: seniorimportance: nice to knowfreq 34%

basics

~20 s

One global eps encodes a single notion of dense, so it cannot be tight enough for a core and loose enough for a halo. HDBSCAN sweeps all radii instead and keeps the clusters that persist longest.

open as a page