CART (Algorithmus)

CART (Classification and Regression Trees) ist ein Algorithmus, der zur Entscheidungsfindung dient. Er wird bei Entscheidungsbäumen eingesetzt.

Der CART-Algorithmus wurde erstmals 1984 von Leo Breiman et al. publiziert.

Allgemeines

Ein bedeutendes Merkmal des CART-Algorithmus ist, dass nur Binärbäume erzeugt werden können, das heißt, dass an jeder Verzweigung immer genau zwei Äste vorhanden sind. Das zentrale Element dieses Algorithmus ist also das Finden einer optimalen binären Trennung.

Beim CART-Algorithmus wird die Attributsauswahl durch die Maximierung des Informationsgehalts gesteuert. CARTs zeichnen sich dadurch aus, dass sie die Daten in Bezug auf die Klassifikation optimal trennen. Dies wird mit einem Schwellwert erreicht, der zu jedem Attribut gesucht wird. Der Informationsgehalt eines Attributes wird als hoch erachtet, wenn durch die Auswertung der sich aus der Teilung über die Schwellwerte ergebenden Attributausprägungen mit einer hohen Trefferquote eine Klassifikation vorgenommen werden kann. Bei den Entscheidungsbäumen, welche durch den CART-Algorithmus berechnet werden, gilt: Je höher der Informationsgehalt eines Attributs in Bezug auf die Zielgröße, desto weiter oben im Baum findet sich dieses Attribut.

Die Entscheidungsschwellwerte ergeben sich jeweils durch die Optimierung der Spaltenentropie. Die Gesamtentropien der Attribute ergeben sich durch ein gewichtetes Mittel aus den Spaltenentropien.

Mathematische Beschreibung

Sei ${\mathcal {D}}=\{(x^{(i)},y_{i})\}_{i=1}^{m}$ die Menge der Trainingsdaten mit Eingabevariablen $x^{(i)}=(x_{1}^{(i)},\dots ,x_{n}^{(i)})\in {\mathcal {X}}$ und Ausgabewerten $y\in {\mathcal {Y}}$. Ein Entscheidungsbaum $T$ ist formal darstellbar mittels einer Funktion $f_{T}:{\mathcal {X}}\rightarrow {\mathcal {Y}}$, die jeder Eingabe eine Vorhersage des Ausgabewertes zuordnet. Der CART Algorithmus zur Erzeugung eines solchen Baumes findet selbständig die Verzweigungen (Knoten) und assoziierten Regeln zur Trennung der Daten (enS split rule), mit denen diese Zuordnung möglichst optimal wird.

Regression

Sei zunächst ${\mathcal {Y}}\subseteq \mathbb {R}$, d. h. die Ausgabe ist ein quantitatives Merkmal und der zu konstruierende Baum soll ein Regressionsproblem lösen. Um einen optimalen Baum zu finden, muss erst einmal ein Trainingskriterium (Fehlerfunktion) definiert werden. Typischerweise wird dafür die Mittlere quadratische Abweichung genutzt:

$E(T,{\mathcal {D}})={\frac {1}{m}}\sum _{i=1}^{m}(f_{T}(x^{(i)})-y_{i})^{2}$,

welche dann minimiert wird. Die Fehlerfunktion ist allerdings generell frei wählbar.

Jedem Blatt $l$ wird eine Menge $R_{l}$ zugeordnet, sodass für alle $L$ Blätter die zugeordneten disjunkten Mengen eine Partition von $D$ bilden. Man sucht nun einen Schätzwert, der für alle $x^{(i)}\in R_{l}$ möglichst nahe an den wahren Werten $\{y_{i}\;|\;x^{(i)}\in R_{l}\}$ liegt. Der Schätzer

$f_{T}(x^{(i)}\in R_{l})={\textrm {mean}}(y_{i}\;|\;x^{(i)}\in R_{l})=:{\hat {c}}_{l}$

liefert dafür eine Lösung. Da die Berechnung aller möglichen Bäume nicht auf effiziente Weise umsetzbar ist, eignet sich für diesen Ansatz ein Greedy-Algorithmus am besten. D.h. konkret: Man beginnt mit einem Baum, der nur aus einem Knoten besteht und findet dann sukzessive lokal optimale Verzweigen. An jedem Knoten bestimmt man das Merkmal $j$, das alle Einträge des Elternknoten am besten in zwei Regionen unterteilen kann, wobei immer auch eine optimale Teilungsvorschrift gefunden werden muss. Für ordinale Merkmale erfolgt dies mittels Schranke $s$, welche die beiden Regionen $R_{1}(j,s)=\{x^{(i)}\;|\;x_{j}^{(i)}\leq s\}$ und $R_{2}(j,s)=\{x^{(i)}\;|\;x_{j}^{(i)}>s\}$ für alle $x^{(i)}$ in der ursprünglichen Partition des Elternknotens so erzeugt, dass die Fehlerfunktion minimiert wird. Sind die Merkmale nicht ordinal, ergeben sich die Verzweigungsvorschriften anhand der Zuordnung zu den verschiedenen Merkmalsausprägungen. Formal lässt sich das schreiben als

$\min _{j,s}{\big (}\min _{c_{1}}\sum _{x^{(i)}\in R_{1}(j,s)}(y_{i}-c_{1})^{2}+\min _{c_{2}}\sum _{x^{(i)}\in R_{2}(j,s)}(y_{i}-c_{2})^{2}{\big )}$,

wobei ${\hat {c}}_{k}={\textrm {mean}}(y_{i}\;|\;x^{(i)}\in R_{k}(j,s))_{k=1,2}$ jeweils die beiden Summen minimiert.

Ausgehend von dem einzelnen Knoten, fügt man also in jedem Schritt zwei neue Knoten hinzu, die wiederum solange weiter verzweigt werden, bis eine Abbruchbedingung (z. B. die maximale Pfadlänge von der Wurzel bis zu den Blättern) erfüllt ist.

Pruning

Da der Baum so in den meisten Fällen zu komplex, also anfällig für Überanpassung (englisch overfitting) ist, kann (sollte) er gestutzt werden (englisch Pruning). Überanpassung lässt sich verhindern, indem in der Fehlerfunktion ein Regulationsterm (vgl. englisch Regularization) eingeführt wird, der nicht von den Daten abhängt und die Komplexität des Entscheidungsbaumes bestraft. Dadurch wird unterbunden, dass der Baum spezifische Eigenschaften der Trainingsdaten lernt, die im Allgemeinen (also bei anderen Daten aus der gleichen Grundgesamtheit) nicht zu den wahren Vorhersagen beitragen.

Die zweite Möglichkeit, die im Folgenden beschrieben wird, ist es zunächst einen relativ großen Baum $T_{0}$ zu konstruieren, der dann im Nachhinein beschnitten wird. Sei $T\subset T_{0}$ ein echter Teilgraph, der durch Entfernung inneren Knoten erzeugt werden kann (d. h. die Partitionen der Kinder dieses Knotens werden zusammengelegt). Sei $|T|$ die Anzahl der Blätter eines solchen Teilgraphs, wobei jedem Blatt $l$ die Partition Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R_l} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |R_l|} Elementen zugeordnet ist. Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat c_l} wie oben und

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q_l(T, \mathcal{D_t}) = \frac{1}{|R_l|} \sum_{x^{(i)} \in R_l} (y_i - \hat c_l)^2} .

Die Idee ist es einen Baum zu finden, der die Funktion

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C_\alpha(T, \mathcal{D_t}) = \sum_{l=1}^{|T|} |R_l| Q_l(T, \mathcal{D_t}) + \alpha |T|}

für gegebenes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \alpha} minimiert. Hierzu wird eine von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{D}} verschiedene Datenmenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{D_t}} (englisch test set) benutzt, um einer Überanpassung vorzubeugen (vgl. Kreuzvalidierungsverfahren).

Der frei wählbare Parameter Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \alpha} beschreibt die Gewichtung zwischen Güte der Voraussage des Entscheidungsbaums und seiner Komplexität. Für gegebenes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \alpha} wird eine absteigende Sequenz von Teilbäumen erzeugt, indem bei jedem Schritt der innere Knoten entfernt wird, der den geringsten pro-Knoten Anstieg von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sum\nolimits_l |R_l| Q_l(T, \mathcal{D_t})} erzeugt, bis nur noch ein einziger Knoten übrig ist. Es gibt dann einen eindeutig bestimmbaren kleinsten Teilbaum, der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C_\alpha(T, \mathcal{D_t})} minimiert.

Klassifizierung

Seien nun die Ausgabewerte kategorisch, d. h. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{Y}} ist eine endliche Menge und o. B. d. A. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y_i \in \{1,2,\dots, K\}} . Die einzigen Änderungen des Algorithmus im Vergleich zur Regression betreffen die Fehlerfunktionen für die Konstruktion des Baums und das Pruning.

Wir definieren

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat p_{lk} := \frac{1}{|R_l|} \sum_{x_i \in R_l} I(y_i=k)} ,

wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |R_l|} gleich der Anzahl der Elemente in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R_l} sei und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I(\cdot)} die Indikatorfunktion.

Damit lässt sich nun in jeder Region Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R_l} die Klassifizierung der Einträge nach Mehrheitsentscheid durchführen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f_T(x^{(i)} \in R_l) = \textrm{argmax}_k \, \hat p_{lk}} .

Mögliche Fehlerfunktionen geben die sogenannte Unreinheit der Partitionen an und können definiert werden als:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{1}{|R_l|} \sum_{x_i \in R_l} I(y_i \neq k) = 1 - \hat p_{lk} \quad} (Missklassifizerungsfehler)

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sum_{k=1}^K \hat p_{lk}(1-\hat p_{lk}) \quad} (Gini-Simpson-Index)

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -\sum_{k=1}^K \hat p_{lk} \log \hat p_{lk} \quad} (Kreuzentropie, Shannon-Index)

Jede dieser Funktionen kann bei der Konstruktion eines Entscheidungsbaumes anstelle der mittleren quadratischen Abweichung genutzt werden, sodass der wesentliche Teil des Algorithmus unverändert bleibt.

Siehe auch

• Iterative Dichotomiser 3 (ID3)
• C4.5
• CHAID
• Klassifikationsbaum-Methode
• Implementierungen
  • In R: rpart
  • In Python mit Scikit-learn: sklearn.tree

Literatur

• T. Hastie, R. Tibshirani, J. Friedman: The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Second Edition. Springer-Verlag New York, 2009, ISBN 978-0-387-84857-0