03 · Nadzorowane · 4 min czytania · Interaktywne · aktualizacja
Jak działa drzewo decyzyjne i dlaczego buduje się z nich XGBoost?
W skrócie
Drzewo decyzyjne klasyfikuje przykład serią pytań tak/nie o pojedyncze cechy („wiek ≤ 6,5?”) aż do liścia z decyzją. Dzieli przestrzeń cech na prostokąty.
Co to jest
Drzewo decyzyjne to model, który prowadzi przykład od korzenia do liścia serią pytań o jedną cechę i próg, np. „wiek ≤ 6,5?”; liść podaje klasę albo wartość. Każde pytanie dzieli przestrzeń cech wzdłuż jednej osi, więc drzewo wycina z niej prostokąty (hiperprostokąty) i w każdym podejmuje osobną decyzję.
Drzewa stosuje się samodzielnie, gdy liczy się czytelność reguł, a przede wszystkim jako element składowy lasów losowych i boostingu gradientowego (XGBoost, LightGBM, CatBoost) — standardu dla danych tabelarycznych.
Mechanizm — dlaczego tak działa
Budowa jest zachłanna (algorytm CART, Breiman i in. 1984). W korzeniu drzewo sprawdza każdą cechę i każdy sensowny próg i wybiera podział, po którym dwie powstałe grupy są najbardziej jednorodne — mierzone spadkiem nieczystości Giniego lub entropii (klasyfikacja) albo wariancji (regresja). Potem powtarza to w każdej gałęzi osobno, aż gałąź jest czysta, za mała albo osiągnięto limit głębokości.
Dlaczego to wystarcza? Drzewo nie musi wiedzieć, jak cechy łączą się we wzór: kolejne pytania same wycinają obszary, w tym progi i interakcje, których model liniowy nie narysuje żadną prostą. Dwa pytania o tę samą cechę dają przedział, pytania o różne cechy — prostokąt, a pytanie zadane tylko w jednej gałęzi to interakcja („wiek ma znaczenie, ale tylko u mężczyzn”). Każdy liść to stała, więc drzewo o głębokości d ma najwyżej 2ᵈ liści i jest funkcją schodkową. Zależności ukośne, np. suma dwóch cech, wymagają wielu pytań zamiast jednego.
Pojedyncze drzewo ma dużą wariancję: niewielka zmiana danych zmienia pytanie w korzeniu, a z nim całe drzewo. Głębokie drzewo zapamiętuje dane, płytkie się niedoucza. Las losowy uśrednia wiele drzew trenowanych na różnych próbkach i podzbiorach cech (redukcja wariancji); boosting dokłada płytkie drzewa, z których każde poprawia błędy poprzednich (redukcja obciążenia). Z tych samych prostokątów powstaje wtedy gładsza i dokładniejsza granica.
Zastrzeżenie: drzewa nie wymagają standaryzacji (pytanie o próg nie zmienia się przy rosnącym przekształceniu cechy), dobrze znoszą różne skale i — w niektórych implementacjach — braki danych. Nie ekstrapolują jednak poza zakres treningu, a bez agregacji są niestabilne.
Na przykładzie
Titanic: 891 pasażerów, przeżyło 38,4%. Cechy: klasa, płeć, wiek (braki uzupełnione medianą), liczba rodzeństwa lub małżonków, rodziców lub dzieci, cena biletu; podział 70/30, random_state=0. Model „nikt nie przeżył” ma na teście 61,6%. Drzewo o głębokości 1 zadaje jedno pytanie — o płeć — i osiąga 79,1%. Drzewo głębokości 2 na całym zbiorze czyta się jak opis katastrofy: z kobiet z 1. i 2. klasy przeżyło 161 ze 170, z kobiet z 3. klasy 72 ze 144, z chłopców do 6,5 roku 16 z 24, a ze starszych mężczyzn tylko 93 z 553.
Drzewo głębokości 3 (8 liści) miało na teście 83,2%. Drzewo bez limitu urosło do 143 liści, osiągnęło 98,6% na treningu i tylko 78,0% na teście — gorzej niż jedno pytanie o płeć. W 5-krotnej walidacji krzyżowej najlepiej wypadły głębokości 3–4 (81,8% i 82,2%), a drzewo bez limitu — 77,8%.
Dane: Titanic
W praktyce
- scikit-learn:
DecisionTreeClassifier(criterion="gini", max_depth=None)domyślnie rośnie do czystych liści — ustawmax_depth,min_samples_leaflubccp_alpha(przycinanie);plot_treeiexport_textpokazują reguły. - XGBoost: domyślnie
max_depth=6; LightGBM rośnie liśćmi (num_leaves=31); CatBoost buduje drzewa symetryczne. - Głębokość 1–3 to słabe drzewa typowe dla boostingu; samodzielne, czytelne drzewo ma zwykle głębokość 3–5.
- Na danych tabelarycznych boosting drzew zwykle bije sieci; sieci wygrywają na obrazach, tekście i przy bardzo dużych zbiorach.
- Typowy błąd:
max_depth=Nonena małych danych i wiara w wynik treningowy; drugi — standaryzacja „dla drzewa”, która nic nie zmienia.
Najczęstsze pytania
- Jak drzewo decyzyjne wybiera, o co zapytać?
- Sprawdza każdą cechę i każdy próg między sąsiednimi wartościami, liczy, o ile podział zmniejsza nieczystość (Gini, entropia) lub wariancję, i wybiera największy spadek. Powtarza to w każdej gałęzi osobno — zachłannie, bez patrzenia kilka kroków w przód.
- Czy drzewo decyzyjne wymaga standaryzacji danych?
- Nie. Pytanie „x ≤ próg” daje ten sam podział po dowolnym rosnącym przekształceniu cechy, więc skala, logarytm czy standaryzacja nic nie zmieniają. To jedna z głównych wygód drzew i boostingu w porównaniu z sieciami i regresją liniową.
- Dlaczego pojedyncze drzewo się przeucza, a las czy boosting mniej?
- Drzewo rosnące do czystych liści zapamiętuje każdy przykład i jest niestabilne. Las uśrednia setki drzew na różnych próbkach, co wygładza przypadkowe cięcia; boosting używa płytkich drzew i małego kroku, więc każde drzewo wnosi niewiele.
Źródła
- Breiman, L., Friedman, J., Olshen, R., Stone, C. (1984). Classification and Regression Trees. Wadsworth.
- Quinlan, J. R. (1986). "Induction of decision trees". Machine Learning 1(1), 81–106.
- Hastie, T., Tibshirani, R., Friedman, J. (2009). The Elements of Statistical Learning, 2nd ed., Springer, rozdz. 9.2 "Tree-based methods".
- James, G., Witten, D., Hastie, T., Tibshirani, R. (2021). An Introduction to Statistical Learning, 2nd ed., Springer, rozdz. 8 "Tree-based methods".
- Chen, T., Guestrin, C. (2016). "XGBoost: a scalable tree boosting system". KDD. arXiv:1603.02754