Aufbau Entscheidungsbäume aus dem Kratzen: Ein Anfänger Coding Tutorial

Entscheidungsbäume sind einer der intuitivsten und am weitesten verbreiteten Algorithmen für maschinelles Lernen sowohl für die Klassifizierung als auch für die Regression. Sie arbeiten, indem sie Daten in Zweige auf der Grundlage von Merkmalswerten aufteilen und die Art und Weise nachahmen, wie Menschen Entscheidungen treffen. Während Bibliotheken wie scikit-learn das Erstellen von Entscheidungsbäumen trivial machen, ist die Implementierung eines von Grund auf eine hervorragende Möglichkeit für Anfänger, das Innenleben des Algorithmus zu erfassen. Dieses Tutorial führt Sie durch die Theorie und den Code, so dass Sie Ihren eigenen Entscheidungsbaum von Grund auf aufbauen können.

Was ist ein Decision Tree?

Ein Entscheidungsbaum ist eine Flussdiagramm-ähnliche Struktur, bei der jeder interne Knoten einen Test für ein Feature darstellt (z. B. "Ist Alter > 30?"), jeder Zweig das Ergebnis dieses Tests darstellt und jeder Blattknoten ein Klassenlabel oder einen kontinuierlichen Wert hat. Ziel ist es, ein Modell zu erstellen, das eine Zielvariable vorhersagt, indem einfache Entscheidungsregeln aus den Datenmerkmalen abgeleitet werden. Entscheidungsbäume sind beliebt, weil sie leicht zu interpretieren sind und wenig Datenvorverarbeitung erfordern (keine Skalierung oder Normalisierung).

Der Baum wird rekursiv aufgebaut: Ausgehend von der Wurzel wählt der Algorithmus das beste Feature und den Split-Punkt aus, der die Daten am saubersten trennt. Dieser Prozess wird in jeder Teilmenge wiederholt, bis eine Stoppbedingung erfüllt ist. Für mehr Hintergrund bietet Wikipedias Eintrag zum Entscheidungsbaumlernen einen soliden Überblick.

Kernkonzepte, die Sie verstehen müssen

Nodes, Branchs und Leaves

Der Root-Knoten enthält den gesamten Trainingsdatensatz. Interne Knoten testen ein Feature und teilen die Daten in zwei oder mehr Child-Knoten. Zweige sind die Verbindungen, die das Ergebnis eines Tests darstellen. Blattknoten (Terminalknoten) geben die endgültige Vorhersage aus – die häufigste Klasse in der Klassifizierung oder den Mittelwert in der Regression.

Aufspaltungskriterien

Um einen Baum zu bauen, braucht man eine Methode, um die Qualität einer potenziellen Aufteilung zu messen.

Der Algorithmus bewertet jede mögliche Aufteilung auf jedes Merkmal und wählt dasjenige aus, das die größte Verringerung der Unreinheit (oder den Gewinn an Informationen) ergibt.

Information Gain und Gain Ratio

Der Informationsgewinn ist die Differenz zwischen der Verunreinigung des übergeordneten Knotens und der gewichteten Summe der Verunreinigungen von Kindern. Obwohl es einfach ist, neigt es dazu, Merkmale mit vielen Werten zu bevorzugen. Das Verstärkungsverhältnis (in C4.5) normalisiert dies. Für dieses Tutorial werden wir mit dem Standardinformationsgewinn mit Gini-Verunreinigung bleiben, der die Standardeinstellung in CART (Classification and Regression Trees) ist.

Aufbau eines Entscheidungsbaums Schritt für Schritt

1. Bereiten Sie Ihre Daten vor

Zur Vereinfachung: Verwenden Sie einen Datensatz mit Merkmalen und Zielbezeichnungen.

Die Daten bereinigen: fehlende Werte behandeln, Duplikate entfernen und numerische Typen sicherstellen. Entscheidungsbäume können mit gemischten Datentypen umgehen, aber wir bleiben bei der Implementierung bei numerischen.

2. Definition einer Splitting-Kriterium-Funktion

Wir werden die Gini-Verunreinigung implementieren. Der Gini-Index für eine Reihe von Elementen ist:

wobei p i der Anteil der Elemente in Klasse i ist. Bei einem binären Split ist der Gini insgesamt der gewichtete Durchschnitt der Child-Knoten.

3. Durchführung der Split-Bewertung

Für jedes Feature sortieren Sie die eindeutigen Werte, testen Sie jeden möglichen Schwellenwert (Mittelpunkt zwischen aufeinanderfolgenden sortierten Werten), teilen Sie die Daten für jeden Kandidaten-Schwellenwert in linke und rechte Gruppen auf, berechnen Sie den Gini und verfolgen Sie die beste Aufteilung.

4. Bauen Sie den Baum rekursiv

Eine Funktion erstellen, die eine Teilmenge von Daten und eine aktuelle Tiefe benötigt. Sie prüft Stoppbedingungen (z. B. maximale erreichte Tiefe, minimale Samples pro Knoten oder kein Informationsgewinn). Wenn eine Bedingung erfüllt ist, erstellen Sie einen Blattknoten mit der Mehrheitsklasse. Andernfalls finden Sie die beste Aufteilung und erstellen Sie einen internen Knoten und rufen Sie die Funktion rekursiv auf der linken und rechten Aufteilung auf.

5. Vorhersagen treffen

Sobald der Baum gebaut ist, ist die Vorhersage einfach: Beginnen Sie an der Wurzel, folgen Sie den Zweigen, indem Sie die Feature-Tests für das neue Sample auswerten, und geben Sie den Wert des Blattes zurück, auf dem Sie landen.

Vollständige Implementierung in Python

Im Folgenden finden Sie eine vollständige, minimale Implementierung eines Entscheidungsbaums zur Klassifizierung mit Gini-Verunreinigung, der zum Lernen gedacht ist – er ist nicht für große Datensätze optimiert.

import numpy as np
from collections import Counter

class DecisionTree:
 def __init__(self, max_depth=None, min_samples_split=2):
 self.max_depth = max_depth
 self.min_samples_split = min_samples_split
 self.tree = None

 def fit(self, X, y):
 dataset = np.column_stack((X, y))
 self.tree = self._grow_tree(dataset)

 def _grow_tree(self, dataset, depth=0):
 X, y = dataset[:, :-1], dataset[:, -1]
 n_samples, n_features = X.shape
 n_labels = len(np.unique(y))

 # Stopping conditions
 if (n_labels == 1 or depth == self.max_depth or n_samples < self.min_samples_split):
 leaf_value = Counter(y).most_common(1)[0][0]
 return {'leaf': True, 'value': leaf_value}

 best_feature, best_threshold = self._best_split(dataset, n_features)
 if best_feature is None:
 leaf_value = Counter(y).most_common(1)[0][0]
 return {'leaf': True, 'value': leaf_value}

 left_idx, right_idx = self._split(dataset[:, best_feature], best_threshold)
 left_subtree = self._grow_tree(dataset[left_idx], depth+1)
 right_subtree = self._grow_tree(dataset[right_idx], depth+1)
 return {'leaf': False,
 'feature': best_feature,
 'threshold': best_threshold,
 'left': left_subtree,
 'right': right_subtree}

 def _best_split(self, dataset, n_features):
 best_gini = float('inf')
 best_feature, best_threshold = None, None
 for feature in range(n_features):
 thresholds = np.unique(dataset[:, feature])
 for i in range(len(thresholds)-1):
 thresh = (thresholds[i] + thresholds[i+1]) / 2
 left_idx, right_idx = self._split(dataset[:, feature], thresh)
 if len(left_idx) == 0 or len(right_idx) == 0:
 continue
 gini = self._gini_gain(dataset, left_idx, right_idx)
 if gini < best_gini:
 best_gini = gini
 best_feature = feature
 best_threshold = thresh
 return best_feature, best_threshold

 def _split(self, values, threshold):
 left_idx = np.where(values <= threshold)[0]
 right_idx = np.where(values > threshold)[0]
 return left_idx, right_idx

 def _gini_gain(self, dataset, left_idx, right_idx):
 total = len(left_idx) + len(right_idx)
 gini_left = self._gini(dataset[left_idx, -1])
 gini_right = self._gini(dataset[right_idx, -1])
 return (len(left_idx)/total) * gini_left + (len(right_idx)/total) * gini_right

 def _gini(self, labels):
 _, counts = np.unique(labels, return_counts=True)
 p = counts / np.sum(counts)
 return 1 - np.sum(p**2)

 def predict(self, X):
 return np.array([self._predict_row(x, self.tree) for x in X])

 def _predict_row(self, x, node):
 if node['leaf']:
 return node['value']
 if x[node['feature']] <= node['threshold']:
 return self._predict_row(x, node['left'])
 else:
 return self._predict_row(x, node['right'])

Testen des Baumes

Verwenden Sie einen einfachen Datensatz wie den klassischen Iris-Datensatz (zwei Merkmale für die binäre Klassifizierung). Der ] scikit‐learn Iris-Datensatz funktioniert gut. Vergleichen Sie die Genauigkeit Ihres Baumes mit von scikit‐learn, um die Richtigkeit zu überprüfen.

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

data = load_iris()
X = data.data[:100] # take only first two classes (binary)
y = data.target[:100]

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

tree = DecisionTree(max_depth=3)
tree.fit(X_train, y_train)
preds = tree.predict(X_test)
accuracy = np.mean(preds == y_test)
print(f'Accuracy: {accuracy:.2f}')

Fortgeschrittene Techniken zur Verbesserung Ihres Baumes

Beschneiden, um Overfitting zu vermeiden

Ein ausgewachsener Baum kann sich in den Trainingsdaten Rauschen merken. Durch das Beschneiden werden Äste entfernt, die wenig Vorhersagekraft haben. Herkömmliche Methoden sind Pre-Pruning (das Wachstum frühzeitig über oder stoppen) und Post-Pruning (das Anwachsen des vollen Baumes und dann das Entfernen von Ästen mit einem Validierungssatz oder Kostenkomplexitäts-Pruning).

Umgang mit kontinuierlichen und kategorischen Features

Für Continuous Features haben wir Mittelpunkte zwischen sortierten Werten als Schwellenwerte verwendet. Für kategorische Features (z.B. „Farbe = rot/grün/blau) kann jede Kategorie zu einem separaten Zweig (Multi-Wege-Split) werden oder man kann sie binär codieren. Die meisten modernen Implementierungen (wie scikit-learn) verwenden binäre Splits auch für kategorische Features, indem sie alle Teilmengen auswerten.

Umgang mit fehlenden Werten

Reale Daten haben oft fehlende Werte. Ein einfacher Ansatz besteht darin, fehlende Werte dem häufigsten Zweig unter Trainingsproben zuzuordnen, die diese Funktion haben. C4.5 verwendet eine probabilistische Methode. Da es sich um ein Anfänger-Tutorial handelt, gehen wir davon aus, dass die Daten vollständig sind.

Vergleich mit Bibliotheken und weitere Lesung

Während das Bauen von Grund auf pädagogisch ist, verwenden Produktionssysteme Bibliotheken wie scikit-learn, die optimierte C-Implementierungen bieten. Mehr erfahren Sie aus der offiziellen scikit-learn Decision Trees Dokumentation Für tiefere Theorie ist das Buch “The Elements of Statistical Learning” von Hastie, Tibshirani und Friedman eine maßgebliche Ressource. Eine weitere hervorragende Referenz ist das ursprüngliche CART-Buch von Breiman et al.

Schlussfolgerung

Der Aufbau eines Entscheidungsbaums entmystisiert einen der grundlegendsten Algorithmen im maschinellen Lernen. Sie haben gelernt, wie ein einfaches rekursives Splitting-Verfahren ein leistungsfähiges Modell erzeugen kann. Indem Sie den Code selbst schreiben, erhalten Sie ein tieferes Verständnis für Verunreinigungsmaße, Splitselektion und die Kompromisse zwischen Bias und Varianz. Versuchen Sie als nächsten Schritt, Regressionsunterstützung, Beschneiden oder Umgang mit kategorischen Merkmalen hinzuzufügen. Die Fähigkeiten, die Sie hier entwickeln, werden Ihnen gut dienen, wenn Sie zu komplexeren Ensemble-Methoden wie zufälligen Wäldern und Gradientenverstärkung übergehen.