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 to deal with a text classification problem. A web crawler crawls webpages of a certain domain and for each webpage I want to find out whether it belongs to only one specific class or not. That is, if I call this class Positive, each crawled webpage belongs either to class Positive or to class Non-Positive.

I already have a large training set of webpages for class Positive. But how to create a training set for class Non-Positive which is as representative as possible? I mean, I could basically use each and everything for that class. Can I just collect some arbitrary pages that definitely do not belong to class Positive? I'm sure the performance of a text classification algorithm (I prefer to make use of a Naive Bayes algorithm) highly depends on which webpages I choose for class Non-Positive.

So what shall I do? Can somebody please give me an advice? Thank you very much!

share|improve this question

5 Answers 5

up vote 5 down vote accepted

The Spy EM algorithm solves exactly this problem.

S-EM is a text learning or classification system that learns from a set of positive and unlabeled examples (no negative examples). It is based on a "spy" technique, naive Bayes and EM algorithm.

The basic idea is to combine your positive set with a whole bunch of randomly crawled documents. You initially treat all the crawled documents as the negative class, and learn a naive bayes classifier on that set. Now some of those crawled documents will actually be positive, and you can conservatively relabel any documents that are scored higher than the lowest scoring true positive document. Then you iterate this process until it stablizes.

share|improve this answer
    
Thanks a lot, that sounds quite promising. I'll take a look into it. –  pemistahl Sep 8 '12 at 16:25

Good thesis about one-class clasification: Tax, D. M.: One-class classification - Concept-learning in the absence of counter-examples, PhD thesis, Technische Universiteit Delft, 2001.

share|improve this answer
    
Welcome to the site, @nub. We hope to build a permanent repository of statistical information, as such, we worry about the possibility of linkrot. Would you mind giving a summary of the info in that thesis in case the link goes dead? –  gung Mar 7 '13 at 5:35

Good training requires data that provides good estimates of the individual class probabilities. Every classification problem involves at least two classes. In your case the second class is anyone that is not in the positive class. To form a good decision boundary using Bayes or any other good method is best done with as much training data randomly selected from the class. If you do non random selection you might get a sample that doesn't truly represent the shape of the class conditional densities/distributions and could lead to a poor choice of the decision boundary.

share|improve this answer
1  
You are right, this is exactly what bothers me. How to select a sample of non-positive samples that leads to a good decision boundary? Is doing a random selection the best I can do? –  pemistahl Sep 8 '12 at 15:13

I agree with Michael.

Regarding your question about random selection; yes: you have to select randomly from the complementary set of your 'positives'. If there is any confusion that it is possible that your 'positives' are not fully defined as 'pure positive', if I may use that phrase, then you can also try at the least some kind of matched definition for positives so that you will control on those variables that are generating potentially some contamination on the definition of 'positive'. In this case you have to correspondingly match on the same variables on the 'non-positive' side also.

share|improve this answer

An article that may be of interest is:

"Extended nearest shrunken centroid classification: A new method for open-set authorship attribution of texts of varying sizes", Schaalje, Fields, Roper, and Snow. Literary and Linguistic Computing, vol. 26, No. 1, 2011.

Which takes a method for attributing a text to a set of authors and extends it to use the possibility that the true author is not in the candidate set. Even if you don't use the NSC method, the ideas in the paper may be useful in thinking about how to proceed.

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.