18
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • $\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
    Commented Jul 29, 2015 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
    Commented Jul 29, 2015 at 20:54

5 Answers 5

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks a lot, that sounds quite promising. I'll take a look into it. $\endgroup$
    – pemistahl
    Commented Sep 8, 2012 at 16:25
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\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
    Commented Mar 7, 2013 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
    Commented Jul 29, 2015 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
    Commented Jun 15, 2016 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
    Commented Jun 16, 2016 at 1:04
  • $\begingroup$ I'm not the OP. Just a random SO user who happened across this question. $\endgroup$
    – Josiah Yoder
    Commented Jun 16, 2016 at 15:12
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Sep 8, 2012 at 15:13
0
$\begingroup$

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.

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

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.

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.