Combining link-based and content-based methods for web document classification

ABSTRACT

This paper studies how link information can be used to improve classification results for Web collections. We evaluate four different measures of subject similarity, derived from the Web link structure, and determine how accurate they are in predicting document categories. Using a Bayesian network model, we combine these measures with the results obtained by traditional content-based classifiers. Experiments on a Web directory show that best results are achieved when links from pages outside the directory are considered. Link information alone is able to obtain gains of up to 46 points in F1, when compared to a traditional content-based classifier. The combination with content-based methods can further improve the results, but too much noise may be introduced, since the text of Web pages is a much less reliable source of information. This work provides an important insight on which measures derived from links are more appropriate to compare Web documents and how these measures can be combined with content-based algorithms to improve the effectiveness of Web classification.

REFERENCES

• 1: R. Amsler. Application of citation-based automatic classification. Technical report, The University of Texas at Austin, Linguistics Research Center, Austin, TX, December 1972.
• 2: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 3: Pável Calado , Berthier Ribeiro-Neto , Nivio Ziviani , Edleno Moura , Ilmério Silva, Local versus global link information in the Web, ACM Transactions on Information Systems (TOIS), v.21 n.1, p.42-63, January 2003 [doi>10.1145/635484.635486]
• 4: 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
• 5: D. Cohn and T. Hofmann. The missing link - a probabilistic model of document content and hypertext connectivity. In T. K. Leen, T. G. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems 13, pages 430--436. MIT Press, 2001.
• 6: Jeffrey Dean , Monika R. Henzinger, Finding related pages in the World Wide Web, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1467-1479, May 17, 1999
• 7: M. Fisher and R. Everson. When are links useful? Experiments in text classification. In F. Sebastianini, editor, Proceedings of the 25th annual European conference on Information Retrieval Research, ECIR 2003, pages 41--56. Springer-Verlag, Berlin, Heidelberg, DE, 2003.
• 8: Johannes Fürnkranz, Exploiting Structural Information for Text Classification on the WWW, Proceedings of the Third International Symposium on Advances in Intelligent Data Analysis, p.487-498, August 01, 1997
• 9: Eric J. Glover , Kostas Tsioutsiouliklis , Steve Lawrence , David M. Pennock , Gary W. Flake, Using web structure for classifying and describing web pages, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511520]
• 10: Norbert Gövert , Mounia Lalmas , Norbert Fuhr, A probabilistic description-oriented approach for categorizing web documents, Proceedings of the eighth international conference on Information and knowledge management, p.475-482, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/319950.320053]
• 11: D. Hawking and N. Craswell. Overview of TREC-2001 Web track. In The Tenth Text REtrieval Conference (TREC-2001), pages 61--67, Gaithersburg, Maryland, USA, November 2001.
• 12: X. He, H. Zha, C. H. Q. Ding, and H. D. Simon. Web document clustering using hyperlink structures. Computational Statistics & Data Analysis, 41(1):19--45, November 2002.
• 13: 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
• 14: Thorsten Joachims , Nello Cristianini , John Shawe-Taylor, Composite Kernels for Hypertext Categorisation, Proceedings of the Eighteenth International Conference on Machine Learning, p.250-257, June 28-July 01, 2001
• 15: M. M. Kessler. Bibliographic coupling between scientific papers. American Documentation, 14(1):10--25, January 1963.
• 16: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 17: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , D. Sivakumar , Andrew Tompkins , Eli Upfal, The Web as a graph, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-10, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335170]
• 18: A. McCallum and K. Nigam. A comparison of event models for Naive Bayes text classification. In Proceedings of AAAI/ICML -98, Workshop on Learning for Text Categorization, pages 41--48. AAAI Press, 1998.
• 19: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 20: 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]
• 21: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 22: Berthier A. N. Ribeiro , Richard Muntz, A belief network model for IR, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.253-260, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243272]
• 23: B. Ribeiro-Neto, I. Silva, and R. Muntz. Soft Computing in Information Retrieval: Techniques and Applications, chapter 11---Bayesian Network Models for IR, pages 259--291. Springer Verlag, 1st edition, 2000.
• 24: Altigran S. da Silva , Eveline A. Veloso , Paulo B. Golghe , Berthier Ribeiro-Neto , Alberto H. F. Laender , Nivio Ziviani, CoBWeb A Crawler for the Brazilian Web, Proceedings of the String Processing and Information Retrieval Symposium & International Workshop on Groupware, p.184, September 21-24, 1999
• 25: Seán Slattery , Tom M. Mitchell, Discovering Test Set Regularities in Relational Domains, Proceedings of the Seventeenth International Conference on Machine Learning, p.895-902, June 29-July 02, 2000
• 26: H. G. Small. Co-citation in the scientific literature: A new measure of relationship between two documents. Journal of the American Society for Information Science, 24(4):265--269, July 1973.
• 27: Aixin Sun , Ee-Peng Lim , Wee-Keong Ng, Web classification using support vector machine, Proceedings of the 4th international workshop on Web information and data management, November 08-08, 2002, McLean, Virginia, USA [doi>10.1145/584931.584952]
• 28: Loren Terveen , Will Hill , Brian Amento, Constructing, organizing, and visualizing collections of topically related Web resources, ACM Transactions on Computer-Human Interaction (TOCHI), v.6 n.1, p.67-94, March 1999 [doi>10.1145/310641.310644]
• 29: Mike Thelwall , David Wilkinson, Finding similar academic web sites with links, bibliometric couplings and colinks, Information Processing and Management: an International Journal, v.40 n.3, p.515-526, January 2004 [doi>10.1016/S0306-4573(03)00042-6]
• 30: Howard Turtle , W. Bruce Croft, Evaluation of an inference network-based retrieval model, ACM Transactions on Information Systems (TOIS), v.9 n.3, p.187-222, July 1991 [doi>10.1145/125187.125188]
• 31: Yiming Yang, Expert network: effective and efficient learning from human decisions in text categorization and retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.13-22, July 03-06, 1994, Dublin, Ireland
• 32: Yiming Yang , Seán Slattery , Rayid Ghani, A Study of Approaches to Hypertext Categorization, Journal of Intelligent Information Systems, v.18 n.2-3, p.219-241, March-May 2002 [doi>10.1023/A:1013685612819]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

General Terms:
Algorithms, Experimentation

Keywords:
Bayesian networks, classification, link analysis, web