Czym jest drzewo decyzyjne?

Drzewo decyzyjne (ang. decision tree) to algorytm uczenia maszynowego, który podejmuje decyzje za pomocą hierarchicznej sekwencji pytań dotyczących cech danych. Strukturę algorytmu można przedstawić jako drzewo, w którym:

  • Węzły wewnętrzne reprezentują testy na atrybutach (np. „czy wiek > 30?")
  • Gałęzie reprezentują wyniki testów (tak/nie lub wartości atrybutu)
  • Liście reprezentują decyzje końcowe (klasy lub wartości)

Drzewa decyzyjne łączą świat systemów ekspertowych (jawne reguły IF-THEN) ze światem uczenia maszynowego (automatyczne uczenie z danych). Każda ścieżka od korzenia do liścia odpowiada regule decyzyjnej, a całe drzewo można odczytać jako zbiór reguł — co czyni ten algorytm jednym z najbardziej interpretowalnych modeli ML.

Ładowanie wizualizacji...

Jak działa budowa drzewa decyzyjnego?

Algorytm buduje drzewo metodą dziel i rządź (divide and conquer). W każdym kroku wybiera atrybut, który najlepiej rozdziela dane na bardziej jednorodne podzbiory. Proces powtarza się rekurencyjnie, aż spełniony zostanie warunek stopu (np. wszystkie elementy w węźle należą do jednej klasy).

Krok po kroku

  1. Start: Cały zbiór treningowy trafia do korzenia drzewa.
  2. Wybór atrybutu: Algorytm ocenia wszystkie dostępne atrybuty za pomocą miary jakości podziału (Information Gain, Gini Index, etc.) i wybiera najlepszy.
  3. Podział: Dane dzielone są na podzbiory wg wartości wybranego atrybutu. Każdy podzbiór trafia do dziecka węzła.
  4. Rekurencja: Dla każdego dziecka powtarzamy kroki 2-3.
  5. Warunek stopu: Węzeł staje się liściem, gdy: wszystkie elementy mają tę samą klasę, brak dalszych atrybutów do podziału lub osiągnięto maksymalną głębokość.

Miary jakości podziału

Entropia i Information Gain (ID3, C4.5)

Entropia Shannona mierzy „nieuporządkowanie" zbioru. Dla zbioru S z klasami c₁, c₂, ..., cₖ:

H(S) = -Σ pᵢ · log₂(pᵢ)

Entropia wynosi 0, gdy zbiór jest całkowicie jednorodny (wszystkie elementy jednej klasy) i osiąga maksimum przy równomiernym rozkładzie klas.

Information Gain (zysk informacyjny) mierzy, o ile entropia zmniejszy się po podziale wg atrybutu A:

IG(S, A) = H(S) - Σ (|Sᵥ|/|S|) · H(Sᵥ)

Algorytm ID3 (Iterative Dichotomiser 3), stworzony przez Rossa Quinlana w 1986 roku, wybiera atrybut maksymalizujący Information Gain.

Gain Ratio (C4.5)

ID3 ma wadę: faworyzuje atrybuty z wieloma wartościami (np. numer PESEL — unikalny dla każdego rekordu, więc entropia po podziale = 0). C4.5 (następca ID3) koryguje to za pomocą Gain Ratio:

GR(S, A) = IG(S, A) / SplitInfo(A)

SplitInfo penalizuje atrybuty z wieloma wartościami, eliminując sztuczne zawyżanie IG.

Indeks Gini (CART)

Algorytm CART (Classification and Regression Trees) używa indeksu Gini:

Gini(S) = 1 - Σ pᵢ²

Indeks Gini mierzy prawdopodobieństwo, że losowo wybrany element zostanie błędnie sklasyfikowany, gdybyśmy przypisali mu klasę losowo (wg rozkładu klas). Wartość 0 = czysta klasa, wartość 0.5 = maksymalne wymieszanie (dwie klasy po 50%).

CART różni się od ID3/C4.5 tym, że zawsze tworzy drzewa binarne (każdy węzeł ma dokładnie dwoje dzieci), podczas gdy ID3 może tworzyć węzły z wieloma gałęziami.

Przetrenowanie i przycinanie

Problem przetrenowania

Drzewo budowane bez ograniczeń będzie rosnąć, aż każdy liść zawiera elementy jednej klasy — idealnie dopasowując się do danych treningowych. To przetrenowanie (overfitting): model zapamiętuje szum i anomalie zamiast uczyć się ogólnych wzorców.

Drzewo przetrenowane ma wiele głębokich gałęzi z małą liczbą próbek w liściach. Na danych treningowych osiąga niemal 100% trafności, ale na nowych danych — słabe wyniki.

Przycinanie wstępne (Pre-pruning)

Ograniczenia nakładane podczas budowy drzewa:

  • Maksymalna głębokość (max_depth) — zatrzymaj podział, gdy drzewo osiągnie zadaną głębokość
  • Minimalna liczba próbek w węźle (min_samples_split) — nie dziel węzła z mniej niż N próbkami
  • Minimalna liczba próbek w liściu (min_samples_leaf) — każdy liść musi zawierać co najmniej N próbek
  • Maksymalna liczba liści (max_leaf_nodes) — ogranicz całkowitą liczbę liści

Przycinanie wsteczne (Post-pruning)

Drzewo budowane jest do pełnego rozmiaru, a następnie przycinane od dołu. Algorytm porównuje trafność drzewa z i bez danego poddrzewa na zbiorze walidacyjnym. Jeśli usunięcie poddrzewa nie pogarsza (lub poprawia) wynik, poddrzewo zastępowane jest liściem.

Reduced Error Pruning — najprostsza metoda: testuj każdy węzeł wewnętrzny, zastąp liściem, sprawdź trafność na zbiorze walidacyjnym.

Cost-Complexity Pruning (Minimal Cost-Complexity Pruning) — stosowane w CART. Definiuje parametr α kontrolujący trade-off między rozmiarem drzewa a trafnością. Sekwencja drzew o rosnącym α (malejącej złożoności) generowana jest automatycznie; optymalne α wybiera walidacja krzyżowa.

Drzewa regresyjne

Drzewa decyzyjne nie ograniczają się do klasyfikacji. Drzewa regresyjne przewidują wartości ciągłe (np. cenę mieszkania). Różnice:

  • Miara podziału: zamiast entropii/Gini stosuje się wariancję lub MSE (Mean Squared Error) — podział minimalizujący wariancję w poddrzewach
  • Wartość w liściu: średnia wartości docelowej próbek w liściu (zamiast klasy większościowej)
  • Predykcja: schodkowa funkcja — drzewo dzieli przestrzeń cech na prostokąty i przypisuje każdemu stałą wartość

Zalety i wady drzew decyzyjnych

Zalety

  • Interpretowalność — drzewo można odczytać jako zbiór reguł IF-THEN, wizualizować graficznie i wyjaśnić każdą decyzję
  • Brak wymogów skalowania — drzewa nie wymagają normalizacji ani standaryzacji cech
  • Obsługa danych mieszanych — mogą przetwarzać cechy numeryczne i kategoryczne
  • Odporność na outliersy — podziały binarne są mało wrażliwe na wartości odstające
  • Niski koszt predykcji — O(log n) operacji porównania

Wady

  • Niestabilność — małe zmiany w danych mogą prowadzić do zupełnie innego drzewa
  • Skłonność do przetrenowania — bez przycinania drzewo zapamiętuje szum
  • Granice decyzyjne — drzewa tworzą prostokątne granice (równoległe do osi), co ogranicza ich zdolność do modelowania złożonych zależności
  • Nieoptymalność — algorytm zachłanny (greedy) nie gwarantuje globalnie optymalnego drzewa

Drzewa decyzyjne a metody zespołowe

Wady pojedynczego drzewa eliminują metody zespołowe (ensemble methods):

  • Random Forest — las wielu drzew budowanych na losowych podzbiorach danych i cech. Uśrednianie predykcji redukuje wariancję.
  • Gradient Boosting — sekwencja drzew, z których każde koryguje błędy poprzedniego. Redukuje błąd systematyczny.
  • AdaBoost — drzewa budowane z naciskiem na źle klasyfikowane próbki.

Metody zespołowe oferują wyższą trafność kosztem interpretowalności — las 500 drzew jest trudny do wizualizacji. Metryki oceny pomagają porównać modele.

Implementacja w scikit-learn

Biblioteka scikit-learn oferuje klasy DecisionTreeClassifier i DecisionTreeRegressor z pełnym zestawem hiperparametrów: criterion (gini/entropy/log_loss), max_depth, min_samples_split, min_samples_leaf, max_features, ccp_alpha (cost-complexity pruning).

Wizualizacja drzewa możliwa jest za pomocą sklearn.tree.plot_tree() lub eksportu do formatu Graphviz.

Praktyczne wskazówki

  1. Zawsze przycinaj — używaj max_depth lub ccp_alpha; drzewo bez ograniczeń to pewne przetrenowanie
  2. Walidacja krzyżowa — nie ufaj trafności na danych treningowych; stosuj k-fold CV
  3. Feature importance — drzewa dostarczają ranking ważności cech (proporcjonalny do redukcji miary nieczystości); wykorzystaj go do selekcji cech
  4. Rozważ ensemble — pojedyncze drzewo rzadko jest optymalnym modelem; Random Forest lub Gradient Boosting zwykle dają lepsze wyniki
  5. Interpretowalność — gdy wyjaśnialność jest priorytetem (medycyna, finanse), pojedyncze drzewo może być lepszym wyborem niż zespół

Podsumowanie

Drzewa decyzyjne to fundament wielu zaawansowanych algorytmów ML. Ich siła leży w intuicyjności — każda decyzja jest jawna i weryfikowalna. Choć pojedyncze drzewo ma ograniczenia (niestabilność, prostokątne granice), stanowi doskonały punkt wyjścia i cegiełkę dla potężnych metod zespołowych jak Random Forest i Gradient Boosting.