Clustering large scale data in fine-grained clusters

Question

I've got large amount of data (e.g. 100K) and I want to cluster them in very fine-grained clusters (e.g. 10K). I look for an appropriate algorithm that uses the similarity function instead of whole data and also I can't compute whole similarity matrix because of data scale. Python implementation is appreciated.

Answer 1

You are facing some scalabiliy issues here. Most clustering algorithms run in $O(n^2)$ or worse (most hierarchical clustering are implemented in $O(n^3)$); many even have an $O(n^2)$ memory requirement.

The only algorithms with a better runtime that right now come into my mind are DBSCAN and OPTICS: with an appropriate index structure these can run in $O(n \log n)$ and only need linear memory. However, if you do not have an appropriate index they also will be in quadratic runtime. And I don't know if there is a good index structure for textual similarity. Furthermore, you cannot specify the number of clusters you want to get out. They are meant to find structure in the data, not just partition it "somehow". They also will produce noise points they do not consider to be part of any cluster.

And of course there is k-means. It's runtime is linear in n: $O(n*k*i)$. But since you plan to use a very high value of k, and in particular i*k>n will likely hold, you are essentially quadratic, too.

Furthermore, as you are working with sparse data, you will need a variation of k-means known as "spherical k-means". And even then, there is quite some doubt whether or not the results of k-means are very meaningful. The problem is that the means will no longer be sparse. They are not real "text" either, obviously. So to some extend they are quite anomalous. So in my opinion, k-means is quite okay if you just need to partition your data set somehow, but I do not consider this to be cluster analysis. It will no longer partition the data according to some inherent structure of the data that the algorithm identified. Instead, it just tries to optimize the mathematical criterion of the sum-of-squared-deviations, which often has an unclear relationship to whatever "structure" there is in the data.

As for performance: there are a number of ways to speed up k-means, but very few implementations support anything but the most basic Lloyd algorithm. For example, you can put your means into a index structure to get the cost of an iteration to $O(n \log k)$, which does make a difference for large $k$. However, again, this will likely not work with textual similarity. Then there is a variant that not only tracks the closest mean, but keeps the distances to all other means. By assuming triangular inequality, it can avoid recomputing distances by tracking if any mean moved enough to become the new closest mean. This will effectively bring down the factor $n$, but comes at $O(n*k)$ memory cost. And your similarity function probably will not satisfy the triangular inequality...

But the main problems is that we don't know what your goal is. If we had more information of what you are trying to do with the clusters, we might be able to point you at some more appropriate method. I hope that I indicated enought that while k-means will produce a clustering of the desired number of clusters, you actually do not have any guarantee that it is much better than splitting the data into random cells. Largely, because you would need a definition of "better" to be able to get a better result.

Answer 2

I've had some success with using standard algorithms (e.g., k-means, etc.) and sparce matrices...are you familiar with those? There's a related StackOverflow question you may find helpful, but, basically, a sparse matrix is a compact way of representing a large matrix that is primarily zeros. Using these as a data type tends to help, as they bring a substantial memory reduction over using the full matrix. I know you asked about Python, but there are also some great resources for creating/working with these data types in R (e.g., the SparseM package).