Metody odkrywania wiedzy: wykład 4
Indukcja drzew decyzyjnych

Paweł Cichosz

Date: 2001/2002

Wykład jest poświęcony prezentacji jednego z najbardziej popularnych podejść do uczenia się klasyfikacji, opartego na drzewach decyzyjnych. Podany będzie podstawowy algorytm budowania drzewa na podstawie przykładów i najważniejsze praktyczne aspekty jego stosowania.

Drzewo decyzyjne jako hipoteza

Przez drzewo decyzyjne rozumiemy strukturę, która ma zwykłe właściwości drzewa w znaczeniu, jaki temu słowu nadaje się w informatyce, jest więc strukturą złożoną z węzłów, z których wychodzą gałęzie prowadzące do innych węzłów lub liści, oraz z liści, z których nie wychodzą żadne gałęzie. Węzły odpowiadają testom przeprowadzanym na wartościach atrybutów przykładów, gałęzie odpowiadają możliwym wynikom tych testów, liście zaś etykietom kategorii.

Testy

Test jest w ogólnym przypadku dowolną funkcją określoną na dziedzinie $t:X\mapsto R_t$, przy czym w praktyce rozważamy testy, które są funkcyjnie zależne od atrybutów. Najczęściej przyjmuje się ograniczenie, że wynik testu może zależeć od wartości dokładnie jednego atrybutu i tylko taki przypadek będzie tu rozważany.

Zależnie od typów atrybutów mogą być używane różne rodzaje testów, z których najważniejsze omówione są poniżej (podane nazewnictwo nie jest powszechnie przyjęte) dla atrybutu $a:X\mapsto A$.

Testy tożsamościowe:

test utożsamiany jest z atrybutem, $t(x)\equiv a(x)$ (dla atrybutów nominalnych lub porządkowych).

Testy równościowe:

test sprawdzający równość dla wartości atrybutu (dla atrybutów nominalnych lub porządkowych):

$$t(x) = \begin{cases}1 & \text{jeśli $a(x)=v$,}\\ 0 & \text{jeśli $a(x)\neq v$,} \end{cases}$$ (1)

gdzie $v\in A$.

Testy przynależnościowe:

test sprawdzający przynależność do zbioru dla wartości atrybutu (dla dowolnych typów atrybutów):

$$t(x) = \begin{cases}1 & \text{jeśli $a(x)\in V$,}\\ 0 & \text{jeśli $a(x)\not\in V$,} \end{cases}$$ (2)

gdzie $V\subset A$.

Testy podziałowe:

test sprawdzający przynależność do podzbiorów powstałych przez podział przeciwdziedziny atrybutu (dla dowolnych typów atrybutów):

$$t(x) = \begin{cases}1 & \text{jeśli $a(x)\in V_0$,}\\ 2 & \text{jeśli $a(x)\in V_1$,}\\ \dots\\ m & \text{jeśli $a(x)\in V_m$,}\\ \end{cases}$$ (3)

gdzie parami rozłączne zbiory $V_1,V_2,\dots,V_m$ stanowią wyczerpujący podział przeciwdziedziny atrybutu $A$.

Testy nierównościowe:

test sprawdzający nierówność dla wartości atrybutu (dla atrybutów porządkowych i ciągłych):

$$t(x) = \begin{cases}1 & \text{jeśli $a(x)\leq\theta$,}\\ 0 & \text{jeśli $a(x)>\theta$,} \end{cases}$$ (4)

gdzie $\theta\in A$.

Dla testu $t$ i zbioru przykładów $P$ będziemy stosować oznaczenia:

$$P_{tr} = \{x\in P \;\vert\; t(x)=r\}$$

$$P^d_{tr} = \{x\in P \;\vert\; c(x)=d\land t(x)=r\}$$

Klasyfikacja za pomocą drzewa

Klasyfikacja przykładu za pomocą drzewa decyzyjnego polega na przejściu ścieżki od korzenia do liścia drzewa wzdłuż gałęzi wyznaczanych przez wyniki stosowania do tego przykładu testów związanych z odwiedzanymi kolejno węzłami. Osiągnięcie liścia wyznacza kategorię. W ten sposób drzewo decyzyjne umożliwia zaklasyfikowanie dowolnego przykładu, a więc reprezentuje hipotezę.

Algorytm zstępującej konstrukcji drzewa

Podstawowy algorytm budowania drzewa w sposób zstępujący (od korzenia powstają kolejne ,,piętra'' węzłów) można sformułować w postaci następującej procedury rekurencyjnej.

Kryterium stopu

Kryterium stopu określa, kiedy ma być zatrzymany proces rozrostu drzewa, czyli kiedy dla pewnego zbioru przykładów nie powstanie kolejny węzeł wewnętrzny, lecz liść. Oczywiste sytuacje, kiedy powinno się tak stać, są następujące:

• aktualny zbiór przykładów $P$ jest pusty,
• wszystkie przykłady ze zbioru $P$ należą do tej samej kategorii pojęcia $c$,
• zbiór możliwych do użycia testów $S$ jest pusty.

Najpóźniej po spełnieniu któregoś z tych warunków dalszy rozrost drzewa musi zostać zatrzymany. Powstałe wówczas drzewo będzie spójne z danymi trenującymi, o ile nie są one sprzeczne i zbiór testów jest wystarczający. W praktyce rozrost drzewa może być zatrzymywany wcześniej i będą wówczas otrzymane drzewa niespójne z danymi trenującymi, które jednak mogą być preferowane ze względu na większą prostotę i możliwość uniknięcia nadmiernego dopasowania.

Wybór testu

Przy wyborze testu należy się kierować rozsądnym postulatem, aby zbudować możliwie jak najprostsze drzewo. Zwiększa to jego czytelność dla człowieka i zmniejsza ryzyko nadmiernego dopasowania. Dążenie do prostoty sprowadza się do dążenia do tego, aby kolejno wybierane testy jak najbardziej przybliżały moment, kiedy będzie można utworzyć liść, czyli aby w węzłach potomnych coraz dokładniej można było określić kategorię. W związku z tym do wyboru spośród możliwych do użycia testów stosuje się liczbowe funkcje oceny jednego z następujących rodzajów:

1. funkcje mierzące różnicę między zbiorem $P$ a zbiorami $P_{tr}$ dla $r\in R_t$ ze względu na rozkład częstości kategorii,
2. funkcje mierzące różnice między poszczególnymi zbiorami $P_{tr}$ dla $r\in R_t$ ze względu na rozkład częstości kategorii,
3. funkcje mierzące statystyczną niezależność między rozkładem kategorii a wyznaczanym przez test $t$ podziałem $P$ na podzbiory.

Najbardziej popularne jest wykorzystanie entropii do pomiaru niejednorodności rozkładu kategorii. Oparta na niej funkcja oceny testu, nazywana przyrostem informacji, jest obliczana następująco:

$$g_t(P) = I(P) - E_t(P)$$ (5)

gdzie

$$I(P) ={} \sum_{d\in C} -\frac{\vert P^d\vert}{\vert P\vert} \log\frac{\vert P^d\vert}{\vert P\vert}$$

$$E_t(P) ={} \sum_{r\in R_t}\frac{\vert P_{tr}\vert}{\vert P\vert}E_{tr}(P)$$

$$E_{tr}(P) ={} \sum_{d\in C}-\frac{\vert P^d_{tr}\vert}{\vert P_{tr}\vert} \log\frac{\vert P^d_{tr}\vert}{\vert P_{tr}\vert}$$

Przy dokładniejszej analizie okazuje się, że przyrost informacji ma tendencję do preferowania w nieuzasadniony sposób testów o dużej liczbie wyników. Jeśli przy budowie drzewa wykorzystywane są testy znacznie różniące się liczbą możliwych wyników, w celu uniknięcia takich preferencji sugeruje się wykorzystywanie do oceny jakości testów ilorazu:

$$\frac{g_t(P)}{\mathrm{IV}_t(P)}$$ (6)

gdzie $\mathrm{IV}_t(P)$ oznacza wartość informacyjną testu $t$ dla zbioru przykładów $P$, zdefiniowaną następująco:

$$\mathrm{IV}_t(P) = \sum_{r\in R_t}-\frac{\vert P_{tr}\vert}{\vert P\vert} \log\frac{\vert P_{tr}\vert}{\vert P\vert}$$ (7)

Wielkość ta mierzy równomierność, z jaką test $t$ dzieli zbiór $P$ na podzbiory.

Z kolei niezależność między rozkładem kategorii a wyznaczanym przez wyniki testu podziałem $P$ na podzbiory można mierzyć za pomocą statystyki $\chi^2$:

$$\chi^2_t(P) = \sum_{d\in C}\sum_{r\in R_t}\frac{\big(\vert P^d_{tr}\vert-e^d_{tr}(P)\big)^2} {e^d_{tr}(P)}$$

gdzie

$$e^d_{tr}(P) = \frac{\vert P_{tr}\vert\cdot\vert P^d\vert}{\vert P\vert}$$

Zbiór kandydujących do wyboru testów zazwyczaj zawiera wszystkie możliwe do określenia testy dla wykorzystywanych do opisu przykładów atrybutów pewnych z góry przyjętych rodzajów. Często są to np. testy tożsamościowe dla atrybutów nominalnych i nierównościowe dla porządkowych i ciągłych, albo testy przynależnościowe lub podziałowe dla wszystkich typów atrybutów. W przypadku atrybutów ciągłych liczba testów, jakie należy rozważyć, jest duża i może decydować o koszcie obliczeniowym algorytmu. Konieczne są wówczas pewne heurystyki eliminujące najmniej obiecujące testy oraz odpowiednio staranna implementacja. Niektóre przypadki są przedyskutowane niżej.

Testy nierównościowe

Zauważmy, że dla testów nierównościowych jako progi nierówności wystarczy brać pod uwagę tylko po jednej wartości (np. środkowej) pomiędzy każdymi dwoma sąsiednimi wartościami atrybutu występującymi w aktualnym zbiorze przykładów. W związku z tym dla wygody dokonuje się sortowania wartości atrybutu. Możliwość dalszego usprawnienia oceny testów nierównościowych kryje się w następującej właściwości. Można wykazać, że jeśli dla dwóch kolejnych (po posortowaniu) wartości $v_1$ i $v_2$ atrybutu ciągłego lub porządkowego $a$ wszystkie przykłady w zbiorze $P$ mają tę samą kategorię, to na pewno optymalna wartość progowa $\theta$ nie znajduje się między $v_1$ i $v_2$ i w związku z tym obliczanie jakości testów dla takich wartości $\theta$ można bezpiecznie pominąć. Intuicyjne uzasadnienie tego faktu jest prostsze od ścisłego dowodu i zadowolimy się nim. Otóż jeśli dla każdego przykładu $x\in P$, dla którego $v_1\leq a(x)\leq v_2$, mamy $c(x)=d$, to w przypadku wyboru wartości progowej $v_1\leq\theta<v_2$ uzyskamy podział zbioru $P$ na dwa podzbiory, w których te przykłady o kategorii $d$ będą rozdzielone (część z nich znajdzie się w jednym, a część w drugim podzbiorze). Oznacza to, że w podzbiorach tych będzie bardziej równomierny rozkład kategorii, niż gdyby wszystkie przykłady, o których mowa, znalazły się w tym samym podzbiorze, a tym samym nasz wybór wartości progowej $\theta$ nie jest najlepszy z możliwych.

Testy przynależnościowe

Ze względu na wykładniczo rosnącą liczbę możliwych podzbiorów przeciwdziedziny atrybutu również najlepszego testu przynależnościowego jest złożony obliczeniowo. Prosta heurystyka może polegać na tym, aby na początek rozważać wyłącznie podzbiory jednoelementowe i poddać ocenie oparte na nich testy przynależnościowe, następnie do najlepszego (lub kilku najlepszych) podzbioru dodać każdy możliwy drugi element i znów wybrać najlepszy podzbiór dwuelementowy, itd., tak długo jak długo ocena najlepszego uzyskanego dotąd testu będzie się poprawiać.

Testy podziałowe

Problem wyboru najlepszego testu podziałowego dla atrybutów o skończonej liczbie wartości jest problemem optymalnego podziału zbioru na podzbiory. Prosta heurystyka może polegać na rozpoczęciu od podzbiorów jednoelementowych i następnie w każdym kroku wyborze do połączenia dwóch takich podzbiorów, w których rozkład kategorii jest najbardziej zbliżony. Do mierzenia różnicy między rozkładami można np. wykorzystać statystykę $\chi^2$. W tym celu rozważamy faktyczny rozkład kategorii w obu podzbiorach oraz rozkład oczekiwany określony na podstawie podzbioru będącego ich połączeniem.

Koszt testów

W niektórych praktycznych zastosowaniach indukcji drzew decyzyjnych istotnym kryterium wyboru testów podczas konstrukcji drzewa, oprócz ich jakości, może być koszt. W pewnych dziedzinach rozsądnie jest przyjąć, że zastosowanie do dowolnego przykładu różnych testów wiąże się z różnymi kosztami. Jest tak na ogół wtedy, kiedy dla wszystkich lub niektórych określonych na dziedzinie atrybutów wartości nie są znane z góry, lecz mogą być wyznaczone w razie potrzeby ,,na żądanie''.

Jeśli przyjmiemy za podstawę oceny jakości testów przyrost informacji, a przez $\rho(t)$ oznaczymy koszt testu $t$, to kryteria prostą funkcję oceny uwzględniającą jednocześnie jakość i koszt testu można zapisać następująco:

$$\vartheta_t(P) = \frac{g_t^2(P)}{\rho(t)}$$ (8)

jeśli przyjmiemy, że za ocenę jakości odpowiada przyrost informacji $g_t(P)$. Ocena testu jest tu odwrotnie proporcjonalna do jego kosztu, lecz jakość jest uznawana za ważniejszą i w związku z tym przyrost informacji występuje w drugiej potędze. Naturalnym uogólnieniem jest wprowadzenie parametru określającego inny wykładnik tej potęgi. Inna możliwa funkcja oceny jest zdefiniowana jako

$$\vartheta_t(P) = \frac{2^{g_t(P)}-1}{(1+\rho(t))^{\alpha}}$$ (9)

gdzie $\alpha\in[0,1]$. Wpływ kosztów na ocenę testów podlega w tym przypadku regulowaniu przez dobór wartości parametru $\alpha$. Są to zaczerpnięte z literatury przykładowe funkcje oceny, które okazały się skuteczne w pewnych określonych dziedzinach. Przypuszczalnie dla każdego konkretnego zastosowania należy eksperymentalnie ustalić najbardziej skuteczny sposób uwzględniania kosztów testów.

Wybór kategorii

Wybór kategorii dla tworzonego liścia jest oczywisty: powinna to być kategoria większości przykładów w aktualnym zbiorze $P$, a gdyby ten zbiór był pusty, kategoria domyślna. Na pierwszym poziomie drzewa jest ona określana przez argument procedury budującej drzewo, a na niższych poziomach -- jako większościowa kategoria w zbiorze przykładów związanym z węzłem macierzystym.

Przycinanie drzew

Ze względu na dążenie do prostoty i uniknięcia nadmiernego dopasowania w praktyce najczęściej konieczne jest przycinanie drzew. Polega ono w podstawowej wersji na zastępowaniu wybranych węzłów (a tym samym całych poddrzew) liścmi, którym przypisuje się kategorię większości przykładów trenujących, które w trakcie budowy drzewa były związane z eliminowanym węzłem. Podstawowe znaczenie ma kryterium przycinania, które decyduje, czy węzeł będzie zastąpiony liściem. Najczęściej stosowane metody są krótko scharakteryzowane poniżej.

Przycinanie redukujące błąd:

przycięcie następuje, jeśli błąd próbki na odrębnym zbiorze przycinania (różnym od zbioru trenującego) jest dla węzła nie mniejszy, niż dla zastępującego liścia.

Przycinanie pesymistyczne:

przycięcie następuje, jeśli pesymistyczne oszacowanie błędu rzeczywistego węzła (oparte na przedziale ufności, zazwyczaj z poziomem) wyznaczone na podstawie błędu próbki na zbiorze trenującym jest większe od błędu próbki zastępującego go liścia, co można dla liścia $l$ i węzła $n$ zapisać następująco:

$$e^c_P(l) \leq e^c_P(n) + u_{\delta}\sqrt{\frac{e^c_P(n)(1-e^c_P(n))} {\vert P\vert}}$$ (10)

gdzie $P$ oznacza zbiór przykładów trenujących związanych z przycinanym węzłem $n$. Najczęściej przyjmuje się $u_{\delta}=1$. Ponieważ często -- przy standardowym kryterium stopu budowy drzewa -- otrzymuje się wartości $e^c_P(n)=0$, przy których podany warunek traci sens, można na potrzeby przycinania obliczać błąd próbki z wykorzystaniem $m$-szacowania, np.:

$$e^c_P(n) = \frac{\big\vert\{x\in P \;\vert\; n(x)\neq c(x)\}\big\vert + 1} {\vert P\vert + \vert C\vert}$$ (11)

gdzie $n(x)$ oznacza kategorię przypisaną przykładowi $x$ przez poddrzewo o korzeniu w węźle $n$.

Przycinanie na podstawie zasady minimalnej długości kodu:

przycięcie następuje, jeśli długość kodu niezbędna do zakodowania węzła i popełnianych przez niego pomyłek jest nie mniejsza, niż odpowiednia długość kodu dla liścia i popełnianych przez niego pomyłek. Długość kodu dla węzła w najprostszym przypadku obliczamy jako:

$$1 + \log_2\vert S\vert$$ (12)

gdzie $S$ jest zbiorem testów możliwych do użycia w węźle, a dla liścja jako:

$$1 + \log_2\vert C\vert$$ (13)

Długość kodu dla $k$ pomyłek popełnianych na zbiorze $P$ obliczymy jako:

$$k(\log_2\vert P\vert + \log_2(\vert C\vert-1))$$ (14)

Zagadnienia praktyczne

Przejrzymy tu krótko możliwe modyfikacje podstawowego algorytmu budowania drzewa decyzyjnego, które mogą być konieczne w pewnych zastosowaniach do odkrywania wiedzy.

Drzewa probabilistyczne

Tradycyjnie w metodach uczenia się maszyn dużą wagę przykłada się do błędu hipotez i hipotezy niedokładne uznaje się za nieprzydatne. Przy odkrywaniu wiedzy jednak nie zawsze celem, dla którego buduje się drzewo, jest klasyfikowanie nowych danych -- często może chodzić wyłącznie o znalezienie i przekazanie analitykom do interpretacji i wykorzystania zależności między atrybutami a kategorią, nawet jeśli nie prowadzi ona do bardzo dokładnej klasyfikacji. Dla wielu rzeczywistych zbiorów danych zbudowanie drzewa nadającego się do klasyfikowania nowych przykładów z zadowalającą dokładnością w praktyce okazuje się niemożliwe. W tych sytuacjach od drzew, których liście zawierają kategorie przykładów, bardziej przydatne są drzewa, których liście zawierają oszacowania rozkładów prawdopodobieństw kategorii. Takie drzewa ukazują występowanie zależności nawet jeśli nie jest ona na tyle ,,silna'', aby można było dla niej zbudować drzewo ,,deterministyczne''

Modyfikacja algorytmu jest w tym przypadku bardzo prosta. Sprowadza się do innego kryterium stopu (nie dąży się do uzyskania liścia z przykładami wyłącznie jednej kategorii, zwłaszcza że może to nigdy nie być osiągalne), a po jego spełnieniu do umieszczaniu w liściu zamiast większościowej kategorii liczników częstości występowania kategorii w aktualnym zbiorze przykładów $P$, będących podstawą do szacowania prawdopodobieństw.

Inkrementacyjna budowa drzewa

W pewnych zastosowaniach zachodzi konieczność aktualizowania hipotezy indukcyjnej przez uwzględnienie napływających okresowo nowych danych. Nawet jeśli wszystkie ,,stare'' dane są ciągle dostępne, budowanie za każdym razem drzewa od początku byłoby nieekonomiczne. W takich sytuacjach należy sięgnąć po algorytmy inkrementacyjnej aktualizacji drzewa. Naszkicujemy koncepcję, na jakiej tego typu algorytmy mogą być oparte.

Jest jasne, że podstawowy schemat inkrementacyjnego konstruowania drzewa decyzyjnego można sformułować jako procedurę składającą się z operacji wykonywanych w celu modyfikacji dotychczasowego drzewa przez uwzględnienie kolejnego przykładu trenującego. Aby zrekompensować brak dostępności wszystkich przykładów trenujących, przyjmiemy, że w węzłach i liściach drzewa przechowywane będą informacje niezbędne do podejmowania decyzji o wybieraniu testów i ustalaniu kategorii. Chodzi tu konkretnie o liczby $\vert P\vert$, $\vert P^d\vert$, $\vert P_{tr}\vert$ i $P^d_{tr}\vert$ dla wszystkich kategorii $d\in C$ oraz możliwych testów $t$ i ich wyników $r\in R_t$, gdzie $P$ oznacza zbiór wszystkich dotychczasowych przykładów odpowiadających danemu węzłowi lub liściowi. Do ich wyznaczenia zbiór ten nie jest wymagany, więc nie ma potrzeby zapamiętywania tych przykładów. Wystarczy uwzględniając w węźle lub liściu nowy przykład dokonać aktualizacji przechowywanych w nim informacji, polegającej na zwiększeniu odpowiednich liczników.

Uwzględnienie pierwszego przykładu powoduje utworzenie liścia. Każdy przykład uwzględniany w liściu lub węźle powoduje zwiększenie związanych z nim liczników. W przypadku, gdy jest to liść, uwzględnianie przykładu może zostać zakończone lub liść może zostać przekształcony w węzeł. Decyzja ta ma znaczenie analogiczne do decyzji o zatrzymaniu rekurencyjnych wywołań przy zstępującej konstrukcji drzewa, a kryterium jej podejmowania, które nazwiemy w związku z tym kryterium stopu, może być również bardzo podobne. Zgodnie z nim liść należy przekształcić w węzeł, jeśli nie wszystkie dotychczas uwzględnione w nim przykłady reprezentują tę samą kategorię. Możliwa jest także złagodzona wersja tego kryterium, wymagająca dominującej kategorii większościowej. Jeśli kryterium stopu dla liścia nie jest spełnione, zostaje on zastąpiony węzłem, dla którego oczywiście wybierany jest najlepszy według przyjętej funkcji oceny test. Następnie przykład musi zostać uwzględniony w tym poddrzewie tego węzła, któremu udpowiada uzyskiwany dla niego wynik wybranego testu. To samo zresztą musi się stać, jeśli uwzględniamy przykład w węźle, który nie został właśnie utworzony w celu zastąpienia liścia, lecz był już nim przedtem.

Jeśli poprzestaniemy na zastępowaniu w razie potrzeby liści węzłami i aktualizacji liczników, uzyskiwane drzewa będą silnie uzależnione od kolejności dostarczania przykładów i z pewnością w większości przypadków dalekie od optymalności ze względu na rozmiar. Rozmiar drzew decyzyjnych zależy od testów wybieranych dla poszczególnych węzłów, zaś w naszkicowanym schemacie inkrementacyjnej konstrukcji drzewa wybór testów następuje tylko przy przekształcaniu liści w węzły. Kiedy w przyszłości do utworzonego węzła trafią kolejne przykłady, pierwotny wybór testu może okazać się niezadowalający. Dla utrzymania odpowiednio wysokiej jakości drzewa niezbędna jest możliwość weryfikacji testów umieszczonych w poszczególnych węzłach i w razie potrzeby ich zmiana, prowadząca do rekonstrukcji drzewa. Dla każdego węzła należy zatem sprawdzić, czy aktualnie umieszczony w nim test jest najlepszy według przyjętej funkcji oceny, której wartość można obliczyć korzystając w przechowywanych w tym węźle liczników. Jeśli okaże się, że test ten powinien zostać wymieniony na inny, powstaje konieczność rekonstrukcji, która w ogólnym przypadku może być operacją dość skomplikowaną i być może także kosztowną, zdecydowanie jednak mniej, niż kosztowałoby zbudowanie nowego poddrzewa od podstaw. Nie wnikając w zbyt skomplikowane szczegóły tej operacji zauważmy co następuje:

• Funkcja poprawiająca drzewo w najbardziej naturalny sposób może być sformułowana rekurencyjnie, tak aby po sprawdzeniu i ewentualnej modyfikacji węzła-korzenia następowało wykonanie tych operacji dla jego poszczególnych poddrzew.
• Weryfikowanie testów nie musi być przeprowadzane dla węzłów, które nie były modyfikowane przez uwzględnianie następnych przykładów od czasu, gdy po raz ostatni dokonano dla nich wyboru lub weryfikacji testu. Pozwala to ograniczyć głębokość rekurencji, gdyż żaden węzeł potomny węzła nie wymagającego sprawdzenia, także nie wymaga sprawdzenia.
• Przy zmienianiu testu w węźle należy wziąć pod uwagę, czy nowo wybrany test nie występuje w którymś z jego poddrzew. Jeśli tak, powinna zostać przeprowadzona zamiana tych testów.
• Rekonstrukcja drzewa może być szczególnie skomplikowana, jeśli stosowane są testy o różnej liczbie wyników. Ograniczenie się do testów o binarnych wynikach, czyli równościowych dla atrybutów nominalnych oraz nierównościowych dla atrybutów porządkowych i ciągłych, zapewnia jednakową liczbę gałęzi wychodzących z każdego węzła i przez to znacząco ułatwia manipulacje zmieniające strukturę drzewa.
• Przy zmianie testu w węźle należy zadbać o odpowiednią aktualizację liczników przechowywanych w jego węzłach potomnych.

Interaktywna budowa drzewa

Nie zawsze nawet najbardziej skuteczne funkcje oceny testów i kryteria stopu prowadzą do drzewa spełniającego oczekiwania analityka prowadzącego proces odkrywania wiedzy. Czasem jego intuicja i doświadczenie mówi, jakich atrybutów na danym poziomie drzewa nie należy testować (nawet jeśli są najlepsze według funkcji oceny), które testować przed testowaniem innych, albo kiedy utworzyć liść (nawet jeśli automatyczne kryterium stopu nie jest spełnione), co może prowadzić niekoniecznie do drzewa dokładniejszego, ale lepiej nadającego się do interpretacji. To wszystko każde z pewnym dystansem patrzeć na prowadzone w ramach uczenia się maszyn badania nad ,,najlepszymi'' kryteriami oceny testów, stopu, przycinania itd. Są sytuacje praktyczne, w których i tak zamiast tych kryteriów decydować będzie doświadczenie analityka i jego rozumienie dziedziny, nie dające się przełożyć na liczbowe funkcje oceny.

Kolejność rozwijania węzłów

Przedstawiony rekurencyjny algorytm budowania drzewa decyzyjnego dokonuje jego rozbudowy zgodnie ze strategią w głąb. Oznacza ona, że jeśli dla nowo utworzonego węzła drzewa istnieje pewna liczba gałęzi, to kolejno dla każdej z nich jest konstruowane pełne poddrzewo aż do osiągnięcia liści, zanim zostanie wzięta pod uwagę następna gałąź. Przy alternatywnym podejściu wszerz dla każdej gałęzi najpierw jest tworzony tylko jeden poziom węzłów lub liści potomnych, a następnie w ten sam sposób przetwarza się gałęzie wychodzące z tych węzłów itd. W jeszcze bardziej skrajnym podejściu można każdorazowo brać pod uwagę tylko jedną nierozwiniętą gałąź w całym drzewie, znajdującą się na jego dowolnym poziomie i wybieraną ze względu na funkcję jakości najlepszego testu, jaki może być użyty w celu utworzenia dla niej węzła. O takim schemacie konstrukcji drzewa decyzyjnego powiemy, że wykorzystuje strategię najpierw najlepszy. Oczywiście każda z tych strategii da identyczny efekt przy kryterium stopu zależnym tylko od rozkładu kategorii w aktualnym zbiorze przykładów, ale w niektórych sytuacjach praktycznych mogą być stosowane kryteria stopu zależne np. od długości aktualnej ścieżki w drzewie lub liczby wszystkich dotychczas utworzonych dotąd węzłów, i wtedy oczywiście różne kryteria wyboru kolejnego węzła do rozwinięcia dadzą różne efekty.

Brakujące wartości atrybutów

Zagadnienie brakujących wartości atrybutów podczas uczenia się oraz stosowania hipotezy będzie przedmiotem innego wykładu, na którym zostaną przedstawione odpowiednie techniki, odpowiednie dla różnych algorytmów uczenia się i różnych reprezentacji hipotez. Tu zajmiemy się tylko jedną specyficzną techniką postępowania przy klasyfikacji przykładów z brakującymi wartościami atrybutów za pomocą drzew decyzyjnych, polegające na uwzględnianiu różnych możliwych wyników testu dla atrybutu o nieznanej wartości i wyznaczaniu prawdopodobieństwa poszczególnych kategorii.

Niech ścieżka od korzenia drzewa decyzyjnego do pewnego liścia $l$ prowadzi kolejno przez $m$ węzłów $n_1$, $n_2,\dots,n_m$, z którymi są związane odpowiednio testy $t_1,t_2,\dots,t_m$. Przez $r_1\in R_{t_1},r_2\in R_{t_2},\dots,r_m\in R_{t_m}$ oznaczmy odpowiednie wyniki tych testów, wyznaczające kolejne gałęzie drzewa składające się na ścieżkę. Prawdopodobieństwo tego, że podczas klasyfikowania pewnego ustalonego przykładu $x_*$ zostanie osiągnięty liść $l$, można wówczas zapisać jako następujący iloczyn:

$$\begin{split}\mathrm{Pr}(l\,\vert\,x_*) ={}& \mathrm{Pr}(t_1(... ...\,t_1(x_*)=r_1, \dots,t_{m-1}(x_*)=r_{m-1})\text{.} \end{split}$$ (15)

Gdy wyniki każdego testu dla przykładu $x_*$ są znane (czyli wartości wszystkich atrybutów są dla tego przykładu dostępne), każde z występujących w powyższym wyrażeniu prawdopodobieństw jest równe dokładnie 0 albo $1$. Wówczas osiągany podczas klasyfikowania tego przykładu liść jest wyznaczony jednoznacznie. Jeśli jednak wynik pewnego testu $t_k$ przeprowadzanego w węźle $n_k$ nie może być ustalony ze względu na brakującą wartość odpowiedniego atrybutu, to możemy przyjąć, że prawdopodobieństwo $\mathrm{Pr}(t_k(x_*)=r_k\,\vert\,t_1(x_*)=r_1,\dots,t_{k-1}(x_*)=r_{k-1})$ ma wartość równą odpowiedniemu prawdopodobieństwu dla losowo wybranego przykładu z dziedziny, zgodnie z określonym na niej pewnym rozkładem prawdopodobieństwa $\Omega$, czyli $\mathrm{Pr}_{x\in\Omega}(t_k(x)=r_k\,\vert\,t_1(x)=r_1,\dots,t_{k-1}(x)=r_{k-1})$. Takie prawdopodobieństwo można oszacować na podstawie dowolnego zbioru przykładów wybranych zgodnie z rozkładem $\Omega$, w tym także na podstawie zbioru trenującego (licząc przykłady, które trafiają do węzła $n_k$ oraz te spośród nich, dla których test $t_k$ daje wynik $r_k$). Oszacowania takiego można dokonać w trakcie budowy drzewa i przechowywać jego wynik w każdym węźle, aby nie wykonywać tych samych obliczeń wielokrotnie.

Dla dowolnego przykładu $x_*$, dla którego wynik jednego lub większej liczby testów nie może być ustalony, możemy więc osiągnąć z niezerowym prawdopodobieństwem wiele liści. Prawdopodobieństwo tego, że kategorią tego przykładu jest pewna kategoria $d\in C$, oszacujemy wówczas jako

$$\mathrm{Pr}(c(x_*)=d) = \sum_l \mathrm{Pr}(l\,\vert\,x_*) \cdot\mathrm{Pr}_{x\in\Omega}(c(x)=d\,\vert\,l)$$ (16)

gdzie $\mathrm{Pr}_{x\in\Omega}(c(x)=d\,\vert\,l)$ oznacza prawdopodobieństwo tego, że kategorią przykładu $x$ wybranego z dziedziny zgodnie z rozkładem $\Omega$ i zaliczonego do liścia $l$ jest $d$, które może być w oczywisty sposób oszacowane na podstawie rozkładu kategorii w tym liściu.

Literatura

1. Cichosz, P. Systemy uczące się. WNT, 2000. (Podrozdziały 3.1, 3.2, 3.3, 3.5.)
2. Witten, I. A., Frank, E. Data Mining. Morgan Kaufmann, 2000. (Podrozdziały 3.2, 4.3, 6.1.)
3. Quinlan, J. R. Induction of decision trees. Machine Learning, 1:81-106, 1986.
4. Quinlan, J. R. Simplifying decision trees. International Journal of Man-Machine Studies, 27:221-234, 1987.

About this document ...

Metody odkrywania wiedzy: wykład 4
Indukcja drzew decyzyjnych

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -no_navigation mow-w4.tex

The translation was initiated by Pawel Cichosz on 2004-02-12