Drzewa decyzyjne.doc

DRZEWA DECYZYJNE

              Wprowadzenie

Sposób zapisywania wiedzy służącej do podejmowania decyzji przy pomocy drzew, jest bardzo stary i nie wywodzi się ani z systemów ekspertowych ani z sztucznej inteligencji. Dzisiaj jednak drzewa decyzyjne stanową podstawową metodę indukcyjnego uczenia się maszyn, spowodowane jest to dużą efektywnością, możliwością prostej programowej implementacji, jak i intuicyjną oczywistość dla człowieka. Ta metoda pozyskiwania wiedzy opiera się na analizie przykładów, przy czym każdy przykład musi być opisany przez zestaw atrybutów, gdzie każdy atrybut może przyjmować różne wartości. Wartości te powinny być dyskretne, w przypadku ciągłości dokonuje się zwykle dyskretyzacji na podstawie kilku przedziałów. Dopuszcza się możliwość, iż ciąg przykładów może zawierać błędy, jak również może zawierać atrybuty nie posiadające określonej wartości.

Formalnie drzewem decyzyjnym jest graf-drzewo, którego korzeń jest tworzony przez wybrany atrybut, natomiast poszczególne gałęzie reprezentują wartości tego atrybutu. Węzły drzewa w następnych poziomach będą przyporządkowane do kolejnym atrybutom, natomiast na najniższym poziomie otrzymujemy węzły charakteryzujące poszczególne klasy-decyzje.

Przykładowe drzewo decyzyjne może wyglądać tak:

Zalety:

·         Drzewa decyzyjne mogą reprezentować dowolnie złożone pojęcia pojedyncze lub wielokrotne, jeśli tylko ich definicje da się wyrazić w zależności od atrybutów

·         Efektywność pamięciowa reprezentacji drzewiastej

·         Czas decyzyjny ograniczony liniowo przez liczbę atrybutów (maksymalna głębokość drzewa)

·         Forma reprezentacji czytelna dla człowieka

·         Łatwość przejścia od reprezentacji drzewiastej do reprezentacji regułowej

Wady:

·         Testuje się wartość jednego atrybutu na raz, co powoduje niepotrzebny rozrost drzewa dla danych gdzie poszczególne atrybuty zależą od siebie (inne metody reprezentacji mogą być w tym przypadku o wiele mniej złożone)

·         Kosztowna reprezentacja alternatyw pomiędzy atrybutami – znaczny rozrost drzewa (w przeciwieństwie do reprezentacji koniunkcji, która jest zapisywana jako pojedyncza „ścieżka”, czyli droga od korzenia do liścia)

·         Drzewa decyzyjne nie stwarzają łatwej możliwości do ich inkrementacyjnego aktualizowania, algorytmy udoskonalające gotowe już drzewa poprzez zestaw nowych przykładów są bardzo złożone i zazwyczaj wynikiem jest drzewo gorszej jakości niż drzewo budowane od początku z kompletnym zestawem przykładów

              Konstruowanie drzewa decyzyjnego

                            Konstrukcje drzewa na podstawie zbioru przykładów, najprościej przedstawić w postaci algorytmu rekurencyjnego uruchamianego dla każdego węzła w drzewie:

              Pierwszym krokiem algorytmu jest podjęcie decyzji, czy rozpatrywany węzeł analizując dostępny zestaw atrybutów i klas-decyzji powinien stać się albo

1)     Etykietą opisującą klasę-decyzję (liść końcowy drzewa) wg kryterium stopu, taka decyzja spowoduje utworzenie węzła i zakończenie się tego wywołania algorytmu, albo:

2)     Węzłem-rozgałęzieniem co spowoduje wybór atrybutu z puli dostępnych atrybutów według kryterium wyboru atrybutu i następnie na podstawie wartości jakich przyjmuje wybrany argument z zestawu przykładów tworzone są kolejne węzły drzewa - uruchamiany jest rekurencyjnie ten algorytm, jednak dla każdego „rozgałęzienia” podawany jest zestaw atrybutów zmniejszony o aktualnie wybrany atrybut, jak również zestaw przykładów jest zmniejszany o te przykłady, które nie posiadają odpowiedniej wartości wybranego atrybutu dla każdego rozgałęzienia.

              W ten sposób są skonstruowane w praktyce wszystkie algorytmy tworzenia drzew decyzyjnych. Jedyne różnice w ich implementacjach polegają na odpowiedniej konstrukcji kryterium stopu i kryterium wyboru atrybutu. Odpowiednia technika wyboru argumentu ma kluczowy wpływ na wygląd drzewa decyzyjnego, gdyż właśnie od kolejności wyboru atrybutów zależy w głównej mierze głębokość i stopień rozbudowy drzewa.

              Czasami ze względów czysto technicznych odchodzi się od realizacji algorytmów rekurencyjnych szczególnie, gdy operujemy na dużej ilości przykładów i atrybutów - wtedy każde wywołanie procedury pociąga za sobą duże ilości danych magazynowanych na stosie programowym. Dlatego w takich przypadkach korzysta się z tak zwanego „jawnego stosu” bądź też z wykorzystuje się metodę konstruowania drzewa strategią „wszerz” jednak działanie samego algorytmu jest w praktyce identyczne.

              Kryterium stopu

              Wywołania rekurencyjne algorytmu tworzącego drzewo należy kiedyś zakończyć, odpowiada za to właśnie „kryterium stopu”. Określa ono czy dany węzeł drzewa powinien być traktowany jako końcowy liść drzewa zawierający w swoim opisie etykietę klasy-decyzji. Musi on zwrócić wartość etykiety w dwóch przypadkach:

1. Kiedy w trakcie wywołań rekurencyjnych w zestawie przykładów znajdują się już tylko przykłady opisujące tylko jedną klasę-decyzji. W takim przypadku kryterium stopu powinno zwrócić właśnie tę klasę.
2. Kiedy zestaw atrybutów argumentów osiągnie zero wtedy kryterium stopu powinno zgłosić jedną z możliwości:

·         Błąd, gdyż na podstawie przykładów nie można jednoznacznie ustalić odpowiednią klasę-odpowiedź. Może to być spowodowane niepoprawnym zbiorem przykładów (zawierającym przekłamania), lub zestaw atrybutów nie opisuje przykładów w dostatecznym stopniu.

·         Zwrócić etykietę klasy-decyzji, która najliczniej występuje w zestawie przykładów, jednak takie rozwiązanie nie zapewni spójności drzewa z uczącym ciągiem przykładów

              Kryterium wyboru atrybutu

              Jest to w zasadzie najważniejsza część algorytmu, to od niej zależy kolejność wyboru atrybutów, a co w znaczącym stopniu wpływa na wygląd drzewa. Poprawny ich dobór gwarantuje nieskomplikowany i czytelny obraz drzewa. Na wybór odpowiedniego atrybutu w zasadzie jego typ nie ma wpływu, gdyż atrybuty o typie ciągłym bądź wyliczeniowym traktuje się tak jakby były to atrybuty dyskretne poprzez sklasyfikowanie ich do odpowiednich przedziałów.

              Wybór odpowiedniego atrybutu ze zbioru atrybutów, jest dokonywany dzięki wprowadzeniu systemu ocen. Stało się to możliwe dzięki matematycznym narzędziom takim jak teoria informacji i statystyka. Wybierając jeden z atrybutów jesteśmy w stanie podzielić zbiór danych przykładów na mniejsze zbiory w zależności od wartości wybranego atrybutu. System ocen atrybutów opiera się na założeniu, iż najbardziej „bezużytecznym” atrybutem jest taki, w którym rozkład częstości występowania kolejnych klas-wyboru jest taki sam przed i po podziale zbioru danych przykładów wg ocenianego atrybutu.

              Obserwując konkretne implementacje algorytmów tworzenia drzew decyzyjnych można podzielić funkcje „oceniające” na trzy podstawowe grupy:

1.      Funkcje mierzące różnicę między zbiorem P (przykładów), a zbiorami, na jakie dzieli się ten zbiór wg wartości ocenianego atrybutu ze względu na rozkład częstotliwości klas-decyzji.

2.      Funkcje mierzące różnicę między poszczególnymi podzbiorami zbioru P (utworzonymi na podstawie wartości „ocenianego” atrybutu), ze względu na rozkład częstotliwości klas-decyzji.

3.      Funkcje mierzące statystyczną niezależność między rozkładem klas-decyzji a podziałem P na podzbiory.

              Pierwsza grupa funkcji jest najliczniejsza. Należą do niej wszystkie algorytmy wywodzące się z CLS (ang. Concept Learning System) czy też jego rozwinięcia ID3. Ocena atrybutów w tych algorytmach jest wyznaczana na podstawie przyrostów informacji. Informację zawartą w zbiorze etykietowanych przykładów P można wyrazić następująco:

.

4