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

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?

• Spherical means identical variance-covariance matrices for each cluster (assuming gaussian distribution), which is also known as model-based clustering. Which approach do you consider as deterministic?
– chl
Commented Nov 18, 2013 at 12:11
• It would be nice if you give the source of the citation. Commented Nov 18, 2013 at 12:12
• k-means "assumes" that the clusters are more or less round and solid (not heavily elongated or curved or just ringed) clouds in euclidean space. They are not required to come from normal distributions. EM does require it (or at least specific type of distribution to be known). Commented Nov 18, 2013 at 12:21

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.

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
• Can you develop a little on the variants of $k$-means? I had a quick look in The elements of statistical learning (Hastie, Tibshirani, Friedman), chapter 14... they support the idea of existence of a "$k$-means algorithm". Commented Dec 2, 2013 at 9:30
• Many books equal k-means with lloyds algorithm, but he never called it k-means. MacQueen introduced the name k-means. Sorry: many books use incorrect naming here. k-means is the problem, lloyd only one popular solution. In fact, R will run Hartigan-Wong by default to solve kmeans. Commented Dec 2, 2013 at 9:37

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.

• Thank you for this example. It helps a lot fix some ideas.
– Myna
Commented Dec 4, 2013 at 21:18