Drzewo decyzyjne

Drzewo decyzyjne
Polecane artykuły
Model ekonometryczny Diagram procesu Diagram relacji Analiza czynnikowa GERT Algorytm genetyczny Typizacja Metody taksonomiczne Analiza danych

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, czy też klasyfikacyjnych, jak niektórzy je nazywają, 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ę.

TL;DR

Drzewo decyzyjne to graficzny sposób wspierania procesu decyzyjnego, stosowany w teorii decyzji. Drzewa decyzyjne mają wiele zastosowań, zwłaszcza w przypadku problemów decyzyjnych z wieloma wariantami i warunkami ryzyka. Budowa drzewa decyzyjnego opiera się na korzeniu, węzłach, krawędziach i liściach. Drzewa decyzyjne charakteryzują się strukturą hierarchiczną i pozwalają na klasyfikację nowych obiektów. Istnieją różne algorytmy służące do budowania drzew decyzyjnych, takie jak CART i C4.5. Drzewa decyzyjne są coraz częściej wykorzystywane w ekonomii i innych dziedzinach do wspomagania procesu podejmowania decyzji.

Budowa

Rys. 1. Przykład drzewa decyzyjnego

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:

1. Zbadanie, czy zbiór obiektów jest jednorodny. Jeśli jest, algorytm kończy pracę. Jeśli nie, to wykonywana jest dalsza część algorytmu.
2. 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.
3. Podział zbioru w najlepszy sposób ze względu na przyjęte kryterium.
4. Użycie powyższego algorytmu do wszystkich podzbiorów.
5. Kategoryzacja drzewa, czyli likwidacja fragmentów drzewa o małym znaczenie dla jakości rezultatów klasyfikacji.
6. Zastosowanie drzewa do klasyfikacji nowych obiektów.

Algorytmy służące do budowania drzewa decyzyjnego

Obecnie idea funkcjonowania drzew decyzyjnych za pomocą algorytmów oraz informacji dotyczących określonych przypadków wykorzystywana jest przy komputerowym procesie podejmowania decyzji.

• Jednym z najpopularniejszych algorytmów jest algorytm CART, czyli Classification and Regression Tree. Jego autorami są Breiman, Friedman, Olshen oraz Stone, którzy wykorzystali w procesie decyzyjnym zastosowanie dwóch kryteriów podziału zebranych cech. Pierwszym z nich jest podział na dwie równe grupy. Kolejnym jest kryterium podziału Giniego, czyli mierze koncentracji zmiennej losowej (J. Kozak, P. Juszczuk, 2016, s. 52-56)
• Algorytm C4.5 został po raz pierwszy zaproponowany przez Quinlana w 1996r. Udoskonalony został w nim między innymi sposób klasyfikacji większej grupy danych. W konsekwencji otrzymywany wynik zawiera mniejszą ilość błędów. Jest to możliwe dzięki wykorzystaniu reguły względnego zysku. Algorytm ten jest w stanie dokonać odpowiedniego podziału nawet w przypadku występowania ciągłego rozkładu wartości cech oraz niepełnych informacji, dzięki wyznaczaniu najprawdopodobniejszych ich wartości. Dodatkowo w algorytmie C4.5 wprowadzono zasadę przycinania, czyli przeciwdziałania nadmiernego wzrostu drzewa (M. Bogunia, 2008, s. 11-12)

Patrz także: Analiza FMEA

Bibliografia

• Bujak Ł. (2008). Drzewa decyzyjne, Uniwersytet Mikołaja Kopernika, Toruń
• Gatnar E. (1998). Symboliczne metody klasyfikacji danych, PWN, Warszawa
• Kozak J., Juszczuk P. (2016), Algorytmy do konstruowania drzew decyzyjnych w przewidywaniu skuteczności kampanii telemarketingowej banku, Studia Informatica Pomerania, nr 1
• Krętowski M., Bobrowski L. (2002). Generowanie wielowymiarowych drzew decyzyjnych na podstawie zbiorów danych, "Zeszyty naukowe politechniki białostockiej", nr 1
• Lula P. (2007). Metody sztucznej inteligencji i ich zastosowania w ekonomii i zarządzaniu, Akademia Ekonomiczna, Kraków
• Magee, J. F. (1964). Decision trees for decision making. Harvard Business Review
• Przywara D. (2007). Drzewa decyzyjne, metody budowania, zastosowania, Wrocław
• Quinlan, J. R. (1990). Decision trees and decision-making. Systems, Man and Cybernetics, IEEE Transactions on, 20(2)
• Rokach, L., & Maimon, O. (2014). Data mining with decision trees: theory and applications, World Scientific Publishing

Autor: Wojciech Korona, Monika Czwakiel