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; ]

Improve this question
$\endgroup$
6
  • 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 - Reinstate Monica
    Commented Mar 13, 2014 at 18:50
  • $\begingroup$ First post edited. Thank you for pointing that out. $\endgroup$
    – Maurizio
    Commented Mar 13, 2014 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 - Reinstate Monica
    Commented Mar 13, 2014 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
    Commented Mar 13, 2014 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
    Commented Mar 14, 2014 at 1:20

1 Answer 1

Reset to default
9
$\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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ +1. May I ask you to unwrap, in some detail, what is the difference between Lloyd and MacQueen versions? $\endgroup$
    – ttnphns
    Commented Mar 14, 2014 at 5:29
  • 1
    $\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$
    – Has QUIT--Anony-Mousse
    Commented Mar 14, 2014 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
    Commented May 4, 2014 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
    Commented Jan 20, 2017 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$
    – Has QUIT--Anony-Mousse
    Commented Jan 20, 2017 at 12:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.