Dlaczego drzewa decyzyjne nie są drogie obliczeniowo?

38

We wstępie do nauki statystycznej z aplikacjami w R autorzy piszą, że dopasowanie drzewa decyzyjnego jest bardzo szybkie, ale nie ma to dla mnie sensu. Algorytm musi przejść przez każdą funkcję i podzielić ją na wszystkie możliwe sposoby, aby znaleźć optymalny podział. W przypadku operacji numerycznych z obserwacjami może to skutkować podziałami dla każdej operacji. $n$ $n$

Czy nie rozumiem, jak działa podział binarny? Czy istnieje powód, dla którego ten algorytm nie potrwa długo?

cart

— matt_js
źródło

1

+1 za pytanie. Możesz zacząć sprawdzać notatkę z wykładu , strona 15, użyj algorytmu

zamiast

.

O (N)

$O(N)$

O (N^{2})

$O(N^2)$

— Haitao Du

40

Algorytmy drzew decyzyjnych nie obliczają wszystkich możliwych drzew, gdy pasują do drzewa. Gdyby to zrobili, rozwiązaliby trudną NPproblem. Algorytmy dopasowania drzewa decyzyjnego zazwyczaj podejmują chciwe decyzje w procesie dopasowania - na każdym etapie optymalizują pod-problem w celu znalezienia optymalnego podziału z danymi w danym węźle i kontynuują proces dopasowania. Ponadto, gdy wchodzisz głębiej w drzewo decyzyjne, masz mniejszy zestaw danych, który dotarł do danego węzła, dzięki czemu będziesz optymalizować regułę podziału na mniejszy podzbiór danych. Wszystkie te wybory są liniowymi skanami danych w danym węźle. Nie jest to skomplikowane, ale może stać się nieco kosztowne obliczeniowo, jeśli masz dużą liczbę obserwacji lub dużą liczbę zmiennych towarzyszących do podzielenia. Jednak wiele pracy można podzielić i wysłać na różne maszyny, aby pracować, więc istnieją sposoby na zbudowanie architektury obliczeniowej w celu zwiększenia jej skali.

— Lucas Roberts
źródło

10

Innymi słowy, jest mniej więcej porównywalny z wyszukiwaniem binarnym.

— Robert Harvey

1

l o g_{2} (N)

$log_2(N)$

2

Zgadzam się, ale zasada nadal obowiązuje. (Dlatego użyłem słowa „mniej więcej”)

— Robert Harvey

2

Istnieją pewne różnice między algorytmami CART i C4.5 do budowania drzew decyzyjnych. Na przykład CART używa Gini Impurity do wybierania funkcji, podczas gdy C.4.5 używa Shannon Entropy. Nie sądzę, że różnice są istotne dla odpowiedzi, więc nie będę rozróżniał między nimi.

Co sprawia, że drzewa decyzyjne są szybsze niż mogłoby się wydawać:

Jak powiedzieli inni, algorytmy te są algorytmami jednokierunkowymi. Dokonują lokalnych optymalizacji. W każdej gałęzi wybierają regułę, która maksymalizuje / minimalizuje dowolną używaną metrykę (Gini lub Entropy). Oznacza to, że mogą ominąć reguły, w których użycie operatora logicznego, takiego jak andpoprawiłoby drzewo. Oznacza to, że powinieneś być bardzo ostrożny / sprytny podczas inżynierii funkcji. Załóżmy na przykład, że próbujesz przewidzieć, ile osób pije, możesz polecić takie rzeczy jak inżynier new_feature = hour > 22 & hour < 4 & (friday_night | saturday_night). Drzewa decyzyjne mogą nie uwzględniać takich zasad lub przypisywać im mniejsze znaczenie niż powinny.
$X_1 = \{3,1.5,2.5,2,1\}$ X <= 1X <= 1.5X <= 2 $X_1 = \{1,1.5,2,2.5,3\}$ X <= 1X <= 1.5 $\bar x$ $v$ $\bar x \leftarrow \frac{n\bar x+v}{n+1}$
Drzewa decyzyjne mogą być zrównoleglone. Każdy węzeł składa się z dwóch niezależnych gałęzi. Dlatego w każdej gałęzi masz możliwość równoległego tworzenia drzewa. Ponadto sam wybór funkcji można również zrównoleglić. To sprawia, że pakiety są xgboosttak szybkie. Zwiększanie gradientu jest sekwencyjne i nie może być zrównoleglone, ale same drzewa mogą.

— Ricardo Cruz
źródło

1

Aby wzbogacić odpowiedzi,

Hierarchiczne drzewa decyzyjne równoległe do osi są szybkie (CART, C4.5), ale istnieją inne alternatywy, takie jak niehierarchiczne drzewa decyzyjne lub te, które wykonują skośne partycje, które nie są, chociaż mogą być bardziej dokładne. Jeśli jesteś zainteresowany, sprawdź następujące referencje (nie są to wybitne propozycje).

Niehierarchiczny:

Grubinger, T., Zeileis, A. i Pfeiffer, K.-., 2014. Evtree: Ewolucyjne uczenie się optymalnie globalnych drzew klasyfikacji i regresji w RJStat.Software 61 (1), 1-29.

Podziały ukośne:

Murthy, SK, Kasif, S. i Salzberg, S., 1994. System indukcji ukośnych drzew decyzyjnych. J. Artif. Intel. Res. 2 (1), 1-32. http://dx.doi.org/doi:10.1613/jair.63 . Cantú-Paz, E. i Kamath, C., 2003. Indukowanie skośnych drzew decyzyjnych za pomocą algorytmów ewolucyjnych. IEEE Trans. Evol. Comput. 7 (1), 54–68. http://dx.doi.org/10.1109/TEVC.2002.806857 . Heath, D., Kasif, S. i Salzberg, S., 1993. Indukcja skośnych drzew decyzyjnych. J. Artif. Intel. Res. 2 (2), 1002–1007.

Powodzenia!

— Rafa_Mas
źródło