k-Means Clustering

k-means needs one number from you: k, how many groups you want. Then:

1. Initialize: place k centers, for example on k random data points.
2. Assign: each point joins the cluster of its nearest center.
3. Update: move each center to the average position of its points.
4. Repeat steps 2 and 3 until assignments stop changing.

Each round can only lower the total squared distance from points to their centers, so the algorithm always stops. But it may stop in a poor arrangement if the starting centers were unlucky. The usual fixes: run it several times and keep the best, or use k-means++, which spreads the initial centers out.

To choose k, people often plot the total distance for k = 1, 2, 3… and look for the “elbow” where adding clusters stops helping much.

The math

k-means minimizes the within-cluster sum of squares over assignments $C_1, \dots, C_k$ with centroids $\mu_j$:

$$\sum_{j=1}^{k} \sum_{x \in C_j} \lVert x - \mu_j \rVert^2$$