5. Drzewa decyzyjne

1. Wprowadzenie

W sytuacji, gdy analiza dużych zasobów danych stała się koniecznością, dużą popularność zdobywa technika drzew decyzyjnych (zwanych również drzewami klasyfikacyjnymi). Pozwala ona na:

• badanie zbioru obiektów opisywanych przez przyjęty zestaw cech (atrybutów), przy czym celem analizy jest dokonanie podziału obiektów na jednorodne klasy. Sposób dokonywania podziału ma charakter hierarchiczny, punktem wyjścia jest zbiór zawierający wszystkie analizowane obiekty. W trakcie analizy jest on dzielony na pewną liczbę podzbiorów. W kolejnych krokach każdy z podzbiorów polega dalszemu podziałowi. W ostatnim etapie analizy każdy obiekt stanowi oddzielną klasę;

• Określenie reguł decyzyjnych opisujących zasady przypisywania obiektów do wyróżnionych klas. Reguły odwołują się do wartości atrybutów opisujących obiekty.

Za przykład drzewa decyzyjnego może służyć schemat przedstawiony na poniższym rysunku. Prezentuje on drzewo powstałe w wyniku analizy danych dotyczących osób ubiegających się o kredyt bankowy. Sformułowane reguły decyzyjne pozwalają na podjęcie decyzji odnośnie udzielenia kredytu bądź odrzucenia wniosku klienta.

K - wysokość kredytu

Rys.36 Przykład drzewa klasyfikacyjnego.

Drzewo klasyfikacyjne składa się z korzenia, węzłów, krawędzi oraz liści, czyli węzłów, z których nie wychodzą już żadne krawędzie. Liście reprezentują klasy na jakie drzewo klasyfikacyjne dzieli obiekty. Z każdym liściem można związać regułę decyzyjną, którą stanowi koniunkcja warunków znajdujących się na ścieżce od korzenia do liścia drzewa. Reguły decyzyjne prowadzące do takiej samej klasy (liści) można traktować jako składniki alternatywy. Przykładowo, drzewo zaprezentowane na rys. 36 generuje dwie reguły klasyfikacji. Pierwsza z nich przyjmuje postać:

Jeżeli

wnioskodawca posiada rachunek ROR w banku oraz suma jego wpływów na konto z ostatnich 3 miesięcy była większa bądź równa kwocie kredytu

lub

wnioskodawca posiada rachunek ROR w banku oraz suma jego wpływów na konto z ostatnich 3 miesięcy była mniejsza niż kwota kredytu i wnioskodawca posiada co najmniej 2 poręczycieli

lub

wnioskodawca nie posiada rachunku ROR i dysponuje co najmniej 3 poręczycielami

to

wniosek należy przyjąć

Natomiast drugą regułę można sformułować w następujący sposób:

Jeżeli

wnioskodawca posiada rachunek ROR oraz suma wpływów z ostatnich trzech miesięcy jest mniejsza od kwoty kredytu oraz wnioskodawca ma mniej niż 2 poręczycieli

lub

wnioskodawca nie posiada rachunku ROR i liczba jego poręczycieli jest mniejsza od 3

to

wniosek należy odrzucić

Drzewo decyzyjne zbudowane w oparciu o dane empiryczne, można wykorzystać do klasyfikacji nowych obiektów, które nie brały udziału w procesie tworzenia drzewa. Przykładowo, wniosek kredytowy osoby posiadającej rachunek ROR w banku o kredyt w wysokości 10 000zł, bez poręczycieli, zostałby odrzucony, jeżeli suma wpływów na rachunek ROR tej osoby w ostatnich trzech miesiącach wynosiła 6000zł. Przy sumie wpływów wynoszącej 11000zl, innych warunkach niezmienionych, wniosek zostałby przyjęty.

Drzewa decyzyjne mają strukturę hierarchiczną. W kolejnych krokach dokonuje się podziału zbioru obiektów odpowiadając na pytania o wartości wybranych cech lub ich kombinacji liniowych. Ostateczna decyzja (klasyfikacja obiektu) zależy od odpowiedzi na wszystkie pytania. W algorytmach konstrukcji drzew klasyfikacyjnych istotnym elementem jest wybór kolejności cech według których, na poszczególnych etapach, będzie dokonywany podział zbioru obiektów.

Cechy (zmienne) wykorzystywane do podziału zbioru obiektów nazywane są często zmiennymi predykcyjnymi, natomiast klasy (liście) reprezentujące wartości tzw. zmiennej zależnej.

Przykładowo, dla drzewa klasyfikacyjnego z rys.1 dokonywano podziału obiektów kolejno, według wartości następujących cech (zmiennych predykcyjnych):

• posiadacz_rachunku_ROR,

• suma_wpływów_z_ostatnich_3_miesięcy,

• liczba_poręczycieli.

Zmienną zależną może być natomiast zmienna przyjąć_wniosek mogąca przyjmować wartości ze zbioru {TAK, NIE}.

Ze względu na ilość krawędzi wychodzących z każdego węzła, drzewa klasyfikacyjne można podzielić na:

• binarne - z każdego węzła wychodzą dwie krawędzie,

• niebinarne (wielokierunkowe) - drzewa posiadające węzły, z których wychodzą więcej niż 2 krawędzie.

Drzewa binarne wykorzystuje się głównie do klasyfikacji obiektów o cechach ilościowych (np. rys. 36), natomiast drzewa niebinarne mają zastosowanie do klasyfikacji obiektów o cechach jakościowych.

Drzewa klasyfikacyjne można również podzielić ze względu na liczbę cech uwzględnianych w trakcie podziałów obiektów. Z tego punktu widzenia wyróżnia się:

• drzewa jednowymiarowe - gdy podział obiektów w węzłach dokonywany jest na podstawie wartości jednej cechy. Jeżeli i-ta cecha ta ma charakter ilościowy, to testowany warunek można zapisać w postaci c_i < C, gdzie c_i jest wartością i-tej cechy obiektu, a C jest pewną stałą (np. rys. 36),

• drzewa wielowymiarowe - gdy podział obiektów w węzłach dokonywany jest przy uwzględnieniu wartości więcej niż jednej zmiennej. Gdy rozpatrywane zmienne przyjmują wartości numeryczne, to można stwierdzić, że podział dokonywany w węźle przeprowadzany jest na podstawie kombinacji liniowej wartości cech, tzn. testowany jest warunek postaci:
  , gdzie n jest równe liczbie cech obiektu, c_i jest wartością i-tej cechy obiektu zaś a_i dla i = 0,..., n są pewnymi stałymi.

Opracowano szereg algorytmów tworzenia drzew klasyfikacyjnych, takie jak na przykład CLS, CART, ID3, CHAIP. Na wejściu tych algorytmów pojawia się zbiór uczący (zbiór obiektów opisanych przez zbiór cech i zaklasyfikowanych do znanych klas), a na wyjściu drzewo klasyfikacyjne reprezentujące reguły decyzyjne. Ogólną zasadę konstrukcji drzew klasyfikacyjnych można ująć w następujących punktach [Gatnar, 1998]:

1. Sprawdzenie, czy zbiór obiektów jest jednorodny. Jeśli tak, to algorytm kończy pracę. Jeśli nie, to realizowana jest dalsza część algorytmu.

2. Rozważanie wszystkich możliwych podziałów zbioru obiektów na podzbiory (ze względu na cechy obiektów wybrane w pewien ustalony sposób) i 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 wybrany sposób (najlepszy ze względu na przyjęte kryterium).

4. Zastosowanie powyższego algorytmu do każdego z podzbiorów.

5. Uporządkowanie drzewa - usuniecie tych fragmentów drzewa, które mają niewielkie znaczenie dla jakości rezultatów klasyfikacji

6. Wykorzystanie drzewa do klasyfikacji nowych obiektów.

Do pomiaru jakości podziału zbioru obiektów w węzłach drzewa wykorzystuje się szereg miar, takich jak np. entropia, wskaźnik zróżnicowania Giniego, lecz ich omówienie wykracza poza zakres niniejszego opracowania. Osoby zainteresowane mogą znaleźć stosowne definicje np. w [Gatnar, 1998] lub w [Witten i in., 2000].

Podsumowując rozważania dotyczące drzew klasyfikacyjnych można stwierdzić, że stanowią one uzupełnienie metod klasycznych, takich jak np. analiza dyskryminacyjna. Cechą, która wyróżnia je spośród innych metod jest hierarchiczność podejmowania decyzji. Jako ich niewątpliwą zaletę należy wymienić możliwość graficznego przedstawiania danych oraz łatwość interpretacji. Drzewa klasyfikacyjne znalazły zastosowanie między innymi w takich dziedzinach jak medycyna (diagnostyka), botanika (klasyfikacja) oraz ekonomia (wspomaganie procesu podejmowania decyzji).

1. Zastosowanie drzew decyzyjnych

Przedstawienie zasad klasyfikacji obiektów w postaci drzewa ma szereg zalet. Pierwszą zaletą jest łatwość interpretacji wykrytych reguł i możliwość ich przedstawienia w czytelnej postaci graficznej. Po drugie, utworzone drzewo można w prosty sposób przekształcić w szereg reguł decyzyjnych, opisujących sposób podziału (i mogących znaleźć swoje zastosowanie w systemach wspomagających procesy decyzyjne). Drzewo może być również z powodzeniem wykorzystane do predykcji przynależności nowych, nieznanych w trakcie jego tworzenia, obiektów. Drzewo decyzyjne (klasyfikacyjne) pozwala również na dogłębną analizę informacji wykorzystywanych w procesie klasyfikacji. Te wszystkie czynniki sprawiają, że drzewa decyzyjne są przydatnym narzędziem analizy danych ekonomicznych.

Sposób wykorzystania drzew decyzyjnych do klasyfikacji obiektów zostanie zaprezentowany na przykładzie klasyfikacji wniosków kredytowych. Obliczenia zrealizowano z wykorzystaniem modułu Drzewa klasyfikacyjne programu Statistica w.5.5.

W tabeli 1 znajdują się dane dotyczące 60 wniosków kredytowych (obiektów). Zadanie polega na zidentyfikowaniu reguł przydzielania kredytu.

Każdy wniosek charakteryzowany jest poprzez 3 zmienne predykcyjne:

• DOCHODY - średnia (np. z ostatnich 6 miesięcy) miesięczna wysokość dochodów na 1 członka rodziny wnioskodawcy,

• PORECZ - liczba poręczycieli,

• PRZEZNACZ - planowany cel wydatkowania pieniędzy pochodzących z kredytu. Zmienna ta przyjmuje 2 wartości: sprzęt (np. zakup telewizora, lodówki) oraz wakacje (przeznaczenie kredytu na pokrycie kosztów wyjazdu wakacyjnego).

oraz 1 zmienną zależną:

• KREDYT - przyjmującą wartość tak, w przypadku udzielenia kredytu oraz wartość nie gdy kredytu nie udzielono.

Dla potrzeb obliczeniowych programu STATISTICA zmienne DOCHODY oraz PORECZ są uznane za zmienne porządkowe, natomiast zmienna PRZEZNACZ jest zmienną nominalną.

lp.	DOCHODY	PORECZ	PRZEZNAC	KREDYT		lp.	DOCHODY	PORECZ	PRZEZNAC	KREDYT
1	140	1	sprzęt	nie		31	500	1	sprzęt	nie
2	140	1	wakacje	nie		32	500	1	wakacje	nie
3	180	2	sprzęt	nie		33	500	2	sprzęt	tak
4	220	2	wakacje	nie		34	500	2	sprzęt	tak
5	220	3	sprzęt	nie		35	500	2	sprzęt	tak
6	280	2	wakacje	nie		36	500	2	wakacje	nie
7	350	1	sprzęt	nie		37	520	2	sprzęt	tak
8	350	1	sprzęt	nie		38	520	2	sprzęt	tak
9	360	1	sprzęt	nie		39	530	2	sprzęt	tak
10	360	1	wakacje	nie		40	550	2	wakacje	nie
11	360	2	sprzęt	nie		41	590	2	wakacje	nie
12	360	2	wakacje	nie		42	599	2	wakacje	nie
13	400	2	sprzęt	tak		43	600	2	sprzęt	tak
14	400	2	wakacje	nie		44	600	2	wakacje	tak
15	410	2	sprzęt	tak		45	600	2	wakacje	tak
16	410	2	sprzęt	tak		46	600	2	wakacje	tak
17	410	2	sprzęt	tak		47	610	1	wakacje	nie
18	410	2	wakacje	nie		48	610	2	wakacje	tak
19	420	0	sprzęt	nie		49	620	2	wakacje	tak
20	420	1	sprzęt	nie		50	630	0	sprzęt	nie
21	420	1	wakacje	nie		51	630	0	wakacje	nie
22	420	2	sprzęt	tak		52	650	1	sprzęt	nie
23	440	2	sprzęt	tak		53	650	2	wakacje	tak
24	440	2	wakacje	nie		54	680	2	wakacje	tak
25	450	1	sprzęt	nie		55	700	1	wakacje	nie
26	450	1	wakacje	nie		56	700	2	sprzęt	tak
27	450	2	sprzęt	tak		57	700	2	wakacje	tak
28	480	2	sprzęt	tak		58	700	2	wakacje	tak
29	500	0	wakacje	nie		59	720	0	wakacje	nie
30	500	1	sprzęt	nie		60	850	2	wakacje	tak

Tabela 1 Dane wykorzystane do ilustracji metody tworzenia drzew klasyfikacyjnych.

Po zastosowaniu metody CART wyczerpującego poszukiwania podziałów otrzymano drzewo klasyfikacyjne takie jak na rys. 37. Klasyfikuje ono poprawnie wszystkie wnioski.

Rys. 37 Drzewo klasyfikacyjne uzyskane dla danych z tabeli 1.

Drzewo klasyfikacyjne obejmuje 4 podziały (4 węzły decyzyjne) i 5 węzłów końcowych (liści). Histogramy wewnątrz prostokątów symbolizujących węzły pokazują ilość wniosków zaklasyfikowanych na danym etapie jako przyjęte lub nieprzyjęte. Cyfra w lewym górnym rogu węzła oznacza numer węzła, natomiast liczby na gałęziach oznaczają liczbę wniosków przypisanych do węzła do którego prowadzi gałąź.

W pierwszej fazie tworzenia drzewa wszystkie wnioski przypisane są do węzła pierwszego (korzenia drzewa) i tymczasowo są zaklasyfikowane jako nie przyjęte (napis w prawym górnym roku korzenia) ponieważ w danych generalnie więcej jest takich właśnie wniosków. Następnie wnioski klasyfikowane są według kryterium: czy liczba poręczycieli jest mniejsza bądź równa 1.5, co w praktyce oznacza, że liczba poręczycieli jest mniejsza bądź równa 1. Wnioski spełniające to kryterium są przypisywane do węzła 2 i odrzucane (takich wniosków jest 21), pozostałe wnioski przypisywane są do węzła 3, w którym następuje ich podział według wysokości dochodu na członka rodziny. Jeżeli te dochody są mniejsze bądź równe 380, to wnioski klasyfikowane są jako odrzucone (węzeł 4), w przeciwnym wypadku przechodzą do węzła piątego. Następuje kolejna klasyfikacja tych wniosków według planowanego przeznaczenia pieniędzy pochodzących z kredytu. W przypadku planowanego przeznaczenia pieniędzy z kredytu na zakup sprzętu wnioski są przyjmowane, natomiast, jeżeli planowanym przeznaczeniem jest pokrycie wydatków wakacyjnych to wnioski są przyjmowane tylko wtedy gdy średnia dochodu na członka rodziny jest większa od 599.5.

Rys. 38 ilustruje ważność zmiennych predykcyjnych, w skali od 0 do 100, przy określaniu wartości zmiennej decyzyjnej. Jak można zaobserwować, największe znaczenie na określanie wartości zmiennej decyzyjnej miała zmienna DOCHODY, potem PORECZ, a najmniejsze zmienna PRZEZNACZ.

Rys. 38 Ważność zmiennych predykcyjnych.

Skonstruowane drzewo klasyfikacyjne stanowi kwintesencję stosowanych (jawnie bądź niejawnie) reguł, można więc je wykorzystać do klasyfikacji nowych wniosków na przyjęte lub odrzucone. Przykładowo, osobie legitymującej się dochodami na członka rodziny wynoszącymi 650zł, dysponującej dwoma poręczycielami kredyt zostanie przyznany bez względu na planowane przeznaczenie środków pochodzących z kredytu.

Przykład powstał jedynie w celu ilustracji metodologii postępowania przy tworzeniu drzew klasyfikacyjnych. Dane w tabeli 1 są fikcyjne.

141

czy wnioskodawca posiada rachunek ROR w banku?

suma wpływów z ostatnich 3 miesięcy

liczba poręczycieli

liczba poręczycieli

przyjąć wniosek

przyjąć wniosek

odrzucić wniosek

przyjąć wniosek

odrzucić wniosek

TAK

NIE

>=K

<K

>=2

<2

>=3

<3

korzeń

węzły

liście

krawędzie

---