Drzewo decyzyjne – metoda graficzna wspierająca podejmowanie decyzji, jak również model stosowany w uczeniu maszynowym do klasyfikacji lub regresji.

Podejmowanie decyzji z wykorzystaniem drzewa decyzyjnego odbywa się poprzez odpowiadanie na kolejne pytania. Pojedyncze pytanie musi być proste i dotyczyć jednego konkretnego atrybutu. Pytania ułożone są w strukturę hierarchiczną – wybór następnego pytania (lub końcowej decyzji) zależy od odpowiedzi udzielonej na poprzednie.

Proste drzewo decyzyjne może być w pełni zaprojektowane już przy tworzeniu programu i zaimplementowane w kodzie np. za pomocą instrukcji warunkowych. W uczeniu maszynowym drzewo jest generowane automatycznie na podstawie próbek ze zbioru uczącego.

REKLAMA

Teoria grafów

Drzewo to taki graf, który jest:

• prosty – wybraną parę wierzchołków może bezpośrednio łączyć co najwyżej jedna krawędź,
• spójny – między dowolną parą wierzchołków da się wyznaczyć ścieżkę,
• acykliczny – taka ścieżka jest dokładnie jedna.

W drzewie decyzyjnym poszczególne węzły (wierzchołki, z których wychodzą co najmniej dwie krawędzie) zawierają proste kryteria podziału, np. sprawdzanie, czy wartość danego atrybutu jest większa od pewnej wartości. Proces decyzyjny rozpoczyna się od węzła określanego jako korzeń. Następnie, w zależności od rezultatu sprawdzania danego kryterium, przechodzi się do kolejnych węzłów. Liście (wierzchołki mające tylko jednego sąsiada) oznaczają końcowe decyzje.

Uczenie maszynowe

Jeśli drzewo ma przewidywać klasę, do której przynależy dany obiekt, jest to drzewo klasyfikacyjne. Jeśli przewidywana jest wartość liczbowa, jest to drzewo regresyjne. Drzewa klasyfikacyjne i regresyjne zbiorczo określane są skrótowcem CART, od ang. Classification and Regression Tree.

Drzewo w uczeniu maszynowym tworzone jest automatycznie na podstawie próbek ze zbioru uczącego. Algorytmy tworzenia drzewa decyzyjnego mogą być różne, polegają one na dodawaniu kolejnych węzłów w taki sposób, aby zbiory próbek mieszczących się w obrębie jednego liścia były jak najbardziej jednorodne. Typowy algorytm budowy drzewa decyzyjnego można zapisać następująco:

1. Wybierz taki podział zbioru (przez podział rozumiemy atrybut i próg), żeby dwa powstałe w ten sposób podzbiory były jak najbardziej jednorodne. W przypadku drzew klasyfikacyjnych do oceny niejednorodności zbioru często wykorzystywany jest wskaźnik zanieczyszczenia Giniego, w przypadku drzew regresyjnych – odchylenie standardowe.
2. Dla każdego z otrzymanych podzbiorów:
   1. Jeśli spełniony jest warunek stopu (osiągnięta wystarczająco niska niejednorodność zbioru lub maksymalna głębokość drzewa), utwórz w tym miejscu liść. W przypadku klasyfikacji wartością tego liścia jest ta klasa, która występuje w otrzymanym zbiorze najczęściej. W przypadku regresji zwracaną wartością jest średnia elementów.
   2. W przeciwnym razie wróć do punku 1.

Aby uniknąć przeuczenia, czasami stosuje się dodatkowo mechanizm przycinania (ang. prunning) polegający na tym, żeby usunąć część gałęzi.

REKLAMA

Bibliografia

• P. Gupta, Decision Trees in Machine Learning, Towards Data Science, 2017 [Dostęp 2022-09-17].
• J. Kozak, P. Juszczuk , Algorytmy do konstruowania drzew decyzyjnych w przewidywaniu skuteczności kampanii telemarketingowej banku, Studia Informatica Pomerania, nr 39 , 2016, s. 49-59, DOI: 10.18276/si.2016.39-05.