Am veröffentlicht

Website Optimierung mit Advanced Analytics – Teil 3: Random Forest

Nachdem im letzten Teil ein Data Mining Algorithmus als Bestandteil eines Recommendation Systems erläutert wurde, soll der Algorithmus dieses Beitrages in der Lage sein Predictions (dt. Vorhersagen) über das Nutzerverhalten zu treffen. Dafür betrachten wir Random Forest und die Vorzüge gegenüber Decision Trees. Für einen Einstieg in Decision Trees empfehlen wir vor dem Weiterlesen folgenden Beitrag in unserem Blog.

Grenzen von Decision Trees

Random Forest basiert auf Decision Trees (dt. Entscheidungsbäumen). Abstrakt gesprochen bilden Entscheidungsbäume die menschliche Entscheidungsfindung computerinterpretierbar nach. Ziel ist es, die Datenmenge in möglichst homogene Gruppen einzuteilen, die untereinander möglichst heterogen sind. Dabei treten zwei Arten von Fehlern auf. Um die beiden Fehlertypen zu verstehen, ist es wichtig sich zu überlegen wie Entscheidungen getroffen werden. Die Algorithmen operieren auf Daten. Sie suchen nach häufig auftretenden Mustern und deren Korrelationen. Verlässliche Aussagen lassen sich dabei nur auf Grundlage von großen Datenmengen treffen.

Bei der menschlichen Entscheidungsfindung grenzen wir die Ergebnismenge ein. Dabei gilt: Je stärker die Ergebnismenge eingegrenzt werden kann, desto genauer das Ergebnis. Was für uns eine logische Schlussfolgerung ist, kann für den Rechner das Gegenteil bewirken. Denn dem Rechner steht in Form von Daten nur ein begrenztes „Wissen“ zur Verfügung. Grenzen wir die Ergebnismenge weiter ein, verringert sich die Datenmenge, also das „Wissen“. Trifft der Algorithmus in folge dessen Entscheidungen auf dieser geringen Datenmenge, bewertet er eine Situation ohne ausreichende „Wissensgrundlage“. Dies führt zum so genannten Overfitting (dt. Überanpassung), weil sehr kleine Teilmengen überproportional bewertet werden. In Konsequenz werden Vorhersagen für bereits bekannte Ausgangssituationen sehr genau prognostiziert, die Generalisierung der Entscheidungsregeln auf unbekannten Daten leidet jedoch. Im Ergebnis lernt der Algorithmus die Trainingsdaten auswendig.

Die folgende Abbildung visualisiert das Problem des Overfittings anhand eines Polynom dritten Grades:

underfitting

appropriate fitting

overfitting

Ein Ansatz, um Overfitting zu verhindern, nennt man Pruning. Pruning bezeichnet die Begrenzung der Tiefe eines Entscheidungsbaumes. Der Ansatz ist effektiv aber rigoros, denn er führt direkt zum zweiten Fehlertyp:

Um die Ergebnismenge einzuschränken, bleibt nur die Möglichkeit Fragen bezüglich der Beschaffenheit der Daten zu stellen. In dem Moment, in dem sich jemand überlegt, welche Frage er stellt, um einen möglichst homogenen Teil der Daten zu selektieren, nimmt er Einfluss auf das Ergebnis. Dieses Problem beschreibt der Bias (dt. Befangenheit). Wenn nun also mittels Pruning ein Teil des Entscheidungsbaumes abgeschnitten wird, wird zwangsläufig auch das Ergebnis manipuliert.

Random Forest

An dieser Stelle kommt der Random Forest ins Spiel. Dieser besteht aus einer Vielzahl von Entscheidungsbäumen (Forest), die zufällig generiert werden (Random). Der Zufall wird dabei durch den Algorithmus bestimmt, denn er bildet aus den vorgegebenen Entscheidungsbäumen eine Vielzahl neuer, kleinerer Entscheidungsbäume, die jeweils Teilbäume der ursprünglichen Entscheidungsbäume darstellen. Durch den Einsatz von Teilbäumen wird das Problem des Overfitting umgangen, während die Menge an Teilbäumen den Bias reduzieren, indem ein Mittel aus den Entscheidungen vieler Teilbäume gebildet wird.

So viel zum Aufbau des Random Forest, aber wie nutzt man den Algorithmus zur Optimierung der Website? Random Forest wird beispielsweise für Klassifikationsprobleme eingesetzt. Klassifikationsprobleme bedürfen einer approximierten mapping-Funktion, um von einem Startzustand X zu einem definierten Endzustand Y zu kommen. Y wird dabei häufig als Klasse, Label oder Kategorie bezeichnet, daher der Name Klassifikationsproblem. Regressionsprobleme werden im Beispiel außenvor gelassen.

Der Startzustand wird in unserem Beispiel durch die Ausprägungen der aktuellen Session eines Kunden dargestellt, der Endzustand könnte z.B. eine bestimmte Produktkategorie oder ein einzelnes Produkt sein. Letzten Endes ist man damit in der Lage, den nächsten Klick des Kunden zu prognostizieren. Das Wissen über den nächsten Klick impliziert gleichzeitig das Interesse des Kunden. In dem Moment in dem der Betreiber einer Website weiß für welche Produkte sich ein Kunde interessiert, ist er in der Lage seine Website dynamisch anzupassen, um dem Kunden die Dinge die er sucht auf einen Blick bereitzustellen oder ihn mit besonderen Angeboten zu locken.

Fazit

In diesem Artikel wurden die Vorzüge eines Random Forest gegenüber einfachen Decision Trees erläutert. Außerdem haben wir gesehen, dass Algorithmen in der Lage sind Nutzerverhalten zu prognostizieren. Neben dem Vorgestellten Algorithmus gibt es eine Vielzahl an Algorithmen die weitreichende Optimierungsmöglichkeiten bieten. Als Ausblick sollen an dieser Stelle Neuronale Netze genannt werden.

Neuronale Netze werden für vergleichbare Problemstellungen wie klassische Machine Learning Algorithmen eingesetzt. Sie sind dabei jedoch leistungsstärker und erzielen bessere Ergebnisse. Im Gegensatz zu den klassischen Lösungsansätzen benötigen sie dafür deutlich mehr Rechenleistung. Dadurch gilt es im Einzelfall zu entscheiden, welcher Algorithmus die bessere Variante ist.