Regression

Sei zunächst ${\displaystyle {\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:

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

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle s}$, welche die beiden Regionen ${\displaystyle R_{1}(j,s)=\{x^{(i)}\;|\;x_{j}^{(i)}\leq s\}}$ und ${\displaystyle R_{2}(j,s)=\{x^{(i)}\;|\;x_{j}^{(i)}>s\}}$ für alle ${\displaystyle 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

${\displaystyle \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 ${\displaystyle {\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.

Klassifizierung

Seien nun die Ausgabewerte kategorisch, d. h. ${\displaystyle {\mathcal {Y}}}$ ist eine endliche Menge und o. B. d. A. ${\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

${\displaystyle {\hat {p}}_{lk}:={\frac {1}{|R_{l}|}}\sum _{x_{i}\in R_{l}}I(y_{i}=k)}$,

wobei ${\displaystyle |R_{l}|}$ gleich der Anzahl der Elemente in ${\displaystyle R_{l}}$ sei und ${\displaystyle I(\cdot )}$ die Indikatorfunktion.

Damit lässt sich nun in jeder Region ${\displaystyle R_{l}}$ die Klassifizierung der Einträge nach Mehrheitsentscheid durchführen:

${\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:

${\displaystyle {\frac {1}{|R_{l}|}}\sum _{x_{i}\in R_{l}}I(y_{i}\neq k)=1-{\hat {p}}_{lk}\quad }$ (Missklassifizerungsfehler)

${\displaystyle \sum _{k=1}^{K}{\hat {p}}_{lk}(1-{\hat {p}}_{lk})\quad }$ (Gini-Simpson-Index)

${\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.