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!

  • $\begingroup$ This is in fact two class clustering since you have two classes. For one class you would have only one class and would be interested in assessing how well does your observations fit the data (i.e. detecting outliers). $\endgroup$ – Tim Jul 29 '15 at 20:31
  • $\begingroup$ This learning problem has a name - PU learning. This is naturally to be used if positive examples are easy or natural to get but negatives are basically everything rest (difficult to get). In principle you want to learn a standard two class classifier but with a different criteria - optimize the area under PR curve. This software package allows you to train such a classifier code.google.com/p/sofia-ml $\endgroup$ – Vladislavs Dovgalecs Jul 29 '15 at 20:54

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.

  • $\begingroup$ Thanks a lot, that sounds quite promising. I'll take a look into it. $\endgroup$ – pemistahl Sep 8 '12 at 16:25

Here is a good thesis about one-class classification:

  • Tax, D. M.: One-class classification - Concept-learning in the absence of counter-examples, PhD thesis, Technische Universiteit Delft, 2001. (pdf)

This thesis introduces the method of Support Vector Data Description (SVDD), a one-class support vector machine that finds a minimal hypersphere around the data rather than a hyperplane that separates the data.

The thesis also reviews other one-class classifiers.

  • $\begingroup$ 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? $\endgroup$ – gung - Reinstate Monica Mar 7 '13 at 5:35
  • $\begingroup$ Thank you for summarizing. Please register & merge your accounts (you can find out how in the My Account section of our help center), then you will be able to edit & comment on your own posts. $\endgroup$ – gung - Reinstate Monica Jul 29 '15 at 19:37
  • $\begingroup$ @gung Thanks for the welcome. I'm thrilled to have received "Yearling" badge on StackOverflow itself, so now I can comment everywhere. $\endgroup$ – Josiah Yoder Jun 15 '16 at 23:40
  • $\begingroup$ @JosiahYoder, if you are the OP here, please merge your accounts. You can find out how in the My Account section of our help center. $\endgroup$ – gung - Reinstate Monica Jun 16 '16 at 1:04
  • $\begingroup$ I'm not the OP. Just a random SO user who happened across this question. $\endgroup$ – Josiah Yoder Jun 16 '16 at 15:12

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.

  • 1
    $\begingroup$ 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? $\endgroup$ – 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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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