Nauka drzewa decyzyjnego - Decision tree learning

Uczenie drzew decyzyjnych lub indukcja drzew decyzyjnych jest jednym z podejść modelowania predykcyjnego wykorzystywanych w statystyce , eksploracji danych i uczeniu maszynowym . Wykorzystuje drzewo decyzyjne (jako model predykcyjny ), aby przejść od obserwacji dotyczących pozycji (reprezentowanych w gałęziach) do wniosków dotyczących wartości docelowej pozycji (reprezentowanej w liściach). Modele drzew, w których zmienna docelowa może przyjmować dyskretny zestaw wartości, nazywane są drzewami klasyfikacyjnymi ; w tych strukturach drzewiastych liście reprezentują etykiety klas, a gałęzie reprezentują połączenia cech, które prowadzą do tych etykiet klas. Drzewa decyzyjne, w których zmienna docelowa może przyjmować wartości ciągłe (zazwyczaj liczby rzeczywiste ) nazywane są drzewami regresji . Drzewa decyzyjne należą do najpopularniejszych algorytmów uczenia maszynowego ze względu na ich zrozumiałość i prostotę.

W analizie decyzji drzewo decyzyjne może służyć do wizualnego i jawnego przedstawiania decyzji i podejmowania decyzji . W eksploracji danych drzewo decyzyjne opisuje dane (ale powstałe drzewo klasyfikacyjne może stanowić dane wejściowe do podejmowania decyzji ). Ta strona dotyczy drzew decyzyjnych w eksploracji danych .

Ogólny

Drzewo przedstawiające przeżycie pasażerów Titanica ("sibsp" to liczba małżonków lub rodzeństwa na pokładzie). Liczby pod liśćmi pokazują prawdopodobieństwo przeżycia i procent obserwacji w liściu. Podsumowując: Twoje szanse na przeżycie były duże, jeśli byłeś (i) kobietą lub (ii) mężczyzną w wieku poniżej 9,5 roku i miałeś mniej niż 3 rodzeństwa.

Nauka drzew decyzyjnych jest metodą powszechnie stosowaną w eksploracji danych. Celem jest stworzenie modelu, który przewiduje wartość zmiennej docelowej na podstawie kilku zmiennych wejściowych.

Drzewo decyzyjne to prosta reprezentacja do klasyfikacji przykładów. W tej sekcji załóżmy, że wszystkie cechy wejściowe mają skończone, dyskretne domeny i istnieje jedna cecha docelowa zwana „klasyfikacja”. Każdy element dziedziny klasyfikacji nazywamy klasą . Drzewo decyzyjne lub drzewo klasyfikacyjne to drzewo, w którym każdy węzeł wewnętrzny (nie będący liściem) jest oznaczony cechą wejściową. Łuki wychodzące z węzła oznaczonego cechą wejściową są oznaczone każdą z możliwych wartości cechy docelowej lub łuk prowadzi do podrzędnego węzła decyzyjnego na innej funkcji wejściowej. Każdy liść drzewa jest oznaczony klasą lub rozkładem prawdopodobieństwa nad klasami, co oznacza, że ​​zbiór danych został zaklasyfikowany przez drzewo do określonej klasy lub do określonego rozkładu prawdopodobieństwa (co, jeśli drzewo decyzyjne jest dobrze -skonstruowany, jest pochylony w kierunku pewnych podzbiorów klas).

Drzewo budowane jest poprzez podzielenie zbioru źródłowego , stanowiącego węzeł główny drzewa, na podzbiory, które stanowią następniki potomne. Podział opiera się na zestawie reguł podziału opartych na cechach klasyfikacji. Ten proces jest powtarzany dla każdego pochodnego podzbioru w sposób rekurencyjny zwany partycjonowaniem rekurencyjnym . Rekurencji jest zakończona, gdy podzbiór w węźle posiada wszystkie te same wartości zmiennej docelowej lub gdy rozszczepienie nie dodaje wartości do prognoz. Ten proces odgórnej indukcji drzew decyzyjnych (TDIDT) jest przykładem algorytmu zachłannego i jest to zdecydowanie najczęstsza strategia uczenia drzew decyzyjnych z danych.

W eksploracji danych drzewa decyzyjne można opisać również jako połączenie technik matematycznych i obliczeniowych, które pomagają w opisie, kategoryzacji i uogólnieniu danego zestawu danych.

Dane przychodzą w rekordach postaci:

Zmienna zależna, , jest zmienną docelową, którą próbujemy zrozumieć, sklasyfikować lub uogólnić. Wektor składa się z cech itp., które są używane do tego zadania.

Trzy różne reprezentacje drzewa regresji danych kifozy
Przykładowe drzewo, które szacuje prawdopodobieństwo wystąpienia kifozy po operacji kręgosłupa z uwzględnieniem wieku pacjenta i kręgu, od którego rozpoczęto operację. To samo drzewo jest pokazane na trzy różne sposoby. Po lewej Kolorowe liście pokazują prawdopodobieństwo kifozy po operacji kręgosłupa i procent pacjentów w liściu. Środek Drzewo jako działka perspektywiczna. Prawy widok z lotu ptaka środkowej działki. Prawdopodobieństwo kifozy po operacji jest wyższe w ciemniejszych obszarach. (Uwaga: leczenie kifozy znacznie się rozwinęło od czasu zebrania tego raczej niewielkiego zestawu danych.)

Typy drzew decyzyjnych

Drzewa decyzyjne wykorzystywane w eksploracji danych dzielą się na dwa główne typy:

  • Analiza drzewa klasyfikacji ma miejsce, gdy przewidywanym wynikiem jest klasa (dyskretna), do której należą dane.
  • Analiza drzewa regresji ma miejsce wtedy, gdy przewidywany wynik można uznać za liczbę rzeczywistą (np. cenę domu lub długość pobytu pacjenta w szpitalu).

Termin analiza drzewa klasyfikacji i regresji (CART) jest terminem zbiorczym używanym w odniesieniu do jednej z powyższych procedur, wprowadzonym po raz pierwszy przez Breimana i in. w 1984 roku. Drzewa używane do regresji i drzewa używane do klasyfikacji mają pewne podobieństwa, ale także pewne różnice, takie jak procedura stosowana do określenia miejsca podziału.

Niektóre techniki, często nazywane metodami zespołowymi , konstruują więcej niż jedno drzewo decyzyjne:

  • Wzmocnione drzewa Stopniowe budowanie zespołu przez trenowanie każdej nowej instancji, aby podkreślić instancje treningowe, które zostały wcześniej błędnie zamodelowane. Typowym przykładem jest AdaBoost . Mogą być używane do problemów typu regresyjnego i klasyfikacyjnego.
  • Zagregowane (lub zapakowane) drzewa decyzyjne Bootstrap , wczesna metoda zespołowa, budują wiele drzew decyzyjnych poprzez wielokrotne ponowne próbkowanie danych szkoleniowych z zastępowaniem i głosowanie na drzewach w celu uzyskania prognozy konsensusu.
  • Las rotacyjny – w którym każde drzewo decyzyjne jest trenowane poprzez zastosowanie analizy głównych składowych (PCA) na losowym podzbiorze cech wejściowych.

Szczególnym przypadkiem drzewa decyzyjnego jest lista decyzyjna , która jest jednostronnym drzewem decyzyjnym, tak że każdy węzeł wewnętrzny ma dokładnie 1 węzeł liścia i dokładnie 1 węzeł wewnętrzny jako dziecko (z wyjątkiem węzła najniższego, którego jedynym dzieckiem jest węzeł jednoliściowy). Chociaż listy decyzyjne są mniej wyraziste, są prawdopodobnie łatwiejsze do zrozumienia niż ogólne drzewa decyzyjne ze względu na ich dodatkową rzadkość, pozwalają na narzucanie niechciwych metod uczenia się i monotonicznych ograniczeń.

Godne uwagi algorytmy drzew decyzyjnych obejmują:

  • ID3 (iteracyjny dychotomizer 3)
  • C4.5 (następca ID3)
  • CART (drzewo klasyfikacji i regresji)
  • Automatyczne wykrywanie interakcji chi-kwadrat (CHAID). Wykonuje podziały wielopoziomowe podczas obliczania drzew klasyfikacyjnych.
  • MARS : rozszerza drzewa decyzyjne, aby lepiej obsługiwać dane liczbowe.
  • Drzewa warunkowego wnioskowania. Podejście oparte na statystyce, które wykorzystuje testy nieparametryczne jako kryteria podziału, skorygowane pod kątem wielu testów, aby uniknąć nadmiernego dopasowania. Takie podejście skutkuje bezstronnym wyborem predyktorów i nie wymaga przycinania.

ID3 i CART zostały wynalezione niezależnie mniej więcej w tym samym czasie (między 1970 a 1980), ale stosują podobne podejście do uczenia się drzewa decyzyjnego z trenujących krotek.

Zaproponowano również wykorzystanie koncepcji teorii zbiorów rozmytych do zdefiniowania specjalnej wersji drzewa decyzyjnego, znanej jako rozmyte drzewo decyzyjne (FDT). W tego typu klasyfikacji rozmytej zazwyczaj wektor wejściowy jest powiązany z wieloma klasami, z których każda ma inną wartość ufności. Wzmocnione zespoły FDT zostały ostatnio zbadane i wykazały wydajność porównywalną z innymi bardzo wydajnymi klasyfikatorami rozmytymi.

Metryka

Algorytmy konstruowania drzew decyzyjnych zwykle działają odgórnie, wybierając na każdym kroku zmienną, która najlepiej dzieli zbiór elementów. Różne algorytmy używają różnych metryk do mierzenia „najlepszego”. Zwykle mierzą one jednorodność zmiennej docelowej w podzbiorach. Kilka przykładów podano poniżej. Te metryki są stosowane do każdego podzbioru kandydującego, a wynikowe wartości są łączone (np. uśredniane), aby zapewnić miarę jakości podziału.

Nieczystość Giniego

Używany przez algorytm CART (drzewo klasyfikacji i regresji) dla drzew klasyfikacyjnych, zanieczyszczenie Giniego (nazwane na cześć włoskiego matematyka Corrado Giniego ) jest miarą tego, jak często losowo wybrany element ze zbioru byłby niepoprawnie oznakowany, gdyby został oznaczony losowo zgodnie z dystrybucja etykiet w podzbiorze. Zanieczyszczenie Giniego można obliczyć, sumując prawdopodobieństwo wybrania elementu z etykietą razy prawdopodobieństwo błędu w kategoryzacji tego elementu. Osiąga swoje minimum (zero), gdy wszystkie obserwacje w węźle należą do jednej kategorii docelowej.

Domieszka Giniego jest również miarą informacyjną i odpowiada Entropii Tsallisa ze współczynnikiem deformacji , co w fizyce wiąże się z brakiem informacji w układach nierównowagowych, nierozległych, dyssypatywnych i kwantowych. Za granicę odzyskuje się zwykłą entropię Boltzmanna-Gibbsa lub Shannona. W tym sensie zanieczyszczenie Giniego jest tylko odmianą zwykłej miary entropii drzew decyzyjnych.

Aby obliczyć zanieczyszczenie Giniego dla zestawu elementów z klasami, załóżmy , i niech będzie ułamkiem elementów oznaczonych klasą w zestawie.

Zdobywanie informacji

Używany przez algorytmy generowania drzewa ID3 , C4.5 i C5.0. Zysk informacyjny opiera się na koncepcji entropii i zawartości informacyjnej z teorii informacji .

Entropia jest zdefiniowana jak poniżej

gdzie są ułamki, które sumują się do 1 i reprezentują procent każdej klasy obecnej w węźle podrzędnym, który wynika z podziału w drzewie.

Uśrednianie możliwych wartości ,

Oznacza to, że oczekiwany zysk informacyjny jest informacją wzajemną, co oznacza, że ​​średnio zmniejszenie entropii T jest informacją wzajemną.

Zysk informacji jest używany do decydowania, na którą cechę podzielić na każdym etapie budowania drzewa. Prostota jest najlepsza, dlatego chcemy, aby nasze drzewo było małe. Aby to zrobić, na każdym kroku powinniśmy wybrać podział, który daje najbardziej spójne węzły podrzędne. Powszechnie stosowana miara spójności nazywana jest informacją mierzoną w bitach . Dla każdego węzła drzewa wartość informacyjna „reprezentuje oczekiwaną ilość informacji, która byłaby potrzebna do określenia, czy nowa instancja powinna zostać sklasyfikowana jako tak lub nie, biorąc pod uwagę, że przykład dotarł do tego węzła”.

Rozważ przykładowy zestaw danych z czterema atrybutami: perspektywa (słonecznie, pochmurno, deszczowo), temperatura (gorąca, łagodna, chłodna), wilgotność (wysoka, normalna) i wietrzna (prawda, fałsz), z binarnym (tak lub nie) zmienna docelowa, odtwarzanie i 14 punktów danych. Aby skonstruować drzewo decyzyjne na podstawie tych danych, musimy porównać zyski informacyjne każdego z czterech drzew, każde podzielone na jedną z czterech cech. Podział o największym wzmocnieniu informacyjnym zostanie przyjęty jako pierwszy podział i proces będzie kontynuowany, aż wszystkie węzły potomne będą miały spójne dane lub do momentu, gdy wzmocnienie informacyjne wyniesie 0.

Aby znaleźć zysk informacyjny podziału za pomocą windy , musimy najpierw obliczyć informacje w danych przed podziałem. Oryginalne dane zawierały dziewięć „tak” i pięć „nie”.

Podział przy użyciu funkcji windy daje w wyniku dwa węzły potomne, jeden dla wartości wietrznej true i jeden dla wartości wietrznej fałszu. W tym zestawie danych, istnieje sześć punktów danych z prawdziwego wietrznej wartości, z których trzy mają luz (gdzie gra jest zmienną docelową) wartość Tak, a trzy z zabaw wartość no. Osiem pozostałych punktów danych z wietrzną wartością false zawiera dwa „nie” i sześć „tak”. Informacja o węźle wietrznym = prawdziwy jest obliczana przy użyciu powyższego równania entropii. Ponieważ w tym węźle jest taka sama liczba „tak” i „nie”, mamy

Dla węzła, w którym windy =false, było osiem punktów danych, sześć tak i dwa nie. Tak więc mamy

Aby znaleźć informacje o podziale, bierzemy średnią ważoną tych dwóch liczb w oparciu o liczbę obserwacji w którym węźle.

Teraz możemy obliczyć zysk informacji osiągnięty przez podział na wietrznej funkcji.

Aby zbudować drzewo, należałoby obliczyć zysk informacji z każdego możliwego pierwszego podziału. Najlepszy pierwszy podział to taki, który zapewnia najwięcej informacji. Ten proces jest powtarzany dla każdego nieczystego węzła, aż drzewo będzie kompletne. Ten przykład jest zaadaptowany z przykładu zamieszczonego w Witten et al.

Redukcja wariancji

Wprowadzona w CART redukcja wariancji jest często stosowana w przypadkach, gdy zmienna docelowa jest ciągła (drzewo regresji), co oznacza, że ​​użycie wielu innych metryk wymagałoby najpierw dyskretyzacji przed zastosowaniem. Redukcja wariancji węzła N jest zdefiniowana jako całkowita redukcja wariancji zmiennej docelowej Y z powodu podziału w tym węźle:

gdzie , , i to odpowiednio zestaw wskaźników próbki przed podziałem, zestaw wskaźników próbki, dla których test podziału jest prawdziwy, oraz zestaw wskaźników próbki, dla których test podziału jest fałszywy. Każda z powyższych sum jest w rzeczywistości oszacowaniami wariancji , zapisanymi w formie bez bezpośredniego odniesienia do średniej.

Miara „dobroci”

Wykorzystywana przez CART w 1984 r. miara „dobroci” jest funkcją, która ma na celu zoptymalizowanie równowagi między zdolnością kandydata do podziału do tworzenia czystych dzieci z jego zdolnością do tworzenia dzieci o jednakowej wielkości. Ten proces jest powtarzany dla każdego nieczystego węzła, aż drzewo będzie kompletne. Funkcja , gdzie jest kandydującym podziałem w węźle , jest zdefiniowana jak poniżej

gdzie i są lewymi i prawymi dziećmi node używając odpowiednio split ; i są proporcjami rekordów odpowiednio w i ; i i są proporcjami rekordów klasowych odpowiednio w i .

Rozważ przykładowy zestaw danych z trzema atrybutami: oszczędności (niskie, średnie, wysokie), aktywa (niskie, średnie, wysokie), dochód (wartość liczbowa) i zmienną binarną ryzyka kredytowego (dobre, złe) i 8 punktów danych. Pełne dane przedstawia poniższa tabela. Aby rozpocząć drzewo decyzyjne, obliczymy maksymalną wartość użycia każdej cechy, aby znaleźć, która z nich podzieli węzeł główny. Ten proces będzie kontynuowany, dopóki wszystkie elementy podrzędne nie będą czyste lub wszystkie wartości będą poniżej ustawionego progu.

Klient Oszczędności Aktywa Dochód (1000 dolarów) Ryzyko kredytowe
1 Średni Wysoka 75 Dobry
2 Niski Niski 50 Zły
3 Wysoka Średni 25 Zły
4 Średni Średni 50 Dobry
5 Niski Średni 100 Dobry
6 Wysoka Wysoka 25 Dobry
7 Niski Niski 25 Zły
8 Średni Średni 75 Dobry

Aby znaleźć oszczędności cech , musimy zanotować ilość każdej wartości. Oryginalne dane zawierały trzy niskie, trzy średnie i dwa wysokie. Spośród najniższych jeden miał dobre ryzyko kredytowe, a spośród średnich i wysokich 4 miał dobre ryzyko kredytowe . Załóżmy podział kandydata w taki sposób, że rekordy z niskimi oszczędnościami zostaną umieszczone w lewym dziecku, a wszystkie inne rekordy zostaną umieszczone w prawym dziecku.

Aby zbudować drzewo, należy obliczyć „dobroć” wszystkich kandydujących podziałów dla węzła głównego. Kandydat z maksymalną wartością podzieli węzeł główny, a proces będzie kontynuowany dla każdego nieczystego węzła, aż drzewo zostanie ukończone.

W porównaniu z innymi miarami, takimi jak zysk informacji, miara „dobroci” będzie próbowała stworzyć bardziej zrównoważone drzewo, prowadzące do bardziej spójnego czasu podejmowania decyzji. Jednak poświęca pewien priorytet na tworzenie czystych elementów podrzędnych, co może prowadzić do dodatkowych podziałów, których nie ma w przypadku innych metryk.

Zastosowania

Zalety

Wśród innych metod eksploracji danych drzewa decyzyjne mają różne zalety:

  • Prosty do zrozumienia i interpretacji. Ludzie są w stanie zrozumieć modele drzew decyzyjnych po krótkim wyjaśnieniu. Drzewa można również wyświetlać graficznie w sposób łatwy do interpretacji dla osób niebędących ekspertami.
  • Potrafi obsługiwać zarówno dane liczbowe, jak i kategoryczne . Inne techniki zwykle specjalizują się w analizowaniu zbiorów danych, które mają tylko jeden typ zmiennej. (Na przykład reguły relacji mogą być używane tylko ze zmiennymi nominalnymi, podczas gdy sieci neuronowe mogą być używane tylko ze zmiennymi liczbowymi lub kategoriami przekonwertowanymi na wartości 0-1.) Wczesne drzewa decyzyjne były w stanie obsługiwać tylko zmienne kategorialne, ale nowsze wersje, takie jak jak C4.5, nie mają tego ograniczenia.
  • Wymaga niewielkiego przygotowania danych. Inne techniki często wymagają normalizacji danych. Ponieważ drzewa mogą obsługiwać predyktory jakościowe, nie ma potrzeby tworzenia zmiennych fikcyjnych .
  • Używa modelu białego pudełka lub otwartego pudełka. Jeśli dana sytuacja jest obserwowalna w modelu, wyjaśnienie warunku jest łatwe do wyjaśnienia za pomocą logiki boolowskiej. Natomiast w modelu czarnoskrzynkowym wyjaśnienie wyników jest zazwyczaj trudne do zrozumienia, na przykład w przypadku sztucznej sieci neuronowej .
  • Możliwość walidacji modelu za pomocą testów statystycznych. Umożliwia to uwzględnienie niezawodności modelu.
  • Podejście nieparametryczne, które nie przyjmuje żadnych założeń dotyczących danych uczących lub reszt predykcji; np. brak założeń dotyczących dystrybucji, niezależności lub stałej wariancji
  • Działa dobrze z dużymi zestawami danych. Duże ilości danych mogą być analizowane przy użyciu standardowych zasobów obliczeniowych w rozsądnym czasie.
  • Odzwierciedla podejmowanie decyzji przez człowieka dokładniej niż inne podejścia. Może to być przydatne podczas modelowania ludzkich decyzji/zachowań.
  • Odporny na współliniowość, szczególnie wzmacniający
  • Wbudowany wybór funkcji . Dodatkowa nieistotna funkcja będzie mniej używana, aby można je było usunąć przy kolejnych uruchomieniach. Hierarchia atrybutów w drzewie decyzyjnym odzwierciedla wagę atrybutów. Oznacza to, że funkcje na górze są najbardziej pouczające.
  • Drzewa decyzyjne mogą aproksymować dowolną funkcję Boole'a, np . XOR .

Ograniczenia

  • Drzewa mogą być bardzo mało wytrzymałe. Niewielka zmiana danych uczących może spowodować dużą zmianę w drzewie, a co za tym idzie ostatecznych prognoz.
  • Wiadomo, że problem uczenia się optymalnego drzewa decyzyjnego jest NP-zupełny w kilku aspektach optymalności, a nawet w przypadku prostych pojęć. W konsekwencji praktyczne algorytmy uczenia drzew decyzyjnych opierają się na heurystyce, takiej jak algorytm zachłanny, w którym w każdym węźle podejmowane są lokalnie optymalne decyzje. Takie algorytmy nie mogą zagwarantować zwrócenia globalnie optymalnego drzewa decyzyjnego. Aby zmniejszyć zachłanny efekt lokalnej optymalności, zaproponowano kilka metod, takich jak drzewo podwójnej odległości informacyjnej (DID).
  • Uczący się drzew decyzyjnych mogą tworzyć nadmiernie złożone drzewa, które nie uogólniają dobrze danych treningowych. (Jest to znane jako overfitting ). Mechanizmy takie jak przycinanie są niezbędne, aby uniknąć tego problemu (z wyjątkiem niektórych algorytmów, takich jak podejście warunkowego wnioskowania, które nie wymaga przycinania).
  • Średnia głębokość drzewa określona przez liczbę węzłów lub testów do momentu klasyfikacji nie jest gwarantowana jako minimalna lub mała przy różnych kryteriach podziału.
  • W przypadku danych zawierających zmienne kategorialne o różnej liczbie poziomów, zysk informacji w drzewach decyzyjnych jest przesunięty na korzyść atrybutów o większej liczbie poziomów. Jednak problemu wyboru predyktorów z obciążeniem unika się dzięki podejściu warunkowego wnioskowania, podejściu dwuetapowemu lub adaptacyjnemu doborowi cech z pominięciem jednego.

Realizacje

Wiele pakietów oprogramowania do eksploracji danych zapewnia implementacje jednego lub więcej algorytmów drzewa decyzyjnego.

Przykłady obejmują

Rozszerzenia

Wykresy decyzyjne

W drzewie decyzyjnym wszystkie ścieżki od węzła głównego do węzła liścia przebiegają na zasadzie koniunkcji lub AND . W grafie decyzyjnym możliwe jest użycie alternatywy (OR) do połączenia dwóch kolejnych ścieżek przy użyciu minimalnej długości komunikatu (MML). Wykresy decyzyjne zostały dodatkowo rozszerzone, aby umożliwić dynamiczne uczenie się wcześniej nieokreślonych nowych atrybutów i wykorzystywanie ich w różnych miejscach na wykresie. Bardziej ogólny schemat kodowania skutkuje lepszą dokładnością predykcyjną i logarytmiczną oceną probabilistyczną. Ogólnie rzecz biorąc, z grafów decyzyjnych wynikają modele z mniejszą liczbą liści niż drzewa decyzyjne.

Alternatywne metody wyszukiwania

Zastosowano algorytmy ewolucyjne, aby uniknąć lokalnych optymalnych decyzji i przeszukać przestrzeń drzewa decyzyjnego z niewielkim odchyleniem a priori .

Możliwe jest również próbkowanie drzewa za pomocą MCMC .

Drzewo można wyszukiwać od dołu do góry. Lub kilka drzew można zbudować równolegle, aby zmniejszyć oczekiwaną liczbę testów do momentu klasyfikacji.

Zobacz też

Bibliografia

Dalsza lektura

Zewnętrzne linki