# 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.

• K-means has no way to create clusters, so it really depends on the initial set, but when I find a cluster becomes empty, I delete it. Jul 26, 2013 at 17:25

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.

• thank you for your explanation of the objective function Anony-Mousse. I actually meant the sum of squared distances, not the total distance, and edited my post accordingly. I think I see some significance in your explanation of Voronoi cells, but I am still not sure what that means for a cyclical solution.
– Paul
Jul 26, 2013 at 17:17
• Don't think of squared distances either - it won't work for arbitrary distances. It's really squared errors, across all objects and dimensions. What I meant to say is that it seems as if you have an error somewhere in your code. Adding a new cluster center must again decrease the objective function. If all your operations (and the computation of the objective function!) are valid, each must in fact decrease this objective function. Jul 27, 2013 at 9:38
• Anony Mousse, thank you for following up, you are right. I noticed that the cyclical solution was usually fairly close to a permutation of the clusters, which led me to the bug in my code.
– Paul
Jul 27, 2013 at 14:50
• One final note: My K-means algorithm is now converging every time. However, I am still noticiing that the total squared distances over all observations and dimensions does not necessarily decrease with each iteration. Does this mean I still have a bug in my code? Or is this normal behavior?
– Paul
Jul 27, 2013 at 17:18
• It's not supposed to increase. If it doesn't keep decreasing for a number of steps this can have multiple reasons. For example, numerical precision, or unstable assignments. Don't reassign objects to other clusters if both clusters have the exact same distance, unless you can still guarntee convergence then. Jul 27, 2013 at 17:21

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.