3.1. K-Means

K-Means Clustering

K-Means is a clustering algorithm that finds $K$ cluster centers ${\mu }_k\in {\mathbb{R}}^D$ and assigns each data point $x_n\in {\mathbb{R}}^D$ to one cluster $z_n\in \{1,\dots ,K\}$, such that the total within-cluster squared error is given by the objective function
$\arg {\min }_{\mu ,z}{\sum }_{n=1}^N\Vert x_n-{\mu }_{z_n}{\Vert }_2^2.$

The optimal clusters ${\mu }^{\ast }$ are found programmatically using Lloyd’s Algorithm. Start by randomly choosing $K$ data points as initial cluster centers. Then, repeat until until cluster assignments stop changing, such that $z^{(t)}=z^{(t-1)}$:

1. Assign each data point $x_n$ to its nearest cluster center $z_n$, such that $z_n=\arg {\min }_k\Vert x_n-{\mu }_k{\Vert }_2^2$
2. Recompute each cluster center as the mean of its assigned points:
   ${\mu }_k=\frac{1}{N_k}{\sum }_{i=1}^{N_k}{x}_{k_i}.$

K-Means is guaranteed to converge, because alternating minimization of assignments ($z$) and centers ($\mu$) never increases the objective. Most often, the hyperparameter $K$ is chosen using the elbow method by plotting the K-Means objective vs. $K$ and choosing the point where improvement sharply decreases (i.e., “the elbow”).

Proof

Mathematical Derivation (Optional Detail)

To minimize

\sum_{n=1}^N |x_n - \mu_{z_n}|2

we rearrange by cluster:

\sum{k=1}^{K}\sum_{i=1}^{N_k}\sum_{d=1}^{D}(x_{k_i,d}-\mu_{k,d})

Taking the derivative w.r.t. \mu_{k,d} and setting to zero:

\mu_{k,d} = \frac{1}{N_k}\sum_{i=1}

→ Each cluster center is the mean of its assigned points.

Prove Lloyd correctness and convergence guarantee