CART ist eine Lernmethode für die bedingte Wahrscheinlichkeitsverteilung der Ausgabe-Zufallsvariable Y bei gegebener Eingabe-Zufallsvariable X.

Definition

CART geht davon aus, dass der Entscheidungsbaum ein Binärbaum ist und die Werte der internen Knotenfunktionen „Ja“ und „Nein“ sind. Der linke Zweig ist der Zweig mit dem Wert „Ja“ und der rechte Zweig ist der Zweig mit dem Wert „Nein“. Ein solcher Entscheidungsbaum entspricht der rekursiven Aufteilung jedes Merkmals in zwei Teile, der Aufteilung des Eingaberaums, also des Merkmalsraums, in eine endliche Anzahl von Einheiten und der Bestimmung der vorhergesagten Wahrscheinlichkeitsverteilung auf diesen Einheiten, also der bedingten Wahrscheinlichkeitsverteilung der Ausgabe unter gegebenen Eingabebedingungen.

Der CART-Algorithmus besteht aus den folgenden zwei Schritten:

1. Baumgenerierung: Generieren Sie einen Entscheidungsbaum basierend auf dem Trainingsdatensatz. Der generierte Entscheidungsbaum sollte so groß wie möglich sein.
2. Baumbeschneiden: Verwenden Sie den Validierungsdatensatz, um den generierten Baum zu beschneiden und den optimalen Teilbaum auszuwählen. Als Beschneidungskriterium wird die Minimalverlustfunktion verwendet.

Die Generierung eines Entscheidungsbaums ist ein Prozess der rekursiven Konstruktion eines binären Entscheidungsbaums. Für den Regressionsbaum wird das Kriterium der Minimierung des quadratischen Fehlers verwendet, für den Klassifikationsbaum das Kriterium der Minimierung des Gini-Index, um eine Merkmalsauswahl durchzuführen und einen Binärbaum zu generieren.

Generierung von Regressionsbäumen

Nehmen Sie an, dass X und Y jeweils Eingabe- und Ausgabevektoren sind und Y eine kontinuierliche Variable ist. Überlegen Sie anhand des Trainingsdatensatzes $latex { D}=\left\{\left(x\_{1}, y\_{1}\right),\left(x\_{2}, y\_{2}\right), \ldots,\left(x\_{N}, y\_{N}\right)\right\}$latexD={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}, wie ein Regressionsbaum generiert werden kann.

Ein Regressionsbaum entspricht einer Partition des Eingaberaums (d. h. Merkmalsraums) und dem Ausgabewert jeder Einheit in der Partition. Angenommen, der Eingaberaum wurde in M Einheiten $latex R\_{1}, R\_{2}, \ldots, R\_{M}$latexR_1,R_2,…,R_M unterteilt und es gibt einen festen Ausgabewert $latex c\_{m}$latexc_m für jede Einheit $latex R\_{m}$latexR_m. Dann kann das Regressionsbaummodell wie folgt ausgedrückt werden: $latex f(x)=\sum\_{m=1}^{M} c\_{m} I\left(x \in R\_{m}\right)$latexf(x)=∑_m=1Mc_mI(x∈R_m)

Wenn die Partition des Eingaberaums bestimmt ist, kann der quadratische Fehler verwendet werden$latex \sum\_{x\_{i} \in R\_{m}}\left(y\_{i}-f\left(x\_{i}\right)\right)^{2}$latex∑_x_i∈R_m(y_i−f(x_i))2

Um den Vorhersagefehler des Regressionsbaums für die Trainingsdaten darzustellen, wird der optimale Ausgabewert jeder Einheit mithilfe des Kriteriums des minimalen quadratischen Fehlers gelöst. Es ist leicht zu erkennen, dass der optimale Wert $latex c\_{m}$latexc_m der Einheit $latex R\_{m}$latexR_m der Mittelwert der Ausgabe $latex y\_{i}$latexy_i für alle Eingabeinstanzen $latex x\_{i}$latexx_i auf $latex R\_{m}$latexR_m ist, d. h.

Die Frage ist, wie der Eingaberaum aufgeteilt werden soll. Hier verwenden wir eine heuristische Methode, um die erste auszuwählen J Variablen $latex x^{(j)}$latexx(j) und die Werte, die es annimmtS als Segmentierungsvariable und Segmentierungspunkt und definieren Sie zwei Regionen:

Finden Sie dann die optimale Split-Variable J und der optimale Splitpunkt S . Konkret lösen

Für feste Eingangsgrößen J Der optimale Splitpunkt lässt sich finden S

Durchlaufen Sie alle Eingabevariablen und finden Sie die optimale Segmentierungsvariable J , wodurch ein Paar $latex (j, s)$latex(j,s) entsteht, das wiederum den Eingaberaum in zwei Bereiche unterteilt. Anschließend wird der obige Teilungsprozess für jede Region wiederholt, bis die Abbruchbedingung erfüllt ist.

Generierung von Klassifikationsbäumen

Der Klassifikationsbaum verwendet den Gini-Index, um das optimale Merkmal auszuwählen und den optimalen binären Schnittpunkt für das Merkmal zu bestimmen.

Gini-Index

Im Klassifizierungsprozess wird angenommen, dass es K Klassen gibt und die Wahrscheinlichkeit, dass ein Stichprobenpunkt zur k-ten Klasse gehört, $latex p\_{k}$latexp_k beträgt. Dann wird der Gini-Index der Wahrscheinlichkeitsverteilung wie folgt definiert:

Wenn bei einem Klassifizierungsproblem mit zwei Klassen die Wahrscheinlichkeit, dass ein Stichprobenpunkt zur ersten Klasse gehört, p ist, lautet der Gini-Index der Wahrscheinlichkeitsverteilung:

Für eine gegebene Stichprobenmenge D beträgt der Gini-Index:

Unter diesen ist $latex C\_{k}$latexC_k die Teilmenge der Stichproben in D, die zur k-ten Klasse gehören, und K ist die Anzahl der Klassen.

Wenn der Stichprobensatz D in zwei Teile aufgeteilt wird, $latex D\_{1}$latexD_1 und $latex D\_{2}$latexD_2, je nachdem, ob das Merkmal A einen bestimmten möglichen Wert a annimmt, das heißt:

Dann wird unter der Bedingung des Merkmals A der Gini-Index der Menge D wie folgt definiert:

Der Gini-Index $latex {Gini}(D)$latexGini(D) stellt die Unsicherheit der Menge D dar, und der Gini-Index $latex {Gini}(D, A)$latexGini(D,A) stellt die Unsicherheit der Menge D nach der Partitionierung durch A=a dar. Je höher der Gini-Index, desto größer ist die Unsicherheit des Stichprobensatzes, die der Entropie ähnelt.

Generative Algorithmen

Eingabe: Trainingsdatensatz D, Bedingungen zum Beenden der Berechnung

Ausgabe: CART-Entscheidungsbaum

Führen Sie gemäß dem Trainingsdatensatz ausgehend vom Stammknoten rekursiv die folgenden Operationen an jedem Knoten aus, um einen binären Entscheidungsbaum zu erstellen:

1. Nehmen Sie an, dass der Trainingsdatensatz des Knotens D ist, und berechnen Sie den Gini-Koeffizienten der vorhandenen Merkmale für den Datensatz. Zu diesem Zeitpunkt wird für jedes Merkmal A und für jeden möglichen Wert a D in zwei Teile aufgeteilt, $latex D\_{1}$latexD_1 und $latex D\_{2}$latexD_2, je nachdem, ob der Test des Stichprobenpunkts A=a „ja“ oder „nein“ ergibt, und der Gini-Index für A=a wird berechnet
2. Wählen Sie unter allen möglichen Merkmalen A und allen möglichen Aufteilungspunkten a das Merkmal mit dem kleinsten Gini-Index und seinem entsprechenden Aufteilungspunkt als optimales Merkmal und optimalen Aufteilungspunkt aus. Generieren Sie basierend auf dem optimalen Merkmal und dem optimalen Teilungspunkt zwei untergeordnete Knoten aus dem aktuellen Knoten und verteilen Sie den Trainingsdatensatz entsprechend den Merkmalen auf die beiden untergeordneten Knoten.
3. Rufen Sie (1) und (2) rekursiv für die beiden untergeordneten Knoten auf, bis die Abbruchbedingung erfüllt ist.
4. CART-Entscheidungsbaum generieren