2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
4
$\begingroup$

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:

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

enter image description here

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

enter image description here

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

enter image description here

The images were taken from the following link: K-Means Empty Cluster Example

| improve this answer | |
$\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.