K-means: what its clusters look like, where to start, how many

Part 6 showed that Lloyd's algorithm always converges. The next question is what the clusters it converges to look like. Start with the simplest case, \(K = 2\): the algorithm stops with two clusters whose means are \(\boldsymbol\mu_1\) and \(\boldsymbol\mu_2\).

Convergence means every point is happy with its own mean. A point in cluster 1 must be at least as close to \(\boldsymbol\mu_1\) as to \(\boldsymbol\mu_2\), in squared distance. If it were closer to \(\boldsymbol\mu_2\), the next reassignment would move it and the algorithm would not have stopped. So for every \(\mathbf{x}\) in cluster 1:

Expand each side with \(\lVert\mathbf{a}-\mathbf{b}\rVert^2 = \lVert\mathbf{a}\rVert^2 + \lVert\mathbf{b}\rVert^2 - 2\mathbf{a}^\top\mathbf{b}\):

The \(\lVert\mathbf{x}\rVert^2\) terms cancel. Move \(-2\,\mathbf{x}^\top\boldsymbol\mu_2\) to the left, \(\lVert\boldsymbol\mu_1\rVert^2\) to the right, and divide by 2:

To see which points satisfy the condition, start from the vector \(\mathbf{w} = \boldsymbol\mu_2 - \boldsymbol\mu_1\), the step you add to \(\boldsymbol\mu_1\) to reach \(\boldsymbol\mu_2\), drawn from the origin.

1. The points with \(\mathbf{x}^\top(\boldsymbol\mu_2 - \boldsymbol\mu_1) = 0\) have zero dot product with \(\mathbf{w}\). They form the line through the origin at right angles to \(\mathbf{w}\) (line ① below).
2. Asking instead for \(\mathbf{x}^\top(\boldsymbol\mu_2 - \boldsymbol\mu_1) = b\) moves that line parallel to itself, along \(\mathbf{w}\). In the lecture's picture \(\lVert\boldsymbol\mu_2\rVert\) is larger than \(\lVert\boldsymbol\mu_1\rVert\), so \(b > 0\) and the line moves toward \(\boldsymbol\mu_2\) (line ②). Whether \(b\) is positive or negative depends on which mean is longer.
3. Cluster 1 is the side of line ② where \(\mathbf{x}^\top\mathbf{w} \le b\), the side that contains \(\boldsymbol\mu_1\). Cluster 2 is the other side.

How far did the line move? Find one point on it. The average of the two means works:

The cross terms cancel because \(\boldsymbol\mu_1^\top\boldsymbol\mu_2 = \boldsymbol\mu_2^\top\boldsymbol\mu_1\). So line ② passes through the midpoint of the two means and is at right angles to the segment joining them: it is the perpendicular bisector of that segment. This is also the direct way to see it. Join the two means, draw the perpendicular bisector, and every point on one side is closer to the mean on that side.

With K = 2, the converged K-means clusters are always separated by a straight line (a hyperplane in \(\mathbb{R}^d\)). This follows from the convergence condition alone.

With \(K = 3\) the algorithm converges with three means \(\boldsymbol\mu_1, \boldsymbol\mu_2, \boldsymbol\mu_3\). The data is drawn in two dimensions to make it visible; nothing in the argument depends on the dimension.

A point in cluster 1 must be closer to \(\boldsymbol\mu_1\) than to \(\boldsymbol\mu_2\) and closer to \(\boldsymbol\mu_1\) than to \(\boldsymbol\mu_3\). If either failed, the point would jump to the other cluster and the algorithm would not have converged.

• Closer to \(\boldsymbol\mu_1\) than to \(\boldsymbol\mu_2\): the \(\boldsymbol\mu_1\) side of the perpendicular bisector of \(\boldsymbol\mu_1\) and \(\boldsymbol\mu_2\).
• Closer to \(\boldsymbol\mu_1\) than to \(\boldsymbol\mu_3\): the \(\boldsymbol\mu_1\) side of the bisector of \(\boldsymbol\mu_1\) and \(\boldsymbol\mu_3\). Since \(\boldsymbol\mu_3\) need not lie on the line through \(\boldsymbol\mu_1\) and \(\boldsymbol\mu_2\), this is a different line.
• Cluster 1's region is the intersection of the two sides.

The bisector of \(\boldsymbol\mu_2\) and \(\boldsymbol\mu_3\) then splits what is left: the region of \(\boldsymbol\mu_2\) (closer to \(\boldsymbol\mu_2\) than to both others) and the region of \(\boldsymbol\mu_3\). There are three separators, one for each pair of means.

One side of a line is a half-space: the line divides the plane in two, and each half is a half-space. In higher dimensions a hyperplane plays the role of the line. Every mean is compared with the \(K - 1\) other means, so:

Regions built this way, one per centre, each holding the points closer to that centre than to any other, are called Voronoi regions, and together they form a Voronoi partition of the space. The argument above holds in any dimension. So the clusters produced by Lloyd's algorithm always sit in the Voronoi regions of their own means, and Lloyd's algorithm can be read as a search for a good Voronoi partition: one whose clusters have a small objective.

Try it below. Drag the means and the regions follow. One Lloyd step moves every mean to the average of the points in its region, the update from Part 6; the points then fall into the regions of the new means.

The geometry also tells us when K-means will fail. Take two-dimensional data on two concentric circles: a ring of points around a smaller circle of points. The natural clustering has two clusters, the outer ring and the inner circle.

Run Lloyd's algorithm with \(K = 2\). It converges, as always. But the two clusters must lie in Voronoi regions, so a line separates them. Exactly where the line falls depends on how the points are spaced (it need not be slanted; it could be vertical), but it is a line, and no line can put the whole ring on one side and the inner circle on the other, because the ring surrounds the inner circle. K-means as described can never return the inner/outer split.

If you do not expect your clusters to sit in Voronoi-like regions, expect K-means to fail on that data.

Standard fact, not from the lecture: an intersection of half-spaces is convex, so every K-means cluster region is convex. A ring is not convex, so no choice of K can return the ring as one cluster.

The fix, in outline L16 · 21:11

The course does not develop this, but the lecture gives pointers. Recall Part 5: when features are related non-linearly, map the data to a higher-dimensional space, find linear structure there, and it becomes non-linear structure in the original space. The same idea applies to clustering. The data may have no natural Voronoi structure in its own space, yet after a suitable map to a high-dimensional space its natural clusters may fall into different Voronoi regions, where plain Lloyd's algorithm works. The kernel trick avoids the cost of computing that map. The result is called kernel K-means.

Kernel K-means is closely related to computing eigenvectors of the kernel matrix and using them as a new representation of the data points, which are then clustered. It is also related to a popular method called spectral clustering, which in turn has much in common with PCA. Neither is covered in this course. 21:45

Two issues about Lloyd's algorithm remain: how to initialize it, and how to choose the number of clusters. 22:49

The convergence argument in Part 6 never used the starting point, so Lloyd's algorithm converges however it is initialized. Where it converges does depend on the start, because it can get stuck in a local minimum. A good initialization gives it a better chance of ending in good clusters. The lecture discusses these options:

• Random boxes. Put each data point into one of the K clusters uniformly at random. The algorithm still converges, but this ignores the structure of the data and gives no initial push to escape poor local minima.
• Random data points as means. Pick K data points uniformly at random and treat them as the initial means. This initializes the means rather than the cluster indicators. Every other point then joins its closest mean, so at least the start has the property we want at the end: each point sits with its nearest mean. With 1000 points and K = 5, the means might be data points number 5, 72, 89, 22 and one more; each of the other 995 points goes to the nearest of these five. This is not yet a converged state: the means are recomputed from the new clusters and Lloyd's algorithm carries on. In practice this is what is typically done.
• Restarts. The K random points may be an unlucky pick. So repeat the whole run with fresh random picks several times and keep the clustering with the best (lowest) objective value.

1. Random initialization with restarts
2. Repeat several times:
3. Pick K data points uniformly at random as the initial means.
4. Assign every point to its nearest mean, then run Lloyd's algorithm to convergence.
5. Record the final partition and its objective \(\sum_{i=1}^n \lVert\mathbf{x}_i - \boldsymbol\mu_{z_i}\rVert^2\).
6. Return the partition with the smallest objective.

A more principled option is K-means++, which is the usual K-means (Lloyd's) algorithm with a better initialization. It still starts from K data points, but picks them with care.

What should good initial means look like? At convergence the means represent the clusters: the whole data set is compressed into K representatives. Representatives should be as different from each other as possible. If two of them were close, two clusters would describe nearly the same thing, and one cluster would do. So K-means++ starts with means that are far apart, with a probabilistic twist, and it picks them one at a time instead of all at once.

1. K-means++ initialization (superscript 0 marks the initial means)
2. Pick the first mean \(\boldsymbol\mu^0_1\) uniformly at random from \(\{\mathbf{x}_1, \dots, \mathbf{x}_n\}\).
3. For \(l = 2, \dots, K\):
   • Give every data point the score \(s(\mathbf{x}) = \min_{j = 1, \dots, l-1} \lVert \mathbf{x} - \boldsymbol\mu^0_j \rVert^2\), its squared distance to the closest mean picked so far.
   • Pick \(\boldsymbol\mu^0_l\) at random from the data points, choosing \(\mathbf{x}_i\) with probability \(s(\mathbf{x}_i) \,/\, \sum_{m=1}^n s(\mathbf{x}_m)\).
4. Run Lloyd's algorithm starting from \(\boldsymbol\mu^0_1, \dots, \boldsymbol\mu^0_K\).

Why the minimum? The distance to the closest chosen mean measures how far a point is from all of them: if even the closest one is far away, every chosen mean is far away. A point that has already been picked has score 0, so it cannot be picked twice. Standard name: sampling in proportion to this squared distance is called D² sampling.

Sampling in proportion to a score L17 · 8:50

Scores become probabilities by dividing each by their total. Suppose only three points remain, with scores 10, 20 and 30. The total is 60, so:

With 1000 points and 5 means already picked, the other 995 points are the candidates for the sixth mean, and the same normalization turns their 995 scores into a probability distribution to sample from.

Why not simply take the point with the largest score, the one whose nearest chosen mean is farthest away? In the example that rule always picks \(\mathbf{x}_3\). Under K-means++, \(\mathbf{x}_3\) is still the most likely pick (probability 1/2), but \(\mathbf{x}_2\) or even \(\mathbf{x}_1\) can be chosen.

The randomness is what makes a guarantee possible. For any deterministic rule one can build an adversarial data set on which the guarantee fails. A randomized rule can instead promise something on average. K-means++ does the natural thing: the point the deterministic rule would choose gets the highest probability, and every other point still gets some.

Run K-means++ and then Lloyd's algorithm. Once the initial means are fixed, Lloyd's algorithm is deterministic. The initial means are random, though, so the final objective value is a random quantity. The guarantee compares its expected value, over the random initialization, with the best objective any partition can achieve.

Standard result, beyond the lecture (Arthur and Vassilvitskii, 2007): the factor is \(c = 8(\ln K + 2)\), so it grows only slowly with K. It already holds for the initial means alone, and Lloyd's iterations can only lower the objective from there.

The cost L17 · 17:07

The price is time. Each of the K rounds computes a score for every data point, normalizes the scores and samples. With a billion points and 10 means, that is 10 passes over a billion points before Lloyd's algorithm even starts. There are tricks to speed this up, but the K rounds remain.

Picking K points uniformly at random, and trying several times, is faster, but it is not principled: nothing pushes the means apart. Even so, in practice, especially with high-dimensional data, the uniform method is used extensively. The choice depends on how much time and computing you have. K-means++ is a solid way to initialize when you can afford it. 17:41

In practice nobody gives you K. You get data points, and usually you do not know how many natural clusters they contain, so K has to be chosen from the data. The lecture gives broad principles. The specific methods are all heuristics, there are more of them than one lecture can cover, and some are worked through in tutorial sessions.

Could the objective itself choose K? Recall

Take \(K = n\). Every data point is its own cluster and its own mean, every term is 0, and \(F = 0\), the smallest value \(F\) can take. If K were chosen by minimizing \(F\) as well, \(K = n\) would always win. That is useless: a separate cluster for every point is hardly a clustering, and it compresses nothing.

So two goals pull in opposite directions. For a fixed K we still want the partition that minimizes \(F\), or gets as close as we can. But we also want K small, because the point is to understand the data in compressed form. A larger K always allows a lower objective, so the objective alone cannot decide K.

For each candidate K, measure two things: the objective of the partition the algorithm returns, and how big K is. Then penalize large K:

\(F_K\) is the objective of the best partition found with K clusters, and \(\text{penalty}(K)\) is an increasing function of K that we choose.

Think of the penalty as the price of buying one more cluster. Going from \(K = 5\) to \(K = 6\) costs \(\text{penalty}(6) - \text{penalty}(5)\). With more clusters, clusters typically get smaller and points get closer to their means, so the objective drops. The purchase is worth it only if it drops by more than the price. From \(K = 1\) to \(K = 2\) the drop is usually large, since with one cluster nothing is really being clustered. As K grows, the price keeps rising while the extra drop shrinks, and somewhere the two balance.

This is the lecture's sketch: against \(K = 1, 2, \dots, n\), the objective falls and reaches 0 at \(K = n\), the penalty rises, and their sum falls at first until the penalty takes over and it starts to rise. The K at the bottom is the choice.

1. Choosing K by objective + penalty
2. For each candidate K, run Lloyd's algorithm. Any initialization works: K-means++, or uniform random starts run several times.
3. Keep the best partition for that K and its objective \(F_K\).
4. Compute \(F_K + \text{penalty}(K)\).
5. Choose the \(K^*\) with the smallest sum.

What the procedure leaves open is the penalty function itself. That is where specific criteria come in.

Two common criteria of the form "objective plus penalty":

Here \(\mathcal{L}\) is a likelihood: roughly, how probable the observed data is under parameters estimated from that data. The term \(-2\ln\mathcal{L}\) plays the part of the objective, measuring how well the model fits, and the other term is the penalty on K. Both penalties grow linearly in K. BIC's also grows with the number of points, through \(\ln n\).

Each criterion is optimal under a different assumption about how the data is generated probabilistically. With such an assumption you can measure fit in a more nuanced way than the K-means objective, through the likelihood. The course has not yet modelled data probabilistically, so the lecture leaves the details for later. Estimation starts in Part 8, and the lecture plans to revisit model selection once that is in place.

Standard definitions: the K in AIC and BIC counts the free parameters of the probabilistic model. For a clustering model that number grows with the number of clusters.

These criteria are not set in stone. The elbow method and other choices are also common in practice. The lecture only names the elbow method. Standard description: plot the objective against K and pick the K where the curve bends from steep to flat. In the figure above that is \(K = 4\).

Run the algorithm for several values of K, then pick K with a criterion that balances the objective against a penalty on K.

That completes the discussion of Lloyd's algorithm. The four questions posed about it in Part 6 now all have answers:

This ends clustering. So far the course has been about unsupervised learning: representation learning (PCA and kernel PCA) and clustering, with K-means as the main example. The next topic, estimation, continues with unsupervised learning, but it will later apply to supervised learning too, so it acts as a bridge between the two.

Convergence condition

At convergence every point is at least as close to its own mean as to any other mean.

Perpendicular bisector

The line (hyperplane) through the midpoint of two means at right angles to the segment between them; the K = 2 boundary.

Half-space

One side of a line in \(\mathbb{R}^2\), or of a hyperplane in \(\mathbb{R}^d\): \(\{\mathbf{x} : \mathbf{x}^\top\mathbf{w} \le b\}\).

Voronoi region

The set of points closer to one centre than to every other; an intersection of \(K-1\) half-spaces. K-means clusters lie in them.

Kernel K-means

K-means run in a high-dimensional feature space via the kernel trick, so clusters can be non-linear in the original space.

Local minimum

A partition Lloyd's algorithm cannot improve on by its own steps, though better partitions exist.

Random initialization

Start from K data points picked uniformly at random as the means.

Restarts

Run from several random starts and keep the partition with the lowest objective.

K-means++

Lloyd's algorithm with initial means picked one at a time by D² sampling.

Score / D² sampling

\(s(\mathbf{x}) = \min_j \lVert\mathbf{x} - \boldsymbol\mu^0_j\rVert^2\); the next mean is \(\mathbf{x}_i\) with probability \(s(\mathbf{x}_i)/\sum_m s(\mathbf{x}_m)\).

Penalty on K

An increasing function of K added to the objective so that extra clusters must pay for themselves.

AIC

Akaike information criterion, \(2K - 2\ln\mathcal{L}\): penalty linear in K.

BIC

Bayesian information criterion, \(K\ln n - 2\ln\mathcal{L}\): penalty grows with K and with \(\ln n\).

Elbow method

Pick the K where the objective-versus-K curve bends from steep to flat.