Czy drzewa decyzyjne są prawie zawsze drzewami binarnymi?

21

Niemal każdy przykład drzewa decyzyjnego, z którym się zetknąłem, jest drzewem binarnym. Czy to jest dość uniwersalne? Czy większość standardowych algorytmów (C4.5, CART itp.) Obsługuje tylko drzewa binarne? Z tego, co zbieram, CHAID nie ogranicza się do drzew binarnych, ale wydaje się, że jest to wyjątek.

Dwukierunkowy podział, po którym następuje kolejny dwukierunkowy podział na jedno z dzieci, nie jest tym samym, co pojedynczy trójstronny podział. To może być punkt akademicki, ale staram się upewnić, że rozumiem najczęstsze przypadki użycia.

machine-learning data-mining cart

— Michael McGowan
źródło

18

Jest to głównie problem techniczny: jeśli nie ograniczysz się do opcji binarnych, istnieje po prostu zbyt wiele możliwości następnego podziału w drzewie. Więc zdecydowanie masz rację we wszystkich punktach poruszonych w twoim pytaniu.

Należy pamiętać, że większość algorytmów drzewiastych działa krok po kroku i nawet nie gwarantuje się, że dają najlepszy możliwy wynik. To tylko jedno dodatkowe zastrzeżenie.

W większości praktycznych celów, choć nie podczas budowy / przycinania drzewa, dwa rodzaje podziałów są równoważne, biorąc pod uwagę, że pojawiają się bezpośrednio po sobie.

— Nick Sabbe
źródło

Tylko w celu wzmocnienia pierwszego punktu: liczba możliwych podziałów rośnie wykładniczo. Jeśli dzielisz na zmienną ciągłą, która ma 1000 różnych wartości, istnieje 999 podziałów binarnych, ale 999 * 998 podziałów trójdzielnych.

— Peter Flom - Przywróć Monikę

2

@Peter Właściwie istnieją trójskładnikowe podziały.

(\binom{1000 - 1}{3 - 1}) = 999 * 998 / 2

$\binom{1000-1}{3-1} = 999*998/2$

— whuber

5

Dwukierunkowy podział, po którym następuje kolejny dwukierunkowy podział na jedno z dzieci, to nie to samo, co pojedynczy trójstronny podział

Nie jestem pewien, co masz na myśli. Dowolny podział wielokrotny może być reprezentowany jako seria podziałów dwukierunkowych. W przypadku podziału trójstronnego możesz podzielić na A, B i C, najpierw dzieląc na A&B w porównaniu do C, a następnie dzieląc A z B.

Dany algorytm może nie wybrać tej konkretnej sekwencji (zwłaszcza jeśli, jak większość algorytmów, jest zachłanny), ale z pewnością mógłby. A jeśli jakakolwiek procedura randomizacji lub stagewise zostanie wykonana jak w przypadkowych lasach lub drzewach wzmocnionych, szanse na znalezienie właściwej sekwencji podziałów wzrosną. Jak zauważyli inni, podziały w wielu kierunkach są kosztowne obliczeniowo, więc biorąc pod uwagę te alternatywy, większość badaczy wydaje się wybierać podziały binarne.

Mam nadzieję że to pomoże

— David J. Harris
źródło

3

Tak Rozumiem, że A, B i C można osiągnąć najpierw dzieląc na A&B vs. C, a następnie dzieląc A z B. Rzeczywiście miałem na myśli, że dany algorytm może nie wybrać tej konkretnej sekwencji.

— Michael McGowan

2

Jeśli chodzi o wykorzystanie drzewa decyzyjnego i dzielenia (binarne kontra inne), znam tylko CHAID, który ma podziały niebinarne, ale prawdopodobnie są inne. Dla mnie głównym zastosowaniem podziału niebinarnego jest ćwiczenie eksploracji danych, w którym szukam sposobu optymalnego binowania zmiennej nominalnej z wieloma poziomami. Seria podziałów binarnych nie jest tak przydatna jak grupowanie wykonane przez CHAID.

— B_Miner
źródło

To zabawne, że wspomniałeś o binowaniu, ponieważ myślenie o binowaniu sprawiło, że zacząłem się zastanawiać nad tym pytaniem (chociaż myślałem o binowaniu zmiennych numerycznych zamiast zmiennych nominalnych).

— Michael McGowan

@Michael, Tak, to też działa, ale wyrzucasz informacje. Używam go, gdy muszę łączyć rzadkie poziomy zmiennej nominalnej - kiedy ostateczne modelowanie zostanie wykonane bez podejścia typu drzewa (powiedzmy, że regresja logistyczna lub SVM i wiele rzadkich zmiennych manekina powoduje problemy)

— B_Miner

0

Przeczytaj to

Ze względów praktycznych (eksplozja kombinatoryczna) większość bibliotek implementuje drzewa decyzyjne z podziałem binarnym. Zaletą jest to, że są kompletne z NP (Hyafil, Laurent i Ronald L. Rivest. „Konstruowanie optymalnych binarnych drzew decyzyjnych jest NP-kompletne”. Information Processing Letters 5.1 (1976): 15-17.)

— Zapłać C.
źródło