PEBL: positive example based learning for Web page classification using SVM

ABSTRACT

Web page classification is one of the essential techniques for Web mining. Specifically, classifying Web pages of a user-interesting class is the first step of mining interesting information from the Web. However, constructing a classifier for an interesting class requires laborious pre-processing such as collecting positive and negative training examples. For instance, in order to construct a "homepage" classifier, one needs to collect a sample of homepages (positive examples) and a sample of non-homepages (negative examples). In particular, collecting negative training examples requires arduous work and special caution to avoid biasing them. We introduce in this paper the Positive Example Based Learning (PEBL) framework for Web page classification which eliminates the need for manually collecting negative training examples in pre-processing. We present an algorithm called Mapping-Convergence (M-C) that achieves classification accuracy (with positive and unlabeled data) as high as that of traditional SVM (with positive and negative data). Our experiments show that when the M-C algorithm uses the same amount of positive examples as that of traditional SVM, the M-C algorithm performs as well as traditional SVM.

REFERENCES

• 1: Erin L. Allwein , Robert E. Schapire , Yoram Singer, Reducing multiclass to binary: a unifying approach for margin classifiers, The Journal of Machine Learning Research, 1, p.113-141, 9/1/2001
• 2: H. Chen, C. Schuffels, and R. Orwig. Interuet categorization and search: a machine learning approach. Journal of Visual Communications and Image Representation, 7(1):88--102, 1996.
• 3: Corinna Cortes , Vladimir Vapnik, Support-Vector Networks, Machine Learning, v.20 n.3, p.273-297, Sept. 1995 [doi>10.1023/A:1022627411411]
• 4: Mark Craven , Dan DiPasquo , Dayne Freitag , Andrew McCallum , Tom Mitchell , Kamal Nigam , Seán Slattery, Learning to extract symbolic knowledge from the World Wide Web, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.509-516, July 1998, Madison, Wisconsin, United States
• 5: Francesco De Comité , François Denis , Rémi Gilleron , Fabien Letouzey, Positive and Unlabeled Examples Help Learning, Proceedings of the 10th International Conference on Algorithmic Learning Theory, p.219-230, December 06-08, 1999
• 6: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society, Series B, 39:1--38, 1977.
• 7: François Denis, PAC Learning from Positive Statistical Queries, Proceedings of the 9th International Conference on Algorithmic Learning Theory, p.112-126, October 08-10, 1998
• 8: Susan Dumais , Hao Chen, Hierarchical classification of Web content, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.256-263, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345593]
• 9: Eric J. Glover , Gary W. Flake , Steve Lawrence , Andries Kruger , David M. Pennock , William P. Birmingham , C. Lee Giles, Improving Category Specific Web Search by Learning Query Modifications, Proceedings of the 2001 Symposium on Applications and the Internet (SAINT 2001), p.23, January 08-12, 2001
• 10: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998
• 11: Thorsten Joachims, Transductive Inference for Text Classification using Support Vector Machines, Proceedings of the Sixteenth International Conference on Machine Learning, p.200-209, June 27-30, 1999
• 12: A. Kruger , C. L. Giles , F. M. Coetzee , E. Glover , G. W. Flake , S. Lawrence , C. Omlin, DEADLINER: building a new niche search engine, Proceedings of the ninth international conference on Information and knowledge management, p.272-281, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354829]
• 13: Fabien Letouzey , François Denis , Rémi Gilleron, Learning from Positive and Unlabeled Examples, Proceedings of the 11th International Conference on Algorithmic Learning Theory, p.71-85, December 11-13, 2000
• 14: Larry M. Manevitz , Malik Yousef, One-class svms for document classification, The Journal of Machine Learning Research, 2, 3/1/2002
• 15: H. Mase. Experiments on automatic web page categorization for ir system. Technical report, Stanford University, http://citeseer.nj.nec.com/164846.html, 1998.
• 16: Eddy Mayoraz, Multiclass Classification with Pairwise Coupled Neural Networks or Support Vector Machines, Proceedings of the International Conference on Artificial Neural Networks, p.314-321, August 21-25, 2001
• 17: Kamal Nigam , Andrew Kachites McCallum , Sebastian Thrun , Tom Mitchell, Text Classification from Labeled and Unlabeled Documents using EM, Machine Learning, v.39 n.2-3, p.103-134, May-June 2000 [doi>10.1023/A:1007692713085]
• 18: Hyo-Jung Oh , Sung Hyon Myaeng , Mann-Ho Lee, A practical hypertext catergorization method using links and incrementally available class information, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.264-271, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345594]
• 19: David M. J. Tax , Robert P. W. Duin, Uniform object generation for optimizing one-class classifiers, The Journal of Machine Learning Research, 2, 3/1/2002
• 20: W.-C. Wong and A. W.-C. Fu. Finding structure and characteristics of web documents for classification. In ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 2000.
• 21: Yiming Yang , Xin Liu, A re-examination of text categorization methods, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.42-49, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312647]
• 22: Jeonghee Yi , Neel Sundaresan, A classifier for semi-structured documents, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.340-344, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347164]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.m MISCELLANEOUS

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Mapping-Convergence (M-C) algorithm, SVM (Support Vector Machine), labeled data, unlabeled data