Dbscan Density-Based Clustering Spatial Analysis

# DBSCAN: Density-Based Clustering & Spatial Analysis

## Introduction & Motivation

DBSCAN: density-based spatial clustering. No fixed K; finds clusters of arbitrary shape. Noise points as outliers. Applications: anomaly detection, spatial data mining, trajectory clustering.

Motivation: Arbitrary shapes; robust to outliers.

Applications: Density discovery, anomaly detection.

---

## Core Concepts & Theory

### Epsilon Neighborhood

Points within distance ε.

### Core Points

Points with ≥MinPts neighbors.

### Density Reachability

Path of density-connected points.

---

## Mathematical Formulation

Epsilon neighborhood:
$$N_\epsilon(p) = \{q \in D : d(p, q) \leq \epsilon\}$$

Core point:
$$|N_\epsilon(p)| \geq ext{MinPts}$$

Cluster:
$$C = ext{connected core points and border points}$$

---

## Advanced Theory & Extensions

### HDBSCAN

Hierarchical density clusters.

### DBSCAN Variants

Varying ε; parameter-free approaches.

### Weighted DBSCAN

Sample weights; importance.

---

## Computational Considerations

Naive: O(N²) distance computation.

With index: O(N log N) using spatial index.

Epsilon selection: KNN distance analysis.

---

## Practical Implementation Strategies

### Epsilon Selection

K-distance graph; elbow point.

### MinPts Parameter

Typically 2*dimensions or higher.

### Scaling

Normalize features; affects distance.

---

## Benchmark Datasets & Evaluation

Synthetic 2D: Easy visualization.

Blobs dataset: Standard benchmark.

Real-world: Spatial coordinates.

---

## Key Challenges & Limitations

### Parameter Sensitivity

ε and MinPts affect results strongly.

### Dimensionality Curse

Distances uniform in high dimensions.

### Varying Density

Single ε fails for varying densities.

---

## Hyperparameter Tuning

Epsilon ε: K-distance plot; elbow.

MinPts: Typically 2*D where D=dimensions.

Metric: Euclidean or Manhattan.

---

## Real-World Applications & Case Studies

Anomaly Detection: Identify noise points.

Geospatial Clustering: Location-based clustering.

Activity Recognition: Trajectory clustering.

---

## Integration with Other Methods

DBSCAN + KNN → distance-based analysis.

DBSCAN + NN → feature-space clustering.

---

## Summary & Key Takeaways

DBSCAN via density-based partitioning enables flexible clustering discovery with arbitrary shapes and automatic noise detection.

Principles:
1. Density: core vs. border points.
2. Reachability: path of neighbors.
3. Parameter selection: K-distance plot.
4. Scalability: spatial indexing.
5. Robustness: outlier handling.

---

---

## Appendix: Practical Labs

### Lab 1: Epsilon Neighborhood

import numpy as np

def epsilon_neighborhood(X, point_idx, epsilon):
 """Find epsilon neighborhood of a point"""
 distances = np.linalg.norm(X - X[point_idx], axis=1)
 neighbors = np.where(distances <= epsilon)[0]
 return neighbors

# Test
np.random.seed(42)
X = np.random.randn(100, 2)
point_idx = 0
epsilon = 0.5

neighbors = epsilon_neighborhood(X, point_idx, epsilon)

assert point_idx in neighbors, "Point is its own neighbor"
assert len(neighbors) >= 1, "At least self as neighbor"
print("✓ Epsilon neighborhood working")

if __name__ == "__main__":
 print("Lab 1: EpsilonNeighborhood - PASSED")

### Lab 2: Core Points Identification

import numpy as np

def identify_core_points(X, epsilon, min_pts):
 """Identify core points in DBSCAN"""
 N = len(X)
 core_points = []
 
 for i in range(N):
 distances = np.linalg.norm(X - X[i], axis=1)
 neighbors = np.where(distances <= epsilon)[0]
 
 if len(neighbors) >= min_pts:
 core_points.append(i)
 
 return np.array(core_points)

# Test
np.random.seed(42)
X = np.random.randn(100, 2)
epsilon = 0.5
min_pts = 5

core_points = identify_core_points(X, epsilon, min_pts)

assert len(core_points) <= 100, "Core points subset"
print("✓ Core points working")

if __name__ == "__main__":
 print("Lab 2: CorePoints - PASSED")

### Lab 3: DBSCAN Clustering

import numpy as np

def dbscan(X, epsilon, min_pts):
 """DBSCAN clustering algorithm"""
 N = len(X)
 labels = -np.ones(N, dtype=int) # -1 for noise
 cluster_id = 0
 
 for i in range(N):
 if labels[i] != -1:
 continue
 
 # Find neighbors
 distances = np.linalg.norm(X - X[i], axis=1)
 neighbors = np.where(distances <= epsilon)[0]
 
 # Not a core point
 if len(neighbors) < min_pts:
 continue
 
 # Expand cluster
 labels[neighbors] = cluster_id
 to_process = list(neighbors)
 
 while to_process:
 j = to_process.pop(0)
 if labels[j] == -1:
 labels[j] = cluster_id
 
 if labels[j] != cluster_id:
 continue
 
 # Find neighbors of j
 distances_j = np.linalg.norm(X - X[j], axis=1)
 neighbors_j = np.where(distances_j <= epsilon)[0]
 
 if len(neighbors_j) >= min_pts:
 to_process.extend(neighbors_j)
 
 cluster_id += 1
 
 return labels

# Test
np.random.seed(42)
X = np.random.randn(100, 2)
labels = dbscan(X, epsilon=0.5, min_pts=5)

assert len(labels) == 100, "Labels for all points"
assert np.all(labels >= -1), "Valid labels"
print("✓ DBSCAN clustering working")

if __name__ == "__main__":
 print("Lab 3: DBSCANClustering - PASSED")

### Lab 4: K-Distance Graph

import numpy as np

def k_distance_graph(X, k=5):
 """Compute k-distance graph for epsilon selection"""
 N = len(X)
 distances_all = []
 
 for i in range(N):
 distances = np.linalg.norm(X - X[i], axis=1)
 distances_sorted = np.sort(distances)
 k_distance = distances_sorted[min(k, len(distances_sorted)-1)]
 distances_all.append(k_distance)
 
 distances_all = np.sort(distances_all)[::-1] # Sort descending
 
 return distances_all

# Test
np.random.seed(42)
X = np.random.randn(100, 2)
k_distances = k_distance_graph(X, k=5)

assert len(k_distances) == 100, "Distance for each point"
assert np.all(k_distances >= 0), "Non-negative distances"
print("✓ K-distance graph working")

if __name__ == "__main__":
 print("Lab 4: KDistanceGraph - PASSED")