Są algorytmami drzewa decyzyjnego liniowymi lub nieliniowymi

21

Ostatnio mój przyjaciel został zapytany, czy algorytmy drzewa decyzyjnego są algorytmami liniowymi czy nieliniowymi w wywiadzie. Próbowałem poszukać odpowiedzi na to pytanie, ale nie znalazłem satysfakcjonującego wyjaśnienia. Czy ktoś może odpowiedzieć i wyjaśnić rozwiązanie tego pytania? Jakie są też inne przykłady nieliniowych algorytmów uczenia maszynowego?

— użytkownik2966197
źródło

Zastanawia się, w jakim kontekście mieli na myśli regresję, liniowo rozdzielalne dane?

— image_doctor,

1

Prawdopodobnie oznaczały granicę między klasami; czy składa się z hiperpłaszczyzn, czy nie.

— Emre

17

Drzewo decyzyjne jest nieliniowym odwzorowaniem Xna y. Łatwo to sprawdzić, jeśli wybierzesz dowolną funkcję i utworzysz drzewo na maksymalną głębokość.

Na przykład:

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

Oczywiście jest to drzewo całkowicie nadpasowane i nie uogólnia się. Ale pokazuje, dlaczego drzewo decyzyjne jest mapowaniem nieliniowym.

— odwrócenie
źródło

10

Ostatnio mój przyjaciel został zapytany, czy algorytm drzewa decyzyjnego jest algorytmem liniowym czy nieliniowym w wywiadzie

Drzewa decyzyjne to nieliniowy klasyfikator, taki jak sieci neuronowe itp. Zasadniczo jest wykorzystywany do klasyfikowania danych nieliniowo rozdzielalnych.

Nawet w przypadku przykładu regresji drzewo decyzyjne jest nieliniowe.

Na przykład linia regresji liniowej wyglądałaby mniej więcej tak:

Czerwone kropki to punkty danych.

A wykres regresji drzewa decyzyjnego wyglądałby mniej więcej tak:

Zatem drzewa decyzyjne są nieliniowe

— Dawny33
źródło

Zwiększenie głębokości drzewa doprowadziłoby do lepszego dopasowania, a tym samym do bardziej nieliniowej struktury.

— Dawny33

3

Drzewa decyzyjne są nieliniowe. W przeciwieństwie do regresji liniowej nie ma równania do wyrażenia związku między zmiennymi niezależnymi i zależnymi.

Dawny:

Regresja liniowa - cena owoców = b0 + b1 * Świeżość + b2 * Rozmiar

Drzewo decyzyjne - Węzły: Dojrzałe - Tak lub nie | Świeży - tak lub nie | Rozmiar - <5,> 5, ale <10 i> 10 |

W drugim przypadku nie ma liniowej zależności między zmiennymi niezależnymi i zależnymi.

3

Jak wielu zauważyło, drzewo regresji / decyzji jest modelem nieliniowym. Należy jednak pamiętać, że jest to fragmentaryczny model liniowy : w każdym sąsiedztwie (zdefiniowanym w sposób nieliniowy) jest liniowy. W rzeczywistości model jest tylko lokalną stałą.

$\theta$

y_{i} = α_{1} 1 (x_{i} < θ) + α_{2} 1 (x_{i} \geq θ) + ϵ_{i}

$y_i = \alpha_1 1(x_i < \theta) + \alpha_2 1(x_i \geq \theta) + \epsilon_i$

$1(A)$

— Matifou
źródło

2

$VC$ $2^d$ $d$ $2^{2^d}$ $m$ $d$ $min(2^d, m)$ ID3C4.5

— Głoska bezdźwięczna
źródło