Binäre Klassifikation von Internet-Seiten

Abgabe: bis Sonntag, den 30.5.2010

1. Daten besorgen, Klassen definieren
   
   1. 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
   
   1. Dokument zu Wort-Liste
      Extrahieren Sie den Inhalt der Seiten, etwa mit dem Tool html2text, und zerlegen Sie diesen Text in eine Liste von Wörtern. Was Wort hier bedeutet, legen Sie selbst fest. Spezifizieren Sie diese Abbildung, d.h. erklären Sie, was aus dem Originaldokument erhalten bleibt und was wie reduziert wird.
   2. 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).
      Bemerkungen:
      • Sollte sich im weiteren Verlauf herausstellen, dass die Anzahl der gewonnen Features zu groß für Ihr Programm ist, können Sie z.B. Terme mit kleinerer DF aus der Termmenge streichen. Ein solches Vorgehen bezeichnet man als Feature Selection.
      • 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.
   3. Überführen sie die Feature-Vektoren in eine Sparse-Repräsentation und speichern Sie diese sowie die Labelinformationen ab.
   
   
3. Training und Evaluation
   Zur automatischen Klassifikation von Internet-Seiten soll nun eine Support Vector Machine trainiert werden. Verwenden Sie hierfür das libsvm-Framework, das über verschiedene Programmiersprachen eingebunden werden kann. Als Performance-Maß soll hier stets Sccuracy verwendet werden.
   
   1. Machen Sie sich mit dem Framework und der von Ihnen gewählten Schnittstelle vertraut, indem Sie eine C-SVM mit den in Teil 2 vorbereiteten Daten trainieren und evaluieren. Verwenden Sie einen Kernel und Parameter ihrer Wahl.
   2. Vergleichen Sie die Performance auf der Testmenge wenn der Klassifikator mit verschiedenen polynomiellen Kerneln (<x,y> + 1)^g trainiert wird. Setzen Sie dafür verschiedene Tradeoff-Parameter ein, C=2^-10,2^-9,...2^5, und vergleichen diese Testwerte für verschiedene Kernel-Parameter, g=1 (linearer Kernel), 2, 3, 4.
   3. Gehen Sie nun zurück zu Teilaufgabe 2 und ändern Sie Definition der Abbildung Dokument zu Feature-Vector in einer Weise ab, von der Sie sich vorstellen könnten, dass es die Klassifikation verbessert. Vergleichen Sie die Performance dieses neuen Klassifikators mit dem vorangegangenen für g=2 und verschiedene C-Werte, C=2^-10,2^-9,...2^5. Falls Ihre feature-Definition einen Parameter enthält, setzen Sie C=1 und trainieren stattdessen mit verschiedenen Werten des Feature-Parameters.
      Hier kommt es nicht darauf an, daß sich die Performance tatsächlich verbessert, sondern auf eine alternative Feature-Definition und ihre Evaluation.
   4. Für den Vergleich mit einem dritten Klassifikator mit einer bestimmten Performance auf dem Testset wäre es naheliegend, diejenigen Parameterwerte (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?
   
   

• Hin­weise zu Auf­gabe 2.1: Falls das von Ihnen einge­set­zte Tool zum Ex­trahieren des Seit­en­in­halts bei eini­gen Doku­menten ohne Aus­gabe ab­bricht, können Sie zur Lösung der Auf­gabe die Doku­mente ein­fach bei­seite lassen.

• Hin­weise zu Auf­gabe 2.2: Die Def­i­ni­tion der termspez­i­fis­chen Gewich­tung (IDF) we­icht in eini­gen Büchern oder auch in der Wikipedia etwas von der Def­i­ni­tion in den Folien ab.​ Welche dieser Def­i­ni­tion des IDF-Wert Sie wählen, können Sie selb­st entschei­den.