Sind Entscheidungsbaumalgorithmen linear oder nichtlinear?

21

Kürzlich wurde ein Freund von mir in einem Interview gefragt, ob Entscheidungsbaumalgorithmen lineare oder nichtlineare Algorithmen sind. Ich habe versucht, nach Antworten auf diese Frage zu suchen, konnte aber keine zufriedenstellende Erklärung finden. Kann jemand die Lösung dieser Frage beantworten und erklären? Was sind noch andere Beispiele für nichtlineare Algorithmen für maschinelles Lernen?

user2966197
quelle
Frage mich, in welchem ​​Kontext sie diese Regression bedeuteten, linear trennbare Daten?
image_doctor
1
Sie meinten wahrscheinlich die Grenze zwischen den Klassen; Besteht es aus Hyperebenen oder nicht?
Emre

Antworten:

17

Ein Entscheidungsbaum ist eine nichtlineare Abbildung von Xbis y. Dies ist leicht zu erkennen, wenn Sie eine beliebige Funktion übernehmen und einen Baum mit maximaler Tiefe erstellen.

Beispielsweise:

if x = 1, y = 1
if x = 2, y = 15
if x = 3, y = 3
if x = 4, y = 27
...

Natürlich ist dies ein vollständig überpassender Baum und wird nicht verallgemeinern. Aber es zeigt, warum ein Entscheidungsbaum eine nichtlineare Abbildung ist.

Inversion
quelle
10

Kürzlich wurde ein Freund von mir in einem Interview gefragt, ob der Entscheidungsbaumalgorithmus ein linearer oder ein nichtlinearer Algorithmus ist

Entscheidungsbäume sind nichtlineare Klassifizierer wie neuronale Netze usw. Sie werden im Allgemeinen zum Klassifizieren nichtlinear trennbarer Daten verwendet.

Selbst wenn Sie das Regressionsbeispiel betrachten, ist der Entscheidungsbaum nicht linear.

Zum Beispiel würde eine lineare Regressionslinie ungefähr so ​​aussehen:

Bildbeschreibung hier eingeben

Die roten Punkte sind die Datenpunkte.

Und ein Entscheidungsbaum-Regressionsdiagramm würde ungefähr so ​​aussehen:

Bildbeschreibung hier eingeben

Entscheidungsbäume sind also eindeutig nicht linear

Dawny33
quelle
Das Erhöhen der Tiefe des Baums würde zu einer stärkeren Überanpassung und damit zu einer nichtlineareren Struktur führen.
Dawny33
3

Entscheidungsbäume sind nicht linear. Im Gegensatz zur linearen Regression gibt es keine Gleichung, um die Beziehung zwischen unabhängigen und abhängigen Variablen auszudrücken.

Ex:

Lineare Regression - Fruchtpreis = b0 + b1 * Frische + b2 * Größe

Entscheidungsbaum - Knoten: Reif - Ja oder Nein | Frisch - ja oder nein | Größe - <5,> 5, aber <10 und> 10 |

Im zweiten Fall gibt es keine lineare Beziehung zwischen unabhängigen und abhängigen Variablen.


quelle
3

Wie viele betonten, ist ein Regressions- / Entscheidungsbaum ein nicht lineares Modell. Beachten Sie jedoch, dass es sich um ein stückweise lineares Modell handelt: In jeder Nachbarschaft (nicht linear definiert) ist es linear. Tatsächlich ist das Modell nur eine lokale Konstante.

θ

yich=α11(xich<θ)+α21(xichθ)+ϵich

1(EIN)

Matifou
quelle
2

VC2dd22dmdmin(2d,m)ID3C4.5

Medien
quelle