Random Forest

Ein Random Forest ist ein Klassifikationsverfahren, welches aus mehreren verschiedenen, 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. Neben einer Klassifikation kann der Random Forest auch zur Regression eingesetzt werden.

Der Begriff Random Forest wurde von Leo Breiman im Jahr 2001 ^[1] geprägt, welcher verschiedene Methoden der Randomisierung der Bäume, beispielsweise mittels Bagging oder Boosting erforschte. Seiner Arbeit ging die Forschung von Tin Kam Ho ^[2] im Jahr 1995 voraus.

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. Die Trainingszeit bei einem Random Forest steigt linear mit der Anzahl der Bäume.
Die Evaluierung eines Testbeispieles geschieht auf jedem Baum einzeln und ist daher parallelisierbar. Er evaluiert also schnell.
Er ist sehr effizient auf große Datenmengen (Anzahl der Klassen, Beispiele sowie Merkmale) anzuwenden.
Starke (wichtige) Klassen können erkannt werden.
Der Zusammenhang von Klassen kann mittels Random Forests 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:

Bei N Beobachtungen in der Trainingsmenge werden n Objekte zufällig mit Zurücklegen gezogen.
Bei M Merkmalen (Features oder Dimensionen) der Beispiele werden an jedem Knoten im Baum $$ m<<M $$ Merkmale zufällig gewählt, die zur Betrachtung des Schnitts (Split) genommen werden. Dies kann zum Beispiel mittels der Minimierung der Entropie geschehen.
Der Baum wird voll ausgebaut und nicht zurückgeschnitten (Pruning).

Zur Klassifikation wird nun ein Beispiel in jedem Baum ausgewertet. Jene Klasse, welche am häufigsten gewählt wurde ist die Klassifikation des Random Forest.

Anna Bosch^[3] hat in ihrer Arbeit zusätzlich jedem Blatt die a posteriori Wahrscheinlichkeiten der Klassen gespeichert, mit der sie zu diesem Blatt finden. Diese Wahrscheinlichkeiten werden anschließend für die Wahl der Klassifikation berücksichtigt. Dadurch konnte sie im Weiteren die Fehlerrate in ihrer Anwendung verringern.

Software

Leo Breiman und Adele Cutler: Eine Implementierung eines Random Forest in FORTRAN 77
Random Forests von Salford Systems
randomForest in R
Oblique random forests mit multivariaten Entscheidungsbaeumen 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).

Weblinks

http://stat-www.berkeley.edu/users/breiman/RandomForests/cc_home.htm (Random Forests, Homepage von Leo Breiman und Adele Cutler)

Quellen

↑ ^1,0 ^1,1 Breiman L., Random forests. In Machine Learning, Seiten 5-32, 2001
↑ 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
↑ 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 (PDF).

[Breiman2001-1] 1,0 ^1,1 Breiman L., Random forests. In Machine Learning, Seiten 5-32, 2001

[Ho1995-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

[Bosch2007-3] 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 (PDF).

[1]

[2]

[3]