How to avoid k-means to merge two groups of points into one cluster?

Question

I've implemented a k-means clustering algorithm, but in some cases (~12%) a situation like that happened:

In these cases, my algorithm is creating one cluster for both the yellow and blue group of points and is dividing the purple group into two clusters. When this occurs, the cluster division becomes 23-12-65, when it should be 33-33-34.

My algorithm is:

1. Select 3 random points c0, c1 and c2 in the dataset.
2. For each point p in the dataset, associate p with the nearest c_.
3. For each point c_, set c_ to the mean point of its associated points.
4. Repeat 2 and 3 500 times.
5. Output c0, c1 and c2.

I'm assuming this problem happens in step 1, where two points from the purple group are selected. Is this normal for k-means? If there's a solution, how to fix or minimize this problem? I'm creating the dataset using the sklearn.datasets.make_blobs method, so I've already tried raising the number of points to 500 (n_samples=500) and lowering the standard deviation of the data making the points more sparse (cluster_std=0.1).

---

Some background: I'm unit testing this algorithm, so it'll assert if each of the three found centroids are inside of each square in the image. In this specific case, the assertion fails, even if in ~88% of the cases it asserts.

Answer 1

Since k-means relies on random initialisation, if local minima exist, there is no way to guarantee that the algorithm finds what might be obvious to the human eye. But, there are ways to mitigate it. One simple approach is having multiple runs for it and pick the solution with the lowest cost. This number of runs can be a parameter, maybe set to 1 as default. In the end, your unit tests should have fault tolerance or you should pick random initialisation points in a supervised manner.