Unsupervised Learning¶
Unsupervised learning works with inputs \(\mathbf{x}_1, \dots, \mathbf{x}_n\) but no outcome variable. The aim is to discover structure: groups of similar observations (clustering) or compact representations of the data (dimensionality reduction). Typical applications include customer segmentation, anomaly detection and data visualization.
No ground truth
Without labels there is no direct way to check whether a result is correct. Whether a clustering is useful often depends on whether it can be interpreted in the subject-matter context. Clustering algorithms will produce groups even for data without any real group structure.
k-means¶
k-means partitions the data into \(k\) clusters \(C_1, \dots, C_k\) with centers \(\boldsymbol\mu_1, \dots, \boldsymbol\mu_k\) by minimizing the within-cluster sum of squares:
The standard algorithm, often called Lloyd's algorithm, alternates two steps until the assignments no longer change:
- Assignment: assign each point to its nearest center.
- Update: move each center to the mean of the points assigned to it.
The algorithm always converges, but only to a local optimum, so it is run from several starting points. The k-means++ initialization (Arthur & Vassilvitskii, 2007) chooses well-spread starting centers.
The number of clusters \(k\) must be chosen in advance, for example with the elbow method, the silhouette coefficient or domain knowledge. k-means works best for compact, roughly spherical clusters of similar size and is sensitive to outliers and to the scale of the features. Alternatives include Gaussian mixture models and the density-based DBSCAN.
Hierarchical clustering¶
Agglomerative hierarchical clustering starts with every observation in its own cluster and repeatedly merges the two closest clusters until only one remains. The result is a tree called a dendrogram. Cutting the dendrogram at a chosen height yields a clustering, so the number of clusters need not be fixed in advance.
The method depends on how the distance between two clusters is defined, the linkage:
| Linkage | Distance between clusters | Typical result |
|---|---|---|
| Single | smallest pairwise distance | elongated, chain-like clusters |
| Complete | largest pairwise distance | compact clusters |
| Average | average pairwise distance | a compromise |
| Ward | increase in within-cluster sum of squares | compact clusters, similar to k-means |
Standard implementations need memory and time that grow at least quadratically with \(n\), which limits the method to moderate data sizes.
Principal component analysis¶
Principal component analysis (PCA) finds new, uncorrelated axes, the principal components, ordered by how much of the data's variance they capture. For centered data \(\mathbf{X}\), the first principal component direction is
and each subsequent direction maximizes the remaining variance subject to being orthogonal to the previous ones. The directions are the eigenvectors of the covariance matrix, and the corresponding eigenvalues are the variances along them. In practice PCA is computed via the singular value decomposition (SVD) of \(\mathbf{X}\).
PCA is used for
- dimensionality reduction, since a few components often capture most of the variance,
- visualization, by projecting data onto the first two components,
- preprocessing, for example to remove noise or multicollinearity.
Standardize first
PCA depends on the units of measurement. A variable measured in euros will dominate one measured in years simply because of its larger numerical variance. Unless the variables share a common scale, standardize them to mean 0 and variance 1 before applying PCA.
Beyond linear methods
PCA only captures linear structure. Methods such as t-SNE and UMAP are popular for nonlinear visualization, and in deep learning, autoencoders and learned embeddings play a similar role (see Neural Networks).