Random Forest

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. Für eine Klassifikation darf jeder Baum in diesem Wald eine Entscheidung treffen und die Klasse mit den meisten Stimmen entscheidet die endgültige Klassifikation. Random Forests können auch zur Regression eingesetzt werden.

Der Begriff Random Forest wurde von Leo Breiman im Jahr 2001^[1] 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^[2] im Jahr 1995 voraus.

Zufallswälder sind eine Methode im Bereich des Ensemble learnings.

Eigenschaften

Ein Random Forest kann mit vielen Vorteilen gegenüber anderen Klassifikationsmethoden wie der SVM punkten.

• 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 Klassen, viele Trainingsbeispiele, viele Merkmale).
• Wichtige Klassen können erkannt werden.
• Der Zusammenhang zwischen Klassen kann erkannt werden.

Funktionsweise

Es gibt viele verschiedene Varianten und Ansätze, einen Random Forest zu trainieren und klassifizieren zu lassen. Dazu zählt unter anderem, welche Entscheidungsbäume verwendet werden und ob eine maximale Tiefe der Bäume vorgegeben wird. Nach Breiman^[1] soll für jeden Entscheidungsbaum im Wald folgender Algorithmus angewandt werden:

1. Es werden ${\displaystyle n}$ Bootstrap-Samples gezogen.^[3]
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. Die anschließende Auswahl eines Merkmals aus dieser Menge kann zum Beispiel mittels der Minimierung der Entropie geschehen.
3. Der Baum wird voll ausgebaut und nicht zurückgeschnitten (Pruning).

Zur Klassifikation einer Eingabe wird diese in jedem Baum ausgewertet. Diejenige Klasse, die am häufigsten gewählt wurde, ist die Ausgabe des Random Forest. (Wenn es mehrere Klassen gibt, die am häufigsten gewählt wurden, muss man sich anderweitig für eine entscheiden.)

Bosch et al.^[4] 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.

Software

• Leo Breiman und Adele Cutler: Eine Implementierung eines Random Forest in FORTRAN 77
• Random Forests von Salford Systems
• randomForest und ranger in R
• Oblique random forests mit multivariaten Entscheidungsbäumen in R
• Random Jungle ist eine schnelle Implementierung für hochdimensionale Daten. (C++, paralleles Rechnen, geringer Speicherverbrauch, Linux + Windows)
• Waikato Environment for Knowledge Analysis: Das freie Softwarepaket Weka der Universität von Waikato stellt neben vielen weiteren Klassifikatoren und Regressionsmethoden auch eine Random-Forest Implementierung zur Verfügung.
• Vigra: Vigra bietet neben einer Vielzahl von Bildverarbeitungsalgorithmen auch eine effiziente C++ Implementierung des Random Forest Klassifikators sowie verschiedene Regressionsverfahren (u. a. LARS).
• MLlib: die Spark "Machine Learning Library" (MLlib) bietet u. a. eine unter Apache-Lizenz verfügbare RandomForest Implementierung für Spark Cluster
• SPSS Random Forest: Beispiel für Random Forest in IBM SPSS
• Random Forests in Scikit-learn (Python)
• M5PrimeLab ist eine Matlab/Octave Toolbox für Modellbäume auf Basis der M5-Regel

Weblinks

• Random Forests, Homepage von Leo Breiman und Adele Cutler

Quellen

1. ↑ ^{a b} 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.