Unsupervised learning

The k-means objective#

K-means minimises within-cluster sum of squares (WCSS), also called inertia.

minimise  J = SUM_{j=1..k}  SUM_{x in C_j}  || x - mu_j ||^2

• k — number of clusters, fixed in advance
• C_j — the set of points assigned to cluster j
• mu_j — the centroid of cluster j, equal to the mean of the points in C_j
• || . || — Euclidean (L2) norm

This objective explains the method's behaviour completely. Squared Euclidean distance is why k-means prefers spherical, equal-variance clusters. It is also why the method is sensitive to feature scale, and why single outliers move centroids so much.

Lloyd's algorithm and its cost#

The standard solver alternates two steps until assignments stop changing.

repeat:
   assignment step:  C_j  <- { x : argmin_j || x - mu_j ||^2 }
   update step:      mu_j <- mean( C_j )

Each step never increases J, and the number of distinct assignments is finite, so the algorithm terminates. It terminates at a local minimum. It has no guarantee of reaching the global one.

Cost per iteration:  O(n * k * d)
Total:               O(n * k * d * i)

• n — number of points
• k — number of clusters
• d — number of dimensions
• i — iterations to convergence, typically small in practice

Exact k-means is NP-hard for k >= 2 in general dimension (Aloise et al., 2009; Dasgupta, 2008). Worst-case iteration counts are superpolynomial (Arthur & Vassilvitskii, 2006). Smoothed analysis explains why practice is nonetheless fast (Arthur, Manthey & Röglin, 2011).

k-means++ (Arthur & Vassilvitskii, 2007) seeds centroids with probability proportional to squared distance from the nearest existing centroid. It gives an expected O(log k)-competitive solution and is the default initialisation in scikit-learn.

Model-based alternatives#

Gaussian mixture models replace hard assignment with a probabilistic generative model.

p(x) = SUM_{j=1..k}  pi_j * N( x | mu_j, Sigma_j )

• pi_j — mixing weight of component j, non-negative and summing to one
• mu_j — mean vector of component j
• Sigma_j — covariance matrix of component j, allowing elliptical, differently-oriented clusters
• N — the multivariate normal density

Fitted by Expectation-Maximisation (Dempster, Laird & Rubin, 1977), which monotonically increases the likelihood lower bound. K-means is the limiting case of EM on a GMM. Take isotropic covariance sigma^2 * I, let sigma -> 0, and use hard assignment.

Density-based methods make different assumptions again. DBSCAN (Ester et al., 1996) defines clusters as maximal density-connected sets under parameters eps and minPts. It discovers k rather than requiring it, handles non-convex shapes, and labels low-density points as noise. HDBSCAN (Campello et al., 2013) removes the global eps by building a hierarchy over varying density.

Dimensionality reduction#

The second major family compresses rather than groups.

A caution worth repeating: t-SNE and UMAP plots invite over-reading. Cluster sizes, inter-cluster distances, and empty space are largely artefacts of the algorithm's parameters (Wattenberg, Viégas & Johnson, 2016). Never draw a conclusion from a t-SNE picture without confirming it in the original space.

Evaluation without ground truth#

Internal indices score geometry rather than correctness.

Silhouette(i) = ( b(i) - a(i) ) / max( a(i), b(i) )

• a(i) — mean distance from point i to other points in its own cluster
• b(i) — mean distance from point i to points in the nearest other cluster
• Result lies in [-1, 1]; values near 1 indicate a well-separated point

Other internal indices include Davies-Bouldin (1979) and Calinski-Harabasz (1974). All of them encode a geometric prior, and all favour the cluster shapes their own definition assumes. Silhouette computed with Euclidean distance will reliably prefer k-means output over DBSCAN output, regardless of which is more useful.

When labels do exist for validation, use Adjusted Rand Index (Hubert & Arabie, 1985) or Adjusted Mutual Information. Both are corrected for chance agreement.

Current state#

Classical clustering is no longer where the field's attention sits. The dominant modern form of unsupervised learning is self-supervised representation learning, which invents a prediction task from unlabelled data.

• Contrastive objectives: SimCLR (Chen et al., 2020), MoCo (He et al., 2020), and InfoNCE from CPC (van den Oord et al., 2018).
• Non-contrastive: BYOL (Grill et al., 2020), which avoids negative pairs. Also DINO (Caron et al., 2021), whose attention maps segment objects without any segmentation labels.
• Masked reconstruction: BERT (Devlin et al., 2019) for text, MAE (He et al., 2022) for images.

Language model pretraining is the largest unsupervised learning system ever deployed. Next-token prediction requires no human labels, which is exactly why it scaled.

The practical relationship to clustering has inverted. Current practice does not cluster raw features. It learns a representation self-supervised, then clusters in that embedding space. Euclidean distance is far more meaningful there than in the original coordinates.

Key references#

• Lloyd, S. (1982). Least Squares Quantization in PCM. IEEE Trans. Information Theory. Written in 1957, published in 1982.
• Arthur, D. & Vassilvitskii, S. (2007). k-means++: The Advantages of Careful Seeding. SODA.
• Ester, M., Kriegel, H.-P., Sander, J. & Xu, X. (1996). A Density-Based Algorithm for Discovering Clusters. KDD.
• Dempster, A., Laird, N. & Rubin, D. (1977). Maximum Likelihood from Incomplete Data via the EM Algorithm. JRSS-B 39(1).
• Rousseeuw, P. (1987). Silhouettes: A Graphical Aid to the Interpretation and Validation of Cluster Analysis. J. Comp. Appl. Math. 20.
• Chen, T. et al. (2020). A Simple Framework for Contrastive Learning of Visual Representations. ICML.

What to learn next#

• Clustering — algorithm-level detail and selection criteria.
• Embeddings — the representation spaces modern clustering operates in.
• Autoencoders — unsupervised representation learning by reconstruction.