Skalierbare Entscheidungsbäume in MLlib

Entscheidungsbäume und ihre Ensembles sind die wichtigsten Arbeitspferde der Branche für die Aufgaben des maschinellen Lernens wie Klassifizierung und Regression. Entscheidungsbäume sind leicht zu interpretieren, behandeln kategoriale und kontinuierliche Features, erweitern sich auf die Klassifizierung mehrerer Klassen, erfordern keine Feature-Skalierung und können Nichtlinearitäten und Feature-Interaktionen erfassen.

Aufgrund ihrer Beliebtheit bietet fast jede Bibliothek für maschinelles Lernen eine Implementierung des Entscheidungsbaumalgorithmus. Die meisten sind jedoch für die Datenverarbeitung auf einem einzigen Rechner konzipiert und können nur selten elegant auf eine verteilte Umgebung skaliert werden. Apache Spark ist eine ideale Plattform für eine skalierbare verteilte Entscheidungsbaumimplementierung, da die In-Memory-Datenverarbeitung von Spark es uns ermöglicht, mehrere Durchgänge über den Trainingsdatensatz effizient durchzuführen.

Vor etwa einem Jahr haben Open-Source-Entwickler ihre Kräfte zusammengeschlossen, um eine schnelle verteilte Entscheidungsbaumimplementierung zu entwickeln, die seit Version 1.0 Teil der Spark MLlib-Bibliothek ist. Die Spark-Community hat seitdem aktiv den Code für Entscheidungsbaum verbessert. In diesem Blogbeitrag wird die Implementierung beschrieben, einige der wichtigsten Optimierungen hervorgehoben und Testergebnisse vorgestellt, die die Skalierbarkeit demonstrieren.

Neu in Spark 1.1: MLlib-Entscheidungsbäume unterstützen jetzt die Mehrklassenklassifizierung und enthalten mehrere Leistungsoptimierungen. Zusätzlich zu Scala und Java gibt es jetzt APIs für Python.

Hintergrund des Algorithmus

Auf hoher Ebene kann man sich ein Entscheidungsbaummodell als hierarchische If-Other-Anweisungen vorstellen, die Merkmalswerte testen, um ein Label vorherzusagen. Nachfolgend wird ein Beispielmodell für eine binäre Klassifizierungsaufgabe gezeigt. Es basiert auf Daten zur Kilometerleistung von Autos aus den 1970er Jahren! Er sagt die Kilometerleistung des Fahrzeugs (hoch/niedrig) basierend auf Gewicht (schwer/leicht) und Leistung voraus.

Ein Modell wird aus einem Trainingsdatensatz gelernt, indem eine Struktur von oben nach unten erstellt wird. Die if-else-Anweisungen, auch bekannt als Aufteilungskriterien, werden gewählt, um eine Vorstellung von Informationsgewinn zu maximieren. Sie verringern die Variabilität der Labels in den zugrunde liegenden (zwei) Tochterknoten im Vergleich zum übergeordneten Knoten. Das erlernte Entscheidungsbaummodell kann später verwendet werden, um die Labels für neue Instanzen vorherzusagen.

Diese Modelle sind interpretierbar und funktionieren in der Praxis oft gut. Bäume können auch kombiniert werden, um noch leistungsfähigere Modelle mithilfe von Ensemblebaumalgorithmen zu erstellen. Baumgruppen wie Zufallswälder und verstärkte Bäume sind in der Branche häufig die besten Ergebnisse sowohl bei Klassifizierungs- als auch bei Regressionsaufgaben.

Einfache API

Das folgende Beispiel zeigt, wie ein Entscheidungsbaum in MLlib mit wenigen Codezeilen mithilfe der neuen Python-API in Spark 1.1 leicht trainiert werden kann. Es liest einen Datensatz aus, trainiert ein Entscheidungsbaummodell und misst dann den Trainingsfehler des Modells. Beispiele für Java und Scala finden Sie in der Spark-Dokumentation von DecisionTree.

Optimierte Implementierung

Spark ist aufgrund seiner ausgefeilten DAG-Ausführungs-Engine und In-Memory-Caching für iterative Berechnungen eine ideale Datenverarbeitungsplattform für eine skalierbare verteilte Entscheidungsbaumimplementierung. Wir erwähnen einige wichtige Optimierungen.

Ebenenbezogenes Training: Wir wählen die Splits für alle Knoten auf derselben Ebene der Struktur gleichzeitig aus. Diese stufenweise Optimierung reduziert die Anzahl der Durchgänge über den Datensatz exponentiell: Wir führen einen Durchlauf für jede Ebene statt einen Durchlauf für jeden Knoten in der Struktur durch. Dadurch lassen sich erhebliche Einsparungen bei E/A, Datenverarbeitung und Kommunikation erzielen.

Ungefähre Quantile: Implementierungen mit einzelnen Computern verwenden normalerweise sortierte eindeutige Merkmalswerte für kontinuierliche Merkmale als Split-Kandidaten für die beste Split-Berechnung. Das Auffinden sortierter eindeutiger Werte ist jedoch ein kostspieliger Vorgang über einen verteilten Datensatz. Der MLlib-Entscheidungsbaum verwendet Quantilen für jedes Merkmal als geteilte Kandidaten. Dies ist ein Standardkompromiss zur Verbesserung der Entscheidungsbaumleistung ohne signifikanten Verlust an Genauigkeit.

Vermeiden des Kartenvorgangs: Die frühen Prototypimplementierungen des Entscheidungsbaums verwendeten sowohl Karten- als auch Reduzierungsvorgänge bei der Auswahl der besten Aufteilungen für Baumknoten. Der aktuelle Code benötigt wesentlich weniger Berechnungs- und Kommunikationsaufwand, da die bekannte Struktur der vorberechneten Split-Kandidaten genutzt wird, um den Map-Schritt zu vermeiden.

Binweise Berechnung: Die beste Split-Berechnung diskretisiert Features in Bins, und diese Bins werden verwendet, um ausreichende Statistiken für die Aufteilung zu berechnen. Wir berechnen die binierten Repräsentationen jeder Instanz vorab und sparen so bei jeder Iteration Berechnungsaufwand.

Skalierbarkeit

Wir demonstrieren die Skalierbarkeit von MLlib-Entscheidungsbäumen anhand empirischer Ergebnisse für verschiedene Datensätze und Clustergrößen.

Skalierung mit Datasetgröße

Die beiden folgenden Abbildungen zeigen die Trainingszeiten von Entscheidungsbäumen, wenn wir die Anzahl der Instanzen und Features im Datensatz skalieren. Die Schulungszeiten stiegen linear an, was die Skalierbarkeit der Implementierung unterstreicht.

Diese Tests wurden auf einem EC2-Cluster mit einem Masterknoten und 15 Workerknoten unter Verwendung von r3.2xlarge-Instanzen (8 virtuelle CPUs, 61 GB Arbeitsspeicher) durchgeführt. Die Strukturen wurden auf 6 Ebenen aufgebaut, und die Datensätze wurden mit der Bibliothek spark-perf generiert.

Spark 1.1 Beschleunigungen

Die nächsten beiden Abbildungen zeigen Verbesserungen in Apache Spark 1.1 im Vergleich zur ursprünglichen Apache Spark 1.0-Implementierung. Bei denselben Datensätzen und Clustern ist die neue Implementierung bei vielen Datensätzen 4-5 Mal schneller!

Was kommt als nächstes?

Die baumbasierte Algorithmusentwicklung nach Version 1.1 wird sich hauptsächlich auf Ensemblealgorithmen wie Random Forests und Boosting konzentrieren. Wir werden auch den Entscheidungsbaumcode weiter optimieren und planen, in kommenden Versionen Unterstützung für weitere Optionen hinzuzufügen.

Laden Sie Spark 1.1 noch heute herunter, um selbst Entscheidungsbäume zu verwenden!

Weitere Informationen

• Beispiele und die API finden Sie in der MLlib-Entscheidungsbaumdokumentation.
• Sehen Sie sich die Präsentation des Entscheidungsbaums vom Spark Summit 2014 an.
• Sehen Sie sich Video und Folien aus einem anderen Vortrag über Entscheidungsbäume an, der im September 2014 in SF Scala/Bay Area stattfand.

Danksagungen

Die Entscheidungsbaumarbeit für Spark MLlib wurde zunächst gemeinsam mit Hirakendu Das (Yahoo Labs), Evan Sparks (UC Berkeley AMPLab) sowie Ameet Talwalkar und Xiangrui Meng (Databricks) durchgeführt. Seitdem sind weitere Mitwirkende hinzugekommen, und wir freuen uns auch über Ihre Beiträge!

(Dieser Blogbeitrag wurde mit KI-gestützten Tools übersetzt.) Originalbeitrag