Wie alle überwachten Modelle für maschinelles Lernen werden Entscheidungsbäume so trainiert, dass sie eine Reihe von Trainingsbeispielen am besten erklären. Die optimale Schulung eines Entscheidungsbaums ist ein NP-hartes Problem. Daher wird das Training in der Regel mithilfe von Heuristiken durchgeführt – einem einfach zu erstellenden Lernalgorithmus, der einen nicht optimalen, aber nahezu optimalen Entscheidungsbaum liefert.
Die meisten Algorithmen, die zum Trainieren von Entscheidungsbäumen verwendet werden, arbeiten mit einer gierigen Strategie des Teilens und Eroberns. Der Algorithmus beginnt mit dem Erstellen eines einzelnen Knotens (der Wurzel) und erweitert den Entscheidungsbaum rekursiv und gierig.
An jedem Knoten werden alle möglichen Bedingungen ausgewertet und bewertet. Der Algorithmus wählt die „beste“ Bedingung aus, d. h. die Bedingung mit der höchsten Punktzahl. Fürs Erste genügt es, zu wissen, dass der Wert ein Messwert ist, der mit der Aufgabe in Verbindung steht, und dass Bedingungen ausgewählt werden, um diesen Messwert zu maximieren.
Im Dataset Palmer Penguins (das später in diesem Kurs für Codebeispiele verwendet wird) haben beispielsweise die meisten Adeliepinguine und Zügelpinguinen einen Schnabel, der länger als 16 mm ist, während die meisten Gentoo-Pinguine kleinere Schnäbel haben. Daher liefert die Bedingung bill_length_mm ≥ 16 fast perfekte Vorhersagen für Zügelpinguine, kann aber nicht zwischen Adelie- und Zügelpinguinen unterscheiden. Der Algorithmus wird diese Bedingung wahrscheinlich auswählen.
Abbildung 7. Der erste Schritt zum Wachsen eines Baumes.
Der Algorithmus wird dann rekursiv und unabhängig auf beide untergeordneten Knoten angewendet. Wenn keine zufriedenstellenden Bedingungen gefunden werden, wird der Knoten zu einem Endknoten. Die Blattvorhersage wird als der repräsentativste Labelwert in den Beispielen 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 genauer an.
Schritt 1:Stamm erstellen:
Schritt 2:Knoten 1 vergrößern. Die Bedingung „x1 ≥ 1“ wurde gefunden. Es werden zwei untergeordnete Knoten erstellt:
Schritt 3:Knoten 2 vergrößern. Es wurden keine Bedingungen gefunden, die erfüllt sind. Machen Sie also aus dem Knoten ein Blatt:
Schritt 4:Knoten 3 vergrößern. Die Bedingung „x2 ≥ 0,5“ wurde gefunden. Es werden zwei untergeordnete Knoten erstellt.
Es gibt noch andere Methoden, um Entscheidungsbäume zu erweitern. Eine beliebte Alternative besteht darin, Knoten global zu optimieren, anstatt eine Strategie des Teilens und Eroberns zu verwenden.
growing_strategy="BEST_FIRST_GLOBAL" aktivieren.
Weitere Informationen finden Sie in der Dokumentation.
Je nach Anzahl und Typ der Eingabefeatures kann die Anzahl der möglichen Bedingungen für einen bestimmten Knoten sehr groß, in der Regel sogar unendlich sein. Bei einer Grenzwertbedingung wie „Attribut i ≥ t“ ist beispielsweise die Kombination aller möglichen Grenzwertwerte für t ∈ ℝ unendlich.
Die Routine, die für die Suche nach der besten Bedingung verantwortlich ist, wird als Splitter bezeichnet. Da viele mögliche Bedingungen getestet werden müssen, sind Verzweigungen das Nadelöhr beim Trainieren eines Entscheidungsbaums.
Welcher Wert durch den Splitter maximiert wird, hängt von der Aufgabe ab. Beispiel:
- Der Informationsgewinn und der Gini-Koeffizient (beide werden später behandelt) werden häufig für die Klassifizierung verwendet.
- Die mittlere quadratische Abweichung wird häufig für die Regression verwendet.
Es gibt viele Trennalgorithmen, die jeweils unterschiedliche Unterstützung für Folgendes bieten:
- Der Typ der Features, z. B. numerisch, kategorisch, Text
- Die Aufgabe, z. B. binäre Klassifizierung, mehrklassige Klassifizierung, Regression
- Der Bedingungstyp, z. B. Schwellenwertbedingung, Bedingung im Satz, schräge Bedingung
- Die Kriterien für die Regularisierung, z. B. genaue oder gerundete Trennpunkte für Grenzwertbedingungen
Außerdem gibt es gleichwertige Splittervarianten mit unterschiedlichen Kompromissen in Bezug auf Arbeitsspeichernutzung, CPU-Auslastung, Berechnungsverteilung usw.