Wie alle überwachten Modelle für maschinelles Lernen werden Entscheidungsbäume darauf trainiert, eine Reihe von Trainingsbeispielen bestmöglich zu erklären. Das optimale Training eines Entscheidungsbaums ist ein NP-schweres Problem. Daher wird das Training im Allgemeinen mithilfe von Heuristiken durchgeführt – einem einfach zu erstellenden Lernalgorithmus, der einen nicht optimalen, aber annähernd optimalen Entscheidungsbaum liefert.
Die meisten Algorithmen, die zum Trainieren von Entscheidungsbäumen verwendet werden, arbeiten mit einer „Greedy Divide and Conquer“-Strategie. Der Algorithmus beginnt damit, einen einzelnen Knoten (den Stamm) zu erstellen und den Entscheidungsbaum rekursiv und gierig zu vergrößern.
An jedem Knoten werden alle möglichen Bedingungen ausgewertet und bewertet. Der Algorithmus wählt die „beste“ Bedingung aus, also die Bedingung mit dem höchsten Wert. Für den Moment reicht es aus, wenn Sie wissen, dass der Wert ein Messwert ist, der mit der Aufgabe korreliert, und dass Bedingungen ausgewählt werden, um diesen Messwert zu maximieren.
Im Dataset Palmer Pinguins (das später in diesem Kurs für Codebeispiele verwendet wird) haben die meisten Adelie- und Zügelpinguine beispielsweise einen Schnabel von mehr als 16 mm. Die meisten Eselspinguine haben dagegen kleinere Schnabel. Daher trifft die Bedingung bill_length_mm ≥ 16 fast perfekte Vorhersagen für Gentoo-Pinguine, kann aber nicht zwischen Adelies und Zügelpinguine unterscheiden. Diese Bedingung wird wahrscheinlich vom Algorithmus ausgewählt.
Abbildung 7. Der erste Schritt beim Baumzüchten.
Der Algorithmus wiederholt dann rekursiv und unabhängig auf beiden untergeordneten Knoten. Wenn keine Bedingungen gefunden werden, die die Bedingungen erfüllen, wird der Knoten zu einem Blatt. Die Blattvorhersage wird in den Beispielen als der repräsentativste Labelwert bestimmt.
Der Algorithmus sieht so aus:
def train_decision_tree(training_examples):
root = create_root() # Create a decision tree with a single empty root.
grow_tree(root, training_examples) # Grow the root node.
return root
def grow_tree(node, examples):
condition = find_best_condition(examples) # Find the best condition.
if condition is None:
# No satisfying conditions were found, therefore the grow of the branch stops.
set_leaf_prediction(node, examples)
return
# Create two childrens for the node.
positive_child, negative_child = split_node(node, condition)
# List the training examples used by each children.
negative_examples = [example for example in examples if not condition(example)]
positive_examples = [example for example in examples if condition(example)]
# Continue the growth of the children.
grow_tree(negative_child, negative_examples)
grow_tree(positive_child, positive_examples)
Sehen wir uns die Schritte zum Trainieren eines bestimmten Entscheidungsbaums einmal genauer an.
Schritt 1:Stamm erstellen:
Schritt 2: Wachstumsknoten 1. Die Bedingung „x1 ≥ 1“ wurde gefunden. Es werden zwei untergeordnete Knoten erstellt:
Schritt 3: Wachstumsknoten 2 erhöhen. Es wurden keine passenden Bedingungen gefunden. Machen Sie den Knoten also zu einem Blatt:
Schritt 4: Wachstumsknoten 3 erhöhen. Die Bedingung „x2 ≥ 0,5“ wurde gefunden. Es werden zwei untergeordnete Knoten erstellt.
Es gibt auch andere Methoden, Entscheidungsbäume zu pflanzen. Eine beliebte Alternative besteht darin, Knoten global zu optimieren, anstatt eine Divide-and-Conquer-Strategie zu verwenden.
growing_strategy="BEST_FIRST_GLOBAL" aktivieren.
Weitere Informationen finden Sie in der
Dokumentation.
Abhängig von der Anzahl und Art der Eingabemerkmale kann die Anzahl der möglichen Bedingungen für einen bestimmten Knoten riesig und in der Regel unendlich sein. Beispiel: Bei der Schwellenwertbedingung $\mathrm{feature}_i \geq t$ ist die Kombination aller möglichen Schwellenwerte für $t \in \mathbb{R}$ unendlich.
Die Routine, die zum Ermitteln der besten Bedingung verantwortlich ist, wird Splitter genannt. Da viele mögliche Bedingungen getestet werden müssen, sind Splitter der Engpass beim Trainieren eines Entscheidungsbaums.
Der vom Splitter maximierte Wert hängt von der Aufgabe ab. Beispiel:
- Für die Klassifizierung werden in der Regel Informationsgewinn und Gini (beide weiter unten behandelt) verwendet.
- Der mittlere quadratische Fehler wird häufig für Regressionen verwendet.
Es gibt viele Aufteilungsalgorithmen, die jeweils unterschiedliche Unterstützungsbereiche für Folgendes bieten:
- Der Typ der Merkmale, z. B. numerisch, kategorial, Text
- Die Aufgabe; zum Beispiel binäre Klassifizierung, mehrklassige Klassifizierung, Regression
- Der Typ der Bedingung, z. B. Schwellenwertbedingung, In-Set-Bedingung, Schrägbedingung
- Die Regularisierungskriterien, z. B. exakte oder ungefähre Splitter für Schwellenwertbedingungen
Darüber hinaus gibt es gleichwertige Splitter-Varianten mit unterschiedlichen Kompromissen in Bezug auf Arbeitsspeichernutzung, CPU-Auslastung, Berechnungsverteilung usw.