4. Übungsblatt - Web Mining

Multiklassen-Klassifikation mit Naives Bayes und k-NN

Abgabe: bis 1.6.

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.
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 Tokens von D, aber es ist hier sinvoller, es wie bei der Formel zu dem full multinomial model über die Terme 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.
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.
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?