0
$\begingroup$

If I follow the algorithm at here: http://www.ece.northwestern.edu/~wkliao/Kmeans/index.html

Suppose I am unlucky. When I randomly pick the initial cluster centers, two of the initial cluster centers are from two data points that should belong to the same true cluster, called A.

In this case, can the algorithm give incorrect result? For example, the two unlucky cluster centers would split data points from A. Then another cluster center would get more data points than it should.

How to avoid that?

$\endgroup$
  • $\begingroup$ So far, I get the idea that this can happen even if my program is completely correct. K-means++ can mitigate this problem. $\endgroup$ – hamster on wheels Mar 2 '17 at 22:35
3
$\begingroup$

Wikipedia has a great section on the issue of k-means initialization, which has been studied extensively in academia. The method described in your link is known as the "Forgy" method, and Celebi et al (2013) and others have found it can yield sub-optimal clusterings. You're right that k-means++ can mitigate this issue, and in my experience it produces better clusters than simple k-means.

Moving on to your question: k-means is an unsupervised algorithm. There are no "true" clusterings, and thus no incorrect result. Instead, the algorithm seeks to minimize the within-cluster sum of squares (WCSS), and there is no guarantee with vanilla k-means (or any k-means variation, if I remember correctly) that you will find the optimal clustering according to the WCSS. Additionally, your results are both sensitive to your choice of $k$ and distance metric, which further complicates issues.

So: k-means can yield sub-optimal clusters depending on initialization, as well as your choice of $k$ and distance metric. I'd suggest trying k-means++ to mitigate initialization issues, and check different values of $k$ using grid search to see what produces results you are happy with.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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