In K-means, what happens if a centroid is never the closest to any point? 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.



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?
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.