21
$\begingroup$

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 ?

Improve this question
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – Iterator
    Commented Aug 26, 2011 at 17:59
  • 1
    $\begingroup$ 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. $\endgroup$
    – Iterator
    Commented Aug 26, 2011 at 18:41
  • 1
    $\begingroup$ 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 . $\endgroup$
    – Zach
    Commented Aug 26, 2011 at 20:33
  • 2
    $\begingroup$ 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. $\endgroup$
    – DavidDLewis
    Commented Aug 26, 2011 at 22:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – user56915
    Commented Oct 3, 2014 at 21:24

5 Answers 5

Reset to default
13
$\begingroup$

This should be possible to make it work as long as the data is represented as a sparse data structure such as scipy.sparse.csr_matrix instance in Python. I wrote a tutorial for working on text data. It is further possible to reduce the memory usage further by leveraging the hashing trick: adapt it to use the HashingVectorizer instead of the CountingVectorizer or the TfidfVectorizer. This is explained in the documentation section text features extraction.

Random Forests are in general much more expensive than linear models (such as linear support vector machines and logistic regression) and multinomial or Bernoulli naive Bayes and for most text classification problems that do not bring significantly better predictive accuracy than simpler models.

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.

Edited in April 2015 to reflect the current state of the scikit-learn library and to fix broken links.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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). $\endgroup$
    – user721975
    Commented Aug 26, 2011 at 18:04
  • $\begingroup$ 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. $\endgroup$
    – Iterator
    Commented Aug 26, 2011 at 18:43
  • $\begingroup$ +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. $\endgroup$
    – Iterator
    Commented Aug 26, 2011 at 18:44
  • $\begingroup$ @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. $\endgroup$
    – Iterator
    Commented Aug 26, 2011 at 20:43
  • $\begingroup$ As for "non standard" dimension reduction (using random projections) and feature hashing check the hashing trick by John Langford and this discussion on metaoptimize. $\endgroup$
    – ogrisel
    Commented Aug 26, 2011 at 21:11
10
$\begingroup$

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

Improve this answer
$\endgroup$
0
3
$\begingroup$

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.

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

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.

Improve this answer
$\endgroup$
10
  • $\begingroup$ +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. $\endgroup$
    – user721975
    Commented Sep 4, 2011 at 20:11
  • $\begingroup$ 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? $\endgroup$
    – user721975
    Commented Sep 4, 2011 at 20:13
  • $\begingroup$ @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. $\endgroup$
    – DavidDLewis
    Commented Sep 6, 2011 at 12:46
  • $\begingroup$ @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. $\endgroup$
    – DavidDLewis
    Commented Sep 6, 2011 at 12:49
  • 1
    $\begingroup$ 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? $\endgroup$
    – DavidDLewis
    Commented Sep 7, 2011 at 22:26
1
$\begingroup$

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 / ...).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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