# How do I compare multiple runs of K-means?

I have results of best centroids for multiple (10) runs of k-means. How do I compare these weights to check if they are close to each other or different?

My goal is to check weather I get to the same local minima after training with random initial centroids.

First off, unless your clustering problem is a trivial clustering problem the global minima will be virtually impossible to solve for (requires enumerating through all possible cluster points). Therefore the solution of multiple different runs will most likely place you in multiple local minimas.

Here are a couple resources discussing why the k-means algorithm's do not find the global minima. https://stackoverflow.com/questions/14577329/why-doesnt-k-means-give-the-global-minima
Why doesn't k-means give the global minimum?

One way to compare the learned weights is to compare the expressive power of their respective classifiers. One way to do so is by utilizing the squared L2 difference. $$\sum_{c}\sum_{x \in c}{(c-x)^2}$$ Where $c$ is ever cluster, and $x$ represents ever data-point registered to that cluster. The smaller the loss the better the classifier.

I don't believe that directly comparing the clusters weights gives you much information about individual run's of k-means.

EDIT: Authors comment clarified the question a little bit more.

Let's say we want compare the weights of two k-means. Let us say that the $i$th k-means produces $k$ centroid's $C_i: {c^i_0,c^i_1,...c^i_k}$.Now the problem with directly comparing clusters at the same index for different k-mean runs is that clusters do not necessarily have to be localized to a specific index. In one run a centroid might appear in the first index, while in a separate run that same centroid might appear in a different index. Here is a very naive approach. $$D[i,j]=\begin{bmatrix} ||c^i_0-c^j_0||_2^2&||c^i_0-c^j_1||_2^2&||c^i_0-c^j_k||_2^2 \\0&||c^i_1-c^j_1||_2^2&||c^i_1-c^j_k||_2^2 \\0&0&||c^i_k-c^j_k||_2^2 \end{bmatrix}.$$ This is the distance between every centroid in two k-means runs. Keep in mind that this matrix only has to be calculated for the upper triangular due to the symmetry in the distance function used (squared $L2$).Then you can calculate the total distance between two k-mean runs as $$D(i,j)=\sum_i{min(D_i)}$$.

This is a very naive approach. It does not set a constraint that indices can only show up once in the minimum function ($1$ to $1$ mapping between every centroid in two k-mean runs). To generalise this approach to $n$ k-mean runs, you can construct another distance matrix like the one above with every entry $D_{i,j}=D[i,j]$ Let me reiterate that this is a very naive approach. But it does show the distance between two k-means, and it has a nice property that if two k-mean runs did learn the same exact centroids, regardless of order the distance $D[i,j]=0$.

Let me know if this helps.

• Thanks @ArmenAghajanyan your answer is brilliant for comparing how well the weights classified the data. What i am trying to do is slightly different, i am using a different cost function from standard k-means, i am trying to check if the function has multiple local minima, please see my complete question here stats.stackexchange.com/questions/186130/… – Young_DataAnalyst Dec 14 '15 at 22:45
• Couldn't you just check if you get the same value for the cost function for all the solutions? in that case it means you get to the same local minimum. – Simone Dec 14 '15 at 23:19
• @Young_DataAnalyst I added a possible approach to my problem, in the edit of my answer. – Armen Aghajanyan Dec 15 '15 at 4:35
• @Simone And I agree with Simone, the same solution should yield the same exact cost. – Armen Aghajanyan Dec 15 '15 at 4:36
• @ArmenAghajanyan Brilliant solution, i have implemented a function to compute your D(i,J) in MATLAB. Now the challenge i am facing is i am getting a matrix that shows the index of closest centroids by its individual mapped feature. (Ci1 Ci2...Cid) were d is data dimension therefore each centroid has multiple different closest index, how will i solve this? I need distance of a centroid as a whole. Ci – Young_DataAnalyst Dec 18 '15 at 16:04

To add up to Armen Aghajanyan answer, I guess it is difficult to check if you get the global minimum unless you know theoretical properties of your clustering problem.

As he suggested, you might be limited to compare the 10 solutions between each others. An empirical way to quantify the similarity between clusterings might be using the squared L2 distance indeed.

If you have cluster labels you can also compute the similarity between clusterings by the consensus index. This is just an average similarity between all clustering pairs.

For example you might want to use the Adjusted Mutual Information (AMI) in Matlab (here or here) as similarity measure between two clusterings $U$ and $V$. Then the consensus index (CI) between $n$ clusterings is defined as: $$\mbox{CI} = \frac{2}{n(n-1)}\sum_{i < j} \mbox{AMI}(U_i,V_j)$$ Try to have a look here for reference. If you use an adjusted similarity measure for clustering comparisons the CI is equal to 0 if there the clusterings are random and independent and is equal to 1 when they are identical.

• The Rand index and the adjusted rand index provide a classical approach, this statistic is simply based on pairwise counts between clusterings. en.wikipedia.org/wiki/Rand_index – Jonathan Lisic Dec 15 '15 at 2:36
• Thanks @JonathanLisic, yes you can use any similarity measure between clusterings you like. Actually the adjusted rand index and the adjusted mutual information are connected: arxiv.org/abs/1512.01286 – Simone Dec 15 '15 at 3:30