Web unit mining: finding and classifying subgraphs of web pages

ABSTRACT

In web classification, most researchers assume that the objects to classify are individual web pages from one or more web sites. In practice, the assumption is too restrictive since a web page itself may not always correspond to a concept instance of some semantic concept (or category) given to the classification task. In this paper, we want to relax this assumption and allow a concept instance to be represented by a subgraph of web pages or a set of web pages. We identify several new issues to be addressed when the assumption is removed, and formulate the web unit mining problem. We also propose an iterative web unit mining (iWUM) method that first finds subgraphs of web pages using some knowledge about web site structure. From these web subgraphs, web units are constructed and classified into semantic concepts (or categories) in an iterative manner. Our experiments using the WebKB dataset showed that iWUM improves the overall classification performance and works very well on the more structured parts of a web site.

REFERENCES

• 1: Brian Amento , Loren Terveen , Will Hill, Does “authority” mean quality? predicting expert quality ratings of Web documents, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.296-303, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345603]
• 2: Andrei Z. Broder , Robert Krauthgamer , Michael Mitzenmacher, Improved classification via connectivity information, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.576-585, January 09-11, 2000, San Francisco, California, United States
• 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: Nick Craswell , David Hawking , Stephen Robertson, Effective site finding using link anchor information, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.250-257, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383999]
• 5: Mark Craven , Seán Slattery, Relational Learning with Statistical Predicate Invention: Better Models for Hypertext, Machine Learning, v.43 n.1-2, p.97-119, April-May 2001 [doi>10.1023/A:1007676901476]
• 6: 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]
• 7: Martin Ester , Hans-Peter Kriegel , Matthias Schubert, Web site mining: a new way to spot competitors, customers and suppliers in the world wide web, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775084]
• 8: L. Getoor, E. Segal, B. Taskar, and D. Koller. Probabilistic models of text and link structure for hypertext classification. In Proc. of Intl Joint Conf. on Artificial Intelligence Workshop on Text Learning: Beyond Supervision, Seattle, WA, 2001.
• 9: D. Hawking and N. Craswell. Overview of the TREC-2001 web track. In Proc. of TREC, Maryland, 2001. http://trec.nist.gov/.
• 10: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 11: 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
• 12: Wessel Kraaij , Thijs Westerveld , Djoerd Hiemstra, The Importance of Prior Probabilities for Entry Page Search, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564383]
• 13: D. Mladenic. Turning Yahoo to automatic web-page classifier. In Proc. of 13th European Conf. on Artificial Intelligence, pages 473--474, Brighton, UK, 1998.
• 14: J. M. Pierre. On the automated classification of web sites. Linköping Electronic Articles in Computer and Info. Science, 6, 2001.
• 15: Fabrizio Sebastiani, Machine learning in automated text categorization, ACM Computing Surveys (CSUR), v.34 n.1, p.1-47, March 2002 [doi>10.1145/505282.505283]
• 16: 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]
• 17: Grace Wahba, Support vector machines, reproducing kernel Hilbert spaces, and randomized GACV, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 18: T. Westerveld, D. Hiemstra, and W. Kraaij. Retrieving web pages using content, links, urls and anchors. In Proc. of TREC, Maryland, 2001. http://trec.nist.gov/.
• 19: Yiming Yang, A study of thresholding strategies for text categorization, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.137-145, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383975]
• 20: 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.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.7 Digital Libraries
          Subjects: Collection

General Terms:
Algorithms, Experimentation

Keywords:
web classification, web unit, web unit mining