# Clustering: k-means alternatives when its assumptions do not hold

Essentially this tutorial (http://scikit-learn.org/stable/auto_examples/cluster/plot_kmeans_assumptions.html#example-cluster-plot-kmeans-assumptions-py ) explains very clearly some limitations of the k-means clustering method which are rooted in its assumptions.

Specifically: 1) k-means assumes the variance of the distribution of each attribute (variable) is spherical; 2) all variables have the same variance; 3) the prior probability for all k clusters is the same, i.e., each cluster has roughly equal number of observations;

Now, thanks to the silhouette method, I can handle the case with the wrong number of blobs but I am in the dark for how to handle the other cases. Could you point me to some methods to solve the other issues and if, possible, how to blend them toghether since in my datasets these behaviours coexist?

• Your question might get more response if you listed the relevant assumptions that are given in your link. That said, Gaussian Mixture Models are a common approach for the types of data shown there. Aug 21, 2016 at 23:06
• Prior to running k-means, it is customary to normalize all variables such that all of them have 0 mean and unit variance. This validates assumption 2). Aug 22, 2016 at 7:08
• 1) k-means assumes the variance of the distribution of each attribute (variable) is spherical What's that? Spherical univariate distribution, how can that be? 2) all variables have the same variance [for the whole sample] K-means has no such assumption. 3) each cluster has roughly equal number of observations K-means has no such assumption (rather, it assumes clusters of approximately equal diameter). Aug 22, 2016 at 10:07
• blobs but I am in the dark for how to handle the other cases. Could you point me to some methods to solve the other issues and if, possible, how to blend them toghether This is not clear what you want, in the end. The whole your question looks to me rather dim in meaning. Aug 22, 2016 at 10:10

In the answers to How to understand the drawbacks of K-means we have already discussed drawbacks of k-means in detail.

Some of them may appear easy to counter for toy examples (e.g. by undoing scaling for distorted data sets) but real data will be much more complex, and global normalization may not be enough, unfortunately.

Rather than hot-fixing these problems, you should rather verify if the k-means objective solves your problem.

It's not just about clustering points into partitions. There is an underlying problem that you want to solve. With clustering it usually is about getting "insight" into your data. A simple approach here is to study the results carefully and discard any that seem suspicious. This cannot be automated (you can automate generating diverse results to avoid redundancies though, see "alternative clustering").

k-means is better be seen as a vector quantization approach rather than clustering. It does not attempt to identify the structure that is in the data, but it postulates a structure (k centers) and then optimizes the model parameters. During optimization it assumes that all variables are equal and the cost of each instance is measured as sum-of-squares $$\text{cost}(x_i) = \min_{\text{center }c} \sum_{\text{dim }d} (x_{i,d}-\mu_{c,d})^2$$ It will fail whenever the data does not have the postulated structure, or this cost function is inappropriate.

Thus, whenever considering k-means, the first thing you need to check if minimizing above equation solves your problem. If you don't want to answer the question "which centers have the smallest cost according to above equation" then k-means is the wrong algorithm!

Here is a positive example, where k-means is a good choice:

We have an RGB image with 24 bit depth (8bpp) and we want to compress that image for fast loading on the interwebz. Instead of storing 24 bit per pixel, we want to use just 4 bit that index into a 16 color palette. Run-length encoding will further help compressing the data. So we have to approximate every pixel with one palette entry. Larger deviations are bad, so using the square helps, and the color approximation error of a pixel can be computed as $\Delta R^2+\Delta G^2+\Delta B^2$. This matches exactly the cost function of k-means - and thus we can use this algorithm to optimize our color palette.