title: What to do when KMeans returns fewer than K clusters?
body: <p>I've implemented K-Means in Java and have a bit of a head scratcher.  I select my initial centroids by choosing a random value in each dimension within the range of values of the data points.  I've run into cases where this results in one or more of these centroids not ending up being the closet centroid of <em>any</em> data point.  So what do I do for the next iteration?  Just leave it at its original randomized value?  Pick a new random value? Compute as an average of the other centroids?  Seems like this isn't accounted for in the original algorithm, but probably I've just missed something.</p>