Overview of Clustering Concept (k-means) — Beginner-Friendly Notes

1. What Clustering Is

Find k groups so points within a group are close together and groups are far apart — no labels given (unsupervised).

2. k-means — The Classic Algorithm (concept, not heavy maths)

Goal: minimise within-cluster variance (sum of squared distances to cluster centre).

Steps (Lloyd's):

1. Choose k (e.g., 3) and initialise 3 centroids randomly
2. Assign each point to nearest centroid (Euclidean)
3. Recompute centroid = mean of points in that cluster
4. Repeat 2-3 until assignments stop changing

Text diagram:

Points → assign to nearest ● (centroid) → move ● to mean → repeat

3. Example — Customer Segmentation

• Features: income, spending score. k=3 → clusters: "low income low spend", "high income high spend", "mid". Useful for targeted offers without knowing labels.

4. Key Points for Exam

Point	Detail
Needs k upfront	You choose k; use elbow plot (variance vs k) or domain knowledge
Distance	Euclidean (so scale features — standardise)
Sensitive to	initial centroids (run multiple times), outliers (drag centroid)
Shape bias	Prefers spherical, equal-size clusters (fails on rings, moons)
Complexity	$O(n \cdot k \cdot iterations)$ — fast, scalable
Output	Each point gets cluster id + centroids as prototypes

5. Choosing k (beginner heuristic)

Plot WCSS (within-cluster sum of squares) vs k — WCSS drops fast then flattens; "elbow" is good k. Or use silhouette score.

6. One-Line Summary

k-means iteratively assigns points to nearest centroid and recomputes means to minimise within-cluster variance, requiring pre-chosen $k$ and feature scaling, favouring spherical clusters and sensitive to initialisation and outliers.

7. Quick Self-Check

1. What happens if k is too small vs too large?
2. Why standardise features before k-means?