Gaussian Mixture Models & Spectral Clustering, In Full Depth

K-Means gives every point a hard, all-or-nothing cluster assignment. Gaussian Mixture Models give a probability of belonging to each cluster instead — a genuinely different, softer notion of what clustering even means.

Gaussian Mixture Models (GMM)

The model: assume the data was generated by a mixture of $k$ Gaussian distributions, each with its own mean $\mu_j$, covariance $\Sigma_j$, and mixing weight $\pi_j$ (how much of the overall data that component accounts for):

$P(\mathbf{x}) = \sum_{j=1}^k \pi_j \, \mathcal{N}(\mathbf{x} \mid \mu_j, \Sigma_j)$

This is directly the generative modeling idea from LDA/QDA — model each group as a Gaussian — applied without known class labels. In fact, GMM is essentially unsupervised QDA: same Gaussian machinery, but the group membership itself is what needs to be discovered, not given.

Soft assignment: for each point, GMM computes $P(\text{cluster } j \mid \mathbf{x})$ for every $j$ — a full probability distribution over cluster membership, not a single hard label. A point sitting between two cluster centers might get 60%/40% membership, honestly reflecting genuine ambiguity — something K-Means structurally cannot express (every point gets exactly one cluster, however close the call). Real EM, real soft memberships, live:

Training GMM: Expectation-Maximization (EM)

Since neither the cluster parameters nor the assignments are known upfront, GMM is trained with Expectation-Maximization, alternating between two steps until convergence:

1. E-step (Expectation): given the current $\mu_j, \Sigma_j, \pi_j$, compute each point's soft membership probability for every cluster.
2. M-step (Maximization): given those soft memberships, re-estimate $\mu_j, \Sigma_j, \pi_j$ to best fit the (softly) assigned points — a weighted version of ordinary Gaussian parameter estimation.

This is structurally identical to K-Means's assign-then-update loop (see K-Means) — E-step is a soft version of "assign," M-step is a soft version of "update centroids." In fact, K-Means is provably the limiting case of GMM with equal, spherical, shrinking-to-zero covariance — GMM is the more general model, K-Means the simplified, hard-assignment special case.

Choosing $k$: like K-Means, $k$ is a hyperparameter — but GMM has a principled model-selection tool K-Means lacks: since GMM defines an actual probability model, you can compare different $k$ values using AIC/BIC (information criteria that penalize model complexity — see ML Workflow Fundamentals), rather than relying only on an inertia-elbow heuristic.

Spectral Clustering

A completely different mechanism for handling non-convex clusters, based on graph theory rather than density or distance-to-centroid:

1. Build a similarity graph — connect each point to its nearby points (e.g. k-nearest neighbors, see KNN), weighted by similarity.
2. Compute the graph's Laplacian matrix and find its smallest eigenvectors (see Linear Algebra — Eigenvalues and Eigenvectors) — these eigenvectors capture the graph's natural "cut points," the places where connectivity is weakest.
3. Use those eigenvectors as new, transformed coordinates for each point, and run ordinary K-Means in that transformed space.

Why this handles non-convex shapes: two points on opposite ends of the same curved crescent are far apart in raw Euclidean distance, but densely connected through a chain of nearby neighbors along the crescent — the similarity graph captures that chain-connectivity directly, and the eigenvector transformation reshapes the space so that chain-connected points end up close together, letting plain K-Means (which only understands round blobs) succeed on the transformed coordinates even though it would fail on the original ones. This is the same K-Means-fails-on-two-moons problem, solved by changing the space K-Means operates in rather than changing the algorithm itself.

Choosing Among the Four Clustering Methods

Unsupervised Learning's clustering family complete: K-Means & Hierarchical → DBSCAN & HDBSCAN → GMM & Spectral. Next: Dimensionality Reduction — PCA, t-SNE, UMAP, and the rest of the family that compresses features rather than grouping examples.