Expectation–maximization (EM) algorithm

Expectation maximization (EM) algorithms is an iterative algorithm applied to problems that does not have a closed form solution. In other words if the problem is under constrained then the EM algorithm finds a maximum likelihood (ML) or maximum a posteriori (MAP) estimates of model parameters and the function. The EM algorithm has two steps (1) Expectation (E) step and (2) Maximization (M) step. The algorithm iterates between these two steps (E step and M step) until it finds the optimum solution. In the E step the algorithm estimates the function for the expectation of the likelihood based on the current estimates of the model parameters. In the M step the algorithm computes the model parameters that maximizes the expected likelihood found in the previous E step.

In an unsupervised clustering problem, if one applies hard decision instead of a soft decision for membership function in an EM setting then this becomes equivalent to K-means algorithm. In other words, if one applied probability to to assign cluster membership to each data point then in this case the K-means clustering becomes equivalent to the  EM algorithm.


K-means with soft decision => EM algorithm

EM algorithm in clustering with hard decision =>  K-means clustering