Ogólnie

 

Drzewo decyzyjne – graficzna metoda wspomagania procesu decyzyjnego, stosowana w teorii decyzji. Algorytm drzew decyzyjnych jest również stosowany w uczeniu maszynowym do pozyskiwania wiedzy na podstawie przykładów.

W teorii decyzji drzewo decyzyjne jest drzewem decyzji i ich możliwych konsekwencji (stanów natury). Zadaniem drzew decyzyjnych może być zarówno stworzenie planu, jak i rozwiązanie problemu decyzyjnego.

Metoda drzew decyzyjnych jest szczególnie przydatna w problemach decyzyjnych z licznymi, rozgałęziającymi się wariantami oraz w przypadku podejmowania decyzji w warunkach ryzyka.

Przykładowy problem decyzyjny

 

Student Leszek obudził się 25 minut przed egzaminem. Profesor był formalistą i nawet minuta spóźnienia wykluczała możliwość pisania egzaminu, Leszkowi groziła więc sesja poprawkowa. Sprawa była jednak znacznie bardziej skomplikowana, gdyż Leszek miał zamiar wyjechać do pracy do Stanów Zjednoczonych, zaś wcześniejszy powrót we wrześniu oznaczałby dla niego utratę 4000 zł zarobków. Jeżeli jednak zdążyłby dotrzeć na czas, to rodzice w nagrodę za dobre oceny kupiliby mu prezent (zazwyczaj wartości 500 zł).

Leszek musiał więc starannie przemyśleć, w jaki sposób dotrzeć do szkoły. Autobus nie wchodził w grę, jazda nim zajmowała co najmniej 40 minut. Pozostawała jeszcze inna możliwość – pożyczyć samochód ojca. Samochód ten jednak był w kiepskim stanie i szanse na dojechanie do szkoły wynosiły 90%, zaś w przypadku awarii Leszek musiałby pokryć część kosztów naprawy, gdyż ojciec od dawna winił go za za zły stan samochodu (3 tys. zł). Oprócz tego musiał zdecydować, czy opłaca się jechać przez miasto szybko, czy wolno. Przy wolnej jeździe dotarłby na czas z prawdopodobieństwem 60%, natomiast przy szybkiej zdążyłby na pewno (Leszek potrafił naprawdę szybko jeździć). Mógł jednak zostać zatrzymany przez patrol policji, co groziło mandatem w wysokości 500 zł (prawdopodobieństwa trafienia na patrol – 20%).

Druga możliwość to wynajęcie taksówki, za którą trzeba będzie zapłacić 30 zł. Jednak taksówkę trzeba będzie znaleźć w ciągu kilku minut, co można wykonać z prawdopodobieństwem sukcesu 80% (jeżeli nie będzie taksówki w pobliżu, Leszek już nie zdąży). Aby ponaglić kierowcę, Leszek może wręczyć napiwek w wysokości 20 zł, co zwiększy szanse na dotarcie na czas do 85% (w przeciwnym wypadku tylko 70%).

Jaką decyzję powinien podjąć Leszek?

Konstruowanie drzewa decyzyjnyego

 

Drzewo składa się z węzłów (decyzji i stanów natury) i gałęzi (możliwych wariantów). Tradycyjnie decyzje oznaczamy prostokątami, natomiast stany natury kołami.

Konstrukcję drzewa rozpoczynamy od korzenia. Na początku Leszek ma do wyboru: samochód lub taksówka. Rozpatrzmy węzeł samochód. Mamy do czynienia z dwoma stanami natury: samochód zepsuje się lub dojedzie. Sytuacja, w której samochód zepsuje się, jest jednocześnie węzłem końcowym, gdyż Leszek nie ma już żadnego wyboru: W ten sposób kontynuujemy konstrukcję całego drzewa.

W prawidłowo skonstruowanym drzewie węzły decyzyjne i stanów natury powinny występować na przemian, zaś każda ścieżka powinna być zakończona węzłem końcowym.

Rozwiązywanie problemu decyzyjnego

 

Rozwiązywanie problemu przy pomocy drzewa decyzyjnego rozpoczynamy od węzłów końcowych tego drzewa, przypisując im końcowe wypłaty. Przykładowo, dla sekwencji: taksówka → znajdzie → napiwek → zdąży, końcowa wypłata wynosi 4000 zł (zarobek w Stanach) + 500 zł (prezent) − 30 zł (koszt taksówki) − 20 zł (napiwek) = 4450 zł.

Następnym krokiem jest zaznaczenie przy gałęziach wychodzących ze stanów natury odpowiadających im prawdopodobieństw. Na przykład dla węzła nr 6 prawdopodobieństwa wynoszą: policja – 0,2, uda się – 0,8.

Kolejny krok to wyznaczenie dla każdego węzła – stanu natury wartości oczekiwanej. Np. dla węzła nr 6 wartość oczekiwana wyniesie: 0,2 * (−500) zł + 0,8 * 4500 zł = 3500 zł. Przy każdym węźle decyzyjnym zapisujemy największą wartość z wyznaczonych wartości oczekiwanych (odpowiada to najkorzystniejszej decyzji). Teraz podczas cofania się po drzewie do korzenia wypełniamy kolejno wszystkie węzły: Optymalna ścieżka decyzji jest wyznaczona przez największe wartości oczekiwane.

W podanym przykładzie z obliczeń wynika, że Leszek powinien poszukać taksówki i dać taksówkarzowi napiwek.

Problemy przy budowie drzewa

 

Konstrukcje drzewa na podstawie zbioru przykładów, najprościej przedstawić w postaci algorytmu rekurencyjnego uruchamianego dla każdego węzła w drzewie: Pierwszym krokiem algorytmu jest podjecie decyzji, czy rozpatrywany węzeł analizując dostępny zestaw atrybutów i klas-decyzji powinien stać się albo

  1. Etykietą opisującą klasę-decyzję (liść końcowy drzewa) wg kryterium stopu, taka decyzja spowoduje utworzenie węzła i zakończenie się tego wywołania algorytmu, albo:
  2. Węzłem-rozgałęzieniem co spowoduje wybór atrybutu z puli dostępnych atrybutów według kryterium wyboru atrybutu i następnie na podstawie wartości jakich przyjmuje wybrany argument z zestawu przykładów tworzone są kolejne węzły drzewa - uruchamiany jest rekurencyjnie ten algorytm, jednak dla każdego „rozgałęzienia” podawany jest zestaw atrybutów zmniejszony o aktualnie wybrany atrybut, jak również zestaw przykładów jest zmniejszany o te przykłady, które nie posiadają odpowiedniej wartości wybranego atrybutu dla każdego rozgałęzienia.
W ten sposób są skonstruowane w praktyce wszystkie algorytmy tworzenia drzew decyzyjnych. Jedyne różnice w ich implementacjach polegają na odpowiedniej konstrukcji kryterium stopu i kryterium wyboru atrybutu. Odpowiednia technika wyboru argumentu ma kluczowy wpływ na wygląd drzewa decyzyjnego, gdyż właśnie od kolejności wyboru atrybutów zależy w głównej mierze głębokość i stopień rozbudowy drzewa.

Czasami ze względów czysto technicznych odchodzi się od realizacji algorytmów rekurencyjnych szczególnie, gdy operujemy na dużej ilości przykładów i atrybutów - wtedy każde wywołanie procedury pociąga za sobą duże ilości danych magazynowanych na stosie programowym. Dlatego w takich przypadkach korzysta się z tak zwanego „jawnego stosu” bądź też z wykorzystuje się metodę konstruowania drzewa strategią „wszerz” jednak działanie samego algorytmu jest w praktyce identyczne.