M2-052M2: Classical Machine LearningClustering AlgorithmsEasy
⚡Flashcard Drill➔Mastery:
Formulate the K-Means Algorithm, Coordinate Descent Objective, and Convergence Guarantees
🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
📐 Mathematical Definition
⚡ One-Sentence Core Answer
K-Means minimizes Within-Cluster Sum of Squares (WCSS) via alternating coordinate descent between cluster assignment and centroid updating, guaranteeing convergence to a local minimum in a finite number of iterations.
📌 Key Takeaways
- •Objective (Inertia / WCSS): , where and .
- •Step 1 (Assignment / Expectation): Fix centroids , assign each point to closest centroid: .
- •Step 2 (Update / Maximization): Fix assignments , update centroid to cluster mean: .
- •Convergence: Monotonically non-increasing objective over finite discrete partitions (), guaranteeing termination.
📐 Mathematical Derivations
Proof of coordinate descent monotonicity: (1) In Step 1: For fixed , is minimized independently for each sample by assigning to the minimum distance , which strictly reduces or maintains . (2) In Step 2: For fixed , setting gradient , which is the unique global minimum of the quadratic term for cluster . Since each step strictly decreases and the number of distinct partitions of points into clusters is finite (), the algorithm cannot cycle and must terminate at a local minimum in finite steps.
🏭 Production Trade-offs
K-Means++ initialization (Arthur & Vassilvitskii, 2007): Standard random initialization frequently gets trapped in terrible local minima with disjoint clusters. K-Means++ chooses the first centroid uniformly at random, and then chooses subsequent centroids with probability proportional to squared distance to nearest chosen centroid: . This guarantees an expected approximation ratio .
⚠️ Common Interview Pitfalls
- ✕Assuming K-Means finds the global optimum (it is guaranteed to converge to a LOCAL minimum; must run multiple random restarts
n_init=10). - ✕Using K-Means on non-spherical, elongated, or manifold-shaped clusters (K-Means implicitly assumes isotropic spherical Gaussian clusters with equal variance).
🎯 Interviewer Follow-up Inquiries
- ?How does K-Means++ initialization mathematically guarantee approximation bound?
- ?Why is K-Means mathematically equivalent to a Gaussian Mixture Model with hard assignment and spherical covariance as ?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
📚