Teil 3: Klassifizieren von Daten

Apache Mahout: Die Guten ins Töpfchen …

Karsten Voigt , David Broßeit

© Shutterstock / Cienpies Design

Woher weiß ein System eigentlich, welche Mail in meinem Spamordner landen soll und welche ich vielleicht doch lieber lesen möchte? Täglich werden Abermillionen an Mails versendet, und dabei ist wahrscheinlich nur ein kleiner Bruchteil wirklich lesenswert. Über die automatische Klassifizierung von E-Mails lernen Systeme, Spam immer besser zu erkennen. Helfen diese Mechanismen auch im Aufbau von Empfehlungssystemen?

In den ersten beiden Teilen dieser Reihe, die auch im Java Magazin erschienen sind, haben wir uns mit Produktempfehlungen und der Gruppenbildung von Kunden mit Mahout auseinandergesetzt. In beiden Fällen wurde dabei eine Vielzahl an Daten analysiert und aufbereitet, ohne dass dabei dem System eine feste Zuordnung von Elementen mitgegeben wurde. Das Ergebnis der Analyse war nicht direkt vorhersehbar. Wenn man nun eine bestehende Ansammlung von Mails automatisch clustern lässt, wird man sicherlich interessante Gruppen erhalten, und eventuell sind auch einige sinnvolle dabei (z. B. Mails von der Familie). Dass aber Spam automatisch in einer eigenen Gruppe landet, ist eher unwahrscheinlich. Das Bilden von Gruppen läuft als ohne Aufsicht ab und so wird die Clusterbildung auch als Unsupervised Learning bezeichnet.

Die Klassifizierung verfolgt nun einen etwas anderen Ansatz. Aus einer gegebenen bekannten Größe an Elementen und deren Zuordnung zu einer Gruppe wird versucht, ein Vorgehen abzuleiten, das neue Elemente automatisch der richtigen Gruppe zuordnet (Supervised Learning). Die Zuordnung von E-Mails zu Spam funktioniert in einem solchen Fall, weil vorher bestehende Mails bereits manuell als Spam markiert wurden.

Ein anderes klassisches Beispiel für Klassifizierungen sind die Mechanismen zur Fraud Detection. Hier wird bei der Abwicklung von Zahlungen über Kreditkarten aus Erkenntnissen der Vergangenheit versucht, untypische Kaufmuster eines Kunden zu identifizieren und entsprechend als Betrug/Nichtbetrug einzugruppieren. An diesen beiden Beispielen erkennt man bereits, dass bei der Klassifizierung von Elementen meist nur eine überschaubare Anzahl an Zielgruppen als Ergebnis erwartet wird. Im einfachsten Fall ist dies nur eine Zuordnung zu Ja oder Nein in Bezug auf ein bestimmtes Merkmal. Die Klassifizierung wird also eingesetzt, wenn sich die Ausgangsdaten gut kategorisieren lassen.

Offene Fragestellungen bzw. eine theoretisch unbegrenzte Anzahl von Gruppen sind für die Klassifizierung nicht geeignet. Bevor man also mit der Klassifizierung startet, sollte man überlegen, ob die eigenen Daten und die gewünschte Aussage wirklich für die Klassifizierung geeignet sind. Es besteht hier natürlich auch die Möglichkeit der Kombination von Algorithmen, so könnte man über die Clusterbildung die potenziellen Kategorien einer Klassifizierung bestimmen. Gleichzeitig beginnt die Klassifizierung immer mit bekannten Zuordnungen. Wenn noch nie eine Mail als Spam markiert wurde, kann auch keine Klassifizierung von Spamnachrichten erfolgen.

Schritte der Klassifizierung

Abbildung 1 zeigt schematisch die einzelnen Schritte, die für eine Klassifizierung von Daten durchlaufen werden müssen. Als Eingangsgröße dient eine Reihe von Objekten, die den Gruppen bereits zugeordnet sind. Es existiert zu Beginn bereits eine ausreichende Menge an (manuell) klassifizierten Daten. Die Qualität der Klassifizierung steigt mit einer größeren Anzahl an aussagekräftigen Ausgangsdaten. Das Set der Startdaten wird in einen Trainings- und in einen kleineren Testdatenpool geteilt. Mit den Trainingsdaten wird die Vorschrift zur Klassifizierung ermittelt. Bei diesem Training wird das so genannte Modell erzeugt. Das Modell wird dann für das Testen verwendet, um mithilfe der Testdaten die Korrektheit des Trainingsergebnisses zu verifizieren. Das Training selbst nutzt dabei nur die Eingangsdaten ohne die Klassifizierungsinformation. Diese Information wird zum Abgleich der Testergebnisse verwendet. Ist das erzeugte Modell hinreichend korrekt, so kann es für den produktiven Einsatz genutzt werden.

Es ist hier im Allgemeinen eher unwahrscheinlich, dass das Modell 100 Prozent der Testdaten korrekt klassifiziert. Im produktiven Einsatz werden neue, nicht klassifizierte Elemente an das Modell gegeben und eingruppiert. Mit fortgeschrittenem Lebenszyklus und neuen Erkenntnissen in der Klassifizierung wird der Gesamtprozess wiederholt und ein neues, aktualisiertes Modell erzeugt. In der Realität wird man bereits für die initiale Bestimmung des Modells mehrere Iterationen des Prozesses durchlaufen müssen.

Abb. 1: Schematische Darstellung der Klassifizierung

Abb. 1: Schematische Darstellung der Klassifizierung

Wie kommt nun der Computer auf ein korrektes Modell, und welche Parameter der Eingangsdaten sollen eigentlich verwendet werden? Um diese Frage zu beantworten, ist noch etwas mehr Theorie notwendig. Tabelle 1 listet die Definition einiger Begriffe, die im Rahmen der Klassifizierung verwendet werden. Die Vorhersagevariablen (Predictor Variable) können dabei vier unterschiedliche Ausprägungen annehmen, die in Tabelle 2 dargestellt werden. Je nach Ausgangsszenario muss der entsprechende Typ gewählt werden. Die Typen haben gleichzeitig unterschiedliche Auswirkung auf die Performance der Klassifizierung, sodass es empfehlenswert ist, immer mit dem engsten Typraum zu arbeiten, das heißt, wenn man mit Categorical-Werten arbeiten kann, dann sollte man nicht Word- oder gar Text-like verwenden.

Tabelle 1: Begriffsdefinitionen für die Klassifizierung

Tabelle 1: Begriffsdefinitionen für die Klassifizierung

Tabelle 2: Typen der Vorhersagevariablen

Tabelle 2: Typen der Vorhersagevariablen

Vorbereiten des Trainings

Bevor man mit dem Erzeugen des Modells beginnen kann, müssen die Daten der Ausgangsbasis gesammelt werden. Damit die richtigen Daten erhoben werden, muss die Frage beantwortet werden: Welches Ergebnis möchte ich mit der Klassifizierung erreichen? Wie soll meine Zielvariable (Target Variable) aussehen?

Wie bereits erwähnt, muss die Zielvariable dabei einen überschaubaren Ergebnisraum besitzen. Innerhalb der gesammelten Daten muss gleichzeitig festgelegt werden, welche Eigenschaften für die Klassifizierung herangezogen werden sollen. Im E-Commerce-Kontext könnten hier das Klickverhalten, gekaufte oder betrachtete Produkte zur Auswertung herangezogen werden. Sind persönliche Informationen bekannt, so könnten auch diese verwendet werden. Oft wird der Inhalt einer relationalen Datenhaltung denormalisiert, sodass ein vollständiger Analysedatensatz als eine eigenständige Zeile vorhanden ist. Die Abbildung 2 zeigt einen Ausschnitt aus dem Datenmodell von IBM WebSphere Commerce und der daraus erzeugten Zeile zur Klassifizierung von Kunden über den Umsatz in Produktkategorien und Preisgruppen.

Abb. 2: Beispiel einer Zeile für Eingangsdaten

Abb. 2: Beispiel einer Zeile für Eingangsdaten

Die meiste Arbeit im Rahmen der Klassifizierung stellt die Definition geeigneter Eingangsvariablen dar. Um ein möglichst gutes Ergebnis zu erzielen, sollte man mit verschiedenen Varianten der Eingangsvariablen das Klassifizieren testen. Sind Daten und Variablen bekannt, so müssen diese Informationen in ein Format transformiert werden, das von Mahout verwendet werden kann. Je nach verwendeter Implementierung (z. B. MapReduce mit Hadoop oder Spark) sind hier unterschiedliche Varianten notwendig. Die einzelnen Schritte bis zum Trainieren sind in Abbildung 3 nochmals aufgeführt. Das Erzeugen der Sequenzdateien und Vektoren für die MapReduce-Implementierung kann über die Kommandozeile erfolgen (-i bedeutet Input und -o bedeutet Output):

MAHOUT_HOME/bin/mahout seqdirectory –i /eingangsdaten/ -o /ausgangsdaten_seq
MAHOUT_HOME/bin/mahout seq2sparse –i /ausgangsdaten_seq/part-m-00000 –o /ausgangsdaten_vector
Abb. 3: Bereitstellung der Trainingsdaten

Abb. 3: Bereitstellung der Trainingsdaten

Der erste Aufruf erzeugt aus einer Reihe von Textdokumenten die Sequenzinformationen. Der zweite Aufruf nutzt dann diese Daten, um daraus die Vektoren für die Klassifizierung zu erstellen. Die angegebene Seite beschreibt die Aufrufe und die möglichen Parameter im Detail. Das Aufteilen der Daten in ein Trainings- und ein Testdatenset kann ebenso über die Kommandozeile erfolgen. Im Beispiel werden 20 Prozent der Daten für das Testen verwendet. Die Trennung der Daten kann über entsprechende Kommandozeilenparameter weiter beeinflusst werden.

MAHOUT_HOME/bin/mahout seqdirectory -i /ausgangsdaten_vector /tfidf-vectors/ --trainingOutput /ausgangsdaten_train --testOutput /ausgangsdaten_test --randomSelectionPct 20

Das Erzeugen der Vektoren für die Klassifizierungsdaten kann auch programmatisch erfolgen. Listing 1 zeigt exemplarisch ein entsprechendes Beispiel. Das Interface FeatureVectorEncoder besitzt eine Reihe an Implementierungen, die die in Tabelle 2 genannten Typen entsprechend unterstützen. Jede Eingangsvariable (Feature) benötigt einen eigenen Encoder. Im Codebeispiel wird der ConstantValueEncoder verwendet, um die vordefinierten Werte des Enums aufzunehmen, und der StaticWordValueEncoder für den Nachnamen. Um die Encoder in der weiteren Verarbeitung unterscheiden zu können, wird im Konstruktor ein eindeutiger Name mitgegeben. Für den Vektor selbst stehen wieder die unterschiedlichen Varianten (siehe 2. Teil der Artikelreihe in Java Magazin 7.2015) zur Verfügung. Dem Encoder werden in der Methode addToVector dann der Wert, eine Gewichtung und die Instanz des Vektors mitgegeben. Der Wert wird dabei immer als die entsprechende String-Repräsentation übergeben.

private enum CValues {
  DOENER, PIZZA, CURRYWURST
}

private class CObject {
  CValues value = null;
  String lastName = null;
}

public void fillVector() {
  List<CObject> elements = getElements();

  FeatureVectorEncoder contEncoder = new ConstantValueEncoder("cvalue");
  FeatureVectorEncoder wordEncoder = new StaticWordValueEncoder("wvalue"); 

  Vector v = new DenseVector(2000);

  for (CObject cobject : liste) {
    contEncoder.addToVector(cobject.value.name(), 1, v);
    wordEncoder.addToVector(cobject.lastName, 1, v);
  }
}

Im Codebeispiel wurde genau ein Vektor für die Daten verwendet. In der Praxis müssen hier verschiedene Strategien angewendet werden. Mahout selbst bildet Werte in Vektoren als Zahlen (float) an den verschiedenen Positionen (Index) ab. Das heißt, die originalen textuellen Werte sind nicht mehr im Vektor enthalten, vielmehr wird von den Werten ein Hash gebildet, und dieser Hash wird im Vektor entsprechend abgelegt. Für jedes potenzielle Wort in den Eingangsdaten muss eine entsprechende Position im Vektor existieren.

Damit ein Wert im Vektor wiedergefunden werden kann und auch, um die initiale Größe des Vektors zu bestimmen, ist es erforderlich, ein Dictionary aufzubauen. Über dieses Dictionary wird festgelegt, wo sich welcher Wert im Vektor befindet. Soll nun Text als Eingangsvariable verwendet werden, so ist dieser zwar auch wie ein einzelnes Wort abbildbar, dies führt jedoch schnell zu Performanceherausforderungen. In diesem Fall sind andere Strategien anzuwenden. Es ist zum Beispiel möglich, nur die eindeutigen Wörter im Text zu zählen und mit einer Gewichtung zu versehen, oder auch aus dem Text die n Wörter auszuwählen, die die höchste oder niedrigste Wahrscheinlichkeit haben, zu einer Gruppe zu gehören (hier kann man weitere Informationen dazu finden). Eine zusätzliche Besonderheit bildet die Abbildung von Double-Werten über den ContinuousValueEncoder. Hier muss der übergebene Wert auf null gesetzt werden, und die Gewichtung repräsentiert die Double-Werte der Ausgangsdatenbasis.

Trainieren und Testen des Modells

Liegen die Ausgangsdaten im richtigen Format vor, kann das eigentliche Training gestartet werden. Für das Training stehen die in Tabelle 3 genannten Algorithmen zur Verfügung. Je nach Anwendungsszenario kann die entsprechende Implementierung gewählt werden. Für die Verwendung des Naive-Bayes-Algorithmus existiert wieder ein entsprechender Kommandozeilenaufruf:

MAHOUT_HOME/bin/mahout trainnb –i /ausgangsdaten_train –o /klassifizierungsmodell –li /labelindex –el
MAHOUT_HOME/bin/mahout testnb –i /ausgangsdaten_test –m /klassifizierungsmodell –l /labelindex –o /ergebnis

Die Funktion trainnb generiert das Modell der Klassifizierung. Neben dem Modell wird auch der Labelindex geschrieben, der als Eingangsdatenquelle für das Testen mitverwendet wird. Über den Parameter –l können die Labels, die in der Analyse Verwendung finden sollen, kommasepariert mitgegeben werden. So kann man hier ohne Neugenerierung der Vektoren mit verschiedenen Eingangsvariablen experimentieren. Das Testen des Modells erfolgt dann über die Funktion testnb. Achtung, der Labelindex wird beim Trainieren mit –li angegeben und beim Testen mit –l. Als Ergebnis des Tests wird auf der Konsole ausgegeben, wie viele Elemente korrekt oder nicht korrekt klassifiziert wurden.

Tabelle 3: Algorithmen für die Klassifizierung

Tabelle 3: Algorithmen für die Klassifizierung

Die Ergebnisse werden auch in einer Confusion-Matrix dargestellt. In dieser Matrix werden die korrekten und die falschen Ergebnisse einander gegenübergestellt. Abbildung 4 zeigt ein entsprechendes Beispiel, in dem drei Gruppen klassifiziert wurden. An der Klassifizierung für Currywurst sieht man, dass die Gruppen „Döner“ und „Pizza“ je einmal vorhergesagt wurden, obwohl die Testdaten „Currywurst“ als Klassifizierung enthielten. Achtmal wurde Currywurst korrekt vorhergesagt.

Abb. 4: Beispiel einer Confusion Matrix

Abb. 4: Beispiel einer Confusion Matrix

Ob ein Modell hinreichend korrekt ist, kann noch über weitere von Mahout unterstützte Metriken ermittelt werden. Die Klasse Auc zum Beispiel kann ein Modell prüfen, das binäre Informationen ermittelt. Der AUC-Algorithmus prüft, mit welcher Wahrscheinlichkeit die Klassifizierung ein Element mit einem bestimmten Feature korrekt ermittelt. Ein Wert von 1 bedeutet dabei, dass die Klassifizierung vollständig korrekt ist. Diesen Wert wird man in der Praxis nie erreichen, vielmehr sind Werte zwischen 0,7 und 0,9 eher als hinreichend zuverlässige Klassifizierungen zu finden. Wird der Wert 0 zurückgegeben, so liefert die Klassifizierung ein Ergebnis, das genau entgegengesetzt zum erwarteten Wert liegt.

Der letzte Schritt in der Bereitstellung der Klassifizierung ist die Überführung des Modells in den produktiven Einsatz. In den meisten Fällen wird dazu das Modell auf einem separaten Server ausgelagert, und von dort wird die Klassifizierung neuer Elemente getriggert. Je nach gewählten Eingangsvariablen (Anzahl, Typen etc.) können längere Laufzeiten bei der Klassifizierung auftreten. Hier müssen geeignete Prozesse für die Ausführung definiert und umgesetzt werden. Mahout beschreibt hier keine Vorgaben, wie im konkreten Fall der Produktiveinsatz aussehen sollte, vielmehr kann man sich an den Gegebenheiten des eingesetzten Betriebssystems bzw. der allgemeinen Betriebsparameter orientieren. Es ist zum Beispiel möglich, die Klassifizierung als Cron-Job aufzusetzen, der regelmäßig ein Eingangsverzeichnis prüft und das Ergebnis in eine Datenbank schreibt.

Weitere Algorithmen in MahoutNeben den drei vorgestellten Anwendungsszenarien bietet Mahout noch weitere Implementierungen von verschiedenen Algorithmen an. In der Gruppe der Algorithmen für Dimensionality Reduction findet man zum Beispiel die Singular Value Decomposition, Stochastic SVD oder auch die QR Decomposition. Diese Algorithmen versuchen die Komplexität (Dimensionen) der Eingangsgrößen zu reduzieren, sodass das Set der verfügbaren Features auf ein notwendiges Maß beschränkt wird. Über den Latent Dirichlet Allocation-Algorithmus können Dokumente analysiert werden. Zu Beginn werden dabei die Themen der Dokumente definiert und dann Ähnlichkeiten zwischen Dokumenten auf Basis der definierten Themen ermittelt. Die folgenden zusätzlichen Algorithmen sind außerdem verfügbar. Teilweise finden diese Algorithmen in anderen Algorithmen Anwendung, zum Beispiel kann die Lucene-Integration bei der Klassifizierung von Texten für die Bereitstellung der Vektoren verwendet werden.

  • RowSimilarityJob
  • ConcatMatrices
  • Collocations
  • Sparse TF-IDF Vectors from Text
  • XML Parsing
  • E-Mail Archive Parsing
  • Lucene-Integration
  • Evolutionary Processes

Schlussbemerkung

In diesem Beitrag haben Sie einen Einblick in die Möglichkeiten, theoretischen Grundlagen und notwendigen Implementierungen für ein Klassifizierungssystem erhalten. Ein komplettes Beispiel inklusive notwendiger Testdaten ist hier im Detail beschrieben. Beispieldaten bzw. Quelldateien liegen zusätzlich im examples-Verzeichnis der Mahout-Distribution.

Mit Mahout lässt sich eine Vielzahl an Algorithmen für selbstlernende Systeme ausführen. Besonders wenn eine große Menge an Eingangsdaten (Big Data) vorhanden sind, kann Mahout schnell seine Performancevorteile ausspielen. Alle drei vorgestellten Disziplinen (Empfehlungen, Clustern, Klassifizieren) sind mit Apache Mahout ausführbar und können als Basis für ein E-Commerce-Empfehlungssystem verwendet werden. Leider ist die Dokumentation an vielen Stellen sehr schwach bzw. gar nicht vorhanden, sodass man doch beträchtliche Zeit für die Suche von Informationen aufwenden muss. Bestehende Publikation zu Mahout sind leider teilweise veraltet und können auf die aktuelle Mahout-Version nicht immer angewendet werden. Gleichzeitig muss man aber sagen, dass Fragen in den Mailinglisten sehr schnell beantwortet werden. Wer etwas Zeit investiert und bereits einige Erfahrung in der Theorie der verschiedenen Algorithmen hat, findet in Mahout ein breites Spektrum an anwendbaren Implementierungen. Ein eigenes Empfehlungssystem mit Mahout als Grundlage kann somit realisiert werden.

Aufmacherbild: E-mailing Marketing campaign key via Shutterstock / Urheberrecht: Cienpies Design

Geschrieben von
Karsten Voigt

Karsten Voigt arbeitet für die T-Systems Multimedia Solutions als IT Architekt für Enterprise-E-Commerce-Lösungen. Im Rahmen von B2B-Projekten setzt er verschiedene Technologien zur effizienten Produktpräsentation und Optimierung des Kaufverhaltens ein.

David Broßeit

David Broßeit studiert Wirtschaftsinformatik an der Hochschule für Technik und Wirtschaft in Dresden. Im Rahmen eines Praxissemesters im Bereich E-Commerce hat er sich mit dem Themenkomplex Big Data und intelligente Produktempfehlungen auseinander gesetzt.

Kommentare

Hinterlasse einen Kommentar

Hinterlasse den ersten Kommentar!

avatar
400
  Subscribe  
Benachrichtige mich zu: