K-Means Algorithm

K-Means partitions $n$ samples into $K$ mutually exclusive hard clusters by coordinate descent on the within-cluster sum of squares (WCSS) objective $J = \sum_{k=1}^{K} \sum_{x \in C_k} \Vert x - \mu_k \Vert^2$.Each iteration alternates two steps: ① assignment — fix centroids, assign each $x$ to the nearest one, $c(x) = \arg\min_k \Vert x - \mu_k \Vert$; ② update — fix assignments, set each centroid to the cluster mean $\mu_k = \tfrac{1}{|C_k|} \sum_{x \in C_k} x$.Both steps never increase $J$, so the algorithm always converges — but only to a local optimum; each round costs $O(nKd)$, total $O(nKdT)$ with $T$ iterations.

exploratory clustering of unlabeled data (user/item segmentation, personas), image color quantization, vector quantization, and as the hard-assignment special case of GMM; interviews ask for the objective, convergence, initialization, and choosing $K$.

unlike hierarchical clustering with its $O(n^2)$ similarity matrix, K-Means is linear-time and scales to millions of samples; unlike GMM it needs no covariance estimation — simple, fast, and easy to implement. The tradeoff: convex (spherical) hard clusters only — poor on non-convex or uneven-density data, and the result is strongly initialization-dependent (see K-Means++).

Test Your Knowledge: Practice Questions for "K-Means Algorithm"

Single choice pitfall questions with instant feedback and mistake tracking.