Sind Entscheidungsbäume fast immer Binärbäume?

21

Fast jedes Entscheidungsbaum-Beispiel, auf das ich gestoßen bin, ist zufällig ein Binärbaum. Ist das so ziemlich universell? Unterstützen die meisten Standardalgorithmen (C4.5, CART usw.) nur binäre Bäume? Soweit ich weiß, ist CHAID nicht auf binäre Bäume beschränkt, aber das scheint eine Ausnahme zu sein.

Eine Zwei-Wege-Trennung, gefolgt von einer weiteren Zwei-Wege-Trennung bei einem der Kinder, ist nicht dasselbe wie eine einzelne Drei-Wege-Trennung. Dies mag ein akademischer Punkt sein, aber ich versuche sicherzustellen, dass ich die häufigsten Anwendungsfälle verstehe.

machine-learning data-mining cart Michael McGowan
quelle

Antworten:

18

Dies ist hauptsächlich ein technisches Problem: Wenn Sie sich nicht auf binäre Auswahlmöglichkeiten beschränken, gibt es einfach zu viele Möglichkeiten für die nächste Aufteilung im Baum. Sie haben in allen Punkten, die in Ihrer Frage angesprochen wurden, definitiv Recht.

Beachten Sie, dass die meisten baumartigen Algorithmen schrittweise arbeiten und auch als solche nicht garantiert das bestmögliche Ergebnis liefern. Dies ist nur eine zusätzliche Einschränkung.

Für die meisten praktischen Zwecke, jedoch nicht während des Baus / Beschneidens des Baums, sind die beiden Arten der Teilung jedoch gleichwertig, da sie unmittelbar nacheinander auftreten.

Nick Sabbe
quelle
Nur um auf Ihren ersten Punkt einzugehen: Die Anzahl der möglichen Teilungen steigt exponentiell an. Wenn Sie eine kontinuierliche Variable mit 1000 verschiedenen Werten aufteilen, gibt es 999 binäre Aufteilungen, aber 999 * 998 trinäre Aufteilungen.
Peter Flom - Wiedereinsetzung von Monica
2
@Peter Es gibt tatsächlich 998/2 ternäre Teilungen. (1000−13−1)=999∗998/2
Whuber
5

Eine Zwei-Wege-Aufteilung, gefolgt von einer weiteren Zwei-Wege-Aufteilung bei einem der Kinder, ist nicht dasselbe wie eine einzelne Drei-Wege-Aufteilung

Ich bin mir nicht sicher, was du hier meinst. Jede Mehrwege-Aufteilung kann als eine Reihe von Zweiwege-Aufteilungen dargestellt werden. Bei einer Dreifachaufteilung können Sie in A, B und C aufteilen, indem Sie zuerst in A & B und dann in C aufteilen und dann A von B trennen.

Ein gegebener Algorithmus wählt möglicherweise nicht diese bestimmte Sequenz aus (insbesondere, wenn er, wie die meisten Algorithmen, gierig ist), aber dies könnte durchaus der Fall sein. Und wenn zufällige oder stufenweise Abläufe wie in zufälligen Wäldern oder aufgestockten Bäumen durchgeführt werden, steigt die Wahrscheinlichkeit, die richtige Abfolge von Teilungen zu finden. Wie andere bereits ausgeführt haben, sind Mehrwegeteilungen rechenintensiv. Angesichts dieser Alternativen scheinen sich die meisten Forscher für binäre Teilungen entschieden zu haben.

Hoffe das hilft

David J. Harris
quelle
3
Ja, ich verstehe, dass A, B und C erreicht werden können, indem zuerst in A & B vs. C aufgeteilt wird und dann A von B getrennt wird. Mein Punkt war in der Tat, dass ein gegebener Algorithmus diese bestimmte Sequenz möglicherweise nicht auswählt.
Michael McGowan
2

In Bezug auf die Verwendung des Entscheidungsbaums und der Aufteilung (binär im Vergleich zu anderen) kenne ich nur CHAID mit nicht-binären Aufteilungen, aber es gibt wahrscheinlich auch andere. Für mich ist die Hauptanwendung einer nicht-binären Aufteilung das Data-Mining, bei dem es darum geht, eine nominelle Variable mit vielen Ebenen optimal zu bündeln. Eine Reihe von binären Teilungen ist nicht so nützlich wie eine von CHAID durchgeführte Gruppierung.

B_Miner
quelle
Es ist lustig, dass Sie das Binning erwähnt haben, denn das Nachdenken über das Binning hat mich dazu veranlasst, über diese Frage nachzudenken (obwohl ich über das Binning von numerischen Variablen und nicht von nominalen Variablen nachgedacht habe).
Michael McGowan
@Michael, ja das funktioniert auch aber du wirfst Informationen weg. Ich benutze es, wenn ich dünne Ebenen einer nominalen Variablen kombinieren muss - wenn die endgültige Modellierung ohne einen baumartigen Ansatz durchgeführt wird (etwa logistische Regression oder SVM und viele
dünne
0

Bitte lesen Sie dies

Aus praktischen Gründen (kombinatorische Explosion) implementieren die meisten Bibliotheken Entscheidungsbäume mit binären Teilungen. Das Schöne ist, dass sie NP-vollständig sind (Hyafil, Laurent und Ronald L. Rivest. "Die Erstellung optimaler binärer Entscheidungsbäume ist NP-vollständig." Information Processing Letters 5.1 (1976): 15-17.)

Bezahle C.
quelle