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 am looking to do classification on my text data. I have 300 classes, 200 training documents per class (so 60000 documents in total) and this is likely to result in very high dimensional data (we may be looking in excess of 1million dimensions).

I would like to perform the following steps in the pipeline (just to give you a sense of what my requirements are):

  1. Converting each document to feature vector (tf-idf or vector space model)
  2. Feature selection (Mutual Information based preferably, or any other standard ones)
  3. Training the classifier (SVM, Naive Bayes, Logistic Regression or Random Forest)
  4. Predicting unseen data based on the classifier model trained.

So the question is what tools/framework do I use for handling such high dimensional data? I am aware of the usual suspects (R, WEKA...) but as far as my knowledge goes (I may be wrong) possibly none of them can handle data this large. Is there any other off the shelf tool that I could look at?

If I have to parallelize it, should I be looking at Apache Mahout? Looks like it may not quite yet provide the functionality I require.

Thanks to all in advance.


Update: I looked around this website, R mailing list and the internet in general. It appears to me that the following problems could emerge in my situation:

(1) Preprocessing of my data using R (tm package in particular) could be impractical, since tm will be prohibitively slow.

(2) Since I will need to use an ensemble of R packages (pre-processing, sparse matrices, classifiers etc.) interoperability between the packages could become a problem, and I may incur an additional overhead in converting data from one format to another. For example, if I do my pre-processing using tm (or an external tool like WEKA) I will need to figure out a way to convert this data into a form that the HPC libraries in R can read. And again it is not clear to me if the classifier packages would directly take in the data as provided by the HPC libraries.

Am I on the right track? And more importantly, am I making sense :-) ?


share|improve this question
    
R can handle data sets much larger than this, you just need to make good use of the tools available. There is no difference between what can be accomplished in any major language or environment, though Weka and Mahout lag in terms of what's available. FWIW, this is a fairly small sample size, and 1M dimensions is no biggie, but it's also overkill statistically. My recommendations are R or Python, as they're both free & easy for beginners. Matlab is not free, but also good. It also incurs a big tax when you use a lot of computers. –  Iterator Aug 26 '11 at 17:59
1  
A far more salient point is that you have more classes than examples per class and you're embedding it in a very high dimensional space. I'm not sure you're going to get very good class separation here. Do you have some structural relations for your classes? If so, them some of these methods may fare poorly without that insight. –  Iterator Aug 26 '11 at 18:41
1  
You can use the foreach library write parallel code in R. This works especially well in conjunction with random forests, which are inherently easy to parallelize . –  Zach Aug 26 '11 at 20:33
2  
A few questions: 1) Are you interested in comparing all the different types of learning approaches you mention, or do you just need one to get a job done? 2) Does each document belong to 1, 1 or more, or 0 or more of the classes? 3) Do you specifically want to use feature selection for some reason, or did you just think it was necessary? I agree with the other comments that this is a modest-sized problem by today's standards, and dimensionality reduction is not necessary. –  DavidDLewis Aug 26 '11 at 22:36
1  
I am working on text classification involving nearly 10,000 topics (e.g. classes or categories or whatever term you prefer). I am currently working on tuning this text classification system at this scale. I cannot share my own techniques as they are proprietary, but I have one bit of advice: be very cautious in assuming that some suggested technique scales unless it has already been proven to do so. In my experience, very few do. –  sfgower Oct 3 at 21:24

5 Answers 5

up vote 8 down vote accepted

If you use some random projections to reduce the dimensionality to a the order of 1e4 or 1e5 before fitting the classifiers, scikit-learn should be able to deal with this (as long as the sparse vectorized data fits in memory as a scipy.sparse.csr_matrix datastructure instance). I wrote a tutorial for working on text data that might help you get started and give you a feeling.

Random projections are not yet implemented by default in sklearn but should be easy to get right using a bit of scipy.sparse fu. Alternatively it would be possible to replace the default dictionary-based text Vectorizer with a hashing feature vectorizer. This component is planned but not yet implemented either.

Note that Random Forests are not yet implemented in sklearn but that will probably be the case soon (decision tree work is under way for instance).

If scikit-learn ends up not being able to scale to your problem, Vowpal Wabbit will do (and probably faster than sklearn) albeit it does not implement all the models your are talking about.

share|improve this answer
    
Well the problem with using any "non standard" dimension reduction technique is that you are likely to run into trouble when you try to publish your work. In the text classification field at least, I know for a fact that reviewers like to see the commonly used techniques (makes it easier to compare against existing classification techniques also). –  user721975 Aug 26 '11 at 18:04
    
Don't worry - @ogrisel didn't mention anything non-standard, at least not as it pertains to state of the art text classification, though I haven't yet read his tutorials. –  Iterator Aug 26 '11 at 18:43
    
+1 I think Python is probably an enjoyable way to go. There are some very recent packages in R for text mining, but if one has more computational than statistical expertise and interests, Python would be my recommendation. –  Iterator Aug 26 '11 at 18:44
    
@ogrisel: Kudos for the contributions you & others have made to sklearn. I have recommended it to many who work in Python - the whole design is exemplary. –  Iterator Aug 26 '11 at 20:43
    
As for "non standard" dimension reduction (using random projections) and feature hashing check the hashing trick by John Langford and this discussion on metaoptimize. –  ogrisel Aug 26 '11 at 21:11

Gensim for Python is magic. And since it's in Python, you can use it in conjunction with @ogrisel's suggestion.

share|improve this answer
    
+1 Great suggestion. –  Iterator Aug 26 '11 at 18:45

Not to toot my own horn, but I made a pretty popular video series on text analytics with Rapidminer. You can see it here:

http://vancouverdata.blogspot.com/2010/11/text-analytics-with-rapidminer-loading.html

You can likely avoid doing feature selection, just use a classifier that doesn't create a million * million matrix in memory :)

Logistic regression will choke on that many dimensions. Naive Bayes assumes independent dimensions, so you will be fine. SVM doesn't depend on the number of dimensions (but on the number of support vectors) so it will be fine as well.

300 is a lot of classes though. I would start with only a few and work your way up.

share|improve this answer
    
Great pointer and advice. Thanks. Can you please elaborate what you mean by "start with only a few and work your way up"? –  user721975 Aug 28 '11 at 16:23
    
well, instead of 300 classes (like "violin, viola, cello, trumpet..."), you could reclassify them to a smaller number such as "string, brass" . –  Neil McGuigan Aug 28 '11 at 19:09
    
OK, I get it now. –  user721975 Aug 28 '11 at 20:01

First, based on your comments, I would treat this as 300 binary (yes/no) classification problems. There are many easy-to-use open source binary classifier learners, and this lets you trade time for memory.

SVMs and logistic regression are probably the most popular approaches for text classification. Both can easily handle 1000000 dimensions, since modern implementations use sparse data structures, and include regularization settings that avoid overfitting.

Several open source machine learning suites, including WEKA and KNIME, include both SVMs and logistic regression. Standalone implementations of SVMs include libSVM and SVMlight. For logistic regression, I'll plug BXRtrain and BXRclassify, which I developed with Madigan, Genkin, and others. BXRclassify can build an in-memory index of thousands of logistic regression models and apply them simultaneously.

As for converting text to attribute vector form, I somehow always end up writing a little Perl to do that from scratch. :-) But I think the machine learning suites I mentioned include tokenization and vectorization code. Another route would be to go with more of a natural language toolkit like LingPipe, though that may be overkill for you.

share|improve this answer
    
+1 Good comments. If I were to do 300 yes/no classifications, how would I pick the negative training data for a class? Positive data obviously is the documents that belong to the class. –  user721975 Sep 4 '11 at 20:11
    
Another comment. SVM/Logistic reg can for sure handle a million dimensions, but how could I run experiments to pick parameters for these classifiers? For example, on a small data set you could run 10fold cross validation to decide on the parameters, but what approach does one take for such large data so that the algorithm finishes running in a reasonable time? –  user721975 Sep 4 '11 at 20:13
    
@user721975: For a particular discrimination, the positive documents are those with the label X on them, and the negative documents are all the rest of the documents. –  DavidDLewis Sep 6 '11 at 12:46
    
@user721975: It's hard to give general advice about the running time, since details vary so much among algorithms and implementations. 10-fold cross validation may not be impractical for your data set: 60000 examples is not that matter. –  DavidDLewis Sep 6 '11 at 12:49
1  
Unbalanced training sets are not necessarily a problem. But actually I realize there's something I'm confused about: since documents can belong to 0, 1, or several classes, what do you mean by having 200 training documents per class? Did you do something to remove documents with 0 classes or 2+ classes? In general, how did you generate this set of 60000 documents? –  DavidDLewis Sep 7 '11 at 22:26

Since Sklearn 0.13 there is indeed an implementation of the HashingVectorizer.

EDIT: Here is a full-fledged example of such an application from sklearn docs

Basically, this example demonstrates that you can classify text on data that cannot fit in the computer's main memory (but rather on disk / network / ...).

share|improve this answer

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.