will k-means clustering converge to the same results given the same data set?

Question

I did some study on the k-means clustering algorithm. It seems that the only non-deterministic part is the centroid - initialization.

Assume I have 10k data points, and a given k. I then initialize the initial centroids randomly in my each try:

Try_1: Initial k-centroids randomly with seed_1. Then keep updating the centroids until converge (assuming we can use the 10k data points multiple times)

Try_2: Initial k-centroids randomly with seed_2. Then keep updating the centroids until converge (assuming we can use the 10k data points multiple times)

Try_3: Initial k-centroids randomly with seed_3. Then keep updating the centroids until converge (assuming we can use the 10k data points multiple times)

Try_4: Initial k-centroids randomly with seed_4. Then keep updating the centroids until converge (assuming we can use the 10k data points multiple times)

Try_5: Initial k-centroids randomly with seed_5. Then keep updating the centroids until converge (assuming we can use the 10k data points multiple times)

In these 5 tries, will the final cluster results be the same?

Answer 1

They won't necessarily be the same. Consider observations equally distributed over a circle (radius = 1). Depending on the initial centroids, the algorithm will converge on different solutions. For instance, consider the case where two centroids are initially located on each side of one of the circle's diameters. Those can be any pair of points, and the algorithm will already be converged with different solutions.

However, there exist cases where the algorithm will necessarily converge to the same solution. For instance, consider points equally distributed over a segment, in a 2 cluster problem. It is quite clear (although a bit harder to explain) that any initialization will eventually converge to the same solution (this actually need sadditional assumptions, such as no point being on the edge of both clusters, at least).

In your example case, with a more complex structure, the problem is more difficult to analyze. There are some problems which will likely give the same results every time, other that will yield different results. But anyway you can't be sure, in the general case, that it will fall back to a single solution.