Choosing K (elbow method, silhouette score)

2.5.2 · AI-ML › Unsupervised Learning

The Elbow Method

Elbow method woh K dhundta hai jahan zyada clusters add karna aapko khaas faida dena band kar deta hai.

Yeh Kaise Kaam Karta Hai: Inertia Aapki Guide Ke Roop Mein

YEH FORMULA KYON?
Har term $\Vert \mathbf{x}-{\mathbf{\mu }}_i{\Vert }^2$ ek point se uske cluster center tak ki squared distance hai. Sabhi clusters ke sabhi points par sum karne se total "compactness" milti hai. Kam inertia = tighter clusters.

First Principles Se Derivation:

1. Goal: Har cluster ke andar variance minimize karo

   • Variance spread measure karta hai. Cluster $C_i$ ke liye centroid ${\mathbf{\mu }}_i$ ke saath: $\text{Var}(C_i)=\frac{1}{|C_i|}{\sum }_{\mathbf{x}\in C_i}\Vert \mathbf{x}-{\mathbf{\mu }}_i{\Vert }^2$
   • Sabhi clusters mein total variance: $|C_i|$ se multiply karo aur sum karo → yahi inertia hai!

2. Squared distance kyon?

   • Outliers ko heavily penalize karta hai (2× door wala point inertia mein 4× contribute karta hai)
   • Ek closed-form centroid deta hai: $\sum \Vert \mathbf{x}-\mathbf{\mu }{\Vert }^2$ ko $\mathbf{\mu }$ ke upar minimize karne se $\mathbf{\mu }=\text{mean}$ of the points milta hai. Isliye K-means centroids ko mean pe update karta hai—yeh ek coordinate-descent (Lloyd's algorithm) hai, point-assignment aur mean-recomputation alternating karta hai, gradient descent nahi.
   • Euclidean geometry assumption se match karta hai

3. The Elbow:

   • Jaise K badhta hai, inertia hamesha ghatti hai (zyada clusters = points kisi na kisi centroid ke zyada paas)
   • K = N par (points ki sankhya), inertia = 0 (har point apna khud ka cluster hai)
   • Lekin K=1 aur K=N ke beech kahin, ghattne ki rate sharply slow hoti hai—wahi elbow hai!

Kaise Apply Karein:

1. K = 1, 2, 3, .., K_max ke liye K-means run karo
2. Har K ke liye inertia record karo
3. K (x-axis) vs Inertia (y-axis) plot karo
4. "Elbow" dhundho—jahan curve sharply mod leti hai

Silhouette Score

Silhouette score measure karta hai har point apne cluster mein kitna fit baitha hai neighboring clusters ke comparison mein.

Derivation: Cohesion vs Separation

Cluster $C_I$ mein ek single point ${\mathbf{x}}_i$ ke liye:

1. Cohesion (apne cluster ke kitna paas):
   $a(i)=\frac{1}{|C_I|-1}{\sum }_{{\mathbf{x}}_j\in C_I,j\ne i}d({\mathbf{x}}_i,{\mathbf{x}}_j)$ Same cluster ke sabhi doosre points tak average distance.
   Denominator mein $|C_I|-1$ kyon? Cluster mein $|C_I|$ points hain, lekin hum ${\mathbf{x}}_i$ khud ko exclude karte hain, average ke liye $|C_I|-1$ neighbors bachte hain.

2. Separation (nearest other cluster se kitna door):
   $b(i)={\min }_{J\ne I}\frac{1}{|C_J|}{\sum }_{{\mathbf{x}}_j\in C_J}d({\mathbf{x}}_i,{\mathbf{x}}_j)$ Nearest neighboring cluster $C_J$ ke points tak average distance.
   Minimum kyon? Hum sabse paas ke alternative ki parwah karte hain—agar ${\mathbf{x}}_i$ sabhi doosre clusters se door hai, toh yeh sahi jagah par hai.

3. Silhouette coefficient:
   $s(i)=\frac{b(i)-a(i)}{\max (a(i),b(i))}$

Derivation logic:

• Agar ${\mathbf{x}}_i$ well-clustered hai: $a(i)$ chhota (apne cluster ke paas), $b(i)$ bada (doosron se door) → $s(i)\approx 1$
• Agar poorly clustered: $a(i)\approx b(i)$ → $s(i)\approx 0$
• Agar misclassified: $a(i)>b(i)$ → $s(i)<0$

Max se divide kyon? Distance scale parwah kiye bina $[-1,1]$ range mein normalize karta hai.

K Choose Karne Ke Liye Silhouette Ka Use

1. K = 2, 3, .., K_max ke liye silhouette score compute karo
2. Highest average silhouette wala K choose karo
3. Bonus: Har point ke liye silhouette plot karo (silhouette diagram)—bahut saare negative scores wale clusters poorly defined hain

Elbow aur Silhouette Ko Combine Karna

Best practice workflow:

1. Elbow curve plot karo → 2-3 candidate K values identify karo
2. Un candidates ke liye silhouette compute karo
3. Silhouette diagram check karo (per-point scores)—balanced cluster sizes dhundho, kam negatives
4. Domain experts ya downstream task se validate karo

Connections

• K-Means Clustering: Yeh methods sirf un algorithms ke liye kaam karti hain jinhe pehle K chahiye
• DBSCAN: Density-based clustering K choose karne ki zaroorat nahi (automatically dhundh leta hai)
• Hierarchical Clustering: Elbow/silhouette ki jagah dendrograms use karta hai
• Gap Statistic: Advanced alternative—inertia ko null distribution se compare karta hai
• Hyperparameter Tuning: K choose karna learning rate choose karne jaisa hai—validation chahiye
• Bias-Variance Tradeoff: Bahut kam clusters = high bias, bahut zyada = high variance (noise overfitting)

Flashcards

#flashcards/ai-ml

K-means mein inertia kya measure karta hai? :: Within-cluster sum of squared distances—points centroids ke kitne paas cluster hote hain. Kam = tighter clusters.

Point i ke liye Silhouette coefficient formula :: $s(i)=\frac{b(i)-a(i)}{\max (a(i),b(i))}$ jahan $a(i)$ = apne cluster tak avg distance, $b(i)$ = nearest other cluster tak avg distance.

K choose karne ka best practice :: Elbow + silhouette + domain knowledge ek saath use karo. Koi bhi single method perfect nahi hai; yeh milkar best K par vote karte hain.

Concept Map