K-Means Clustering

Definition

The k-means clustering algorithm solves the following optimization problem $\underset{\mathbf{S}}{\min }\sum _{k=1}^K\sum _{x_i\in S_i}||x_i-m_k|{|}^2$ where $K$ is the number of clusters, a Partition $\mathbf{S}=\{S_k|k=1,\dots ,K\}$ is a set of clusters, and $m_k=\frac{1}{|S_k|}\sum _{x_i\in S_i}{x}_i$ The k-means clustering algorithm aims to partition observations into clusters in which each observation belongs to the cluster with the nearest mean.

Algorithm

1. Initialize $\{m_i^{(1)}|i=1,\dots ,K\}$.

2. Assignment step: Assign each observation to the cluster with the nearest mean

   $S_i^{(t)}=\left\{x_p|\underset{1\le j\le K}{\mathrm{argmin}}||x_p-m_j^{(t)}|{|}^2\right\}$ where each $x_p$ is assigned to exactly one $S_i^{(t)}$

3. Update step: Recalculate means for observations assigned to each cluster. $m_i^{(t+1)}=\frac{1}{|S_i^{(t)}|}\sum _{x_j\in s_i^{(t)}}{x}_j$

4. Iterate step 2 and 3 until the within cluster variation converges.

Facts

The k-means clustering uses spherical metric (Euclidean distance) to group data, so that it is useful only when clusters are convex sets.