CART-Algorithmus

Der CART-Algorithmus (Classification and Regression Trees) ist ein grundlegender Algorithmus im Bereich des maschinellen Lernens, der zur Erstellung von Entscheidungsbäumen verwendet wird. Entscheidungsbäume sind eine der intuitivsten und am einfachsten zu verstehenden Methoden für Klassifikations- und Regressionsaufgaben. CART spielt eine zentrale Rolle in der Modellierung, indem es Daten rekursiv in kleinere und homogenere Teilmengen aufteilt, um Vorhersagen zu treffen.

Was ist ein Entscheidungsbaum?

Hier eine kurze Erinnerung: Ein Entscheidungsbaum ist eine baumartige Struktur, die aus Knoten und Kanten besteht. Jeder Knoten repräsentiert eine Entscheidungsregel, basierend auf einem Merkmal der Daten, und jede Kante stellt das Ergebnis dieser Entscheidung dar, das zu einem neuen Knoten oder einem Endknoten führt. Endknoten (Blätter genannt) enthalten die Vorhersagen.
CART kann sowohl für Klassifikationsaufgaben als auch für Regressionsaufgaben verwendet werden.

  • Bei Klassifikationsproblemen teilt CART die Daten in Klassen ein.
  • Bei Regressionsproblemen sagt CART einen numerischen Wert vorher.
Entschiedungsbaum für das Iris-Datenset
Entschiedungsbaum für das Iris-Datenset

Schritt-für-Schritt-Erklärung des CART-Algorithmus

1. Datenauswahl und Aufteilung

Der CART-Algorithmus beginnt mit einem Datensatz, den wir in Features (Merkmale) \( X_1, X_2, \dots, X_n \) und Zielvariablen \( Y \) aufteilen. Ziel ist es, eine optimale Regel zu finden, um den Datensatz rekursiv aufzuteilen.

 

2. Bestimmung der besten Aufteilung

Für jede mögliche Aufteilung des Datensatzes an einem Knoten wählt der Algorithmus diejenige, die eine möglichst homogene Unterteilung der Zielvariable erzielt. Der Algorithmus evaluiert dafür verschiedene Splits, indem er für jedes Merkmal und jede Schwelle \( t \) berechnet, wie „gut“ eine Aufteilung ist. Dazu verwendet der Algorithmus unterschiedliche mathematische Konzepte für Klassifikation und Regression:

  • Klassifikation: Die Homogenität eines Knotens wird durch Metriken wie den Gini-Index oder die Entropie bewertet.
    Der Gini-Index für einen Knoten \( t \) ist definiert als:\[
    Gini(t) = 1 – \sum_{i=1}^{k} p_i^2
    \]
    wobei \( p_i \) der Anteil der Datenpunkte in Klasse \( i \) im Knoten \( t \) ist und \( k \) die Anzahl der Klassen.

    Der Gini-Index gibt an, wie oft man einen zufällig gewählten Datenpunkt falsch klassifizieren würde, wenn man die Klassenzuordnung nur anhand der Verteilung in diesem Knoten vornehmen würde. Der Algorithmus sucht nach Splits, die den Gini-Index minimieren.

Gini-Index in Abhängigkeit vom Split-Schwellenwert
  • Regression: Bei Regressionsbäumen wird die Homogenität durch den mittleren quadratischen Fehler (MSE) gemessen:\[
    MSE = \frac{1}{N} \sum_{i=1}^{N} (y_i – \hat{y})^2
    \]
    Hierbei ist \( N \) die Anzahl der Datenpunkte im Knoten, \( y_i \) ist der tatsächliche Wert und \( \hat{y} \) der vorhergesagte Wert.

    Der Algorithmus versucht, die Aufteilung zu finden, die den MSE minimiert, indem er die Differenz zwischen den tatsächlichen Werten und den Vorhersagen reduziert.

MSE in Abhängigkeit vom Split-Schwellenwert bei Regression

3. Rekursive Aufteilung

Nach der Bestimmung des besten Splits wird der Datensatz an diesem Punkt aufgeteilt. Diese Aufteilung wird rekursiv auf die neuen Teildatensätze angewendet, bis eine der folgenden Bedingungen erfüllt ist:

  • Eine maximale Tiefe des Baumes ist erreicht.
  • Eine Mindestanzahl von Datenpunkten in einem Knoten ist unterschritten.
  • Ein Knoten ist homogen (alle Datenpunkte gehören zur selben Klasse oder der gleiche Wert wird vorhergesagt).

Jeder Endknoten des Baums liefert dann eine Vorhersage: Bei Klassifikationsbäumen wird die häufigste Klasse in diesem Knoten als Vorhersage verwendet, bei Regressionsbäumen der Durchschnitt der Zielvariablen.

4. Rückschnitt (Pruning)

Ohne Begrenzung kann ein Entscheidungsbaum übermäßig komplex werden und Overfitting verursachen. Um dies zu vermeiden, wird oft ein Rückschnitt (Pruning) durchgeführt. Hierbei werden unnötige Knoten entfernt, die nur geringfügig zur Verbesserung der Vorhersagen beitragen. Dies reduziert die Komplexität des Baums und verbessert die Generalisierungsfähigkeit auf neue Daten.

Ein typisches Verfahren ist das cost-complexity pruning, bei dem ein Trade-off zwischen der Genauigkeit des Modells und der Anzahl der Blätter gefunden wird. Dies wird durch eine Regularisierung erreicht, die die Tiefe des Baumes bestraft.

Fehlerrate und Anzahl der Blätter im Verhältnis zur Baumtiefe

Der CART-Algorithmus im Überblick

Für jede mögliche Aufteilung eines Knotens bei einem Entscheidungsbaum führt der CART-Algorithmus folgende Schritte durch:
  1. a) Berechnung des Gini-Index (für Klassifikation): Der Gini-Index wird für jeden Split berechnet, indem die Homogenität der resultierenden Teilmengen beurteilt wird.
    Beispiel: Angenommen, ein Split teilt die Daten in zwei Gruppen:
    Gruppe 1 enthält 80% der Punkte der Klasse A und 20% der Klasse B,
    Gruppe 2 enthält 30% Klasse A und 70% Klasse B.
    Der Gini-Index wird für beide Gruppen berechnet und die Aufteilung wird so gewählt, dass der gewichtete Gini-Index minimiert wird.
  1. b) Berechnung des MSE (für Regression): Bei Regressionen bewertet der Algorithmus die Varianz der Zielwerte nach dem Split. Je niedriger die Varianz, desto besser ist die Aufteilung.
  2. Split-Auswahl: Die Aufteilung mit dem niedrigsten Gini-Index (bei Klassifikation) oder der niedrigsten MSE (bei Regression) wird als optimaler Split gewählt.
  3. Rekursive Anwendung: Dies wird rekursiv auf jeden Knoten des Baums angewendet, bis keine Verbesserung mehr möglich ist.

Zusammenfassung

Der CART-Algorithmus ist ein leistungsfähiges und flexibles Werkzeug für Klassifikations- und Regressionsaufgaben. Er basiert auf der rekursiven Aufteilung eines Datensatzes, um homogene Gruppen zu erstellen, und verwendet dabei mathematische Konzepte wie den Gini-Index oder den mittleren quadratischen Fehler, um die besten Splits zu finden. Der Algorithmus lässt sich leicht visuell durch Entscheidungsbäume darstellen, was ihn besonders verständlich macht.

Nach oben scrollen