K-means as a limiting case
Section of Mixtures and the EM algorithm, part of Statistical learning
K-means as a limiting case
| Type | Section |
| Taught in | Mixtures and the EM algorithm |
| Part | Statistical learning |
Restrict every component to a common spherical covariance \Sigma_h=\sigma^2 I, and give the components equal weights. Substitute those restrictions into the E step. The posterior membership then depends on \mathbf{x}_i only through squared Euclidean distance to the component means,
\tau_{ih} =\frac{\exp\bigl\{-\lVert\mathbf{x}_i-\boldsymbol\mu_h\rVert^2/(2\sigma^2)\bigr\}} {\sum_m\exp\bigl\{-\lVert\mathbf{x}_i-\boldsymbol\mu_m\rVert^2/(2\sigma^2)\bigr\}}.
Send \sigma^2\to 0. For each i the sum is dominated by the smallest distance, so \tau_{ih}\to 1 for a nearest mean and \tau_{ih}\to 0 otherwise, ties aside. The E step becomes the hard assignment of K-means, and the weighted mean becomes the ordinary cluster mean. K-means, in the form of Lloyd’s algorithm, is this small-variance, equal-weight, spherical limit of EM. The three restrictions are what replace ellipsoidal components by Voronoi cells.
A three-component univariate Gaussian mixture can be fitted to iris petal length by the same iteration. The path of the observed log-likelihood is the practical check of monotonicity: each accepted step should sit at least as high as the step before it.
Used in
See also
Lloyd’s K-means algorithm · Hartigan–Wong algorithm · Finite mixture model · Posterior membership · Complete-data likelihood · EM for a normal mixture · Monotonicity of EM · Likelihood of a normal mixture