ML7.2 · LESSON 2 OF 6

Centroid updates

Perform a clustering update and explain dimensionality reduction, mixtures and anomaly detection.

THE IDEA

Why the mean?

Assignments tell you who belongs together; now improve the centres. For one group of points, which single centre makes the sum of squared distances smallest? The mean. For the points 0 and 2, try centre 0.5: 0.25 + 2.25 = 2.5. Centre 1: 1 + 1 = 2. Centre 1.5: 2.25 + 0.25 = 2.5. The mean 1 wins, and the same is true in any number of dimensions.

So k-means alternates two moves, each of which can only lower (or keep) the objective J = Σ ‖xᵢ − μ_cᵢ‖²: assign (best groups for fixed centres) and update (best centres for fixed groups). This is Lloyd's algorithm. Step through the tiny example by hand:

Step 1 of 3

Assign. Give each point to its nearest centroid. Start: centres at 0 and 10, points 0, 2, 8, 10. Groups: {0, 2} and {8, 10}. Sum of squares: 0 + 4 + 4 + 0 = 8.

Watch it iterate

Place three starting centroids (or choose a start), then press Next step. Assign frames draw the lines; update frames move the squares to the means and show the arithmetic. The chart at the right is the sum of squares after every half-step. It only ever goes down, and the loop stops when an assignment changes nothing. This takes a few rounds on 24 points, not hundreds.

Starts:

Click the plot to place 3 starting centroids, or pick a start below it.

Run it. Dashed trails show where each centroid has been. Try the three ready-made starts.

Predict first. A cluster ends up with no points after an assign step. What should the update step do with its centroid?

The loop always stops, but not always at the best answer

Every step lowers J or leaves it unchanged, and there are only finitely many ways to split the points, so the loop must stop. It stops at a local optimum: nothing can be improved by one more assign or update. It need not be the best split. With one starting centroid in each blob the final sum of squares is 29.126 after 1 update. Start with the three centroids bunched at [[2,2],[3,3],[5,3]] and the loop converges to 138.273, about 4.7 times worse, with clusters of sizes 3, 5, 16: one blob was split and two were glued together. The fix in practice is cheap: run several different starts and keep the lowest J (this is what spreading initial centroids out, as k-means++ does, is for).

Choosing k: the elbow

J always shrinks when you add centroids (with k equal to the number of points, J is 0), so you cannot just pick the k with the smallest J. Instead plot the best J for each k and look for the elbow, where extra clusters stop paying for themselves. Here: k = 1: 297.9, k = 2: 146.3, k = 3: 29.1, k = 4: 21.1, k = 5: 16.1, k = 6: 12.1. Going from 2 to 3 clusters cuts J by 117.2; going from 3 to 4 only by 8.

k = 2

k = 2: sum of squares 146.31 k = 1 -> 2: drop of 151.58

Slide k and watch both the clusters and the bar chart. The bend is at k = 3 for this data, but real data often has no clean elbow.

Chapter context

Unsupervised methods expose structure according to their objectives and assumptions. They do not discover a single objectively correct organization of a dataset; changing distance, dimension or density assumptions can change the result.

TRY IT YOURSELF

Part 1. Do it on the plot

Place three starting centroids by clicking, or use the start buttons, then step until convergence. Best final sum of squares you can reach: 29.126.

Starts:

Click the plot to place 3 starting centroids, or pick a start below it.

To do: Place three starting centroids and press Next until the loop converges (an assign step that changes nothing)
To do: Converge to the best partition you know of (final within-cluster sum of squares equals the 3-blob optimum)
To do: Now make k-means converge to a clearly worse answer (final sum of squares more than 1.5 times the best) by starting badly
To do: Converge after a single update (one assign, one update, then an assign that changes nothing)

Part 2. Do it in code

update(X, labels, C) returns a NEW array of centroids: each is the mean of the points assigned to it. A cluster with no points keeps its old centroid (never divide by zero, never return nan).
kmeans(X, C0, max_iter=100) runs the loop from the starting centroids C0. Each round: assign (nearest centroid, ties to the lowest index), record the within-cluster sum of squares, and stop if the labels did not change; otherwise update and repeat.
Return (labels, centroids, history) where history is the list of sums of squares recorded at every assignment. It must never go up. Do not modify C0.

import numpy as np

def update(X, labels, C):
    # mean of each cluster; keep the old centroid when a cluster is empty
    pass

def kmeans(X, C0, max_iter=100):
    # return (labels, centroids, history)
    pass

X = np.array([[0.0], [2.0], [8.0], [10.0]])
print(kmeans(X, np.array([[0.0], [10.0]])))

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

What is the updated center for [0,2]?

AOne, because the mean of 0 and 2 is (0 + 2) / 2.BTwo, because the update takes the largest point in the group.CZero, because the centre stays where it started after the first update.

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

J=\sum_i\|x_i-\mu_{c_i}\|^2,\quad \mu_k=\frac1{|C_k|}\sum_{i\in C_k}x_i.

For centered data X, PCA uses leading eigenvectors of $X^TX/(n-1)$ , or an equivalent SVD. Centering and feature scaling are separate choices.

For a Gaussian mixture, EM responsibilities are

r_{ik}=\frac{\pi_k\mathcal N(x_i\mid\mu_k,\Sigma_k)}{\sum_j\pi_j\mathcal N(x_i\mid\mu_j,\Sigma_j)}.

Mixing weights pi are nonnegative and sum to one; each row of responsibilities also sums to one. Weighted sufficient-statistic updates differ from hard k-means assignments.

Worked example

With points [0,2,8,10] and starting centers [0,10], assignments are [0,2] and [8,10]. Updated means are 1 and 9. Squared errors are 1,1,1,1, totaling 4. This example gives one iteration; it does not prove that every initialization finds the best partition.

Reference code

The following example uses the Python standard library and does not call a remote service.

points, centers = [0,2,8,10], [0,10]
groups = [[x for x in points if min(range(2), key=lambda j: (x-centers[j])**2) == i] for i in range(2)]
updated = [sum(group)/len(group) for group in groups]
assert updated == [1,9]
assert sum((x-c)**2 for group,c in zip(groups,updated) for x in group) == 4

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Clusters are objective-dependent. PCA maximizes variance, which may not correspond to useful semantic structure. Anomaly detection is not the same as identifying known fraud classes.