I am solving a clustering problem on a trivial dataset with the k-means algorithm. I am running a couple of tests and, from time to time, one centroid doesn't attract any points, i.e. I've got an empty cluster (see the purple "x" in the picture).
What should I do? Shall I delete it or just stop updating its value? Why?
I am aware that built-in functions (e.g.,
kmeans() in R) have automatic ways of dealing with this situation, but I am trying to write the standard algorithm from scratch. As soon as I fix it I'll be able to compare my results to built-in functions. At this moment I'm looking for some theoretical reasons why I should prefer one solution or another.
In the picture each colour represents a cluster according to the current iteration and each "X" is its centroid (old ones have been kept and marked with the number of the iteration in which they were computed).
[Some related links about empty cluster case, added later by @ttnphns: https://stackoverflow.com/q/41634047/868905; what's the implementation of SciKit-Learn K-Means for empty clusters?; Result of K-Means Algorithm Not Desired; How to implement k-means cluster analysis algorithm correctly?; https://stackoverflow.com/q/24919346/868905; https://stackoverflow.com/q/18009664/868905; https://stackoverflow.com/q/29243800/868905; https://stackoverflow.com/q/11075272/868905; ]