k-means clustering

Question

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?

Answer 1

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.