Dealing with unassigned clusters in (MiniBatch)KMeans? [duplicate]

Question

I'm clustering a largeish dataset (3-4 million rows, 3+ features, all numeric), and I'm clustering with a large k (f~=2000). I'm not actually interested in finding clusters, I and just using kmeans because it relatively evenly partitions non-clustered data (by count). I need all clusters to be assigned to at least some data (ideally enough to do a linear regression on that cluster, so >50), but quite often the clustering fails and some clusters do not get assigned:

>>> mbkmeans = MiniBatchKMeans(n_clusters=2187)
>>> len(np.unique(mbkmeans.fit_predict(X)))
# .../k_means_.py:1381: RuntimeWarning: init_size=300 should be larger than k=2187. Setting it to 3*k
  init_size=init_size)
2165
>>> kmeans.n_iter_
12

This is not due to duplicated data - in each dataset there are no more than 5% duplicated rows. I suspect it is due to the problem described at http://user.ceng.metu.edu.tr/~tcan/ceng465_f1314/Schedule/KMeansEmpty.html, whereby cluster centres end up in a no-man's land between two or more other clusters that are closer to all the intermediate data.

So, the question is, is there any general procedure for avoiding this problem?

And in particular, is there a way to do that in scikit-learn? Or is there a better set of arguments than the default for MiniBatchKmeans that I could use (there are a couple that I don't fully understand)?

Answer 1

Don't use minibatch unless your data does not find into memory anymore. That variant was designed to work out-of-core on extremely large (Google scale) fast sets.

Because it only processes a random sample each iteration, it

1. Never finishes, you have to define some threshold to stop, and

2. As points enter and leave the sample, clusters may become empty easily. As this appears to be a problem, don't use kmeans.

Beware that k-means not at all "relatively evenly partiton (by count)". On the contrary, k-means frequently produces clusters that contain almost the entire data set, and some "outlier" clusters that have exactly one point. By the k-means objective, these solutions are good, as they reduce variance. If you have clusters disappear, then they were almost empty before, not "evenly partitioned by count".