Übung 4 - Web Mining

Das neue System ist online. Pro Tag dürfen drei Vorhersagen hochgeladen werden. 

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.

Evaluierung

Sie können Ihre Vorhersage über das Upload-System hochladen und evaluieren lassen (Tab "Competition"). Es werden alle Ihre Abgaben in einer Tabelle angezeigt, also auch Ihre beste Abgabe im Vergleich zu den besten Abgaben der anderen Gruppen. Geordnet wird dabei nach Micro-averaged F1 (siehe auch weiter unten). Pro Kalendertag ist nur eine bestimmte Anzahl Evaluierungen möglich, und zwar drei. Sie sollten deshalb sparsam damit umgehen. Die letzte Einreichung wird Sonntag/Montag, also noch nach Mitternacht möglich sein.

1. Implementierung Lern-Algorithmus (3 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 Experimenten 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 (5 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. Da Sie jeweils nur ein begrenztes Kontingent an Auswertungen auf den Testdaten haben, führen Sie jeweils vorher eigene Abschätzungen aus (siehe A2.1) und geben Sie, falls Sie doch ein Upload wagen wollen, sowohl die reale Auswertung als auch Ihre Abschätzung für die vier Maße an. Entsprechen sich beide Werte? Falls nicht, warum?

4. Bonus und Siegerehrung

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. Fügen Sie Ihre beste Vorhersagedatei der Abgabe an.

• 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 und verwendete Methoden 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. Machen Sie dafür aber auch von der Möglichkeit Gebrauch, fortlaufend online Vorhersagen auf den Testdaten auswerten zu können.