3. Übungsblatt - Web Mining

Abgabe:
bis 4.6. on-line unter http://www.ke.informatik.tu-darmstadt.de/exercises/

 

  1. Implementieren Sie einen einfachen Naive Bayes Klassifizierer nach dem in der Vorlesung vorgestellten Grund-Modell. Gehen Sie wie folgt vor:
    • Erweitern Sie Ihre (oder jemandes anderen) Lösungen für das erste Übungsblatt, sodaß mehrere Texte, die 2 Kategorien repräsentieren, eingelesen werden können, und für jede Kategorie eine separate Zählung der Wort-Häufigkeiten vorgenommen wird. Die Art und Weise der Eingabe bleibt ebenfalls Ihnen überlassen. Als einfache Lösung bietet sich an, alle Dokumente einer Kategorie in ein separates Verzeichnis zu stellen, und den Namen dieses Verzeichnisses als Namen für die Kategorie zu verwenden.
    • Berechnen Sie aus diesen Häfigkeiten die bedingten Wahrscheinlichkeiten für jedes Wort, gegeben die Klasse (verwenden Sie die Laplace-Korrektur, sodaß keine Null-Wahrscheinlichkeiten vorkommen können).
    • Um ein Beispiel zu klassifizieren, berechnen Sie aus diesen Wortwahrscheinlichkeiten die Gesamtwahrscheinlichkeit für jede Klasse, in dem Sie für alle im Text vorkommenden Worte die zugehörigen bedingten Wahrscheinlichkeiten für jede Klasse getrennt aufmultiplizieren. Um etwaige numerische Probleme in den Griff zu bekommen, empfiehlt es sich, die Logarithmen der Wahrscheinlichkeiten zu addieren anstatt die Wahrscheinlichkeiten selbst zu multiplizieren!
    • Die Klasse mit der größeren Wahrscheinlichkeit wird dann vorhergesagt.

    Zum Testen Ihres Programms können Sie zwei (oder mehr) Kategorien beliebiger Dokumenten-Sammlungen verwenden (z.B. Resultate 2-er Crawls mit thematisch unterschiedlichen Kategorien, Ihre E-mails, bestehende Text-Klassifikations-Sammlungen (z.B. (mini) 20 newsgroups, weitere links auf den Vorlesungsfolien)). Verwenden sie mehrere Hundert Dokumente pro Kategorie.

    Teilen Sie Ihre Dokumentensammlung in 2 Hälften, sodaß die Dokumente jeder Kategorie in etwa gleich auf beide Hälften verteilt sind.

    1. Verwenden Sie die eine Hälfte zum Trainieren des Klassifizierers und bestimmen Sie auf der anderen die Vorhersagegenauigkeit (Accuracy), sowie Recall und Precision für jede Kategorie.
    2. Wiederholen Sie das, indem Sie die Rolle der beiden Hälften vertauschen. Vergleichen Sie die erhaltenen Meßwerte.
    3. Bestimmen Sie die Meßwerte auch auf den Trainingsdaten. Interpretieren Sie die Resultate.
  2. Der Naive Bayes Klassifizierer sagt die Klasse vorher, die die größere Gesamt-Wahrscheinlichkeit hat, d.h. die Wahrscheinlichkeit, die größer als 0.5 ist (vergessen Sie nicht die beiden Werte zu normalisieren, sodaß Sie sich auf eins addieren, wie es sich für Wahrscheinlichkeiten gehört). Wenn die beiden Klassen + und - heissen, wird also die Klasse + vorhergesagt, wenn P(+|D) > 0.5 und - wird vorhergesagt wenn P(+|D) < 0.5 ist (und daher P(-|D) = 1 - P(+|D) > 0.5 ist).

    Das Verfahren läszt sich modifizieren, indem man die Schranke flexibel gestaltet, d.h. indem man + vorhersagt, wenn P(+|D) > x ist, für irgendein gegebenes x zwischen 0 und 1. Je nach Wahl der Schranke x, werden mehr oder weniger Dokumente als + klassifiziert, d.h. der Recall und die Precision ändern sich.

    Berechnen Sie für jede Ihrer beiden Klassen auf dem Test-Set eine Recall/Precision-Kurve, nach den folgenden 3 Methoden:
    1. Die Test-Beispiele nach ihrer von Naive Bayes geschätzten Wahrscheinlichkeit für P(+|D) (bzw. P(-|D)) sortieren, die sortierte Liste durchgehen und jeden Wert einmal als Schranke x verwenden. Für jede Schranke berechnen Sie dann Recall und Precision, unter der Annahme (s.o.), daß alle darüberliegenden Werte positiv (bzw. negativ) klassifiziert werden.
    2. Daraus wie in der Vorlesung gezeigt Interpolated Recall und Precision berechnen, für die Recall Werte von (0,0.1,0.2,...0.9.1)
    3. Die Schranke x auf 11 verschiedene Werte 0, 0.1, 0.2, ... 0.9. 1.0 setzen, und für jedes Szenario Recall und Precision berechnen.

    Berechnen Sie für jede der Schranken in der letzten Aufgabe auch die Accuracy, und zeichnen Sie sie über dem Wert der Schranke.

    Anmerkung: Falls Sie die Naive Bayes-Aufgabe nicht lösen, können Sie diese Aufgabe auch an simulierten Wahrscheinlichkeiten lösen.


Last modified: Thu Jun 9 01:02:17 2005
A A A | Drucken | Impressum | Sitemap | Suche | Mobile Version
zum Seitenanfangzum Seitenanfang