Supervised learning of wrappers from structured data sources

Abstract

HTML Wrapping ist eine häufig gebrauchte Strategie fr den Zugriff und die Extraktion von Daten, die sich im World Wide Web befinden.<br /> HTML Wrapper lokalisieren die relevanten Daten in den Webseiten und transformie ren sie in Formate, die fr die weitere maschinelle Verarbeitung geeignet sind, wie zum Beispiel XML.<br />In den letzten Dekaden wurden verschiedene Methoden und Sprachen zur Generierung von HTML Wrappern vorgeschlagen und analysiert.<br /> Das reicht von hand-codierten Perl Programmen, Induktion von Stringautomaten und semi-automatischen visuellen Systemen mit speziell konstruierten Extraktion ssprachen bis hin zu Data-Mining Methoden wie Support Vektor Maschinen, Bayesianischen Sortiermaschinen und Markov Modellen.<br />In der vorliegenden Dissertation konzentrieren wir uns auf das interaktive Lernen von Wrapper Programmen.<br /> Diese Systeme erstellen Wrapper basierend auf der visuellen Interaktion mit einem menschlichen Designer.<br /> Der Wrapperdesigner interagiert direkt mit der dargestellten Webseite, insbesondere durch Markierung von positiven und negativen Beispielinstanzen.<br /> Diese Beispielinstanzen dienen als Basis fr die Generierung eines Wrappers.<br /> Die Semistruktur von Webseiten, die sich als DOM Baum darstellen lässt, erweist sich als sehr ntzliches Hilfsmittel fr die Datenextraktion.<br /> Deshalb interessieren wir uns inbesondere fr Methoden des Lernens von Baumstrukturen, wo wir auf bessere Ergebnisse im Bereich der Erlernbarkeit solcher Strukturen hoffen als in vergleichbaren Lerntheorien auf flachen Strings.<br />Der erste Teil der Dissertation beschäftigt sich mit den existierenden Modellen des aktiven Lernens, die auf die interaktive Wrapper Generierung anwendbar sind.<br /> Wir studieren die theoretischen Grenzen der aktiven Erlernbarkeit, wir untersuchen die existierenden Algorithmen und vergleichen die relevanten Lernenmodelle.<br />Der zweite Teil der Dissertation beschäftigt sich mit dem aktiven Lernen von HTML Wrappern.<br /> Wir wählen die Sprache XPath als Formalismus fr das Ausdrcken von HTML Wrappern und studieren die Erlernbarkeit von verschiedenen XPath Fragmenten.<br /> Danach präsentieren wir eine Methode fr Behandlung von HTML Attributen die auf dem Konzept der Entropie basiert.<br /> Diese Methode ermöglicht es, die vorgeschlagenen Algorithmen fr das Lernen von Baumstrukturen mittels Abfragen mit anderen Methoden aus Data-Mining und Semantic Web, wie zum Beispiel Ontologien, Entscheidungsbäume oder der Bayesianischen Klassifikation, besser zu kombinieren.<br />

HTML wrapping is a commonly adopted strategy for accessing and extracting data located on the Web.<br /> HTML wrappers locate relevant data in Web pages and transform them into formats suitable for further machine processing such as XML.<br />In the last decade various approaches to creating HTML wrappers have been researched.<br /> These range from hand-coded Perl programs, induction of string based automata and semi-automatic visual systems with specially designed wrapping languages to data mining approaches such as support vector machines, Bayesian classifiers and hidden Markov models.<br />In this thesis, we focus on the learning process of interactive wrapper generators.<br /> These are systems that create wrappers from visual interaction with a human wrapper designer.<br /> The wrapper designer interacts directly with the rendered Web page, marking positive and negative example instances.<br /> These example instances are then used to generate the wrapper.<br /> A tree-structured representation of Web pages (the DOM tree) has proved to be useful for HTML wrappers.<br /> We therefore are specifically interested in tree learning techniques, where we hope for better wrapper learnability results in comparison to flat string approaches.<br />The first part of this thesis is devoted to existing active learning models applicable to interactive wrapper generation.<br /> We study the theoretical bounds of active learnability, analyse existing algorithms and compare the existing learning models.<br />The second part of this thesis focuses on the active learning of HTML wrappers.<br /> We choose the XPath language as the formalism for expressing HTML wrappers and study the learnability of various XPath fragments.<br /> At the end, we present a method of dealing with HTML attributes.<br /> This method allows us to better combine the proposed algorithms for learning of tree shapes with other approaches from data mining and semantic Web research, for example ontologies, decision trees and Bayesian classification.