# Clustering of 10's of millions of high dimensional data

I have a set of 50 million text snippets and I would like to create some clusters out of them. The dimensionality might be somewhere between 60k-100k. The average text snippet length would be 16 words. As you can imagine, the frequency matrix would be pretty sparse. I am looking for a software package / libray / sdk that would allow me to find those clusters. I had tried CLUTO in the past but this seems a very heavy task for CLUTO. From my research online I found that BIRCH is an algorithm that can handle such problems, but, unfortunately, I couldn't find any BIRCH implementation software online (I only found a couple of ad-hoc implementations, like assignment projects, that lacked any sort of documentation whatsoever). Any suggestions?

EDIT: Here is some explanation on what "dimensionality" and "similarity" is in the context of my problem: Each text-snippet is a sentence taken from a huge text corpus (news articles). A vector is created for each sentence by projecting each text snippet onto a N-dimensional space where each dimension corresponds to a word. So, if a sentence is:

"I like red apples more than green apples"


then the corresponding vector would have dimensions "I":1, "like":1, "apples":2 "more":1 etc...

I will decide which of the millions of distinct words will make up the space upon which the projection will be made. Typically the top-N most frequent words will be selected for this.

Then, the similarity will simply be the distance between the vectors of two sentences. (usually I normalize the vectors first and then take the dot product between two vectors - this is known as "cosine similarity")

• Pardon for asking, what define "dimensionality" in your case? And what the characteristics are you going to cluster snippets by? Similarity between snippets - then what similarity? Commented Sep 15, 2011 at 6:40
• please check the edit on my original post which answers your questions Commented Sep 15, 2011 at 11:03

## 2 Answers

One option is to use Latent Dirichlet Allocation (LDA) to model the underlying topics that occur in the sentences. Edwin Chen has a good explanation of LDA here.

Here's one python package that contains an LDA implementation. It handles cases that don't fit in memory as well (those yours should when its represented as a sparse matrix).

Another option is to apply kmeans to the sparse matrix. If runtime is an issue in either case, simply reduce the dimensionality of the feature vector.

What is the goal of clustering these sentences?

• Concerning k-means, do you think it would achieve a N complexity? Commented Sep 16, 2011 at 10:54
• K-mean's time complexity is linear with respect to each of its parameters (number of samples, number of clusters, number of features) Commented Sep 20, 2011 at 2:47
• Thanks for this answer- I would like to ask a follow up question, I need to group similar short documents together. I am not sure if LDA will work for such short text documents.
– pnv
Commented Jan 30, 2017 at 6:25

This is a typical problem solved by support-vector-machines. One can achieve great results in text-mining using SVM.

For software-suites see: libSVM or svm-light

• I thought SVMs are used for classification tasks. I just found a clustering solution based on SVMs though, but I was wondering if it could handle such a huge dataset. Commented Sep 15, 2011 at 13:43
• Classification and clustering have much in common.
– user6325
Commented Sep 15, 2011 at 13:58