3
$\begingroup$

I am implementing K-Means from scratch and that exercise raised a question.

To update my centroids, for each centroid, I have to find the points for which that centroid is the closest.

In some cases, especially when the number of centroids is high and the number of instances is low (i.e. k=20 and 100 instances), I find centroids for which no point has them as their closest centroid. In other words, they become "orphans" as no instances are allocated to them.

Xs are centroids and Os are instances

In the example above, the two centroids (X) at the top clearly both have points for which they are the closest centroid. But the centroid at the bottom is never the closest centroid for any instance.

How do I deal with this?

  • Should the lone centroid remain unmoved?
  • Should I move that centroid? If yes, how?
  • Should I remove it?

Is there a standard way to deal with this?

------------ EDIT: --------------

On Github, I found this:

https://github.com/klebenowm/cs540/blob/master/hw1/KMeans.java

This suggests that if a centroid becomes an "orphan", it should be assigned to the point that is the furthest from its centroid.

This seems like a sound method, is there any paper or theory supporting this?

$\endgroup$
1
$\begingroup$

It's usually indicating bad starting centroids.

If it happens later in the process, it may indicate kmeans doesn't work well on this data, because a stable clustering just be easy to find.

$\endgroup$
2
$\begingroup$

You should leave the lone centroid unmoved. In the next iteration, it's possible that the cluster centers have moved in such a way that now there are some instances that are closest to the lone centroid, and it can get picked up. At the end of the k-means algorithm, you could remove clusters that have no instances associated with them, but it doesn't really matter.

At the end of the day, it's probably not a good idea to use k-means in the manner that you described, and we should not expect it necessarily to produce good results.

$\endgroup$
2
  • $\begingroup$ Thanks for the answer. What do you mean with the last part? How am I using K-means wrong? The case I mentioned is mostly theoretical. If I have centroids that don't get picked up, I would use a lower k $\endgroup$ – Valentin Calomme Nov 5 '17 at 23:46
  • $\begingroup$ Yes that’s exactly what I meant — using k-means with 20 centroids and 100 instances probably won’t work well in most cases. My point is that you don’t need to worry much about the performance implications of edge cases like this because someone doing this probably misusing the algorithm and won’t be getting a good result anyway! As you say, a lower k value should be used unless there’s a specific reason not to. $\endgroup$ – timleathart Nov 6 '17 at 9:42
-2
$\begingroup$

You don't have to worry about it, as we know, in k-means clustering, you only have to choose the initial centroids. This would create first iteration of clusters. In the next iteration, the centroids would move to the center of the newly created clusters. this whole process will continue till you get convergence. Now, the number of centroids selected at the first place are good or not, is a separate question. Also, we also know, the result of a k-means is dependent upon the initial selected centroids and we have various methods of selecting intital centroids, but just answer your question here, run the full algorithm and you wont have such lone centroids at the end of the algo.

$\endgroup$

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.