DBSCAN

1. Intuition

DBSCAN groups points that are densely packed together and marks points in low-density regions as noise. Unlike K-Means, you don't need to specify the number of clusters, and the clusters can be any shape — moons, spirals, rings.

2. Two Key Hyperparameters

• eps (ε) — radius of the neighborhood around a point.
• minPts — minimum number of points required inside that neighborhood to be "dense".

3. Point Types

• Core point: has at least minPts neighbors within ε.
• Border point: within ε of a core point, but has fewer than minPts of its own.
• Noise point: neither — labeled as outlier (-1 in scikit-learn).

4. The Algorithm

5. Choosing eps — k-Distance Plot

Plot the distance from each point to its k-th nearest neighbor (k ≈ minPts), sorted ascending. The "knee" of the curve is a good ε.

6. Python Implementation

from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
from sklearn.datasets import make_moons

X, _ = make_moons(n_samples=400, noise=0.06, random_state=0)
X = StandardScaler().fit_transform(X)

db = DBSCAN(eps=0.2, min_samples=5).fit(X)
labels = db.labels_                     # -1 == noise
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
print("clusters:", n_clusters, "noise:", (labels == -1).sum())

7. DBSCAN vs K-Means

• Shape: K-Means → convex blobs; DBSCAN → arbitrary shapes.
• K: K-Means requires K; DBSCAN discovers it.
• Noise: DBSCAN flags outliers natively; K-Means forces every point into a cluster.
• Density variation: DBSCAN struggles with clusters of very different densities — use HDBSCAN or OPTICS.

8. Strengths & Weaknesses

Strengths

• Finds non-convex clusters.
• Robust to outliers (labels them as noise).
• No need to pick K.

Weaknesses

• Sensitive to eps; bad in high dimensions (curse of dimensionality).
• Fails when clusters have very different densities.
• Distance-based — always standardize features first.