Random Forest

Ein Random Forest.

Random Forest (Vorlage:DeS) oder Random Decision Forest ist ein Verfahren, das beim maschinellen Lernen eingesetzt wird. Es handelt sich um eine Ensemblemethode, die bei Klassifikations- und Regressionsverfahren eingesetzt wird. Beim Training werden mehrere möglichst unkorrelierte Entscheidungsbäume erzeugt. Dabei wird jeder Entscheidungsbaum mit einer anderen, zufällig ausgewählten Stichprobe der Trainingsdaten trainiert. Zusätzlich berücksichtigt jeder Baum für die Aufteilung der Objekte aus seiner Stichprobe an jedem Knoten nur eine zufällig gewählte Teilmenge aller Merkmale. Anschließend werden alle Bäume zu einem Ensemble, dem Random Forest bzw. Wald (Graphentheorie), kombiniert.

Das Ergebnis des Random Forests wird mit Hilfe einer Aggregatfunktion aus den Ergebnissen aller Bäume gebildet. Bei Klassifikationsaufgaben entspricht das Ergebnis der Klasse, die die meisten Bäume gewählt haben. Bei Regressionsaufgaben wird das Ergebnis als Mittelwert der Ergebnisse aller Bäume gebildet. Der Einsatz von Random Forests korrigiert Abweichungen, die die Ergebnisse von einzelnen Entscheidungsbäumen aufgrund von Überanpassung aufweisen.

Random Forests ist außerdem ein von Leo Breiman und Adele Cutler eingetragenes Warenzeichen für ein gleichnamiges Softwarepaket.

Geschichte

Der erste Artikel, der die Eigenschaften von Random Decision Forests untersucht, wurde von Tin Kam Ho im Jahr 1995 veröffentlicht. Ho untersuchte Random Decision Forests, die sie aus mehreren Entscheidungsbäumen bildete. Dabei gehörten alle Bäume zu einer bestimmten Art von Entscheidungsbäumen (Aufteilung an einer schiefen Hyperebene). Sie stellte fest, dass diese Random Decision Forests mit zunehmendem Wachstum weiter an Genauigkeit gewinnen können, ohne dass es dabei zu einer Überanpassung kommt, falls jeder einzelne Entscheidungsbaum so eingeschränkt wird, dass er für die Aufteilung an jedem Knoten nur eine zufällig gewählte Teilmenge aller Merkmale berücksichtigt. Dieses Verfahren nannte sie Random Subspace Methode. In einer späteren Arbeit zeigte Ho, dass auch Random Decision Forests aus anderen Arten von Entscheidungsbäumen bessere Vorhersagen liefern als einzelne Entscheidungsbäume.

Die Grundlagen für das heutzutage als Random Forest bekannte Verfahren wurden im Jahr 2001 von Leo Breiman veröffentlicht. Der Artikel beschreibt ein Verfahren, das unkorrelierte Bäume erzeugt. Dabei optimiert Breiman den CART-Algorithmus mit der Random Subspace Methode und er erzeugt mit Bagging für jeden Baum eine andere Stichprobe des Trainingsdatensatzes. Außerdem beschreibt er, wie man den Vorhersagefehler für neue Daten (Vorlage:EnS) abschätzen kann und wie man die Bedeutung, die einzelne Merkmale für das Ergebnis haben, messen kann.

Grundlagen

Maschinelles Lernen mit Entscheidungsbäumen

Ein Entscheidungsbaum besteht aus Knoten und Blättern. Dabei repräsentiert jeder Knoten eine logische Regel und jedes Blatt eine Antwort auf das Entscheidungsproblem. Beim maschinellen Lernen werden die Regeln aus einem Datensatz mit Trainingsdaten gelernt. Für jeden Knoten wird eine Regel gelernt, die bestimmt, wie die Objekte aus den Trainingsdaten auf die beiden Folgeknoten aufgeteilt werden. Der CART-Algorithmus ist ein bekannter Algorithmus, der einen Binärbaum erzeugt, der zur Lösung von Aufgaben zur Klassifikation oder Regression eingesetzt werden kann.

Das Konzept der Entscheidungsbäume ist einfach und mächtig. Der Trainingsaufwand ist gering. Es ist unempfindlich gegenüber Ausreißern und irrelevanten Merkmalen und funktioniert deshalb gut mit Daten, die nicht aufwendig aufbereitet wurden. Deshalb werden Entscheidungsbäume gerne beim Data-Mining eingesetzt. Allerdings sind solche Bäume nur selten genau. Insbesondere tendieren sehr tiefe Bäume dazu, fehlerhafte Muster zu erlernen. Sie passen sich ihren Trainingsmengen zu sehr an und zeigen dann eine geringe Verzerrung und eine sehr hohe Varianz. Siehe auch Verzerrung-Varianz-Dilemma.

Ein Random Forest mittelt über mehrere tiefe Entscheidungsbäume, die auf verschiedenen Teilen desselben Trainingssatzes trainiert wurden. Dadurch wird die Varianz verringert und in der Regel die Leistung des endgültigen Modells erheblich gesteigert. Die Nachteile bestehen in einer geringen Erhöhung der Verzerrung und einem komplexeren Modell.

Bagging

Illustration zum Training eines Random Forest Modells mit Bagging. Aus den Trainingsdaten (hier mit 250 Zeilen und 100 Spalten) werden durch Ziehen mit Zurücklegen zufällig B Datensätze des Umfangs n gezogen. Danach wird mit jedem der B Datensätze je ein Entscheidungsbaum trainiert. Anschließend werden die Ergebnisse der B Bäume gemittelt, um das endgültige Ergebnis zu erhalten.

Der Trainingsalgorithmus von Random Forests verwendet das Verfahren Bootstrap aggregating, auch Bagging genannt.

Zunächst werden aus dem Originaldatensatz, der für das Training dient, mit dem Bootstrapping-Verfahren B neue Stichproben des Umfanges $n$ durch Ziehen mit Zurücklegen erzeugt. Mit den neuen Stichproben werden $B$ Vorhersagemodelle $m_i$ ($i=1,\dots ,B$) trainiert. Für einen Wert $x$ ergeben sich dann $B$ Vorhersagewerte $m_i(x)$.

Nach dem Training können Vorhersagen für einen neuen Wert $x^{\prime }$ aus dem Durchschnitt der Vorhersagen der einzelnen Bäume gebildet werden.

$\hat{f}=\frac{1}{B}\sum _{b=1}^B{f}_b(x^{\prime })$

oder, bei Klassifikatoren, durch die Mehrheitsentscheidung aller Bäume.

Diese Methode verbessert das Ergebnis, weil sie die Varianz verringert. Die Vorhersagen einzelner Bäume sind viel anfälliger für Rauschen in den Trainingsdaten als der Durchschnittswert von Bäumen, die nicht miteinander korrelieren. Das Bootstrapping-Verfahren ermöglicht es durch die Erzeugung unterschiedlicher Trainingsdatensätze, Bäume zu erzeugen, die nicht miteinander korrelieren.

Außerdem kann man die Größe des Vorhersagefehlers (siehe Konfidenzintervall) an der Stelle $x^{\prime }$ mithilfe der Standardabweichungen der einzelnen Bäume einfach abschätzen:

$\sigma =\sqrt{\frac{\sum _{b=1}^B(f_b(x^{\prime })-\hat{f}{)}^2}{B-1}}.$

Die Anzahl $B$ der Bäume kann frei gewählt werden. Ein typischer Wert liegt bei mehreren hundert oder tausend Bäumen. Ein optimaler Wert kann mit Kreuzvalidierungsverfahren bestimmt werden oder durch die Beobachtung des out-of-bag errors.

Vom Bagging zum Random Forest

Oben wird das ursprüngliche Bagging-Verfahren beschrieben, das mehrere zufällige Stichproben zum Trainieren von Entscheidungsbäumen zieht. Die Erfinder des Random-Forest-Verfahrens setzen dieselbe Idee auch zum Trainieren der einzelnen Bäume ein. Der Trainingsalgorithmus wurde so angepasst, dass bei jeder Aufteilung nur eine zufällig gewählte Teilmenge aller Merkmale berücksichtigt wird. Dieses Verfahren wird Random Subspace Methode oder Feature Bagging genannt. Es verhindert eine mögliche Korrelation der Bäume für bestimmte Stichproben: wenn ein oder mehrere Merkmale sehr großen Einfluss für die Vorhersage haben, dann wird das ohne die Random Subspace Methode dazu führen, dass diese Merkmale in vielen Bäumen ähnlich ausgewertet werden und die Bäume korrelieren. Eine Analyse dazu, wie Bagging und die Random Subspace Methode die Qualität der Vorhersage verbessern, hat Ho veröffentlicht.

Algorithmus

Jeder Entscheidungsbaum im Random Forest wird mit folgendem Algorithmus erzeugt:Vorlage:Rp

1. Ziehe ein Bootstrap-Sample mit $N$ Datensätzen aus dem Trainingsdatensatz durch Ziehen mit Zurücklegen.
2. Benutze das Bootsstrap-Sample, um den Entscheidungsbaum wachsen zu lassen. Wiederhole die folgenden Schritte rekursiv für jeden Knoten des Baums, bis die minimale Knotengröße erreicht ist.
   1. Wähle aus den $M$ Merkmalen (Features oder Dimensionen) der Trainingsdaten zufällig $m\ll M$ Merkmale aus.
   2. Wähle aus den $m$ Merkmalen das Merkmal aus, das sich am besten für die nächste Aufteilung (Split) eignet. Das Merkmal und sein Split-Wert können zum Beispiel mittels der Minimierung der Entropie oder des Mean-Squared Errors ausgewählt werden, siehe CART (Algorithmus)
   3. Teile die Objekte im Knoten auf seine beiden Folgeknoten auf.

Die so erzeugten Bäume bilden zusammen den Random Forest. 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 wird einfach die Klasse zurückgeliefert, die am häufigsten gewählt wurde. 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.

Man kann das Training eines Random Forest durch viele Konfigurationsparameter beeinflussen. Dazu zählt unter anderem, welche und wie viele Entscheidungsbäume aufgebaut werden und ob eine maximale Tiefe der Bäume vorgegeben wird.

Die Erfinder des Random-Forest-Verfahrens empfehlen als typische Werte für ein Klassifikationsproblem mit $M$ Merkmalen $m=\sqrt{M}$ (abgerundet) Merkmale und eine minimale Knotengröße von 1. Für Regressionsprobleme empfehlen sie m=$M/3$ (abgerundet) Merkmale und eine minimale Knotengröße von 5. In der praktischen Anwendung hängen die optimalen Werte vom Problem ab und sollten an das gegebene Problem angepasst werden.Vorlage:Rp

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 des Klassifikators 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 ihre Vorhersagen per Konstruktion nicht perfekt korreliert.

Vorteile

Ein Random Forest hat bei Klassifikations- und Regressionsproblemen folgende wesentlichen Vorteile gegenüber anderen Klassifikationsmethoden:

• Ein Random Forest kann sowohl Regressionsprobleme als auch Klassifizierungsprobleme mit großer Genauigkeit lösen. Man kann eine Überanpassung durch Kreuzvalidierungen erkennen und dadurch vermeiden, dass man eine ausreichende Anzahl von Bäumen erzeugt.
• Der Klassifikator trainiert sehr schnell: Dieser Vorteil ergibt sich durch die kurze Trainings- bzw. Aufbauzeit eines einzelnen Entscheidungsbaumes und dadurch, dass die Trainingszeit bei einem Random Forest linear mit der Anzahl der Bäume steigt.
• Die Evaluierung eines Testbeispieles geschieht auf jedem Baum einzeln und ist daher parallelisierbar. Er evaluiert also schnell.
• Er ist sehr effizient für große Datenmengen (viele Trainingsbeispiele, viele Merkmale).
• Er kann auch für die Schätzung fehlender Werte verwendet werden, weil er die Genauigkeit beibehält, wenn ein Teil der Daten fehlt.
• Random Forests erleichtern es, die Bedeutung einer Variable oder eines Merkmals für ein Modell zu bewerten. Durch Berechnung der erwarteten Impurity-Verringerung kann eine Feature Importance angegeben werden.
• Random Forests können große Datensätze verarbeiten und besitzen eine nach oben skalierbare Modellkapazität. Da sie zusätzlich nichtlineare Zusammenhänge beschreiben können, liefern sie bei guter Anpassung häufig gute Ergebnisse.

Nachteile

Ein Random Forest hat bei Klassifikations- und Regressionsproblemen folgende wesentlichen Nachteile gegenüber anderen Klassifikationsmethoden:

• Die Trainingszeit wächst mit der Zahl der Bäume, weil jeder Baum einzeln berechnet wird.
• Random Forests belegen mehr Speicherplatz als kleine, einfachere Modelle.
• Das Modell ist komplexer und deshalb schwieriger zu interpretieren als das von einem einzelnen Entscheidungsbaum.

Out-of-bag error

Out-of-bag (OOB) error, auch out-of-bag estimate, ist eine Methode, um den Vorhersagefehler von Random Forests zu messen. Als Folge des Baggings enthält die Bootstrap-Stichprobe, mit der ein einzelner Baum trainiert wird, nicht alle Datenpunkte aus dem Trainingsdatensatz. Zur Berechnung des out-of-bag-errors bestimmt man den gemittelten Vorhersagefehler für alle Trainingsdatenpunkte $x_i$, wobei man nur die Bäume berücksichtigt, die $x_i$ nicht in ihrer Bootstrap-Stichprobe enthalten.

Feature Importance

Mit Hilfe von Random Forests kann die Bedeutung von Merkmalen für Klassifikationsaufgaben und Regressionsaufgaben einfach bestimmt werden. Die folgende Methode ist in Breimans Artikel beschrieben und in dem R Softwarepaket randomForest umgesetzt.

Permutation Importance

Im ersten Schritt wird ein Random Forest mit einem Datensatz ${𝒟}_n=\{(X_i,Y_i){\}}_{i=1}^n$ trainiert. Danach werden für jeden Datenpunkt $x_i$ alle out-of-bag errors aufgezeichnet und über den Forest gemittelt (falls beim Training kein Bagging benutzt wurde, können ersatzweise Fehler eines unabhängigen Testdatensatzes benutzt werden).

Um die Bedeutung des $j$-ten Merkmals zu bestimmen, werden die Werte des $j$-ten Merkmals in den out-of-bag Datenpunkten permutiert und der gemittelte out-of-bag errors wird noch einmal für diesen gestörten Datenpunkt berechnet. Der Wert für die Bedeutung für das $j$-te Merkmal wird berechnet, indem man die Differenz zwischen dem out-of-bag error vor und nach der Permutation über alle Bäume mittelt. Der Wert wird durch die Standardabweichung dieser Differenzen normalisiert.

Merkmale mit hohen Werten haben eine größere Bedeutung für die Aufteilung als Merkmale mit kleineren Werten.

Ähnlichkeit zum K-Nächster-Nachbar-Algorithmus

Es gibt Ähnlichkeiten zwischen Random Forests und dem K-Nearest-Neighbor-Algorithmus. Beide gewichten bei ihren Vorhersagen für neue Datenpunkte diejenigen Datenpunkte aus dem Trainingsdatensatz höher, die nahe an den neuen Datenpunkten liegen.

Der K-Nächster-Nachbar-Algorithmus bildet die Nähe durch eine gewichtete Abstandsfunktion ab, die näheren Punkten ein höheres Gewicht gibt als weiter entfernten. Beim Random Forest wirkt sich das Mitteln über viele unkorrellierte Bäume ähnlich aus.

Gegeben seien $n$ unabhängige und identisch verteilte Werte $(x_i,y_i)$ eines zufälligen Eingabevektors $X:=(X^{(1)},\dots ,X^{(d)})\in R^d$ und einer zufälligen Antwortvariablen $X\in R$. Will man die Regressionsfunktion $g(x):=\mathrm{E}(Y\mid X=x)$ schätzen, dann kann man für jeden Punkt $x_0\in R^d$ eine Schätzfunktion $\hat{g}(x_0)$ von $g(x_0)$ definieren, die auf den Funktionswerten $(x_i,y_i)$ basiert. Die mittlere quadratische Abweichung bei $x_0$ ist

$\mathrm{MSE}(\hat{g}(x_0))=\mathrm{E}((\hat{g}(x_0)-g(x_0){)}^2)=(\mathrm{E}(\hat{g}(x_0)-g(x_0)){)}^2+\mathrm{Var}(\hat{g}(x_0))$

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

$\hat{g}(x_0)=\sum _{i=1}^n{w}_i\cdot y_i$

Dabei ist das Gewicht $w_i$ gleich $\frac{1}{k}$ für die $k$ nächsten Nachbarn von $x_0$ und gleich 0 für alle anderen Punkte.

Beim Random Forest betrachtet man die Schätzfunktion $\hat{g}$ von $g$ für das Regressionsproblem $Y=g(X)+ϵ$ mit $\mathrm{E}(ϵ)=0$ und $\mathrm{Var}(ϵ)={\sigma }^2$ auf der Grundlage einer Zufallsstichprobe $(x_1,y_1),(x_2,y_2),\dots ,(x_n,y_n)$ und nimmt an, dass die Zufallsvariable $X$ eine Wahrscheinlichkeitsverteilung in $[0,1{]}^d$ hat. Ist $\hat{g}$ die Schätzfunktion eines nicht adaptiven Random Forest, dessen Endknoten die Größe $k$ haben, dann gibt es eine Konstante ${\mathrm{\Lambda }}_3>0$, sodass für alle $n$ und alle Funktionswerte $x_0\in [0,1{]}^d$ folgende Abschätzung für die mittlere quadratische Abweichung gilt:

$\mathrm{MSE}(\hat{g}(x_0))\ge {\mathrm{\Lambda }}_3\cdot k^{-1}\cdot (\log (n){)}^{-(d-1)}$.

Das bedeutet, dass $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 $n^{-\frac{2\cdot m}{2\cdot m+d}}$ ist.

Weblinks

• Random Forests, Homepage von Leo Breiman und Adele Cutler