How to measure the similarity of k-means clustering using different datasets?

Question

I run k-means clustering on my dataset (100 samples in total) and partition the data into k=5 clusters. Then I want to test how robust of the k-means can be; however, I haven't got more new data samples. My idea is:

• Take the first sample out and run k-means on the rest of 99 samples.
• Loop over the step described above for each sample (e.g., take out the 2nd sample at the 2nd iteration), and run the k-means 100 times in total.

My question is how to measure the similarity of the 100 k-means results? I am thinking of get the statistics of silhouette coefficients. Does that make sense?

Thanks.

A.

Answer 1

Using statistics such as Silhouettes will tell you whether each run of the algorithm produces equally tight clusters. This may be sufficient for your needs, but it won't tell you if the same clusters are found each time. You could explicitly compare the cluster centres each time (but remember that different permutations of the same centres may happen in different runs, as the model is unsupervised). Another option is to use the Adjusted Rand Index (or normalized mutual information) to measure the similarity between two cluster solutions. These basically measure how often two points are assigned to the same cluster and how often to different clusters.