পাঠ ৩৩ · ৪৫-এর মধ্যে · মডিউল ৫

Home / AI Courses / Machine Learning / DBSCAN

DBSCAN — ঘনত্বভিত্তিক ক্লাস্টারিং

DBSCAN — Density-Based Spatial Clustering

৭ মিনিট পড়া মাঝারি · Intermediate sklearn

এই পাঠে যা শিখবেন

Density-based ভাবনা — ঘন এলাকা = cluster
Core, border, noise point — তিন categorization
$\varepsilon$ ও min_samples বাছাই — k-distance plot
Algorithm step-by-step — region query থেকে cluster expansion
Dhaka taxi/Pathao hotspot detection — case study

১ · K-Means-এর সীমাবদ্ধতা থেকে DBSCAN-এর জন্ম

K-Means দু'টি assumption-এ আঁকড়ে আছে — cluster spherical ও equal-sized। কিন্তু বাস্তবে — Dhaka-র ride-hailing রিকুয়েস্ট pattern চিন্তা করুন। গুলশান, মিরপুর, ধানমন্ডি — দুই-তিনটি hot spot। প্রতিটি spot-এর shape rectangular, road-network-এর মত elongated। কিছু request ফাঁকা এলাকায় (rare)। K-Means এই pattern ধরতে পারবে না — মানে সব এলাকায় equal split করে দেবে।

১৯৯৬ সালে Ester, Kriegel, Sander, Xu — KDD conference-এ একটি সম্পূর্ণ ভিন্ন পদ্ধতি দিলেন: DBSCAN (Density-Based Spatial Clustering of Applications with Noise)। মূল idea — "cluster = ঘন এলাকা, যেখানে ঘনত্ব কম সেখানে cluster boundary"। SIGKDD 2014-এ "test of time" award পেল — একটি কালজয়ী algorithm।

Density-based core idea

একটি point-এর চারপাশে $\varepsilon$ ব্যাসার্ধের গোলকে যদি কমপক্ষে min_samples point থাকে — সেটি "core" point। Core point-গুলো সংযুক্ত হয়ে cluster তৈরি। ফাঁকা এলাকার single point — noise।

২ · তিন ধরনের point

$\varepsilon$ = neighborhood radius, min_samples = $m$ ধরে নিই।

Core point: $\varepsilon$-neighborhood-এ কমপক্ষে $m$ point। ঘন এলাকার কেন্দ্র।
Border point: নিজের neighborhood-এ $m$-এর কম, কিন্তু কোনো core point-এর neighborhood-এ আছে। Cluster-এর প্রান্তে।
Noise point: কোনোটাই না — একা ফাঁকায়। Cluster-এ assign হয় না (label = -1)।

ঢাকা শহরে রাত ৯টার ভিড় ভাবুন। একটি বড় জনসমাগম এলাকা (নিউ মার্কেট) — চারদিকে ঘন মানুষ। ভেতরের লোকজন core, প্রান্তের border। দূরে রাস্তার পাশে একা দাঁড়িয়ে যে — noise (এই cluster-এর কেউ না)।

৩ · Algorithm — step-by-step

একটি unvisited point বাছাই।
তার $\varepsilon$-neighborhood query।
যদি neighbor count $< m$ → noise (later visit-এ border হতে পারে)।
যদি $\geq m$ → core। নতুন cluster শুরু।
Cluster expand: প্রতিটি neighbor-এর neighborhood query, যদি core — তাদের neighbor-ও যোগ। এভাবে chain।
সব visit হলে stop। যত cluster — তত cluster, যত orphan — তত noise।

Complexity: naive $O(n^2)$, R-tree বা ball-tree দিয়ে $O(n \log n)$। sklearn default ball-tree (high-D-এ KD-tree)।

৪ · Hyperparameter বাছাই

DBSCAN-এর সবচেয়ে বড় challenge — $\varepsilon$ ও min_samples ঠিক করা।

min_samples heuristic: $m \approx 2 \cdot d$ (যেখানে $d$ = dimension)। ২-D data → $m = 4$, ১০-D → $m = 20$। বড় dataset-এ আরও বড়।

$\varepsilon$ — k-distance plot:

প্রতিটি point-এর $k$-th nearest neighbor (যেখানে $k = m$) এর দূরত্ব compute।
সব দূরত্ব ascending sort করে plot।
"Knee" বা "elbow" — যেখানে curve sharp turn — সেটাই $\varepsilon$।

৫ · DBSCAN-এর strength

$k$ আগে দিতে হয় না: algorithm নিজেই cluster count বের করে।
Non-spherical shape: ring, spiral, S-shape — সবই handle।
Outlier auto-detection: noise point label = -1 — কোনো cluster-এ assign হয় না।
Robust: outlier centroid distort করে না (K-Means-এর বিপরীত)।
Density-aware: "cluster" বাস্তব intuition-এর সাথে align।

৬ · DBSCAN-এর weakness

Varying density: একটি ঘন cluster + একটি sparse cluster — same $\varepsilon$ দু'টোতেই কাজ করে না।
High-D: "ঘন/পাতলা" intuition collapse করে — curse of dimensionality।
Hyperparameter sensitive: $\varepsilon$ একটু বদলালে — সম্পূর্ণ ভিন্ন cluster।
Border ambiguous: একটি border point কোন core-এর সাথে — ordering-dependent।

Varying density সমস্যা সমাধানে — HDBSCAN (Campello-Moulavi-Sander, ২০১৩): hierarchical + density। sklearn-extra বা hdbscan package।

DBSCAN — ঘন এলাকার core point (সবুজ), প্রান্তের border (হলুদ), একা থাকা noise (লাল)। Elongated shape K-Means ভেঙে ফেলবে — DBSCAN ধরে।

৭ · sklearn-এ DBSCAN — Dhaka pickup hotspot

Pathao/Uber-এর ১০০০ ride request-এর GPS coordinate। কোথায় hotspot, কোথায় sparse?

Python · sklearn

import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler

# synthetic Dhaka pickup GPS — 4 hotspots + scatter
np.random.seed(0)
hotspots = [(23.78, 90.40),  # Gulshan
            (23.74, 90.39),  # Dhanmondi
            (23.81, 90.37),  # Mirpur
            (23.71, 90.41)]  # Motijheel

pts = []
for lat, lon in hotspots:
    pts.append(np.random.normal([lat, lon], [0.005, 0.005], (200, 2)))
# scattered noise
pts.append(np.random.uniform([23.65, 90.30], [23.85, 90.50], (100, 2)))
X = np.vstack(pts)

# Lat/lon scale similar — তবু StandardScaler safe practice
X_s = StandardScaler().fit_transform(X)

db = DBSCAN(eps=0.3, min_samples=10).fit(X_s)
labels = db.labels_

n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = list(labels).count(-1)

print(f"Found {n_clusters} clusters, {n_noise} noise points")
for c in range(n_clusters):
    print(f"  Cluster {c}: {sum(labels == c)} points")

৪টি cluster (Gulshan, Dhanmondi, Mirpur, Motijheel) এবং ১০০টি noise — DBSCAN automatic ধরবে। K-Means $k=4$ দিতে হত — আগে জানা না থাকলে DBSCAN superior।

৮ · k-distance plot — $\varepsilon$ বাছাই

Python · sklearn

from sklearn.neighbors import NearestNeighbors

k = 10  # min_samples
nbrs = NearestNeighbors(n_neighbors=k).fit(X_s)
dists, _ = nbrs.kneighbors(X_s)
k_dist = np.sort(dists[:, k-1])

# elbow — সবচেয়ে বড় gradient change
print("First 10 k-distances:", k_dist[:10].round(3))
print("Last 10 k-distances:",  k_dist[-10:].round(3))
print("Elbow সাধারণত high-percentile-এ — knee detector ব্যবহার করুন")

Sorted k-distance plot-এ "knee" — যেখানে curve হঠাৎ উপরে উঠে — সেটাই $\varepsilon$। python-এ kneed library auto-detect করে।

৯ · DBSCAN ব্যবহারের ক্ষেত্র

GIS/spatial: ride hotspot, crime mapping, disease outbreak।
Anomaly detection: credit card fraud, network intrusion।
Image segmentation: color-based regions।
Astronomy: galaxy cluster identification।
Bioinformatics: gene expression cluster।

DBSCAN-এ scaling অপরিহার্য (Euclidean দূরত্ব)। Lat-lon-এ কাজ করলে — haversine distance ব্যবহার করুন metric="haversine" (radian-এ input)। নাহলে equator vs pole-এ pixel-distance ভিন্ন হবে।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ DBSCAN-এর varying density problem — HDBSCAN কীভাবে সমাধান করে?

DBSCAN-এর fundamental flaw — single $\varepsilon$ সব cluster-এ apply। কিন্তু realistic data-এ density vary করে।

সমস্যাটা চিত্রিত:

একটি ঘন cluster (Gulshan rich, request packed) ও একটি sparse cluster (savar, request scattered)।
Small $\varepsilon$ — সঘন detect কিন্তু sparse-কে noise।
Large $\varepsilon$ — sparse detect কিন্তু dense merge।
একসাথে দু'টোই — impossible single-$\varepsilon$।

HDBSCAN-এর approach (Campello et al., ২০১৩):

Multiple $\varepsilon$ একসাথে consider।
Mutual reachability distance — point-pair-এর "true" density।
Hierarchy build — সব $\varepsilon$-এর জন্য DBSCAN-equivalent।
Cluster stability — কোন cluster বহু density-তে persist করে।
Stable cluster বাছাই — varying density natural handle।

Algorithm steps:

Mutual reachability graph তৈরি।
MST (minimum spanning tree)।
Hierarchical cluster tree।
Cluster persistence score।
Stable cluster extraction।

Hyperparameter:

শুধু min_cluster_size — minimum cluster member count।
$\varepsilon$ গায়েব — auto-determined per cluster।
প্রকৃত "tuning-free"।

Benefits:

Varying density — natural।
Cluster size auto।
Noise point identified।
Cluster persistence interpretable।
Soft membership probability available।

Trade-offs:

Slower than DBSCAN।
$O(n^2)$ memory in naive form।
Implementation complex।
Library — hdbscan (Python), faster than scikit।

Bangladesh use cases:

Pathao request — Dhaka dense, Chittagong sparse, rural very sparse — HDBSCAN ideal।
Health outbreak — urban hotspot ঘন, rural ছড়ানো।
Customer segmentation — big spender ঘন, casual sparse।

মূল উপলব্ধি: DBSCAN — single density। HDBSCAN — multi-density। Practical world rarely single-density — তাই HDBSCAN যেখানে available সেখানে preferred।

প্র ০২ DBSCAN-এ border point ambiguous — কোন cluster-এ assign? এটা কি bug না feature?

চমৎকার subtle observation। DBSCAN-এর paper-এও ambiguity acknowledge করা।

Scenario:

একটি border point দু'টি core point-এর neighborhood-এ — দু'টি ভিন্ন cluster-এর।
প্রথম যে cluster expansion এই point-এ পৌঁছায় — সেটাই assign পায়।
Algorithm-এর processing order-এর উপর result depend করে।

Bug না feature?

Argument for "bug": reproducibility-এর সমস্যা — same data, different order, different result।
Argument for "feature": border point inherently ambiguous — যেকোনো assignment defensible।

Practical impact:

সাধারণত border point ছোট fraction (<১০%)।
Most real data-এ cluster well-separated → border কম।
Boundary গুরুত্বপূর্ণ হলে — soft clustering (GMM)।

Solutions:

Sort by distance: closest core-এর সাথে assign — deterministic।
HDBSCAN: probability-based soft membership।
Density Peaks (Rodriguez-Laio, ২০১৪): alternative — peak-based, deterministic।
Multi-run consensus: ১০০ run-এর majority vote।

Implementation detail:

sklearn-এ — first-come-first-served, point order-dependent।
Reproducibility — random seed, sorted input।
Production-এ document করুন — "border may vary by ৫%"।

মূল উপলব্ধি: Border ambiguity DBSCAN-এর "elegant flaw" — pure density-based-এ inherent। Soft clustering গভীর সমাধান। Most practical work-এ এটা negligible।

প্র ০৩ High-dimensional data (১০০+ feature) DBSCAN-এ কেন ভেঙে পড়ে? Workaround কী?

Curse of dimensionality DBSCAN-কে আক্রমণ করে কঠোরভাবে। বুঝতে হলে — দূরত্ব ও density-র সম্পর্ক।

মূল সমস্যা — দূরত্ব concentration:

High-D-এ random points-এর pairwise distance প্রায় সমান।
"নিকটতম" ও "দূরতম" পার্থক্য vanishes।
$\varepsilon$-neighborhood meaningless — হয় empty, হয় সব।
Density concept collapse।

Mathematical:

$d$-D unit cube-এর volume — $1$।
$d$-D unit ball-এর volume — $\frac{\pi^{d/2}}{\Gamma(d/2+1)} \to 0$ as $d \to \infty$।
$\varepsilon$-ball-এ point পড়ার probability vanishingly small।

Practical symptoms:

সব point noise (no core)।
সব point single mega-cluster।
$\varepsilon$ tune করেও sweet spot নেই।

Workarounds:

(১) Dimensionality reduction:

PCA → 10-50 D।
UMAP → 2-10 D — non-linear (preserve local structure)।
Autoencoder → arbitrary low-D।
Reduced space-এ DBSCAN।

(২) Distance metric switch:

Cosine similarity — angle-based, scale-invariant।
Manhattan ($L_1$) — high-D-এ Euclidean-এর চেয়ে marginally better।
Mahalanobis — covariance-aware।
Domain-specific (e.g., edit distance for sequences)।

(৩) Subspace clustering:

Different cluster — different feature subspace।
SUBCLU (subspace clustering DBSCAN extension)।
Genomics, document — subspace common।

(৪) Feature selection first:

Variance-based filter।
Mutual information.
10-30 most informative feature বেছে নিন।

(৫) Embedding model:

BERT-like model দিয়ে dense embedding।
"Semantic distance" structured।
৭৬৮-D যদিও — high-quality embedding-এ density meaningful।

(৬) Alternative algorithm:

HDBSCAN — slightly more robust।
OPTICS — single-density-এর বিকল্প।
Spectral clustering — high-D-এ ভাল।
Deep clustering (DEC, IDEC) — embedding + cluster jointly।

Bangladesh case:

Customer ৫০ feature — PCA → ১০ → DBSCAN।
Document clustering — TF-IDF ১০০০-D → BERT embedding ৭৬৮-D → UMAP ৫-D → HDBSCAN। This is standard pipeline।

মূল উপলব্ধি: DBSCAN low-D natural। High-D-এ — preprocess, dimension reduce, alternative metric। "Dimensionality reduction → density clustering" — modern unsupervised pipeline-এর backbone।

প্র ০৪ Bangladesh-এ একটি ride-hailing কোম্পানি hotspot detection-এ DBSCAN deploy করছে। Production pipeline কেমন হবে?

Pathao/Uber-এর actual production scenario। Real-time + historical analytics — দু'টি পথ।

(১) Use cases:

Driver positioning: idle drivers কোথায় move করবে।
Surge pricing: ঘন hotspot-এ demand surge।
Pickup zone: airport, bus station — designated zone।
Anomaly detection: hotspot suddenly empty — disaster, traffic jam।

(২) Data pipeline:

Source: app GPS log, ride request DB।
Streaming — Kafka/Kinesis।
Batch — last hour aggregated।
Storage — geo-indexed (PostGIS, MongoDB geo)।

(৩) Preprocessing:

GPS noise filter (Kalman, accuracy threshold)।
Out-of-Dhaka filter।
Time-of-day bucket (rush hour vs off-peak)।
Day-of-week segmentation।

(৪) DBSCAN config:

Distance — haversine (great-circle, in radians)।
$\varepsilon$ — ১০০-৩০০ meter (district-specific)।
min_samples — ১০-৫০ requests/window।
Time window — ১৫ মিনিট rolling।

(৫) Real-time vs batch:

Real-time: incremental DBSCAN বা reactive recompute every ৫ মিনিট।
Batch: hourly aggregation, daily pattern, weekly trend।
Cache: hotspot location, density score।

(৬) Hotspot characterization:

Centroid (cluster center)।
Density (points per sqkm)।
Persistence (consecutive window-এ exist)।
Type (residential, commercial, transit)।

(৭) Driver app integration:

Heatmap visualization।
Suggested move direction (gradient-based)।
Estimated request frequency।

(৮) Validation:

A/B test — driver follow vs ignore suggestion।
Driver income, idle time metrics।
Customer wait time।
Surge pricing accuracy।

(৯) Edge cases:

Concert/event — sudden one-time hotspot।
Eid, festival — pattern bole-aspect বদলায়।
Rain, flood — anomaly।
Adversarial driver behavior (gaming the system)।

(১০) Privacy:

Individual rider track নয়।
Aggregated cluster only।
Location precision rounded।
Data retention policy।

(১১) Monitoring:

Cluster count consistency।
Hotspot stability (sudden shift = data issue)।
Driver feedback loop।
Service area expansion impact।

মূল উপলব্ধি: Production DBSCAN ৯০% engineering, ১০% algorithm। Bangladesh ride-hailing-এ — connectivity issue, GPS accuracy, sudden weather event — সব handle করা real challenge। DBSCAN flexible enough — কিন্তু operations সবচেয়ে গুরুত্বপূর্ণ।

অনুশীলন

হিসাব করুন: ৫টি 1-D point — ${1, 2, 3, 8, 100}$, $\varepsilon=2$, min_samples=2। প্রতিটি point কী (core/border/noise)?
- Point 1: neighbors within 2 = {2, 3} → 3 (incl self) → core।
- Point 2: {1, 3} → 3 → core।
- Point 3: {1, 2} → 3 → core।
- Point 8: {} → 1 → noise (none within 2)।
- Point 100: {} → 1 → noise।
- Cluster: {1, 2, 3} একটি cluster, 8 ও 100 noise।

sklearn-এ চেষ্টা: Two-moon synthetic data — DBSCAN বনাম K-Means।

from sklearn.datasets import make_moons
from sklearn.cluster import KMeans, DBSCAN

X, _ = make_moons(n_samples=200, noise=0.05, random_state=0)

km = KMeans(n_clusters=2, n_init=10, random_state=0).fit(X)
db = DBSCAN(eps=0.2, min_samples=5).fit(X)

print("KMeans cluster sizes:", np.bincount(km.labels_))
print("DBSCAN cluster sizes:", np.bincount(db.labels_ + 1))  # -1 → 0
# K-Means দু'টিকে straight line দিয়ে কাটে → ভুল
# DBSCAN moon-shape ঠিক ধরে

ভাবুন: Bangladesh-এ road-accident hotspot detection-এ DBSCAN। কী challenges? Pipeline ডিজাইন।
- Data: police accident report, ambulance dispatch, citizen report।
- Feature: GPS, time, severity, vehicle type।
- Preprocessing: highway vs city — separate analysis।
- $\varepsilon$: ৫০-১০০ meter (urban), ৫০০ meter (highway)।
- Time-aware: last 1 year, weighted by recency।
- Validation: traffic police domain knowledge।
- Action: speed bump, signal, awareness campaign।
- Challenge: reporting bias (urban over-report), data quality।
- Ethics: driver/area stigmatize avoid।