Concept35 minBefore this:k-Means Clustering

Gaussian Mixture Models

What if clusters are tilted, overlap, and you need a probability of membership?

The situation

Your customer segments are tilted and overlap, and k-means slices across them. Marketing also wants to know that a customer is 62% one segment, not just assigned to one. The interviewer asks:

What is a Gaussian mixture model, and how is it fitted?

Running example: the same food-delivery customers (standardised orders per month and basket size), but a different simulated base of 320 customers where two segments are tilted: within each, basket size grows with order frequency (correlation 0.9), and the two tilted segments overlap. A third, small round segment sits below. k-means struggles here (ARI 0.62, see the k-means lesson).

Stretched, overlapping groups, and "how sure are we?"

k-means draws straight boundaries between centroids and assumes round clusters, so it slices the tilted segments crosswise. It also gives hard answers: a customer right between two segments is "segment 2", full stop. Marketing would rather know "62% likely segment 2, 38% segment 1" and target accordingly. We need a model of each cluster's shape and a probability of membership.

The idea

Think of sorting customers in pencil instead of pen: 62% this segment, 38% that one. Then each segment redraws its shape using those partial votes. Re-score everyone, redraw again, and repeat until it settles.

Illustrative. The percentages are each customer's responsibilities.

Play

Try to break it. Move through the EM iterations from the start. Watch the ellipses tilt, the log-likelihood rise and the uncertain customers change.

Run it yourself

Watch EM fit the tilted segments

EM iterations

log-likelihood (higher is better)

–

agreement with true segments (ARI)

–

uncertain customers (top probability < 0.8)

–

Colour = most likely component; faded points are uncertain (lighter = lower top responsibility). Ellipses are 2σ contours. Iteration 0 is the k-means start.

From the k-means start (ARI 0.57 after one iteration), the ellipses rotate to follow the tilt. The log-likelihood climbs from −1,006 to −656 by iteration 10 and settles at −651.8; ARI reaches 0.85, and 13 customers remain genuinely uncertain (top probability below 0.8), almost all where the two tilted segments overlap. Five different starts all converged to the same solution here.

Now say why: why can the likelihood never fall between iterations, and why might this still not be the best fit overall?

Maths

In one breath

A Gaussian mixture model says the data was generated by k bell-shaped (Gaussian) blobs, each with its own centre, shape (covariance) and share of the data. Fitting it with EM alternates two steps, like k-means but soft: the E-step computes, for every point, the probability that each blob produced it (its responsibilities); the M-step re-estimates each blob's weight, mean and covariance from those weighted points. You get tilted, stretched clusters k-means can't fit, a probability of membership per point, a likelihood you can use to choose k (BIC), and a density model for anomaly detection. The costs: local optima, more parameters, and degenerate solutions if a blob collapses onto a few points.What you'll be able to do after this: write the mixture density, run one EM iteration in words, choose a covariance type and k with BIC, and explain k-means as a special case.

component 1component 2component 3numbers / likelihood2σ ellipsesfailure

A mixture of bell curves

scikit-learn: a Gaussian mixture "assumes all the data points are generated from a mixture of a finite number of Gaussian distributions with unknown parameters", and can be thought of as "generalizing k-means clustering to incorporate information about the covariance structure of the data as well as the centers of the latent Gaussians" mixture guide.

Once fitted, Bayes' rule gives each customer's membership probabilities, the responsibilities:

One principle

Guess the hidden labels softly, refit, repeat

Swipe sideways to see the whole diagram.

Start from a guess (usually k-means): two components, each with a centre, an ellipse and a weight. One customer sits between them.
E-step: for that customer, compute the responsibilities with the current parameters: 45% component 1, 55% component 2. No hard choice.
Do this for every customer. Points deep inside an ellipse get ~100% for it; points in between are split.
M-step: refit each component as if its responsibilities were fractional counts: its weight is its total responsibility over n, its mean is the responsibility-weighted average, and its covariance the weighted spread. The ellipses move and reshape.
Repeat. Each round can only increase (or keep) the likelihood, so EM converges, but, like k-means, to a local optimum that depends on the start.

scikit-learn: EM "computes for each point a probability of being generated by each component of the model. Then, one tweaks the parameters to maximize the likelihood of the data given those assignments. Repeating this process is guaranteed to always converge to a local optimum" mixture guide.

Go deeper: the M-step formulas

With N_j = Σ_i r_ij: π_j = N_j/n; μ_j = (1/N_j) Σ_i r_ij x_i; Σ_j = (1/N_j) Σ_i r_ij (x_i − μ_j)(x_i − μ_j)^T. These are just the usual mean and covariance with fractional counts. EM maximises a lower bound on the log-likelihood that touches it at the current parameters, which is why the likelihood can't go down (Bishop, PRML §9.4).

k-means as a limit: give every component the same spherical covariance σ²I and equal weights, and let σ → 0. Responsibilities become 0/1 (nearest centre wins) and the M-step becomes "mean of the assigned points": exactly Lloyd's algorithm (PRML §9.3.2).

Choosing k

BIC: likelihood minus a price per parameter

More components always raise the likelihood, so the likelihood alone always says "more". The Bayesian information criterion adds a penalty:

Number of components k

log-likelihood

–

BIC

–

BIC falls from 2,029 (k = 1) to 1,440 (k = 2) to a minimum of 1,402 at k = 3, then rises (1,428, 1,455, 1,478) even though the log-likelihood keeps creeping up (−652, −648, −644, −638). scikit-learn's caveat: BIC "recovers the true number of components only in the asymptotic regime (i.e. if much data is available and assuming that the data was actually generated i.i.d. from a mixture of Gaussian distributions)" mixture guide.

In practice

EM, and its Bayesian cousin

The standard fitting method is expectation–maximisation (Dempster, Laird & Rubin, 1977), a general recipe for models with hidden variables (here: which component produced each point). scikit-learn's GaussianMixture uses it, initialised from k-means by default. BayesianGaussianMixture uses variational inference with priors, which can switch off unneeded components and "avoids the singularities often found in expectation-maximization solutions but introduces some subtle biases" mixture guide.

Shape constraints

Spherical, diagonal or full covariance

A full 2-D covariance has 3 numbers per component; in d dimensions it has d(d + 1)/2, which grows fast. scikit-learn lets you constrain it: spherical (one variance, round), diag (axis-aligned ellipses), tied (all components share one full covariance), or full (each its own) mixture guide.

ARI

–

BIC (lower is better)

–

parameters

–

Only full covariance can tilt, so only it follows the correlated segments: ARI 0.85 vs 0.44 (diag) and 0.52 (spherical). BIC agrees without seeing the labels: 1,402 for full vs 1,538 and 1,883. In high dimensions with little data, full covariance overfits or becomes singular; diag or tied are the safer choices there.

Beyond clustering

A density model you can reuse

Anomaly detection: p(x) is low for unusual customers; flag points below a density threshold (score_samples).
Generating data: sample a component by its weight, then a point from its Gaussian (sample).
Soft features: responsibilities as inputs to a downstream model.
Historically: GMMs modelled acoustic features in speech recognition (GMM-HMM) and speaker verification for decades before neural networks replaced them. my take

The whole recipe

Scale features; reduce dimensions (PCA) if there are many.
Grid over k and covariance_type; fit each with several initialisations (n_init).
Pick the lowest BIC, then check the components make sense.
Use predict_proba for soft membership, score_samples for density/anomaly scores.

When to use it

Use a GMM when

Clusters are elliptical or overlap
You need membership probabilities
You want a density for anomaly scores or sampling

Reach for something else when

Curved or arbitrary shapes: DBSCAN/HDBSCAN
Very large data and round clusters: k-means
Very high dimensions with few points: reduce first or use diag

The answer that sounds right

The trap

"Just maximise the likelihood directly"

Fitting means finding the π, μ and Σ that make the data most likely. If we knew which component produced each customer, that would be easy: fit one Gaussian per group by its mean and covariance. We don't, and the log-likelihood has a sum inside the logarithm, so there's no closed-form answer. Worse, it has a trap: put one component on a single customer and shrink its covariance to zero, and the likelihood shoots to infinity. scikit-learn warns the algorithm "is known to diverge and find solutions with infinite likelihood unless one regularizes the covariances artificially" mixture guide. That's why implementations add a small reg_covar to every covariance.

Caveats

Strengths

Elliptical, tilted, different-sized clusters
Soft membership probabilities
A real likelihood: BIC for k, densities for anomalies
"the fastest algorithm for learning mixture models" (scikit-learn, on EM)

Weaknesses

Local optima; needs good initialisation and restarts
Assumes each cluster is Gaussian; curved shapes need many components
Covariances can collapse (singularities); needs regularisation
Full covariance scales as d² parameters per component

Say it

What is a Gaussian mixture model, and how is it fitted?

Say your answer out loud

Aim for 30 seconds. It feels different from reading it, and that's the point.

Tick what you covered

It models data as a weighted sum of k Gaussians, each with its own mean and covariance.
It's fitted with EM.
The E-step computes each point's responsibility for each component.
The M-step re-estimates the weights, means and covariances.
The likelihood never decreases, so it converges to a local optimum.
You choose k with BIC, and it handles tilted clusters with soft assignments.