1. Czym jest drzewo klasyfikacyjne?
2. Budowa drzewa - korzeń, węzły, liście
3. Istota działania - jak drzewo podejmuje decyzje
4. Etapy budowy drzewa - krok po kroku
5. Przykładowe dane: kredytobiorcy “dobry” i “zły”
6. Budowa drzewa w R - praktyka
7. Ocena jakości klasyfikacji - wzory i obliczenia
8. Przeuczenie i optymalne przycinanie drzewa
9. Koszty błędów klasyfikacji
10. Wady i zalety metody
11. Podsumowanie

Drzewo klasyfikacyjne to nieparametryczna metoda uczenia nadzorowanego, która pozwala na przypisanie obserwacji do jednej z wcześniej zdefiniowanych klas na podstawie wartości cech (zmiennych objaśniających).

Drzewo ma strukturę hierarchiczną - przypomina odwrócone drzewo, w którym:

• korzeń znajduje się na górze,
• liście znajdują się na dole,
• a decyzje podejmowane są przez kolejne podziały zbioru danych.

Cel: zbudować model, który dla nowego obiektu (np. wniosku kredytowego) wskaże klasę - w naszym przypadku: dobry lub zły kredytobiorca.

• Korzeń (root) - punkt startowy, zawiera cały zbiór uczący.
• Węzeł wewnętrzny (internal node) - reguła podziału na podzbiory.
• Gałąź (branch) - wynik testu (np. “Dochód < 5000”).
• Liść (leaf, terminal node) - końcowy węzeł zawierający decyzję klasyfikacyjną.

Wszystkie wierzchołki niebędące liśćmi nazywamy wierzchołkami niefinalnymi.

Drzewo dzieli przestrzeń cech na rozłączne, prostokątne obszary. Każdej takiej “kostce” przypisuje jedną klasę - tę, która dominuje w obszarze.

Klasyfikacja nowej obserwacji polega na przejściu ścieżką od korzenia do liścia:

1. Sprawdzamy regułę w korzeniu (np. Dochód < 5500?).
2. Idziemy w lewo lub w prawo zależnie od odpowiedzi.
3. Powtarzamy proces w kolejnych węzłach.
4. Po dotarciu do liścia odczytujemy przewidywaną klasę.

Kluczowe pytanie podczas budowy: Jak wybrać cechę i punkt podziału, aby grupy w węzłach potomnych były możliwie “czyste” (jednorodne)?

Aby ocenić jakość rozdzielenia obserwacji w węźle, używamy miar nieczystości (impurity):

• Indeks Giniego: \[G(t) = 1 - \sum_{k=1}^{K} p_k^2\]

• Entropia: \[H(t) = -\sum_{k=1}^{K} p_k \log_2(p_k)\]

• Błąd klasyfikacji: \[E(t) = 1 - \max_k(p_k)\]

gdzie \(p_k\) to udział obserwacji klasy \(k\) w węźle \(t\).

Wybieramy ten podział, który maksymalnie zmniejsza nieczystość (największy spadek Giniego/entropii).

1. Start w korzeniu - cały zbiór uczący traktujemy jako jedną grupę.
2. Wybór najlepszego podziału - dla każdej cechy szukamy progu, który najlepiej rozdziela klasy (minimalizuje Giniego/entropię).
3. Podział węzła - dane dzielimy na dwa (lub więcej) podzbiorów - powstają węzły potomne.
4. Rekurencja - punkty 2-3 powtarzamy w każdym nowym węźle.
5. Stop - przerywamy, gdy:
   • węzeł jest “czysty” (jedna klasa),
   • osiągnęliśmy maksymalną głębokość,
   • liczba obserwacji w węźle jest zbyt mała,
   • dalszy podział nie poprawia istotnie jakości.
6. Przycinanie (pruning) - usuwamy fragmenty drzewa, które zbyt szczegółowo dopasowują się do danych (zapobieganie overfittingowi).
7. Walidacja - oceniamy jakość na zbiorze testowym.

Wygenerowaliśmy fikcyjny zbiór 400 klientów banku z dwiema klasami:

• Dobry kredytobiorca (240 obs.) - terminowo spłaca zobowiązania.
• Zły kredytobiorca (160 obs.) - występują opóźnienia/zaległości.

Zmienne objaśniające:

• Wiek - wiek klienta (w latach),
• Dochod - miesięczny dochód netto (zł),
• Staz_pracy - staż pracy (lata),
• Zadluzenie - łączne zadłużenie (zł),
• Liczba_kredytow - liczba aktywnych kredytów,
• Status_mieszk - status mieszkaniowy (Własne / Wynajem / Rodzice).

library(rpart)
library(rpart.plot)

# Dopasowanie drzewa klasyfikacyjnego
model <- rpart(
  Klasa ~ Wiek + Dochod + Staz_pracy + Zadluzenie +
          Liczba_kredytow + Status_mieszk,
  data    = train,
  method  = "class",
  parms   = list(split = "gini"),
  control = rpart.control(cp = 0.01, minsplit = 20, maxdepth = 5)
)

Parametry funkcji rpart():

• method = "class" - klasyfikacja (nie regresja).
• split = "gini" - kryterium podziału (alternatywa: "information").
• cp - parametr złożoności (kontrola przycinania).
• minsplit - minimalna liczba obserwacji potrzebna do podziału.
• maxdepth - maksymalna głębokość drzewa.

W każdym węźle widzimy: przewidywaną klasę, prawdopodobieństwa klas oraz procent obserwacji w węźle.

• Reguła 1: JEŚLI Zadluzenie< 3144 ORAZ Dochod>=5435 => klasa: Dobry
• Reguła 2: JEŚLI Zadluzenie< 3144 ORAZ Dochod< 5435 ORAZ Staz_pracy>=9.5 => klasa: Dobry
• Reguła 3: JEŚLI Zadluzenie< 3144 ORAZ Dochod< 5435 ORAZ Staz_pracy< 9.5 => klasa: Zly
• Reguła 4: JEŚLI Zadluzenie>=3144 => klasa: Zly

Każdy liść drzewa odpowiada jednej regule decyzyjnej - to ogromna zaleta interpretacyjna tej metody.

• TP (true positive) - poprawnie wskazani źli klienci,
• TN (true negative) - poprawnie wskazani dobrzy klienci,
• FP / FN - błędy klasyfikacji.

Oznaczenia: TP - poprawnie “Zły”, TN - poprawnie “Dobry”, FP - błędnie “Zły”, FN - błędnie “Dobry”.

\[ \text{Accuracy} = \frac{TP + TN}{TP + TN + FP + FN} \qquad \text{Error Rate} = \frac{FP + FN}{TP + TN + FP + FN} \]

\[ \text{Sensitivity (Recall)} = \frac{TP}{TP + FN} \qquad \text{Specificity} = \frac{TN}{TN + FP} \]

\[ \text{Precision} = \frac{TP}{TP + FP} \qquad F_1 = \frac{2 \cdot \text{Precision} \cdot \text{Recall}}{\text{Precision} + \text{Recall}} \]

\[ \kappa = \frac{p_o - p_e}{1 - p_e}, \quad p_o = \text{Accuracy}, \quad p_e = \sum_{k} \frac{n_{k\cdot} \cdot n_{\cdot k}}{N^2} \]

Z naszej macierzy pomyłek (zbiór testowy, N = 120): TP = 43, TN = 68, FP = 7, FN = 2.

\[\text{Accuracy} = \frac{43 + 68}{120} = \frac{111}{120} \approx 0.925\]\[\text{Error Rate} = \frac{7 + 2}{120} \approx 0.075\]\[\text{Sensitivity} = \frac{43}{43 + 2} = \frac{43}{45} \approx 0.956\]\[\text{Specificity} = \frac{68}{68 + 7} = \frac{68}{75} \approx 0.907\]

\[\text{Precision} = \frac{43}{43 + 7} = \frac{43}{50} \approx 0.860\]\[F_1 = \frac{2 \cdot 0.860 \cdot 0.956}{0.860 + 0.956} \approx 0.905\]\[p_e = \frac{70 \cdot 75 + 50 \cdot 45}{120^2} \approx 0.521\]\[\kappa = \frac{0.925 - 0.521}{1 - 0.521} \approx 0.843\]

Interpretacja: Accuracy = 0.925 oznacza, że model poprawnie klasyfikuje 92.5% klientów testowych. Czułość = 0.956 mówi, jaki odsetek rzeczywiście złych klientów został wykryty.

AUC (Area Under Curve) bliskie 1 oznacza model bliski idealnemu, AUC = 0,5 to klasyfikator losowy.

Przeuczenie występuje, gdy drzewo zbyt dokładnie dopasowuje się do danych uczących - “zapamiętuje” je razem z szumem, zamiast uczyć się ogólnych wzorców.

Objawy przeuczenia:

• bardzo niski błąd na zbiorze uczącym, wysoki błąd na zbiorze testowym,
• ogromna liczba liści (czasem po jednej obserwacji na liść),
• bardzo głębokie drzewo z regułami opartymi na pojedynczych przypadkach,
• niestabilność - drobna zmiana danych daje zupełnie inne drzewo.

Drzewo niedouczone (underfitting) to drugi biegun - zbyt płytkie, ignoruje istotne zależności.

Cel: znaleźć drzewo o optymalnej złożoności - takie, które minimalizuje błąd na niezależnym zbiorze (test / kros-walidacja).

Drzewo duże: błąd uczący = 0.000, błąd testowy = 0.050    → różnica = 0.050
Drzewo umiarkowane: błąd uczący = 0.043, błąd testowy = 0.075    → różnica = 0.032

Duża luka pomiędzy błędem uczącym i testowym to sygnał ostrzegawczy o przeuczeniu.

Najpopularniejszy algorytm to przycinanie z karą za złożoność (Breiman, 1984). Dla każdego poddrzewa \(T\) definiujemy:

\[ R_\alpha(T) = R(T) + \alpha \cdot |\tilde{T}| \]

gdzie:

• \(R(T)\) - błąd resubstytucji (np. udział błędów na zbiorze uczącym),
• \(|\tilde{T}|\) - liczba liści drzewa,
• \(\alpha \geq 0\) - parametr kary (w rpart parametr cp).

Dla \(\alpha = 0\) wybieramy drzewo maksymalne; dla \(\alpha \to \infty\) - sam korzeń. Algorytm generuje ciąg zagnieżdżonych poddrzew odpowiadających rosnącym wartościom \(\alpha\).

Optymalne \(\alpha\) wybieramy minimalizując błąd walidacji krzyżowej xerror.

Wykres pokazuje błąd walidacji krzyżowej (xerror) w funkcji cp. Linia przerywana to próg 1-SE (jedno odchylenie standardowe od minimum) - zwykle wybieramy najmniejsze drzewo, którego błąd mieści się pod tą linią (reguła 1-SE Breimana - daje modele prostsze i bardziej stabilne).

# 1) Reguła "minimum xerror"
opt_cp_min <- model$cptable[which.min(model$cptable[, "xerror"]), "CP"]

# 2) Reguła 1-SE (zalecana)
min_row   <- which.min(model$cptable[, "xerror"])
xerr_min  <- model$cptable[min_row, "xerror"]
xstd_min  <- model$cptable[min_row, "xstd"]
prog_1se  <- xerr_min + xstd_min
opt_cp_1se <- model$cptable[
  min(which(model$cptable[, "xerror"] <= prog_1se)), "CP"
]

model_przyciety <- prune(model, cp = opt_cp_1se)

cp_min = 0.01, cp_1se = 0.01.

Drzewo przycięte: błąd uczący = 0.043, błąd testowy = 0.075.

Przycięte drzewo jest prostsze, łatwiej je zinterpretować, a jego błąd testowy jest zwykle lepszy lub porównywalny z drzewem pełnym - bo nie modeluje już szumu.

Złożoność drzewa kontrolujemy parametrami rpart.control():

• cp - minimalna poprawa nieczystości potrzebna, by zaakceptować podział,
• minsplit - minimalna liczba obserwacji w węźle, aby próbować podziału,
• minbucket - minimalna liczba obserwacji w liściu,
• maxdepth - maksymalna głębokość drzewa,
• xval - liczba podzbiorów w walidacji krzyżowej (domyślnie 10).

Dwie strategie zapobiegania przeuczeniu:

1. Pre-pruning (zatrzymanie wcześniej) - ustawiamy ostrzejsze cp, minsplit, maxdepth.
2. Post-pruning (przycinanie po fakcie) - hodujemy duże drzewo, potem prune().

W praktyce stosuje się kombinację obu.

W zadaniu kredytowym typy błędów mają różny ciężar finansowy:

• FN (uznaliśmy złego klienta za dobrego) - bank traci niespłaconą część kredytu, np. 10 000 zł.
• FP (uznaliśmy dobrego klienta za złego) - bank traci jedynie marżę z odrzuconej umowy, np. 1 000 zł.

Standardowe drzewo zakłada, że oba błędy “kosztują” tyle samo. W rzeczywistości FN może być 5-20 razy droższy niż FP. Trzeba to uwzględnić w modelu.

Macierz kosztów \(C\):

\[ C = \begin{pmatrix} 0 & C_{FP} \\ C_{FN} & 0 \end{pmatrix} \qquad \text{Całkowity koszt} = C_{FP} \cdot FP + C_{FN} \cdot FN \]

# Założenie: FN kosztuje 5x więcej niż FP
# Wiersze = klasa rzeczywista, kolumny = klasa przewidziana
# Kolejność etykiet: c("Dobry", "Zly")
macierz_kosztow <- matrix(c(0, 1,     # rzeczywisty Dobry -> przew. Dobry/Zły
                            5, 0),    # rzeczywisty Zły   -> przew. Dobry/Zły
                          nrow = 2, byrow = TRUE,
                          dimnames = list(c("Dobry","Zly"),
                                          c("Dobry","Zly")))

model_koszt <- rpart(
  Klasa ~ Wiek + Dochod + Staz_pracy + Zadluzenie +
          Liczba_kredytow + Status_mieszk,
  data    = train,
  method  = "class",
  parms   = list(loss = macierz_kosztow),
  control = rpart.control(cp = 0.01, minsplit = 20, maxdepth = 5)
)

loss przekazujemy w parms. Drzewo zacznie agresywniej klasyfikować klientów jako “Zły”, bo FN jest 5× droższy.

Model z kosztami zwykle ma wyższy FP, ale znacznie niższy FN - i niższy łączny koszt.

1. Macierz kosztów (loss) w rpart - bezpośrednio modyfikuje kryterium podziału.
2. Ważenie obserwacji (weights) - przypisujemy większe wagi klasie mniejszościowej / kosztowniejszej.
3. Przesunięcie progu klasyfikacji - zamiast 0,5 używamy progu \(p^*\) minimalizującego oczekiwany koszt:

\[ p^* = \frac{C_{FP}}{C_{FP} + C_{FN}} \]

Dla naszych założeń (\(C_{FP}=1000\), \(C_{FN}=10000\)): \(p^* = \frac{1000}{11000} \approx 0{,}091\).

1. Resampling - SMOTE / oversampling klasy mniejszościowej.
2. Cost-sensitive ensembles - wagi w lasach losowych / boostingu.

• Wysoka interpretowalność - łatwo wyjaśnić każdą decyzję (“white-box”).
• Brak założeń o rozkładach zmiennych, brak konieczności standaryzacji.
• Obsługa zmiennych mieszanych - liczbowe i kategoryczne jednocześnie.
• Odporność na braki danych (split surogatowy).
• Wykrywanie interakcji między zmiennymi.
• Szybkość predykcji - prosta sekwencja porównań.
• Stanowią bazę dla potężnych metod zespołowych (Random Forest, Boosting).

• Niestabilność - małe zmiany danych mogą skutkować zupełnie innym drzewem.
• Skłonność do przeuczenia - bez przycinania drzewa rosną nadmiernie.
• Słabsza dokładność niż modele zespołowe (np. lasy losowe).
• Podziały prostokątne - trudność w modelowaniu zależności liniowych.
• Faworyzowanie zmiennych o większej liczbie poziomów.
• Trudność modelowania skomplikowanych granic decyzyjnych za pomocą jednego drzewa.

• Drzewo klasyfikacyjne to interpretowalny model uczenia maszynowego, oparty na rekurencyjnym podziale przestrzeni cech.
• Struktura: korzeń → węzły wewnętrzne → liście.
• Najpopularniejsze kryteria podziału: indeks Giniego i entropia.
• Kluczowe etapy: rozrastanie drzewa, przycinanie, walidacja.
• Przeuczenie kontrolujemy parametrami cp, minsplit, maxdepth oraz post-pruningiem (reguła 1-SE).
• Optymalne \(\alpha\) minimalizuje \(R_\alpha(T) = R(T) + \alpha|\tilde{T}|\).
• Ocenę jakości prowadzimy za pomocą: macierzy pomyłek, Accuracy/Error Rate, czułości, swoistości, F1, Kappa, AUC - ze wzorami podstawionymi do liczbowych wartości.
• W praktyce uwzględniamy koszty błędów (loss, wagi, próg klasyfikacji) - zwłaszcza w bankowości i medycynie.

“Drzewo klasyfikacyjne tłumaczy decyzję językiem reguł - jest jak rozmowa z modelem.”

Kontakt: mbukowski1977@gmail.com

Pełny kod źródłowy w pliku drzewo_klasyfikacyjne.Rmd.

Aby wygenerować prezentację:

# Zainstaluj wymagane pakiety (jeśli nie masz):
install.packages(c("rpart", "rpart.plot", "dplyr", "ggplot2",
                   "knitr", "kableExtra", "caret", "pROC",
                   "gridExtra", "rmarkdown"))

# Renderowanie prezentacji:
rmarkdown::render("drzewo_klasyfikacyjne.Rmd")