Clustering large 3D dataset into many clusters

Question

I have a 3D point cloud with several million points and I need to partition it into roughly 50k clusters. As the clusters have to be spherical, usually a drawback of k-means, k-means seems pretty appropriate. My problem is that $k$ is too big, thus the runtime is unacceptable. The clusters don't have to be exact, I can tolerate misclassifications quite well.

I found a paper on mini-batch k-means, which might work. And this paper utilizing MapReduce. I also read this and other questions, but question and answers are too vague. This (slide 2) source claims with the use of k-d trees runtime can be reduced from $O(l*K*m*n)$ to $O(m*logm)$, I can't find how that should work?

Is mini-batch k-means the way to go? Is there maybe some simple solution for low dimensional data (3D)?

I would appreciate a C++ implementation, so far I could only find mini batch k-means in scikit which I might translate. Can you recommend any other?

Answer 1

I have seen people use OPTICS on millions of points, but that won't create "spherical" clusters.

Probably something extremely simple like LEADER is what you want.

K-means with large k is pretty problematic. First of all, the runtime scales badly with k, and secondly on noisy data you will have clusters with just one outlier quite often.

For just 3 dimensional data, k-d-trees are definitely worth a try. In particular for large k. However these methods are not easy to implement. You'd need a nearest-neighbor join of two trees (one with the data, one with the centers). That requires some pretty complex data management that is not fun to do, and I don't know any k-d-tree library that would provide this functionality.

Mini-batch k-means won't help you much either. The batch sizes must be much larger than k. Plus, it never converges. So you'd need to run it as long as you can afford and then hope the result is good enough. That is okay for visual-bag-of-words but not for many other cases.