AutoFeed: an unsupervised learning system for generating webfeeds

ABSTRACT

Our goal is to automatically extract data from semi-structured webn sites. Previously, researchers have developed two types of supervised learning approaches for extracting web data: methods that create precise, site-specific extraction rules and methods that learn less-precise site-independent extraction rules. In either case, significant training is required. In this paper, we describe a third, more ambitious approach, where we use unsupervised learning to analyze sites and discover their structure. Our method relies on a set of heterogeneous "experts", each of which is capable of identifying certain types of generic structure. Each expert represents its discoveries as "hints". Based on these hints, our system clusters the pages and identifies semi-structured data that can be extracted. To identify a good clustering, we use a probabilistic model of the hint-generation process. The paper describes our formulation of the fully-automatic web-extraction problem, our clustering approach, and our results on a set of experiments.

REFERENCES

• 1: Arvind Arasu , Hector Garcia-Molina , Stanford University, Extracting structured data from Web pages, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872799]
• 2: James Caverlee , Ling Liu , David Buttler, Probe, Cluster, and Discover: Focused Extraction of QA-Pagelets from the Deep Web, Proceedings of the 20th International Conference on Data Engineering, p.103, March 30-April 02, 2004
• 3: William W. Cohen , Matthew Hurst , Lee S. Jensen, A flexible learning system for wrapping tables and lists in HTML documents, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511477]
• 4: William W. Cohen , Yoram Singer, A simple, fast, and effective rule learner, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.335-342, July 18-22, 1999, Orlando, Florida, United States
• 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: Valter Crescenzi , Giansalvatore Mecca , Paolo Merialdo, RoadRunner: Towards Automatic Data Extraction from Large Web Sites, Proceedings of the 27th International Conference on Very Large Data Bases, p.109-118, September 11-14, 2001
• 7: Valter Crescenzi , Paolo Merialdo , Paolo Missier, Fine-grain web site structure discovery, Proceedings of the 5th ACM international workshop on Web information and data management, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956699.956703]
• 8: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 9: David W. Embley , Cui Tao , Stephen W. Liddle, Automatically Extracting Ontologically Specified Data from HTML Tables of Unknown Structure, Proceedings of the 21st International Conference on Conceptual Modeling, p.322-337, October 07-11, 2002
• 10: Lise Getoor , Nir Friedman , Daphne Koller , Benjamin Taskar, Learning Probabilistic Models of Relational Structure, Proceedings of the Eighteenth International Conference on Machine Learning, p.170-177, June 28-July 01, 2001
• 11: Craig A. Knoblock , Kristina Lerman , Steven Minton , Ion Muslea, Accurately and reliably extracting data from the Web: a machine learning approach, Intelligent exploration of the web, Physica-Verlag GmbH, Heidelberg, Germany, 2003
• 12: Nicholas Kushmerick, Wrapper induction: efficiency and expressiveness, Artificial Intelligence, v.118 n.1-2, p.15-68, April 2000 [doi>10.1016/S0004-3702(99)00100-9 ]
• 13: Kristina Lerman , Lise Getoor , Steven Minton , Craig Knoblock, Using the structure of Web sites for automatic segmentation of tables, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007584]
• 14: K. Lerman, S. Minton, and C. A. Knoblock. Wrapper maintenance: A machine learning approach. JAIR, 18:149--181, 2003.
• 15: S. Minton, S. I. Ticrea, and J. Beach. Trainability: Developing a responsive learning system. In IIWeb, pages 27--32, 2003.
• 16: D. C. Reis , P. B. Golgher , A. S. Silva , A. F. Laender, Automatic web news extraction using tree edit distance, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988740]
• 17: Noam M. Shazeer , Michael L. Littman , Greg A. Keim, Solving crossword puzzles as probabilistic constraint satisfaction, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.156-162, July 18-22, 1999, Orlando, Florida, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms

Keywords:
heterogeneous experts, unsupervised wrapper induction, web site modelling