A practical hypertext catergorization method using links and incrementally available class information

ABSTRACT

As WWW grows at an increasing speed, a classifier targeted at hypertext has become in high demand. While document categorization is quite a mature, the issue of utilizing hypertext structure and hyperlinks has been relatively unexplored. In this paper, we propose a practical method for enhancing both the speed and the quality of hypertext categorization using hyperlinks. In comparison against a recently proposed technique that appears to be the only one of the kind, we obtained up to 18.5% of improvement in effectiveness while reducing the processing time dramatically. We attempt to explain through experiments what factors contribute to the improvement.

REFERENCES

• 1: Chidanand Apté , Fred Damerau , Sholom M. Weiss, Towards language independent automated learning of text categorization models, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.23-30, July 03-06, 1994, Dublin, Ireland
• 2: Krishna Bharat , Monika R. Henzinger, Improved algorithms for topic distillation in a hyperlinked environment, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.104-111, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290972]
• 3: Soumen Chakrabarti , Byron Dom , Piotr Indyk, Enhanced hypertext categorization using hyperlinks, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.307-318, June 01-04, 1998, Seattle, Washington, United States
• 4: Soumen Chakrabarti , Byron E. Dom , S. Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins , David Gibson , Jon Kleinberg, Mining the Web's Link Structure, Computer, v.32 n.8, p.60-67, August 1999 [doi>10.1109/2.781636]
• 5: 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
• 6: W. Bruce Croft , Howard R. Turtle, Retrieval strategies for hypertext, Information Processing and Management: an International Journal, v.29 n.3, p.313-324, May–June, 1993 [doi>10.1016/0306-4573(93)90058-L]
• 7: P. J. Hayes , P. M. Andersen , I. B. Nirenburg , L. M. Schmandt, TCS: a shell for content-based text categorization, Proceedings of the sixth conference on Artificial intelligence applications, p.320-326, January 1990, Santa Barbara, California, United States
• 8: Marti A. Hearst, Support Vector Machines, IEEE Intelligent Systems, v.13 n.4, p.18-28, July 1998 [doi>10.1109/5254.708428]
• 9: Won-Kyun Joo 7 Sung-Hyon Myaeng, "Improving Retrieval Effectivness with Link Information", Proc. of the international Workshop on IRAL '98, 1998.
• 10: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 11: Jeong-Mook Lim, Hyo-Jung Oh, Sung-Hyon Myaeng, and Mann-Ho Lee, "Improving Efficiency with Document Category Information in Link-based Retrieval", Proc. of the international Workshop on IRAL "99, 1999.
• 12: David D. Lewis and Marc Ringuette, " A Comparison of Two Learning Algorithms for Text Categorization", Proc. of the ya Annual Symposium on Document Analysis and Information Retreival, 1994.
• 13: Andrew McCallum and Kamal Nigram, "A Comparison of Event Models for Naive Bayes Text Classification", AAA1 '98 Workshop on Learning for Text Categorization, 1998.
• 14: Jacques Savoy, An extended vector-processing scheme for searching information in hypertext systems, Information Processing and Management: an International Journal, v.32 n.2, p.155-170, March 1996 [doi>10.1016/S0306-4573(96)85003-5]
• 15: 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]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Text processing
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation
          Subjects: Hypertext/hypermedia

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
text categorization