# 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. – Mike Dunlavey Jul 26 '13 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 '13 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. – Has QUIT--Anony-Mousse Jul 27 '13 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 '13 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 '13 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. – Has QUIT--Anony-Mousse Jul 27 '13 at 17:21