Drzewo decyzyjne to 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.

Drzewa decyzyjne w teorii decyzji

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.

Konstruowanie drzewa decyzyjnego

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

Przykładowy problem decyzyjny

"Zakład Produkcyjny produkujący piłki plażowe ma ostatnio dużo reklamacji, miesięcznie na sumę 50000 zł. Właściciel zakładu rozpatruje dwa warianty poprawienia tej sytuacji. Pierwszy wariant to zmiana technologii produkcji piłek zakup know - how to suma 30.000 zł. Można też jakość poprawić powołując dział kontroli jakości, koszt jego to 10000 zł miesięcznie lub motywując pracowników bezpośrednio związanych z produkcją premią jej koszt to 18000 zł. Jaką decyzję powinien podjąć właściciel

Budowanie drzewa

Drzewo składa się z węzłów (decyzji i stanów natury) i gałęzi (możliwych waiantów). Tradycyjnie decyzje oznaczamy prostokątami, natomiast stany natury kołami.
Konstrukcję drzewa rozpoczynamy od korzenia. Na początku właściciel zakładu ma do wyboru: zakup know - how lub zmiany wewnątrz zakładu
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:
Drzewo_decyzyjne -

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.20, uda się - 0.80.
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.20 * (-500) zł + 0.80 * 4500 zł = 3500 zł. Przy każdym wężle decyzyjnym zapisujemy największą wartość z wyznaczonych wartości oczekiwanych (odpowiada to najkorzystniejszej decyzji). Teraz cofając się po drzewie do korzenia, wypełniamy kolejno wszystkie węzły:
Drzewo_decyzyjne -

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

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ólna prezentacja 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 były na podstaiwe atrybutów były podejmowane decyzje klasyfikujace (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łeziają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.
Publikacja wraz ze zdjęciami jest udostępniona w Encyklopedii "Zgapedia" części portalu zgapa.pl. Treść objęta jest licencją GNU FDL Wolnej Dokumentacji w wersji 1.3 lub dowolnej pózniejszej opublikowanej przez Free Software Foundation i została ona opracowana na podstawie Wikipedii, tutaj możesz znaleźć artykuł źródłowy oraz autorów. Warunki użytkowania Encyklopedii znajdziesz na tej stronie.