Czym jest i jak działa drzewo decyzyjne?

miroslawmamczur.pl 7 miesięcy temu

– Tato, a Ty ciągle przy tym komputerze. Może wyjdziemy całą rodzinką na spacer? Jagódka wyjrzała za okno – albo jednak nie. Nie pada, ale jest zimno. Zostańmy w domu i pograjmy w gry planszowe!

– Jupi!! Gry planszowe! – krzyknęła z euforią Otylka.

– Dajcie mi 5 minutek. Dokończę tylko tworzyć drzewo decyzyjne – odpowiedziałem.

– Drzewo? Przecież nie masz żadnego drzewa na ekranie tatusiu.

– Hmm… Drzewo decyzyjne to taki jakby plan, który pomaga nam podjąć decyzję. Sama przed chwilką takie drzewo stworzyłaś – uśmiechnąłem się.

– Naprawdę? – spojrzała Jagoda z niedowierzaniem w stronę Otylki.

– Tak! Chciałaś iść na spacer. Na początku spojrzałaś za okno i sprawdzałaś czy pada, czy nie. Następnie podążyłaś za odpowiednimi gałęziami, analizując kolejne elementy, takie jak temperatura. I otrzymałaś odpowiedź, czy iść na spacer.

– Czyli drzewo decyzyjne to taki plan, który pomaga nam podejmować dobre decyzje!

– Dokładnie tak, Jagódko! To narzędzie, które pomaga nam zrozumieć, jakie czynniki wpływają na nasze decyzje i jakie konsekwencje mogą wyniknąć z naszych wyborów.

Drzewo decyzyjne to potężne narzędzie w dziedzinie sztucznej inteligencji i uczenia maszynowego, które znajduje zastosowanie w różnych obszarach, od klasyfikacji danych po rozwiązywanie problemów decyzyjnych. Zapraszam Was do fascynującej podróży przez świat drzew decyzyjnych, jednych z najprostszych, ale mimo swojej prostoty bardzo przydatnych narzędzi, jakie mamy w arsenale uczenia maszynowego.

Czym jest drzewo decyzyjne?

Prostymi słowami drzewo decyzyjne to taki rodzaj planu lub mapy, która pomaga w podejmowaniu prostych decyzji na podstawie różnych opcji i warunków.

Inaczej mówiąc, drzewo decyzyjne to graficzna struktura, w której każdy węzeł reprezentuje decyzję, a każda gałąź reprezentuje możliwy rezultat tej decyzji.

Powyżej zwizualizowałem drzewo decyzyjne, które zostało zbudowane w głowie Jagódki na podstawie jej dotychczasowych spacerów i jej subiektywnego doświadczenia. Aby było nam prościej omawiać drzewo decyzyjne w kontekście uczenia maszynowego, wykorzystajmy inny przykład – bardziej biznesowy.

Nasz przykład

Niech naszym zadaniem będzie klasyfikacja klientów banku, czy dana osoba spłaci kredyt, czy będzie miała problemy z oddaniem pieniędzy z odsetkami.

Każdą osobę w naszym zbiorze będziemy traktować jako osobną obserwację. Osoby w naszym zbiorze będą opisane różnymi cechami. Naszym celem jest oddzielenie osób, które spłacą kredyt od tych, które będą miały z tym problem, zadając pytania na podstawie posiadanych danych.

Powiedzmy, iż mamy 100 osób z czego 50 spłaciło kredyt, a 50 nie. Mamy również informacje:

a) czy kiedykolwiek w ciągu ostatnich 3 lat miała problemy ze spłatą (Tak/Nie),

b) o średnich systematycznych zarobkach w ciągu ostatniego pół roku (np. 3000, 5000, itp).

Wówczas nasze drzewo mogłoby wyglądać tak:

Drzewo decyzyjne – terminologia

Na początku warto omówić pewną terminologię używaną w drzewach decyzyjnych:

węzeł główny (ang. node root) – to pierwszy węzeł drzewa. Ten węzeł zawiera wszystkie dane wejściowe i od niego wychodzi pierwsze pytanie, które dzieli (ang. split) nasz zbór na podzbiory.
podział (ang. splitting) – podział danych na dwa (najczęściej w algorytmach zaimplementowano drzewa binarne, ale mogą sie zdarzyć podziały na więcej niż dwa podzbiory) podzbiory na podstawie pytania. Na przykład bierzemy cechę “czy osoba miała kiedyś problemy ze spłatą kredytu”. jeżeli TAK to w prawo, pozostali w lewo.
przycinanie (ang. pruning) – warto o tym wspomnieć, ponieważ jest to odwrotny proces do podziału. Polega na redukcji zbędnych węzłów w drzewie, dzięki czemu model staje się mniejszy i mniej podatny na przeuczenie się (ang. overfitting).
węzeł decyzyjny (ang. decision node) – jest to węzeł powstały w wyniku podziału węzła nadrzędnego. Węzły te reprezentują pośrednie decyzje w drzewie.
rodzic i dzieci (ang. parent and children) – w drzewie decyzyjnym węzeł podzielony na podwęzły nazywany jest rodzicem, a wychodzące z niego węzły podrzędne nazywane są dziećmi. Rodzic reprezentuje decyzję lub warunek, podczas gdy dzieci reprezentują potencjalne wyniki lub dalsze decyzje oparte na tym warunku.
węzeł liściowy (ang. leaf node) – jest to ostatni węzeł (tzw. liść bez dzieci). Węzły liściowe nazywane są również węzłami końcowymi.
gałąź lub poddrzewo (ang. subtree) – jest to podsekcja całego drzewa decyzyjnego. Reprezentuje określoną ścieżkę decyzji i wyników w drzewie.

Zatem godnie z powyższą terminologią nasze drzewo wygląda tak:

Algorytm tworzenia drzew decyzyjnych

Celem drzewa decyzyjnego jest segregacja obiektów według klas (u nas: spłaci / nie spłaci), a idealnym drzewem decyzyjnym (czyli modelem predykcji w tym przypadku) byłoby takie, które tworzy ostateczne liście zawierające w sobie tylko jedną klasę.

No dobrze, ale na jakiej podstawie drzewo decyzyjne wie, jaką cechę wziąć i jak poukładać dane właśnie w drzewo decyzyjne?

To zależy od algorytmu wybranego do procesu tworzenia drzewa decyzyjnego. Najbardziej popularnymi algorytmami są:

ID3 (Iterative Dichotomiser 3) – jest to jeden z najstarszych algorytmów do budowy drzew decyzyjnych, opracowany przez Rossa Quinlana w 1986 roku. ID3 działa na zasadzie iteracyjnego podziału zbioru danych na podzbiory, wybierając atrybuty, które najlepiej separują dane na podstawie pewnej miary nieczystości, np. entropii.
C4.5 – jest to ulepszona wersja algorytmu ID3, również opracowana przez Rossa Quinlana. C4.5 wprowadza kilka usprawnień w stosunku do ID3, takich jak obsługa brakujących danych, obsługa atrybutów numerycznych oraz generowanie reguł decyzyjnych.
CART (Classification and Regression Trees) – algorytm CART został zaproponowany przez Leo Breimana w 1984 roku. Jest bardziej programistyczną implementacją. Polega na budowaniu drzewa binarnego (każdy węzeł może mieć maksymalnie dwoje dzieci) i działa na zasadzie podziału zbioru danych na podzbiory minimalizując miarę nieczystości współczynnika Giniego. Ten współczynnik jest fajną alternatywą dla entropii, bo jest prostszy do wyliczeń z perspektywy komputerów.
CHAID (Chi-squared Automatic Interaction Detection) – algorytm CHAID, opracowany przez Gordona Kassena, jest używany przede wszystkim w analizie statystycznej. Działa na zasadzie podziału zbioru danych na podzbiory, wykorzystując test chi-kwadrat do określenia istotności związku między atrybutami a zmienną docelową.

Warto podkreślić, iż implementacja CART jest najczęściej używana w algorytmach, np. w biblitece sklearn czy xgboost.

Jak algorytm CART znajduje najlepszy podział?

Tak naprawdę w CART możemy zastosować kilka metod w celu znalezienia najlepszych podziałów dla naszych danych. Natomiast najbardziej znanymi są nieczystość Giniego oraz entropia. Obie metody służą do oceny jakości podziału zbioru danych. Natomiast są między nimi nieznaczne różnice.

Nieczystość Giniego (ang. Gini impurity)

Rozważmy sytuację analityka kredytowego, który ma za zadanie podzielić 100 osób na dwie grupy: tych, którzy spłacą kredyt i tych, którzy mogą mieć z tym problem. Jego celem jest taki podział, aby ostatecznie grupa osób stojących koło siebie (powiedzmy w jednym pokoju) zawierała tylko osoby, które spłacą kredyt lub nie. Dzięki temu jedną grupę zaprosimy do banku, a drugiej niestety podziękujemy.

Podczas segregowania osób na dwie grupy, analityk stara się minimalizować mieszanie ich w każdej grupie. Nieczystość Giniego w tym przypadku mierzy, jak często, losując dwie osoby z różnych grup, otrzymamy różne wyniki. jeżeli w jednej grupie są głównie osoby, które spłacą kredyt, a w drugiej głównie osoby, które mogą mieć z tym problem, to nieczystość Giniego będzie niska, ponieważ szanse na wybranie osoby, która spłaci kredyt z jednej grupy i osoby, która nie spłaci z drugiej grupy, będą duże (bliskie 1). A ostatecznie 1-coś bliskiego jeden daje wartość bliską zeru.

Jednak jeżeli grupy są mieszane, czyli w jednej grupie znajdują się zarówno osoby, które nie spłacą kredytu i jak i te, które go spłacą, to nieczystość Giniego będzie wysoka (1 minus małe prawdopodobieństwo). To oznacza, iż szanse na wybranie osoby, która spłaci kredyt lub tych, którzy tego nie zrobią z danej grupy, będą podobne.

Przykład liczenia nieczystości Giniego

Przyjrzyjmy się naszemu przykładowi po lewej stronie węzła. Dla liczb, które tam widzimy, możemy wyliczyć, że:

Teraz wyliczmy ostatnie liście na lewej gałęzi naszego drzewa.

I to tutaj dzieje się magia jak podamy zmienną kategoryczną lub ciągłą do modelowania, ponieważ algorytm sam szuka optymalnego podziału danej zmiennej. Czyli nasze pytanie “systematyczne wpływy ≥3k+?” będzie porównywał z wpływami > 5k+, 10k+ itd.

A jak porównujemy i szukamy najlepszego podziału naszej zmiennej (lub zmiennych, jeżeli mamy ich więcej)? Robimy to poprzez obliczenie nieczystości Giniego dla każdej z tych części i sumujemy je, uwzględniając proporcję elementów w każdej z nich. Następnie wybieramy podział, który minimalizuje tę sumę, co oznacza, iż najlepiej segreguje dane według klasy.

Czyli u nas wygląda to tak:

A co by było, gdyby przyjąć inną wartość zarobków, np. 5.000?

Dla podziału według zarobków > 5.000 suma ważona jest większa niż dla podziału 3.000, dlatego przyjmujemy tamten podział.

Uwaga. Warto pamiętać, iż jeżeli nieczystość Giniego dla dwóch węzłów podrzędnych nie jest niższa niż nieczystość Giniego dla węzła nadrzędnego, to algorytm przestanie szukać podziałów.

I już – proste, prawda?

Entropia (ang. entropy)

Wróćmy jeszcze do analityka, który ma za zadanie podzielić klientów. Posegregowaliśmy klientów na dwie grupy i zaczynamy się zastanawiać, jak bardzo są one pomieszane.

Jeśli w jednej z grup po podziale jest mniej więcej tyle samo osób, które spłacą kredyt jak i nie spłacą i chcielibyśmy losowo wybrać jedną osobę z tej grupy, to jeżeli są one równomiernie rozłożone, to entropia będzie wysoka. Dlaczego? Bo nie jesteśmy pewni, jaką osobę znajdziemy (tę, która spłaci czy też nie spłaci).

Natomiast jeżeli w grupie większość osób spłaci kredyt, a tylko kilka rodzynków będzie miało problemy, to entropia będzie niższa, ponieważ jesteśmy bardziej pewni, iż wybierając losowo, trafimy na osobę, która spłaci kredyt.

Entropia mierzy więc, jak bardzo dane są pomieszane lub nieuporządkowane. W przypadku drzew decyzyjnych, algorytm stara się znaleźć podział danych, który minimalizuje entropię, co oznacza, iż grupy danych są bardziej jednorodne w kontekście przynależności do danej klasy (np. spłaci czy nie spłaci).

Przykład liczenia entropii

Aby zidentyfikować najlepszy podział, musimy wykonać troszkę bardziej skomplikowane wyliczenia.

Nieczystość Giniego vs entropia

Nieczystość Giniego i entropia służą do tego samego, czyli oceny jakości podziału danych w drzewach decyzyjnych, ale wykorzystują nieco inne podejścia do tego samego problemu. Nieczystość Giniego skupia się na minimalizacji błędów klasyfikacji, podczas gdy entropia mierzy stopień nieporządku w danych.

Z doświadczenia powiem wam, iż dają bardzo zbliżone wyniki. Natomiast ja preferuje Giniego ze względu na prostszy sposób wyliczenia dla komputerów – przy dużej liczbie danych do przeliczenia czas to pieniądz.

Zalety drzew decyzyjnych

Oto pięć najważniejszych według mnie zalet drzew decyzyjnych:

Łatwość interpretacji – drzewa decyzyjne generują proste reguły decyzyjne, które są łatwe do zrozumienia i interpretacji, choćby dla osób bez specjalistycznej wiedzy z zakresu analizy danych. Bardzo prosto możemy je zwizualizować i to jest moim zdaniem największa ich zaleta.
Czas liczenia – w porównaniu do innych algorytmów uczenia maszynowego, takich jak uczenie ze wzmocnieniem czy sieci neuronowe, drzewa decyzyjne wymagają niewielkiego nakładu obliczeniowego podczas trenowania i klasyfikacji.
Odporność na obserwacje odstające – drzewa decyzyjne są stosunkowo odporne na obserwacje odstające, co oznacza, iż pojedyncze nietypowe punkty danych nie wpływają znacząco na ich wydajność.
Wymaga niewielkiego przygotowania danych – drzewa decyzyjne radzą sobie ze zmiennymi ciągłymi, co eliminuje potrzebę tworzenia zmiennych fikcyjnych lub normalizacji danych.
Odporność na współliniowość – drzewa decyzyjne są odporne na współliniowość, co oznacza, iż mogą efektywnie radzić sobie z danymi, w których pewne cechy są powiązane.

Warto też pamiętać, iż drzewa decyzyjne mogą być stosowane zarówno do problemów klasyfikacji (np. identyfikacja transakcji fraudowej) jak i regresji (np. prognozowanie cen nieruchomości).

Te zalety sprawiają, iż drzewa decyzyjne są popularnym narzędziem w analizie danych i uczeniu maszynowym, szczególnie w sytuacjach, gdzie łatwość interpretacji i szybkość trenowania są istotne.

Wady drzew decyzyjnych

Mimo licznych zalet, drzewa decyzyjne mają także pewne wady, o których warto wspomnieć.

Zbyt prosty model – ponieważ jest to prosty algorytm, a większość problemów, z którymi się stykamy, nie jest tak oczywista, to nie jest w stanie uchwycić wystarczającej złożoności danych. Dlatego bardzo często algorytmy uczenia ze wzmocnieniem czy lasy losowe dają lepsze wyniki, ponieważ potrafią uchwycić większą złożoność danych poprzez agregację wielu słabych klasyfikatorów.
Wrażliwość na zmiany danych – drzewa decyzyjne są bardzo wrażliwe na choćby niewielkie zmiany w danych uczących, co może prowadzić do znaczących zmian w strukturze drzewa i ostatecznych przewidywaniach. To może powodować brak stabilności modelu, a przecież nie chcemy takiej niepewności na porodukcji.
Skłonność do przetrenowania – drzewa decyzyjne mogą łatwo dopasować się do szumu w danych treningowych, co może prowadzić do przetrenowania modelu. Przetrenowanie może powodować zbyt duże dopasowanie do danych treningowych i słabą zdolność generalizacji do nowych danych. Na szczęście znamy metody, aby sobie z tym radzić!

Przykład w python

Uwaga! Poniższy kod ma na celu tylko po krótce pokazać, jak prosto można zbudować drzewo decyzyjne w python. Nie przygotowuję żadnego wyboru zmiennej, optymalizacji parametów itp. itd.

Wczytajmy sobie potrzebne pakiety:

from sklearn.datasets import make_classification from sklearn.model_selection import train_test_split from sklearn.tree import DecisionTreeClassifier from sklearn.metrics import roc_auc_score import matplotlib.pyplot as plt

Pójdźmy na łatwizę i wygenerujmy sobie sami zbiór danych.

# Create a balanced random dataset X, y = make_classification(n_samples=1000, n_features=10, n_classes=2, weights=[0.5, 0.5], random_state=2024)

Funkcja make_classification generuje zestaw danych zawierający macierz cech (X) oraz wektor z etykietami klas (y), które są wykorzystywane do trenowania i testowania modeli klasyfikacji.

Teraz przygotujmy podział zbioru:

# Division into training and test set X_train, X_test, y_train, y_test = train_test_split( X, y, test_size=0.2, random_state=2024)

Budowa modelu

Teraz musimy uważać. W sklearn drzewo decyzyjne ma domyślnie ustawiony parametr głębokości drzewa na None. Oznacza to, iż drzewo będzie tak długo się tworzyć, aż domyśly algorytm na nieczystość Giniego nie znajdzie kolejnego podziału. Dlatego może dojść do przetrenowania lub zbytniego skomplikowania drzewa.

# default model model = DecisionTreeClassifier(random_state=2024) model.get_params()

Zobaczmy jaki model zbuduje się na domyślnych parametrach:

# training model model.fit(X_train, y_train) # calculating AUC on test data y_pred_proba = model.predict_proba(X_test)[:, 1] auc = round(roc_auc_score(y_test, y_pred_proba),3) print(f"max_depth={model.tree_.max_depth}; AUC: {auc}")

Widzimy, iż zbudowane zostało drzewo decyzyjne aż do głębokości 8. Zatem mielibyśmy maksymalnie 2^8 możliwości, co daje 256 różnych ścieżek! Całkiem sporo możliwości.

Dlatego sprawdźmy jakie metryki AUC byśmy dostali w zależności od głębokości drzewa:

def decision_tree_calc(max_depth=None): model = DecisionTreeClassifier(random_state=2024, max_depth=max_depth) model.fit(X_train, y_train) y_pred_proba = model.predict_proba(X_test)[:, 1] auc = round(roc_auc_score(y_test, y_pred_proba),3) print(f"max_depth={model.tree_.max_depth}; AUC: {auc}") return auc, model depth_dict = {} for max_depth in range(1, 11): auc, model = decision_tree_calc(max_depth=max_depth) depth_dict[max_depth] = auc

Zróbmy jeszcze obrazek, aby łatwiej uzasadnić naszą decyzję biznesowi, iż sugerowalibyśmy głębokość drzewa równą dwa.

# Extract keys and values from the dictionary keys = list(depth_dict.keys()) values = list(depth_dict.values()) # Create bar chart plt.figure(figsize=(10, 5)) # Define color for each bar, set crimson for the highest value bar colors = ['gray' if v != max(values) else 'crimson' for v in values] bars = plt.bar(keys, values, color=colors) # Add values on top of each bar for bar, value in zip(bars, values): plt.text(bar.get_x() + bar.get_width() / 2, bar.get_height() + 0.005, f'{value:.3f}', ha='center', va='bottom') # Add title and labels plt.title('Values of AUC based on decision tree depth') plt.xlabel('Max depth') plt.ylabel('AUC on test') # Set x-axis ticks to show all values plt.xticks(keys) # Show plot plt.show()

Drzewo decyzyjne – wizualizacja

Tak jak wspominałem wcześniej, największą dla mnie zaletą drzew decyzyjnych jest ich interpretowalność. Sprawdźmy zatem, jak takie drzewo wygląda. Dzięki temu osoby decyzyjne lub eksperci domenowi będą mogli sami zweryfikować, czy podziały w drzewie mają sens.

Aby to zrobić, należy najpierw zainstalować graphviz. Program możecie pobrać tutaj: https://graphviz.org/download/. Następnie możemy go wykorzystać w naszym kodzie:

from sklearn.tree import export_graphviz import graphviz print(f"graphviz: {graphviz.__version__}")

Napiszmy jeszcze funkcję do zapisywania grafów drzew:

def decision_tree_graph(model, file_to_save_name): # Export decision tree to DOT format dot_data = export_graphviz(model, out_file=None, filled=True, rounded=True, special_characters=True) # Visualize decision tree graph = graphviz.Source(dot_data) # Save tree as PNG file graph.render('./img/' + file_to_save_name, format='png') # Open tree in default PDF viewer graph.view()

I teraz zwizualizujmy drzewo o głębokości 2:

max_depth = 2 auc, model = decision_tree_calc(max_depth=max_depth) decision_tree_graph(model, f'graph_max_depth_{str(max_depth)}')

oraz o głębokości 4:

max_depth = 4 auc, model = decision_tree_calc(max_depth=max_depth) decision_tree_graph(model, f'graph_max_depth_{str(max_depth)}')

Poniżej możecie zobaczyć, jak to fajnie wizualizuje na podstawie bardzo znanego zbioru iris:

from sklearn.datasets import load_iris # Load iris dataset iris = load_iris() X, y = iris.data, iris.target # Train decision tree classifier iris_model = DecisionTreeClassifier(max_depth=3) iris_model.fit(X, y) # graph visualization decision_tree_graph(iris_model, f'iris_dataset_max_depth_3')

Darmowa sztuczka z drzewami decyzyjnymi

Zbudowaliście super model, ale szefowie chcieliby lepiej zrozumieć jak działa? Wówczas możecie zbudować drzewo decyzyjne, gdzie jako zmienną celu (ang. target) weźmiecie prawdopodobieństwo z waszego modelu (np. <0.2 to 0, a ≥0.2 to 1). Następnie wykorzystajcie proste techniki wizualizacji takiego drzewa, aby pokazać jakie zmienne do niego weszły i aby prośniej wyjaśnić osobom z biznesu, na czym model się opiera.

Podsumowanie

Mam nadzieję, iż teraz drzewa decyzyjne nie mają przed Wami tajemnic. Jak mogliście się przekonać, drzewa decyzyjne to proste, ale i bardzo przydatne narzędzie w arsenale algorytmów uczenia maszynowego. Mam nadzieję, iż czasami po nie sięgniecie – szczególnie w przypadku modeli, gdzie kluczową rolę odgrywa wyjaśnialność decyzji!

Pozdrawiam z całego serca,