Clustering ~100,000 Short Strings in Python

I want to cluster ~100,000 short strings by something like q-gram distance or simple "bag distance" or maybe Levenshtein distance in Python. I was planning to fill out a distance matrix (100,000 choose 2 comparisons) and then do hierarchical clustering with pyCluster. But I'm running into some memory problems before even getting off the ground. For example, the distance matrix is too large for numpy.

aa = numpy.zeros((100000, 100000))
ValueErro开发者_StackOverflowr: array is too big.

Does this seem like a reasonable thing to do? Or am I doomed to memory problems in this task? Thanks for your help.

100,000 * 100,000 * 32bits = 40 GBytes, which would be a lot of RAM, so yes, you need to find another way. (And even if you could fit this data into memory, the calculation would take too long.)

One common and easy shortcut is to cluster a small random subset of the data, and after you find the clusters of this subset, just put the rest of the points into the clusters where they fit best.

10 billion elements is an awful lot. I don't know from q-grams, but if that matrix is sparse, you could use a 200,000-ish element dict.

Do you need the matrix? I assume you want to use a matrix for speed?

I have a k-means cluster algorithm (rather than a hierarchical cluster algorithm) and this calculates node distances as required. Probably only viable for fast distance metrics, though. And you have more data than I do - but you are bound by memory limitations.

1. There is a method in Machine Learning called Embedding which can, in principle, search for a solution for this problem using O(n+m) memory instead of O(n*m) (n=10^5 items, m=10^5 features). Unfortunately, I don't know of an available source code that is implemented in O(m+n). See:

   Euclidean Embedding of Co-occurrence Data. Amir Globerson, Gal Chechik, Fernando Pereira and Naftali Tishby. Journal of Machine Learning Research, JMLR, 8 (Oct), 2007. pdf / Matlab code

2. There could be other solutions. I think that you should ask this question at a forum of Machine Learning people, e.g., https://stats.stackexchange.com/, or even more specific for language processing: http://metaoptimize.com/qa/.