Unsupervised Learning
Clustering, dimensionality reduction and density estimation.
Most data come without labels: shopping baskets, gene-expression profiles, billions of photos. Unsupervised learning asks what structure is there anyway. This lesson develops the classic answers with their algorithms and guarantees: clustering (k-means, hierarchies, DBSCAN, Gaussian mixtures fitted by EM), dimensionality reduction (PCA), and density estimation, along with the curse of dimensionality that haunts all three.
What you’ll learn
- State the k-means objective, prove that Lloyd's algorithm never increases it and terminates, and explain k-means++ seeding and why the problem is NP-hard.
- Compare hierarchical clustering, DBSCAN and Gaussian mixtures, and derive the EM updates for a Gaussian mixture with their monotonicity.
- Derive PCA as variance maximization, connect it to the eigenvectors of the covariance and the SVD of the data, and use explained variance to choose a dimension.
- Build a kernel density estimate, explain the bandwidth's bias–variance trade-off and its rate, and quantify the curse of dimensionality.
k-means and Lloyd's algorithm
In unsupervised learning there is no label to predict, so every method must say what structure it is looking for. Clustering looks for groups. Given points and a number , k-means chooses centroids and an assignment that minimize the within-cluster sum of squares, or inertia:
Lloyd's algorithm (1957, published 1982) minimizes it by alternating over the two blocks of variables:
LLOYD(points x_1..x_n, initial centroids μ_1..μ_k)
repeat
for i = 1..n: # assignment step, O(nkd)
c(i) ← argmin_j ||x_i − μ_j||² (on a tie, keep the current cluster)
for j = 1..k with cluster j nonempty: # update step, O(nd)
μ_j ← mean of { x_i : c(i) = j }
until no assignment changes
return c, μAssignment. With the centroids fixed, is a sum of separate terms, one per point, and each is minimized by the nearest centroid:
Update. With the assignment fixed, splits by cluster. For a cluster with mean and any point , the cross term vanishes because , so the mean is the unique minimizer:
Termination. After each update the centroids are the means of the current partition, so is a function of the partition alone, and there are at most partitions. A point changes cluster only if it gets strictly closer (the tie rule), so every iteration that changes the partition strictly lowers . No partition can recur, and the algorithm stops.
Termination is not efficiency or optimality. Lloyd usually converges in a few dozen iterations, but some inputs need iterations even in the plane (Vattani, 2011), although its smoothed complexity is polynomial (Arthur, Manthey & Röglin, 2011). The fixed point is only a local optimum, and finding the global one is NP-hard, already for when the dimension is part of the input (Aloise et al., 2009) and for general in the plane (Mahajan, Nimbhorkar & Varadarajan, 2012).
Starts matter, so use good ones. k-means++ (Arthur & Vassilvitskii, 2007) picks the first centroid uniformly from the data and each next one with probability proportional to , the squared distance to the nearest centroid chosen so far. Before Lloyd even runs, its expected inertia is at most times the optimum.
Which property does Lloyd's algorithm guarantee on every dataset?
- It finds the clustering with the minimum possible inertia
- It converges in a number of iterations polynomial in
- It stops after finitely many iterations at a clustering that neither the assignment nor the update step can improve
- It reaches the same clustering from every initialization
Show the answer
C. It stops after finitely many iterations at a clustering that neither the assignment nor the update step can improve
Each step weakly lowers , every change of partition lowers it strictly, and there are finitely many partitions. That gives termination at a fixed point, a local optimum, and nothing more: global optimality is NP-hard, the worst-case iteration count is exponential, and different starts reach different fixed points.
Hierarchies and density
Every clustering method encodes a notion of what a cluster is. k-means assigns each point to its nearest centroid, so its clusters are the cells of a Voronoi diagram: convex, and best suited to round groups of similar size and spread. Two families make different assumptions.
Agglomerative hierarchical clustering starts from singletons and repeatedly merges the two closest clusters, recording a tree of merges (a dendrogram) that can be cut at any height. The linkage defines the distance between clusters: single (closest pair; equivalent to building a minimum spanning tree and prone to chaining), complete (farthest pair), average, or Ward (the merge that least increases the within-cluster sum of squares, the k-means criterion). The general algorithm needs memory and time; single linkage runs in time with SLINK (Sibson, 1973).
DBSCAN (Ester, Kriegel, Sander & Xu, 1996) has two parameters, a radius and a count . A core point has at least points within ; clusters are the connected groups of core points within of each other, plus the border points near them; everything else is labeled noise. It finds clusters of any shape and needs no , but one cannot fit clusters of very different densities.
| Method | A cluster is… | Needs | Weak spot |
|---|---|---|---|
| k-means | a Voronoi cell around a centroid | non-convex or elongated shapes; outliers; feature scaling | |
| Single linkage | a connected chain of close points | a cut height | chaining through bridges of noise |
| Ward linkage | a compact group, merged greedily | a cut height or | same biases as k-means, and greedy |
| DBSCAN | a dense region separated by sparse space | , | clusters of very different densities; high dimension |
| Gaussian mixture | one elliptical Gaussian component | local optima; degenerate covariances |
Gaussian mixtures and EM
A Gaussian mixture model is a generative model: pick a component with probability , then draw . Its density is , and it clusters softly: each point gets a posterior probability of belonging to each component. Fitting it by maximum likelihood means maximizing , the log of a sum, which has no closed-form maximizer. Expectation–maximization (EM; Dempster, Laird & Rubin, 1977) alternates two easy steps instead.
E-step. Given the current parameters, compute each point's responsibilities, the posterior probabilities of the components, by Bayes' rule:
M-step. Treat the responsibilities as fractional labels and maximize the expected complete-data log-likelihood . Each component gets a weighted Gaussian fit; with :
For the weights, add a Lagrange multiplier for : gives , and summing over gives :
Why the likelihood never decreases. For any weights with , Jensen's inequality gives a lower bound , with equality when is the posterior at . The E-step makes the bound tight at ; the M-step raises it; so .
import numpy as np
from scipy.stats import multivariate_normal
def em_step(X, pi, mu, Sigma, ridge=1e-6):
n, d = X.shape
k = len(pi)
# E-step: responsibilities r[i, j] = P(z_i = j | x_i)
dens = np.column_stack([pi[j] * multivariate_normal.pdf(X, mu[j], Sigma[j])
for j in range(k)])
loglik = np.log(dens.sum(axis=1)).sum() # of the old parameters
r = dens / dens.sum(axis=1, keepdims=True)
# M-step: responsibility-weighted maximum likelihood
Nk = r.sum(axis=0)
pi = Nk / n
mu = (r.T @ X) / Nk[:, None]
Sigma = np.stack([(r[:, j, None] * (X - mu[j])).T @ (X - mu[j]) / Nk[j]
+ ridge * np.eye(d) for j in range(k)])
return pi, mu, Sigma, loglikSuccessive values of loglik never decrease. Production code works with log-densities (the log-sum-exp trick) to avoid underflow. The small ridge keeps covariances invertible.
Three facts connect EM to the rest of the lesson. k-means is a limit of EM: fix and and let ; the responsibilities harden into nearest-centroid assignments and the M-step becomes the centroid update. The likelihood is unbounded: a component that centers on one data point and shrinks its covariance to zero sends , so the global "maximum" is degenerate and EM is valued for the good local maxima it finds; a floor or prior on the covariances prevents collapse. Choosing uses held-out likelihood or penalized criteria such as BIC, .
The same E-step/M-step pattern fits hidden Markov models (Baum–Welch, in HMM Algorithms), and its lower bound is the evidence lower bound of variational inference (Information Theory for AI).
PCA: variance, eigenvectors and the SVD
Dimensionality reduction represents each by a few coordinates , . Principal component analysis (Pearson, 1901; Hotelling, 1933) looks for the -dimensional subspace that keeps the most variance or, equivalently, loses the least squared reconstruction error. Center the data, , and let be the sample covariance.
Projecting onto a unit vector gives scores , whose variance is a quadratic form in the covariance:
Maximize subject to with the Lagrangian . Its gradient vanishes exactly at eigenvectors, where the variance captured equals the eigenvalue, so the best is the top eigenvector:
Each further component maximizes the variance subject to orthogonality to the previous ones, which by the spectral theorem (The Math Toolkit of AI) gives the next eigenvectors. For with orthonormal columns, the top eigenvectors maximize the total variance kept:
The reconstruction loses exactly what is not kept, so maximizing variance and minimizing squared reconstruction error are the same problem:
In practice PCA is computed from the SVD of the centered data matrix, : then , so the principal directions are the right singular vectors, , and the scores are the columns of . This avoids forming , which squares the condition number. A full SVD costs ; the top components cost about with Lanczos or randomized methods. Choose from the explained-variance ratio or the elbow of a scree plot, and standardize the features first if their units differ, because PCA is not scale-invariant.
A covariance matrix has eigenvalues . What percentage of the variance do the first two principal components keep?
Show the answer
75 %
. The mean squared reconstruction error of the 2-D projection is the rest, .
Density estimation and the curse of dimensionality
The most complete description of unlabeled data is its density . A histogram estimates it by counting points in bins of width . The kernel density estimate (Rosenblatt, 1956; Parzen, 1962) replaces each point by a smooth bump, a probability density scaled by the bandwidth :
The bandwidth is a bias–variance dial. In one dimension a Taylor expansion gives , where : wide bumps blur peaks and fill valleys. The variance is about with : narrow bumps make a spiky estimate that changes with every sample. In dimensions the variance becomes order . Minimizing the integrated squared bias plus variance gives
For a roughly Gaussian 1-D sample with a Gaussian kernel, this yields Silverman's rule of thumb ; in practice is also chosen by cross-validated likelihood.
In one dimension, you collect 32 times more data. By what factor should the error-optimal bandwidth shrink?
Show the answer
2 ×
and , so the bandwidth halves, while the optimal error falls by . Slower than the parametric rate : that is the price of assuming only smoothness.
Now read the rate as a function of dimension. Halving the error takes times more data: 2.4 times in one dimension, 11 times in ten. Geometry says why. To capture 1% of points spread uniformly over a 10-dimensional unit cube, a sub-cube needs side , so a "local" neighborhood spans most of the range of every coordinate, and distances between random points concentrate around a common value. Silverman (1986) computed that estimating a standard normal density at its center to 10% relative mean squared error takes about 4 points in one dimension and about 842,000 in ten. This is the curse of dimensionality.
What rescues high-dimensional data is structure: points near low-dimensional manifolds, smoothness, and models with the right assumptions, such as mixtures, or the deep generative models (flows, VAEs, diffusion models) of Generative Models.
Key takeaways
- k-means minimizes the inertia; Lloyd's assignment and update steps never increase it and terminate at a local optimum. The global problem is NP-hard, and k-means++ seeding is within of optimal in expectation.
- Clustering methods encode assumptions: Voronoi cells (k-means), chains (single linkage), density (DBSCAN), elliptical components (Gaussian mixtures). EM fits mixtures by alternating responsibilities and weighted maximum likelihood, and never decreases the likelihood.
- PCA keeps the top eigenvectors of the covariance, the right singular vectors of the centered data: the variance kept is and the reconstruction error .
- Low-dimensional pictures distort: PCA keeps spread, not neighborhoods; t-SNE and UMAP keep neighborhoods, not cluster sizes or distances.
- A kernel density estimate trades bias against variance , for an optimal error : the curse of dimensionality, beaten only by structure.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Why must Lloyd's algorithm for k-means terminate?
- Its step size decreases geometrically
- The centroids converge to the true cluster centers
- The inertia never increases, drops strictly whenever the partition changes, and there are finitely many partitions
- It stops after a fixed number of iterations
Show the answer
C. The inertia never increases, drops strictly whenever the partition changes, and there are finitely many partitions
Both steps weakly decrease ; with ties broken consistently, every change of partition strictly decreases it, and depends only on the partition once centroids are means. With at most partitions, none can repeat, so the algorithm stops.
Why can k-means with never separate two interleaved crescents?
- Its two clusters are Voronoi cells of the centroids, separated by a straight line, and the crescent split is not even its optimum
- It needs more restarts
- It needs k-means++ initialization
- The crescents have too many points
Show the answer
A. Its two clusters are Voronoi cells of the centroids, separated by a straight line, and the crescent split is not even its optimum
Each point joins its nearest centroid, so the boundary between two clusters is the perpendicular bisector of the centroids. In the widget, the true moon split has inertia 48.5, worse than the straight cut's 31.7, so better optimization would not help: the objective does not describe these clusters.
In EM for a Gaussian mixture, what is the M-step update of a component's mean ?
- The mean of the points closest to
- The data point with the highest responsibility for component
- The overall mean of the data
- The responsibility-weighted average
Show the answer
D. The responsibility-weighted average
The M-step is weighted maximum likelihood, with each point counted in component with weight . In the hard-assignment limit (weights 0 or 1) it reduces to k-means' centroid update.
For centered data with SVD , the first principal direction is…
- the first column of
- the first column of , the top eigenvector of the covariance
- the direction of the largest data point
- the eigenvector of the covariance with the smallest eigenvalue
Show the answer
B. the first column of , the top eigenvector of the covariance
, so the right singular vectors are the covariance eigenvectors and maximizes the projected variance . The columns of are the scores, the coordinates of the points along each direction.
A kernel density estimate is computed with a very small bandwidth . What does it look like?
- A single broad bump, regardless of the data
- Exactly the true density, since smaller means less bias
- A spike at each data point: low bias but high variance
- A uniform density
Show the answer
C. A spike at each data point: low bias but high variance
As , each kernel collapses onto its point and becomes a set of spikes: unbiased in the limit but wildly variable, with variance of order . As it becomes one broad, heavily biased bump. The best balances the two and shrinks like .
Go deeper
- k-Means, EM & Mixture Models · Hard and soft clustering, and why EM works.
- PCA, t-SNE & UMAP · Finding low-dimensional structure in high-dimensional data.
- Density Estimation · Kernels, histograms and the curse of dimensionality.
Further reading
- C. M. Bishop, Pattern Recognition and Machine Learning (Springer, 2006), chapters 9 and 12.
- T. Hastie, R. Tibshirani & J. Friedman, The Elements of Statistical Learning, 2nd ed. (Springer, 2009), chapter 14.
- D. Arthur & S. Vassilvitskii, "k-means++: the advantages of careful seeding," Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1027–1035 (2007).
- B. W. Silverman, Density Estimation for Statistics and Data Analysis (Chapman & Hall, 1986).