Clustering with K-Means and EM: how are they related?

Question

I have studied algorithms for clustering data (unsupervised learning): EM, and k-means. I keep reading the following :

k-means is a variant of EM, with the assumptions that clusters are spherical.

Can somebody explain the above sentence? I do not understand what spherical means, and how kmeans and EM are related, since one does probabilistic assignment and the other does it in a deterministic way.

Also, in which situation is it better to use k-means clustering? or use EM clustering?

Answer 1

K means

1. Hard assign a data point to one particular cluster on convergence.
2. It makes use of the L2 norm when optimizing (Min {Theta} L2 norm point and its centroid coordinates).

EM

1. Soft assigns a point to clusters (so it give a probability of any point belonging to any centroid).
2. It doesn't depend on the L2 norm, but is based on the Expectation, i.e., the probability of the point belonging to a particular cluster. This makes K-means biased towards spherical clusters.

Answer 2

There is no "k-means algorithm". There is MacQueens algorithm for k-means, the Lloyd/Forgy algorithm for k-means, the Hartigan-Wong method, ...

There also isn't "the" EM-algorithm. It is a general scheme of repeatedly expecting the likelihoods and then maximizing the model. The most popular variant of EM is also known as "Gaussian Mixture Modeling" (GMM), where the model are multivariate Gaussian distributions.

One can consider Lloyds algorithm to consist of two steps:

• the E-step, where each object is assigned to the centroid such that it is assigned to the most likely cluster.
• the M-step, where the model (=centroids) are recomputed (= least squares optimization).

... iterating these two steps, as done by Lloyd, makes this effectively an instance of the general EM scheme. It differs from GMM that:

• it uses hard partitioning, i.e. each object is assigned to exactly one cluster
• the model are centroids only, no covariances or variances are taken into account

Answer 3

Here is an example, if I were doing this in mplus, which might be helpful and compliment more comprehensive answers:

Say I have 3 continuous variables and want to identify clusters based on these. I would specify a mixture model (more specficially in this case, a latent profile model), assuming conditional independence (the observed variables are independent, given cluster membership) as:

Model: 
%Overall%
v1* v2* v3*;  ! Freely estimated variances
[v1 v2 v3];   ! Freely estimated means

I would run this model multiple times, each time specifying a different number of clusters, and choose the solution I like the most (to do this is a vast topic on its own).

To then run k-means, I would specify the following model:

Model: 
%Overall%
v1@0 v2@0 v3@0;  ! Variances constrained as zero
[v1 v2 v3];      ! Freely estimated means

So class membership is only based on distance to the means of the observed variables. As stated in other responses, the variances have nothing to do with it.

The nice thing about doing this in mplus is that these are nested models, and so you can directly test if the constraints result in worse fit or not, in addition to being able to compare discordance in classification between the two methods. Both of these models, by the way, can be estimated using an EM algorithm, so the difference is really more about the model.

If you think in 3-D space, the 3 means make a point...and the variances the three axes of an ellipsoid running through that point. If all three variances are the same, you would get a sphere.