Random Forest

Grundidee und Zweck

Ein Random Forest (deutsch „Zufallswald“), auch Random Decision Forest, ist eine Ensemblemethode des maschinellen Lernens für Klassifikations- und Regressionsaufgaben. Ein Ensemble verbindet mehrere Vorhersagemodelle zu einem gemeinsamen Modell. Beim Random Forest sind diese Modelle zahlreiche Entscheidungsbäume, die möglichst wenig miteinander korrelieren sollen.

Ein Entscheidungsbaum besteht aus Knoten und Blättern. Jeder Knoten enthält eine gelernte logische Regel, die Daten auf zwei Folgeknoten verteilt; jedes Blatt liefert eine Antwort. Der CART-Algorithmus erzeugt solche Binärbäume für Klassifikation oder Regression. Entscheidungsbäume lassen sich schnell trainieren, sind unempfindlich gegenüber Ausreißern und irrelevanten Merkmalen und benötigen oft wenig Datenaufbereitung. Tiefe Einzelbäume neigen jedoch zur Überanpassung: Sie lernen fehlerhafte Besonderheiten der Trainingsdaten, besitzen dadurch eine geringe Verzerrung, aber eine sehr hohe Varianz.

Ein Random Forest verringert diese Varianz, indem er über viele tiefe, unterschiedlich trainierte Bäume mittelt. Jeder Baum erhält eine zufällige Stichprobe der Trainingsdaten und betrachtet bei jeder Aufteilung nur eine zufällig ausgewählte Teilmenge der Merkmale. Für eine Klassifikation gewinnt die von den meisten Bäumen gewählte Klasse; bei einer Regression wird beispielsweise der Mittelwert ihrer Vorhersagen verwendet. Dies verbessert normalerweise die Vorhersageleistung, erhöht aber geringfügig die Verzerrung und macht das Modell komplexer.

Tin Kam Ho untersuchte Random Decision Forests erstmals 1995 und bezeichnete die zufällige Merkmalsauswahl als Random Subspace Methode. Sie stellte fest, dass entsprechend eingeschränkte Wälder mit zunehmendem Wachstum genauer werden können, ohne zu überanpassen. Leo Breiman veröffentlichte 2001 die Grundlagen des heute üblichen Verfahrens: Er verband den CART-Algorithmus und die Random Subspace Methode mit Bagging und beschrieb außerdem Verfahren zur Schätzung des Vorhersagefehlers und der Merkmalsbedeutung.

Bagging und zufällige Merkmalsauswahl

Der Trainingsalgorithmus verwendet Bootstrap aggregating, kurz Bagging. Aus einem ursprünglichen Trainingsdatensatz werden durch Ziehen mit Zurücklegen B neue Stichproben mit jeweils n Datensätzen erzeugt. Mit diesen Stichproben werden B Modelle m_i für i = 1, …, B trainiert. Für einen neuen Eingabewert x′ ergibt sich bei einer Regression die gemeinsame Vorhersage aus

f̂ = (1/B) · ∑_{b=1}^{B} f_b(x′).

Bei einer Klassifikation wird stattdessen eine Mehrheitsentscheidung getroffen. Bagging senkt die Varianz, weil einzelne Bäume stärker auf Rauschen in ihren Trainingsdaten reagieren als der Durchschnitt möglichst unkorrelierter Bäume. Unterschiedliche Bootstrap-Stichproben tragen dazu bei, solche Bäume zu erzeugen.

Die Streuung der einzelnen Vorhersagen und damit die Größe des Vorhersagefehlers an der Stelle x′ kann durch die Standardabweichung geschätzt werden:

σ = √(∑_{b=1}^{B}(f_b(x′) − f̂)²/(B−1)).

Die Anzahl B kann frei gewählt werden; typisch sind mehrere hundert oder tausend Bäume. Ein geeigneter Wert lässt sich durch Kreuzvalidierung oder durch Beobachtung des Out-of-bag-Fehlers bestimmen.

Random Forests ergänzen das ursprüngliche Bagging um Feature Bagging, auch Random Subspace Methode genannt: Bei jedem Knoten wird nur eine zufällig gewählte Teilmenge aller Merkmale als mögliche Grundlage der Aufteilung betrachtet. Ohne diese Einschränkung würden besonders einflussreiche Merkmale in vielen Bäumen ähnlich genutzt, sodass deren Vorhersagen stärker korrelierten. Die zufällige Merkmalsauswahl vermindert diese Korrelation zusätzlich.

Training und Gesamtvorhersage

Jeder Baum wird unabhängig von den anderen aufgebaut:

• Aus dem Trainingsdatensatz wird durch Ziehen mit Zurücklegen ein Bootstrap-Sample mit N Datensätzen erzeugt.

• Der Baum wächst rekursiv, bis die minimale Knotengröße erreicht ist.

• An jedem Knoten werden aus insgesamt M Merkmalen zufällig m Merkmale mit m ≪ M ausgewählt.

• Unter diesen m Merkmalen wird dasjenige mit dem besten Split, also der besten Aufteilung, bestimmt. Merkmal und Split-Wert können beispielsweise durch Minimierung der Entropie oder des Mean-Squared Errors ausgewählt werden.

• Die Objekte des Knotens werden entsprechend auf zwei Folgeknoten verteilt.

Alle so erzeugten Bäume bilden den Random Forest. Ihre unterschiedlichen Antworten werden anschließend aggregiert. Bei einer Klassifikation wird die am häufigsten gewählte Klasse ausgegeben. Bei einem Gleichstand zwischen mehreren Klassen ist eine zusätzliche Entscheidungsregel erforderlich. Bei einer Regression kann der Mittelwert der Baumvorhersagen verwendet werden.

Zu den einstellbaren Parametern gehören die Zahl und Art der Bäume, eine mögliche maximale Baumtiefe, die Zahl m der je Knoten betrachteten Merkmale und die minimale Knotengröße. Für ein Klassifikationsproblem mit M Merkmalen empfehlen die Erfinder typischerweise m = √M, abgerundet, und eine minimale Knotengröße von 1. Für Regression empfehlen sie m = M/3, abgerundet, und eine minimale Knotengröße von 5. Die optimalen Werte hängen jedoch vom jeweiligen Problem ab.

Bosch et al. speichern zusätzlich in jedem Blatt die A-posteriori-Wahrscheinlichkeiten der Klassen, mit denen die Daten das Blatt erreichen. Werden diese Wahrscheinlichkeiten bei der Klassifikation berücksichtigt, kann sich die Fehlerrate verringern.

Stärken, Grenzen und Qualitätsmessung

Eine große Zahl unkorrelierter Bäume kann genauer vorhersagen als ein einzelner Baum, weil die Aggregation unabhängiger oder wenig korrelierter Ergebnisse deren Streuung senkt. Die Vorhersagen sind nicht perfekt korreliert, da jeder Baum bei einem Split das beste Merkmal aus einer zufälligen Teilmenge auswählt.

Zu den Vorteilen gehören eine hohe Genauigkeit bei Klassifikation und Regression sowie die Möglichkeit, Überanpassung mithilfe von Kreuzvalidierung zu erkennen. Einzelne Bäume lassen sich schnell aufbauen; die gesamte Trainingszeit wächst linear mit der Baumzahl. Weil jeder Baum getrennt ausgewertet wird, ist auch die Vorhersage parallelisierbar. Random Forests eignen sich für große Datenmengen mit vielen Beispielen und Merkmalen, können fehlende Werte schätzen und bleiben teilweise genau, wenn Daten fehlen. Sie besitzen eine nach oben skalierbare Modellkapazität, können nichtlineare Zusammenhänge darstellen und erlauben die Bewertung der Bedeutung einzelner Merkmale.

Nachteilig ist, dass Training und Speicherbedarf mit der Zahl der Bäume wachsen. Gegenüber kleinen, einfachen Modellen benötigen Random Forests mehr Speicher. Außerdem ist ein Wald schwieriger zu interpretieren als ein einzelner Entscheidungsbaum.

Der Out-of-bag error (OOB error oder out-of-bag estimate) misst den Vorhersagefehler. Da eine Bootstrap-Stichprobe nicht alle Trainingspunkte enthält, gibt es für jeden Punkt x_i Bäume, die nicht mit ihm trainiert wurden. Für jeden Trainingspunkt wird der Vorhersagefehler ausschließlich anhand dieser Bäume bestimmt; anschließend werden die Fehler gemittelt. So kann die Leistung auf nicht verwendeten Daten abgeschätzt werden, ohne zwingend einen eigenen Testdatensatz einzusetzen.

Merkmalsbedeutung und Nähe zu K-Nearest Neighbor

Die Feature Importance beschreibt, wie wichtig ein Merkmal für die Vorhersagen ist. Bei der Permutation Importance wird zunächst ein Random Forest mit dem Datensatz 𝒟_n = {(X_i,Y_i)}_{i=1}^n trainiert und für jeden Punkt der gemittelte Out-of-bag-Fehler aufgezeichnet. Falls kein Bagging verwendet wurde, können stattdessen Fehler auf einem unabhängigen Testdatensatz dienen.

Zur Bewertung des j-ten Merkmals werden dessen Werte in den Out-of-bag-Daten zufällig vertauscht, also permutiert. Danach wird der Fehler erneut berechnet. Die über alle Bäume gemittelte Differenz zwischen dem Fehler vor und nach der Permutation wird durch die Standardabweichung dieser Differenzen normalisiert. Ein hoher Wert bedeutet, dass das Merkmal für die Aufteilungen wichtiger ist als ein Merkmal mit niedrigem Wert. Eine weitere genannte Möglichkeit ist die erwartete Verringerung der Impurity, also der Unreinheit eines Knotens.

Random Forests ähneln dem K-Nächster-Nachbar-Algorithmus, weil beide nahe Trainingspunkte für die Vorhersage eines neuen Punktes stärker gewichten. K-Nearest Neighbor bildet Nähe ausdrücklich durch eine gewichtete Abstandsfunktion ab. Für die k nächsten Nachbarn von x₀ gilt w_i = 1/k, für alle anderen Punkte w_i = 0, sodass

ĝ(x₀) = ∑_{i=1}^{n} w_i · y_i.

Beim Random Forest entsteht eine ähnliche Gewichtung indirekt durch das Mitteln vieler unkorrelierter Bäume. Für eine Schätzung ĝ(x₀) der Regressionsfunktion g(x₀) = E(Y | X = x₀) zerfällt die mittlere quadratische Abweichung in

MSE(ĝ(x₀)) = E((ĝ(x₀)−g(x₀))²) = (E(ĝ(x₀)−g(x₀)))² + Var(ĝ(x₀)).

Für das Modell Y = g(X) + ε mit E(ε) = 0 und Var(ε) = σ² sowie X in [0,1]^d gilt bei einem nicht adaptiven Random Forest mit Endknotengröße k: Es gibt eine Konstante Λ₃ > 0, sodass für alle n und x₀ ∈ [0,1]^d

MSE(ĝ(x₀)) ≥ Λ₃ · k⁻¹ · (log(n))^{−(d−1)}.

Damit ist k⁻¹ · (log(n))^{−(d−1)} eine untere Schranke für die Konvergenzgeschwindigkeit seiner mittleren quadratischen Abweichung. Als optimale Konvergenzgeschwindigkeit des mittleren quadratischen Fehlers bei Regressionsproblemen wird dagegen n^{−2m/(2m+d)} angegeben.