ml drzewa decyzyjne - ghdrako/doc_snipets GitHub Wiki

Model drzew decyzyjnych to efektywny kwalifikator, który wykorzystuje strukturę drzewa do modelowania relacji pomiędzy cechami a potencjalnymi wynikami.

Drzewa decyzyjne buduje sie z wykorzystaniem heurystycznej techniki zwanej partycjonowaniem rekurencyjnym. Podejście to często okresla sie mianem "dziel i zwyciezaj", poniewaz dane sa dzielone na podzbiory, któłre nastepnie wielokrotnie dzieli sie na jeszcze mniejsze i tak dalej, az proces zatrzymije sie kierdy algorytm ustali, ze dane w podzbiorach sa wystarczajaco homogeniczne albo zostanie spełniony jakis inny warunek konca.

Jednym z ograniczeń reprezentacji w drzewie decyzyjnych jest to ze uzywa podziałow rownoległycg do osi. Kazdy podzial uwzglednia tylko jedna ceche co uniemozliwa tworzenie bardziej złzonych granic decyzyjnych.

Drzewa decyzyjne (ang. decision trees) stanowią wszechstronny algorytm uczenia maszynowego, służący zarówno do zadań klasyfikacji, jak i regresji. Sa też elementem składowym losowych lasów.

W ogólnym ujęciu głównym problem drzew decyzyjnych polega na ich całkiem dużej wariancji: małe zmiany w hiperparametrach lub danych mogą generować bardzo różne modele. Przeciwdziałaniem temu problemowi jest uśrednianie prognoz uzyskanych z wielu drzew co umożliwia znaczna redukcje wariancji. Taki zespół drzew nazywany jest lasem losowym (ang. random forest) i stanowi on jeden z najpotężniejszych współczesnych rodzajów modeli.

Drzewo decyzyjne stanowi jedna z najlepiej poznanych technik klasyfikacji. Można go używać w obydwu typach uczenia nadzorowanego (zadania klasyfikacji oraz regresji). Jego struktura decyzyj przypomina drzewo i odwzorowuje sposób myślenia człowieka, dzięki czemu łatwiej zrozumieć i interpretować wyniki. Możemy sprawdzić tez logikę kryjąca się za przewidywaniami.

Drzewa decyzyjne składają się z 3 głównych elementów, węzła wewnętrznego,rozgałęzienia i liścia. Tutaj każdy końcowy element symbolizuje cechę, połączenia miedzy węzłami oznacza regułę decyzyjna lub regułę podziału, natomiast w liściach przechowywane są wyniki predykcji. Pierwszym(głównym) węzłem jest korzeń (ang. root node). Dzieli on dane na podstawie cech lub wartości atrybutów. Dzielimy dane rekurencyjnie aż do chwili gdy wszystkie elementy będą się odnosić do tej samej klasy, lub do wyczerpania wszystkich kolumn,Istnieje wiele różnych algorytmów drzew decyzyjnych, np. CART, ID3, C4.5 czy CHAID. W bibliotece scikit-learn dostępne sa CART i ID3. W algorytmie CART (ang. Classification and Regresion Tree) do wyboru najlepszej kolumny służy tu wskaźnik Giniego. Wskaźnik ten stanowi różnice pomiędzy sumą kwadratów prawdopodobieństw każdej klasy a wartością 1. Cecha lub kolumna o najmniejszej wartości wskaźnika Giniego jest wybierana jako cecha stanowiąca podstawę podziału. Wartość wskaźnika Giniego mieści się w zakresie pomiędzy 0 a 1. Jeśli wynosi ona 0, oznacza ze wszystkie elementy przynależą do jednej klasy, natomiast wartość 1 świadczy o rozkładzie losowym wszystkich elementów. Wartość 0,5 świadczy o równomiernym podziale pomiędzy poszczególne klasy:

Przyklad

Mamy 100 wiadomosci w danym wezle 80 SPAM i 20 HAM. Liczymy nieczystość Giniego:

Algorytm sprawdza różne możliwe punkty podziału. Dla każdego potencjalnego podziału liczy średnią ważoną nieczystość dzieci.

Wybiera podział, który daje największą redukcję nieczystości czyli minimalizujacy ta wartość.

W algorytmie ID3 (ang. Iterative Dichotomizer 3) do wyboru atrybutów służy przyrost informacji lub entropia. Pojęcie entropii zostało zapożyczone z teorii informacji, które pozwala ocenić losowość, albo nieporządek w zbiorze wartości klas.Zbiory o wysokiej entropii sa bardzo zróżnicowane i dostarczają bardzo niewielu informacji o innych elementach które mogą również należeć, ponieważ elementy nie maja oczywistych cech wspólnych. Drzewo decyzyjne próbuje znaleźć podział, który zmniejsza entropie, w rezultacie zwiększa homogeniczność grupy.

Entropie zwykle mierzy się w bitach. Jeśli istnieją tylko 2 możliwe klasy, wartości entropii mieszczą się w zakresie od 0 do 1. W przypadku n klas entropia ma zakres od 0 do log2(n).

Cecha lub atrybut o największym przyroście informacji posłuży do podziału danych. Wartość 0 entropii oznacza istnienie tylko jednej klasy, natomiast wartość 1 świadczy o równomiernym rozkładzie elementów.

Dla entropii analogicznie minimalizuje się entropię dzieci, czyli maksymalizuje tzw. information gain:

Jak wskazuje maximum przy wartości x=0,5 , podział 50:50 daje największą entropie. W miarę jak jedna klasa zaczyna coraz bardziej dominować nad druga, entropia stopniowo spada do zera.

Aby użyć entropii do określenia optymalnej cechy, według której należny dokonać podziału, algorytm oblicza zmianę homogeniczności, która wynika z podziału według każdej możliwej cechy; miarę te nazywamy zyskiem informacyjnym. Zysk informacyjny dla cechy F oblicza się jako różnice entropii w segmencie przed podziałem (S1) i w partycjach wynikających z podziału (S2):

Sprawę komplikuje to ze po podziale dane sa zgrupowane w więcej niż jednej partycji. Dlatego funkcja obliczająca entropie musi uwzględniać łączna entropie we wszystkich partycjach wynikających z podziału. W tym celu mnożny entropie każdej partycji przez proporcje przykładów przypadająca na te partycje. Można to wyrazić następującym wzorem:

Łączna entropia wynikająca z podziału jest suma entropii każdej z n partycji warzonej proporcja przykładów przypadającą na partycje (wi).

Im wyższy zysk informacyjny, tym lepiej cecha tworzy homogeniczne grupy po dokonaniu podziału według tej cechy. Jeśli zysk wynosi zero, to podział według tej cechy nie powoduje zmniejszenia entropii. Z drugiej strony maksymalny zysk informacyjny jest równy entropii przed podziałem. W takim wypadku entropia po podziale musi być równa zero,co oznacza, ze wynikiem podziało są całkowicie homofoniczne grupy.

Powyższe wzory dotyczą cech nominalnych, ale drzewa decyzyjne wykorzystują zysk informacyjny również do dokonywania podziałów według cech liczbowych. W tym celu często testuje się różne podziały, które dzielą wartości na grupy większe lub mniejsze od pewnego progu. Sprowadza to cechę liczbowa do dwupoziomowej cechy kategorycznej, co pozwala obliczyć zysk informacyjny w zwykły sposób. Do podziału wybiera się liczbowy punkt ciecia, który przynosi największy zysk informacyjny.

Roznice miedzy nieczystoscia Giniego a zyskiem informacyjnym

While Gini impurity and information gain are both used to evaluate splits in decision trees, they can lead to different split decisions due to their distinct optimi- zation objectives. Gini impurity focuses on minimizing the “mix” of classes within each split, while information gain aims to reduce overall uncertainty (entropy) in the system. These differences become apparent in datasets with imbalanced class dis- tributions or when the splits lead to groups of very different sizes. For example, Gini impurity may prefer a split that creates a highly pure, but smaller group, as it directly rewards reductions in impurity. In contrast, information gain may favor a split that distributes the reduction in entropy more evenly across groups, even if individual group purity is lower. This divergence in decision-making refl ects their underlying mathematical approaches and highlights the importance of selecting the metric that aligns with the specifi c goals or constraints of a given classifi cation problem.

Problem przeuczenia - nadmiernego dopasowania

Drzewa decyzyjne mogą rosnąć bez ograniczeń, wybierając cech do podziału i grupując przykłady w coraz mniejszych partycjach, aż każdy przykład zostanie idealnie sklasyfikowany, albo algorytmowi zabraknie cech do dalszych podziałów. Jeśli jednak drzewo stanie się za duże, wiele decyzji będzie zbyt specyficznych, a model nadmiernie dopasuje się do danych treningowych. Proces przycinania (ang. pruning) drzewa decyzyjnego polega na ograniczaniu jego rozmiaru tak, aby lepiej generalizowało się na wcześniej niewidziane dane.

Jednym z rozwiązań tego problemu jest zatrzymanie wzrostu drzewa po osiągnięciu pewnej liczby decyzji albo wykryciu ze węzły decyzyjne zawierają tylko nieliczne przykłady. Jest to tak zwane wczesne zatrzymanie się albo wstępne przycinanie drzewa decyzyjnego. Ponieważ drzewo unika w ten sposób niepotrzebnej pracy jest to atrakcyjna strategia. Ma jednak tę wadę ze nie da się przewidzieć, czy drzewo nie przegapi subtelnych, ale ważnych wzorców, których nauczyło by się gdyby urosło do większego rozmiaru.

Alternatywa, zwana przycinaniem końcowym, polega na celowym zbudowaniu zbyt dużego drzewa, a następnie przycinaniu liści w celu ograniczenia rozmiaru drzewa do bardziej odpowiedniego rozmiaru. Często jest to podejście bardziej efektywne bo trudno jest określić optymalna głębokość drzewa decyzyjnego zanim się go nie zbuduje. Późniejsze przycinanie daje pewność że algorytm odkrył wszystkie ważne wzorce danych.

Jedna z zalet algorytmu C5.0 jest to ze wyręcza on użytkownika w przycinaniu - automatycznie podejmuje wiele decyzji z wykorzystaniem rozsądnych ustawień domyślnych. Jego ogólna strategia jest końcowe przycinanie drzewa. Algorytm najpierw buduje duże drzewo, które jest nadmiernie dopasowane do danych treningowych. Następnie usuwa gałęzie i węzły, które maja niewielki wpływ na błędy klasyfikacji.

Proces budowy klasyfikatora drzewa decyzyjnego: