43 Unsupervised Methods
← Back to: Classical ML Overview
43.1 k-means: clustering by proximity
Partition \(n\) points into \(k\) clusters, each represented by a centroid, by minimizing within-cluster squared distance:
\[ \min_{\{C_j\}}\ \sum_{j=1}^{k}\sum_{x\in C_j}\|x - \mu_j\|^2. \]
Lloyd’s algorithm alternates two cheap steps until stable: (1) assign each point to its nearest centroid; (2) recompute each centroid as its cluster’s mean. It is fast and ubiquitous, but assumes roughly spherical, equal-size clusters and needs \(k\) chosen in advance — and the result depends on initialization (k-means++ mitigates this).
43.2 PCA: variance-maximizing directions
PCA finds an orthogonal basis ordered by how much variance each direction captures. The principal components are the top eigenvectors of the covariance matrix \(\Sigma = \tfrac{1}{n}X^\top X\) (equivalently, the SVD of centered \(X\)):
\[ \Sigma v_i = \lambda_i v_i, \qquad \lambda_1 \ge \lambda_2 \ge \cdots \]
Projecting onto the top few components compresses the data while keeping most of its variance — useful for visualization, denoising, and preprocessing. PCA is a linear bottleneck; the autoencoder generalizes it to a non-linear one, and the geometry it studies (directions in a vector space carrying meaning) is the same geometry that makes word embeddings work.
43.3 Timeline context
These methods are the conceptual bridge to representation learning. PCA’s “meaningful directions in a learned space” became the distributed representations of Hinton’s work and then embeddings; clustering intuitions reappear in how trained embedding spaces organize semantically. Neural nets did not replace these — they learn the representation end-to-end rather than fixing it a priori, and k-means/PCA remain the go-to tools for exploratory analysis and compression.
← Back to: Classical ML Overview