Übung 3 - Web Mining

Binäre Klassifikation von Internet-Seiten

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, oder Sie verwenden zwei Klassen aus dem 4 Universities Data Set. Aber wir ermutigen Sie auch, andere Datensätze zu suchen oder selbst einen interessanten Datensatz zu erstellen, indem Sie Seiten sammeln (z.B. von einer Online-Zeitung) und diese binär klassifizieren (z.B. zwei bereits existierende Kategorien benutzen).

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 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
Wenden Sie auf die Liste von Wörtern Stoppwort-Filterung und Stemming an. 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 im Trainingsset 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 Dokument aus Ihrem Trainingsdatensatz aus und geben Sie repräsentativ für dieses das Ergebnis der einzelnen Transformations-Schritte an. Zeigen Sie insbesondere das Sparse-Format, wenn Sie nur die 10 häufigsten Wörter (Dokumenthäufigkeit) verwenden sollen. Geben Sie auch an, wie viel Wörter vor und nach Stopp-Wort-Filterung und Stemming übrig geblieben sind.

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 (oder ein anderes vergleichbares SVM-Paket, wenn Sie hiermit besser vertraut sind oder es in der von Ihnen präferierten Programmiersprache besser verfügbar ist). Als Performanz-Maß soll hier im Allgemeinen 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), einem C-Parameter von 50 (-C 50) mit den in Aufgabe 2 vorbereiteten Daten trainieren und auf den vorbereiteten Testdaten evaluieren. Verwenden Sie dabei nur die häufigsten z.B. 1000 Wörter für das Trainieren und Testen.
Geben Sie die Konfusionsmatrix, die erlangte Accuracy und die benötigte Trainings- und Testzeit an. Vergleichen Sie die Accuracy mit der eines Klassifizierers, der immer die häufigste Klasse in den Trainingsdaten vorhersagt (Baseline).
Testen Sie mit höheren C-Parametern, falls Sie ungewöhnliche Resultate bekommen (siehe auch Hinweise am Ende).
Fügen Sie wenigstens für diese Teilaufgabe auch die verwendeten Trainings- und Testdateien im Sparse-Format Ihrer Abgabe bei. (1 P)
Lassen Sie sich auf den Testdaten aus der ersten Teilaufgabe die Vorhersage-"Wahrscheinlichkeiten" oder Konfidenzen ausgeben (z.B. Parameter -b 1 bei LibSVM) und erstellen Sie hiermit eine Recall-Precision-Kurve.
Dies erreichen Sie, indem Sie statt der Verwendung der üblichen Schranke (üblicherweise 0 bei Scores oder 0,5 bei Wahrscheinlichkeiten) diese variieren. Sortieren Sie hierfür die Vorhersagen nach ihrem Score und wählen Sie nacheinander jeden Score als Schranke. Ermitteln Sie für diese Schranken Recall und Precision und tragen Sie diese Werte-Paare in den Graphen ein.
Beschreiben Sie die Kurve. Bestimmen sie aus der Kurve den Break-Even-Point (1,5 P).
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 Ähnliches für Windows zu verwenden. (2 P)
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. Versuchen Sie dabei, die Performanz-Werte aus den vorherigen Aufgaben zu schlagen.
Was konnten Sie in Ihren Experimenten beobachten und was sind Ihre Schlussfolgerungen? (1,5 P)
Sie nehmen an einem Data-Mining-Wettbewerb teil, in dem es um binäre Klassifizierung geht. Sie erhalten vom Veranstalter eine Trainingsmenge, in denen die wahren Klassen bekannt sind und auf denen Sie Ihren Algorithmus trainieren können. Außerdem erhalten Sie eine Evaluierungsmenge, auf der Sie nicht die Klassen kennen. Sie können aber dem Veranstalter eine Vorhersage auf dieser Menge zuschicken und erhalten eine Rückmeldung über die Accuracy. Gewinner ist dann derjenige mit der höchsten Accuracy.
Warum ist dieses Setting vom Veranstalter problematisch? Wie kann man sich diese Schwachstelle zu Nutze machen? Wie könnte man das Problem lösen? (1 P)

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, 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 Stemmer 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, dass 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.
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.
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.
Falls Sie Aufgabe 1 und 2 nicht lösen können, wählen Sie einen geeigneten Datensatz (binäre Klassen, möglichst Text) aus http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/ aus und verwenden Sie diesen in Aufgabe 3.
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 oder auch niedrigeren C Parameter. Der C Parameter kann hierbei sogar in die Tausende gehen oder auch sehr nahe an Null sein.