Übung 2 - Web Mining
- 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 - Französisch) einer Web-Seite zu ermitteln. Hierfür müssen
sie wieder die Funktion
student(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/ss11/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.
- Gehen Sie auf /lehre/ss11/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 Sie für jeden Text das Ergebnis zeilenweise in
eine Datei namens
challenge.txt
im Format "Seitennummer Sprache\n". - 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 eine kurze Pause machen lassen.
Beim Abarbeiten der Link-Queue sollte er die
- Breadth-First-Strategie (neue Links werden hinten in der Queue einsortiert)
- Depth-First Strategie (neue Links werden vorne in der Queue einsortiert)
- Vergleichen Sie die Anzahl der URLs einer Seite mit der Anzahl derjenigen, die davon neu sind, d.h. nicht schon mal gefunden wurden. Entscheiden sie selbst wie sie diesen Vegleich erstellen (z.B. anhand eines Streudiagramm mit einen Punkt pro Seite oder doppelten Balkendiagramms mit einer geeigneten x-Achse, etc.).
- 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, ...)
- Ermitteln Sie die Anzahl der unterschiedlichen Host-Namen, die Sie antreffen.
- 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 jeweils für beide Suchstrategien.
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.
Hilfreiche Module:
Zweck | Perl | Python |
---|---|---|
Laden einer Web-Seite | LWP::Simple | urllib |
Extrahieren von Hyperlinks | HTML::LinkExtor | SGMLParser (Beispiel), htmldata |
Queueing | collections.deque | |
Kanonisierung von URLs | URI | urlparser |
Queries an Suchmaschinen | WWW::Search::AltaVista etc. | web_search |