Kmeans algorithm cyclical solution 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.
Thanks.
 A: From the actual objective, K-means does not optimize the sum of total distances.
K-means optimizes the sum of squares, i.e. $SSQ:=\sum_o \min_\mu \sum_i |x_i - \mu_i|^2$.
$i$ iterates over all dimensions, and $\mu$ are the cluster centers.
Technically, this means assigning each point to the closest cluster center by (squared or non-squared) Euclidean distance. But logically, you try to minimize above squared deviations across all object and dimensions.
So make sure to use the SSQ as quality measure, not some sum of distances.
Secondly, K-means clusters usually shouldn't become empty. Not if you initialize the means to be actual data points and avoid duplicates. Because then, this data point is bound to have a distance of 0.
K-means clusters are voronoi cells, which are convex (at least if you properly use squared euclidean, and not some random other distance function). The mean cannot move outside of this convex area for the next iteration; only within this area. So they can't collide and such things.
A: Although this question already has an accepted answer, I would like to address the yet unadressed problem of a possible non-convergence of k-means.
This can indeed occur due to ties and cyclical assignemnt of ties to different clusters. To avoid this issue, you must always use the same deterministic tie breaking, e.g., always assign ties to the cluster with teh smaller cluster label.
