Drzewo decyzyjne Przekierowano ze strony: Dendrogram ang. tree diagram

Drzewo decyzyjne to nic innego jak graficzny sposób wspierania procesu decyzyjnego. Drzewo stosowane jest w teorii decyzji i ma sporo zastosowań. Może zarówno rozwiązać problem decyzyjny, jak i stworzyć plan. Metoda drzew decyzyjnych sprawdza się przede wszystkim, kiedy mamy problemy decyzyjne z wieloma rozgałęziającymi się wariantami oraz kiedy podejmujemy decyzję w warunkach ryzyka. Drzewa znalazły zastosowanie w takich dziedzinach jak botanika i medycyna. Coraz częściej sięga się do nich także w ekonomii, gdyż są w stanie ułatwiać i usprawniać komputerowe wspomaganie procesu podejmowania decyzji.

Technika drzew decyzyjnych pozwala na: wyznaczenie zasad decyzyjnych opisujących reguły przypisywania obiektów do wyróżnionych klas (zasady odwołują się do wartości atrybutów opisujących obiekty) analizowanie zbioru obiektów opisywanych przez przyjęty zestaw atrybutów; celem analizy jest doskonalenie podziału obiektów na jednorodne klasy; metoda dokonywania podziału ma charakter hierarchiczny. Punktem wyjścia jest zbiór zawierający wszystkie analizowane obiekty; w trakcie analizy jest dzielony na określoną liczbę podzbiorów. W kolejnych krokach każdy z podzbiorów podlega dalszemu podziałowi; na końcu analizy każdy obiekt stanowi oddzielną klasę.

Drzewem decyzyjnym jest graf-drzewo, które składa się z korzenia, węzłów, krawędzi oraz liści. Liście to węzły, z których nie wychodzą już żadne krawędzie. Korzeń drzewa tworzony jest przez wybrany atrybut, natomiast poszczególne gałęzie reprezentują wartości tego atrybutu. Dzięki drzewu decyzyjnemu, zbudowanemu na podstawie danych empirycznych, można sklasyfikować nowe obiekty, które nie brały udziału w procesie tworzenia drzewa. Drzewa decyzyjne charakteryzują się strukturą hierarchiczną. Znaczy to, że w kolejnych krokach dzieli się zbiór obiektów, poprzez odpowiedzi na pytania o wartości wybranych cech lub ich kombinacji liniowych. Ostateczna decyzja zależy od odpowiedzi na wszystkie pytania. W algorytmach konstrukcji drzew jednym z kluczowych elementów jest wybór kolejności cech, według których, na poszczególnych etapach, będzie dokonywany podział zbioru obiektów. Technika drzew decyzyjnych to uzupełnienie metod klasycznych. Przykładem może tu być analiza dyskryminacyjna. Hierarchiczność podejmowania decyzji jest cechą, która wyróżnia drzewo decyzyjne od innych metod.

Ogólną zasadę konstrukcji drzew decyzyjnych można ująć w następujących punktach:

• Zbadanie, czy zbiór obiektów jest jednorodny. Jeśli jest, algorytm kończy pracę. Jeśli nie, to wykonywana jest dalsza część algorytmu.
• Rozpatrywanie wszystkich możliwych podziałów zbioru obiektów na podzbiory oraz określenie, który z podziałów tworzy najbardziej jednorodne zbiory - ocena jednorodności/jakości podziału na podstawie pewnego, przyjętego kryterium.
• Podział zbioru w najlepszy sposób ze względu na przyjęte kryterium.
• Użycie powyższego algorytmu do wszystkich podzbiorów.
• Kategoryzacja drzewa, czyli likwidacja fragmentów drzewa o małym znaczenie dla jakości rezultatów klasyfikacji.
• Zastosowanie drzewa do klasyfikacji nowych obiektó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.

Rozpocznijmy od przykładu, który rozwiążemy przy pomocy drzewa decyzyjnego:

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?

Budowanie drzewa

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ówkę.





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.



Drzewa decyzyjne w uczeniu maszynowym służą do wyodrębniania wiedzy z zestawu przykładów (patrz Eksploracja danych). Zakładamy, że posiadamy zestaw przykładów: obiektów opisanych przy pomocy atrybutów, którym przyporządkowujemy jakąś decyzję (patrz tabela decyzyjna).

Przykład

Chcemy zautomatyzować proces przyjmowania kandydatów na praktyki w dużej firmie. Posiadamy setki przykładów z przeszłości, chcemy wydobyć z nich reguły decyzyjne. Atrybuty Wykształcenie, Języki obce, Doświadczenie i Ogólne wrażenie są kodowane skalą od 1 do 5.

Wiek	Płeć	Wykształcenie	Języki obce	Doświadczenie	Ogólne wrażenie	Przyjęty
25	m	2	4	1	4	nie
22	k	4	3	4	2	nie
21	m	4	5	5	4	tak
29	m	1	3	2	3	nie

Na podstawie tabeli decyzyjnej tworzymy drzewo, którego węzłami są poszczególne atrybuty, gałęziami wartości odpowiadające tym atrybutom, a liście tworzą poszczególne decyzje. Na podstawie przykładowych danych wygenerowano następujące drzewo:





Drzewo w takiej postaci odzwierciedla, w jaki sposób na podstawie atrybutów były podejmowane decyzje klasyfikujące (dla uproszczenia połączono niektóre gałęzie). Zaletą tej reprezentacji jest jej czytelność dla człowieka. W prosty sposób można przekształcić ją do reprezentacji regułowej.

Algorytm

Algorytm działa rekurencyjnie dla każdego węzła drzewa. Musimy podjąć decyzję, czy węzeł będzie:

1. liściem według kryterium stopu – kończymy to wywołanie rekurencyjne
2. węzłem rozgałęziającym się według kryterium wyboru atrybutu – dokonujemy wyboru atrybutu, tworzymy rozgałęzienia według wartości, jakie przyjmuje dany atrybut, i dla każdego węzła potomnego tworzymy rekurencyjne wywołanie algorytmu, z listą atrybutów zmniejszoną o właśnie wybrany atrybut.

Wszystkie algorytmy działają według podanego schematu, różnice w implementacji dotyczą kryteriów stopu i wyboru atrybutu.

Odmianą drzew decyzyjnych są diagramy decyzyjne (ang. decision diagrams). Od drzew decyzyjnych różnią się tym, że do danego węzła można dojść więcej niż jedną drogą.

Diagramy decyzyjne pozwalają zaoszczędzić pamięć w przypadku bardzo rozbudowanych drzew, w których określone poddrzewa powtarzają się w wielu miejscach. Powoduje to, że są użyteczne w dziedzinach bardziej sformalizowanych (np. w automatycznej analizie poprawności oprogramowania), jednak nie są stosowane w statystyce, gdzie na skutek losowych błędów w danych poddrzewa prawie nigdy nie są identyczne.

Przykład: Drzewo przypisujące liczbom naturalnym a i b z zakresu 1 do N sumę a+b posiada +N+N węzłów. Diagram decyzyjny dla tego samego problemu posiada tylko +N+2N węzłów.

Szczególnym, często stosowanym przypadkiem diagramów decyzyjnych są binarne diagramy decyzyjne (binary decision diagrams, BDD), w których każdy węzeł niebędący liściem ma dokładnie dwóch potomków.