Reliable Negative Extracting Based on kNN for Learning from Positive and Unlabeled Examples

Journal of ComputersPublished 1 January 2009

Bangzuo Zhang, Wanli Zuo

DOI10.4304/jcp.4.1.94-101

Citations42

TL;DR

A new reliable negative extracting algorithm for step 1 is proposed that adopts kNN algorithm to rank the similarity of unlabeled examples from the k nearest positive examples, and set a threshold to label some unlabeling examples that lower than it as the reliable negative examples rather than the common method to label positive examples.

Abstract

Many real-world classification applications fall into the class of positive and unlabeled learning problems. The existing techniques almost all are based on the two-step strategy. This paper proposes a new reliable negative extracting algorithm for step 1. We adopt kNN algorithm to rank the similarity of unlabeled examples from the k nearest positive examples, and set a threshold to label some unlabeled examples that lower than it as the reliable negative examples rather than the common method to label positive examples. In step 2, we use iterative SVM technique to refine the finally classifier. Our proposed method is simplicity and efficiency and on some level independent to k. Experiments on the popular Reuter21578 collection show the effectiveness of our proposed technique.

Keywords

Computer Science

The Nature of Statistical Learning Theory

39,279 Citations1995Vladimir Vapnik

Lecture notes in computer scienceText categorization with Support Vector Machines: Learning with many relevant features

7,925 Citations1998Thorsten Joachims

SVMs achieve substantial improvements over the currently best performing methods and behave robustly over a variety of di-erent learning tasks, eliminating the need for manual parameter tuning.

Technical reportsMaking Large-Scale SVM Learning Practical

4,317 Citations2006Thorsten Joachims

This chapter presents algorithmic and computational results developed for SVM light V 2.0, which make large-scale SVM training more practical and give guidelines for the application of SVMs to large domains.

View PDF

A re-examination of text categorization methods

2,660 Citations1999Yiming Yang, Xin Liu

The results show that SVM, kNN and LLSF signi cantly outperform NNet and NB when the number of positive training instances per category are small, and that all the methods perform comparably when the categories are over 300 instances.

View PDF

Information RetrievalAn Evaluation of Statistical Approaches to Text Categorization

1,946 Citations1999Yiming Yang

Analysis and empirical evidence suggest that the evaluation results on some versions of Reuters were significantly affected by the inclusion of a large portion of unlabelled documents, mading those results difficult to interpret and leading to considerable confusions in the literature.

One-class svms for document classification

1,225 Citations2002Larry M. Manevitz, Malik Yousef

The SVM approach as represented by Schoelkopf was superior to all the methods except the neural network one, where it was, although occasionally worse, essentially comparable.

Building text classifiers using positive and unlabeled examples

672 Citations2004B. Liu, Y. Dai +3 more

A more principled approach to solving the problem of building text classifiers using positive and unlabeled examples based on a biased formulation of SVM is proposed, and it is shown experimentally that it is more accurate than the existing techniques.

Partially Supervised Classification of Text Documents

516 Citations2002Bing Liu, Wee Sun Lee +2 more

This paper shows that the problem of identifying documents from a set of documents of a particular topic or class P and a large set M of mixed documents, and that under appropriate conditions, solutions to the constrained optimization problem will give good solution to the partially supervised classification problem.

PEBL

277 Citations2002Hwanjo Yu, Jiawei Han +1 more

The Positive Example Based Learning (PEBL) framework for Web page classification is introduced which eliminates the need for manually collecting negative training examples in pre-processing and an algorithm called Mapping-Convergence (M-C) is presented that achieves classification accuracy as high as that of traditional SVM (with positive and negative data).

Lecture notes in computer sciencePAC Learning from Positive Statistical Queries

177 Citations1998François Denis

This work defines a PAC learning model from positive and unlabeled examples, and defines a PAC learning model from positive and unlabeled statistical queries and shows that k-DNF and k-decision lists are learnable in both models.