DBSCAN density-based clustering

2.5.6 · AI-ML › Unsupervised Learning

Overview

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) ek clustering algorithm hai jo points ko local density ke basis par group karta hai, na ki centroids se distance ke basis par. K-means ke unlike, yeh arbitrary shape ke clusters dhundh sakta hai aur automatically outliers identify karta hai.

Core Concepts

YEH TEEN TYPES KYUN? Yeh classification us intuitive notion ko capture karti hai ki clusters ke dense centers hote hain (cores), fuzzy boundaries hote hain (borders), aur isolated points kahin belong nahi karte (noise).

Algorithm Derivation from First Principles

Starting Question: Hum "points packed together" ko formally kaise define karein?

Step 1: Local Density Define Karo Kisi bhi point $p$ ke liye, uska ε-neighborhood define karo: $N_{\epsilon }(p)=\{q\in D:\text{dist}(p,q)\le \epsilon \}$

YEH DEFINITION KYUN? Hume ek local measure chahiye. Saare pairwise distances dekhna (global) yeh miss kar dega ki alag regions mein clusters ki alag densities ho sakti hain.

Step 2: Dense Regions Identify Karo Point $p$ ek core point hai agar: $|N_{\epsilon }(p)|\ge \text{MinPts}$

MINPTS KYUN? Ek akela neighbor kaafi nahi hai—noise mein bhi chance se ek nearby point ho sakta hai. MinPts ek threshold create karta hai jo "coincidentally close" aur "genuinely dense" mein fark karta hai. Typical choice: MinPts ≥ dimensionality + 1.

Step 3: Connectivity Define Karo Point $p$ directly density-reachable hai $q$ se agar:

• $q$ ek core point hai
• $p\in N_{\epsilon }(q)$

ONE-DIRECTIONAL KYUN? Ek border point core se reach kiya ja sakta hai, lekin core border se reachable nahi hai (uske paas enough neighbors nahi hain). Yeh asymmetry crucial hai.

Point $p$ density-reachable hai $q$ se agar ek chain hai: $q=p_1,p_2,\dots ,p_n=p$ jahan har $p_{i+1}$, $p_i$ se directly density-reachable hai.

Step 4: Cluster Membership Define Karo Points $p$ aur $q$ density-connected hain agar koi core point $o$ exist karta hai jisse dono density-reachable hain.

Ek cluster $C$ density-connected points ka maximal set hai:

1. Connectivity: $\forall p,q\in C$, $p$ aur $q$ density-connected hain
2. Maximality: Agar $p\in C$ aur $q$, $p$ se density-reachable hai, toh $q\in C$

MAXIMALITY KYUN? Yeh ensure karta hai ki hum ek connected dense region ko arbitrarily split na karein. Cluster utna badhta hai jitna density allow kare.

TENTATIVE NOISE MARKING KYUN? Pehle noise mark kiya gaya point baad mein border point ban sakta hai jab koi nearby core discover ho. Isliye hum "not yet in any cluster" check karte hain na ki "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 D include kyun hai? dist(A,D) = √((2-1)² + (2-1)²) = √2 ≈ 1.41 < 1.5

2. A ke neighbors se expand karo:

   • 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 D se distance ~5.7 hai)
   • |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}

F aur G cluster kyun nahi hue? Halanki woh ek doosre ke paas hain, par kisi ke bhi MinPts=3 neighbors nahi hain. Yeh chhote groups ko clusters kehne se rokta hai.

K-means result: Circular clusters force karta hai, har crescent ko split ya merge kar deta hai galat tarike se.

DBSCAN result:

• Core points dense crescent paths ke saath bante hain
• Border points edges fill karte hain
• Crescents ke beech ka gap mein koi core points nahi hain → natural separation

DBSCAN SUCCEED KYUN KARTA HAI: Yeh density flow follow karta hai. Ek crescent ka point doosre points tak usi crescent ke saath dense neighborhoods ki chains ke through reach kar sakta hai, lekin sparse gap ke paas se doosre crescent tak nahi pahunch sakta. Density-connectivity manifold structure ko respect karti hai.

Ek crescent ke liye detailed walk:

1. Crescent pe kisi bhi dense point P se shuru karo
2. P ka ε-ball curve ke saath ≥5 neighbors contain karta hai → P core hai
3. Woh neighbors bhi dense hain (crescent ki thickness) → woh bhi core hain
4. Chain density-reachability ke zariye crescent path ke saath expand hoti hai
5. Crescent ke tips par (thinner regions), points ke fewer neighbors hain → border points ban jaate hain
6. Gap ke paas, closest points ke ε-balls bhi overlap nahi karte → separate cluster

Parameter Selection

Goal: Woh scale dhundho jahan density transitions hoti hain.

Method:

1. Har point ke liye, uske $k$-th nearest neighbor se distance compute karo ($k=\text{MinPts}$ use karo)
2. Saare points ko unki $k$-distance ke hisaab se ascending order mein sort karo
3. Plot karo: x-axis = point index (sorted), y-axis = k-distance
4. "Elbow" dhundho—jahan curve sharply rise kare

YEH KYUN KAAM KARTA HAI:

• Clusters mein points ke small $k$-distances hote hain (dense neighborhoods)
• Noise points ke large $k$-distances hote hain (sparse neighborhoods)
• Elbow transition represent karta hai: uske left ke points clusters mein hain, right ke points outliers hain
• Elbow par $k$-distance ≈ ε ke liye accha choice

Mathematical intuition: Agar hum k-distance plot ko local densities ki cumulative distribution ki tarah sochein: $F(d)=\frac{|\{p:\text{k-dist}(p)\le d\}|}{|D|}$

Elbow wahan hai jahan $\frac{dF}{dd}$ significantly change kare—density distribution mein ek phase transition.

USE KAISE KAREIN:

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

MINPTS PEHLE KYUN? Aksar MinPts = 2×dimensionality ek rule of thumb ke taur par set kiya jaata hai. 2D mein → MinPts ≥ 4, 3D mein → MinPts ≥ 6. Yeh ensure karta hai ki ek core point ke paas ek local region define karne ke liye enough neighbors hoon, na ki sirf ek line.

Complexity Analysis

Spatial indexing ke saath (KD-tree, Ball-tree): $O(n\log n)$ average case

• Building tree: $O(n\log n)$
• Balanced tree mein range query: $O(\log n+k)$ jahan $k$ = neighbors found
• $n$ points ke liye: $O(n\log n)$

Worst case remains $O(n^2)$: high dimensions mein tree degrade ho jaata hai, ya saare points neighbors hain (ε bahut bada hai).

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

DIMENSION KYUN HURT KARTA HAI? High dimensions mein, distance concentration saare points ko roughly equidistant bana deti hai. KD-trees space ko effectively partition nahi kar paate jab saare points equally "far" hoon.

Advantages and Limitations

Advantages:

1. Arbitrary shapes: Density contours follow karta hai, non-convex clusters handle karta hai
2. Auto-outlier detection: Noise points natural byproducts hain
3. No preset K: Pehle se cluster count jaanna zaruri nahi
4. Scale-invariant (within limits): Agar data scale karo aur ε proportionally scale karo, results unchanged rehte hain

SCALE MATTER KYUN KARTA HAI: Scaling distances change karti hai. Agar features ke vastly different ranges hain (age in years vs. income in thousands), toh ε bade scale se dominate hoga. Normalization required hai.

Limitations:

1. Varying densities: Tab struggle karta hai jab clusters ki alag densities hoon. Ek single ε dense aur sparse dono clusters satisfy nahi kar sakta.

   • KYUN: Dense cluster ko chhota ε chahiye (ya woh noise se merge ho jaata hai); sparse cluster ko bada ε chahiye (ya woh fragment ho jaata hai).

2. High dimensions: Curse of dimensionality—distances meaningless ho jaati hain, density concept break down ho jaata hai.

   • KYUN: High-d mein, volume radius ke saath exponentially grow karta hai. Ek ε-ball jo 2D mein local neighbors capture karta tha, woh 100D mein ek vast hyperspace ban jaata hai.

3. Parameter sensitivity: Chhote ε/MinPts changes ke saath results dramatically change ho sakte hain.

   • KYUN: ε "local" ka scale define karta hai. Bahut chhota → sab kuch noise hai. Bahut bada → sab kuch ek cluster hai.

Kyun sahi lagta hai: "Algorithm khud figure out kar lega."

YEH FAIL KYUN HOTA HAI: ε = 0.5 income dimension mein almost kuch nahi mean karta (jahan distances ~100,000 hain) lekin age dimension mein bahut bada hai (jahan distances ~60 hain). Income dimension dominate karta hai, effectively clustering ko 1D bana deta hai.

FIX: DBSCAN se pehle features ko zero mean, unit variance mein standardize karo: $X_{\text{scaled}}=\frac{X-\mu }{\sigma }$ Ab ε ka consistent meaning hai saari dimensions mein.

Steel-man: "DBSCAN arbitrary shapes handle karta hai, toh different densities bhi handle kar sakta hoga."

YEH FAIL KYUN HOTA HAI: Density-based connectivity ek single density threshold (MinPts in ε-ball) require karta hai.

• Agar ε dense cluster ke liye tune kiya → sparse cluster noise mein fragment ho jaata hai
• Agar ε sparse cluster ke liye tune kiya → dense cluster intact rehta hai, lekin beech ke noise points galat absorb ho jaate hain

FIX: HDBSCAN (Hierarchical DBSCAN) use karo, jo alag density levels par clusterings ki hierarchy build karta hai aur stable clusters extract karta hai. Ya, manually alag parameters ke saath subregions par DBSCAN apply karo.

Steel-man: "Woh edge par hain, toh shayad woh sach mein belong nahi karte."

YEH GALAT KYUN HAI: Border points apne cluster mein sach mein belong karte hain—woh core point ke ε ke andar hain. Unhe "border" isliye kaha jaata hai kyunki woh khud cores hone ke liye itne dense nahi hain, lekin unka assignment definitive hai.

K-means se contrast: K-means mein, do centroids se equidistant points genuinely uncertain hote hain. DBSCAN mein, border points sirf ek cluster ke cores se reachable hote hain (unless tum exactly do dense regions ke boundary par ho, jo measure-zero rare hai).

FIX: Assignment par trust karo. Border points full cluster members hain.

Connections

• K-means Clustering: DBSCAN vs. K-means: arbitrary shapes vs. convex, no K vs. fixed K, noise handle karta hai vs. saare points assign karta hai
• Hierarchical Clustering: HDBSCAN, DBSCAN ko hierarchy ke saath extend karta hai; dendrogram density levels dikhata hai
• Gaussian Mixture Models: GMM density ko Gaussians ka mixture assume karta hai; DBSCAN density shape ke baare mein non-parametric hai
• KD-Trees and Spatial Indexing: DBSCAN mein efficient ε-neighborhood queries ke liye required hai
• Curse of Dimensionality: DBSCAN high dimensions mein kyun fail karta hai—distance concentration density ko meaningless bana deti hai
• Outlier Detection: DBSCAN ke noise points natural outliers hain; Isolation Forest, LOF se compare karo
• OPTICS Algorithm: Ordering Points To Identify Clustering Structure—varying density issue resolve karta hai
• Spectral Clustering: Non-convex clusters ke liye ek aur method, density ki jagah graph connectivity use karta hai

Visual mnemonic: Ek party imagine karo. Dense groups (>MinPts log ek saath paas mein) clusters hain. Akele khade loners noise hain. Groups ke edge par log conversation sun sakte hain (border points).

DBSCAN ek game ki tarah hai jahan tum figure out karne ki koshish karte ho ki kaun se ghar kis neighbourhood mein hain. Rule yeh hai:

Kisi ghar ke paas jao. Uske around ek circle banao (woh ε hai). Circle ke andar kitne ghar hain count karo (jis par khade ho use bhi milao). Agar tum kam se kam 3 ghar count karo (woh MinPts hai), toh bolte ho "Yeh ghar ek neighbourhood mein hai!"

Ab apne circle ke andar har ghar ke liye yahi karo. Agar unke bhi enough neighbors hain, toh woh bhi neighbourhood mein hain! Expand karte jao jaise tum tag khel rahe ho—har woh ghar jo neighbourhood ke kisi ghar ke kaafi paas hai, neighbourhood mein join ho jaata hai.

Agar ek ghar kisi neighbourhood ke ghar ke paas hai lekin khud ke enough neighbors nahi hain, woh neighbourhood ki "edge" par hai. Agar ek ghar ke paas bilkul bhi koi neighbor nahi hai, woh ek lonely farmhouse hai—hum use "noise" bolte hain.

Cool part yeh hai: Neighbourhoods koi bhi shape ki ho sakti hain! Lambi aur curved (jaise ek nadi ke saath ghar), circular (jaise ek park ke around ghar), ya weird blobs. Hume pehle se decide nahi karna ki kitni neighbourhoods hain—ghar khud bata dete hain apne arrangement se.

Practice Problems

#flashcards/ai-ml

DBSCAN ke do main parameters kya hain? :: ε (epsilon) - neighborhood search ke liye radius, aur MinPts - ek ε-neighborhood mein required minimum number of points taaki ek point core point maana ja sake.

DBSCAN mein density-reachability define karo :: Point p, q se density-reachable hai agar points ki ek chain p₁=q, p₂, ..., pₙ=p exist karti hai jahan har pᵢ₊₁, pᵢ se directly density-reachable hai (matlab pᵢ core hai aur pᵢ₊₁ ε distance ke andar hai). Yeh density ko core points ke through propagate hone deta hai.

Concept Map