k-means Clustering

Let the dataset be

$$X=\{x_1,\ldots,x_n\},\qquad x_i\in\mathbb R^d.$$

Choose a number of clusters $K$. k-means keeps two kinds of variables:

$$c_i \in \{1,\ldots,K\} \quad\text{and}\quad \mu_1,\ldots,\mu_K\in\mathbb R^d,$$

where $c_i$ is the cluster assigned to point $x_i$, and $\mu_k$ is the centroid of cluster $k$.

The objective is the within-cluster sum of squares:

$$J(c,\mu)=\sum_{i=1}^n \lVert x_i-\mu_{c_i}\rVert_2^2.$$

Assignment Step

If the centroids are fixed, point $x_i$ contributes only one term to the objective. The best assignment is therefore

$$c_i = \arg\min_{k\in\{1,\ldots,K\}} \lVert x_i-\mu_k\rVert_2^2.$$

This is the Voronoi step: every point joins the region of its nearest centroid.

Move Step

Now freeze the assignments. For one cluster, define

$$C_k=\{i:c_i=k\}.$$

The part of the objective that depends on $\mu_k$ is

$$J_k(\mu_k)=\sum_{i\in C_k}\lVert x_i-\mu_k\rVert_2^2.$$

Differentiate with respect to $\mu_k$:

$$\nabla_{\mu_k}J_k = 2\sum_{i\in C_k}(\mu_k-x_i).$$

Set this to zero:

$$2|C_k|\mu_k-2\sum_{i\in C_k}x_i=0,$$

so

$$\mu_k = \frac{1}{|C_k|} \sum_{i\in C_k}x_i.$$

The centroid moves to the mean of its assigned points.

What Is Guaranteed

The assignment step cannot increase $J$ because it chooses the nearest centroid for each point. The move step cannot increase $J$ because the mean minimizes squared distance for fixed assignments. Since there are only finitely many assignments, the algorithm eventually reaches a state where the assignments stop changing.

The catch is local optimality. Different initial centroids can lead to different final clusters. Also, the Euclidean norm makes feature scaling part of the model. If one coordinate is measured in kilometers and another in millimeters, the larger numeric scale can dominate the clustering unless preprocessing is chosen deliberately.