DBSCAN

KMeans can only cut out "round" clusters — DBSCAN expands through density, finding moon shapes, rings, and anything in between

01 Core Concept (Plain English)

Imagine looking at a city at night from above. The city center blazes with light, the suburbs are sparse, and out in the countryside there are just a few isolated lights.

DBSCAN's logic: dense regions form a "cluster." Start from any bright spot in a dense area, expand along connected dense regions until you reach the edge. Isolated lights are noise — they don't belong to any cluster.

Only two parameters: ε (neighborhood radius) and MinPts (minimum neighbor count). No need to specify the number of clusters in advance.

Three Types of Points

●
Core point

Has at least MinPts points (including itself) within its ε-neighborhood. Forms the "center" of a dense region.

●
Border point

Not a core point itself, but falls within the ε-neighborhood of a core point. Lives on the edge of a cluster.

●
Noise point

Neither a core point nor in any core point's neighborhood. Discarded — not assigned to any cluster.

Step 1: The ε-neighborhood

All points within radius ε of a given point form its neighborhood:

Step 2: Classify the three point types

Label each point based on its neighbor count (ε=1.2, MinPts=3):

Step 3: BFS expansion to form clusters

From each unvisited core point, BFS-expand through all density-reachable points until no more can be added:

Step 4: DBSCAN vs KMeans — moon-shaped data

KMeans splits the moons in half; DBSCAN follows the density boundary naturally:

How to choose ε? A common method: for each point compute the distance to its k-th nearest neighbor (k = MinPts), sort these distances, and look for the "elbow" — that's your ε. MinPts is typically 2× the number of dimensions, minimum 3.

02 Code

Change DATASET (moons/rings/blobs), EPS, and MIN_PTS to explore different results.

03 Deep Dive

Time Complexity

Naïve implementation O(n²) — computing all pairwise distances. With KD-Tree or Ball-Tree for neighborhood queries: O(n log n). sklearn uses Ball-Tree by default.

Density Reachability and Connectivity

  • Directly density-reachable: q is within core point p's ε-neighborhood
  • Density-reachable: there exists a chain of core points p₁→p₂→…→pₙ where each step is directly density-reachable
  • Density-connected: two points are both density-reachable from the same core point — this defines a single cluster

DBSCAN vs KMeans

Prefer DBSCAN

Clusters have arbitrary shapes, data contains noise/outliers, or the number of clusters is unknown. Typical use cases: geospatial clustering, anomaly detection.

Prefer KMeans

Clusters are roughly spherical, the number of clusters is known, and speed matters. KMeans is O(nkT), much faster than DBSCAN.

DBSCAN limitations

Sensitive to ε and MinPts — bad choices give bad results. Struggles with clusters of varying density (use HDBSCAN instead).

High dimensions

The curse of dimensionality makes distances converge, making ε hard to set. Usually dimension-reduce first (e.g. PCA), then cluster.