Übung 2 - Web Mining
Das KE-Plugin wurde aktualisiert, so daß das darin enthaltene .xpi nun auch unter dem atkuellen Firefox 29.0.1 funktioniert. Bitte auch den entsprechenden Forumseintrag dazu beachten.
- (3 Punkte) Entwickeln Sie auf der Basis der in Übungsblatt 1, Aufgabe 4 herausgefundenen Statistiken über Sprachen ein einfaches Verfahren, mit dem es möglich ist, die Sprache eines Textes anhand der Häufigkeiten von Buchstaben und Buchstabenpaaren vorherzusagen.
Erweitern Sie unser kleines KE-Firefox-Plugin aus Aufgabe 5 dahingehend, daß es mithilfe Ihres Verfahrens in der Lage ist, die Sprache (Deutsch - Englisch - Spanisch) einer Web-Seite zu ermitteln. Hierfür müssen sie wieder die Funktionstudent(text)
in der Dateilib/student.js
in Ihrem Sinne erweitern. Beachten Sie dabei die zusätzlichen nützlichen Funktionen inlib/utility.js
in der aktualisierten Version des Plugins (/lehre/ss14/web-mining/keaddon2.zip). Das Plugin soll dabei nicht fähig sein, zu lernen. Sie sollen Ihr Sprachenmodell sozusagen in die Funktion hardcoden.- Erklären Sie kurz ihr Verfahren z.B. auch mittels Pseudocode. Denken Sie daran, Ihrer Abgabe ein funktionsfähiges Plugin (.xpi-Datei) beizufügen.
- Gehen Sie auf /lehre/ss14/web-mining/u2languagechallenge.html und ermitteln Sie die Sprache der 10 dort erhältlichen Webseiten. Die ersten Fünf erhalten nur eine Liste von Buchstaben, die letzten 5 Buchstabenpaare. Schreiben für jeden Text das Ergebnis zeilenweise in eine Datei namens
challenge.txt
im Format "Seitennummer Sprache\n". Bedenken Sie für die ersten 5 Seiten, daß Ihr Verfahren auch funktionieren soll, falls nur Buchstaben und keine Buchstabenpaare vorliegen.
- Erklären Sie kurz ihr Verfahren z.B. auch mittels Pseudocode. Denken Sie daran, Ihrer Abgabe ein funktionsfähiges Plugin (.xpi-Datei) beizufügen.
- (5 Punkte) Schreiben Sie einen einfachen Crawler. Die in der Vorlesung behandelten Verfahren zur Optimierung brauchen Sie dabei nicht zu berücksichtigen. Der Crawler sollte
- keine URLs doppelt besuchen, d.h. Sie sollten URLs kanonisieren,
- die Server nicht zu sehr in Anspruch nehmen, z.B. könnten Sie den Bot nach jedem Request auf dem gleichen Host eine kurze Pause machen lassen,
- eine randomisierte Breadth-First-Strategie verfolgen, d.h. neue Links werden hinten in die Queue einsortiert, aber der nächste anzusteuernde Link wird zufällig gewählt,
- Zähler führen, die die Aufstellung folgender Statistiken erlauben:
- Erstellen Sie ein Histogramm über die Anzahl der URLs pro Seite (wie beim ersten Übungsblatt mit den Worthäufigkeiten, auch logarithmisch).
- Erstellen Sie ein Histogramm mit den Häufigkeiten des Auftretens von Hyperlinks (d.h., wie viele Links treten 1-mal auf, wie viele 2-mal, ...).
- Überlegen Sie sich ein einfaches Verfahren, um Duplikate festzustellen, und beschreiben Sie es. Das Verfahren sollte dabei z.B. Datenbank-generierte Seiten, bei der sich nur kurze Passagen wie Zeitangaben, Navigationsleisten, Werbeeinblendungen unterscheiden, als Duplikate erkennen. Wenden Sie ihr Verfahren nachträglich auf die heruntergeladenen Seiten an und ermitteln Sie die Anzahl der gefundenen Duplikate. Verifizieren Sie Ihr Verfahren stichprobenartig und zeigen Sie ein repräsentatives Beispiel auf.
- Verwenden Sie Ihr Verfahren aus der ersten Aufgabe, um die Sprache der heruntergeladenen Seiten zu ermitteln. Geben Sie die Verteilung über die gefundenen Sprachen an.
- Schreiben Sie auch eine kurze Zusammenfassung über Ihre Erfahrungen bzw. etwaige Probleme mit dieser Aufgabe.
Starten Sie den Crawler an einer Seite Ihrer Wahl, lassen Sie ihn eine Weile (zumindest 1000 Seiten) laufen und erstellen Sie die genannten Statistiken.
3. (2 Punkte) Wenden Sie Ihren Crawler ein weiteres Mal an, diesmal von einer Seite innerhalb der TU Darmstadt startend und springen Sie auch nur auf Links innerhalb der TU (*.tu-darmstadt.de). Lassen Sie sich wieder die Histogramme wie in Teilaufgabe 2.1 und 2.2 ausgeben und vergleichen Sie mit diesen.
Bedenken Sie, daß ein Crawl eine beträchliche Zeit in Anspruch nehmen kann, die Sie auch nicht direkt beeinflussen können. Es ist auch nicht ungewöhnlich, daß Sie z.B. aufgrund von Problemen und Fehlerbereinigungen mehrere Anläufe benötigen. Starten Sie deshalb Ihren ersten Crawl rechtzeitig.
Hinweise
- Beispiele für Duplikate aufgrund von Datenbank-generierter Seiten sind z.B. /lehre/arbeiten vs. /resources/eurlex/lehre/arbeiten und Aufrufe von /bibtex/topics/single/31 oder auch /bibtex/topics zu unterschiedlichen Zeitpunkten (unterschiedliche processing time). /bibtex/topics/single/173 und /bibtex/authors/show/3259 sind allerdings keine Duplikate mehr. Bedenken Sie bei Ihrem Verfahren auch, daß Sie im schlimmsten Fall mit allen bereits gecrawlten Seiten vergleichen müssen.
Hilfreiche Module:
Zweck | Python | |
---|---|---|
Laden einer Web-Seite | LWP::Simple | urllib |
Extrahieren von Hyperlinks |
HTML::LinkExtor |
SGMLParser (Beispiel), htmldata |
Queueing | collections.deque | |
Kanonisierung von URLs | URI | urlparser |
Die meisten der genannten Perl-Module sind im Modul Bundle::LWP enthalten.