K-Means clustering algorithm

2.5.1 · AI-ML › Unsupervised Learning

K-Means Kya Hai?

YEH OBJECTIVE KYUN? Hum chahte hain ki clusters mein points apne center ke around tightly packed hon. Squared distances minimize karna outliers ko heavily penalize karta hai (quadratic penalty) aur math ko gradient-based reasoning ke liye tractable banata hai.

Algorithm: First Principles se Derivation

GOAL: Data $\{x_1,x_2,...,x_n\}$ ko $K$ clusters mein partition karo taaki total variance minimize ho.

Step 1: Centroids Kyun?

Agar hum cluster assignments fix kar lein, toh cluster $C_k$ ke liye best representative point kaun sa hoga?

Minimize: ${\sum }_{x_i\in C_k}||x_i-{\mu }_k|{|}^2$, ${\mu }_k$ ke respect mein

Derivative lo aur zero set karo: $\frac{\partial }{\partial {\mu }_k}{\sum }_{x_i\in C_k}||x_i-{\mu }_k|{|}^2={\sum }_{x_i\in C_k}2(x_i-{\mu }_k)(-1)=0$

${\sum }_{x_i\in C_k}(x_i-{\mu }_k)=0$

${\sum }_{x_i\in C_k}{x}_i=|C_k|{\mu }_k$

${\mu }_k=\frac{1}{|C_k|}{\sum }_{x_i\in C_k}{x}_i$

RESULT: Optimal representative cluster ke saare points ka mean (average) hota hai. Isliye inhe "centroids" kehte hain.

Step 2: Nearest-Neighbor Assignment Kyun?

Agar hum centroids fix kar lein, toh point $x_i$ ko kaun se cluster mein jaana chahiye?

Minimize: Total objective $J$ mein $x_i$ ka contribution

Point $x_i$ ko cluster $k^{\ast }$ mein jaana chahiye jahan: $k^{\ast }=\arg {\min }_{k\in \{1,...,K\}}||x_i-{\mu }_k|{|}^2$

KYUN? Har point independently woh centroid choose karta hai jo uski apni squared distance minimize kare. Yeh greedy assignment tab optimal hai jab centroids fixed hoon.

Step 3: Lloyd's Algorithm

Yeh do steps coupled hain: better assignments se better centroids milte hain, jinse better assignments milti hain. Hum alternate karte hain:

Initialize: Randomly $K$ points ko initial centroids ke roop mein select karo $\{{\mu }_1,...,{\mu }_K\}$

Convergence tak repeat karo:

1. Assignment Step: Har point $x_i$ ke liye, nearest centroid ko assign karo: $c_i=\arg {\min }_k||x_i-{\mu }_k|{|}^2$

2. Update Step: Har centroid ko assigned points ke mean ke roop mein recompute karo: ${\mu }_k=\frac{1}{|C_k|}{\sum }_{x_i\in C_k}{x}_i$

Convergence: Tab ruko jab assignments change karna band ho jayein (ya centroids threshold $ϵ$ se kam move karein)

YEH CONVERGE KYUN KARTA HAI? Har step objective $J$ ko decrease karta hai (ya constant rakhta hai):

• Assignment step: Points closer centroids ki taraf move karte hain → $J$ decrease hota hai
• Update step: Centroids apne cluster ke mean ki taraf move karte hain → $J$ decrease hota hai (hamare derivative proof se)
• $J\ge 0$ neeche se bounded hai
• Monotone convergence theorem se, algorithm zaroor converge karega

IMPORTANT: Convergence ek local minimum ki taraf hoti hai, necessarily global nahi. Alag-alag initializations se alag results aa sakte hain.

Worked Examples

Data: $A=(1,1),B=(2,1),C=(5,5),D=(6,6)$ Goal: 2 clusters dhundo

Iteration 0 (Initialize):

• Random centroids: ${\mu }_1=(1,1),{\mu }_2=(5,5)$

Iteration 1: Assignment:

• $A=(1,1)$: $d({\mu }_1)=0,d({\mu }_2)=\sqrt{32}$ → Cluster 1
• $B=(2,1)$: $d({\mu }_1)=1,d({\mu }_2)=\sqrt{32}$ → Cluster 1
• $C=(5,5)$: $d({\mu }_1)=\sqrt{32},d({\mu }_2)=0$ → Cluster 2
• $D=(6,6)$: $d({\mu }_1)=\sqrt{50},d({\mu }_2)=\sqrt{2}$ → Cluster 2

Update:

• ${\mu }_1=\frac{(1,1)+(2,1)}{2}=(1.5,1)$
• ${\mu }_2=\frac{(5,5)+(6,6)}{2}=(5.5,5.5)$

Iteration 2:

Assignment: (Distances phir se check karo)

• Saare assignments same rehte hain

Converge ho gaya! Final clusters: $\{A,B\}$ aur $\{C,D\}$

YEH STEP KYUN? Har distance calculation Euclidean metric use karti hai kyunki hum squared distances minimize kar rahe hain. Update step coordinates ko component-wise average karta hai kyunki mean sum of squared deviations minimize karta hai.

Problem: 100 customers ko [spending, frequency] se cluster karo

# Pseudocode with reasoning
data = load_customers()  # Shape: (100, 2)
K = 3
 
# Initialize: K-Means++ (smarter than random)
centroids = [random_point()]
for in range(K-1):
    # Pick next centroid far from existing ones
    distances = [min(dist(p, c) for c in centroids) for p in data]
    centroids.append(weighted_random(data, distances))
 
for iteration in range(max_iters):
    # Assignment: Vectorized for speed
    distances = cdist(data, centroids)  # Shape (100, 3)
    labels = argmin(distances, axis=1)   # Shape (100,)
    # Update
    new_centroids = []
    for k in range(K):
        cluster_points = data[labels == k]
        new_centroids.append(mean(cluster_points, axis=0))
    
    if converged(centroids, new_centroids):
        break
    centroids = new_centroids

YEH CHOICES KYUN?

• K-Means++ initialization: Initial centroids ko spread out karta hai → faster convergence, bad local minima se bachata hai
• Vectorization: cdist ek saath saare pairwise distances compute karta hai → loops se 100× faster
• Convergence check: Centroid movement compare karo, assignments nahi → zyada stable stopping criterion

Common Mistakes aur Unhe Kaise Fix Karein

Reality: K-Means ek local minimum mein converge karta hai, jo initialization par depend karta hai. Alag-alag random starts se alag results milte hain.

Steel-man: Algorithm starting point ke given WCSS objective ko perfectly optimize karta hai. Problem yeh hai ki objective landscape mein bahut saari valleys hain.

Fix:

• K-Means ko multiple times alag initializations ke saath run karo (sklearn default: 10 runs)
• K-Means++ initialization use karo (provably random se better)
• Sabse low final WCSS wala solution report karo

Reality: K-Means spherical clusters ki similar size assume karta hai. Yeh fail karta hai:

• Elongated/elliptical clusters par
• Crescent ya ring shapes par
• Bahut alag densities ke clusters par

Steel-man: Spherical Gaussian distributions se generate kiye gaye data ke liye, K-Means actually optimal hai (yeh MLE solution hai).

Fix:

• Preprocess karo: Agar scales alag hain toh features standardize karo
• Non-convex shapes ke liye DBSCAN ya spectral clustering use karo
• Data transform karo (e.g., kernel trick) taaki clusters zyada spherical ho jayein

Reality:

• WCSS hamesha decrease hota hai jab $K$ badhta hai ($K=n$ par, WCSS=0)
• Koi universal "correct" K nahi hai — yeh domain-dependent hai

Steel-man: Systematic search valuable zaroor hai, lekin sahi metric chahiye.

Fix:

• Elbow method: WCSS vs K plot karo, "elbow" dhundo jahan improvement slow ho jaaye
• Silhouette score: Measure karo ki points apne cluster se kitne similar hain vs. doosron se
• Domain knowledge: Kabhi kabhi K known hota hai (e.g., customer segments)
• Gap statistic: WCSS ko null distribution se compare karo

Computational Complexity

Har iteration mein time:

• Assignment step: $O(nKd)$ — $n$ points × $K$ centroids × $d$ dimensions compute karo
• Update step: $O(nd)$ — $n$ points, $d$ dimensions par sum karo

Total: $O(IKnd)$ jahan $I$ = iterations ki sankhya

Space: $O((n+K)d)$ — data aur centroids store karo

Practice mein: $I$ typically chota hota hai (<100) aur $K\ll n$, isliye K-Means large datasets par achhe se scale karta hai.

YEH COMPLEXITY KYUN? Assignment step bottleneck hai: hum $nK$ distances compute karte hain. Advanced implementations KD-trees ya ball trees use karte hain jab $d$ chota ho toh ise reduce karne ke liye.

Convergence ke Peeche ka Math

Claim: Har iteration $J$ ko decrease karta hai (ya same rakhta hai), isliye K-Means converge karta hai.

Proof: Maano $J^{(t)}$ iteration $t$ par objective hai.

Iteration $t+1$ par assignment step ke baad: $J_{\text{assign}}^{(t+1)}\le J^{(t)}$ kyunki har point nearest centroid ki taraf move karta hai (ya wahan rehta hai), jo uski distance increase nahi kar sakta.

Update step ke baad: $J^{(t+1)}\le J_{\text{assign}}^{(t+1)}$ kyunki ${\mu }_k=\arg {\min }_{\mu }{\sum }_{x_i\in C_k}||x_i-\mu |{|}^2$ (pehle prove kiya hua).

Isliye: $J^{(t+1)}\le J^{(t)}$

Kyunki $J\ge 0$ aur finitely many possible labelings hain (zyada se zyada $K^n$), algorithm zaroor converge karega. $\square$

CAVEAT: Convergence ek local minimum ki taraf hoti hai. Global minimum dhundhna NP-hard hai.

Extensions aur Variations

1. K-Means++: Smart initialization jo initial centroids ko spread karta hai $P(\text{choose }{x}_i)\propto D(x_i{)}^2$ jahan $D(x_i)$ = nearest existing centroid tak ki distance

2. Mini-Batch K-Means: Har iteration mein random subsets of data use karo → huge datasets ke liye faster

3. Soft K-Means (Fuzzy C-Means): Partial membership allow karo: $p(C_k|x_i)=\frac{e^{-\beta ||x_i-{\mu }_k|{|}^2}}{{\sum }_j{e}^{-\beta ||x_i-{\mu }_j|{|}^2}}$

4. K-Medoids (PAM): Actual data points ko centers ke roop mein use karo (outliers ke liye robust)

1. Tum K alag-alag boxes pile mein randomly rakhte ho
2. Har candy nearest box ki taraf jaati hai
3. Tum har box ko uske saari candies ke center par move karte ho jo usne choose ki
4. Steps 2-3 repeat karo jab tak boxes move karna band na kar dein

Boxes "seekh" rahe hain ki similar candies ke natural groups kahan hain! Same box mein candies ek doosre se similar ho jaati hain, chahe tumne algorithm ko kabhi nahi bataya ki kaun si candies ek saath jaani chahiye.

Tricky part yeh hai ki tumhe shuru mein decide karna hota hai kitne boxes (K) use karne hain. Zyada kam boxes aur tum alag types ko ek saath squeeze kar lete ho. Zyada boxes aur tum candies ko split kar dete ho jo actually same type ki hain.

"Converge but Local" — Yeh move karna band kar deta hai, lekin overall best answer nahi ho sakta

K-Means = K-Averages — Centroids literally means (averages) hote hain, medians ya modes nahi

"Spherical, Similar Size" — Do S's jo describe karte hain ki K-Means kya pasand karta hai

Connections

• Choosing K: Elbow & Silhouette Methods
• K-Means++ Initialization
• Hierarchical Clustering — alternative approach bina pehle K define kiye
• DBSCAN — non-spherical clusters handle karta hai
• Gradient Descent — similar alternating optimization pattern
• Bias-Variance Tradeoff — K choose karna fit vs. generalization ko trade off karta hai
• Expectation-Maximization (EM) — K-Means ek special case hai (hard EM for Gaussians)

#flashcards/ai-ml

K-Means kaunsa objective function minimize karta hai? :: Within-cluster sum of squares (WCSS): $J={\sum }_{k=1}^K{\sum }_{x_i\in C_k}||x_i-{\mu }_k|{|}^2$

Concept Map