I am currently implementing a Kmeans clustering algorithm in R. I am not using any packages and I wrote it from scratch. I am using only one set of initial guesses, and my action upon finding an empty cluster is to select a new data point randomly and use that as the new mean for the empty cluster.
I have gathered from reading online that the solution does not always converge, and it is highly sensitive to the initial means, so when I see that behavior I am not surprised. But I am finding that sometimes my solution is actually cycling between two or more different solutions. So I have two questions associated with this observation:
1) Within a solution cycle, one solution is always better than the others as measured by the total sum of squared distances of all points to their nearest clusters. So this implies that not only does the algorithm not necessarily find the global optimum, but also it sometimes does not even improve the total sum of squared distances from one iteration to the next? I thought the solution was at least always improving...
2) What is the best way to get around this problem? Do I have to program it to recognize cycles and then select the iteration in the cycle with the lowest total distance? Or is there an easier way?
Any help would be greatly appreciated.