Ein Random Forest (deutsch Zufallswald) ist ein Klassifikations- und Regressionsverfahren, das aus mehreren unkorrelierten Entscheidungsbäumen besteht. Alle Entscheidungsbäume sind unter einer bestimmten Art von Randomisierung während des Lernprozesses gewachsen. Die einzelnen Bäume werden dann zu einem Ensemble, dem Random Forest, kombiniert. Die Ergebnisse der einzelnen Bäume werden im Ensemble mit einer Aggregierungsfunktion zusammengefasst. Häufig verwendete Aggregierungsfunktionen sind der Mittelwert, Median, Mehrheitswahl und viele weitere (siehe unten). Random Forests werden für maschinelles Lernen eingesetzt.

Geschichte

Der Begriff Random Forest wurde von Leo Breiman im Jahr 2001 geprägt. Er erforschte verschiedene Methoden der Randomisierung von Entscheidungsbäumen, beispielsweise mittels Bagging oder Boosting. Seiner Arbeit ging die Forschung von Tin Kam Ho im Jahr 1995 voraus.

Algorithmen

Für jeden Entscheidungsbaum im Random Forest wird folgender Algorithmus angewandt werden:

1. Es werden ${\displaystyle n}$ Bootstrap-Samples aus dem Trainingsdatensatz durch Ziehen mit Zurücklegen gezogen.
2. Von den ${\displaystyle M}$ Merkmalen (Features oder Dimensionen) der Trainingsdaten werden an jedem Knoten im Baum ${\displaystyle m\ll M}$ Merkmale zufällig gewählt, die als Kriterium für den Schnitt (Split) infrage kommen sollen.
3. Die anschließende Auswahl eines Merkmals aus dieser Menge sowie sein Solit-Wert kann zum Beispiel mittels der Minimierung der Entropie oder des Mean-Squared Errors geschehen, siehe CART (Algorithmus)
4. Der Baum wird voll ausgebaut und nicht zurückgeschnitten (Pruning).

Da jeder Baum des Random-Forest unabhängig von den anderen Bäumen aufgebaut wird, kann die Antwort der einzelnen Bäume unterschiedlich ausfallen. Um zu einer Gesamt-Vorhersage zu gelangen wird über die Vorhersage der einzelnen Bäume aggregiert:

• Bei der Klassifikation kann einfach die Klasse zurückgeliefert werden, die am häufigsten gewählt wurde (Majority-Voting). Wenn es mehrere Klassen gibt, die am häufigsten gewählt wurden, muss man sich anderweitig für eine entscheiden.
• Bei der Regression kann beispielsweise der Mittelwert der Vorhersagen gebildet werden

Es gibt viele verschiedene Hyperparameter beim Training, eins Random Forest. Dazu zählt unter anderem, welche Entscheidungsbäume verwendet werden und ob eine maximale Tiefe der Bäume vorgegeben wird.

Bosch et al. speichern zusätzlich in jedem Blatt die A-posteriori-Wahrscheinlichkeiten der Klassen, mit denen sie das Blatt finden. Diese Wahrscheinlichkeiten werden anschließend bei der Klassifikation berücksichtigt. Dadurch kann die Fehlerrate in ihrer Anwendung verringert werden.

Eigenschaften

Eine große Anzahl unkorrelierter Bäume macht genauere Vorhersagen möglich als ein einzelner Entscheidungsbaum. Dies liegt daran, dass durch Aggregierung unkorrelierter Ergebnisse die Streuung des aggregierten Wertes sinkt (vergleiche Standardfehler des Mittelwertes). Da die einzelnen Bäume unabhängig wachsen (da sie jeweils das beste Merkmal unter einer zufälligen Teilmenge von Merkmalen als Split benutzen), sind ihrer Vorhersagen per Konstruktion nicht perfekt korreliert.

Verbindung zu Nächste-Nachbar Algorithmem

Random Forests besitzen Änhlichkeit zu „potential nearest neighbor algorithms“. Hieraus folgt: Betrachtet man ${\displaystyle n}$ unabhängige und identisch verteilte Werte ${\displaystyle (x_{i},y_{i})}$ eines zufälligen Eingabevektors ${\displaystyle X:=(X^{(1)},\ldots ,X^{(d)})\in R^{d}}$ und einer zufälligen Antwortvariablen ${\displaystyle X\in R}$. Will man die Regressionsfunktion ${\displaystyle g(x):=\operatorname {E} (Y\mid X=x)}$ schätzen, dann kann man für jeden Punkt ${\displaystyle x_{0}\in R^{d}}$ eine Schätzfunktion ${\displaystyle {\hat {g}}(x_{0})}$ von ${\displaystyle g(x_{0})}$ definieren, die auf den Funktionswerten ${\displaystyle (x_{i},y_{i})}$ basiert. Der mittlere quadratische Abweichung bei ${\displaystyle x_{0}}$ ist

${\displaystyle \operatorname {MSE} ({\hat {g}}(x_{0}))=\operatorname {E} (({\hat {g}}(x_{0})-g(x_{0}))^{2})=(\operatorname {E} ({\hat {g}}(x_{0})-g(x_{0})))^{2}+\operatorname {Var} ({\hat {g}}(x_{0}))}$

Bei einer gegebenen Metrik schätzt der K-Nearest-Neighbor-Algorithmus den Wert ${\displaystyle g(x_{0})}$, indem er die ${\displaystyle k}$ Punkte betrachtet, die ${\displaystyle x_{0}}$ am nächsten sind:

${\displaystyle {\hat {g}}(x_{0})=\sum _{i=1}^{n}w_{i}\cdot y_{i}}$

Dabei ist das Gewicht ${\displaystyle w_{i}}$ gleich ${\displaystyle {\tfrac {1}{k}}}$ für die ${\displaystyle k}$ nächsten Nachbarn von ${\displaystyle x_{0}}$ und gleich 0 für alle anderen Punkte.

Betrachtet man die Schätzfunktion ${\displaystyle {\hat {g}}}$ von ${\displaystyle g}$ für das Regressionsproblem ${\displaystyle Y=g(X)+\epsilon }$ mit ${\displaystyle \operatorname {E} (\epsilon )=0}$ und ${\displaystyle \operatorname {Var} (\epsilon )=\sigma ^{2}}$ auf der Grundlage einer Zufallsstichprobe ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2}),\ldots ,(x_{n},y_{n})}$ und nimmt an, dass die Zufallsvariable ${\displaystyle X}$ eine Wahrscheinlichkeitsverteilung in ${\displaystyle [0,1]^{d}}$ hat. Ist die ${\displaystyle {\hat {g}}}$ Schätzfunktion eines nicht adaptiven Random Forest, dessen Endknoten die Größe ${\displaystyle k}$ haben, dann gibt es eine Konstante ${\displaystyle \Lambda _{3}>0}$, sodass für alle ${\displaystyle n}$ und alle Funktionswerte ${\displaystyle x_{0}\in [0,1]^{d}}$ folgende Abschätzung für die mittlere quadratische Abweichung gilt:

${\displaystyle \operatorname {MSE} ({\hat {g}}(x_{0}))\geq \Lambda _{3}\cdot k^{-1}\cdot (\log(n))^{-(d-1)}}$

Das bedeutet, dass ${\displaystyle k^{-1}\cdot (\log(n))^{-(d-1)}}$ eine untere Schranke der Konvergenzgeschwindigkeit der mittleren quadratischen Abweichung von nicht adaptiven Random Forests ist. Andererseits ist bekannt, dass die optimale Konvergenzgeschwindigkeit des mittleren quadratischen Fehlers bei Regressionsproblemen gleich ${\displaystyle n^{-{\tfrac {2\cdot m}{2\cdot m+d}}}}$ ist.

Weblinks

• Random Forests, Homepage von Leo Breiman und Adele Cutler

Einzelnachweise

1. 1 2 Breiman L., Random forests. In: Machine Learning, 2001, 45(1), Seiten 5–32, doi:10.1023/A:1010933404324
2. ↑ Tin Kam Ho, Random Decision Forests, Proceedings of the 3rd International Conference on Document Analysis and Recognition, Montreal, Canada, August 14-18, 1995, 278-282, doi:10.1109/ICDAR.1995.598994.
3. ↑ Andy Liaw & Matthew Wiener (2002): "Classification and Regression by random Forest", R News 2/3: 18-22.
4. ↑ Anna Bosch, Andrew Zisserman, Xavier Muñoz: Image classification using random forests and ferns. ICCV 2007. IEEE 11th International Conference on Computer Vision, Seiten 1–8, doi:10.1109/ICCV.2007.4409066.
5. ↑ IBM: What is random forest?
6. ↑ Yi Lin, Yongho Jeon: Random Forests and Adaptive Nearest Neighbors. In: Journal of the American Statistical Association. Band 101, Nr. 474, 1. Juni 2006, ISSN 0162-1459, S. 578–590, doi:10.1198/016214505000001230 (tandfonline.com).