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++).

Write the K-Means objective $J = \sum_{k} \sum_{x \in C_k} \Vert x - \mu_k \Vert^2$; why do the assignment and update steps never increase $J$, guaranteeing convergence?

Derive the centroid update $\mu_k = \tfrac{1}{|C_k|} \sum_{x \in C_k} x$ as the minimizer of the subproblem; is K-Means a convex problem?

K-Means vs GMM (hard vs soft assignment)? How is K-Means fundamentally different from KNN?

Why does K-Means only reach a local optimum? How does initialization affect the result? Mitigations: K-Means++, multiple random restarts, K-Medoids?

What is the time complexity of K-Means? How to pick K (elbow method, silhouette)? Why is it outlier-sensitive and why does it fail on non-convex clusters?