Stanford CS229 Lecture 9: K-Means and Gaussian Mixture Models (Spring 2026)

TL;DR

The lecture presents K‑means as a hard‑assignment clustering algorithm and Gaussian mixture models (GMM) as its soft‑assignment probabilistic counterpart, showing how both are solved by an expectation‑maximization (EM) loop, why initialization matters, and how Jensen’s inequality provides a tractable lower bound for EM.

K‑means algorithm intuition

K‑means seeks to partition data into K clusters by iteratively assigning each point to the nearest cluster center and then recomputing each center as the mean of its assigned points.

The algorithm starts with random initial centers μ₁ … μ_K, assigns each point to the cluster whose center is closest (using Euclidean distance), updates each center to the arithmetic mean of its assigned points, and repeats until assignments no longer change.

Because the cluster labels are arbitrary, swapping all μ’s yields the same solution; what matters is that the centers end up at the correct locations.

Termination, optimality, and initialization

K‑means always terminates because the within‑cluster sum of squared distances (the L₂ objective) is monotonically decreasing and bounded below, so the algorithm reaches a fixed point where assignments stop changing.

Finding the global minimum of this objective is NP‑hard, so K‑means can converge to a suboptimal solution that depends on the initial centers.

Multiple local minima exist; different random initializations can lead to different final clusterings, which is why the initialization step is crucial.

To improve initialization, the K‑means++ procedure selects initial centers in a way that provably yields a good approximation ratio; this variant is the default in common libraries such as scikit‑learn.

Choosing the number of clusters K

Selecting K is a modeling assumption: the analyst must express prior belief about how many distinct groups exist in the data.

Increasing K yields finer partitions, but a lower cost does not automatically imply a better model; evaluating whether a larger K is truly beneficial requires external knowledge or validation criteria.

Thus, picking K remains a qualitative decision guided by the problem domain rather than a purely algorithmic criterion.

From hard to soft assignments: Gaussian mixture models

GMM replaces K‑means’ hard cluster membership with a probabilistic assignment: each point is generated from one of K Gaussian sources with unknown means, covariances, and mixing weights.

The forward model assumes a latent variable Z_i indicating the source of point X_i; Z_i is drawn from a multinomial distribution over the K sources, and X_i is then sampled from the corresponding Gaussian.

Given only the observed points, the goal is to infer the Gaussian parameters and the mixing weights that best explain the data.

Expectation‑maximization for GMM

EM alternates between two steps:

  • E‑step: compute the posterior probability w_{ij} that point i originated from source j, using Bayes’ rule on the current parameter estimates.
  • M‑step: update each Gaussian’s mean, covariance, and mixing weight as the weighted averages of the points, where the weights are the posteriors w_{ij}.

When the posteriors are 0 or 1, the M‑step reduces exactly to the K‑means update; otherwise, EM performs a soft, weighted version of the same computation.

The algorithm iterates until the parameter estimates converge.

Jensen’s inequality and the EM lower bound

EM can be viewed as maximizing a lower bound on the data log‑likelihood.

Jensen’s inequality states that for a convex function φ, 𝔼[φ(X)] ≥ φ(𝔼[X]); for concave functions the inequality reverses.

In the E‑step, EM constructs a surrogate function that is tight at the current parameters and easier to optimize; applying Jensen’s inequality to the log‑likelihood yields this surrogate, guaranteeing that each M‑step increases (or leaves unchanged) the true likelihood.

Thus, EM is guaranteed to converge to a stationary point of the likelihood, though not necessarily the global maximum.

Practical takeaways

  • K‑means is simple and interpretable but sensitive to initialization and can get stuck in poor local minima.
  • K‑means++ provides a principled way to initialize centers with strong theoretical guarantees.
  • GMM extends K‑means by modeling uncertainty in cluster membership and capturing elliptical cluster shapes via covariances.
  • EM provides a general framework for latent‑variable models; its convergence relies on Jensen’s inequality to construct a tight lower bound.
  • Both algorithms require the analyst to specify the number of clusters K, a modeling decision that should be informed by domain knowledge.

These concepts form the basis for many modern unsupervised learning techniques and illustrate the trade‑offs between algorithmic simplicity, computational hardness, and the need for careful initialization and model selection.

Sources