Übung 3 - Web Mining

Binäre Klassifikation von Internet-Seiten

Abgabe: bis Sonntag, den 29.05.11

1. Daten besorgen, Klassen definieren

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.

2. Aufbereitung der Daten

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

Zur automatischen Klassifikation von Internet-Seiten soll nun eine Support Vector Machine 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.
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 50 und erhöhen Sie diesen beim nächsten Schritt um z.B. 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 einzelnen Experimente sollten normalerweise zügig laufen. Sollte es bei Ihnen trotzdem zu Zeitproblemen kommen (eine Laufzeit von 10 min. ist allerdings im Normalbereich), schränken Sie das maximale N ein und machen Sie notfalls auch größere Schritte mit steigendem N.
Führen Sie nun die gleichen Experimente mit 1) Stoppwort-gefilterten Texten und 2) Stoppwort-gefilterten und gestemmten Texten durch. Vergleichen Sie nun die drei Ergebnisreihen in einem einzigen Diagramm. Vergleichen Sie auch den Verlauf der Trainingszeiten, der Übersicht halber möglicherweise in einem getrennten Diagramm.
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.
Wählen Sie eine relativ geringe Anzahl Features (Datensatz ohne Stoppwort-Filterung, ohne Stemming), bei der die SVM relativ schlecht ist, aber dennoch noch eine Chance hat (keine Chance bedeutet, daß man nicht besser ist als einfach immer die größte Klasse vorhersagen). Trainieren Sie nun auf diesen Daten jeweils eine SVM mit einem linearen, polynomiellen (quadratischen) und exponentiellen (radial basis function) Kernel und geben Sie die Accuracy sowohl auf den Test- als auch auf den Trainingsdaten an.
Wie interpretieren Sie die Ergebnisse?
Für den Vergleich mit einem konkurrierenden Lernalgorithmus mit einer bestimmten Performance auf dem Testset wäre es naheliegend, diejenigen Parameterwerte (Anzahl Features, Kernelparameter C, g, o.a.) zu wählen, für die die Performance am besten ist.
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. im letzten Jahr 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.