📊 Drzewo decyzyjne na żywo

Dla kandydata na podział dzielącego zbiór rodzica S na lewe dziecko L i prawe dziecko R, przyrost informacji wynosi ΔGini = Gini(S) − (|L|/|S|) · Gini(L) − (|R|/|S|) · Gini(R). CART sprawdza każdy punkt środkowy między kolejnymi posortowanymi wartościami cechy dla każdej cechy i wybiera parę (cecha, próg) z maksymalnym ΔGini. Ważność cechy to suma redukcji indeksu Giniego ważonych liczbą próbek w węźle, zsumowana po wszystkich podziałach dla danej cechy i znormalizowana tak, aby suma po wszystkich cechach wynosiła 1.

Drzewa decyzyjne pojawiają się w triażu medycznym (np. ocena ryzyka sepsy na podstawie parametrów życiowych), scoringu kredytowym (prawdopodobieństwo niespłacenia pożyczki), wykrywaniu oszustw i przewidywaniu odejść klientów. Pojedyncze płytkie drzewo jest często używane jako interpretowalny model bazowy, ponieważ każdą ścieżkę decyzyjną można wyrazić prostą regułą w rodzaju „jeśli dochód > 40 000 i wskaźnik zadłużenia < 0,3, zatwierdź”. Głębsze drzewa i zespoły (lasy losowe, XGBoost) zamieniają tę przejrzystość na wyższą dokładność na złożonych zbiorach danych.

Częstym błędnym przekonaniem jest to, że głębsze drzewo jest zawsze lepsze, ponieważ osiąga 100% dokładności na danych treningowych. W rzeczywistości nieograniczone drzewo zapamiętuje szum w danych treningowych i słabo generalizuje na nowe próbki — to jest właśnie przeuczenie. Rozwiązaniem jest regularyzacja: ograniczenie maksymalnej głębokości, wymaganie minimalnej liczby próbek na liść lub zastosowanie przycinania kosztowo-złożonościowego (alpha · |liście|), które karze złożoność. Do wyboru tych hiperparametrów stosuje się walidację krzyżową.

Algorytm CART został wprowadzony w 1984 roku przez Leo Breimana, Jerome'a Friedmana, Richarda Olshena i Charlesa Stone'a w książce „Classification and Regression Trees”. Breiman rozwinął później te idee, tworząc bagging (1996) i lasy losowe (2001), a Friedman rozszerzył je o wzmacnianie gradientowe (1999–2001). Te trzy metody wspólnie zrewolucjonizowały uczenie maszynowe na danych tabelarycznych i pozostają szeroko stosowane po dziś dzień.

Las losowy trenuje setki drzew CART na próbkach bootstrapowych danych, przy czym każde drzewo rozważa losowy podzbiór cech przy każdym podziale, a następnie uśrednia ich predykcje. Zmniejsza to wariancję bez istotnego zwiększenia obciążenia. Wzmacnianie gradientowe trenuje natomiast drzewa sekwencyjnie, każde dopasowując się do błędów resztkowych dotychczasowego zespołu, co redukuje obciążenie. Obie metody dziedziczą interpretowalność pojedynczych podziałów, ale są znacznie dokładniejsze na złożonych zbiorach danych niż pojedyncze drzewo.

Tak — to właśnie litera R w CART. W regresji każdy liść przewiduje średnią wartość docelową próbek, które do niego trafiają, a podziały dobiera się tak, aby zminimalizować sumę kwadratów reszt zamiast indeksu Giniego. Diagram drzewa i logika rekurencyjnego podziału są identyczne; zmienia się jedynie predykcja liścia i kryterium podziału. Ta symulacja skupia się na klasyfikacji binarnej, ale ten sam algorytm z MSE jako kryterium daje drzewa regresyjne stosowane w modelach cen nieruchomości i prognozowania popytu.

Aktywne obszary badań obejmują różniczkowalne („miękkie”) drzewa decyzyjne, które można trenować od początku do końca metodą gradientu prostego i osadzać w sieciach neuronowych, drzewa ukośne wykorzystujące liniowe kombinacje cech zamiast podziałów osiowych, aby skuteczniej opisywać granice ukośne, oraz drzewa przyczynowe, które szacują heterogeniczne efekty interwencji w eksperymentach randomizowanych. Badania nad interpretowalnością koncentrują się także na metodach wyjaśniania post-hoc (wartości SHAP), które rozkładają predykcję dowolnego zespołu drzew na wkłady poszczególnych cech.

CART (Classification and Regression Trees) to metoda uczenia nadzorowanego, która rekurencyjnie dzieli przestrzeń cech za pomocą podziałów osiowych. Każdy węzeł wewnętrzny sprawdza jedną cechę względem progu i kieruje punkty w lewo lub w prawo, a każdy liść przypisuje klasę większościową spośród próbek, które do niego docierają. Tutaj klasyfikuje punkty na dwa kolory, Klasę 0 i Klasę 1.

W każdym węźle algorytm sortuje punkty według każdej cechy i próbuje jako próg punktu środkowego między kolejnymi wartościami. Wybiera podział z największą redukcją indeksu Giniego, gdzie przyrost równa się Gini rodzica minus ważona liczbą próbek suma Gini lewego i prawego dziecka. Ten zachłanny, lokalnie optymalny wybór powtarza się, aż reguła zatrzymania wstrzyma dalszy wzrost.

Max Depth ogranicza liczbę poziomów, do jakich może urosnąć drzewo, więc głębsze drzewo może wycinać drobniejsze regiony, ale ryzykuje przeuczeniem. Min Samples Leaf odrzuca każdy podział, który pozostawiłby w węźle potomnym mniej punktów niż wskazana liczba, co zachowuje statystyczną sensowność liści. Razem regularyzują drzewo i pozwalają eksplorować kompromis między głębokością a dokładnością.

Tak, główna logika odpowiada standardowemu klasyfikatorowi CART: wyczerpujące przeszukiwanie progów, przyrost oparty na indeksie Giniego, liście oparte na zasadzie większości głosów oraz ważność cech mierzona jako łączna redukcja Giniego dla danej cechy. Dla przejrzystości uproszczono ją do dwóch cech i klas binarnych, a zamiast przycinania kosztowo-złożonościowego stosowanego w bibliotekach produkcyjnych wykorzystuje wstępne przycinanie poprzez limity głębokości i liczby próbek w liściu.

Drzewa decyzyjne wykonują wyłącznie cięcia osiowe, więc gładkie lub ukośne granice muszą być przybliżane wieloma małymi prostokątami. Wzorce takie jak XOR i Two Moons nie mają żadnego użytecznego podziału osiowego blisko korzenia, więc drzewo potrzebuje dodatkowej głębokości i tworzy granicę o kształcie schodkowym. To ograniczenie jest jednym z powodów, dla których zespoły takie jak lasy losowe i wzmacnianie gradientowe łączą wiele drzew.