Knotenteilungsmethoden in CART^® Klassifikation

Ein Klassifikationsbaum ergibt sich aus einer binären rekursiven Partitionierung des ursprünglichen Trainingsdatensatzes. Jeder Elternknoten (eine Teilmenge von Trainingsdaten) in einem Baum kann in einer endlichen Anzahl von Möglichkeiten in zwei einander ausschließende Kindknoten geteilt werden; die Möglichkeiten hängen von den tatsächlichen Datenwerten ab, die im Knoten erfasst sind.

Das Teilungsverfahren behandelt Prädiktorvariablen als stetig oder kategorial. Für eine stetige Variable X und einen Wert c wird eine Teilung definiert, indem alle Datensätze mit den Werten X, die kleiner oder gleich c sind, an den linken Knoten und alle verbleibenden Datensätze an den rechten Knoten gesendet werden. CART verwendet zum Berechnen von c immer den Durchschnitt von zwei benachbarten Werten. Eine stetige Variable mit N unterschiedlichen Werten generiert bis zu N–1 potenzielle Teilungen des Elternknotens (die tatsächliche Anzahl ist kleiner, wenn Grenzwerte für die minimal zulässige Knotengröße festgelegt werden).

Ein stetiger Prädiktor verfügt z. B. in den Daten über die Werte 55, 66 und 75. Eine mögliche Teilung für diese Variable besteht darin, dass alle Werte, die kleiner oder gleich (55+66)/2 = 60,5 sind, an einen Kindknoten und alle Werte, die größer als 60,5 sind, an den anderen Kindknoten zu senden. Fälle mit dem Prädiktorwert 55 gehen an einen Knoten, während die Fälle mit den Werten 66 und 75 an den anderen Knoten gesendet werden. Die andere mögliche Teilung für diesen Prädiktor besteht darin, dass alle Werte, die kleiner oder gleich 70,5 sind, an einen Kindknoten und Werte, die größer als 70,5 sind, an den anderen Knoten gesendet werden. Fälle mit den Werten 55 und 66 werden an einen Knoten gesendet, während Fälle mit dem Wert 75 an den anderen Knoten gesendet werden.

Für eine kategoriale Variable X mit unterschiedlichen Werten {c₁, c₂, …, c_k} wird eine Teilung als Teilmenge von Stufen definiert, die an den linken Kindknoten gesendet werden. Eine kategoriale Variable mit K Stufen generiert bis zu 2^K-1–1 Teilungen.

Bei Klassifikationsbäumen ist das Ziel multinomial, mit K eindeutigen Klassen. Das Hauptziel des Baums besteht darin, eine Möglichkeit zu finden, unterschiedliche Zielklassen so rein wie möglich in einzelne Knoten zu trennen. Die resultierende Anzahl von Endknoten muss nicht K sein. Es können mehrere Endknoten verwendet werden, um eine bestimmte Zielklasse darzustellen. Ein Benutzer kann frühere Wahrscheinlichkeiten für die Zielklassen angeben. Diese werden von CART während des Wachstums des Baums berücksichtigt.

In den folgenden Abschnitten verwendet Minitab die folgenden Definitionen für eine binäre Antwortvariable:

Die bedingte Wahrscheinlichkeit eines Ereignisses, wenn sich der Fall im folgenden Knoten befindet: t

Die bedingte Wahrscheinlichkeit eines Nicht-Ereignisses, wenn sich der Fall im folgenden Knoten befindet: t:

In den folgenden Abschnitten verwendet Minitab die folgenden Definitionen für eine multinomiale Antwortvariable:

Die korrigierte A-priori-Wahrscheinlichkeit des Knotens t:

Die Wahrscheinlichkeit von Klasse j bei gegebenem Knoten t:

Diese Definitionen geben die Wahrscheinlichkeiten innerhalb des Knotens an. Minitab berechnet diese Wahrscheinlichkeiten für jeden Knoten und jede mögliche Teilung. Minitab berechnet die Gesamtverbesserung für eine mögliche Teilung aus diesen Wahrscheinlichkeiten anhand eines der folgenden Kriterien.

Notation

Begriff	Beschreibung
K	Anzahl der Klassen in der Antwortvariablen
	A-priori-Wahrscheinlichkeit für Klasse j
	Anzahl der Beobachtungen für Klasse j in einem Knoten
	Anzahl der Beobachtungen für Klasse j in den Daten