Relationship between K-means and Expectation Maximization Algorithms

K-means is a simplified version of the Expectation-Maximization (EM) algorithm.

• E-step (Expectation): This is the assignment step. For fixed prototypes, each data point is assigned to the nearest cluster. This is equivalent to calculating which cluster is “expected” for each point. $r_{nk}=\{\begin{array}{ll}1& \text{if }k={\text{argmin}}_j||x_n-w_j|{|}^2\\ 0& \text{otherwise}\end{array}$
• M-step (Maximization): This is the update step. With the cluster assignments fixed, the prototypes are moved to the mean of their assigned data points. This new position maximizes the similarity to the assigned points (i.e., minimizes the error J for the given assignments). $w_k=\frac{{\sum }_{n=1}^N{r}_{nk}{x}_n}{{\sum }_{n=1}^N{r}_{nk}}$