2
$\begingroup$

I'm implementing the k-means algorithm (in R Map-Reduce) and I wanted to verify if the output I'm getting is close enough to the true centroids of the cluster. This is how I'm verifying with a 2D dataset currently: I plot both the dataset and the centroids I've got as output and see if the centroids are close to the centre of the clusters visually. I think I can do that for 3D data too. But I don't know how to verify this with higher dimensional data that cannot be plotted.

It looks really stupid to plot the data and visually verify each time, right? So let me tell you why I'm doing this:

The centroids don't come in a particular order. The 1st centroid in this trial might be in the 2nd position in the next, so I can't find the distance between the matrix of my output and the matrix of, say, the R's default kmeans output (if I'm verifying my output with R's kmeans). Sorting with respect to any one dimension to compare sounds stupid, since any dimension can be a lot more sensitive to the data when compared to another.

So, for now, I'm verifying 2D data visually. Do I have to use dimensionality reduction? Does someone have ideas about how I can verify higher dimension data?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

You can give the induced clusters some arbitrary labeling (as A, B, C) and give the true clusters a labeling (say 1, 2, 3). And plot the "classification" in a confusion matrix. You'll get something like this $$ \left( \begin{array}{c|ccc} & A & B & C \\ \hline 1 & 0.01 & 0.2 & 0.79 \\ 2 & 1 & 0 & 0 \\ 3 & 0.08 & 0.92 & 0 \end{array} \right)$$ If the clustering algorithm performs well, you won't get high values on the diagonal, but you will see an obvious way to relabel to put the high values on the diagonal.

If this isn't enough of an indication by itself, you can use a measure based on the confusion matrix (symmetric error, precision/recall) and just use the relabeling that optimizes that value. If the algorithm performs well, then the optimal relabeling is obvious anyway, and if it doesn't, then taking the optimal relabeling won't help performance.

The cluster analysis page on wikipedia has some other methods for evaluating a clustering against a gold standard, but I think this one fits your use case best.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Nice. I had to look up what a confusion matrix is. Let me clarify on what I have understood here. I'll make the matrix with my output centroids and the actual values of centroids [calculated in some way or the other] and find some measure of similarity between each centroid and the other. In the example you have given, if 1,2 and 3 are output centroids of my code and A,B and C are the true centroids, 1 corresponds to C, 2 corresponds to A and 3 corresponds to B right? Then maybe I can use 1-distance between centroids as the values in the matrix? $\endgroup$
    – Prateek Kulkarni
    Commented Feb 19, 2013 at 9:22
  • $\begingroup$ Not exactly. You can forget about centroids, and just take the assigned clusters. The evaluation consists in checking whether A, B and C map onto your original clusters 1, 2, 3. You don't know which of A, B or C a given original cluster was mapped to, but that doesn't matter. The matrix just tells you how often a point with true cluster 2 was clustered into k-means' cluster B. Now if you knew that the mapping was supposed to be 1=A, 2=B, 3=C, you'd be looking for a very diagonal matrix, but since you don't care about the mapping, you just want a matrix that becomes diagonal for some mapping. $\endgroup$
    – Peter Bloem
    Commented Feb 19, 2013 at 10:06
  • $\begingroup$ Okay. One limitation I have to do this is that I'm using a distributed computing system, and in the stage where I calculate the centroids, I have no access to the actual data points. But I get the idea. $\endgroup$
    – Prateek Kulkarni
    Commented Feb 19, 2013 at 10:22
1
$\begingroup$

How about computing the distances between the means in one result and the means of the other result, compared to the total variance?

But note that running k-means in R with different random seeds / initial means will yield different results on nontrivial data.

Improve this answer
$\endgroup$
5
  • $\begingroup$ You mean to say I create the distance matrix of the my means and the true means compare the variance? But does the variance make any sense? How does this variance relate to the data or the clustering at all? Both sets of means can have the same variance but can have completely different values. $\endgroup$
    – Prateek Kulkarni
    Commented Feb 19, 2013 at 9:29
  • 1
    $\begingroup$ The variance of the cluster assignments. That is what k-means optimizes: "sum of squares". If the optimal cluster-cluster mapping SSQ is smaller than the average SSQ of the cluster assignments, then the difference between the two clusterings is of low relevance. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Feb 19, 2013 at 9:44
  • $\begingroup$ Oh, ok got it. This would have been my first choice of verification if I was not using a distributed computing network. I'm writing this code in Map-Reduce, so I have to go through the data all over again to calculate the variance, which is problem for me. I was looking for external verification procedures, but I should have stated this in the question. Sorry about that. $\endgroup$
    – Prateek Kulkarni
    Commented Feb 19, 2013 at 9:53
  • 1
    $\begingroup$ Just keep that statistic in the reducer. It's fairly cheap to track, like one double extra for each node and cluster. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Feb 19, 2013 at 11:43
  • $\begingroup$ Yeah. That makes sense. $\endgroup$
    – Prateek Kulkarni
    Commented Feb 19, 2013 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.