5
$\begingroup$

I have a data set that has 10k documents, each of which is mapped to one and only one of 4k categories. This forms my training set.

My requirement is that when a new, unseen document comes in, I need to be able to identify all the categories (from among the 4k categories) to which it belongs.

What is the best way to go about doing this? My problem conforms to what's generally known as multi-label classification in the literature, and I see plenty of papers, but no readily available software. I was hoping to know if anyone is aware of any off-the-shelf tools that would do this task.

Thanks in advance.

Update 1: Based on some comments below I am updating my question. Although I have 4k categories and only 10k documents, the distribution of these documents into categories is highly skewed - in other words, there are a small number of categories that have most of the training documents. I am OK with retaining categories that have sufficient training data, and throwing away the other categories if need be. The bigger problem is identifying all the categories of unseen document.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Are the categories mutually exclusive, that is there is no hierarchy linking them together? Also, I'm not sure to understand the second paragraph because it seems to say that an unseen document might belong to several categories while the training set only considers a one-to-one mapping. Could you clarify, please? $\endgroup$
    – chl
    Commented Jul 11, 2011 at 22:13
  • $\begingroup$ @chi : Yes categories are mutually exclusive (although at a later point, I will need to handle hierarchical categories also). And yes the training data has only one to one mapping. Although in training data also a document can belong to multiple categories, since a human annotated the training data for us, in order to simply her task we only asked her to do one to one mapping. Good call. $\endgroup$
    – Andy
    Commented Jul 11, 2011 at 22:18

6 Answers 6

Reset to default
5
$\begingroup$

As @mbq suggests, a battery of binary classifiers is a good place to start. Ridge regression classifiers work pretty well on text classification problems (choose the ridge parameter via leave-one-out cross-validation. If training time is not an issue, also use the bootstrap as a further protection against over-fitting; the committee of boostrap classifiers can be amalgamated into one, so it doesn't have a computational cost at runtime).

However, as there are 4K classes and only 10K samples, it will probably be necessary to look at the hierarchy of classes and try to predict whether the page fits into broad categories first.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Why an LOO scheme in this particular case? $\endgroup$
    – chl
    Commented Jul 11, 2011 at 22:05
  • 1
    $\begingroup$ Mostly because it is cheap (almost free), and I have found it to be reliable in the past for text classification problems (even though it does have a high variance compared to other estimators). Bagging gives a "belt-and-braces" approach to doubly guard against over-fitting, but it only usually makes a quite minor improvement. $\endgroup$
    – Dikran Marsupial
    Commented Jul 12, 2011 at 7:30
  • $\begingroup$ @DikranMarsupial Hi Dikran, your answer is quite insightful. But could you please elaborate on "If training time is not an issue, also use the bootstrap as a further protection against over-fitting; the committee of boostrap classifiers can be amalgamated into one, so it doesn't have a computational cost at runtime" and about bagging? More specifically, what do you mean by bootstrap here? Also the same about bagging. Thank you. $\endgroup$
    – Flake
    Commented Oct 26, 2011 at 9:13
  • 1
    $\begingroup$ Bootstrapping involves training a large number of models on resampled datasets, where the resampling is performed with replacement, and then use the samples in each iteration that are not used in training to test the model (so it is a bit like repeated randomised cross-validation). Bagging means using the models generated via bootstrap to form a committee model, see en.wikipedia.org/wiki/Bootstrap_aggregating . The repeated retraining can take a lot of time, but it is a good belt-and-braces approach to avoiding over-fitting. $\endgroup$
    – Dikran Marsupial
    Commented Oct 26, 2011 at 14:47
4
$\begingroup$

About multilabel classification, the baseline (but usually quite good) approach is just to make a battery of binary classifiers, each trained to recognize one class versus all other, use them all on each sample and combine their answers.
This is trivial to implement, so almost any tool will do.

However, you have other problem -- an ultrapoor training set. 10k samples in 4k classes gives 2-3 examples per class -- this is almost nothing; I can at most imagine some embarrassing 1-NN method in this setting.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sounds like a good idea (at least to get baseline). So when I build a classifier to distinguish class $X$ from the rest of the classes (say $Y$) what would the training data for $Y$ be? I mean for class $X$, I have documents that are labeled as class $X$, but what about $Y$? $\endgroup$
    – Andy
    Commented Jul 11, 2011 at 20:12
  • $\begingroup$ Usually some sample of Y to get a more-less balanced set; however in case of your, let's say, sparse train you would need something integrated with this hierarchical training Dikran suggested or any other method you would use. $\endgroup$
    – user88
    Commented Jul 13, 2011 at 22:28
2
$\begingroup$

Try using R. You can use the factor data type to store what you are calling each document's "label."

Before you use any predictive functions, you'll have to calculate some quantitative attributes about each document. This is going to depend on the nature of your problem, but check out the Natural Language Processing section on CRAN for help with this step.

Once you've converted your documents into a dataframe with one row per document, and variables representing that document's classification, as well as covariates describing the document's content and metadata, you can start building predictive models. You might start with linear discriminant analysis.

With 4k classes and over 10k documents, I think it is going to be difficult to develop a good classifier. See if any of the authors you've been reading have written packages for R.

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

One of my homework assignments this semester was exactly to do his (well, not exactly, most of it was already implemented and we had to do some improvements and experimentation).
You can read the details here.

Anyway, whatever method you choose to use, I suggest to take a look at Weka. Most probably the classifier you are looking for is already implemented there.

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

In general, you'll need to specify what make each category unique to be able to choose which classifier to use. In a silly example, if categories are based on the size of the document... you got the idea.

One good classifier that I used in this task was using the Normalized Compression Distance (NCD). It measures how close two documents are using compressors like ZIP.

For example: you have a document D and you have 10 categories C1, C2... C10. In each category you have one example document: C1a in category C1, C2a in category C2...

To verify the document D, you'll concatenate it with C1a and compress, then concatenate D with C2a and compress, and so on. By doing some calculation, you'll end up have NCD measures. Them you attribute it to the category that gave you the minimum NCD value.

The good point is that I'll end up my master degree in two weeks, using NCD as authorship attribution. Got correct attributions > 95% when dealing with 20 classes, > 55% when dealing with 100 classes, all of portuguese documents from newspapers. The bad point is that it's written in portuguese...

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

I haven't used them yet, but Mulan and Meka are multi-label addons for Weka. Meka seems more off the shelf, and includes support for Mulan.

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.