Drzewa decyzyjne: liść drzewa (najlepiej pierwszy) i poziom drzewa

Problem 1:

Jestem zdezorientowany opisem LightGBM dotyczącym sposobu, w jaki drzewo jest rozwijane.

Stanowią one:

Większość algorytmów uczenia się drzew decyzyjnych rośnie według poziomów (głębokości), jak na poniższym obrazku:

Pytania 1 : Jakie „większość” algorytmów stosuje się w ten sposób? O ile wiem C4.5 i CART używają DFS. XGBoost używa BFS. Jakie inne algorytmy lub pakiety używają BFS do drzew decyzyjnych?

Problem 2:

LightGBM stwierdza:

LightGBM wyrasta z drzewa po liściu (najlepiej na pierwszym miejscu). Wybierze liść o maksymalnej utracie delty. Podczas uprawy tego samego liścia algorytm liścia może zmniejszyć więcej strat niż algorytm poziomu.

Pytanie 2 : Czy słuszne jest stwierdzenie, że poziomo rosnące drzewa będą miały taką samą głębokość dla wszystkich liści?

Pytania 3: Jeśli pytanie 2 nie jest poprawne, drzewa na poziomie wzrostu i liścia będą wyglądać tak samo pod koniec przejścia (bez przycinania itp.). Czy to poprawne stwierdzenie?

Pytania 4: Jeśli pytanie 3 jest prawidłowe, w jaki sposób „algorytm liściasty może zmniejszyć więcej strat niż algorytm poziomu”? Czy ma to związek z algorytmem po przycinaniu?

Jeśli wyhodujesz pełne drzewo, najlepiej pierwsze (pod względem liści) i pierwsze pod względem głębokości (pod względem poziomu) da to samo drzewo. Różnica polega na kolejności rozwijania drzewa. Ponieważ zwykle nie hodujemy drzew do pełnej głębokości, kolejność ma znaczenie: zastosowanie kryteriów wczesnego zatrzymania i metod przycinania może prowadzić do bardzo różnych drzew. Ponieważ pod względem liści wybiera podziały na podstawie ich udziału w globalnej stracie, a nie tylko straty wzdłuż określonej gałęzi, często (nie zawsze) uczy się drzew o niższym błędzie „szybciej” niż poziom. To znaczy dla niewielkiej liczby węzłów, jeśli chodzi o liść, prawdopodobnie osiągnie lepsze wyniki niż poziom. W miarę dodawania kolejnych węzłów, bez zatrzymywania i przycinania, staną się one takie same, ponieważ ostatecznie dosłownie zbudują to samo drzewo.

Odniesienie:

Shi, H. (2007). Uczenie się na podstawie najlepszych drzew decyzyjnych (praca magisterska). University of Waikato, Hamilton, Nowa Zelandia. Źródło: https://hdl.handle.net/10289/2317

EDYCJA: Jeśli chodzi o twoje pierwsze pytanie, zarówno C4.5, jak i CART są przykładami dogłębnymi, a nie najlepszymi. Oto kilka istotnych treści z powyższego źródła:

1.2.1 Standardowe drzewa decyzyjne

Standardowe algorytmy, takie jak C4.5 (Quinlan, 1993) i CART (Breiman i in., 1984) do indukcji odgórnej drzew decyzyjnych, rozszerzają węzły w pierwszej kolejności na głębokości w każdym kroku, stosując strategię dziel i zwyciężaj. Zwykle w każdym węźle drzewa decyzyjnego testowanie obejmuje tylko jeden atrybut, a wartość atrybutu jest porównywana ze stałą. Podstawowa koncepcja standardowych drzew decyzyjnych polega na tym, że najpierw wybierz atrybut do umieszczenia w węźle głównym i utwórz dla niego niektóre gałęzie na podstawie niektórych kryteriów (np. Informacji lub indeksu Gini). Następnie podziel instancje szkoleniowe na podzbiory, po jednym dla każdej gałęzi rozciągającej się od węzła głównego. Liczba podzbiorów jest taka sama jak liczba oddziałów. Następnie ten krok powtarza się dla wybranej gałęzi, wykorzystując tylko te instancje, które faktycznie do niej dojdą. Ustalona kolejność jest używana do rozwijania węzłów (zwykle od lewej do prawej). Jeśli w dowolnym momencie wszystkie instancje w węźle mają tę samą etykietę klasy, która jest znana jako czysty węzeł, dzielenie zostanie zatrzymane, a węzeł zostanie przekształcony w węzeł końcowy. Ten proces budowy trwa, dopóki wszystkie węzły nie będą czyste. Następnie następuje proces przycinania w celu zmniejszenia przeregulowania (patrz sekcja 1.3).

1.2.2 Drzewa decyzyjne według najlepszych

Inną możliwością, która jak dotąd wydaje się być oceniana tylko w kontekście algorytmów zwiększających (Friedman i in., 2000), jest rozbudowa węzłów w kolejności od pierwszego do najlepszego zamiast w ustalonej kolejności. Ta metoda dodaje do drzewa „najlepszy” węzeł dzielony na każdym etapie. „Najlepszy” węzeł to węzeł, który maksymalnie zmniejsza zanieczyszczenie między wszystkimi węzłami dostępnymi do podziału (tj. Nieoznaczonymi jako węzły końcowe). Chociaż skutkuje to tym samym, w pełni rozwiniętym drzewem, co standardowe rozwinięcie w pierwszej kolejności, pozwala nam zbadać nowe metody przycinania drzew, które wykorzystują sprawdzanie krzyżowe w celu wybrania liczby rozszerzeń. W ten sposób można wykonać zarówno przycinanie wstępne, jak i przycinanie, co umożliwia rzetelne porównanie między nimi (patrz sekcja 1.3).

Drzewa decyzyjne z najlepszymi wynikami są konstruowane w sposób dzielący i podbijający podobny do standardowych drzew decyzyjnych z głębokością pierwszą. Podstawowa koncepcja budowy najlepszego drzewa jest następująca. Najpierw wybierz atrybut do umieszczenia w węźle głównym i utwórz kilka rozgałęzień dla tego atrybutu na podstawie niektórych kryteriów. Następnie podziel instancje szkoleniowe na podzbiory, po jednym dla każdej gałęzi rozciągającej się od węzła głównego. W tej pracy rozważane są tylko binarne drzewa decyzyjne, a zatem liczba rozgałęzień wynosi dokładnie dwa. Następnie ten krok powtarza się dla wybranej gałęzi, wykorzystując tylko te instancje, które faktycznie do niej dojdą. Na każdym etapie wybieramy „najlepszy” podzbiór spośród wszystkich podzbiorów dostępnych dla rozszerzeń. Ten proces konstruowania trwa, dopóki wszystkie węzły nie będą czyste lub nie zostanie osiągnięta określona liczba rozszerzeń. Rycina 1. 1 pokazuje różnicę w kolejności podziału między hipotetycznym dwójkowym drzewem o najlepszym pierwszeństwie a hipotetycznym dwójkowym drzewem o pierwszej głębokości. Zauważ, że dla pierwszego drzewa można wybrać inne kolejność, podczas gdy kolejność jest zawsze taka sama w przypadku pierwszej głębokości.