4
$\begingroup$

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

Each colour represent a cluster in the current iteration and each X represent its centroid (each centroid is marked with the number of the iteration in which it has been 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; ]

$\endgroup$
  • 1
    $\begingroup$ What are the points that are plotted? Does each x represent a cluster centroid? What are the os? What do the 0, 1, & 2 represent? $\endgroup$ – gung Mar 13 '14 at 18:50
  • $\begingroup$ First post edited. Thank you for pointing that out. $\endgroup$ – Maurizio Mar 13 '14 at 18:59
  • $\begingroup$ Thanks, are you trying to implement the standard k-means algorithm by hand, or code your own implementation from scratch? I believe any standard k-means function (eg, kmeans() in R) has methods for dealing w/ this situation automatically. $\endgroup$ – gung Mar 13 '14 at 19:05
  • $\begingroup$ I am aware of the built-in kmeans() function, but I am trying to write the standard algorithm from scratch. As soon as I fix it I'll be able to compare the results. At this moment I'm looking for some theoretical reasons why I should prefer one solution or another. $\endgroup$ – Maurizio Mar 13 '14 at 19:18
  • 1
    $\begingroup$ Flippant answer: Play Lonely won't leave me alone in the background, have a sip of your favorite beverage, and appreciate the plot, take it all in. $\endgroup$ – Penguin_Knight Mar 14 '14 at 1:20
5
$\begingroup$

This can naturally happen in Lloyds algorithm; don't try to prevent it. Instead, implement one of the workarounds (e.g. choosing the most-distant point as additional cluster centroid, or simply allowing empty clusters).

You may want to put some safeguards in place - for example, when k is chosen larger than the data set size, there just is no solution that doesn't involve empty clusters.

Note that this mostly happens when you have really bad starting centroids. E.g. when you initialized them by randomly placing centriods on your data space. Choosing existing data points as initial centroids is much more robust (but this may still happen)

MacQueens k-means should be safe from this effect, too.

$\endgroup$
  • $\begingroup$ +1. May I ask you to unwrap, in some detail, what is the difference between Lloyd and MacQueen versions? $\endgroup$ – ttnphns Mar 14 '14 at 5:29
  • $\begingroup$ MacQueen uses an iterative single-pass approach. The first k objects are used as initial centroids, then new object are assigned to their neares center (which is immediately updated). As no reassignments happen, a cluster cannot lose all its points. $\endgroup$ – Anony-Mousse Mar 14 '14 at 7:12
  • $\begingroup$ +1, I just implemented one by choosing existing points as initial centroids, and yes that's more robust. Kmeans++ might also be good. $\endgroup$ – avocado May 4 '14 at 4:39
  • $\begingroup$ choosing the most-distant point as additional cluster centroid Most distant from what? From that (empty) cluster's last valid centroid? From the centroid of of the currently biggest (most populated) cluster? Else? $\endgroup$ – ttnphns Jan 20 '17 at 12:32
  • $\begingroup$ Whatever you prefer. I don't see why one of these variations would be wrong. Benchmark it on a number of data sets to find out what works for you. $\endgroup$ – Anony-Mousse Jan 20 '17 at 12:36

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.