I'm writing code for k-means clustering. I have around 100000 vectors of size 128x1 (SIFT descriptors). I'm trying different initialization methods such as Forgy and Random Partition. What if suppose, no vectors are classified to a cluster (in one of the iterations)? How to calculate centroid for that cluster?
This is mostly an issue with really bad initialization (random vector generation as well as random labeling are stupid, don't use it - choose k points wth sampling, or k-means++) and with data where k-means doesn't work well at all. So if this happens, you know the results won't be good!
Either way, the standard and straightforward solution is simple: use the previous mean if a cluster becomes empty. It could be assigned points later again. And if it doesn't, well, then the cluster is empty. No surprises here, no infinite loops, convergence issues, etc.
If you get an empty cluster, it has no center of mass. You can simply ignore this cluster (set
k=k-1 for next iteration), or repeat the k-means run from a new initialization. You can also choose to place a random data point into that cluster and carry on with the algorithm if you must have this specific number of K clusters.
If it keeps happening, there is a good chance that your K parameter is too high. You should iterate over a few different values for k and pick the best.
Here is how an empty cluster might happen:
- Consider the following example with 7 data points. The different shapes of the points are just to show that there are actually 2 natural clusters (but we do not know that before running the algorithm). In this case we choose
k = 3.
- Three random cluster centers are initialized. At the end of first iteration points 3, 1, 2, and 7 will be in one cluster. 4 and 5 will be in another cluster. And 6 will be in the last cluster. Note here that the distance between 3 and 4 is larger than the distance between 4 and 5 and so 4 is assigned to the cluster represented by 5. Before we begin the second iteration we update the cluster centers and the following picture shows the centers and the clusters at the end of first step.
- Now, the cluster center for the red cluster moved closer to point 4 due to 1, 2, and 7. And the cluster center for the blue cluster moved away from 5 due to point 4. In the next iteration point 4 will decide that it is closer to the red cluster and point 5 will decide that it is closer to the green cluster. This will cause blue cluster to be empty as shown below.
The images were taken from the following link: K-Means Empty Cluster Example