BFOS84 (Breiman, Friedman, Olshen, Stone 1984) — Deutsche Zusammenfassung

Breiman, Friedman, Olshen & Stone 1984 — Classification and Regression Trees

Vermerk 2026-08-03 — Regressions-Detail-Herleitungen sind Lernmaterial, nicht mehr Manuskript-Beleg. Die in diesem Dokument dokumentierten Details zur MSE-Herleitung in Kap. 8.3 (Prop. 8.10 als Minimierer-Beweis, R(t)-Formel-Setzung, R(T)-Zerlegung nach Gleichung 8.12, die sechs Formel-Bausteine für S. 230) sind ab 2026-08-03 nicht mehr im Manuskript belegt. Kap. 3.3 der Zulassungsarbeit wurde zugunsten eines Fokus auf Klassifikation gekürzt (die ausführliche Fassung liegt in E_manuskript/archiv/kap-3.3_regression_ausfuehrlich_2026-08-03.tex). Das Detail-Wissen bleibt hier als reines Verteidigungsmaterial verfügbar, falls Lohscheller in der mündlichen Prüfung nach Regression fragt.

Vollständige Referenz: Leo Breiman, Jerome H. Friedman, Richard A. Olshen, Charles J. Stone, Classification and Regression Trees, Wadsworth & Brooks/Cole, Pacific Grove (CA), 1984. — Ein komplettes Fachbuch (358 Seiten), das den CART-Algorithmus entwickelt und dokumentiert.

Für die Zulassungsarbeit

Kernbotschaft: BFOS84 formalisiert CART als vollständigen Algorithmus für Klassifikations- und Regressionsbäume: Impuritätsrahmen mit Gini-Index, Prune-instead-of-stopping mit Cross-Validation, Regressions-Blattvorhersage als Mittelwert und ausführliche Anwendungsstudien in Medizin, Massenspektroskopie und Regression.

Zitat-Landkarte (Stand 2026-08-11)

Chronologische Gesamt-Übersicht aller Zitate der Arbeit: zitat-index.

Hinweis Kap. 5 + 6: Die Kap.-5.0-Belege (Medizin/Massenspektren) sind im Manuskript bereits als \cite[S.~174\,ff.]{BFOS84} und \cite[S.~203\,ff.]{BFOS84} gesetzt, werden in dieser Zusammenfassung aber erst im Zuge des Kap.-5-Rewrites nach PNRB15-Vollrelesung finalisiert. Ebenso bleibt Kap. 6.2 Z. 66 (Linearkombinations-Splits) als \beleg offen.

\beleg-Stellen (offen)

Manuskript-Kap. / Zeile	Aussage	Beleg-Kürzel
Kap. 5.0 Z. 8	CART widmet medizinischen Diagnose- und Prognoseaufgaben ein eigenes Kapitel (im Manuskript bereits \cite[S.~174\,ff.]{BFOS84}, Zusammenfassungs-Verifikation ausstehend)	\beleg{BFOS84 Kap. 6}
Kap. 5.0 Z. 8	CART behandelt die Analyse von Massenspektren in eigenem Kapitel (im Manuskript bereits \cite[S.~203\,ff.]{BFOS84})	\beleg{BFOS84 Kap. 7}
Kap. 6.2 Z. 66	CART enthält Erweiterung um Splits auf Linearkombinationen mehrerer Merkmale	\beleg{BFOS84 Kap. 2.5}

\cite-Stellen (verifiziert, Kap. 2 + Kap. 3)

Manuskript-Kap. / Zeile	Aussage	Zitatmarker
Kap. 2.2 Z. 67	Beschränkung auf binäre Split-Form in CART und darauf aufbauenden Ensembleverfahren	\cite[S.~28\,f.]{BFOS84}
Kap. 2.4 Z. 305	Bibliografische Nennung Breiman et al. 1984 (CART) im Zeitstrahl	\cite{BFOS84}
Kap. 3.1 Z. 23	Reinheits-Zunahme als Ziel jeder Zerlegung (Split-Auswahl-Prinzip)	\cite[S.~23]{BFOS84}
Kap. 3.1 Z. 28	CART-Klassifikations-Blattmarkierung durch die Plurality Rule (häufigste Klasse)	\cite[S.~26, M2]{BFOS84}
Kap. 3.1 Z. 30	Blattvorhersage bei Regression ist konstant	\cite[S.~228]{BFOS84}
Kap. 3.1 Z. 34	Rechtecke-Kachelung des Merkmalsraums (rekursive Partitionierung in Rechtecke)	\cite[S.~30]{BFOS84}
Kap. 3.2 Z. 110	Impuritätsabnahme-Formel $\Delta i(s,t)=i(t)-p_{L}i(t_L)-p_{R}i(t_R)$	\cite[S.~25]{BFOS84}
Kap. 3.2 Z. 117	Auswahlregel bester Split (Maximierung der Impuritätsabnahme)	\cite[S.~26, M1]{BFOS84}
Kap. 3.3 Z. 137	Blattvorhersage in Regressionsbäumen ist konstant (Zweitnutzung)	\cite[S.~228]{BFOS84}
Kap. 3.3 Z. 144	Mittlerer quadratischer Fehler als klassisches Regressionsfehlermaß	\cite[S.~222]{BFOS84}
Kap. 3.3 Z. 146	Mittelwert als Blattvorhersage in Regressionsbäumen (Prop. 8.10)	\cite[S.~230]{BFOS84}
Kap. 3.3 Z. 157	Def. 8.13: $\Delta R$-Formel + Maximierungsregel als Regressions-Analoga zu Kap. 3.2	\cite[S.~231]{BFOS84}
Kap. 3.4 Z. 184	Gini-Index als Split-Kriterium in CART übernommen	\cite[S.~103, M1]{BFOS84}
Kap. 3.4 Z. 197	Gini-Index in Doppelsummen-Form (Zufallsklassifikationsregel)	\cite[S.~103, M3]{BFOS84}
Kap. 3.4 Z. 211	Äquivalente kompakte Darstellung $1-{\sum }_j{p}^2(j\mid t)$	\cite[S.~104, M1]{BFOS84}
Kap. 3.4 Z. 217	Zwei-Klassen-Fall $i(t)=2p(1\mid t)p(2\mid t)$	\cite[S.~103, M2]{BFOS84}
Kap. 3.4 Z. 270	Twoing-Kriterium als zweites Split-Maß für Mehrklassenprobleme	\cite[S.~104\,f., M2]{BFOS84}
Kap. 3.5 Z. 286	Vollständig ausgewachsener Baum überschätzt eigene Vorhersagegüte (Trainingsrauschen mitgelernt)	\cite[S.~60]{BFOS84}
Kap. 3.5 Z. 288	Empirische Beobachtung: gestutzte Bäume durchlaufen sinnvolle Baumgrößen (Waveform-Daten)	\cite[S.~61, M1]{BFOS84}
Kap. 3.5 Z. 293	Früher Split-Abbruch verwirft potenziell gute Splits (Argument gegen Pre-Pruning-Kombination)	\cite[S.~61, M2]{BFOS84}
Kap. 3.5 Z. 299	Prune-instead-of-stopping: Baum voll wachsen lassen, dann zurückschneiden	\cite[S.~62, M1]{BFOS84}
Kap. 3.5 Z. 306	$N_{\min }$ als Compromise-Method-Hyperparameter	\cite[S.~63]{BFOS84}
Kap. 3.5 Z. 320	Cost-Complexity-Pruning + Kreuzvalidierung produziert Bäume nahe optimaler Größe; Bias-Varianz-Trade-off	\cite[S.~62, M2]{BFOS84}

\cite[S.~28\,f.]{BFOS84} — Binäre Split-Form (Kap. 2.2 Z. 67) — verifiziert 2026-08-02

Manuskript-Aussage: Kap. 2.2 Z. 67 — „Insbesondere die CART-Verfahren und die darauf aufbauenden Ensembleverfahren beschränken sich auf die binäre Form, bei der jeder innere Knoten genau zwei ausgehende Kanten hat und der Test als Ja-Nein-Entscheidung formuliert ist.”

Zitatmarker: \cite[S.~28\,f.]{BFOS84}

Originalwortlaut:

„The four elements needed in the initial tree growing procedure were

1. A set $\mathcal{Q}$ of binary questions of the form $\{\text{Is }x\in A?\}$, $A\subset X$
2. A goodness of split criterion $\varphi (s,t)$ that can be evaluated for any split $s$ of any node $t$
3. A stop-splitting rule
4. A rule for assigning every terminal node to a class

The set $\mathcal{Q}$ of binary questions generates a set $S$ of splits $s$ of every node $t$. Those cases in $t$ answering ‚yes’ go to the left descendant node $t_L$ and those answering ‚no’ to the right descendant $t_R$. In fact, if the question is $\{\text{Is }x\in A?\}$, then $t_L=t\cap A$ and $t_R=t\cap A^c$, where $A^c$ is the complement of $A$ in $X$. At each intermediate node $t$, the split selected is that split $s^{\ast }$ which maximizes $\varphi (s,t)$.”

Deutsche Übersetzung:

„Die vier Elemente, die im Anfangs-Baumwachstumsverfahren benötigt werden, waren:

1. Eine Menge $\mathcal{Q}$ binärer Fragen der Form $\{\text{Ist }x\in A?\}$, $A\subset X$
2. Ein Split-Güte-Kriterium $\varphi (s,t)$, das für jeden Split $s$ jedes Knotens $t$ auswertbar ist
3. Eine Stop-Splitting-Regel
4. Eine Regel, die jedem terminalen Knoten eine Klasse zuweist

Die Menge $\mathcal{Q}$ binärer Fragen erzeugt für jeden Knoten $t$ eine Menge $S$ von Splits $s$. Datenpunkte in $t$, die mit ‚ja’ antworten, gehen zum linken Kindknoten $t_L$, die mit ‚nein’ antworten zum rechten Kindknoten $t_R$. Konkret: Wenn die Frage $\{\text{Ist }x\in A?\}$ lautet, dann ist $t_L=t\cap A$ und $t_R=t\cap A^c$, wobei $A^c$ das Komplement von $A$ in $X$ ist. An jedem inneren Knoten $t$ wird derjenige Split $s^{\ast }$ gewählt, der $\varphi (s,t)$ maximiert.”

Begründung Passung: Item 1 der vier Elemente definiert Splits strukturell als binäre Fragen ($\{\text{Is }x\in A?\}$ mit Ja-Nein-Antwort). Der Folgeabsatz verstärkt den Beleg operativ: Die binäre Frage erzeugt genau zwei Kindknoten $t_L=t\cap A$ und $t_R=t\cap A^c$. Damit ist die Behauptung „jeder innere Knoten hat genau zwei ausgehende Kanten und der Test als Ja-Nein-Entscheidung formuliert ist” auf beiden Ebenen belegt — strukturell (Item 1) und operativ (Zwei-Kind-Zerlegung im Folgeabsatz). Der Zusatz „S.~28,f.” ist notwendig, weil die Aufzählung mit Items 3+4 und der Folgeabsatz sich auf S. 29 fortsetzen.

\cite[S.~23]{BFOS84} — Reinheits-Zunahme als Split-Ziel (Kap. 3.1 Absatz 2) — verifiziert 2026-08-02

Manuskript-Aussage: Kap. 3.1 Absatz 2 — „Breiman et al. formulieren als Ziel jeder Zerlegung, dass die Klassenverteilung in den entstehenden Teilmengen reiner ist als im Elternknoten.”

Zitatmarker: \cite[S.~23]{BFOS84}

Originalwortlaut:

„The first problem in tree construction is how to use $\mathcal{L}$ to determine the binary splits of $X$ into smaller and smaller pieces. The fundamental idea is to select each split of a subset so that the data in each of the descendant subsets are ‚purer’ than the data in the parent subset.”

Deutsche Übersetzung:

„Das erste Problem bei der Baum-Konstruktion ist, wie sich $\mathcal{L}$ nutzen lässt, um die binären Splits von $X$ in immer kleinere Teile zu bestimmen. Die grundlegende Idee ist, jeden Split einer Teilmenge so zu wählen, dass die Daten in den entstehenden Kind-Teilmengen ‚reiner’ sind als die Daten in der Elternteilmenge.”

Begründung Passung: Breimans Formulierung „the data in each of the descendant subsets are ‚purer’ than the data in the parent subset” ist wortgetreu die Reinheits-Zunahme als Ziel jeder Zerlegung. Der Fließtext-Halbsatz „reiner ist als im Elternknoten” übersetzt „purer than … the parent subset” direkt. Der einleitende Satz („smaller and smaller pieces”) liefert zudem den iterativen Charakter der Zerlegung.

\cite[S.~25]{BFOS84} — Impuritätsabnahme-Formel (Kap. 3.2) — verifiziert 2026-08-02

Manuskript-Aussage: Kap. 3.2 — „…so ist die Güte des Splits als Abnahme der Impurität definiert: $\Delta i(s,t)=i(t)-p_{L}i(t_L)-p_{R}i(t_R)$.”

Zitatmarker: \cite[S.~25]{BFOS84}

Originalwortlaut (S. 25):

„Then the goodness of the split is defined to be the decrease in impurity $\Delta i(s,t)=i(t)-p_{L}i(t_L)-p_{R}i(t_R)."$

Deutsche Übersetzung:

„Dann ist die Güte des Splits definiert als die Abnahme der Impurität $\Delta i(s,t)=i(t)-p_{L}i(t_L)-p_{R}i(t_R)."$

Begründung Passung: Wortgetreu belegt. Manuskript und Original verwenden identische Formel; Manuskript-Formulierung „Güte des Splits als Abnahme der Impurität” übersetzt „goodness of the split … the decrease in impurity” direkt. Die zuvor stehende Definition der Größenanteile $p_L,p_R$ als „a proportion $p_L$ of the cases in $t$ go into $t_L$” (S. 25 oben, im gleichen Absatz mit Figure 2.6) stützt die Notation.

\cite[S.~26, M1]{BFOS84} — Auswahlregel bester Split (Kap. 3.2) — verifiziert 2026-08-02

Manuskript-Aussage: Kap. 3.2 — „Aus der Kandidatenmenge $S$ aller möglichen Splits am Knoten $t$ wird der Split $s^{\ast }$ gewählt, der diese Abnahme maximiert: $\Delta i(s^{\star },t)={\max }_{s\in S}\Delta i(s,t)$.”

Zitatmarker: \cite[S.~26, M1]{BFOS84}

Originalwortlaut (S. 26, physisch das erste Highlight → M1):

„The tree was grown in the following way: At the root node $t_1$, a search was made through all 5000 candidate splits to find that split $s^{\ast }$ which gave the largest decrease in impurity; i.e., $\Delta i(s^{\ast },t_1)={\max }_{s\in S}\Delta i(s,t_1)$.”

Deutsche Übersetzung:

„Der Baum wurde folgendermaßen aufgebaut: Am Wurzelknoten $t_1$ wurde eine Suche durch alle 5000 Kandidaten-Splits durchgeführt, um denjenigen Split $s^{\ast }$ zu finden, der die größte Abnahme der Impurität ergab; d. h., $\Delta i(s^{\ast },t_1)={\max }_{s\in S}\Delta i(s,t_1)$.”

Begründung Passung: Breiman führt hier die Auswahlregel für den besten Split ($s^{\ast }$ maximiert $\Delta i(s,t)$) mit identischer Formel wie im Manuskript ein. Die Aussage steht im Kontext eines konkreten Beispiels (Wurzelknoten $t_1$, 5000 Kandidaten-Splits), die Formel ist aber ohne Verlust auf beliebige Knoten $t$ übertragbar. Manuskript-Formulierung „derjenige gewählt, der diese Abnahme maximiert” übersetzt „to find that split $s^{\ast }$ which gave the largest decrease in impurity” direkt.

M-Marker-Konvention: Auf S. 26 stehen zwei Zitate untereinander (Auswahlregel M1 physisch zuerst, Plurality Rule M2 physisch danach). Zwei Fließtext-Cites zu derselben Seite werden durch M-Marker unterschieden.

\cite[S.~26, M2]{BFOS84} — CART-Klassifikations-Blattmarkierung durch Plurality Rule (Kap. 3.1 Absatz 3) — verifiziert 2026-08-02

Manuskript-Aussage: Kap. 3.1 Absatz 3 — „Breiman et al. bestimmen für CART bei Klassifikationsaufgaben die Klasse eines Blatts durch die Plurality Rule: das Blatt erhält die häufigste Klasse der zugeordneten Trainingsdatenpunkte.”

Zitatmarker: \cite[S.~26, M2]{BFOS84} (rückwirkend M2 vergeben 2026-08-02 wegen zweitem Zitat auf S. 26)

Originalwortlaut (S. 26):

„The class character of a terminal node was determined by the plurality rule. Specifically, if $p(j_0\mid t)={\max }_{j}p(j\mid t),$ then $t$ was designated as a class $j_0$ terminal node.”

Deutsche Übersetzung:

„Der Klassencharakter eines terminalen Knotens wurde durch die Plurality Rule bestimmt. Konkret: wenn $p(j_0\mid t)={\max }_{j}p(j\mid t),$ dann wurde $t$ als Klasse-$j_0$-terminaler-Knoten bezeichnet.”

Begründung Passung: Breiman formuliert die Plurality Rule explizit — der terminale Knoten $t$ wird der Klasse $j_0$ zugewiesen, für die die bedingte Wahrscheinlichkeit $p(j_0\mid t)$ maximal ist, also der häufigsten Klasse der zum Knoten gehörenden Trainingsdatenpunkte. Damit ist der Fließtext-Halbsatz „durch die Plurality Rule … die häufigste Klasse der zugeordneten Trainingsdatenpunkte” wortgetreu belegt.

Zur Imperfekt-Form (kontextuelle Anmerkung): BFOS84 nutzt hier den narrativ-beschreibenden Stil („was determined”, „was designated”). Anders als die direkt darüberstehende β-Threshold-Terminierungsregel („was simple and unsatisfactory”, explizit als überholt markiert) wird die Plurality Rule nirgends widerrufen; sie ist die Standard-Klassifikationsregel in CART und der übrigen Baum-Literatur.

\cite[S.~231]{BFOS84} — Regressionsimpurität als MSE (Kap. 3.2) — verifiziert 2026-08-02

Manuskript-Aussage: Kap. 3.2 — „Auch bei Regressionsbäumen bleibt der Rahmen unverändert; an die Stelle einer Klassenreinheit tritt dort die mittlere quadratische Abweichung der Zielwerte im Knoten.”

Zitatmarker: \cite[S.~231]{BFOS84}

Originalwortlaut (S. 231, Definition 8.13):

„DEFINITION 8.13. The best split $s^{\ast }$ of $t$ is that split in $S$ which most decreases $R(T)$. More precisely, for any split $s$ of $t$ into $t_L$ and $t_R$, let $\Delta R(s,t)=R(t)-R(t_L)-R(t_R).$ Take the best split $s^{\ast }$ to be a split such that $\Delta R(s^{\ast },t)={\max }_{s\in S}\Delta R(s,t)."$

Deutsche Übersetzung:

„Definition 8.13. Der beste Split $s^{\ast }$ von $t$ ist derjenige Split in $S$, der $R(T)$ am stärksten senkt. Genauer: Für jeden Split $s$ von $t$ in $t_L$ und $t_R$ sei $\Delta R(s,t)=R(t)-R(t_L)-R(t_R).$ Der beste Split $s^{\ast }$ ist derjenige Split, für den gilt $\Delta R(s^{\ast },t)={\max }_{s\in S}\Delta R(s,t)."$

Begründung Passung: Definition 8.13 überträgt formal den Impuritätsrahmen (Impuritätsabnahme + argmax-Auswahl) aus dem Klassifikationsfall $\Delta i(s,t)$ auf den Regressionsfall $\Delta R(s,t)$. Der Rahmen bleibt strukturell identisch — nur die Impuritätsfunktion wechselt von $i(t)$ (Klassifikation, z. B. Gini/Entropie) zu $R(t)$ (Regression, MSE aus S. 230). Das belegt wortgetreu die Manuskript-Aussage „der Rahmen bleibt unverändert” und die Einführung von $R(t)$ als Regressions-Impurität.

Bezug zu S. 230: $R(t)$ wird in Def. 8.13 verwendet, aber selbst auf S. 230 als MSE definiert ($R(t)=\frac{1}{N}{\sum }_{x_n\in t}(y_n-\bar{y}(t){)}^2$). Def. 8.13 baut auf dieser Definition auf und liefert die Rahmen-Übertragung.

\cite[S.~228]{BFOS84} — Blattvorhersage in Regressionsbäumen ist konstant (Kap. 3.3 Absatz 1) — verifiziert 2026-08-02

Manuskript-Aussage: Kap. 3.3 Absatz 1 — „An die Stelle der Mehrheitsklasse tritt als Vorhersage im Blatt ein reeller Zielwert $y(t)\in \mathbb{R}$. Innerhalb eines Blatts ist dieser Wert konstant.”

Zitatmarker: \cite[S.~228]{BFOS84}

Originalwortlaut (S. 228, Beginn Section 8.4 „Tree Structured Regression”):

„A tree structured predictor is similar to a tree structured classifier. The space $X$ is partitioned by a sequence of binary splits into terminal nodes (see Figure 8.2). In each terminal node $t$, the predicted response value $y(t)$ is constant.”

Deutsche Übersetzung:

„Ein baumstrukturierter Prädiktor ist einem baumstrukturierten Klassifikator ähnlich. Der Raum $X$ wird durch eine Folge binärer Splits in terminale Knoten partitioniert (siehe Abbildung 8.2). In jedem terminalen Knoten $t$ ist der vorhergesagte Antwortwert $y(t)$ konstant.”

Begründung Passung: Breiman formuliert wortgetreu, dass die Blattvorhersage $y(t)$ konstant ist („the predicted response value $y(t)$ is constant”). Der Fließtext-Halbsatz „als Vorhersage im Blatt ein konstanter Wert” übersetzt genau das. Die konkrete Wahl (Mittelwert $\bar{y}(t)$) wird in Absatz 2 belegt (S. 230 Prop. 8.10).

\cite[S.~230, M1]{BFOS84} — Mittelwert als Minimierer (Kap. 3.3 Absatz 2) — verifiziert 2026-08-03

Manuskript-Aussage: Kap. 3.1 Absatz 3 — „Breiman et al. legen für CART … bei Regressionsaufgaben den Mittelwert ihrer Zielwerte [als Blattmarkierung fest].”

Zitatmarker: \cite[S.~230]{BFOS84}

Originalwortlaut (S. 230, Prop. 8.10 + anschließende Setzung):

„PROPOSITION 8.10. The value of $y(t)$ that minimizes $R(d)$ is the average of $y_n$ for all cases $(x_n,y_n)$ falling into $t$; that is, the minimizing $y(t)$ is $\bar{y}(t)=\frac{1}{N(t)}{\sum }_{x_n\in t}{y}_n,$ where the sum is over all $y_n$ such that $x_n\in t$ and $N(t)$ is the total number of cases in $t$.”

„From now on, we take the predicted value in any node $t$ to be $\bar{y}(t)$.”

Deutsche Übersetzung:

„Satz 8.10. Der Wert von $y(t)$, der $R(d)$ minimiert, ist der Mittelwert der $y_n$ über alle Fälle $(x_n,y_n)$, die in $t$ fallen; das heißt, der minimierende $y(t)$ ist $\bar{y}(t)=\frac{1}{N(t)}{\sum }_{x_n\in t}{y}_n,$ wobei die Summe über alle $y_n$ läuft, für die $x_n\in t$ gilt, und $N(t)$ die Gesamtzahl der Fälle in $t$ ist.”

„Von jetzt an nehmen wir den vorhergesagten Wert in jedem Knoten $t$ als $\bar{y}(t)$ an.”

Begründung Passung: Prop. 8.10 leitet den Mittelwert $\bar{y}(t)$ als optimale konstante Vorhersage im Knoten $t$ her (er minimiert den quadratischen Fehler). Der Folgesatz „From now on, we take the predicted value in any node $t$ to be $\bar{y}(t)$” ist die eigentliche Setzung. Damit ist die Fließtext-Aussage „bei Regressionsaufgaben den Mittelwert ihrer Zielwerte als Blattmarkierung festlegen” auf beiden Ebenen belegt — Herleitung (warum der Mittelwert) und Setzung (dass er verwendet wird).

---

Formel-Aufarbeitung der S.-230-Passage

Der Kontext auf S. 230 verwendet mehrere Größen (Resubstitutions-Fehler $R(d)$, Blattvorhersage $\bar{y}(t)$, Baumfehler $R(T)$, Knotenfehler $R(t)$). Sie hängen alle zusammen. Wir gehen sie Schritt für Schritt durch.

Baustein 1 — Die Ausgangsfrage: Was ist der Fehler eines Predictors $d$?

$R(d)=\frac{1}{N}{\sum }_n(y_n-d(x_n){)}^2$

Was hier steht: $d$ ist ein Predictor — eine Funktion, die aus einem Merkmalsvektor $x_n$ eine Vorhersage $d(x_n)$ berechnet. $y_n$ ist der wahre Zielwert des Datenpunkts $n$. Die Differenz $y_n-d(x_n)$ ist der Vorhersagefehler an diesem Datenpunkt. Diese Fehler werden quadriert (damit sich positive und negative Abweichungen nicht wegheben), aufsummiert und durch die Datenpunktanzahl $N$ geteilt.

In Worten: $R(d)$ ist der mittlere quadratische Fehler (Mean Squared Error, MSE) des Predictors $d$ auf der Trainingsmenge. Ein perfekter Predictor hätte $R(d)=0$.

Baustein 2 — Die Frage im Blatt: Welche konstante Vorhersage $y(t)$ minimiert $R(d)$ für die Datenpunkte im Knoten $t$?

Im Blatt wird eine einzelne Zahl $y(t)$ als Vorhersage gewählt. Die Frage: Welche Zahl macht den Fehler auf den zum Knoten $t$ gehörenden Datenpunkten am kleinsten?

Formal: minimiere ${\sum }_{x_n\in t}(y_n-y(t){)}^2$ bezüglich $y(t)$.

Antwort (Proposition 8.10): Der Mittelwert der $y_n$ im Knoten $t$:

$\bar{y}(t)=\frac{1}{N(t)}{\sum }_{x_n\in t}{y}_n$

Warum der Mittelwert? Beweisskizze im Text:

„The proof of Proposition 8.10 is based on seeing that the number $a$ which minimizes ${\sum }_n(y_n-a{)}^2$ is $a=\frac{1}{N}{\sum }_n{y}_n$.”

In Worten: Ableitung der Summe $\sum (y_n-a{)}^2$ nach $a$ ergibt $-2\sum (y_n-a)$. Null setzen: $\sum y_n=N\cdot a$, also $a=\bar{y}$. Das ist ein klassisches Ergebnis der Statistik — die optimale Konstante für den quadratischen Fehler ist der arithmetische Mittelwert. Übertragen auf eine Teilmenge $t$: der Mittelwert $\bar{y}(t)$ minimiert den Fehler in $t$.

Baustein 3 — Die Setzung: Ab jetzt ist $\bar{y}(t)$ die Vorhersage im Knoten.

„From now on, we take the predicted value in any node $t$ to be $\bar{y}(t)$.”

In Worten: Statt jedes Mal neu zu fragen „welcher Wert minimiert den Fehler in $t$”, legt Breiman fest: die Vorhersage in $t$ ist immer $\bar{y}(t)$. Damit wird $\bar{y}(t)$ zur festen Regel — für die Blattbeschriftung im Regressionsbaum.

Baustein 4 — Umschreibung von $R(d)$ nach der Setzung:

Mit $\bar{y}(t)$ als Vorhersage kann man den Gesamtfehler des Baums $T$ als Doppelsumme schreiben:

$R(T)=\frac{1}{N}{\sum }_{t\in \tilde{T}}{\sum }_{x_n\in t}(y_n-\bar{y}(t){)}^2\text{(Gleichung 8.11)}$

Was hier steht: $\tilde{T}$ ist die Menge der Blätter (terminal nodes) des Baums $T$. Für jedes Blatt $t$ läuft die innere Summe über alle Datenpunkte, die in $t$ landen; ihre quadratischen Abweichungen vom Blattmittelwert $\bar{y}(t)$ werden aufsummiert. Alle Blattbeiträge werden addiert und mit $N$ normiert.

In Worten: Der Baumfehler $R(T)$ ist die Summe aller quadratischen Blatt-Abweichungen, gemittelt über alle Datenpunkte.

Baustein 5 — Der Knotenbeitrag $R(t)$:

$R(t)=\frac{1}{N}{\sum }_{x_n\in t}(y_n-\bar{y}(t){)}^2$

Was hier steht: $R(t)$ ist genau die innere Summe aus Gleichung 8.11 (ohne die äußere Blattsumme) — der Fehlerbeitrag des einzelnen Knotens $t$ zum Gesamtfehler.

Wichtig: die Normierung mit $N$ (nicht $N(t)$) ist eine bewusste Konvention — sie sorgt dafür, dass die Größenanteile der Blätter implizit in $R(t)$ enthalten sind. Ein großes Blatt mit vielen Datenpunkten trägt automatisch mehr zum Gesamtfehler bei als ein kleines.

Baustein 6 — Die Zerlegung (Gleichung 8.12):

$R(T)={\sum }_{t\in \tilde{T}}R(t)$

In Worten: Der Gesamtfehler des Baums ist die Summe der Knotenbeiträge über alle Blätter. Die Doppelsumme aus 8.11 wird durch Definition von $R(t)$ zu einer einzigen Summe über Blätter zusammengefasst.

Warum das nützlich ist: Diese Zerlegung wird der Ausgangspunkt für das Cost-Complexity-Pruning in Kap. 3 (BFOS84 Section 3.3). Dort wird der Regularisierungsansatz $R_{\alpha }(T)=R(T)+\alpha \cdot |\tilde{T}|$ direkt auf $R(T)$ aufgebaut. Sie wird auch der Ausgangspunkt für die Regressions-Impuritätsfunktion in Kap. 3.2 der Zulassungsarbeit.

---

Zusammenfassung — was Du hiermit weißt:

• $R(d)$ ist der mittlere quadratische Fehler eines beliebigen Predictors $d$ auf der Trainingsmenge.
• $\bar{y}(t)$ ist der Mittelwert der Zielwerte im Knoten $t$. Prop. 8.10 zeigt: das ist die optimale konstante Vorhersage in $t$.
• Setzung: Von jetzt an ist $\bar{y}(t)$ die Vorhersage in $t$ — das ist die CART-Regressions-Blattregel.
• $R(T)$ ist der Gesamtfehler des Baums nach dieser Setzung.
• $R(t)$ ist der Fehlerbeitrag eines einzelnen Blatts $t$ (mit $N$ normiert, damit Blattgrößen implizit gewichtet sind).
• $R(T)={\sum }_{t}R(t)$ ist die Zerlegung, die später Cost-Complexity-Pruning ermöglicht.

Warum das wichtig für die Zulassungsarbeit ist: M1 ($\bar{y}(t)$) und M2 ($R(t)$) belegen zusammen die Herleitung in Kap. 3.3 Absatz 2. Die Zerlegung $R(T)={\sum }_{t}R(t)$ (Gleichung 8.12, ebenfalls auf S. 230) wird in Kap. 3.3 Absatz 3 relevant und dort mit S. 231 (Def. 8.13) belegt.

\cite[S.~230, M2]{BFOS84} — R(t)-Formel als Regressionsimpurität (Kap. 3.3 Absatz 2) — verifiziert 2026-08-03

Manuskript-Aussage: Kap. 3.3 Absatz 2 — „…Einsetzen von $\bar{y}(t)$ als Blattvorhersage in den Fehlerausdruck und Normierung auf den Gesamtdatensatz mit $N$ Datenpunkten liefert die Regressionsimpurität am Knoten: $R(t)=\frac{1}{N}{\sum }_{x_n\in t}(y_n-\bar{y}(t){)}^2$.”

Zitatmarker: \cite[S.~230, M2]{BFOS84} — R(t)-Formel (physisch das zweite Highlight auf S. 230, nach der „From now on”-Setzung)

Originalwortlaut (S. 230, nach der „From now on”-Setzung):

„Set $R(t)=\frac{1}{N}{\sum }_{x_n\in t}(y_n-\bar{y}(t){)}^2$ so (8.11) can be written as $R(T)={\sum }_{t\in \tilde{T}}R(t)."$

Deutsche Übersetzung:

„Setze $R(t)=\frac{1}{N}{\sum }_{x_n\in t}(y_n-\bar{y}(t){)}^2,$ sodass sich (8.11) als $R(T)={\sum }_{t\in \tilde{T}}R(t)$ schreiben lässt.”

Begründung Passung: Die Manuskript-Formel für $R(t)$ ist identisch mit der Setzung auf S. 230. Die Fließtext-Erklärung („Einsetzen von $\bar{y}(t)$ … Normierung auf $N$”) entspricht Breimans Herleitungsschritt: nach der Setzung $y(t)=\bar{y}(t)$ wird der Fehlerausdruck mit der Blattvorhersage evaluiert und in der R(t)-Notation zusammengefasst. Die $\frac{1}{N}$-Normierung (statt $\frac{1}{N(t)}$) ist Voraussetzung für die Zerlegung $R(T)={\sum }_{t}R(t)$.

M-Marker-Konvention: Auf S. 230 stehen zwei Zitate — Prop. 8.10 (M1) und R(t)-Formel (M2). Die Zerlegung $R(T)=\sum R(t)$ (Gleichung 8.12) ist Bonus-Content dieser Passage und wird in Kap. 3.3 Absatz 3 gebraucht.

\cite[S.~30]{BFOS84} — Rechtecke-Kachelung des Merkmalsraums (Kap. 3.1 Absatz 4) — verifiziert 2026-08-02

Manuskript-Aussage: Kap. 3.1 Absatz 4 — „Anschaulich lässt sich das Verfahren als fortschreitende Zerlegung des Merkmalsraums in achsenparallele Rechtecke beschreiben.”

Zitatmarker: \cite[S.~30]{BFOS84}

Originalwortlaut (S. 30):

„When fixed-dimensional data have only ordered variables, another way of looking at the tree structured procedure is as a recursive partitioning of the data space into rectangles.”

Deutsche Übersetzung:

„Wenn festdimensionale Daten nur geordnete Variablen enthalten, lässt sich das baumbasierte Verfahren auch als rekursive Partitionierung des Datenraums in Rechtecke auffassen.”

Begründung Passung: Breimans „recursive partitioning of the data space into rectangles” ist wortgetreu die Kachelungssichtweise. Der Zusatz „achsenparallel” im Fließtext ergibt sich implizit aus Breimans Voraussetzung „only ordered variables” mit binären Splits der Form $\{x_m\le c\}$ (Section 2.4.1) — jede solche Trennung erfolgt entlang einer einzelnen Achse und erzeugt achsenparallele Kanten. Die Fließtext-Aussage ist damit belegtreu.

\cite{BFOS84} — Bibliografische Nennung im Zeitstrahl (Kap. 2.4 Z. 322)

Manuskript-Aussage: Nennung von Breiman et al. 1984 (CART) im chronologischen Zeitstrahl. Zitatmarker: \cite{BFOS84} Originalwortlaut: Bibliografische Nennung ohne Seitenbezug — kein konkreter Zitatwortlaut. Deutsche Übersetzung: — Begründung Passung: Reine bibliografische Nennung der Primärquelle im Zeitstrahl-Kontext.

---

Kapitel 2. Introduction to Tree Classification

Der Kern für unser Kap. 3.1.

Section 2.2. Drei Design-Entscheidungen

Breiman et al. beschreiben die Baum-Konstruktion konzeptuell in drei elementaren Design-Entscheidungen: Split-Wahl, Terminierung, Klassen-Zuweisung.

Section 2.3. Konstruktion des Baums

Impuritätsabnahme: Für jeden Kandidaten-Split $s$ am Knoten $t$, der $t$ in Kind-Knoten $t_L$ und $t_R$ zerlegt:

$\Delta i(s,t)=i(t)-p_L\cdot i(t_L)-p_R\cdot i(t_R)$

Dabei sind $p_L$ und $p_R$ die Größenanteile der Kind-Knoten.

Auswahlregel: Aus der Kandidatenmenge $S$ wähle den Split $s^{\ast }$, der die Impurität am stärksten senkt:

$\Delta i(s^{\ast },t)={\max }_{s\in S}\Delta i(s,t)\text{(a¨quivalent: }{s}^{\ast }=\arg {\max }_s\Delta i(s,t)\text{)}$

Notation in der Arbeit bewusst wortgetreu zu BFOS84 (s statt δ); die argmax-Form ist die mathematisch äquivalente Umformulierung.

Section 2.4. Initial Tree Growing Methodology

Breiman et al. formalisieren die zuvor konzeptuell eingeführte Baum-Konstruktion in vier expliziten Elementen des Wachstumsverfahrens. Item 1 definiert Splits als binäre Fragen der Form $\{\text{Is }x\in A?\}$; Item 2 fordert ein auswertbares Split-Güte-Kriterium; Elemente 3 und 4 folgen mit Terminierung und Blattzuweisung.

Section 2.4 — N_min-Regel

Konkrete Regel: Weitersplitten bis eine der drei Bedingungen zutrifft:

• Knoten ist klassenrein
• Knoten hat $\le N_{\min }$ Datenpunkte
• Alle Datenpunkte im Knoten haben identische Merkmalsvektoren

Typische Wahl: $N_{\min }=5$, gelegentlich $N_{\min }=1$.

---

Section 2.5.3. Linear Combination Splits

Erweiterung: Statt Splits auf einem einzelnen Attribut kann CART auch Splits auf Linearkombinationen mehrerer Merkmale durchführen:

$\text{Ist }{\sum }_m{a}_m\cdot x_m\le c?$

Motivation: Wenn die wahre Klassengrenze diagonal verläuft (nicht achsenparallel), braucht ein achsenparalleler Baum viele Splits, um sie näherungsweise nachzubilden (Treppenstruktur). Linear-Combination-Splits können diagonale Trennungen direkt modellieren.

In der Praxis: Selten benutzt, weil sie den Baum unlesbar machen.

---

Kapitel 3. Right Sized Trees and Honest Estimates

Der Kern für unser Kap. 3.8 (Post-Pruning).

Section 3.1. Motivation

Der Trainingsfehler $R(T)$ nimmt monoton mit der Baum-Größe ab; der wahre Fehler $R^{\ast }(T)$ hat ein Minimum bei mittlerer Größe.

Prune instead of stopping

BFOS84-Kern-Entscheidung: Anstatt Stopping-Rules zu perfektionieren, ist es besser, erst voll aufzubauen und dann rückwirkend zu prunen. Zwei nummerierte Punkte:

1. Prune instead of stopping. Baue einen viel zu großen Baum und pruen ihn nach oben in der „richtigen Weise” bis zurück zur Wurzel.
2. Nutze genauere Schätzer für $R^{\ast }(T)$, um den richtig dimensionierten Baum aus den geprunten Teilbäumen zu wählen.

Bei kleinen Stichproben ist die bevorzugte Methode die Kreuzvalidierung, die den Aufbau von Hilfsbäumen erforderlich macht.

Section 3.3. Cost-Complexity-Pruning

Das Kern-Verfahren von CART: $R_{\alpha }(T)=R(T)+\alpha \cdot |\tilde{T}|$; für jedes $\alpha$ existiert ein eindeutig optimaler Teilbaum, die richtige Wahl von $\alpha$ per Kreuzvalidierung.

---

Kapitel 4.3. The Gini Criterion

Der Kern für unser Kap. 3.4.

Formale Definition — Doppelsumme

$i(t)={\sum }_{j\ne i}p(j|t)\cdot p(i|t)$

Der Gini-Index eines Knotens $t$ in seiner ursprünglichen Doppelsummen-Form (Gl. 4.8 im Original).

Äquivalente Umformung — Quadratsumme

$i(t)=1-{\sum }_j{p}^2(j|t)$

Rechnerisch einfachere Form (Gl. 4.9). Folgt direkt aus der Randbedingung ${\sum }_{j}p(j|t)=1$.

Wahrscheinlichkeits-Interpretation

In Worten: Der Gini-Index ist die Wahrscheinlichkeit einer Fehlklassifikation unter der (hypothetischen) zufälligen Zuordnungsregel „gib jedem Objekt die Klasse $i$ mit Wahrscheinlichkeit $p(i|t)$“.

---

Kapitel 6. Medical Diagnosis and Prognosis

Anwendungsstudien in der Medizin. Kapitel-Einleitung mit der Anwendungsdomäne.

Konkrete Fallstudien in diesem Kapitel:

• Section 6.1: 30-Tage-Prognose nach Herzinfarkt
• Section 6.2: Diagnose von Herzinfarkten
• Section 6.3: Diagnose von Krebsvarianten anhand von Immunosuppression-Messungen
• Section 6.4: Altersklassifikation anhand von Gangbild-Messungen

Belegt, dass ein ganzes Kapitel dem Anwendungsfeld medizinische Diagnose gewidmet ist.

---

Kapitel 7. Mass Spectra Classification

Anwendungsstudien in der Massenspektroskopie. Klassifikation chemischer Verbindungen anhand ihrer Massenspektren.

---

Kapitel 8. Regression Trees

Regressionsbäume — CARTs Erweiterung auf numerische Zielvariablen.

Kapitel-Einleitung

Das Regressions-Kapitel eröffnet mit der Aussage, dass der baumstrukturierte Ansatz in der Regression einfacher als in der Klassifikation ist. Das gleiche Impuritätskriterium wird sowohl zum Wachsen als auch zum Prunen genutzt.

Regressionsbaum als Histogrammschätzung

Da der Predictor $d(x)$ über jedem Blatt konstant ist, kann der Baum als Histogrammschätzung der Regressionsfläche gesehen werden. Anschauliche Deutung: Ein Regressionsbaum sagt in jedem Blatt einen konstanten Zielwert vor; über den Merkmalsraum entsteht damit eine stückweise konstante Vorhersagefläche — geometrisch eine Kacheldarstellung, statistisch eine (mehrdimensionale) Histogrammschätzung der Regressionsfläche $E(Y\mid X=x)$.

Mittelwert-Vorhersage im Regressionsblatt (Proposition 8.10)

Blattvorhersage $\bar{y}(t)$ minimiert den resubstitution-Fehler:

$\bar{y}(t)=\frac{1}{N(t)}{\sum }_{x_n\in t}{y}_n$

MSE-Impurität im Knoten

MSE-basierte Impuritätsfunktion:

$R(t)=\frac{1}{N}{\sum }_{x_n\in t}(y_n-\bar{y}(t){)}^2$

Def. 8.13: Impuritätsabnahme bei Regression

Die Regressions-Analog-Form der Impuritätsabnahme:

$\Delta R(s,t)=R(t)-R(t_L)-R(t_R)$

Der Beitrag eines Splits zur Fehlerreduktion ist die Differenz zwischen dem within-node-SSE des Elternknotens und der Summe der within-node-SSEs der beiden Kinder. Die im Klassifikationsfall explizit auftretenden Gewichtsfaktoren $p_L,p_R$ fehlen hier, weil bei BFOS84 in $R(t)=(1/N)\sum (y_n-\bar{y}(t){)}^2$ die Normierung mit dem Gesamt-N (nicht dem Knoten-N) bereits enthalten ist — die Größenanteile stecken so implizit in $R(t_L)$ und $R(t_R)$.

Auswahlregel für den besten Regressions-Split

$\Delta R(s^{\ast },t)={\max }_{s\in S}\Delta R(s,t)$

Die argmax/max-Auswahlregel überträgt sich unverändert aus dem Klassifikationsrahmen auf die Regression. Damit ist der impuritätsbasierte Split-Rahmen aus Kap. 3.2 der Arbeit vollständig auf Regression übertragen: gleiche Auswahllogik, nur die Impuritätsfunktion wechselt von Gini/Entropie zur MSE.

---

Zusammenfassung — was Du wissen musst

Wenn Du morgen 5 Sätze über BFOS84 sagen musst, sind es diese:

1. CART (Classification And Regression Trees) formalisiert die Baum-Konstruktion in drei Design-Entscheidungen: Split-Wahl, Terminierung und Klassen-Zuweisung. Diese Struktur ist die Grundlage aller späteren Baum-Verfahren.
2. Split-Kriterium: CART nutzt den Gini-Index — anschaulich: die Wahrscheinlichkeit einer Fehlklassifikation unter einer zufälligen Zuordnungsregel. Formal: $i(t)=1-{\sum }_j{p}^2(j|t)$.
3. Terminierung: CART wächst den Baum bis zur Erschöpfung ($N(t)\le N_{\min }$, typisch $N_{\min }=5$) und prunt dann zurück (statt frühzeitig zu stoppen).
4. Post-Pruning: Cost-Complexity-Pruning mit Regularisierungsparameter $\alpha$; die Wahl von $\alpha$ per Kreuzvalidierung.
5. Regression: CART behandelt auch numerische Zielvariablen — Blattvorhersage ist der Mittelwert, Impuritätsfunktion ist die mittlere quadratische Abweichung. Ausführliche Anwendungsstudien in Medizin (Kap. 6) und Massenspektroskopie (Kap. 7).

---

Formales Referenzblatt

Symboltabelle

Symbol	Aussprache / Name	Bedeutung
$t$	„kleines t”	Knoten in einem Baum (bei BFOS84: gleichzeitig die Teilmenge $t\subset X$ der Datenpunkte, die diesen Knoten erreichen)
$t_L,t_R$	„t-L, t-R”	Linker / rechter Kind-Knoten nach einem Split
$t_1$	„t-1”	Wurzelknoten (die gesamte Trainingsmenge)
$\tilde{T}$	„T Schlange”	Menge der Blattknoten eines Baums $T$ (= terminale Knoten)
$	\tilde{T}	$
$s$	„kleines s” (split)	Kandidaten-Split an einem Knoten (BFOS84 nutzt kleines s, andere Autoren $\delta$)
$s^{\ast }$	„s Stern”	Ausgewählter (bester) Split — der, der die Impurität am stärksten senkt
$S$	„großes S”	Menge aller Kandidaten-Splits an einem Knoten
$i(t)$	„i von t” (impurity)	Impuritätsfunktion eines Knotens — Maß für Klassen-Unreinheit; bei CART: Gini
$\Delta i(s,t)$	„Delta i von s, t”	Impuritätsabnahme durch Split $s$ am Knoten $t$
$p(j\mid t)$	„p von j gegeben t”	Relative Häufigkeit der Klasse $j$ im Knoten $t$
$p_L,p_R$	„p-L, p-R”	Größenanteile der Kind-Knoten am Elternknoten
$N(t)$	„N von t”	Anzahl der Datenpunkte im Knoten $t$
$N_{\min }$	„N-min”	Mindestgröße eines Knotens, bei dem noch gesplittet werden darf (typisch: 5)
$T_{\max }$	„T-max”	Voll aufgebauter Baum (Ausgangspunkt für Pruning)
$T$	„großes T”	Ein Baum (allgemein) — kann $T_{\max }$ oder ein gestutzter Teilbaum sein
$T_{\alpha }$	„T alpha”	Optimaler Teilbaum für den gewählten Wert von $\alpha$ (Cost-Complexity-Pruning)
$R(T)$	„R von T” (Risk)	Fehlerrate (misclassification cost) des Baums auf Trainingsdaten (resubstitution estimate)
$R(t)$	„R von t”	Fehlerrate des einzelnen Knotens $t$
$R^{\ast }(T)$	„R Stern von T”	Wahre Fehlerrate auf unbekannten Daten (true generalization error) — unbeobachtbar, muss geschätzt werden
$R_{\alpha }(T)$	„R alpha von T”	Cost-Complexity = Fehler + $\alpha$ × Komplexität
$\alpha$	„alpha” (griechisch α)	Regularisierungsparameter — bestimmt den Kompromiss zwischen Genauigkeit und Einfachheit
$a_m$	„a-m”	Koeffizient in einer Linearkombination von Merkmalen (Section 2.5.3)
$x_m$	„x-m”	Wert des $m$-ten Merkmals
$c$	„kleines c”	Schwellwert für einen Split (auf Merkmal oder Linearkombination)
$y_n$	„y-n”	Zielwert (bei Regression: numerisch; bei Klassifikation: Klassenlabel)
$\bar{y}(t)$	„y quer von t”	Mittelwert der Zielwerte im Knoten $t$ (Regressions-Blattvorhersage)

Formeln und ihre Bedeutung

(1) Impuritätsabnahme durch einen Split:

$\Delta i(s,t)=i(t)-p_L\cdot i(t_L)-p_R\cdot i(t_R)$

Was sie sagt: Ein Split am Knoten $t$ senkt die Impurität um die Differenz zwischen der ursprünglichen Impurität $i(t)$ und dem gewichteten Mittel der Kind-Impuritäten.

(2) Auswahlregel:

$\Delta i(s^{\ast },t)={\max }_{s\in S}\Delta i(s,t)⟺s^{\ast }=\arg {\max }_{s\in S}\Delta i(s,t)$

Zwei Notationsformen: Die max-Form (BFOS84-Original) gibt den maximalen Wert, die argmax-Form gibt das Argument, das dieses Maximum liefert. Mathematisch äquivalent.

(3) Gini-Index in der Doppelsumme-Form:

$i(t)={\sum }_{j\ne i}p(j|t)\cdot p(i|t)$

Was sie sagt: Der Gini-Index summiert die Produkte der Klassenwahrscheinlichkeiten über alle Paare unterschiedlicher Klassen.

Anschauliche Deutung: Die Wahrscheinlichkeit einer Fehlklassifikation unter der zufälligen Zuordnungsregel „ordne mit Wahrscheinlichkeit $p(i|t)$ der Klasse $i$ zu”.

(4) Gini-Index in der Quadratsummen-Form:

$i(t)=1-{\sum }_j{p}^2(j|t)$

Was sie sagt: Rechnerisch einfachere Form, die aus der Randbedingung ${\sum }_{j}p(j|t)=1$ folgt.

Extremwerte:

• Alle Datenpunkte gleicher Klasse ($p(j_0|t)=1$, sonst 0): $i(t)=1-1=0$ (klassenrein).
• $K$ Klassen gleichverteilt ($p(j|t)=1/K$): $i(t)=1-K\cdot (1/K{)}^2=1-1/K$ (Maximum).
• Zwei-Klassen-Fall bei $p=0,5$: $i(t)=1-0,5=0,5$.

---

Herleitung: von Formel (3) zu Formel (4)

Die beiden Formen des Gini-Index sind mathematisch äquivalent. Die Umformung ist ein Klassiker aus der Wahrscheinlichkeitsalgebra; einmal verstanden merkt man sich den Schritt für immer.

Was ist die Randbedingung?

${\sum }_{j}p(j|t)=1$

Die Summe der Wahrscheinlichkeiten aller Klassen an einem Knoten $t$ ergibt 1. Grund: Jeder Datenpunkt gehört zu genau einer Klasse, die Klassenanteile müssen sich also zu 100 % addieren.

Der Trick — das Quadrat der Randbedingung:

Quadriere beide Seiten der Randbedingung:

${\left({\sum }_{j}p(j|t)\right)}^2=1^2=1$

Die linke Seite ist ein Produkt zweier Summen; ausmultipliziert entsteht eine Doppelsumme über alle Paare $(i,j)$ --- inklusive derjenigen mit $i=j$:

${\left({\sum }_{j}p(j|t)\right)}^2={\sum }_i{\sum }_{j}p(i|t)\cdot p(j|t)=1$

Die Doppelsumme aufsplitten:

Jede Doppelsumme über alle Paare $(i,j)$ lässt sich in zwei disjunkte Teile zerlegen:

• Diagonale ($i=j$): $\sum _{j}p(j|t)\cdot p(j|t)=\sum _j{p}^2(j|t)$
• Off-Diagonale ($i\ne j$): $\sum _{i\ne j}p(i|t)\cdot p(j|t)$

Zusammen ergibt das die ganze Doppelsumme:

${\sum }_j{p}^2(j|t)+{\sum }_{i\ne j}p(i|t)\cdot p(j|t)=1$

Umstellen liefert Formel (4):

$\underset{=i(t)\text{ nach Formel (3)}}{\underbrace{\sum _{i\ne j}p(i|t)\cdot p(j|t)}}=1-{\sum }_j{p}^2(j|t)$

Die linke Seite ist der Gini-Index in Doppelsummen-Form (Formel 3), die rechte Seite die vereinfachte Quadratsummen-Form (Formel 4). Q.E.D.

Warum „rechnerisch einfacher”?

• Doppelsumme hat bei $K$ Klassen $K(K-1)$ Terme (bei $K=10$ also 90 Produkte)
• Quadratsummen-Form hat nur $K$ Quadrate (bei $K=10$ also 10)

Grafische Merkhilfe — die Klassenpaar-Matrix am Beispiel $K=3$:

$$\begin{array}{cccc}& j=1& j=2& j=3\\ i=1& {\mathbf{p}}_1^2& p_1{p}_2& p_1{p}_3\\ i=2& p_2{p}_1& {\mathbf{p}}_2^2& p_2{p}_3\\ i=3& p_3{p}_1& p_3{p}_2& {\mathbf{p}}_3^2\end{array}$$

(Kurzform $p_j=p(j|t)$.)

• Ganze Matrix summiert zu $({\sum }_j{p}_j{)}^2=1$
• Diagonale (fett) sind die $p_j^2$-Terme
• Alles außerhalb der Diagonale ist der Gini-Index in Doppelsummen-Form

Also: Gini = Gesamtsumme (=1) minus Diagonale (${\sum }_j{p}_j^2$).

Für die Verteidigung merken:

• Randbedingung: Wahrscheinlichkeiten aller Klassen summieren zu 1.
• Schlüsselschritt: Quadriere die Randbedingung, splitte die entstehende Doppelsumme in Diagonale ($\sum p^2$) und Off-Diagonale (= Gini in Doppelsummenform).
• Umstellen liefert direkt die Quadratsummen-Form.

(5) N_min-Stop-splitting rule:

$\text{Splitten bis: }(\text{klassenrein})\vee (N(t)\le N_{\min })\vee (\text{alle }{x}_n\text{ identisch})$

Was sie sagt: Weitersplitten bis der Knoten klassenrein, hat höchstens $N_{\min }$ Datenpunkte, oder alle Datenpunkte identisch sind. Typisch: $N_{\min }=5$.

Warum konservativ: Das Wachstum stoppt nicht mit einer statistischen Signifikanz-Regel — das Pruning kommt später als eigener Schritt.

(6) Cost-Complexity:

$R_{\alpha }(T)=R(T)+\alpha \cdot |\tilde{T}|$

Was sie sagt: Bewerte einen Baum als Kombination aus Trainingsfehler und Baum-Komplexität, mit Regularisierungsparameter $\alpha \ge 0$.

Wahl von $\alpha$:

• $\alpha =0$: nur Fehler zählt → $T_{\alpha }=T_{\max }$
• $\alpha \to \infty$: nur Komplexität zählt → $T_{\alpha }=\{t_1\}$ (nur Wurzel)
• Mittlere $\alpha$: verschiedene Teilbäume optimal

(7) Auswahl von $\alpha$:

Kein geschlossener Ausdruck — $\alpha$ wird empirisch bestimmt:

• Kreuzvalidierung: teile Trainingsdaten in $k$ Faltungen (typisch $k=10$); baue für jedes $\alpha$ Bäume auf $k-1$ Faltungen und teste auf der $k$-ten; wähle $\alpha$, das den mittleren Test-Fehler minimiert.
• Unabhängiger Test-Set: falls genügend Daten vorhanden.

(8) Linear-Combination-Split:

$\text{Ist }{\sum }_m{a}_m\cdot x_m\le c?$

Was sie sagt: Statt eines Splits auf einem einzelnen Merkmal $x_m$ wird ein Split auf einer Linearkombination getestet. Die Koeffizienten $a_m$ und der Schwellwert $c$ werden aus den Trainingsdaten optimiert.

Warum: Diagonale Klassengrenzen im Merkmalsraum können mit einer einzigen Linearkombination modelliert werden — bei achsenparallelen Splits bräuchte man eine Treppenstruktur aus vielen Rechtecken.

In der Praxis: Selten genutzt, weil sie die Interpretierbarkeit der Baum-Regeln zerstören.

(9) Regressions-Blattvorhersage:

$\bar{y}(t)=\frac{1}{N(t)}{\sum }_{x_n\in t}{y}_n$

Was sie sagt: Bei Regression ist die Blatt-Vorhersage der arithmetische Mittelwert der Zielwerte aller Datenpunkte im Blatt.

Warum: Der Mittelwert minimiert die Summe der quadratischen Abweichungen — er ist die optimale Konstante für den Mean-Squared-Error-Verlust (Proposition 8.10).

(10) Regressions-Impuritätsfunktion:

$R(t)=\frac{1}{N}{\sum }_{x_n\in t}(y_n-\bar{y}(t){)}^2$

Was sie sagt: Die Impuritätsfunktion bei Regression ist die Summe der quadratischen Abweichungen der Zielwerte vom Mittelwert im Knoten (variance bzw. within-node sum of squares).

Analog zum Klassifikations-Fall: Wie bei Gini ist ein Knoten „rein”, wenn alle Datenpunkte den gleichen Zielwert haben ($R(t)=0$). Ansonsten je größer die Streuung, desto größer $R(t)$.

(11) Impuritätsabnahme durch einen Regressions-Split (Def. 8.13):

$\Delta R(s,t)=R(t)-R(t_L)-R(t_R)$

Was sie sagt: Analog zur Klassifikationsformel (1), aber ohne explizite Gewichte $p_L,p_R$ — die Normierung mit dem Gesamt-N in $R(t)=(1/N)\sum (y_n-\bar{y}(t){)}^2$ enthält die Größenanteile bereits implizit. Vergleich: die Klassifikations-Form (1) wählt eine knoten-relative Definition von $i(t)$ und braucht deshalb die Gewichte explizit.

Herleitung der Äquivalenz: Setzt man in (1) für $i(t)$ eine knoten-relative Streuung ein, gewichtet sie mit $p_L=N(t_L)/N(t)$ bzw. $p_R=N(t_R)/N(t)$, und normiert am Ende mit $N(t)/N$, so ergibt sich exakt (11).

(12) Auswahlregel für den besten Regressions-Split (Def. 8.13):

$\Delta R(s^{\ast },t)={\max }_{s\in S}\Delta R(s,t)⟺s^{\ast }=\arg {\max }_{s\in S}\Delta R(s,t)$

Was sie sagt: Der beste Split am Regressions-Knoten $t$ ist derjenige, der die MSE-Impuritätsabnahme maximiert. Formal identisch zur Klassifikations-Auswahlregel (2), nur mit $\Delta R$ statt $\Delta i$. Der impuritätsbasierte Split-Rahmen aus Kap. 3.2 der Arbeit gilt damit unverändert auch für Regression.

---

Zusammenhänge

• Zitat-Index: zitat-index
• Aktueller Zitat-Katalog: zitat-kontexte
• Quellenkarte: BFOS84
• Parallelentwicklung zu: qui86-zusammenfassung (ID3 mit Information Gain — beide Verfahren formalisieren das gleiche rekursive Grundschema)
• Erweitert durch: qui93-zusammenfassung (C4.5 mit Error-based Pruning statt Cost-Complexity)
• Split-Kriterien-Vergleich: rs04-zusammenfassung (Gini vs. Information Gain: 98 % Übereinstimmung)
• Wird Basis für Ensembles: bre96-zusammenfassung (Bagging von CART-Bäumen) und bre01-zusammenfassung (Random Forests)
• Unsere Arbeit: Kap. 2.2 (binäre Form), Kap. 3.1 (Grundschema + N_min + Regressions-Blattvorhersage), Kap. 3.2 (Impuritätsrahmen + Regressions-MSE + Impuritätsabnahme), Kap. 3.3 (Regressionsbäume), Kap. 3.4 (Gini), Kap. 3.8 (Prune instead of stopping), Kap. 5.0 (Medizin / Massenspektren), Kap. 6.2 (Linear-Combination-Splits als Grenze der achsenparallelen Splits)