I'm a software engineer and am trying to understand how Lloyd's K-Means algorithm fits into the general framework of the Expectation-Maximization (EM) algorithm. I previously read the question "Clustering with K-Means and EM: how are they related?", but it still doesn't make sense.
I fully understand the K-Means algorithm as such:
Steps:
1. Make an initial guess for the centroid positions of K clusters
2. Repeat until convergence {
Expectation: Assign each data point to the nearest cluster centroid
Maximization: Recompute the position of each cluster's centroid
}
I also understand the EM algorithm from this question and this paper to be:
Variables:
i. Latent variables
ii. Parameters theta of an assumed model
Steps:
1. Guess theta
2. Repeat until convergence {
Expectation: Compute distribution over latent variables
using current theta
Maximization: Use MLE formulas to compute new theta from
latent variable distribution
}
So my specific questions relate to how Lloyd's K-Means algorithm fits in the EM framework:
A. What is the "latent variable" in K-means? Is it the assignment of the data points to the clusters?
B. What are the parameters "theta" that we are trying to compute in K-Means?
C. In the maximization step for K-Means, which MLE formula and what model are we using to recompute theta? I understand that we recompute the centroids as if they are the "center of mass" of all the data points in a given cluster, but what kind of "model" is that?