DBSCAN density-based clustering

Overview

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is a clustering algorithm that groups points based on local density rather than distance to centroids. Unlike K-means, it can find clusters of arbitrary shape and automatically identifies outliers.

Core Concepts

WHY these three types? This classification captures the intuitive notion that clusters have dense centers (cores), fuzy boundaries (borders), and isolated points don't belong anywhere (noise).

Algorithm Derivation from First Principles

Starting Question: How do we formalize "points packed together"?

Step 1: Define Local Density For any point $p$, define its ε-neighborhood: $N_\varepsilon(p) = \{q \in D : \text{dist}(p,q) \leq \varepsilon\}$

WHY this definition? We need a local measure. Looking at all pairwise distances (global) would miss that clusters can have different densities in different regions.

Step 2: Identify Dense Regions A point $p$ is a core point if: $|N_\varepsilon(p)| \geq \text{MinPts}$

WHY MinPts? A single neighbor isn't enough—noise could have one nearby point by chance. MinPts creates a threshold that distinguishes "coincidentally close" from "genuinely dense." Typical choice: MinPts ≥ dimensionality + 1.

Step 3: Define Connectivity Point $p$ is directly density-reachable from $q$ if:

• $q$ is a core point
• $p \in N_\varepsilon(q)$

WHY one-directional? A border point can be reached from a core, but the core isn't reachable from the border (it lacks enough neighbors). This asymetry is crucial.

Point $p$ is density-reachable from $q$ if there's a chain: $q = p_1, p_2, \ldots, p_n = p$ where each $p_{i+1}$ is directly density-reachable from $p_i$.

Step 4: Define Cluster Membership Points $p$ and $q$ are density-connected if there exists a core point $o$ such that both are density-reachable from $o$.

A cluster $C$ is a maximal set of density-connected points:

1. Connectivity: $\forall p,q \in C$, $p$ and $q$ are density-connected
2. Maximality: If $p \in C$ and $q$ is density-reachable from $p$, then $q \in C$

WHY maximality? Ensures we don't arbitrarily split a connected dense region. The cluster grows as far as density allows.

WHY the tentative noise marking? A point marked noise initially might later be claimed as a border point when a nearby core is discovered. This is why we check "not yet in any cluster" rather than "marked as noise."

Worked Examples

Step-by-step:

1. Process A(1,1):

   • N_ε(A) = {A, B, C, D} (distances: A-B=1, A-C=1, A-D=√2≈1.41)
   • |N_ε(A)| = 4 ≥ 3 → A is CORE
   • Create Cluster 1, add A WHY is D included? dist(A,D) = √((2-1)² + (2-1)²) = √2 ≈ 1.41 < 1.5

2. Expand from A's neighbors:

   • B: N_ε(B) = {A,B,C,D}, |N_ε(B)| = 4 → CORE, add to Cluster 1
   • C: N_ε(C) = {A,B,C,D}, |N_ε(C)| = 4 → CORE, add to Cluster 1
   • D: N_ε(D) = {A,B,C,D}, |N_ε(D)| = 4 → CORE, add to Cluster 1

3. Process E(5,5):

   • N_ε(E) = {E} only (nearest cluster point is D at distance ~5.7)
   • |N_ε(E)| = 1 < 3 → E is NOISE

4. Process F(10,10):

   • N_ε(F) = {F, G} (dist(F,G) = 1)
   • |N_ε(F)| = 2 < 3 → F is NOISE (tentatively)

5. Process G(10,11):

   • N_ε(G) = {F, G}
   • |N_ε(G)| = 2 < 3 → G is NOISE

Result: Cluster 1 = {A,B,C,D}, Noise = {E,F,G}

WHY aren't F and G clustered? Even though they're close to each other, neither has MinPts=3 neighbors. This prevents tiny groups from being called clusters.

K-means result: Forces circular clusters, splits each crescent or merges them badly.

DBSCAN result:

• Core points form along the dense crescent paths
• Border points fill in the edges
• The gap between crescents contains no core points → natural separation

WHY DBSCAN succeds: It follows the density flow. A point one crescent can reach other points along that crescent through chains of dense neighborhoods, but cannot reach the other crescent across the sparse gap. Density-connectivity respects the manifold structure.

Detailed walk for one crescent:

1. Start at any dense point P on the crescent
2. P's ε-ball contains≥5 neighbors along the curve → P is core
3. Those neighbors are also dense (crescent thickness) → they're core too
4. Chain expands along the crescent path via density-reachability
5. At the crescent tips (thinner regions), points have fewer neighbors → become border points
6. Across the gap, evenε-balls from closest points don't overlap → separate cluster

Parameter Selection

Goal: Find the scale where density transitions occur.

Method:

1. For each point, compute distance to its $k$-th nearest neighbor (use $k = \text{MinPts}$)
2. Sort all points by this $k$-distance in ascending order
3. Plot: x-axis = point index (sorted), y-axis = k-distance
4. Look for the "elbow"—where the curve sharply rises

WHY this works:

• Points in clusters have small $k$-distances (dense neighborhoods)
• Noise points have large $k$-distances (sparse neighborhoods)
• The elbow represents the transition: points left of it are in clusters, right of it are outliers
• The $k$-distance at the elbow ≈ good choice for ε

Mathematical intuition: If we think of the k-distance plot as a cumulative distribution of local densities: $F(d) = \frac{|\{p : \text{k-dist}(p) \leq d\}|}{|D|}$

The elbow is where $\frac{dF}{dd}$ changes significantly—a phase transition in density distribution.

HOW to use:

from sklearn.neighbors import NearestNeighbors
k = MinPts
nbrs = NearestNeighbors(n_neighbors=k).fit(X)
distances, indices = nbrs.kneighbors(X)
k_distances = np.sort(distances[:, k-1])
plt.plot(k_distances)
# Look for the "knee" - the point of maximum curvature

WHY MinPts first? Often set MinPts = 2×dimensionality as a rule of thumb. In 2D → MinPts ≥ 4, in 3D → MinPts ≥ 6. This ensures a core point has enough neighbors to define a local region, not just a line.

Complexity Analysis

With spatial indexing (KD-tree, Ball-tree): $O(n \log n)$ average case

• Building tree: $O(n \log n)$
• Range query in balanced tree: $O(\log n + k)$ where $k$ = neighbors found
• For $n$ points: $O(n \log n)$

Worst case remains $O(n^2)$: high dimensions cause tree degradation, or all points are neighbors (ε very large).

Space: $O(n)$ for cluster labels + $O(n)$ for spatial index

WHY does dimension hurt? In high dimensions, distance concentration makes all points roughly equidistant. KD-trees partition space ineffectively when all points are equally "far."

Advantages and Limitations

Advantages:

1. Arbitrary shapes: Follows density contours, handles non-convex clusters
2. Auto-outlier detection: Noise points are natural byproducts
3. No preset K: Doesn't require knowing cluster count beforehand
4. Scale-invariant (within limits): If you scale data and scaleε proportionally, results unchanged

WHY scale matters: Scaling changes distances. If features have vastly different ranges (age in years vs. income in thousands), ε will be dominated by the larger scale. Normalization required.

Limitations:

1. Varying densities: Struggles when clusters have different densities. A singleε can't satisfy both dense and sparse clusters.

   • WHY: Dense cluster needs small ε (or it merges with noise); sparse cluster needs large ε (or it fragments).

2. High dimensions: Curse of dimensionality—distances become meaningless, density concept breaks down.

   • WHY: In high-d, volume grows exponentially with radius. An ε-ball that captures local neighbors in 2D becomes a vast hyperspace in 100D.

3. Parameter sensitivity: Results can change dramatically with small ε/MinPts changes.

   • WHY: ε defines the scale of "local." Too small → everything is noise. Too large → everything is one cluster.

Why it feels right: "The algorithm should figure it out."

WHY this fails: ε = 0.5 means almost nothing in the income dimension (where distances are ~100,000) but is huge in the age dimension (where distances are ~60). The income dimension dominates, effectively making clustering1D.

FIX: Standardize features to zero mean, unit variance before DBSCAN: $X_{\text{scaled}} = \frac{X - \mu}{\sigma}$ Now ε has consistent meaning across dimensions.

Steel-man: "DBSCAN handles arbitrary shapes, so it should handle different densities too."

WHY this fails: Density-based connectivity requires a single density threshold (MinPts in ε-ball).

• If ε is tuned for the dense cluster → sparse cluster fragments into noise
• If ε is tuned for the sparse cluster → dense cluster stays intact, but noise points in between get incorrectly absorbed

FIX: Use HDBSCAN (Hierarchical DBSCAN), which builds a hierarchy of clusterings at different density levels and extracts stable clusters. Or, manually apply DBSCAN to subregions with different parameters.

Steel-man: "They're on the edge, so maybe they don't really belong."

WHY this is wrong: Border points do belong to their cluster—they're within ε of a core point. They're called "border" because they're not dense enough to be cores themselves, but they're definitively assigned.

Contrast with K-means: In K-means, points equidistant from two centroids are genuinely uncertain. In DBSCAN, border points are only reachable from one cluster's cores (unless you're exactly on a boundary between two dense regions, which is measure-zero rare).

FIX: Trust the assignment. Border points are full cluster members.

Connections

• K-means Clustering: DBSCAN vs. K-means: arbitrary shapes vs. convex, no K vs. fixed K, handles noise vs. assigns all points
• Hierarchical Clustering: HDBSCAN extends DBSCAN with hierarchy; dendrogram shows density levels
• Gaussian Mixture Models: GMM assumes density is mixture of Gaussians; DBSCAN is non-parametric about density shape
• KD-Trees and Spatial Indexing: Required for efficientε-neighborhood queries in DBSCAN
• Curse of Dimensionality: Why DBSCAN fails in high dimensions—distance concentration makes density meaningless
• Outlier Detection: DBSCAN's noise points are natural outliers; compare to Isolation Forest, LOF
• OPTICS Algorithm: Ordering Points To Identify Clustering Structure—resolves varying density issue
• Spectral Clustering: Another method for non-convex clusters, uses graph connectivity instead of density

Visual mnemonic: Picture a party. Dense groups (>MinPts people close together) are clusters. Loners standing apart are noise. People on the edge of groups can hear the conversation (border points).

DBSCAN is like a game where you try to figure out which houses belong to which neighborhood. Here's the rule:

Walk up to a house. Draw a circle around it (that's ε). Count how many houses are inside your circle (including the one you're at). If you count at least 3 houses (that's MinPts), you say "This house is in a neighborhood!"

Now do the same for every house inside your circle. If they also have enough neighbors, they're in the neighborhood too! Keep expanding like you're playing tag—every house that's close enough to a neighborhood house joins the neighborhood.

If a house is close to a neighborhood house but doesn't have enough neighbors itself, it's on the "edge" of the neighborhood. If a house has no neighbors nearby at all, it's a lonely farmhouse—we call it "noise."

The cool part: Neighborhoods can be any shape! Long and curvy (like houses along a river), circular (like houses around a park), or weird blobs. We don't have to decide how many neighborhoods exist beforehand—the houses tell us by how they're arranged.

Practice Problems

#flashcards/ai-ml

What are the two main parameters of DBSCAN? :: ε (epsilon) - the radius for neighborhood search, and MinPts - the minimum number of points required in an ε-neighborhood for a point to be considered a core point.

Define density-reachability in DBSCAN :: Point p is density-reachable from q if there exists a chain of points p₁=q, p₂, ..., pₙ=p where each pᵢ₊₁ is directly density-reachable from pᵢ (meaning pᵢ is core and pᵢ₊₁ is within ε distance). This allows density to propagate through core points.

Concept Map

Hinglish (regional understanding)