Monday, September 21, 2026

Mainak's ML Notebook: K-Means & Unsupervised Learning

K-Means Clustering & Unsupervised Learning Masterclass

Handwritten Study Notes — Complete & Unabridged

⚠️ ONE CORRECTION WORTH TATTOOING INTO YOUR ML NOTES:
KNN ≠ K-Means.
• KNN: Supervised | Has labels | Classification/Regression | "Which known neighbors look like me?"
• K-Means: Unsupervised | No labels | Clustering | "Which points naturally belong together?"

1. The Core Intuition

Think of the problem like this:

“I have data, but nobody has told me the correct group for each row. Can the algorithm discover the groups itself?”

Example Dataset (Customer Data): No target column!

CustomerAnnual SpendVisits/Year
A102
B123
C112
D7018
E7520
F7219
G3510
H4011

K-Means says: “Give me K groups, and I will find K representative centers and assign every point to its nearest center.”

Each cluster has a centroid, which is simply the mean of all points assigned to that cluster.


2. The Actual Mathematics

Suppose a point is $x = (x_1, x_2)$ and a centroid is $\mu = (\mu_1, \mu_2)$.

Euclidean Distance: $$d(x, \mu) = \sqrt{(x_1 - \mu_1)^2 + (x_2 - \mu_2)^2}$$

Numerical Example:
Point $P = (10, 2)$, Centroid $C = (12, 3)$
$d(P,C) = \sqrt{(10-12)^2 + (2-3)^2} = \sqrt{4 + 1} = \sqrt{5} = 2.236$
Nearest centroid wins!


3. What is K-Means Optimizing? (Interview Essential)

K-Means tries to minimize the Within-Cluster Sum of Squares (WCSS), commonly called inertia in scikit-learn:

$$J = \sum_{k=1}^{K} \sum_{x_i \in C_k} ||x_i - \mu_k||^2$$

In simple English: Keep points as close as possible to their cluster center. Notice distance is squared ($\sum d^2$), meaning large outliers/distances get punished heavily!


4. The K-Means Algorithm Loop

  1. Choose $K$
  2. Initialize $K$ centroids
  3. Calculate distance from every point $\to$ every centroid
  4. Assign each point to nearest centroid
  5. Calculate new centroid using mean
  6. Repeat until centroids barely move (CONVERGED)

5. Initialization Methods

Method ① — Random Initialization

Selecting initial centroids randomly from data points. Problem: If random choice picks points in the same region, K-Means can converge to a poor local minimum.

Method ② — K-Means++ (Standard Practice)

"Don't randomly put all centroids next to each other. Spread initial centroids out using weighted probabilities proportional to squared distance: $P(\text{select } x) \propto D(x)^2$."

First centroid chosen randomly. Subsequent centroids chosen with higher probability if they are farther away from already-selected centroids. This avoids bad local minima.

The n_init Parameter

n_init=10 runs K-Means 10 times with different K-Means++ initializations and keeps the solution with the lowest inertia.


6. Complete Manual Hand Calculation Example

Dataset:
Cluster 1 area: $A=(1,1), B=(2,1), C=(1,2)$
Cluster 2 area: $D=(8,8), E=(9,8), F=(8,9)$
Let $K=2$. Initial centroids: $C_1=(1,1), C_2=(8,8)$.

  • Assignment Step: Points A, B, C are closest to $C_1$. Points D, E, F are closest to $C_2$.
  • Centroid Update (Mean):
    New $C_1 = (\frac{1+2+1}{3}, \frac{1+1+2}{3}) = (1.33, 1.33)$
    New $C_2 = (\frac{8+9+8}{3}, \frac{8+8+9}{3}) = (8.33, 8.33)$
  • Repeat until convergence.

7. Interactive Visualizer Widget

Interactive K-Means Demo

Click anywhere on the canvas below to add data points, then click run to watch centroids shift!


Status: Add points and click Step!


8. Hidden Assumptions & Scaling

  • Implicit assumption: K-Means assumes clusters are compact, similar in scale, and approximately spherical/convex (Voronoi regions). It fails on interlocking or complex ring shapes.
  • Feature Scaling is Mandatory: Euclidean distance is dominated by large numbers. Always use StandardScaler() ($z = \frac{x - \mu}{\sigma}$) so features have mean=0 and std=1.
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans
from sklearn.pipeline import Pipeline

pipeline = Pipeline([
    ("scaler", StandardScaler()),
    ("cluster", KMeans(n_clusters=4, init="k-means++", n_init=20, random_state=42))
])
pipeline.fit(X)
labels = pipeline.predict(X)
    

9. How to Choose K?

  1. Domain Knowledge: Business says "We need 4 customer segments" $\to K=4$.
  2. Elbow Method: Plot WCSS (Inertia) across $K = 1, 2, 3 \dots$ Look for the "elbow" where diminishing returns kick in.
  3. Silhouette Score: Measures how similar a point is to its own cluster compared to other clusters ($s \approx 1$ is ideal):
    $$s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))}$$

10. Alternative Clustering Cheat Sheet

SituationBest Algorithm
Compact numeric groupsK-Means
Unknown number of clusters / Arbitrary shapesDBSCAN / HDBSCAN
Noise and outliers important (Fraud/Anomaly)DBSCAN / HDBSCAN
Hierarchical relationships / DendrogramAgglomerative Clustering
Soft / Probabilistic membershipGaussian Mixture Model (GMM)
Very large datasets (Millions of rows)MiniBatchKMeans

11. The 80/20 Interview Map

If Interviewer Asks...Think...
Why K-Means?Compact numeric clusters, fast baseline
Objective function?Minimize SSE / WCSS (Inertia)
Why K-Means++?Smart initialization to avoid local minima
Why n_init?Run multiple times, keep lowest inertia
Why scaling?Distance-based metric prevents feature dominance
K-Means weakness?Spherical assumption, sensitive to outliers, requires K
Millions of rows?MiniBatchKMeans
- Mainak's Study Notebook 2026

No comments:

Post a Comment