Random Forest

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Ein Random Forest ist ein Klassifikationsverfahren, 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 1999[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.

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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 der Entscheidungsbäume im Wald folgender Algorithmus angewandt werden:

  1. Von den Beobachtungen in der Trainingsmenge werden Stück zufällig mit Zurücklegen gezogen.
  2. Von den Merkmalen (Features oder Dimensionen) der Trainingsdaten werden an jedem Knoten im Baum 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.[3] 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[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Quellen[Bearbeiten | Quelltext bearbeiten]

  1. a b Breiman L., Random forests. In Machine Learning, Seiten 5-32, 2001
  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
  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).