1
$\begingroup$

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

k-means graph

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Based on your answer, I decided to pick one random point from each group of points as initial centroids and proceed the algorithm from there. It worked gracefully, thanks for your help! $\endgroup$
    – enzo
    Jan 8, 2021 at 0:16
  • $\begingroup$ That's a good way to ensure the health of your unit tests. $\endgroup$
    – gunes
    Jan 8, 2021 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.