# k-means clustering

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?

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

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.