Suchen

Der Random-Forest-Klassikator als Entscheidungshilfe

Autor / Redakteur: Michael Matzer / Nico Litzel

Der Random-Forest-Algorithmus ist ein sogenanntes beaufsichtigtes Klassifikationsverfahren, das aus mehreren unkorrelierten Entscheidungsbäumen besteht, die eine Klassifizierung oder Vorhersage liefern. Weil sich die Entscheidungsbäume parallel verarbeiten lassen, kann der Algorithmus – bei entsprechend paralleler Ausführung – sehr schnell ausgeführt werden. Die Skalierung ist also leicht zu berechnen. Random Forests können auch der Regressionsanalyse dienen.

Firmen zum Thema

Wie funktioniert der Random-Forest-Algorithmus? Antworten gibt der 12. Teil unserer Grundlagenreihe.
Wie funktioniert der Random-Forest-Algorithmus? Antworten gibt der 12. Teil unserer Grundlagenreihe.
(Bild: © momius - stock.adobe.com)

Im Random Forest besteht der Wald aus lauter Entscheidungsbäumen (Decision Trees). Dabei handelt es sich zunächst um geordnete, gerichtete Bäume, die der Darstellung von Entscheidungsregeln dienen. Die Darstellung als Baumdiagramm illustriert hierarchisch aufeinanderfolgende Entscheidungen. Sie werden in zahlreichen Bereichen, in denen automatisch klassifiziert wird, verwendet und ebenso, wenn formale Regeln hergeleitet werden sollen.

Eine Methode, um die Klassifikationsgüte beim Einsatz von Entscheidungsbäumen zu steigern, ist der Einsatz von Mengen von Entscheidungsbäumen anstelle von einzelnen Bäumen. Solche Mengen von Entscheidungsbäumen bezeichnen die Experten als Entscheidungswälder (englisch: decision forests).

Solche Random (Decision) Forests sind im Machine Learning eine Ensemble-Lernmethode für die Klassifizierung, Regressionsanalyse und andere Aufgaben. Dabei werden stets zur Trainingszeit eine große Menge von Entscheidungsbäumen erzeugt. Ausgegeben werden der Modus einer Klasse (im Bereich der Klassifizierung) oder eine mittlere Vorhersage (im Falle der Regression) der einzelnen Bäume.

Ein einfacher binärer Entscheidungsbaum
Ein einfacher binärer Entscheidungsbaum
(Bild: gemeinfrei / CC0 )

Die Randomisierung per Zufallswahl von Teilmengen sorgt dafür, dass die Entscheidungsbäume sich nicht allzu genau an ihre Trainingsdaten halten. 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. Das ist etwa so, wie wenn eine Person sich bei ihren Freunden und Bekannten nach Empfehlungen für das beste Urlaubsziel umhören würde: Das mit den meisten Empfehlungen würde dann ausgewählt werden. Man bekommt durch Randomisierung eine größere Bandbreite von Möglichkeiten und vermeidet die Einwirkung einer vorgefassten Meinung oder Tendenz.

Boosting und Bagging

Die Idee hinter den Entscheidungswäldern besteht darin, dass ein einzelner Entscheidungsbaum zwar keine optimale Klassifikation liefern muss, die Mehrheitsentscheidung einer Menge von geeigneten Bäumen dies aber sehr wohl leisten kann. Leo Breiman, der zusammen mit Adele Cutler das Verfahren im Jahr 1999 erfand und 2019 patentieren ließ, erforschte verschiedene Methoden der Randomisierung von Entscheidungsbäumen, beispielsweise mittels Bagging oder Boosting.

Boosting bzw. Bootstrap-Aggregation ist ein Algorithmus der automatischen Klassifizierung, der mehrere schwache Klassifikatoren zu einem einzigen guten Klassifikator verschmilzt. Bagging ist eine Methode, um Vorhersagen aus verschiedenen Regressions- oder Klassifikationsmodellen zu kombinieren. Die Ergebnisse der Modelle werden dann im einfachsten Fall gemittelt, das heißt, das Ergebnis jeder Modellvorhersage geht mit gleichem Gewicht in die Vorhersage ein.

Ein Random Forest zeichnet sich durch viele Vorteile gegenüber anderen Klassifikationsmethoden wie etwa der Support Vector Machine (SVM) aus. Die SVM ist im Machine Learning eine Kernel-Methode, mit der sich Muster analysieren lassen. Tatsächlich lassen sich Random-Forest-Formeln zu Kernel-Methoden-Formeln umformulieren, die leichter zu interpretieren und zu analysieren sind. Den Zusammenhang zwischen RF-Methoden und Kernel-Methode hat bereits Breiman erkannt und seit ca. 2000 werden diese beiden Bereiche zügig miteinander verbunden.

Die Vorteile von Random Forest

  • Der RF-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 Verarbeitungszeit lässt sich so vorausberechnen.
  • Die Evaluierung eines Testbeispiels geschieht auf jedem Baum einzeln und ist daher parallelisierbar. Er evaluiert also dann besonders schnell, wenn man entsprechende parallel verarbeitende Technologie wie etwa eine GPU nutzt.
  • Er eignet sich sehr effizient für große Datenmengen (viele Klassen, viele Trainingsbeispiele, viele Merkmale).
  • Wichtige Klassen können erkannt werden.
  • Der Zusammenhang zwischen Klassen lässt sich ablesen.

Die Funktionsweise

Es gibt viele verschiedene Varianten und Ansätze, einen Random-Forest-Algorithmus 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. Gemäß Leo Breiman soll für jeden Entscheidungsbaum im Wald folgender Algorithmus angewandt werden:

Im ersten Schritt werden nBootstrap-Samples gezogen, also eine Stichprobe aus den Trainingsdaten. Von den M Merkmalen (Features oder Dimensionen) der Trainingsdaten werden an jedem Knoten im Baum m ≪ 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. Sinn dieser Maßnahmen ist es, die hohe Varianz in Entscheidungsbäumen zu reduzieren. Erst im dritten Schritt wird der Entscheidungsbaum voll ausgebaut und nicht zurückgeschnitten oder gestutzt (vgl. Pruning). Man arbeitet also mit allen Trainingsdaten.

Blatt und Knoten

In einem Entscheidungsbaum stellt jeder interne Knoten einen „Test“ für ein Attribut dar. Unabhängig davon, ob ein Münzwurf (Kopf oder Zahl) erscheint, stellt jeder Zweig das Ergebnis des Tests dar und jeder Blattknoten stellt eine Klassenbezeichnung dar (Entscheidung nach Berechnung aller Attribute). Ein Knoten, der keine Kinder hat, ist ein „Blatt“.

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. Anna Bosch, Andrew Zisserman, Xavier Muñoz speichern hinsichtlich der Bildverarbeitung zusätzlich in jedem RF-Blatt die A-posteriori-Wahrscheinlichkeiten der Klassen, mit denen sie das RF-Blatt finden. Diese Wahrscheinlichkeiten werden anschließend bei der Klassifikation berücksichtigt. Dadurch kann die Fehlerrate in ihrer Anwendung verringert werden.

Weitere beachtenswerte Parameter erläutern Artikel bei AI United, so etwa zum Random Forest, zur Regressionsanalyse mit Random Forest und zur Feature Selection.

Kombination mit Neuronalen Netzen

Entscheidungsbäume, die ja bei Random Forest eine entscheidende Rolle spielen, können mit Neuronalen Netzen kombiniert werden. So ist es beispielsweise möglich, ineffiziente Äste des Baumes durch Neuronale Netze zu ersetzen, um eine höhere, allein mit den Bäumen nicht erreichbare Klassifikationsgüte zu erreichen.

Auch können die Vorteile beider Klassifikationsmethoden durch die Abbildung von Teilstrukturen in die jeweils andere Methodik genutzt werden: Die Bäume brauchen nicht so viele Trainingsdaten zur Induktion wie die Neuronalen Netze. Dafür können sie ziemlich ungenau sein, besonders wenn sie klein sind. Die Neuronalen Netze hingegen klassifizieren genauer, benötigen aber mehr Trainingsdaten. Deshalb versucht man, die Eigenschaften der Entscheidungsbäume zur Generierung von Teilen Neuronaler Netze zu nutzen, indem sogenannte Tree-Based Neural Networks (TBNN, seit 1994 bekannt) die Regeln der Entscheidungsbäume in die Neuronalen Netze übersetzen.

Beispiel: Segmentierung von Kunden

Der Random-Forest-Algorithmus wird in zahlreichen Branchen verwendet, so etwa im Banking, an der Börse, in der Medizin und im E-Commerce. Im Data Mining ist die Methode der Segmentierung von Mengen als „Data Segmentation“ oder auch „Segmentation Modeling“ bekannt. Im Marketing und CRM gehört Segmentierung zu den Basisverfahren. Wenn eine Bank beispielsweise mit einer Direct-Mailing-Aktion einen neuen Service verkaufen möchte, will sie wissen, bei welchen Kundensegmenten diese Aktion die größte Wirkung erzielen würde.

Um die Erfolgsaussichten zu erhöhen, sollen mit der Aktion nur Haushalte angesprochen werden, die einer Kombination von demografischen Variablen entsprechen, die ein entsprechender Entscheidungsbaum als optimal erklärt hat. Wenn man nicht nur einen solchen Entscheidungsbaum heranzieht, sondern einen ganzen Random Forest, dürfte sich die Genauigkeit der Erfolgsvorhersage (Klassifikation plus Regressionsanalyse) erhöhen. Banken nutzen RF-Algorithmen auch zur Erkennung von Betrug und zum Messen der Kundenzufriedenheit.

Verfügbare Software

Die Software-Pakete von IBM SPSS, R, SAS, Scikit, Weka, Spark MLlib sowie Vigra enthalten alle Implementierungen des Random-Forest-Algorithmus, was die hohe Bedeutung des Algorithmus belegt.

Dieser Beitrag erschien zuerst auf unserem Partnerportal Bigdata-Insider.de.

(ID:46965386)

Über den Autor