Übung 3 - Web Mining

Binäre Klassifikation von Internet-Seiten

Abgabe: bis Sonntag, den 3.6.2012

1. Daten besorgen, Klassen definieren (1 P)

Besorgen Se sich eine Sammlung aus Internet-Seiten, die jeweils einer von zwei Klassen zugeordnet sind. Z.B. können Sie den course vs. non-course -Datensatz von WebKB herunterladen und davon die Dateien aus dem Ordner fulltext verwenden. Aber Sie können auch andere Datensätze suchen oder selbst einen erstellen, indem Sie Seiten sammeln und diese binär klassifizieren.

Teilen Sie den Datensatz randomisiert in Trainings- und Testmenge im Verhältnis 1:1 auf. Wenn Sie wenig Daten haben, können Sie das Verhältnis auch zugunsten der Trainingsmenge verschieben. Für das Training sollten Sie wenigstens auf 160 und für das Testen auf wenigstens 80 Seiten zurückgreifen können.

Beschreiben Sie kurz Ihr Vorgehen.

2. Aufbereitung der Daten (2 P)

Für Aufgabe 3 ist es notwendig, verschiedene Datensätze zu produzieren. Die meisten der dafür notwendigen Verarbeitungsschritte haben Sie bereits in vorherigen Übungen kennengelernt und angewandt. Sie sollten dabei in der Lage sein, die folgenden Schritte durchzuführen.

Dokument zu Wort-Liste
Extrahieren Sie den Inhalt der HTML-Seiten und zerlegen Sie diesen Text in eine Liste von Wörtern. Was Wort hier bedeutet, legen Sie wieder selbst fest. Geben Sie dies kurz an, d.h. erklären Sie, was aus dem Originaldokument erhalten bleibt und was wie reduziert wird.
Stoppwort-Filterung und Stemming
Ihr Programm sollte in der Lage sein, zusätzlich Stoppwort-Filterung und Stemming durchzuführen. Beachten Sie zu Stemming die Hinweise am Ende.
Wort-Liste zu TF-IDF-Vektor
Wählen Sie als Menge der Terme alle Wörter, die in den Wort-Listen des Trainingssets auftauchen. Bilden Sie für jedes Dokument den TF-IDF-Vektor, indem Sie für jeden Term seine relative Häufigkeit innerhalb des Dokuments (TF) mit seiner logarithmierten inversen Document Frequency (IDF) multiplizieren (siehe Folien).
Hinweis: Sowohl die Definition der Termmenge als auch die IDF-Werte werden allein anhand des Trainingssets erstellt und beim Testen wiederverwendet. Denn abgesehen von der konkreten Testinstanz sollen keine Informationen aus dem Testset in die Klassifikation einfließen.
Einfache Feature-Selection
Ihr Programm sollte in der Lage sein, die relevantesten N Wörter (Features) zu selektieren. Sortieren sie dabei einfach die Wörter nach ihrer Dokumenthäufigkeit und behalten sie die N häufigsten.
Sparse-Repräsentation
Überführen sie die Feature-Vektoren in eine Sparse-Repräsentation. Das Programm sollte diese zusammen mit den Klasseninformationen im SVMlight/libsvm-Format abspeichern können (siehe weiter unten).

Wählen Sie ein geeignetes Trainingsdokument aus und geben Sie repräsentativ für dieses das Ergebnis der einzelnen Transformations-Schritte an.

3. Training und Evaluation (7 P)

Zur automatischen Klassifikation von Internet-Seiten soll nun eine Support Vector Machine (SVM) trainiert werden. Verwenden Sie hierfür nach Belieben entweder das SVMlight- oder das libsvm-Framework. Als Performanz-Maß soll hier stets Accuracy verwendet werden.

Machen Sie sich mit dem Framework und der von Ihnen gewählten Schnittstelle vertraut, indem Sie eine Klassifikations-SVM (classification svm bzw. C-SVC) mit linearem Kernel (Parameter -t 0) mit den in Aufgabe 2 vorbereiteten Daten trainieren und evaluieren (kein Stoppwort-Filtering, kein Stemming). Verwenden Sie dabei nur die häufigsten z.B. 1000 Wörter für das Trainieren und Testen.
Geben Sie die erlangte Accuracy und die benötigte Trainings- und Testzeit an. Vergleichen Sie die Accuracy mit der eines Klassifizierers, der immer die häufigste Klassen in den Trainingsdaten vorhersagt (Baseline).
Fügen Sie wenigstens für diese Teilaufgabe auch die verwendeten Trainings- und Testdateien im Sparse-Format Ihrer Abgabe bei.
Zeigen Sie nun die Performanz der SVM in Abhängigkeit der Anzahl der benutzten Features. Variieren Sie die Anzahl der relevantesten Features N und zeichnen Sie die erhaltenen Accuracy-Werte in einem Linien-Diagramm in Abhängigkeit von N. Wählen Sie dabei anfangs z.B. für N einen Wert von 5 und erhöhen Sie diesen beim nächsten Schritt auf das Doppelte (also um 100%) bis Sie an die Gesamtanzahl der Features stoßen. Fügen Sie dabei zusätzliche Evaluierungen ein für Bereiche mit einer hohen Steigung oder mit möglichen Wendepunkten, d.h. Punkte an denen die Accuracy plötzlich abfällt oder ansteigt. Zeichnen Sie in das gleiche oder in ein zusätzliches Diagramm die entsprechenden Trainings-Laufzeiten. Interpretieren Sie die erhaltenen Leistungskurven.
Hinweis: Die Laufzeitmessung beider Programme ist nicht sehr präzise, weshalb es sich empfiehlt, hierfür externe Programme wie time für Linux oder Ahnliches für Windows zu verwenden.
Führen Sie nun die gleichen Experimente mit 1) Stoppwort-gefilterten Texten und 2) Stoppwort-gefilterten und gestemmten Texten durch. Führen Sie die Feature-Selection sowohl vor dem Filtern als auch danach durch, wodurch sich zusammen mit den Ergebnissen aus der vorherigen Teilaufgabe 5 Datenreihen ergeben. Vergleichen Sie diese nun in einem einzigen Diagramm. Vergleichen Sie auch den Verlauf der Trainingszeiten, der Übersicht halber möglicherweise in einem getrennten Diagramm.
Interpretieren Sie Ihre Ergebnisse: Wie sehr beeinflussen die zusätzlichen Vorverarbeitungsschritte die Performanz, auch in Abhängigkeit vom Aufwand?
Nennen Sie ein Szenario, bei denen die Kombination mit der besten Accuracy nicht zwingend die geeigneteste wäre.
Hinweis: Wenn Sie sich merken, welche Features gestoppt und welche gestemmt wurde, können Sie möglicherweise zwei der Datenreihen aus den zwei vorherigen herleiten, falls der Aufwand für eine Neuberechnung zu hoch sein sollte.
Denken Sie sich einen weiteren Aspekt aus, den Sie für interessant halten und den Sie gerne untersuchen möchten, und stellen Sie ähnliche Vergleiche an. Dies kann z.B. die Evaluation in Abhängigkeit einer anderen Größe N (z.B. Anzahl Trainingsbeispiele), einer unterschiedlichen Feature-Generierung (n-Gramme, Buchstabenpaare, Buchstaben, ...) oder Gewichtung (TF, andere), Veränderungen der SVM-Parameter (Kernel-Typ, Fehlertoleranz C), oder was Ihnen sonst noch einfällt. Was konnten Sie in Ihren Experimenten beobachten und was sind Ihre Schlussfolgerungen?
Sie haben von einem Kommilitonen, der genau die Trainings- und Testdaten wie Sie verwendet hat, aber einen anderen Algorithmus, einen bestimmten Performance-Wert erfahren. Für den Vergleich mit Ihrem Lernalgorithmus wäre es nun naheliegend, diejenigen Parameterwerte (Anzahl Features, Kernelparameter C, g, o.a.) zu wählen, für die die Performance am besten ist, und diesen Performance-Wert für den Vergleich zwischen beiden Algorithmen zu nehmen.
Warum ist dieses Vorgehen problematisch? Wie ließe sich dieses Problem beheben?

Hinweise zur Textextraktion aus HTML-Dokumenten

Sollten Sie Probleme mit HTML-Parsern in Ihrer Programmiersprache wie z.B. mit BeautifulSoup, html2text (Python), HTMLDocument.getText(), html parser, Cobra (Java), html2text.pl (perl) oder mit selbst erstellten Parsern haben, so könnten Sie auch ein etwas robusteres externes Programm aufrufen wie html2text oder die textbasierten Webbrowser links, w3m und linx zum Rendern verwenden und anschließend die generierte rohe Textausgabe parsen.

Hinweise zu Stemming

Es existiert eine Vielzahl an Stemming-Algorithmen und Implementierung für die verschiedensten Programmier- und natürlichen Sprachen. Der bekannteste Algorithmus ist hierbei der Porter Stemm Filter. Sie können aber auch jedes beliebige andere verwenden. Hier eine kleine Auswahl:

Hinweise zu den SVMs

Parameter: Verwenden Sie jeweils die Standard-Einstellungen der Programme falls nicht anders angegeben. Stellen Sie allerdings insbesondere bei Verwendung von Wrappern sicher, daß auch die korrekten Standardeinstellungen verwendet werden. So gab es z.B. in vorherigen Jahren Fälle, bei denen der gamma Wert des Kernels von LibSVM? fälschlicherweise auf Null gesetzt wurde.
Datenformat: Beide Formate sollten kompatibel zueinander sein, eine Spezifizierung finden Sie unter http://svmlight.joachims.org/ im How to use Kapitel und geeignete Beispiele finden sich unter http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary.html.
Wrapper: Sie können beide Frameworks jeweils über geeignete Schnittstellen für Ihre Programmiersprache aufrufen (Referenzen auf den Homepages), oder Sie rufen die Programme einfach extern auf und vermeiden dabei auch gleich mögliche Probleme mit den Wrappern.
Je nach Vorverarbeitung der Daten kann es passieren, daß das Resultat der SVMs stets auf demselben Niveau bleibt. Experimentieren Sie in diesem Fall mit höheren C Parameter, z.B. 50 statt 1.