Entscheidungsbaum: Gini-Splits

Ein Entscheidungsbaum unterteilt den Merkmalsraum durch eine Folge achsenparalleler binärer Splits, die jeweils so gewählt werden, dass ein Knotenverunreinigungsmaß maximal reduziert wird. Die Gini-Verunreinigung an einem Knoten beträgt 1 minus die Summe der quadrierten Klassenwahrscheinlichkeiten: Bei einem reinen Knoten ist sie 0,0, bei einem maximal gemischten Zwei-Klassen-Knoten 0,5. Der CART-Algorithmus bewertet jeden möglichen Schwellenwert für jedes Merkmal und wählt denjenigen, der den gewichteten Durchschnitt des Gini-Wertes der beiden Kindknoten minimiert, wobei die Gewichte dem Anteil der Trainingsbeispiele in jedem Kindknoten entsprechen. Ein Baum der Tiefe eins (ein Decision Stump) führt einen einzigen binären Schnitt durch; tiefere Bäume unterteilen den Raum in immer feinere rechteckige Regionen. Bei jedem Split entspricht der Informationsgewinn dem Gini-Wert des Elternknotens minus dem gewichteten Gini-Wert der Kindknoten und misst, wie viel Unsicherheit aufgelöst wird.

Ohne Einschränkungen wächst ein Baum, bis jedes Blatt rein ist, was den Trainingsdatensatz perfekt auswendig lernt, auf neuen Daten jedoch zu starken Fehlern führt: das ist Überanpassung beim Entscheidungsbaum. Die wichtigsten Gegenmaßnahmen sind Vorwärtsbeschneidung (Pre-Pruning: max_depth begrenzen, Mindestanzahl von Beispielen für einen Split oder ein Blatt vorschreiben) und nachträgliches Beschneiden (Post-Pruning: vollständig wachsen lassen, dann Blätter entfernen, die den Validierungsverlust auf einem Haltedatensatz nicht verbessern, gewichtet durch den Komplexitätsparameter Alpha wie bei der Kostenkomplexit-Beschneidung). Ein flacher Baum mit max_depth von 3 bis 5 ist interpretierbar und kann als Flussdiagramm dargestellt werden; seine Entscheidungen sind menschlich nachprüfbar, was ihn zu einem der wenigen echten White-Box-Klassifikatoren macht. Entscheidungsbäume sind außerdem der Basislerner für Random Forests (gebündelte, vollständig gewachsene Bäume) und Gradient Boosting (flache Bäume, die sequenziell auf Residuen angepasst werden), wobei das Ensemble-Verfahren die geringe Verzerrung wiederherstellt und gleichzeitig die Varianz kontrolliert.