Liebe Freunde der Sicherheit,

wenn man Urheber von Bekennerschreiben identifizieren oder feststellen will, ob die Beiträge in einem Internetforum rechtsextreme Tendenzen haben, dann handelt es sich aus mathematisch-informatischer Perspektive um Klassifizierungsprobleme. Man nimmt im ersten Fall eine Menge von Texten, von denen man weiß, wer die Autoren sind. Diese Dokumente werden dann als numerische Vektoren dargestellt, die die Ausprägung möglicher relevanter Merkmale dieser Texte abbilden. Dann wendet man Methoden des maschinellen Lernens an, um einen Klassifikator zu finden, der die Texte, die zu unterschiedlichen Klassen gehören, voneinander unterscheidet. Dieser Klassifikator liefert uns dann einen Hinweise darauf, welcher Klasse sich der Urheber eines Bekennerschreibens mit einer gewissen Wahrscheinlichkeit zuordnen lässt.

Natürlich sind die Ergebnisse des Lernverfahrens nur so gut, wie die Entscheidung, welche Merkmale der Texte für die Klassifizierung relevant sein können. Einige der am häufigsten für die Autorenidentifizierung benutzten linguistischen Feature habe ich in einem früheren Post zusammengestellt. Mir geht es aber hier um die Grundidee des maschinellen Lernens: Man benutzt eine bereits klassifizierte Datenmenge, um aus ihr jene Merkmale zu extrahieren, die für die Klassifizierung unbekannter Daten relevant sind. Eine Möglichkeit, aus Daten Regeln für die Klassifizierung abzuleiten, ist das Entscheidungsbaumverfahren.

Entscheidungsbäume

Beim Entscheidungsbaumverfahren wird eine Datensatz Schritt für Schritt in Unterklassen geteilt. Diese Teilungen der Gesamtmenge in immer kleinere Teilmengen erfolgt anhand eines Sets von Merkmalen, von denen wir vermuten, dass sie für die Einteilung relevant sind.

Nun wollen wir den Datensatz in zwei Unterklassen teilen, die in sich möglichst homogen sind und sich daher auch möglichst stark von einander unterscheiden. Meist wird hier das Kriterium des Informationsgehaltes (Entropie) angewendet. Die Trennkriterien sind so zu wählen, dass die entstehenden Unterklassen im Hinblick auf eine resultierende Klassenverteilung möglichst homogen sind. Dieses Verfahren wendet man nun auch auf jede der neu berechneten Unterklassen an. Ist der Informationsgewinn durch eine weitere Teilung einer Unterklasse sehr gering, dann beendet man das Aufsplitten des Datensatzes an dieser Stelle.

Nach und nach wächst so ein „Baum“, die Bezeichnung eines gerichteten Graphen mit einem Wurzelknoten. Knoten markieren den Vergleich hinsichtlich eines Attributs, Kanten repräsentieren die verschiedenen Ausprägungen des Attributs, Blätter bezeichnen die Klasse. Pfade zu den Blattknoten stellen „Regeln“ dar, die auf künftige Klassifizerungsaufgaben angewendet werden können.

Vornamen von Neonazis in Abhängigkeit von Wohnort und Alter

Nehmen wir ein unverfängliches Beispiel: Wir wollen wissen, welche Namen Neonazis in Abhängigkeit von Alter und Region typischerweise haben. Hierfür nehmen wir einen Datensatz, der auf der Nazileaks-Plattform publiziert wurde und Informationen zu Wohnort und Geburtsdatum enthält. Damit das Ergebnis einigermaßen übersichtlich bleibt, operationalisieren wir die Variable Region über den Postleitzahlenbereich. Um genau zu sein: wir definieren die erste Ziffer der Postleitzahl als relevantes Attribut für die Klassifizierung. Als zweites relevantes Attribut bestimmen wir das Alter.

Der berechnete Entscheidungsbaum zeigt, dass zunächst die Variable Alter mit dem Merkmal „jünger als 36“ vs. „36 Jahre und älter“ den Datensatz am besten in zwei Klassen trennt. Die beiden berechneten Subklassen werden beide wiederum durch das Attribut Alter in zwei Subklassen geteilt, ehe das Attribut PLZ-Bereich zu Spaltungen führt. Eine sich aus dem Entscheidungsbaum ableitbare Regel wäre: Neonazis, die über 44 Jahre alt sind und in den PLZ-Bereich 2, 3, 5 oder 7 wohnen, heißen Erik. Allerdings ist die Fehlerquote in den berechneten Klassen so hoch, dass eigentlich keine belastbaren Aussagen möglich sind. Wahrscheinlich haben wir nicht die richtigen Variablen in das Modell eingefügt.

Zwar ist der Baum in dieser Form gerade noch lesbar, aber dennoch überkomplex. Es gibt viele Endknoten, die nur wenige Objekte enthalten. Um die Ergebnisse besser generalisieren zu können, werden die Bäume „beschnitten“. Dieses Verfahren nennt man „Pruning“. Für den obigen Baum wurde schon ein Pre-Pruning vorgenommen: Die Anzahl der Verzweigungen wurde auf 7 begrenzt. Weil das immer noch recht viel ist, kann man auch ein Post-Pruning durchführen. Dabei fallen Knoten wegen oder werden durch ein Blatt ersetzt, die für die Relevanz für die Klassifizierung keine (oder nur geringe) Relevanz besitzen. Der beschnittene Baum hat dann z.B. diese Form:

Es gibt unterschiedliche Algorithmen zur Berechnung von Entscheidungsbäumen. Hier wurde mit dem CART-Verfahren gerechnet, bei dem der Datensatz bei einem Knoten jeweils binär gesplittet wird. Mein Kollege Noah Bubenhofer, von dem ich das Namensbeispiel übernommen habe, rechnet mit dem C4.5-Algorithmus.

Was kann man nun mit so einem Baum anfangen? Mit diesem speziellen Baum nicht viel. Die Fehlerquote ist zu hoch. Wäre sie niedriger, könnte man die Regeln wie folgt benutzen: Wenn wir den Vornamen einer Person kennen und wissen, dass diese Person ein Neonazi ist, dann könnten wir mit einer gewissen Wahrscheinlichkeit auf Alter und PLZ-Bereich des Wohnortes schließen.

Postleitzahlbereiche in der BRD (Quelle: Wikipedia, Stefan Kühn, CC0 1.0)

Natürlich könnten wir nun nicht einfach behaupten, dass Menschen, die André heißen, älter als 31 Jahre alt sind und aus dem PLZ-Bereich 0 kommen, mit einer bestimmten Wahrscheinlichkeit Neonazis sind. Um solche Aussagen zu ermöglichen hätten wir einen Datensatz gebraucht, der auch die Daten von nicht-Neonazis enthielte. Es könnte ja schließlich auch sein, dass Noenazis genause heißen wie der Rest der Bevölkerung und der obige Baum nur die regionale und altersspezifische Verteilung in Deutschland abbildet. Macht euch also keine Sorgen, wenn ihr Erik heißt und jünger als 22 Jahre alt seid: Wir wissen nicht, welche Gesinnung ihr habt. Noch nicht…