Entscheidungsbäume: blattweise (am besten zuerst) und ebene Baumdurchquerung

13

Fehler 1:

Die Beschreibung von LightGBM bezüglich der Art und Weise, wie der Baum erweitert wird, verwirrt mich .

Sie stellen fest:

Die meisten Lernalgorithmen für Entscheidungsbäume vergrößern den Baum stufenweise (in der Tiefe), wie in der folgenden Abbildung dargestellt:

Bildbeschreibung hier eingeben

Fragen 1 : Welche "meisten" Algorithmen werden auf diese Weise implementiert? Soweit ich weiß, verwenden C4.5 und CART DFS. XGBoost verwendet BFS. Welche anderen Algorithmen oder Pakete verwenden BFS für Entscheidungsbäume?

Ausgabe 2:

LightGBM sagt aus:

LightGBM wächst Baum für Blatt (am besten zuerst). Es wählt das Blatt mit maximalem Delta-Verlust, um zu wachsen. Wenn dasselbe Blatt wächst, kann der blattweise Algorithmus mehr Verluste als der levelweise Algorithmus reduzieren.

Bildbeschreibung hier eingeben

Frage 2 : Ist es richtig zu sagen, dass Bäume mit gleichmäßigem Wachstum für alle Blätter die gleiche Tiefe haben?

Frage 3: Wenn Frage 2 nicht richtig ist, dann sehen die Bäume aus flachem und blattförmigem Wachstum am Ende der Durchquerung gleich aus (ohne Beschneiden usw.). Ist es eine richtige Aussage?

Frage 4: Wenn Frage 3 richtig ist, wie kann "ein blattweiser Algorithmus mehr Verluste reduzieren als ein ebenenweiser Algorithmus"? Hat es mit dem Post-Pruning-Algorithmus zu tun?

Jekaterina Kokatjuhha
quelle

Antworten:

10

Wenn Sie den ganzen Baum wachsen lassen, erhalten Sie mit der besten zuerst (blattweise) und der tiefsten zuerst (ebenenweise) denselben Baum. Der Unterschied liegt in der Reihenfolge, in der der Baum erweitert wird. Da wir Bäume normalerweise nicht in voller Tiefe anbauen, ist die Reihenfolge wichtig: Die Anwendung von Früherkennungskriterien und Schnittmethoden kann zu sehr unterschiedlichen Bäumen führen. Da blattweise Splits basierend auf ihrem Beitrag zum globalen Verlust und nicht nur auf dem Verlust entlang eines bestimmten Zweigs ausgewählt werden, werden Bäume mit niedrigeren Fehlern häufig (nicht immer) "schneller" als ebenenweise gelernt. Das heißt, für eine kleine Anzahl von Knoten wird die Leistung in Bezug auf das Blatt wahrscheinlich in Bezug auf das Niveau übertroffen. Wenn Sie weitere Knoten hinzufügen, ohne sie anzuhalten oder zu beschneiden, werden sie zu derselben Leistung konvergieren, da sie letztendlich buchstäblich denselben Baum erstellen.

Referenz:

Shi, H. (2007). Best-First Decision Tree Learning (Abschlussarbeit, Master of Science (MSc)). Die Universität von Waikato, Hamilton, Neuseeland. Abgerufen von https://hdl.handle.net/10289/2317


BEARBEITEN: In Bezug auf Ihre erste Frage sind sowohl C4.5 als auch CART Beispiele, bei denen es sich nicht um die beste Frage handelt. Hier sind einige relevante Inhalte aus der obigen Referenz:

1.2.1 Standardentscheidungsbäume

Standardalgorithmen wie C4.5 (Quinlan, 1993) und CART (Breiman et al., 1984) für die Top-Down-Induktion von Entscheidungsbäumen erweitern Knoten in der Reihenfolge der Tiefe in jedem Schritt unter Verwendung der Divide-and-Conquer-Strategie. Normalerweise umfasst das Testen an jedem Knoten eines Entscheidungsbaums nur ein einziges Attribut, und der Attributwert wird mit einer Konstanten verglichen. Die Grundidee von Standardentscheidungsbäumen besteht darin, zunächst ein Attribut auszuwählen, das am Wurzelknoten platziert werden soll, und anhand einiger Kriterien (z. B. Informationen oder Gini-Index) einige Verzweigungen für dieses Attribut vorzunehmen. Teilen Sie dann die Trainingsinstanzen in Teilmengen auf, eine für jeden Zweig, der sich vom Wurzelknoten aus erstreckt. Die Anzahl der Teilmengen entspricht der Anzahl der Zweige. Dann wird dieser Schritt für einen ausgewählten Zweig wiederholt, wobei nur die Instanzen verwendet werden, die ihn tatsächlich erreichen. Eine feste Reihenfolge wird zum Erweitern von Knoten verwendet (normalerweise von links nach rechts). Wenn zu irgendeinem Zeitpunkt alle Instanzen an einem Knoten dieselbe Klassenbezeichnung haben, die als reiner Knoten bezeichnet wird, wird die Aufteilung gestoppt und der Knoten wird zu einem Endknoten. Dieser Konstruktionsprozess wird fortgesetzt, bis alle Knoten rein sind. Anschließend folgt ein Schnitt, um Überanpassungen zu reduzieren (siehe Abschnitt 1.3).

1.2.2 Best-First-Entscheidungsbäume

Eine andere Möglichkeit, die bisher nur im Zusammenhang mit Boosting-Algorithmen evaluiert worden zu sein scheint (Friedman et al., 2000), besteht darin, Knoten in der Reihenfolge der besten zuerst anstelle einer festen Reihenfolge zu erweitern. Diese Methode fügt dem Baum in jedem Schritt den "besten" geteilten Knoten hinzu. Der "beste" Knoten ist der Knoten, der die Verunreinigung unter allen zum Teilen verfügbaren Knoten maximal verringert (dh nicht als Endknoten bezeichnet). Dies führt zwar zu demselben ausgewachsenen Baum wie die standardmäßige Depth-First-Erweiterung, ermöglicht es uns jedoch, neue Baumbeschneidungsmethoden zu untersuchen, bei denen die Anzahl der Erweiterungen durch Kreuzvalidierung ausgewählt wird. Auf diese Weise können sowohl das Vor- als auch das Nachschneiden durchgeführt werden, was einen fairen Vergleich zwischen ihnen ermöglicht (siehe Abschnitt 1.3).

Best-First-Entscheidungsbäume werden in einer Divide-and-Conquer-Weise konstruiert, die den Standard-Tiefen-First-Entscheidungsbäumen ähnelt. Die Grundidee, wie ein Best-First-Baum aufgebaut wird, lautet wie folgt. Wählen Sie zunächst ein Attribut aus, das am Stammknoten platziert werden soll, und machen Sie einige Verzweigungen für dieses Attribut basierend auf bestimmten Kriterien. Teilen Sie dann die Trainingsinstanzen in Teilmengen auf, eine für jeden Zweig, der sich vom Wurzelknoten aus erstreckt. In dieser Arbeit werden nur binäre Entscheidungsbäume betrachtet und somit ist die Anzahl der Zweige genau zwei. Dann wird dieser Schritt für einen ausgewählten Zweig wiederholt, wobei nur die Instanzen verwendet werden, die ihn tatsächlich erreichen. In jedem Schritt wählen wir aus allen Teilmengen, die für Erweiterungen zur Verfügung stehen, die "beste" Teilmenge aus. Dieser Konstruktionsprozess wird fortgesetzt, bis alle Knoten rein sind oder eine bestimmte Anzahl von Erweiterungen erreicht ist. Abbildung 1. 1 zeigt den Unterschied in der Aufteilungsreihenfolge zwischen einem hypothetischen binären Best-First-Baum und einem hypothetischen binären Tiefen-First-Baum. Beachten Sie, dass andere Reihenfolgen für den Baum mit der besten zuerst gewählt werden können, während die Reihenfolge im Fall mit der Tiefe zuerst immer dieselbe ist.

David Marx
quelle
Können Sie bitte auch die erste Frage beantworten?
Jekaterina Kokatjuhha
Aktualisiert meine Antwort. Die Kurzversion besagt, dass sowohl C4.5 als auch CART Beispiele für "Tiefensieg" und nicht "Bestensieg" sind.
David Marx
Meine erste Frage betraf nicht die Definition oder Erklärung von Best-First oder DFS. Und ich habe selbst festgestellt, dass C4.5 und CART DFS sind. Die erste Frage lautete: "Welche" meisten "Algorithmen werden levelweise implementiert? [...] Welche anderen Algorithmen oder Pakete verwenden BFS für Entscheidungsbäume?"
Jekaterina Kokatjuhha
1
Das Baumwachstum "mit der Tiefe zuerst" ist ebenmäßig. Das wollte ich dir sagen. Lesen Sie den Auszug, den ich für Sie hervorgehoben habe. Verwechseln Sie hier DFS und BFS nicht mit "Tiefe zuerst" und "Beste zuerst" Baumwachstum. Sie sind nicht dasselbe, und das Tiefenwachstum bezieht sich auf das, was Sie als "BFS" ​​bezeichnen, nicht auf "DFS".
David Marx
Das war der kritische Punkt, den ich die ganze Zeit vermisst habe. Vielen Dank.
Jekaterina Kokatjuhha