Starting K-Means and Choosing K

Lloyd's algorithm always converges, but where it converges depends on where it starts. This chapter settles the two remaining practical questions: how to start it, and how many clusters to ask for.

Starting badly

The crudest start is to throw every point into a random cluster. Every cluster then contains points from all over the data, so all the initial means land near the overall centre, close together, and the algorithm has to untangle everything from there.

A better and very common start is to pick $K$ data points at random and use them as the initial means. Each point then joins its nearest chosen point, and Lloyd's algorithm continues as usual. The danger is luck: if two of the chosen points fall in the same natural group, that group may end up split in two while two other groups are merged. The standard remedy is cheap: run the algorithm several times from different random starts and keep the run with the lowest objective.

k-means++

k-means++ chooses the starting means one at a time, deliberately spreading them out.

1. Pick the first mean uniformly at random from the data.
2. For each remaining point $x$, compute its score: the squared distance to the nearest mean chosen so far, $s(x) = \min_{j < \ell} \lVert x - \mu_j \rVert^2 .$
3. Pick the next mean at random, with each point chosen with probability proportional to its score, $s(x) / \sum_{x'} s(x')$.
4. Repeat until $K$ means are chosen, then run Lloyd's algorithm.

Points far from every existing mean have large scores and are likely to be picked; points already well covered (including the chosen means themselves, whose score is zero) are unlikely. If three candidate points have scores 10, 20 and 30, they are picked with probabilities $\tfrac{1}{6}, \tfrac{1}{3}$ and $\tfrac{1}{2}$.

Why randomise, instead of always taking the farthest point? A deterministic "farthest point" rule is easily fooled by an outlier: one stray point far from everything would always be chosen as a centre. Sampling in proportion to squared distance still strongly favours far points, but a single outlier carries only a small share of the total score when many points are moderately far.

The randomness also makes a guarantee possible. Arthur and Vassilvitskii (2007) proved that the expected objective after the k-means++ initialisation alone is at most $8(\ln K + 2)$ times the optimal objective:

That is an $O(\log K)$ factor, not a constant, but it holds for every data set, and the Lloyd iterations that follow can only improve on it. The cost is time: each new centre needs a pass over all points to update their scores, so initialisation takes $K$ passes over the data. Even so, k-means++ is the default in most libraries, usually combined with several restarts.

Choosing K

The objective cannot choose $K$ by itself. More clusters always help: with $K = n$ every point is its own cluster, its own mean, and the objective is exactly zero. Minimising the objective over $K$ would always return "every point is a cluster", which is useless. The point of clustering is compression, and a good $K$ is a small one that still fits well.

So we trade fit against size. Run the algorithm for $K = 1, 2, 3, \dots$, record the best objective $F(K)$ for each, and pick the $K$ that minimises

where the penalty grows with $K$. Each extra cluster is a "purchase": it is worth buying only if it lowers the objective by more than the extra penalty. Going from one cluster to two usually cuts the objective sharply, which easily pays for the extra cluster; going from nine clusters to ten usually saves little.

Common ways to set the trade-off:

• The elbow. Plot $F(K)$ against $K$ and look for the point where the curve stops falling steeply and flattens. It is an informal, visual penalty.
• Information criteria. If the clusters are given a probabilistic model (as Gaussian mixtures will be in Module 5), the fit is measured by the log-likelihood $\ln \hat L$ and the size by the number of free parameters $p$ in the model, which grows with $K$: $\text{AIC} = 2p - 2\ln \hat L, \qquad \text{BIC} = p \ln n - 2\ln \hat L .$ Choose the $K$ with the smallest value. BIC's penalty grows with the sample size $n$, so it favours fewer clusters than AIC on large data sets.
• Silhouette and gap statistics. Other criteria compare how close points are to their own cluster with how close they are to the next nearest, or compare the curve with what random data would give.

All of these are heuristics; none can tell you the "true" number of clusters, because in unsupervised learning that depends on what the clusters are for.