PHASE 3 · UNSUPERVISED · ALGO #11
k-Means Clustering
Finding structure in unlabeled data
Core Concept
k-Means partitions data into k groups by minimizing the total within-cluster variance. Each point joins the cluster whose centroid (mean) is nearest, and centroids are re-computed until they stop moving. It's an iterative expectation-maximization loop over pure geometry — no labels required.
Key Components
Centroids
k cluster centers; each is the mean of its assigned points.Distance
Euclidean distance decides which centroid a point belongs to.WCSS
Within-cluster sum of squares — the objective it minimizes.Choosing k
Elbow method: plot WCSS vs k, pick the bend.How It Works
- Initialize: place k centroids (random or k-Means++).
- Assign: attach each point to its nearest centroid.
- Update: move each centroid to the mean of its points.
- Repeat assign + update until centroids stop moving (convergence).
minimize J = Σi Σx∈Ci ||x − μi||²
Real-World Applications
- 🛍️Customer segmentation for targeted marketing
- 🖼️Image color quantization / compression
- 📄Document & topic grouping
- 🚨Anomaly detection via distance to nearest centroid
Checkpoint Questions
Why is centroid initialization so important, and how does k-Means++ help?
What exact quantity does the algorithm minimize, and why can it get stuck in a local optimum?
When does k-Means fail — e.g. on non-spherical or unequal-density clusters — and what would you reach for instead?