Übung 4 - Web Mining

Ab­gabe: bis Son­ntag, den 16.6.2013

Classification Competition

In dieser Übung werden Sie gegen die anderen Teams in einem Klassifikationswettbewerb antreten. Sie bekommen hierfür von uns eine Menge an Trainingsdokumenten, für die die Klassenzuordnung bekannt ist, und eine Menge an Testdokumenten, für die die Klassenordnung nicht bekannt ist. Es gibt insgesamt 11 Klassen, es handelt sich also um ein Multiklassen-Problem. Ziel ist es, auf den Trainingsdokumenten einen Klassifizierer zu lernen, der die Testdokumente korrekt Ihren Klassen zuordnet.

Daten

Die Trainingsdaten in u4_train.zip bestehen aus 339 Textdokumenten, die sich in 11 Verzeichnissen befinden. Die Verzeichnisse entsprechen den Klassen. Für jeden Text wurden die darin enthaltenen Sätze randomisiert, so daß immer noch Zwischen-Wort-Beziehungen ausgenutzt werden können.

Die Testdaten in u4_test.zip bestehen aus 112 Textdokumenten, die in der gleichen Weise vorbereitet wurden, nur daß diesmal keine Einteilung in Verzeichnissen vorhanden ist. Die Abgabe erfolgt in einer Datei, in der jedem Dateinamen eine Klasse zugeordnet ist. Beachten Sie hierbei die Hinweise weiter unten.

1. Implementierung Lern-Algorithmus (2 P)

1. Implementieren Sie einen Multiklassen-Klassifizierer Ihrer Wahl. In Betracht kommen hierbei z.B. Naive Bayes, Rocchio (siehe auch SS12), Compress (SS11), k-NN (SS10). Auch Erweiterungen wie Dekomposition, Active Learning etc. kommen dabei in Betracht. Greifen Sie dabei nicht auf bestehende Programmbibliotheken zurück, programmieren Sie den Kern des Algorithmus selbst.
   Beschreiben Sie Ihren Algorithmus, insbesondere Besonderheiten oder Abweichungen von den üblichen Implementierungen.
   

2. Vorbereitung Evaluierung (2 P)

1. Um mögliche Verbesserungen im Algorithmus oder in der Vorverarbeitung zu evaluieren, können Sie den gelabelten Datensatz z.B. wie in der letzten Übung wiederum in Trainings- und Testdaten aufteilen. Überlegen Sie sich für Ihre Experimente eine solche Aufteilung und begründen Sie Ihre Wahl. Welche Vor- und Nachteile hat Ihr Ansatz, und wie geeignet ist dieser Ansatz um die Performance auf den Testdaten der Competition vorherzusagen?
   
2. Implementieren Sie folgende Evaluations-Maße: Accuracy und Micro-averaged Precision, Recall, und F1. Geben Sie in den folgenden Experimente jeweils alle vier Maße an.
   Um diese Maße zu berechnen, müssen Sie die Konfusionsmatrix/matrizen berechnen. Geben Sie zumindest für einen der Experimente die Multiklassen-Konfusionmatrix und die aggregierte Zwei-Klassen-Konfusionsmatrix (benötigt z.B. für Micro-averaged) an.

3. Experimente und Abgabe (6 P)

1. Wenden Sie Ihren Algorithmus auf den Daten an. Versuchen Sie, Ihr Ergebnis durch Verbesserungen am Algorithmus, durch Vorverarbeitungsschritte oder durch andere Maßnahmen zu verbessern. Sie dürfen hierfür das gesamte (legale!) Repertoire, das Sie in den Übungen und in der Vorlesung kennengelernt haben oder Ihnen sonst wie einfällt, ausschöpfen.
   Berichten Sie über Ihre Vorgehensweise und Ihren Fortschritt. Berichten Sie z.B. welchen Unterschied eine bestimmte Maßnahme bewirkt hat, und wieso Sie diese ausprobiert haben. Wurden Ihre Erwartungen jeweils erfüllt?
2. Produzieren Sie für jedes Dokument in den Testdaten eine Vorhersage (siehe Hinweise für Abgabeformat). Verwenden Sie hierbei das Modell, von dem Sie den höchsten Micro-averaged-F1 Wert erwarten. Geben Sie auch eine Abschätzung für die vier Maße auf den Testdaten ab.
   Als kleinen Anreiz gibt es für den Erst-Platzierten 2 Bonuspunkte, für den 2. und 3. 1,5 Bonuspunkte, für den 4. und 5. 1 Bonuspunkt und für den 6. und 7. 0,5 Punkte.
   

Hinweise

• Schreiben Sie Ihre Vorhersagen in eine Datei namens GXX_predictions mit XX als Gruppennummer. Schreiben Sie dabei für jedes Testdokument eine Zeile im Format Dateiname Tabulator Klassename, also z.B.:
  012fa0f142ab9049b98033b4f2a04d23    hobbies
  03082d7773ec8e48918672e8ff5a9586    fiction
  ...
  

  Sortieren Sie die Dateinamen nach alphabetischer Reihenfolge.

• Sie können Ihre Abgabe teilweise validieren, indem Sie folgende Befehle unter Linux bzw. unter Windows mit den GNU Utilities ausführen:
• cat file | grep -c "" sollte 112 ausgeben.
• sort file | uniq | grep -c "" sollte 112 ausgeben.
• sort file | uniq | grep -P -c "^[0-9a-f]{32,32}\t(adventure|belles_lettres|editorial|fiction|government|hobbies|learned|lore|mystery|news|romance)$" sollte 112 ausgeben
• sort file | diff - file sollte sich höchstens über ein Zeilenumbruch am Ende beschweren.
• Sie dürfen sich gerne im Forum über Ihre aktuellen Ergebnisse mit den anderen Gruppen austauschen. Das hilft Ihnen zu sehen, wo sich sich gerade befinden, wo noch Verbesserungspotential ist bzw. ob Sie vielleicht Fehler in der Evaluierung haben.