0
$\begingroup$

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

$\endgroup$

marked as duplicate by ttnphns, Michael Chernick, mdewey, jbowman, kjetil b halvorsen Sep 23 '17 at 18:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I'm running hundreds of models on 100Mb+ datasets. Mini-batch k-means usually converges well in a couple of minutes on the machines I'm using. K-means takes hours. I need to iterate fast, so K-means is not practical. Good point in the last paragraph though. I guess I have been misinterpreting it a bit. Will have to have a think about that. $\endgroup$ – naught101 Oct 4 '17 at 2:45
  • $\begingroup$ Mini Batch does not "converge", ever. It just stops without converging. You can also stop k-means after 10 iterations if you only want an approximation. Benchmark which is better. $\endgroup$ – Anony-Mousse Oct 4 '17 at 5:40

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