Ein Gastbeitrag von Christoph Henkelmann (Firmenseite, privates Blog).
Redaktion: AP

Nachdem wir im ersten Teil (Data-Mining 101, Data-Mining-Arten, Lernarten) die wichtigsten Grundbegriffe geklärt und die Vorgeschichte dieses Postings kurz beleuchtet haben, schauen wir uns heute Data Mining an einem konkreten Beispiel an: Es geht um die Filterung von E-Mails.

Im dritten Teil wollen wir dann – soviel sei schon verraten – kritische Gedanken zur Zuverlässigkeit maschinenbasierter Entscheidungsysteme formulieren, wobei ein (hoffentlich nicht zu makabres) Gedankenspiel rund ums „Aussieben“ verdächtiger Personen eine zentrale Rolle spielen wird.

Zunächst aber:

Teil 2: Hallo Wortvektor, hallo Spam!

Preprocessing

Wie kann nun ein Algorithmus aus einer Liste von Einkäufen feststellen, welches Buch uns als nächstes interessieren könnte? Und aus dem Text einer Nachricht, ob es sich um nette Geburtstagsgrüße oder nervige Werbung für Potenzmittelchen handelt?

Alle zuvor beschriebenen Analyseverfahren brauchen Daten in einer ganz speziellen Form, um etwas damit anfangen zu können. Das Preprocessing ist der wohl wichtigste Schritt beim Data-Mining und für die Qualität der Ergebnisse absolut entscheidend.

Betrachten wir anhand eines ganz einfachen Beispiels, wie Daten präpariert werden müssen, damit man sie an einen Algorithmus „verfüttern“ kann:

„Das ist das Haus vom Nikolaus.“
„Das Haus der Hexe ist aus Lebkuchen.“

Wir nehmen nun diese beiden Sätze, machen aus den Großbuchstaben Kleinbuchstaben und zerlegen den Text in „Tokens“ – das sind separate Abschnitte, meist die durch Leerzeichen getrennten Textteile:

[„das“,“ist“,“das“,“haus“,“vom“,“nikolaus“, „.“]

Je nach Anwendungsfall werden vorher noch Satzzeichen und Ziffern entfernt.

Möchten wir eine semantische Textverarbeitung haben, also Inhalte und Kontext bestimmen („Wem gehört das Haus?“), sind wir jetzt fertig mit Preprocessing. Die Kette aus Wörtern kann übergeben werden – wobei das eigentliche Lernen bei der semantischen Analyse umso schwerer ist.

Viele Verfahren benötigen die Daten jedoch in einer Form, die noch deutlich weiter „heruntergekocht“ ist. Wir bestimmen deshalb aus der vorliegenden Gesamttextemenge alle überhaupt vorkommenden Wörter: das sogenannte Dictionary. Die Reihenfolge und Beziehung der Wörter untereinander geht dabei natürlich komplett verloren. Man spricht deshalb auch von einer Bag of Words. In unserem Beispiel sieht sie wie folgt aus:

{„aus“, „das“, „der“, „haus“, „hexe“, „ist“, „lebkuchen“, „nikolaus“, „vom“}

In ernsthaften Anwendungsfällen ist eine solche Wortsammlung natürlich oft mehrere Tausend Einträge lang.

Nun wird ein sogenannter „Wortvektor“ erstellt, der kodiert, welche Wörter aus unserer Bag of Words wie oft vorhanden sind:

„Das ist das Haus vom Nikolaus.“ → [0, 2, 0, 1, 0, 1, 0, 1, 1]
„Das Haus der Hexe ist aus Lebkuchen.“ → [1, 1, 1, 1, 1, 1, 1, 0, 0]

Zur Erläuterung: Das erste Wort der Bag, „aus“, kommt im ersten Text 0x vor, also steht an Position 1 des Vektors eine 0. Das zweite Wort der Bag, „das“, kommt im ersten Text 2x vor, also steht an Position 2 des Vektors eine 2. Usw.

Weitere Möglichkeiten, Text vorzuverarbeiten sind z.B.:

Buchstaben-n-Gramme: [„das“, „as „, „s i“, “ is“, „ist“, „st „, „t d“, “ da“, „das“, … ], also ein „Fenster“ fester Breite, das über den Text geschoben wird und immer ein Stück Text „einrahmt“

Wort-n-Gramme [(„das“, „ist“, „das“), („ist“, „das“, „haus“), („das“, „haus“, „vom“), („haus“,
„vom“, „nikolaus“), …]

Annotation [(„das“, ARTIKEL), („ist“, VERB), („das“, ARTIKEL), („haus“, NOMEN)], man fügt also jedem Token zusätzliche Informationen hinzu. Diese Informationen können manuell hinzugefügt werden (was sehr zeitaufwändig ist), aus einer zusätzlichen Datenquelle kommen – oder von einem weiteren Machine Learning Verfahren. Man würde quasi Algorithmen „in Reihe schalten“, so dass der Output des einen der Input des nächsten ist.

Dies ist nur ein kurzer, unvollständiger Blick auf das Preprocessing für Textdaten. Für andere Daten gibt es eine Vielzahl anderer Möglichkeiten, Input für Algorithmen zu erstellen: Im Bereich Audio/Video sind das z.B. Frequenzanalysen (DCT, Wavelets), Gradienten, Filter aller Art und Histogramme, im Bereich Datenbanken Feature-Vektoren aus deren Inhalten oder Graphen.

Oft besteht das Ziel einfach darin, einen Vektor (eine Liste immer gleicher Länge) aus Zahlen zu gewinnen – damit können sehr viele Verfahren umgehen.

Weiterverabeitung der Daten

Nun, da wir eine grobe Vorstellung davon haben, worauf Data-Mining-Verfahren zurückgreifen (nämlich nicht wirklich auf unserere Einkaufsliste oder einen E-Mail-Text, sondern auf speziell präparierte Vektoren aus Zahlen), können wir uns der Frage widmen, wie die maschinengerecht vorbereiteten Daten weiterverarbeitet werden – und wie wir ein konrektes Ergebnis erhalten.

Das klassische Beispiel: Spam-Erkennung

Spam-Erkennung ist quasi das „Hello World“-Programm des Data Mining. Zunächst benötigt man E-Mail-Texte. Viele E-Mail-Texte. So viele wie möglich. Ausgehend von dieser initialen Auswahl, oft auch Lernkorpus genannt, trainieren wir unser Verfahren.

Das einfachste (aber immer noch sehr wirkungsvolle) heißt Naive Bayes. Das naiv ist wörtlich zu verstehen: dieser Algorithmus macht eine „naive“ statistische Annahme, die eigentlich nicht korrekt ist, aber in der Praxis dennoch beeindruckend gut funktioniert.

Wir beginnen wie im Nikolausbeispiel, erzeugen also ein Dictionary für alle Wörter und bilden Wortvektoren.

Anschließend wird jeder Wortvektor in eine Formel gegeben, die mit jedem weiteren Beispiel einen Wahrscheinlichkeitswert für die im Wortvektor vorkommenden Wörter (d.h. die Wörter, die einen Eintrag ungleich 0 haben) aktualisiert. In diese Berechnung fließt ein, ob die E-Mail Spam ist oder nicht.

Nachdem dies für alle Beispiele geschehen ist, können wir mit den gelernten Wahrscheinlichkeitswerten unbekannte Mails klassifizieren, indem wir dafür ebenfalls einen Wortvektor bauen bzw. bauen lassen (Wörter, die in unserem gelernten Dictionary nicht vorkommen, werden dabei ignoriert).

Nun wird aus diesem Wortvektor mit Hilfe einer anderen Formel und den gelernten Wahrscheinlichkeitswerten eine Gesamtwahrscheinlichkeit berechnet, die uns sagt,
ob eine bestimmte Mail Spam ist oder nicht. Danach liegt es am Anwender, zu entscheiden, ab welchem Gesamtwahrscheinlichkeitswert unser Spam-Filter „zuschlagen“ soll.

Wir halten fest:

Lernen
1. Dictionary aus allen Wörtern im Lernkorpus erstellen
2. Wortvektor für alle Mails im Lernkorpus erstellen
3. Wortvektor + Info (Spam oder nicht?) in eine Formel geben

Klassifizieren
4. Wortvektor aus zu klassifizierender Mail erstellen
5. Wortvektor mit Lernergebnis in eine andere Formel stecken
6. Feststellen, ob der Wahrscheinlichkeitswert größer als Schwellenwert x ist (dann ist es – vermutlich – Spam)

So weit, so gut. Beim nächsten Mal dann: Precision, Recall und „auffällige“ Bürger.