Entscheidungsbäume: zwanzig Fragen an die Daten

Kennst du das Spiel „Wer bin ich?“ mit zwanzig Fragen? „Lebt es?“ „Ist es größer als eine Katze?“ Gute Spieler fragen nicht zufällig; sie stellen die Frage, die die verbleibenden Möglichkeiten ungefähr halbiert. Ein Entscheidungsbaum ist ein Modell, das dieses Spiel mit Daten spielt – und weil seine Fragen in Klartext formuliert sind, gehört er zu den wenigen Modellen, die man wie ein Flussdiagramm lesen kann. Probier es zuerst selbst aus, bevor du die Erklärung liest.

Probier es aus

• Stell den Regler für die maximale Tiefe auf 1. Der Baum darf nur eine Frage stellen. Lies sie in der Liste der Teilungen ab: Welches Merkmal hielt der Algorithmus für das aussagekräftigste?
• Erhöhe die maximale Tiefe Schritt für Schritt. Beobachte, wie die Trainingsgenauigkeit steigt, und vergleiche sie bei jeder Tiefe mit der Testgenauigkeit.
• Schieb den Regler für die maximale Tiefe auf das Maximum. Ist die Trainingsgenauigkeit nahezu perfekt? Was ist mit der Testgenauigkeit passiert?
• Finde die Tiefe mit der besten Testgenauigkeit und lies dort die obersten Teilungen ab. Könntest du diesen Baum jemandem in zwei Sätzen erklären?

Die Idee in einfachen Worten

Ein Entscheidungsbaum sagt vorher, indem er eine Folge von Ja-Nein-Fragen zu den Merkmalen stellt: „Ist der Passagier jünger als ein bestimmtes Alter?“, „Ist er in der ersten Klasse gereist?“. Jede Antwort schickt das Beispiel einen Ast hinunter, und die nächste Frage hängt von den bisherigen Antworten ab. Am Ende jedes Pfads sitzt ein Blatt mit einer Vorhersage – meist das häufigste Label unter den Trainingsbeispielen, die dort gelandet sind.

In dieser Lektion nutzen wir Daten zu 891 Passagieren der Titanic, von denen 342 überlebten. Zu den Merkmalen gehören die Ticketklasse, das Geschlecht, das Alter, die Zahl der Angehörigen an Bord und der bezahlte Fahrpreis. Der Baum lernt, welche Fragen zu diesen Merkmalen die Überlebenden am besten von den anderen trennen.

Denk an eine Pflegekraft in der Notaufnahme, die die Ersteinschätzung (Triage) macht. Sie berechnet keine gewichtete Summe; sie folgt einer kurzen Kette von Fragen – Atmung? Blutung? Bewusstsein? –, und jede grenzt ein, was zu tun ist. Ein Baum ist diese Kette, nur aus Daten gelernt statt von Ärzten aufgeschrieben.

Warum es funktioniert

Der Baum wird von oben aufgebaut, eine Frage nach der anderen. Bei jedem Schritt probiert der Algorithmus jedes Merkmal und jeden möglichen Grenzwert aus und fragt: Welche Frage teilt diese Gruppe in zwei Gruppen, die möglichst rein sind, also jeweils überwiegend ein Label enthalten? Ein beliebtes Maß für die Unreinheit ist der Gini-Index einer Gruppe:

Gini = 1 − Σ pₖ²

Dabei ist pₖ der Anteil des Labels k in der Gruppe. Eine Gruppe, in der alle dasselbe Label haben, hat Gini 0; eine Gruppe, die je zur Hälfte aus zwei Labels besteht, hat Gini 0,5, den schlechtesten möglichen Wert bei zwei Klassen. Der Algorithmus wählt die Frage, die die durchschnittliche Unreinheit am stärksten senkt, und wiederholt das Verfahren dann getrennt in jedem Ast. Diese gierige (greedy) Schritt-für-Schritt-Suche garantiert nicht den bestmöglichen Baum, ist aber schnell und funktioniert in der Praxis gut.

Sich selbst überlassen, teilt der Baum so lange weiter, bis jedes Blatt rein ist – selbst wenn ein Blatt nur einen einzigen Passagier enthält. Dann hat er die Trainingsdaten samt Rauschen auswendig gelernt: die Überanpassung aus Lektion 7 in neuem Gewand. Die wichtigste Stellschraube ist die maximale Tiefe, also die Zahl der Fragen, die entlang eines Pfads erlaubt sind. Ein flacher Baum ist leicht zu lesen, übersieht aber vielleicht echte Muster; ein tiefer Baum trifft die Trainingsdaten fast perfekt und verallgemeinert schlechter. Die Kreuzvalidierung aus Lektion 8 ist der ehrliche Weg, die Tiefe zu wählen.

Häufiger Fehler

Eine Teilung erklärt keine Ursache. Der Baum fragt nach dem Merkmal, das die Labels in diesen Daten am besten trennt, und das kann ein Stellvertreter für etwas anderes sein: Ticketklasse und Fahrpreis hängen zusammen, und beide sagen etwas darüber, wo auf dem Schiff ein Passagier schlief. Der zweite Fehler ist, einem tiefen Baum zu trauen, weil seine Regeln so präzise aussehen. Eine Regel wie „Alter zwischen 31,5 und 32,5 und Fahrpreis über einem bestimmten Wert“ beschreibt meist ein oder zwei Passagiere, kein Muster. Kleine Änderungen in den Daten können außerdem die erste Teilung und damit den ganzen Baum verändern, was einzelne Bäume instabil macht.

Diese Instabilität ist eine Schwäche, lässt sich aber in eine Stärke verwandeln. In der nächsten Lektion lassen wir viele verschiedene Bäume wachsen und abstimmen.

import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier

df = pd.read_csv("data/raw/titanic.csv")
X = pd.DataFrame({"female": (df["sex"] == "female").astype(int)}).join(df[["pclass", "age", "sibsp", "parch", "fare"]])
Xtr, Xte, ytr, yte = train_test_split(X, df["survived"], test_size=0.3, stratify=df["survived"], random_state=1)
Xtr, Xte = Xtr.fillna({"age": Xtr["age"].median()}), Xte.fillna({"age": Xtr["age"].median()})  # Median der Trainingsdaten für beide
print(f"passengers {len(df)}, survived {df['survived'].sum()}")
for d in (1, 3, 20):
    t = DecisionTreeClassifier(max_depth=d, random_state=0).fit(Xtr, ytr)
    print(f"depth {d:2d}: train {t.score(Xtr, ytr):.3f}, test {t.score(Xte, yte):.3f}, leaves {t.get_n_leaves()}")

passengers 891, survived 342
depth  1: train 0.780, test 0.802, leaves 2
depth  3: train 0.833, test 0.802, leaves 8
depth 20: train 0.986, test 0.780, leaves 141