K-Means Clustering

K-means is an unsupervised algorithm that partitions $n$ points into $k$ clusters by minimizing within-cluster squared distance to cluster centroids. It is a hard-assignment special case of the soft Gaussian Mixture Models.

Objective

Minimize the total within-cluster sum of squares over assignments $c_i$ and centroids ${\mu }_j$:

$$J=\sum _{i=1}^n\sum _{j=1}^{k}1[c_i=j]\Vert x_i-{\mu }_j{\Vert }^2$$

This is NP-hard in general, so we use iterative local optimization.

Lloyd’s Algorithm

1. Initialize $k$ centroids.
2. Assignment step: assign each point to its nearest centroid.
3. Update step: set each centroid to the mean of its assigned points.
4. Repeat until assignments stop changing.

• Each step never increases $J$, so it converges to a local minimum.
• Cost per iteration is $O(nkd)$.

Initialization (k-means++)

• Random init can yield poor local minima; run multiple restarts and keep the lowest $J$.
• k-means++ spreads initial centers: pick the first uniformly, then each next center with probability proportional to squared distance from the nearest chosen center.
• Gives an $O(\log k)$ expected approximation guarantee and faster convergence.

Choosing k

• Elbow method: plot $J$ vs $k$ and pick the bend.
• Silhouette score: measures cohesion vs separation.
• Domain knowledge or downstream task performance.

Limitations

• Assumes spherical, equally sized clusters; struggles with elongated or varying-density shapes.
• Sensitive to scaling and outliers (means are not robust).
• Must fix $k$ in advance; only finds local optima.

Relation to GMMs

K-means is the limiting case of a GMM with isotropic covariances ${\sigma }^{2}I$ as $\sigma \to 0$, replacing soft responsibilities with hard nearest-centroid assignments. Both are optimized by an EM-style alternation.