2
$\begingroup$

I'm trying to find the optimal K-means clustering for a set of elements. For a particular K, K-means repeated several times does not always converge to the same clustering due to the randomness in the initialization. This means that whatever internal performance statistic (a clustering criterion, such as Dunn's index) I'm using to choose k is going to be dependent somewhat on when I run the algorithm, unless I use a seed. To decide whether the clustering is "stable" for a particular k (making it possible for me to believe the performance statistic is representative), I calculate how often the resulting clusters for that k overlap from run-to-run:

$$ \frac{1}{n(r-1)} \sum_{j=2}^r \sum_{i=1}^n \frac{|C_{j-1}^{(i)} \cap C_{j}^{(i)}|}{|C_{j-1}^{(i)}|}$$

Where $n$ is the number of elements I'm clustering, $r$ is the number K-means runs (with fixed k), and $C_j^{(i)}$ is the cluster from the $j$th run containing the $i$th element.

However, this statistic is not from the literature, and I'd be curious to know how others have addressed this problem and if there are issues with my approach that haven't occurred to me. Thanks.

$\endgroup$
9
  • $\begingroup$ I mean metrics such as Dunn Index, Beta CV, etc. that you can use to characterize the performance of K-means for some particular K. If a Kmeans run is heavily affected by the initial conditions, then I can't be sure that whatever statistic I get for a particular k is representative of all of the clusterings I would get for that k, were I to repeat the Kmeans runs with different initial conditions. So I want to answer the question, how dependent is the clustering on the initial conditions? $\endgroup$ Commented Mar 3, 2016 at 19:22
  • 1
    $\begingroup$ Well, there is two different topics here, better not to mix, generally. 1) Choice of the best initial k centres so that K-means come to the global optimum or very close to it; (2) Choice of the true or best k so that the clusters are most valid from the point of view of a particular clustering criterion. $\endgroup$
    – ttnphns
    Commented Mar 3, 2016 at 19:34
  • 1
    $\begingroup$ The only method I have for choosing the initial k centers is randomly selecting k of the elements. The resulting clusterings for my particular data set appear to be rather sensitive to this choice of initial centers. I want to quantify how sensitive it is to the initial centers with the statistic above, following my intuition that for the "right" set of element features and k, I should see Kmeans converge to nearly the same clusters, regardless of the initial k centers. $\endgroup$ Commented Mar 3, 2016 at 19:43
  • 1
    $\begingroup$ Note that K-means seeks to optimize this specific criterion: pooled within-cluster SS, and not Dunn's index or other similar. For every value of k in some range, we usually run K-means several times with different initial seeds for the k centres, then average the "corresponding", most similar final centres and use those k final averaged centres as the initial input for one last run. (to cont.) $\endgroup$
    – ttnphns
    Commented Mar 3, 2016 at 19:47
  • 1
    $\begingroup$ I see some sense in your reasoning in the previous comment. However, it is simpler and more effective, instead of quantify how sensitive it is... just to do your best that the solution be close to optimal. Then, having that good results at hand, select the best k among them, as I described. $\endgroup$
    – ttnphns
    Commented Mar 3, 2016 at 19:55

1 Answer 1

2
$\begingroup$

There are many statistics suitable for comparing the similarity of clusterings. Probably the most popular is the adjusted Rand index.

If you have multiple runs of k-means and the results have a high ARI (close to 1), then they are very similar. An ARI close to 0 would indicate very unstable results; but this is essentially impossible with k-means because it only generates convex clusterings which are bound to be rather similar (an ARI of 0 would arise on random cluster labels that do not take the data into account).

You may want to also look at the WCSS used by k-means. Results with a low ARI but a highly similar WCSS indicate that there a multiple equally good local minima. Then k may be too small. A high ARI similarity but very different WCSS must be caused by only a few points, probably outliers that disturb the algorithm?

$\endgroup$

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.