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