Multiklassen-Klassifikation mit Naives Bayes und k-NN

Abgabe: bis Sonntag, den 13.6.2010

1. Daten besorgen und aufbereiten
   1. Verwenden Sie als Datensatz z.B. den (mini) 20 newsgroups Datensatz. Reduzieren Sie, falls es Ihnen nötig erscheint, die Anzahl der Klassen durch sinnvolles Zusammenlegen oder Auslassen von Kategorien. Sie können jedoch auch beliebige andere Dokumentsammlungen, selbsterstellt oder bereits existierende Text-Klassifikations-Sammlungen, mit mindestens fünf Klassen verwenden.
   2. Teilen Sie wie bei der letzten Übung den Datensatz in einen Trainings- und einen Testdatensatz ein. Teilen Sie die Dokumente möglichst so auf, dass jede Klasse in etwa die gleiche Anzahl Trainings- wie Testbeispiele besitzt.
   3. Erstellen Sie für jedes Dokument den (nicht normalisierten) TF-Vektor und speichern Sie diese sowie die Labeinformation ab.
      Definieren Sie die Termmenge als alle Terme, die in der Trainingsmenge vorkommen.
      
2. Simple Naive Bayes
   Implementieren Sie einen einfachen Naive-Bayes-Klassifizierer. Verwenden Sie bei der Schätzung der Termwahrscheinlichkeiten die Laplace-Korrektur und die Logarithmierung zur Vermeidung von numerischen Schwierigkeiten.
   Zwar läuft auf den Folien zur Bestimmung von p(D|c) das Produkt (bzw. die Summe) über die Sequenz der Tokens t von D, aber es ist hier sinvoller, es wie bei der Formel zu dem Full Multinomial Model über die Terme w im Vokabular laufen zu lassen, da Sie so die TF-Vektoren direkt anwenden können. Lassen Sie aber den Multinomialkoeffizienten, der beim Full Multinomial Model eingesetzt wird, weg.
3. k-NN
   Implementieren Sie einen einfachen k-Nearest Neighbor Klassifizierer.
   Jedes Dokument wird durch seinen TF-Vektor repräsentiert. Um die Nähe von zwei Dokumenten zu messen, sollen sie das Cosinus-Maß verwenden. Verwenden Sie für k beispielsweise 5.
4. Evaluation
   1. Wenden Sie beide Klassifizierer auf die Testdaten an und erstellen Sie jeweils die Multiclass-Konfusionsmatrix. Wenn Sie die beiden Konfusionmatrizen direkt miteinander vergleichen wollen, können Sie sie in eine Tabelle mit doppelten Einträgen schreiben.
      Interpretieren Sie die Konfusionmatrizen.
   2. Berechnen Sie anhand der beiden Konfusionmatrizen die Performance-Maße Precision, Recall und Accuracy unter Verwendung von Micro- und von Macro-Averaging und stellen diese zwölf Werte tabellarisch dar.
      
   3. Führen Sie einen einfachen Laufzeitvergleich durch. Messen Sie dafür die benötigte CPU-Zeit beider Algorithmen jeweils für Training als auch für das Testen.
   4. Welchen Algorithmus würden Sie in welchen Anwendungszenarien bevorzugen. Warum?

Hinweise

• Zwei wichtige Hinweise zum vorgeschlagenen Datensatz mini-newsgroups:
  • Einige der posting sind in mehreren Ordner unter verschiedenen Namen vertreten. Das bedeutet, daß es Dokumente gleichen Inhalts aber mit verschiedenen Labels gibt. Es bedeuted auch, dass die Evaluation etwas zu pessimistisch ist, da ein Trainingsdokument beim Testen erneut auftauchen kann, dann aber zwingend mit einen anderen Label als im Training.
  • Die Dokumente enthalten einen Header inklusive der Label-Information. Diesen Header sollte man nicht in den Feature-Vektor einfließen lassen, da er Daten enthält, die man in der Praxis nicht zu Verfügung hätte.
• Ein alternativer Datensatz ist z.B. der WebKB-Datensatz.
• Alle notwendigen Definitionen finden Sie im Foliensatz text classification.
• Aufgabe 1: Um die Aufteilung in Test- und Trainingsmenge ein wenig zu vereinfachen, können Sie die Gesamtheit der Dokumente durch eine zufällige Auswahl aufteilen. Zwar weichen dann die Größenverhältnisse von Training- zu Testmenge der einzelnen Klassen etwas von einander ab, aber bei 100 oder mehr Dokumenten pro Klasse sind größere Abweichungen sehr unwahrscheinlich.
• Aufgabe 3: Für k-NN können Sie zunächst alle TF-Vektoren normalisieren, so daß das Cosinus-Maß zu einem einfachen Skalarprodukt wird.