K-Means Clustering

Assign to nearest centroid, move centroid to the mean, repeat.

The idea

K-means is the basic algorithm for clustering: given $n$ points and a number $k$, it seeks $k$ centroids, and an assignment of every point to one of them, making $\sum_{i=1}^{n} \lVert x_{i} - \mu_{c(i)} \rVert^{2}$ as small as possible, where $c(i)$ names the cluster of point $x_{i}$ and $\mu_{c(i)}$ is that cluster's centroid. The number of possible assignments is far too large to search, so the algorithm improves a guess instead, alternating two steps that each hold half of the problem fixed.

Algorithm.

Algorithm: K-Means Input: points x_1, ..., x_n, cluster count k, initial centroids μ_1, ..., μ_k Output: an assignment of points to clusters, and the k centroids 1. assignment: with centroids fixed, assign each point to its nearest centroid 2. update: with assignments fixed, move each centroid to the mean of its points 3. if no point changed cluster, return the assignment and centroids 4. go to step 1

Neither step increases the objective. Each point contributes its own squared distance to the total, so reassigning it to a nearer centroid (step 1) can only lower the total; and among all locations, the mean minimizes the sum of squared distances to a fixed set of points, so recomputing centroids (step 2) cannot raise it either. Moving the centroids can change which one is nearest, which is why the next assignment pass may switch some points to a different cluster. There are finitely many assignments, so the loop halts: eventually a pass moves no point, and nothing changes after that. The result is a local minimum, not necessarily the best one, and different starting centroids can lead to different results.

Ways to work on it

• Walkthrough. The assignment/update loop and the inertia objective.
• Practice. Run the update step: centroid = cluster mean.
• Hardest. A 2D update plus initialization and choosing k.

Not sure where to start? Take the ten-question placement test.