DBSCAN — Density-Based Clustering

Problem with K-Means

K-Means assumes:

• Clusters are roughly spherical
• You know K (number of clusters) in advance
• All clusters have similar sizes

Counter-examples:

• Crescent-shaped clusters
• Clusters of different sizes
• Outliers shouldn't be in any cluster
• Unknown number of clusters

DBSCAN (Density-Based Spatial Clustering)

Core Idea

Two points are in the same cluster if they're close together and surrounded by other close points.

How it works:

1. ε (epsilon): How close is "close"? (distance threshold)
2. minPts: Minimum neighbors within ε to be a core point
3. For each point:
   • If >= minPts points within ε → Core point
   • If close to core point → Border point
   • Otherwise → Noise/Outlier

Parameters:

• ε: Too small = all noise. Too large = one big cluster. Use k-distance graph.
• minPts: Often 2×dimensions or 4. Balance sensitivity.

Advantages over K-Means

Pros:

• ✓ No need to specify K (discovers automatically)
• ✓ Finds arbitrary-shaped clusters
• ✓ Detects outliers (noise points)
• ✓ Robust to outliers

Cons:

• ✗ Sensitive to ε and minPts (must tune)
• ✗ Slower than K-Means (O(n²))
• ✗ Struggles with varying cluster densities
• ✗ High-dimensional curse (distances become less meaningful)

Choosing ε

Use the k-distance graph:

1. For each point, calculate distance to kth nearest neighbor
2. Sort distances
3. Plot as line graph
4. Find "elbow" where distances increase sharply
5. That's your ε

DBSCAN vs K-Means