Übung 6 - Web Mining

Das unter /lehre/ss11/web-mining/keaddon6.zip herunterladbare Firefox-Plugin implementiert einen einfachen Wrapper. Im Lernmodus (KE-Symbol in der Statusleiste ist grün) erlaubt es, einen beliebigen, zu extrahierenden DOM-Knoten in einem Dokument auszuwählen. Wird ein Knoten mit CTRL-Klick angeklickt, wird der Funktion collect() in data/contextStudent.js der ausgewählte DOM-Knoten übergeben. Die Funktion speichert das markierte Beispiel in einem Array. Dies kann nun für beliebig viele Knoten wiederholt werden bis auf das KE-Symbol geklickt wird und das Programm in den Extraktionsmodus geht (rotes Symbol).

Hierbei wird für ein geöffnetes Dokument anhand der übergebenen Lernbeispiele die zu extrahierenden DOM-Knoten visuell hervorgehoben. Dies geschieht in der Funktion execute() in data/contextStudent.js. Bevor dies geschieht, wird in induce() in lib/model.js das tatsächliche Extraktionsmuster induziert. Im Falle dieses rudimentären Wrappers wird ein Knoten markiert, falls der Knotentyp (Tag) im Lernschritt markiert wurde. Wurde also z.B. ein Knoten vom Typ <strong> als Beispiel markiert, werden im Extraktionsmodus alle Knoten vom Typ <strong> markiert.

1. Erweitern Sie den Wrapper zu einem einfachen LR-Wrapper. Beschränken Sie sich dabei auf den Fall, daß nur ein Item-Typ auf ein Mal extrahiert werden soll und gehen Sie davon aus, daß eine Seite auch nur ein Item enthält.
   Wählen Sie dabei zwischen der Implementierung des klassischen LR-Wrappers, der auf HTML-Source-Code Ebene arbeitet, und der Implementierung eines LR-Wrapper, der auf dem DOM-Tree arbeitet. Entscheiden Sie sich für eine Variante. Weitere Anweisungen bei den Hinweisen. Legen Sie das Plugin als xpi Datei bei und erklären Sie die Funktionsweise.
   • HTML-LR-Wrapper: Dies ist der klassische LR-Wrapper und am einfachsten zu implementieren. Allerdings läßt er sich nicht so leicht in das Firefox/Javascript-Framework einbinden (dieses arbeitet auf DOM-Ebene) und ist auch in seinen Möglichkeiten beschränkter.
   • DOM-LR-Wrapper: Die Implementierung dieser Variante ist anspruchsvoller und nicht so straight-forward und möglicherweise mit mehr Aufwand verbunden, verfolgt jedoch einen moderneren und erfolgsversprechenderen Ansatz. Diese Variante bietet einen tieferen Einblick in die Wrapper-Modellierung und die Möglichkeit zur Entfaltung von eigenen Ideen. Die Programmierung wird durch das benutzte Framework erleichtern. Die Bearbeitung dieser Variante wird belohnt.
2. Wen­den sie Ihr LR-Sys­tem an einen ein­fachen Fall an. Dafür bi­eten sich etwa die Mi­tar­beit­er­seit­en eines Fachge­bi­et des FB In­for­matik wie die der Ar­beits­gruppe Prof. Gurevych (http://www.ukp.tu-darmstadt.de/people/) an. Extrahieren Sie Name und Tele­fon­num­mer aus den Seit­en der elf ak­tuellen Doktoranden, indem Sie auf zwei Mitarbeiterseit­en im ersten Durchlauf den Namen markieren und sich auf den restlichen Seiten das Ergebnis der Extraktion anschauen. Im zweiten Durchlauf verfahren sie analog dazu mit den Telefonnummern.
   Hat das Ver­fahren funk­tion­iert? Zeigen Sie repräsentativ das Ergebnis der Extraktion an zwei oder drei der Seiten, auch an möglichen Fehlextraktionen. Geben Sie Recall und Precision an. Geben Sie auch die induzierten Delimiter an (Im Falle des DOM-Wrappers wählen Sie hierfür eine geeignete Darstellung, die die Funktionsweise verdeutlicht).
3. Probieren Sie aus, was passiert, wenn man nur ein Beispiel vorgibt und was, wenn man mehr als zwei vorgibt.
4. Suchen Sie zwei weit­ere Fam­i­lien von Seit­en aus dem Netz, von denen Sie glauben, dass das Ver­fahren funktioniert. Extrahieren Sie Daten Ihrer Wahl. Verfahren Sie dabei analog zu Aufgabe 2 und extrahieren Sie in verschiedene Itemtypen (mindestens 2) in separaten Durchläufen. Bericht­en Sie Ihre Er­fahrun­gen und Ergeb­nisse.

Hinweise und weitere Anweisungen

• HTML-LR-Wrapper:
  • collect: Ihr Programm sollte in collect für einen markierten Knoten c den linken und den rechten Delimiter herausfinden und speichern. Die Funktion erhält dabei als Parameter das aktuelle DOM-Element. Wie man den HTML-Code eines DOM-Elements und des gesamten Dokuments erhält, ist im Programm kommentiert. Entscheiden Sie selbst, ob sie das gesamte DOM-Element als markiert ansehen (also auch als zu extrahieren) oder nur den reinen Text, der darin enthalten ist. Letztere Variante entspricht dem klassischen LR-Wrapper und sollte bessere Resultate liefern, da hierbei mehr delimitierende Zeichenkette zur Verfügung steht. Beachten Sie, das von dieser Entscheidung sowohl das Verfahren zur Bestimmung der Delimiter in collect als auch das Verfahren zur anschliessenden Extraktion in execute abhängt.
  • induce: Induzieren Sie in induce() den passenden L- und R-Delimiter für alle markierten Beispiele c_i. Wie aus den Vorlesungsfolien bekannt, ist L der längste gemeinsame Suffix aller L_c_i und R der längste gemeinsame Präfix aller R_c_i. Die induzierten Wrapper werden in der Funktion execute angewandt und die gematchten Knoten markiert. Alternativ können Sie L und R natürlich auch in collect inkrementell induzieren. induce wird aufgerufen sobald auf das KE-Logo geklickt wird.
  • execute: Suchen Sie im übergebenen Dokument nach den L und R Mustern und identifizieren Sie den darin eingeschlossenen Text. Heben Sie den gefundenen Text hervor z.B. durch Umrahmung des enthaltenden DOM-Nodes (ggf. mehrere Nodes) bzw. durch Einfügen von klar sichtbaren Start- und Ende-Markierungen (z.B. farbige eckige Klammern). Code-Beispiele sind vorhanden.
• DOM-LR-Wrapper: Die Delimiter werden in diesem Fall nicht als Liste von Zeichen dargestellt, sondern als Pfad von DOM-Nodes bzw. sogar als Baum von Knoten. Im Gegensatz zum einfachen Zeichen-Matchen enstehen hierbei viele neue interessante Möglichkeiten.
  • So kann z.B. die Darstellung bzw. der Vergleich der Suffixe/Präfixe so gewählt werden, daß die Reihenfolge der Attribute in den Tags keine Rolle mehr spielt, oder abweichende Attribute trotzdem als Match gewertet werden. So könnten z.B. die L-Delimiter <strong class=heavy color=black> und <strong color=black class=heavy> zusammengefügt werden, die bei einem reinen HTML-LR-Wrapper keinen gemeinsamen Suffix hätten. Denkbar wäre auch, eine strikte Übereinstimmung der Attribute aufzugeben und stattdessen eine Art Schnittmenge zu bilden, so daß z.B. auch <strong id=100> und <strong id=120> zusammengefügt werden könnten.
  • Es ist andererseits auch auf eine korrekte Traversierung des DOM-Trees zu achten. So besteht eine Delimiter nicht nur aus den Vorgänger-Knoten (previousSibling), sondern auch aus den Elternknoten (parentNode). Sie müssen sich demnach auch entscheiden, wie sie Vorgänger und Elternknoten ordnen, bzw. ob Sie hierfür zwei getrennte Listen führen.
  • Implementieren Sie ihren Wrapper wie für den HTML-LR-Wrapper in den Methoden collect, induce und execute.

• Für den HTML-LR-Wrapper kann es bei HTML-Doku­menten hil­fre­ich sein, in einem Pre­pro­cess­ing-Schritt den Code zu kanon­isieren, indem man z.B. aufeinanderfolgende Leerzeichen oder Leerzeichen zwis­chen zwei Tags löscht, oder auch auf Beachtung von Klein- und Großschreibung verzichtet. Die Funktionsweise von DOM-LR kann als eine weiterführende Kanonisierung angesehen werden.
• in­duce sam­melt die Präfixe von c_i in den markierten Beispiel­d­oku­menten und wählt ihren läng­sten gemein­samen Suf­fix als L aus (entsprechen­des für R). Es zeigt sich, daß sehr lange De­lim­iter un­zu­verlässig sind. Eine ein­fache Heuris­tik, um die Ko­r­rek­theit der Ex­trak­tion zu erhöhen, ist die De­lim­iter-Länge auf z.B. 20 zu beschränken.
• Wenn (im Fall L) der gewählte Suf­fix nicht prop­er ist, siehe Folien, be­deutet dies, dass er sich auf den Beispiel­d­oku­menten nicht als De­lim­iter eignet, da er zu früh extrahiert. Zum Lösen der Auf­gabe kann man diese Überprüfung auch weglassen. Zum Einen ist es zu­min­d­est bei längeren De­lim­itern un­wahrschein­lich, dass sie nicht prop­er sind, zum An­deren nimmt die Überprüfung nur vor­weg, dass das Ver­fahren bei den gegebe­nen Daten nicht funktion­iert.

• Für dieses Plugin hat sich die benötigte SDK Version geändert. Bitte verwenden Sie Version 1.0b5 der Addon SDK.
• Sie können den Source-Code direkt im Extensions-Verzeichnis von Firefox bearbeiten. Ab Firefox 4.0 werden die Änderungen direkt übernommen.
• Die Fehlerkonsole (in Menü->Extras oder CTRL-SHIFT-J) und insbesondere die Web-Konsole (in Menü->Extras oder CTRL-SHIFT-K) sind sehr nützliche Tools zum Debuggen und direktem Ausprobieren von JavaScript-Code.