Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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

share|improve this question
1  
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? –  ttnphns Sep 15 '11 at 6:40
    
please check the edit on my original post which answers your questions –  Alexandros Sep 15 '11 at 11:03
add comment

2 Answers 2

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?

share|improve this answer
    
Concerning k-means, do you think it would achieve a N complexity? –  Alexandros Sep 16 '11 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) –  benhamner Sep 20 '11 at 2:47
add comment

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

share|improve this answer
    
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. –  Alexandros Sep 15 '11 at 13:43
    
Classification and clustering have much in common. –  peri4n Sep 15 '11 at 13:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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