Entscheidungsbäume (engl. *Decision Trees*) gehören zu den beliebtesten Algorithmen im Bereich des überwachten Lernens. Sie bieten eine intuitive und visuelle Methode zur Klassifikation und Regression, da sie Entscheidungen in einer baumartigen Struktur darstellen. In diesem Blogbeitrag werfe ich einen genaueren Blick auf die Funktionsweise von Entscheidungsbäumen, die zugrunde liegenden mathematischen Konzepte und die praktische Implementierung in Python.
Was sind Entscheidungsbäume?
Ein Entscheidungsbaum ist ein Modell, das Daten in einer hierarchischen Struktur darstellt. Die Knoten des Baums repräsentieren Merkmale (Features) der Daten, während die Äste die Entscheidungsregeln und die Blätter die Endergebnisse (Klassifikationen oder Vorhersagen) darstellen. Ein Entscheidungsbaum kann sowohl für Klassifikationsprobleme (z. B. der Vorhersage von Kategorien) als auch für Regressionsprobleme (z. B. der Vorhersage von numerischen Werten) verwendet werden.
So funktioniert ein Entscheidungsbaum:
- Wurzelknoten: Der oberste Knoten des Baums, der das erste Merkmal darstellt, nach dem die Daten aufgeteilt werden.
- Innere Knoten: Jeder innere Knoten repräsentiert ein Merkmal, das die Daten weiter unterteilt.
- Blätter: Die Endknoten, die das Endergebnis oder die Klasse angeben.
Entscheidungsbäume arbeiten rekursiv, indem sie das Feature wählen, das den besten Informationsgewinn oder die größte Reduktion von Unsicherheit liefert, um die Daten in homogene Gruppen zu teilen.
Algorithmen zur Erstellung von Entscheidungsbäumen
Zwei gängige Algorithmen zum Erstellen von Entscheidungsbäumen sind CART (Classification and Regression Trees) und ID3 (Iterative Dichotomiser 3). Der Hauptunterschied zwischen diesen Algorithmen liegt in der Methode, wie sie die besten Splits (Teilungen) wählen. Bei CART wird in der Regel der Gini-Index verwendet, während ID3 auf Entropie und Informationsgewinn basiert.
Gini-Index
Der Gini-Index misst die Ungleichheit oder die „Verunreinigung“ eines Knotens. Ein Gini-Index von 0 bedeutet perfekte Reinheit (alle Instanzen gehören zur gleichen Klasse). Der Algorithmus bevorzugt Splits, die zu Knoten mit geringerem Gini-Index führen.
Die Formel für den Gini-Index lautet:
\[
Gini(D) = 1 – \sum_{i=1}^{C} p_i^2
\]
wobei \(p_i\) der Anteil der Klasse \(i\) im Datensatz \(D\) ist.
Entropie und Informationsgewinn
Die Entropie ist ein Maß für die Unordnung oder Unsicherheit in einem System. Je höher die Entropie, desto unsicherer ist die Klassifikation. Der Informationsgewinn gibt an, wie stark ein Merkmal die Entropie reduziert.
Die Formel für die Entropie lautet:
\[
H(D) = -\sum_{i=1}^{C} p_i \log_2 p_i
\]
wobei \(p_i\) wieder der Anteil der Klasse \(i\) am Datensatz \(D\) ist.
Der Informationsgewinn wird dann wie folgt berechnet:
\[
\text{Gain}(D, A) = H(D) – \sum_{v \in A} \frac{|D_v|}{|D|} H(D_v)
\]
wobei \(A\) das Merkmal ist, nach dem gesplittet wird, und \(D_v\) die Teilmengen sind, die durch die Werte von \(A\) entstehen.
Vor- und Nachteile von Entscheidungsbäumen
Vorteile:
- Einfach zu interpretieren und zu visualisieren: Entscheidungsbäume sind leicht verständlich, sogar für Nicht-Experten. Man kann sie leicht interpretieren, indem man den Baum von der Wurzel zu einem Blatt verfolgt.
- Keine Skalierung der Daten erforderlich: Entscheidungsbäume sind robust gegenüber Daten mit unterschiedlichen Skalierungen, da sie nur die Reihenfolge der Daten betrachten.
- Verarbeitung von kategorialen und numerischen Daten: Entscheidungsbäume können sowohl kategoriale als auch kontinuierliche Daten problemlos verarbeiten.
Nachteile:
- Overfitting: Entscheidungsbäume neigen dazu, die Trainingsdaten zu überanpassen, insbesondere wenn der Baum tief ist und viele Knoten enthält. Dieses Problem kann durch *Pruning* (Beschneiden des Baumes) oder die Begrenzung der maximalen Tiefe gemildert werden.
- Instabilität: Kleine Änderungen in den Daten können zu drastisch unterschiedlichen Bäumen führen, da jeder Split auf Basis der aktuell besten Trennung gewählt wird.
- Bias bei unbalancierten Datensätzen: Entscheidungsbäume können verzerrt sein, wenn eine Klasse deutlich häufiger vorkommt als andere. Dieses Problem lässt sich durch Methoden wie gewichtete Entscheidungsbäume oder den Einsatz von Ensembles wie Random Forest lösen.
Visualisierung und Interpretation des Entscheidungsbaums
Die Visualisierung des Entscheidungsbaums hilft dabei, die Entscheidungsregeln nachzuvollziehen. Jeder Knoten im Baum zeigt:
– Das ausgewählte Feature, das den Split verursacht hat.
– Die Schwelle, die das Merkmal teilt (bei numerischen Merkmalen).
– Die Verteilung der Klassen in jedem Knoten.
– Der Gini-Index oder die Entropie, je nach gewähltem Kriterium.
Durch das Betrachten der Knoten können wir interpretieren, wie der Baum zu einer Vorhersage kommt. Das erste Merkmal am Wurzelknoten ist dasjenige, das den größten Informationsgewinn bringt. Weitere Knoten spezifizieren detailliertere Regeln, bis eine finale Klassifikation erreicht wird.
Implementierung in Python
Die Implementierung eines Entscheidungsbaums mit der Python-Bibliothek Scikit-learn ist relativ einfach. Hier ist ein Beispiel, wie ein Entscheidungsbaum zur Klassifikation eines Datensatzes trainiert und visualisiert werden kann:
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn import tree
import matplotlib.pyplot as plt
# Daten laden
iris = load_iris()
X, y = iris.data, iris.target
# Daten in Trainings- und Testsets aufteilen
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
# Entscheidungsbaum-Modell erstellen
clf = DecisionTreeClassifier(criterion=’gini‘, max_depth=3)
clf.fit(X_train, y_train)
# Visualisierung des Entscheidungsbaums
plt.figure(figsize=(12,8))
tree.plot_tree(clf, feature_names=iris.feature_names, class_names=iris.target_names, filled=True)
plt.show()
1. Der Iris-Datensatz wird geladen und in Trainings- und Testdaten aufgeteilt.
2. Ein Entscheidungsbaum-Klassifikator wird erstellt, wobei der Gini-Index als Kriterium verwendet wird und die Tiefe des Baumes auf 3 begrenzt ist.
3. Der trainierte Entscheidungsbaum wird visualisiert. Das erste Bild oben in diesem Artikel wurde durch diesen Python-Code erzeugt.
Zusammenfassung
Entscheidungsbäume sind ein leistungsfähiges, leicht verständliches Werkzeug im maschinellen Lernen. Sie bieten eine visuelle Darstellung von Entscheidungsprozessen und sind besonders nützlich für Aufgaben der Klassifikation und Regression. Trotz einiger Nachteile wie dem Overfitting und Instabilitäten sind sie eine solide Wahl für viele Machine-Learning-Projekte, insbesondere in Kombination mit anderen Algorithmen wie Random Forest oder Gradient Boosting, auf die ich in Zukunft noch eingehen werde.
Referenzen
[R1]: Scitkit-Learn Documentation: Decision Tree
[R2]: Scitkit-Learn Documentation: The Iris Dataset
[R3]: Decision Tree in Machine Learning, Prince Yadav (veröffentlicht in TowardsDataScience)
[R4]: Decision Tree in Machine Learning
(GeeksforGeeks)
[R5]: Entscheidungsbäume (IBM.com)