K-Means Clustering & Unsupervised Learning Masterclass
Handwritten Study Notes — Complete & Unabridged
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!
| Customer | Annual Spend | Visits/Year |
|---|---|---|
| A | 10 | 2 |
| B | 12 | 3 |
| C | 11 | 2 |
| D | 70 | 18 |
| E | 75 | 20 |
| F | 72 | 19 |
| G | 35 | 10 |
| H | 40 | 11 |
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)$.
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:
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
- Choose $K$
- Initialize $K$ centroids
- Calculate distance from every point $\to$ every centroid
- Assign each point to nearest centroid
- Calculate new centroid using mean
- 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)
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?
- Domain Knowledge: Business says "We need 4 customer segments" $\to K=4$.
- Elbow Method: Plot WCSS (Inertia) across $K = 1, 2, 3 \dots$ Look for the "elbow" where diminishing returns kick in.
- 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
| Situation | Best Algorithm |
|---|---|
| Compact numeric groups | K-Means |
| Unknown number of clusters / Arbitrary shapes | DBSCAN / HDBSCAN |
| Noise and outliers important (Fraud/Anomaly) | DBSCAN / HDBSCAN |
| Hierarchical relationships / Dendrogram | Agglomerative Clustering |
| Soft / Probabilistic membership | Gaussian 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 |
No comments:
Post a Comment