Content
Summary
k-means clustering partitions unlabeled data points into k groups by repeatedly assigning each point to its nearest cluster center and then moving each center to the mean of its assigned points. It stops when assignments no longer change. It is a simple way to find structure in data such as patient subgroups or gene expression patterns.
Intuition
Imagine scattering k pins on a map of data points. Each point joins the group of the nearest pin. Then each pin slides to the center of mass of its group. Because pins moved, some points are now closer to a different pin, so groups are redrawn, and the pins slide again. This back-and-forth always reduces the total squared distance from points to their pins, until nothing changes. The result is compact groups, but it depends on where the pins started, so it may settle on a local rather than global optimum.
Key equations
Assignment step: point x_i joins the cluster whose center mu_j is nearest.
Update step: each center becomes the mean of the points S_j assigned to it.
Objective: within-cluster sum of squared distances, which k-means decreases at every step.
Derivation
- Goal: choose centers and assignments that minimize J.
- Fix the centers. J is minimized by giving each point to its nearest center, since each point's term is smallest there. This is the assignment step.
- Fix the assignments. For one cluster, set the derivative of the sum of squared distances with respect to mu_j to zero: -2 times the sum of (x_i - mu_j) equals 0.
- Solving gives mu_j equal to the average of the points in S_j. This is the update step.
- Each step cannot increase J, and there are finitely many possible assignments, so the algorithm converges, though possibly to a local minimum.
Worked example
One-dimensional data: 1, 2, 3, 10, 11, 12. Use k=2 with initial centers 1 and 2. Run k-means to convergence.
- Iteration 1 assignment: 1 goes to center 1. 2 goes to center 2. 3 is nearer 2 (distance 1 versus 2). 10, 11, 12 go to center 2.
- Update: cluster A = {1}, mean 1. Cluster B = {2,3,10,11,12}, mean 38/5 = 7.6.
- Iteration 2 assignment: 1 goes to A. 2 is 1 from A and 5.6 from B, so A. 3 is 2 from A and 4.6 from B, so A. 10, 11, 12 go to B.
- Update: A = {1,2,3}, mean 2. B = {10,11,12}, mean 11.
- Iteration 3: assignments are unchanged, so the algorithm stops.
Answer Clusters {1,2,3} and {10,11,12} with centers 2 and 11.
Common mistakes
- Forgetting that results depend on the initial centers; run several random starts or use k-means++.
- Not scaling features, so a variable with large units dominates the distance.
- Assuming k-means finds non-spherical or very unequal-sized clusters correctly.
- Treating the chosen k as known; it must be selected, for example with the elbow method or silhouette score.
- Believing convergence means the global best solution.