Weka ist nicht nur die Bezeichnung für einen neuseeländischen, besonders neugierigen Vogel, es ist auch der Name eines Open-Source-Projektes der Universität Waikato aus Neuseeland. WEKA steht für Waikato Environment for Knowledge Analysis und bezeichnet ein Java-Framework für das Data Mining. Ziel des Data Mining ist es, aus vorhandenen Daten neues Wissen zu gewinnen.

Die Guten ins Töpfchen

Handelt es sich bei den Daten um Textdokumente und nicht etwa um Tabellen, so ist die Rede von Text-Mining. Ein häufiger Anwendungsfall ist die Klassifikation von Textdokumenten, um beispielsweise E-Mails in unerwünschte und willkommene Post zu trennen. Für die automatische Klassifikation werden vor allem Verfahren aus dem Bereich des "Maschinellen Lernens" eingesetzt. Dabei "lernt" ein Softwareprogramm von einer Menge bereits klassifizierter Dokumente, wie es zukünftige Dokumente derselben Art zu unterscheiden hat.
Allerdings verarbeiten die meisten Algorithmen des Maschinellen Lernens nur numerische oder nominale (aufzählbare) Daten. Indem jedoch ein Text in eine Liste numerischer Werte übersetzt wird, können erprobte Standardverfahren zur Anwendung kommen. Eine offensichtliche Transformierung ist das Zählen von Wortvorkommen. Ein gehäuftes Auftreten von Wörtern wie "Kaufen" oder "Gratis" lässt etwa auf Spam schließen. Ein Wort entspricht dabei einem Attribut einer Dateninstanz beziehungsweise einer Spalte in einer Tabelle. Für jedes Textdokument wird gezählt, wie oft dieses Wort vorkommt. Um die Menge an Attributen klein zu halten, werden Stoppwörter wie "ein" oder "so" (also häufige Wörter ohne inhaltliche Relevanz) ignoriert.
Schließlich können die Wortzählungen zu Häufigkeiten normalisiert werden, indem für jede Spalte die Summe über alle Zeilen berechnet und die Werte in den Zeilen durch diese Summe dividiert werden. In Folge summieren sich die einzelnen Werte zu eins. Zusätzliche Transformierungen wie die inverse Dokumentenhäufigkeit (IDF, Inverse Document Frequency) und die Termhäufigkeit (TF, Term Frequency) führen in vielen Fällen zu einer erhöhten Genauigkeit bei der anschließenden Klassifikation. Sie berücksichtigen die Seltenheit und Repräsentativität eines Wortes.

Die Schlechten ins Tröpfchen

Die Genauigkeit einer Klassifikation wird als der prozentuale Anteil der korrekt klassifizierten Dokumente gemessen. Um die Performance eines Klassifikationsverfahrens zu evaluieren, sind zwei unabhängige Datenmengen erforderlich. Ein Trainingset dient dem Klassifikator zum Erlernen eines Klassifikationsmodells. Mittels des Testsets wird anschließend die Klassifikation ausgewertet.
Ein Klassifikationsverfahren benutzt die Trainingsinstanzen, um ein internes Modell zu erstellen, welches die Daten auf einer höheren Abstraktionsebene beschreibt. Anhand dieses Modells entscheidet ein Klassifikator in der Testphase, wie eine Testinstanz zu klassifizieren ist. Die zahlreichen Verfahren unterscheiden sich insbesondere dahingehend, welcher Art ihr Modell ist und wie sie dieses Modell erzeugen. Einige Algorithmen vertrauen auf Entscheidungsbäume, andere auf statische Häufigkeiten und Wahrscheinlichkeiten. Ein bekannter Vertreter der letztgenannten Art ist der Naïve Bayes-Klassifikator, von dem mehrfach gezeigt wurde, dass er unter anderem bei der Textklassifikation gute Resultate erzielt.

Naiver Bayes

Die Bayes'sche Klassifikation basiert auf dem Satz von Bayes, wonach für zwei (zufällige) Ereignisse A und B gilt:

1. P(A|B) = P(B|A) * P(A) / P(B)

Hierbei ist P(A) die Wahrscheinlichkeit für das Eintreten des Ereignisses A und P(A|B) bezeichnet die bedingte Wahrscheinlichkeit, das heißt, die Wahrscheinlichkeit, dass, wenn Ereignis B eingetreten ist, auch Ereignis A eintritt. Bei einem Spamfilter ist A beispielsweise das Ereignis, dass eine E-Mail tatsächlich unerwünscht ist. Das Ereignis B steht hingegen für das Vorkommen eines Wortes in der Email. In der Praxis werden natürlich weitaus mehr Wörter berücksichtigt, sodass B als ein Vektor von Ereignissen zu betrachten ist. Der Naïve Bayes-Klassifikator nimmt an, dass die einzelnen B's, das heißt die Wörter, unabhängig voneinander sind:

1. P(B) = P(B<sub>1</sub>
2. ) * P(B<sub>2</sub>
3. ) * ... * P(B<sub>n</sub>
4. )
5. P(B|A) = P(B<sub>1</sub>
6. |A) * P(B<sub>2</sub>
7. |A) * ... * P(B<sub>n</sub>
8. |A)

Diese naive Annahme, die dem Klassifikator seinen Namen einbrachte, trifft zwar in den wenigsten Fällen zu, funktioniert aber in den meisten Fällen erstaunlich gut und vereinfacht die Berechnung ungemein.
In der Trainingphase schätzt der Naïve Bayes-Klassifikator die Wahrscheinlichkeiten P(B|A) und P(A), indem er aus der vorklassifizierten Menge an Textdokumenten die relativen Worthäufigkeiten in Abhängigkeit von der Dokumentklasse und die relativen Häufigkeiten der Dokumentklassen selbst berechnet. Gemäß dem Satz von Bayes kann dann in der Testphase für ein Dokument die Wahrscheinlichkeit der Klassenzugehörigkeit P(A|B) aus den zuvor geschätzten Wahrscheinlichkeiten kalkuliert werden.

Rundflug

Das Weka-Framework stellt nicht nur verschiedene Varianten der Bayesschen Klassifikation zur Verfügung, sondern darüber hinaus mehrere Dutzend weitere Klassifikatoren wie zum Beispiel Support-Vector-Maschinen, neuronale Netze und verschiedene regelbasierte oder auf Entscheidungsbäumen fußende Verfahren. Zudem implementiert die Weka-Software eine Reihe von Filtern, um beispielsweise für eine gegebene Menge von Texten die beschriebenen Worthäufigkeiten zu bestimmen. Schließlich unterstützt das Open-Source-Projekt auch weitere Spielarten des Data Mining, wie zum Beispiel Clustering, Regression und Attribute Selection.
Als universelles Datenformat kommt in Weka das Attribute Relation File-Format zum Einsatz. Hierbei handelt es sich um ein einfaches Textformat, ähnlich den CSV-Dateien, welches eine einzige Tabelle aufnehmen kann. Im Unterschied zu den CSV-Dateien enthält eine ARFF-Datei einen Header, welcher das Datenformat beschreibt, das heißt die Anzahl, die Namen und die Typen der Attribute beziehungsweise Spalten.
Für die Anwendung der unterschiedlichen Weka-Komponenten stehen verschiedene Schnittstellen bereit. Es existieren sowohl ein Java-API als auch mehrere GUIs, namentlich der Explorer für einfache Datenanalysen, der Experimenter für umfangreiche Evaluierungen und eine Workflow-Umgebung namens KnowledgeFlow. Zudem lassen sich die Komponenten auch auf der Kommandozeile einsetzen.
Für eine vollständige Dokumentation der Schnittstellen sei hier auf die Weka-Website verwiesen [1], die auch die Software zum freien Download bereithält. Das dazugehörige Buch mit dem Titel "Data Mining" wurde bereits im Java Magazin vorgestellt [2]. Im Magazin Linux Enterprise erschien außerdem eine Einführung in die Anwendung von Weka. Dieser Artikel ist ebenfalls online unter [3] verfügbar, sodass im Folgenden auf eine Einführung in das Weka-GUI verzichtet werden kann und stattdessen das Java-API im Vordergrund steht.

Datenfluss

Für die Implementierung eines Textklassifikators werden zwei Komponenten benötigt. Die StringToWordVector-Klasse nimmt eine ARFF-Datei mit einem String-Attribut entgegen, zählt die Worthäufigkeiten und gibt eine ARFF-Datei mit numerischen Attributen aus. Um eine ARFF-Datei im Speicher zu repräsentieren, stellt das Weka-Framework die Klasse Instances bereit. Ein Instance-Objekt stellt hingegen eine einzelne Dateninstanz dar.
Die transformierten Instanzen dienen wiederum als Eingabe für die NaiveBayesUpdateable-Klasse. Die NaiveBayesUpdateable-Klasse unterscheidet sich von der NaiveBayes-Klasse dadurch, dass ihr auch noch nachträglich Trainingsinstanzen hinzugefügt werden können. Hierfür erbt sie von der NaiveBayes-Klasse und implementiert zusätzlich die Schnittstelle UpdateableClassifier. Als Basisklasse für sämtliche Klassifikatoren dient die abstrakte Klasse Classifier. Die hiervon abgeleite und in Listing 1 gezeigte TextClassifier-Klasse verwendet intern die Klassen StringToWordVector und NaiveBayesUpdateable. Gezeigt sind in Listing 1 nur die Implementierungen der wesentlichen Methoden. Der vollständige Quellcode befindet sich auf der Heft-CD. Die Methode buildClassifier akzeptiert ein Instances-Objekt und verwendet die darin enthaltenen Instanzen zur Erzeugung des internen Modells. Im Falle der TextClassifier-Klasse werden die Instanzen zuerst mittels des StringToWordVector-Objekts transformiert und anschließend an das NaiveBayesUpdateable-Objekt weitergereicht, indem dessen buildClassifier-Methode aufgerufen wird.
Vergleichbares geschieht in den Methoden distributionForInstance und updateClassifier. Die distributionForInstance-Methode ermittelt für eine gegebene Instanz die Wahrscheinlichkeiten für die möglichen Klassen. Die Methode updateClassifier aktualisiert hingegen das Klassifikationsmodell, indem es eine weitere Trainingsinstanz hinzufügt.

Listing 1
Textklassifikator für Weka

1. package de.javamagazin.esort;
2. ...
3. public class TextClassifier extends Classifier implements UpdateableClassifier {
4. private StringToWordVector str2wc = null;
5. private NaiveBayesUpdateable nbu = null;
6. private Instances structure = null;
7. public TextClassifier() {
8. super();
9. str2wc = new StringToWordVector();
10. nbu = new NaiveBayesUpdateable();
11. str2wc.setIDFTransform(true);
12. ...
13. }
15. public void buildClassifier(Instances trainingSet) throws Exception {
16. str2wc.setInputFormat(trainingSet);
17. trainingSet = Filter.useFilter(trainingSet, str2wc);
18. nbu.buildClassifier(trainingSet);
19. structure = new Instances(trainingSet, 0);
20. }
22. public double[] distributionForInstance(Instance testInstance) throws Exception {
23. return nbu.distributionForInstance(filter(testInstance));
24. }
26. public void updateClassifier(Instance instance) throws Exception {
27. nbu.updateClassifier(filter(instance));
28. }
30. private Instance filter(Instance instance) throws Exception {
31. str2wc.input(instance);
32. str2wc.batchFinished();
33. return str2wc.output();
34. }
35. }

Zusammentreffen

Damit der Textklassifikator im Weka-GUI zur Verfügung steht, müssen einerseits die Klasse TextClassifier in den Klassenpfad von Java aufgenommen und andererseits die Datei GenericPropertiesCreator.props editiert werden [1]:

1. weka.classifiers.Classifier=\
2. weka.classifiers.bayes,\
3. ...
4. de.javamagazin.esort

Der Eintrag weka.classifiers.Classifier wird demnach um den Paketnamen für die Klasse TextClassifier erweitert. Sämtliche hier aufgelisteten Pakete werden nach Klassen durchsucht, die entweder direkt oder indirekt von der Klasse weka.classifiers.Classifier erben. Die gefundenen Klassen werden schließlich dem Benutzer zur Auswahl angezeigt. Damit die Weka-Software die Konfigurationsdatei findet, muss diese im aktuellen Arbeitsverzeichnis abgelegt werden oder unter Linux alternativ im Home-Verzeichnis.
Für die Evaluierung des Textklassifikators wird ein ausreichend großer Satz von bereits klassifizierten Textdokumenten benötigt. Hierfür eignen sich Datensätze besonders gut, die bereits für andere Evaluierungen eingesetzt wurden, da somit ein Vergleich zu bestehenden Verfahren möglich ist. Ein solcher Datensatz ist jener, der unter [4] zur Verfügung steht und von Tom Mitchell in seinem (überaus lesenswerten) Buch [5] zum Thema Maschinelles Lernen vorgestellt wurde. Es handelt sich um knapp 20.000 Textdokumente, die zwanzig verschiedenen Newsgroups entnommen und gemäß ihrer Abstammung in verschiedenen Ordnern abgelegt wurden. Die folgende Auswertung der TextClassifier-Klasse beschränkt sich jedoch auf zwei Foren (zu den Themen PC und Mac). Um die Textdateien in einer einzigen ARFF-Datei samt Klassenattribut zusammenzufassen, steht unter [6] ein einfaches Java-Konsolenprogramm zur Verfügung. Selbiges sowie die hiermit erzeugte ARFF-Datei befinden sich ebenfalls auf der Heft-CD. Der folgende (Windows-)Befehl lädt diese ARFF-Datei in den Weka-Explorer:

1. java.exe -Xmx512M -cp eSort\bin;eSort\lib\weka.jar weka.gui.explorer.Explorer evaluation\text.arff

Zu beachten ist hierbei, dass Weka derzeit nur fehlerfrei mit der Java-Version 1.4.x funktioniert. Die Angabe des Schalters -X sorgt dafür, dass dem Programm genügend Speicher zur Verfügung steht. Insbesondere Anwendungen im Bereich des Data Mining sind oftmals sehr speicherhungrig - so auch der Textklassifikator.
Im Explorer-GUI wird die Evaluierung auf der Seite Classify durchgeführt. Um statistisch relevante Ergebnisse zu erzielen, zerlegt der Explorer die ARFF-Datei in zehn gleichgroße Mengen. In insgesamt zehn Evaluierungsrunden wird jeweils eine der zehn Mengen als Testset verwendet. Die übrigen Mengen werden in ein Trainingsset zusammengefasst und schließlich die Ergebnisse der einzelnen Runden gemittelt. Das Gesamtergebnis dieser 10fachen Kreuzvalidierung ist in Abpictureung 1 zu sehen. Mit einer Vorhersagegenauigkeit von 88 Prozent erzielt die TextClassifier-Klasse durchaus brauchbare Resultate.

Alleingang

Listing 2 und Listing 3 zeigen abschließend (in Ausschnitten) den programmatischen Einsatz der TextClassifier-Klasse in einem einfachen Konsolenprogramm namens eSort. Beim Aufruf ohne Kommandozeilenparameter kommt der in Listing 2 gezeigte Code zum Einsatz. Im aktuellen Verzeichnis wird nach Unterverzeichnissen mit Textdateien gesucht. Hieraus erzeugt eSort ein Instances-Objekt und verwendet dieses anschließend für das Training eines Textklassifikators. Schließlich serialisiert das Programm das trainierte TextClassifier-Objekt in eine Datei.
Bei der Übergabe ein oder mehrerer Dateien als Kommandozeilenparameter führt eSort den in Listing 3 gezeigten Code aus. Zuerst deserialisiert es das TextClassifier-Objekt. Dann liest es der Reihe nach die Textdateien aus und erzeugt jeweils ein Instance-Objekt. Diese werden anschließend mithilfe der TextClassifier-Methode distributionForInstance klassifiziert und die Klassenwahrscheinlichkeiten werden dem Benutzer präsentiert. Zum Schluss hat der Benutzer noch die Möglichkeit, die tatsächliche Klasse zu nennen und somit das Klassifikationsmodell mit einer weiteren Instanz zu trainieren.

Listing 2
Erzeugung und Serialisierung eines Klassifikationsmodells

1. TextDirectoriesToArffFile txt2arff = new TextDirectoriesToArffFile();
2. Instances dataSet = txt2arff.createDataset(".", false);
3. dataSet.setClassIndex(0);
4. tc = new TextClassifier();
5. tc.buildClassifier(dataSet);
6. ...
7. FileOutputStream fos = new FileOutputStream(MODEL_FILE_NAME);
8. ObjectOutputStream oos = new ObjectOutputStream(fos);
9. oos.writeObject(tc);
10. oos.close();
11. fos.close();

Listing 3
Automatische Klassifikation und Aktualisierung des Klassifikationsmodells

1. FileInputStream fis = new FileInputStream(MODEL_FILE_NAME);
2. ObjectInputStream ois = new ObjectInputStream(fis);
3. tc = (TextClassifier) ois.readObject();
4. ...
5. // Text aus der Datei auslesen und in der Variablen text speichern.
6. ...
7. Instance instance = new Instance(tc.format().numAttributes());
8. instance.setDataset(tc.format());
9. instance.setValue(1, text);
10. double[] dist = tc.distributionForInstance(instance);
11. ...
12. // Wahrscheinlichkeiten für Klassen ausgeben.
13. ...
14. // Benutzer hinterlegt tatsächliche Klasse in der Variablen realClassValue.
15. ...
16. instance.setClassValue(realClassValue);
17. tc.updateClassifier(instance);
18. ...
19. // Model speichern (siehe Listing 2).

Martin Szugat ist ein langjähriger Autor des Software & Support-Verlags. Am Bioinformatik-Lehrstuhl der Universität München implementierte er BioWeka (www.bioweka.org), eine Erweiterung des Weka-Frameworks für die Bioinformatik. Kontakt: Martin.Szugat@gmx.net.

Links & Literatur

• [1] Weka: www.cs.waikato.ac.nz/ml/weka/
• [2] Ian H. Witten, Eibe Frank: Data Mining. Praktische Werkzeuge und Techniken für das Maschinelle Lernen: www.javamagazin.de/itr/buchtipps/psecom,id,302,nodeid,21.html
• [3] Martin Szugat: Im Datenrausch. Praktische Einführung in das Data Mining mit Weka 3.4, Linux Enterprise 1.2005: bioweka.sourceforge.net/download/LE_1.05_75-79.pdf
• [4] UCI KDD-Datensätze: kdd.ics.uci.edu/summary.data.application.html
• [5] Tom Mitchell: Machine Learning, McGraw Hill, 1997
• [6] TextDirectoryToArff: article.gmane.org/gmane.comp.ai.weka/1943/match=textdirectorytoarff