Bre01 (Breiman 2001) — Deutsche Zusammenfassung

Breiman 2001 — Random Forests

Vollständige Referenz: Leo Breiman, „Random Forests”, Machine Learning 45, S. 5–32, 2001.

Für die Zulassungsarbeit

Kernbotschaft: Random Forests kombinieren Bagging mit zufälliger Merkmalsauswahl an jedem Knoten. Der Ensemble-Fehler hängt von Stärke und Korrelation der Einzelbäume ab; die Out-of-Bag-Schätzung macht separate Testsätze überflüssig, und die Permutation Importance quantifiziert Merkmalswichtigkeit.

Zitat-Landkarte (Stand 2026-08-11)

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

Hinweis Kap. 4.5: Der frühere \beleg{Bre01 Kap. 10} (Permutation Importance) wurde am 2026-08-09 aus dem Manuskript entfernt. Section 10 „Exploring the random forest mechanism” (S. 20 ff.) beschreibt die Permutation-Importance-Prozedur zwar, ist aber für den PNRB15-Manuskript-Scope nicht mehr essentiell.

\cite-Stellen (verifiziert, Kap. 2.4 + Kap. 4.3)

Manuskript-Kap. / Zeile	Aussage	Zitatmarker
Kap. 2.4 Z. 323	Bibliografische Nennung Breiman 2001 (Random Forests) im Zeitstrahl	\cite{Bre01}
Kap. 4.3 Z. 115	Random-Forest-Definition: Voting + Namensgebung, formaler Oberbegriff (iid Zufallsvektoren ${\Theta }_k$)	\cite[S.~6]{Bre01}
Kap. 4.3 Z. 120	Merkmalseinschränkung an Knoten (Forest-RI) + Prinzip „minimize correlation while maintaining strength”	\cite[S.~10]{Bre01}
Kap. 4.3 Z. 121	Random-Forest-Bäume werden nicht gestutzt	\cite[S.~11, M1]{Bre01}
Kap. 4.3 Z. 128	Ensemblefehler hängt von Baumstärke + paarweiser Korrelation ab (identische Passage wie Z. 120)	\cite[S.~10]{Bre01}
Kap. 4.3 Z. 167	1/3-Regel: ungefähr ein Drittel der Trainingsdatenpunkte fehlt in jeder Bootstrap-Stichprobe	\cite[S.~11, M2]{Bre01}
Kap. 4.3 Z. 172	OOB-Kernpassage: Aggregation nur über Bäume, in deren Bootstrap-Stichprobe der Datenpunkt fehlt	\cite[S.~11, M1]{Bre01}
Kap. 4.3 Z. 175	OOB-Fehlerschätzung ist im Unterschied zur Kreuzvalidierung erwartungstreu	\cite[S.~11, M2]{Bre01}

(Kap. 5.0 Z. 11 nutzt \cite[S.~12, Tab.~1]{Bre01} für die Datensatz-Zusammenstellung. Diese Belegstelle bleibt hier bewusst offen, weil Kap. 5 nach der PNRB15-Vollrelesung neu formuliert wird und der Cite ggf. dort ergänzt/verändert wird.)

\cite[S.~6]{Bre01} — Random-Forest-Definition + Voting (Kap. 4.3 Z. 115)

Manuskript-Aussage: Random Forests wurden 2001 von Breiman als Weiterentwicklung von Bagging eingeführt; nach dem Aufbau vieler Bäume auf Bootstrap-Stichproben werden ihre Vorhersagen durch Voting aggregiert.

Originalwortlaut (S. 6):

„After a large number of trees is generated, they vote for the most popular class. We call these procedures random forests.” + „Definition 1.1. A random forest is a classifier consisting of a collection of tree-structured classifiers $\{h(\mathbf{x},{\Theta }_k),k=1,\dots \}$ where the $\{{\Theta }_k\}$ are independent identically distributed random vectors and each tree casts a unit vote for the most popular class at input $\mathbf{x}$.”

Deutsche Übersetzung: „Nachdem eine große Anzahl an Bäumen erzeugt wurde, stimmen sie für die häufigste Klasse ab. Wir nennen diese Verfahren Random Forests.” + „Definition 1.1. Ein Random Forest ist ein Klassifikator, bestehend aus einer Sammlung baumstrukturierter Klassifikatoren $\{h(\mathbf{x},{\Theta }_k),k=1,\dots \}$, wobei die $\{{\Theta }_k\}$ unabhängig identisch verteilte Zufallsvektoren sind und jeder Baum eine Einzelstimme für die häufigste Klasse an Eingabe $\mathbf{x}$ abgibt.”

Begründung Passung: Belegt Namensgebung + Voting-Prinzip + formalen Rahmen. Definition 1.1 ist Oberbegriff; die konkrete Merkmalseinschränkung als Instanz („Forest-RI”) wird auf S. 10 präzisiert.

\cite[S.~10]{Bre01} — Merkmalseinschränkung + Stärke/Korrelation-Prinzip (Kap. 4.3 Z. 120 und Z. 128)

Manuskript-Aussagen: (Z. 120) Merkmalseinschränkung an Knoten; (Z. 128) Ensemblefehler abhängig von Stärke + Korrelation.

Originalwortlaut (S. 10, Section 3 „Using random features”):

„To improve accuracy, the randomness injected has to minimize the correlation $\bar{\rho }$ while maintaining strength. The forests studied here consist of using randomly selected inputs or combinations of inputs at each node to grow each tree.”

Deutsche Übersetzung: „Um die Genauigkeit zu verbessern, muss die injizierte Zufälligkeit die Korrelation $\bar{\rho }$ minimieren und dabei die Stärke beibehalten. Die hier untersuchten Random Forests verwenden zufällig ausgewählte Merkmale oder Kombinationen von Merkmalen an jedem Knoten zur Baumkonstruktion.”

Begründung Passung: Ein Marker deckt zwei Manuskript-Aussagen ab: die konkrete Merkmalseinschränkung „at each node” (Z. 120) und das Wirkprinzip „minimize correlation while maintaining strength” (Z. 128).

\cite[S.~11, M1]{Bre01} — OOB-Kernpassage + „not pruned” (Kap. 4.3 Z. 121 und Z. 172)

Manuskript-Aussagen: (Z. 121) Bäume nicht gestutzt; (Z. 172) OOB-Prinzip.

Originalwortlaut (S. 11, Section 3.1):

„In my experiments with random forests, bagging is used in tandem with random feature selection. Each new training set is drawn, with replacement, from the original training set. Then a tree is grown on the new training set using random feature selection. The trees grown are not pruned. […] For each $y,\mathbf{x}$ in the training set, aggregate the votes only over those classifiers for which $T_k$ does not contain $y,\mathbf{x}$. Call this the out-of-bag classifier. Then the out-of-bag estimate for the generalization error is the error rate of the out-of-bag classifier on the training set.”

Deutsche Übersetzung: „In meinen Experimenten mit Random Forests wird Bagging zusammen mit zufälliger Merkmalsauswahl verwendet. Jede neue Trainingsmenge wird mit Zurücklegen aus der Original-Trainingsmenge gezogen. Dann wird auf der neuen Trainingsmenge ein Baum mit zufälliger Merkmalsauswahl aufgebaut. Die Bäume werden nicht gestutzt. […] Für jedes $y,\mathbf{x}$ in der Trainingsmenge werden die Stimmen nur über jene Klassifikatoren aggregiert, für die $T_k$ nicht $y,\mathbf{x}$ enthält. Nenne dies den Out-of-Bag-Klassifikator. Dann ist die Out-of-Bag-Schätzung des Generalisierungsfehlers die Fehlerrate dieses Klassifikators auf der Trainingsmenge.”

Begründung Passung: M1 deckt zwei Manuskript-Aussagen: „trees not pruned” (Z. 121) und OOB-Prinzip (Z. 172). Zusatzbonus: „bagging in tandem with random feature selection” bestätigt den Manuskript-Aufbau in Kap. 4.3 Z. 120.

\cite[S.~11, M2]{Bre01} — 1/3-Regel + Unbiased-Argument (Kap. 4.3 Z. 167 und Z. 175)

Manuskript-Aussagen: (Z. 167) 1/3-Regel; (Z. 175) OOB erwartungstreu, im Unterschied zu Kreuzvalidierung.

Originalwortlaut (S. 11, weiter unten in Section 3.1):

„In each bootstrap training set, about one-third of the instances are left out. […] But unlike cross-validation, where bias is present but its extent unknown, the out-of-bag estimates are unbiased.”

Deutsche Übersetzung: „In jeder Bootstrap-Trainingsmenge werden etwa ein Drittel der Datenpunkte weggelassen. […] Im Gegensatz zur Kreuzvalidierung, bei der ein Bias vorhanden ist, dessen Ausmaß aber unbekannt bleibt, sind die Out-of-Bag-Schätzungen erwartungstreu.”

Begründung Passung: M2 deckt beide Aussagen: 1/3-Regel (ersetzt die frühere Fußnoten-Herleitung $(1-1/N{)}^N\to 1/e$) und Erwartungstreue-Kontrast zu Kreuzvalidierung.

\cite{Bre01} — Bibliografische Nennung im Zeitstrahl (Kap. 2.4 Z. 323)

Manuskript-Aussage: Nennung von Breiman 2001 (Random Forests) im chronologischen Zeitstrahl. Originalwortlaut: Bibliografische Nennung ohne Seitenbezug. Begründung Passung: Reine bibliografische Nennung der Primärquelle im Zeitstrahl-Kontext.

---

Abstract

Vier Kern-Aussagen: (1) Bäume mit unabhängigen Zufallsvektoren, (2) Ensemble-Fehler konvergiert (kein Overfitting durch Baumzahl), (3) Fehler hängt von Stärke + Korrelation ab, (4) OOB macht Testsätze überflüssig.

---

Section 1. Random Forests

1.1 Introduction

Verweise auf frühere Ensemble-Ansätze (Dietterich Random Split Selection 1998, Ho Random Subspace 1998, Amit & Geman 1997). Gemeinsames Muster: für jeden Baum $k$ ein unabhängiger Zufallsvektor ${\Theta }_k$; Klassifikator $h(x,{\Theta }_k)$.

Definition 1.1

Ein Random Forest ist ein Klassifikator, der aus einer Sammlung von baumstrukturierten Klassifikatoren $\{h(x,{\Theta }_k),k=1,\dots \}$ besteht, wobei die $\{{\Theta }_k\}$ unabhängig identisch verteilte Zufallsvektoren sind und jeder Baum einen Einheits-Stimmzettel für die häufigste Klasse an der Eingabe $x$ abgibt.

1.2 Outline of paper — Stärke und Korrelation

Die Genauigkeit eines Random Forest hängt ab von der Stärke der einzelnen Baum-Klassifikatoren und einem Maß der Abhängigkeit zwischen ihnen. Das ist der Beleg für die Aussage der Arbeit „der Ensemble-Fehler hängt von zwei Größen ab, der Stärke der einzelnen Bäume und ihrer paarweisen Korrelation; eine geringere Korrelation senkt den Ensemble-Fehler auch dann, wenn die einzelnen Bäume dadurch etwas schwächer werden.”

---

Section 2. Characterizing the Accuracy of Random Forests

Mathematisch dichteste Section: Konvergenz-Beweis (Section 2.1, starkes Gesetz der großen Zahlen), Herleitung des Bounds $P{E}^{\ast }\le \bar{\rho }(1-s^2)/s^2$ (Theorem 2.3). Für die Arbeit wichtig ist die Aussage Stärke↑ + Korrelation↓ = kleinerer Fehler. Die Formeln werden hier nur zur Vollständigkeit im Referenzblatt geführt.

---

Section 3. Using Random Features

Warum überhaupt zufällige Merkmalsauswahl? Um die Korrelation zwischen den Bäumen zu senken — dann greift der Bound aus Section 2.

3.1 Out-of-Bag-Fehlerschätzung

Erinnerung aus Bre96a: Beim Bootstrap-Sampling fehlt jeder Datenpunkt in ~1/3 der Bootstrap-Stichproben. Diese Datenpunkte sind für den jeweiligen Baum „out of bag”.

Random Forests machen das systematisch: Für jeden Datenpunkt $(y,x)$ im Trainingssatz aggregiere nur die Stimmen der Bäume, für die $(y,x)$ nicht in der Bootstrap-Stichprobe war. Das ergibt einen Out-of-Bag-Klassifikator und einen Out-of-Bag-Fehler.

Kernaussage: Der Out-of-Bag-Schätzer ist so genau wie ein Test-Set derselben Größe wie die Trainingsmenge. Damit entfällt die Notwendigkeit eines separaten Test-Sets.

---

Section 4. Random Forests using Random Input Selection: Forest-RI

Forest-RI

Der einfachste Random Forest mit zufälligen Merkmalen entsteht durch Auswahl einer kleinen Gruppe von Input-Variablen an jedem Knoten. Der Baum wird nach CART-Methodik bis zur Maximalgröße gewachsen und nicht geprunt. Dieses Verfahren wird als Forest-RI bezeichnet.

Wahl von F: Zwei getestete Werte: $F=1$ oder $F=\lfloor {\log }_{2}M+1\rfloor$, wobei $M$ die Gesamtzahl der Input-Variablen ist.

Datensatz-Übersicht Table 1

Table 1 „Data set summary” listet alle evaluierten Datensätze: Glass, Breast cancer, Diabetes, Sonar, Vowel, Ionosphere, Vehicle, Soybean, German credit, Image, Ecoli, Votes, Liver, Letters, Sat-images, Zip-code, Waveform. Belegt die im Fließtext aufgezählte Anwendungsbandbreite (Medizin: Diabetes/Ionosphere/Breast Cancer; Signalklassifikation: Vowel/Waveform/Zip-Code/Sat-Images; Umwelt/Bonität: Soybean/German Credit).

---

Section 5. Random Forests using Linear Combinations of Inputs: Forest-RC

Variante mit Linearkombinationen von $L$ Merkmalen mit zufälligen Koeffizienten. Die konzeptuelle Verbindung zu BFOS84 (Linear Combination Splits) läuft im Ausblick über BFOS84.

---

Sections 6–9. Empirische Analysen

Detaillierte experimentelle Untersuchungen zu Stärke/Korrelation, AdaBoost-Analogie, Rausch-Robustheit, viele schwache Inputs. Kernpunkt: Random Forests sind robust gegenüber Rauschen und funktionieren auch bei vielen irrelevanten Merkmalen.

---

Section 10. Exploring the Random Forest Mechanism — Variable Importance

Ablauf der Permutations-Importance:

1. Nach dem Training: für jedes Merkmal $m$ einzeln
2. In den Out-of-Bag-Datenpunkten die Werte des $m$-ten Merkmals zufällig permutieren
3. Fehler-Anstieg gegenüber dem OOB-Fehler = Importance von $m$

---

Zusammenfassung — was Du wissen musst

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

1. Random Forests = viele Bäume, jeder auf einer Bootstrap-Stichprobe (wie Bagging), zusätzlich an jedem Knoten nur eine zufällige Teilmenge der Merkmale zur Split-Wahl.
2. Der Ensemble-Fehler hängt von Stärke (wie gut jeder Baum) und Korrelation (wie ähnlich die Bäume) ab. Random Forests senken die Korrelation, auch wenn dadurch die Bäume etwas schwächer werden — netto sinkt der Ensemble-Fehler.
3. Mehr Bäume verschlechtern den Random Forest nicht (kein Overfitting durch Baumanzahl), sondern konvergieren gegen einen Grenzwert.
4. Out-of-Bag-Fehlerschätzung liefert eine kostenlose Fehlerschätzung während des Trainings — kein separater Testsatz oder Kreuzvalidierung nötig.
5. Permutations-Importance misst die Wichtigkeit eines Merkmals: Fehleranstieg nach zufälliger Vertauschung seiner Werte in den Out-of-Bag-Daten.

Beziehung zu Bagging:

• Random Forest = Bagging + zufällige Merkmalsauswahl an jedem Knoten
• Wenn F = M (alle Merkmale zur Split-Wahl), reduziert sich Random Forest zu reinem Bagging
• Die zufällige Merkmalsauswahl ist der wesentliche Zusatz über Bagging hinaus

---

Formales Referenzblatt

Symboltabelle

Symbol	Aussprache / Name	Bedeutung
$h(x,{\Theta }_k)$	„h von x komma Theta-k” (Theta = griechisch Θ)	k-ter Baum-Klassifikator im Ensemble. $x$ ist die Eingabe, ${\Theta }_k$ ist der Zufallsvektor, der Bau des Baums bestimmt (welche Bootstrap-Stichprobe, welche Merkmale).
${\Theta }_k$	„Theta-k”	Zufallsvektor für Baum k — kodiert die Zufallsentscheidungen (Bootstrap + Merkmalsauswahl). Alle ${\Theta }_k$ sind unabhängig, identisch verteilt (i.i.d.).
$k$	„k”	Baum-Index ($k=1,2,\dots ,K$)
$K$	„großes K”	Anzahl der Bäume im Random Forest (in Breimans Experimenten typisch 100)
$X,Y$	„X, Y”	Zufallsvariablen für Eingabe (Merkmalsvektor) und wahre Klasse
$x,y$	„x, y”	Konkrete Werte einer Beobachtung
$I(\cdot )$	„Indikatorfunktion”	Gibt 1 wenn Bedingung wahr, sonst 0
${\mathrm{av}}_k$	„average über k”	Mittelwert über alle Bäume $k=1,\dots ,K$
$mg(X,Y)$	„margin von X, Y”	Margin-Funktion für ein Ensemble: wie deutlich das Ensemble die richtige Klasse gegenüber der zweitbesten Klasse bevorzugt. Wertebereich $[-1,+1]$.
$mr(X,Y)$	„margin r” (r = random forest)	Random-Forest-Margin — Grenzwert von $mg$ für unendlich viele Bäume
$rmg(\Theta ,X,Y)$	„raw margin”	Rohe Margin eines einzelnen Baums
$\hat{ȷ}(X,Y)$	„j-Hut”	Diejenige falsche Klasse (nicht $Y$), für die das Ensemble am häufigsten stimmt
$P{E}^{\ast }$	„P-E-Stern”	Verallgemeinerungsfehler — Wahrscheinlichkeit falscher Klassifikation auf neuen Daten
$s$	„s” (s = strength)	Stärke des Ensembles — durchschnittliche Margin über alle Datenpunkte
$\bar{\rho }$	„rho quer” (griechisch rho ρ)	Mittlere Korrelation zwischen den Bäumen
$\mathrm{var}(mr)$	„Varianz von mr”	Varianz der Random-Forest-Margin
$\mathrm{sd}(\Theta )$	„Standard-Deviation”	Standardabweichung der Raw-Margin bei festem $\Theta$
$c/s^2$	„c über s Quadrat”	Kenngröße = Korrelation / Stärke²
$F$	„großes F”	Anzahl der zufällig gewählten Merkmale pro Knoten-Split. Typische Werte: $F=1$ oder $F=\lfloor {\log }_{2}M+1\rfloor$.
$M$	„großes M”	Gesamtzahl der Input-Merkmale in den Daten
$L$	„großes L”	(nur in Forest-RC) Anzahl der Merkmale, die zu einer Linearkombination zusammengefasst werden
$N$	„großes N”	Anzahl der Datenpunkte in der Trainingsmenge
$T$	„großes T”	Trainingsmenge (englisch training set)
$T_k$	„T-k”	k-te Bootstrap-Stichprobe
$j$	„kleines j”	Klassenindex
$\rho (\Theta ,{\Theta }^{\prime })$	„rho von Theta, Theta-Strich”	Korrelation zwischen zwei bestimmten Bäumen mit Zufallsvektoren $\Theta$ und ${\Theta }^{\prime }$

Formeln und ihre Bedeutung

(1) Margin-Funktion:

$mg(X,Y)={\mathrm{av}}_{k}I(h_k(X)=Y)-{\max }_{j\ne Y}{\mathrm{av}}_{k}I(h_k(X)=j)$

Was sie sagt: Anteil der Bäume, die die richtige Klasse vorhersagen, minus Anteil für die häufigste falsche Klasse.

(2) Verallgemeinerungsfehler:

$P{E}^{\ast }=P_{X,Y}(mg(X,Y)<0)$

(3) Random-Forest-Margin:

$mr(X,Y)=P(h(X,\Theta )=Y)-{\max }_{j\ne Y}P(h(X,\Theta )=j)$

(4) Stärke:

$s={\mathbb{E}}_{X,Y}mr(X,Y)$

(5) Chebyshev-Ungleichung als Bound:

$P{E}^{\ast }\le \frac{\mathrm{var}(mr)}{s^2}$

(6) Raw Margin:

$rmg(\Theta ,X,Y)=I(h(X,\Theta )=Y)-I(h(X,\Theta )=\hat{ȷ}(X,Y))$

(7) Theorem 2.3 — der zentrale Bound:

$P{E}^{\ast }\le \frac{\bar{\rho }(1-s^2)}{s^2}$

Was sie sagt: Der Verallgemeinerungsfehler ist beschränkt durch mittlere Korrelation $\bar{\rho }$ zwischen den Bäumen (kleiner ist besser), gedämpft durch Stärke² (größer ist besser).

Der Zielkonflikt: Wenn man versucht, $\bar{\rho }$ zu senken (mehr Zufälligkeit), sinkt oft auch $s$. Netto wird der Ensemble-Fehler trotzdem kleiner — der Kern-Trick von Random Forests.

(8) c/s²-Verhältnis:

$c/s^2=\frac{\bar{\rho }}{s^2}$

(9) Wahl von F in Forest-RI:

$F=1\text{oder}F=\lfloor {\log }_{2}M+1\rfloor$

(10) Permutations-Importance:

$\text{Importance}(m)=\frac{{\text{Fehler}}_{\text{permutiert}}(m)-{\text{Fehler}}_{\text{OOB}}}{{\text{Fehler}}_{\text{OOB}}}\times 100\%$

Was sie sagt: Prozentualer Anstieg der Fehlklassifikations-Rate, wenn die Werte des Merkmals $m$ in den Out-of-Bag-Datenpunkten zufällig durcheinandergewürfelt werden.

Warum sinnvoll: Wenn das Merkmal wichtig ist, zerstört die Permutation seine Information und der Fehler steigt deutlich.

---

Zusammenhänge

• Zitat-Index: zitat-index
• Aktueller Zitat-Katalog: zitat-kontexte
• Quellenkarte: Bre01
• Baut auf: bre96-zusammenfassung (Bagging als direkter Vorläufer)
• Grundverfahren: bfos84-zusammenfassung (CART als Basis-Baum-Algorithmus)
• Anwendung: pnrb15-zusammenfassung (Random Forests in der Predictive-Maintenance-Fallstudie)
• Unsere Arbeit: Kap. 4.3 (Random-Forest-Definition, Stärke/Korrelation, OOB, Forest-RI, Permutation Importance), Kap. 4.4 (Interpretierbarkeitskompensation), Kap. 5.0 (Datensatz-Bandbreite)