# Comparing K-Means and Expectation Maximization on the dataset generated - When does K-Means perform better?

I was experimenting with K-Means and Gaussian Mixture Models (Expectation-Maximization) on the data set that I generated. Here is how the plot for two distributions looks like:

Since this was generated using 2 distributions, I wanted to see the clusters created by both K-Means and Expectation-Maximization. So I created and plotted them. Cluster using K-Means looks as follows:

The 2 clusters created from K-Means were somewhat expected. But the clusters created using Expectation Maximization were not close to what I had imagined it to be. It looks as follows:

I really feel that K-Means was able to capture more points from a particular distribution as compared to EM. Also, I had imagined that EM would be able to create overlapping clusters to distinguish the 2 square formations you see in the dataset plot. What is the intuition behind EM performing this way?

Here is the complete code using which I generated these plots.

    from nltk.cluster import KMeansClusterer, euclidean_distance, cosine_distance
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.mixture import GaussianMixture

np.random.seed(1)

distr_1 = np.sin(2 * np.random.randn(100) + np.random.randn())
distr_2 = (3 * np.random.randn(100)) + np.random.randn()

distr_11 = np.log(np.absolute(2 * np.random.randn(100) + np.random.randn()))
distr_21 = np.sin(3 * np.random.randn(100)) + np.random.randn()

X1_train = np.concatenate((distr_1, distr_2))
X1_train = X1_train.reshape(100, 2)

X11_train = np.concatenate((distr_11, distr_21))
X11_train = X11_train.reshape(100, 2)

X1_plot = X1_train[:, 0]
Y1_plot = X1_train[:, 1]

X11_plot = X11_train[:, 0]
Y11_plot = X11_train[:, 1]

plt.figure('dataset')
fig, ax = plt.subplots()
plt.scatter(X1_plot, Y1_plot)
plt.scatter(X11_plot, Y11_plot)
fig.text(0.95, 0.05, 'Experimental - SG',
fontsize=50, color='gray',
ha='right', va='bottom', alpha=0.5)

plt.gca().legend(('X1', 'X11'))
plt.savefig("data_set.png")
plt.clf()
#plt.show()

merged_x = np.concatenate((X1_train[:,0],X11_train[:,0])).reshape(200,1)
merged_y = np.concatenate((X1_train[:,1],X11_train[:,1])).reshape(200,1)

merged = np.concatenate((merged_x, merged_y), axis=1)

km = KMeans(2, random_state=0)
labels = km.fit(merged).predict(merged)

print(labels)
plt.figure('cluster-euclidean')
fig, ax = plt.subplots()
plt.scatter(merged[:,0], merged[:,1], c=labels, cmap='viridis')
fig.text(0.95, 0.05, 'Experimental - SG',
fontsize=50, color='gray',
ha='right', va='bottom', alpha=0.5)

plt.savefig("euclidean.png")
plt.clf()

clusterer = KMeansClusterer(2, cosine_distance)
clusters = clusterer.cluster(merged, True, trace=True)
plt.figure('cluster-cosine-distance')
fig, ax = plt.subplots()
plt.scatter(merged[:,0], merged[:,1], c=clusters, cmap='viridis')
fig.text(0.95, 0.05, 'Experimental - SG',
fontsize=50, color='gray',
ha='right', va='bottom', alpha=0.5)

plt.savefig('cosine.png')
plt.clf()

###
gmm = GaussianMixture(n_components=2, covariance_type='full')
gmm.fit(merged)
labels = gmm.predict(merged)
plt.figure('EM')
fig, ax = plt.subplots()
plt.scatter(merged[:,0], merged[:,1], c=labels, cmap='viridis')
fig.text(0.95, 0.05, 'Experimental - SG',
fontsize=50, color='gray',
ha='right', va='bottom', alpha=0.5)

plt.savefig('em.png')
plt.clf()
#plt.show()


Edit:

As I generated a lot more data samples, EM was able to give out clusters that were visually much more satisfying. What could be concluded from this? Here is the plot of dataset with much more samples.

And the plot where EM created clusters:

Here K-Means just adds a linear separator, which was expected from K-Means on this dataset.

How do we explain the result here? Why was EM able to cluster data better with much more data samples?

• These two methods work differently because they assume different rules. So the qeustion which works better depends on your data, your prior knowledge and the objective. – user2974951 Oct 18 '18 at 6:16
• @user2974951 I had expected the results of EM to be close to the distribution as you can see in the plot. This is how I understand EM. – Suhail Gupta Oct 18 '18 at 6:18
• Why? The nice thing about Gaussian Mixture Models is that you can specify a lot of different shapes, volumes and sizes for your data, which gives rise to (sometimes) very different results. You should play around with the settings (and read on the possible values for the arguments) to see which could work best for your data. – user2974951 Oct 18 '18 at 6:20
• @user2974951 Won't EM try to get as close to the given distribution as possible? I tried different types of covariance_type as given here and except for tied the results were pretty much similar. – Suhail Gupta Oct 18 '18 at 6:28
• Well... I don't know how Python does this specifically, but in R you have an option to choose from 16 different combinations of shape, volume and size, while this implementation in Python only lists 4. – user2974951 Oct 18 '18 at 6:41

What the K-means algorithm does is just to follow a recipe: alternate between computing the means of each of the K classes (centers of gravity) and assigning each point to the nearest mean. The outcome is such that only points which are close together are deemed to be in the same class.

A Gaussian mixture model, on the other hand, assumes that for each datapoint x_n there is a latent (hidden) variable z_n with values 1, ..., K representing its cluster (or class). Conditional on z_n, x_n is drawn from a Gaussian distribution with mean and co-variance matrix depending on the class z_n. The EM algorithm attempts to find the configuration of the z_n's that maximizes the overall likelihood.

In your example, you're generating data from a mixture of two distributions: orange and blue, so K=2. Orange and blue are not strictly Gaussian, but close enough. Accordingly, in both cases (even with only few data) the mixture model picks up that there is one distribution with a bigger variance (yellow) and one with a smaller variance (purple). By design, K-means has no chance of picking up this pattern.

• "only points which are close together are deemed to be in the same class". What's about points which are diametral in a cluster? – ttnphns Oct 19 '18 at 5:55
• So from your answer, can I generalise in working that distributions having similar variance will be clustered together by Gaussian mixture model? – Suhail Gupta Oct 19 '18 at 7:03
• @SuhailGupta, for a GMM (as in your code), the number K of components is specified in advance. Then K distributions are found (with possible restrictions on the covariance matrix) that best fit the data. I don't know what happens if two components have very similar distributions, but I would guess that two components are fitted which have similar mean vector and covariance matrix. – Peter Straka Oct 19 '18 at 7:38
• @PeterStraka Could you point me to a resource that helps me easily understand covariance matrix? – Suhail Gupta Oct 19 '18 at 8:27
• @SuhailGupta: I've learned from JOHNSON R., WICHERN D., Applied Multivariate Statistical Analysis. But there are many good books on multivariate analysis, see e.g. stats.stackexchange.com/questions/2181/… – Peter Straka Oct 19 '18 at 12:06

To understand why the solutions are not as good as you imagine, make a heatmap plot of the following:

For the two clusters you generate, determine the pdf (probability density function) each. Now plot a heatmap of pdf1(x,y)-pdf2(x,y). Assuming a red-white-blue heatmap, red areas are more likely to belong to one clusters blue areas to the other.

That is the "real" ground truth that you are working with: lots of points in "white" that cannot be clearly assigned to either cluster.

You then can also do the same for the clustering result of EM.

If visual contrast is not good enough, use log(pdf1(x)/pdf2(x)) instead.

This is similar to the following image from Wikipedia:

Except that you want to look at the differences between the shaded intensities (the filled ellipses, not the individual points, redness minus yellowness). Also, the Wikipedia situation has well separated clusters, but in your case they overlap badly, which makes them pretty much inseparable. The visualization above aims at visualizing the lack of separability...

On the analytical side, compare the average squared difference between the two clusters to the average squared difference within each cluster. If the first is not substantially larger than the second, the clusters can likely not be separated well!

• from Wikipedia. Please, add the link to the article. – ttnphns Oct 21 '18 at 11:23
• done that. obviously it was in the EM article. – Anony-Mousse Oct 21 '18 at 23:35