Drzewa decyzyjne: jak zoptymalizować proces decyzyjny?

Wyobraźmy sobie, że grasz w dwadzieścia pytań. Twój przeciwnik potajemnie wybrał temat i musisz dowiedzieć się, co on / ona wybrała. Na każdym kroku możesz zadać pytanie „tak lub nie”, a twój przeciwnik musi odpowiedzieć zgodnie z prawdą. Jak znaleźć sekret w jak najmniejszej liczbie pytań?

Powinno być oczywiste, że niektóre pytania są lepsze niż inne. Na przykład pytanie „Czy może latać?”, Ponieważ Twoje pierwsze pytanie może być bezowocne, a pytanie „Czy to żyje?” Jest nieco bardziej przydatne. Intuicyjnie chcesz, aby każde pytanie znacznie zawęziło przestrzeń możliwych tajemnic, ostatecznie prowadząc do twojej odpowiedzi.

To podstawowa idea drzew decyzyjnych. W każdym punkcie rozważasz zestaw pytań, które mogą podzielić twój zestaw danych. Wybierz pytanie, które zapewnia najlepszy podział, i ponownie znajdź najlepsze pytania dla partycji. Zatrzymujesz się, gdy wszystkie punkty, które rozważasz, należą do tej samej klasy. Zatem zadanie klasyfikacji jest łatwe. Możesz po prostu chwycić punkt i zrzucić go z drzewa. Pytania poprowadzą go do odpowiedniej klasy.

Ważne warunki

Drzewo decyzyjne to rodzaj nadzorowanego algorytmu uczenia się, który można stosować zarówno w przypadku problemów z regresją, jak i klasyfikacją. Działa zarówno dla zmiennych jakościowych, jak i ciągłych zmiennych wejściowych i wyjściowych.

Zidentyfikujmy ważne terminologie dotyczące drzewa decyzyjnego, patrząc na obrazek powyżej:

  • Węzeł główny reprezentuje całą populację lub próbkę. Następnie dzieli się na 2 lub więcej jednorodnych zestawów.
  • Podział jest procesem dzielenia węzła na 2 lub więcej podwęzłów.
  • Kiedy podwęzeł dzieli się na dalsze podwęzły, nazywa się to Węzłem Decyzji.
  • Węzły, które się nie dzielą, nazywane są węzłem końcowym lub liściem.
  • Podczas usuwania podwęzłów węzła decyzyjnego proces ten nazywa się przycinaniem. Przeciwieństwem przycinania jest podział.
  • Podsekcja całego drzewa nazywana jest gałęzią.
  • Węzeł, który jest podzielony na podwęzły, nazywany jest węzłem nadrzędnym podwęzłów; podczas gdy podwęzły nazywane są dzieckiem węzła nadrzędnego.

Jak to działa

Mówię tu tylko o drzewie klasyfikacyjnym, które służy do przewidywania jakościowej odpowiedzi. Drzewo regresji służy do przewidywania wartości ilościowych.

W drzewie klasyfikacji przewidujemy, że każda obserwacja należy do najczęściej występującej klasy obserwacji treningowych w regionie, do którego należy. Interpretując wyniki drzewa klasyfikacyjnego, często jesteśmy zainteresowani nie tylko prognozami klas odpowiadającymi konkretnemu regionowi węzłów końcowych, ale także proporcjami klas wśród obserwacji szkoleniowych, które mieszczą się w tym regionie. Zadanie powiększenia drzewa klasyfikacyjnego polega na zastosowaniu jednej z tych 3 metod jako kryterium do tworzenia podziałów binarnych:

1 - Wskaźnik błędu klasyfikacji: możemy zdefiniować „wskaźnik trafień” jako część obserwacji treningowych w danym regionie, które nie należą do najczęściej występujących klas. Błąd wynika z tego równania:

E = 1 - argmax_ {c} (π̂ mc)

w którym π̂ mc reprezentuje ułamek danych treningowych w regionie R_m należących do klasy c.

2 - Indeks Gini: Indeks Gini jest alternatywną miarą błędów, która została zaprojektowana, aby pokazać, jak „czysty” jest region. „Czystość” w tym przypadku oznacza, ile danych szkoleniowych w danym regionie należy do jednej klasy. Jeśli region R_m zawiera dane pochodzące głównie z jednej klasy c, wówczas wartość indeksu Gini będzie niewielka:

3 - Cross-Entropy: Trzecia alternatywa, podobna do indeksu Gini, jest znana jako Cross-Entropy lub Deviance:

Entropia krzyżowa przyjmie wartość bliską zera, jeśli wszystkie π̂ mc są bliskie 0 lub bliskie 1. Dlatego, podobnie jak indeks Gini, entropia krzyżowa przyjmie małą wartość, jeśli m-ty węzeł jest czysty. W rzeczywistości okazuje się, że indeks Giniego i entropia krzyżowa są dość podobne liczbowo.

Podczas budowania drzewa klasyfikacji zwykle stosuje się albo indeks Gini, albo entropię krzyżową do oceny jakości określonego podziału, ponieważ są one bardziej wrażliwe na czystość węzłów niż poziom błędu klasyfikacji. Podczas przycinania drzewa można zastosować dowolne z tych 3 podejść, ale wskaźnik błędu klasyfikacji jest preferowany, jeśli celem jest dokładność prognozowania przyciętego drzewa.

Implementacja od zera

Przejrzyjmy algorytm budowania drzewa decyzyjnego ze wszystkimi szczegółami. Aby zbudować drzewo decyzyjne, musimy podjąć wstępną decyzję dotyczącą zestawu danych, aby określić, która funkcja jest używana do podziału danych. Aby to ustalić, musimy wypróbować każdą funkcję i ustalić, który podział da nam najlepsze wyniki. Następnie podzielimy zestaw danych na podzbiory. Podzbiory będą następnie przechodzić w dół gałęzi pierwszego węzła decyzyjnego. Jeśli dane w oddziałach są tej samej klasy, to odpowiednio je sklasyfikowaliśmy i nie musimy dalej dzielić. Jeśli dane nie są takie same, musimy powtórzyć proces podziału w tym podzbiorze. Decyzja o podziale tego podzbioru jest podejmowana w taki sam sposób, jak oryginalny zestaw danych, i powtarzamy ten proces, dopóki nie sklasyfikujemy wszystkich danych.

Jak dzielimy nasz zestaw danych? Jednym ze sposobów uporządkowania tego bałaganu jest pomiar informacji. Korzystając z teorii informacji, możemy zmierzyć informacje przed i po podziale. Zmiana informacji przed podziałem i po podziale nazywana jest zyskiem informacji. Kiedy wiemy, jak obliczyć przyrost informacji, możemy podzielić nasze dane na każdą funkcję, aby zobaczyć, który podział daje nam najwyższy przyrost informacji. Podział z najwyższym zyskiem informacji jest naszą najlepszą opcją.

Aby obliczyć przyrost informacji, możemy użyć Shannon Entropy, która jest oczekiwaną wartością wszystkich informacji o wszystkich możliwych wartościach naszej klasy. Zobaczmy kod Pythona:

Jak widać, najpierw obliczamy liczbę wystąpień w zestawie danych. Następnie tworzymy słownik, którego klucze są wartościami w ostatniej kolumnie. Jeśli klucz nie napotkał wcześniej, zostanie utworzony. Dla każdego klucza śledzimy, ile razy ta etykieta występuje. Na koniec używamy częstotliwości wszystkich różnych etykiet do obliczenia prawdopodobieństwa tej etykiety. To prawdopodobieństwo służy do obliczenia entropii Shannona i sumujemy to dla wszystkich etykiet.

Po ustaleniu sposobu pomiaru entropii zestawu danych musimy podzielić zbiór danych, zmierzyć entropię na podzielonych zestawach i sprawdzić, czy podział był właściwy. Oto kod, aby to zrobić:

Ten kod wymaga 3 danych wejściowych: danych, które mają zostać podzielone, funkcji, która ma zostać podzielona, ​​i wartości funkcji, która ma zostać zwrócona. Za każdym razem tworzymy nową listę, ponieważ będziemy wywoływać tę funkcję wiele razy w tym samym zestawie danych i nie chcemy modyfikować oryginalnego zestawu danych. Nasz zestaw danych to lista list; gdy wykonujemy iterację nad każdym elementem na liście i jeśli zawiera wartość, której szukamy, dodamy go do naszej nowo utworzonej listy. Wewnątrz instrukcji if wycięliśmy funkcję, na którą się podzieliliśmy.

Teraz połączymy 2 funkcje: ShannonEntropy i splitDataset, aby przechodzić między zestawami danych i zdecydować, którą funkcję najlepiej podzielić.

Szybko sprawdźmy kod:

  • Obliczamy entropię Shannona całego zestawu danych przed wystąpieniem podziału i przypisujemy wartość do zmiennej baseEntropy.
  • Pierwsza pętla for dla wszystkich funkcji w naszych danych. Używamy wyrażeń listowych do tworzenia listy (featList) wszystkich i-tych wpisów w danych lub wszystkich możliwych wartości obecnych w danych.
  • Następnie tworzymy nowy zestaw z listy, aby uzyskać unikalne wartości (UniqueVals).
  • Następnie przeglądamy wszystkie unikalne wartości tej funkcji i dzielimy dane dla każdej funkcji (subData). Nowa entropia jest obliczana (newEntropy) i sumowana dla wszystkich unikalnych wartości tej funkcji. Zysk informacji (infoGain) to zmniejszenie entropii (baseEntropy - newEntropy).
  • Na koniec porównujemy przyrost informacji między wszystkimi funkcjami i zwracamy indeks najlepszej funkcji do podziału (bestFeature).

Teraz, gdy możemy zmierzyć, jak zorganizowany jest zestaw danych i możemy podzielić dane, nadszedł czas, aby połączyć to wszystko i zbudować drzewo decyzyjne. Z zestawu danych dzielimy go na podstawie najlepszego atrybutu do podzielenia. Po podzieleniu dane przejdą w dół gałęzi drzewa do innego węzła. Ten węzeł ponownie podzieli dane. W tym celu użyjemy rekurencji.

Zatrzymamy się tylko pod następującymi warunkami: (1) zabraknie atrybutów, na które należy podzielić lub (2) wszystkie wystąpienia w gałęzi są tej samej klasy. Jeśli wszystkie wystąpienia mają tę samą klasę, utworzymy węzeł liścia. Wszelkie dane, które docierają do tego węzła liścia, uważa się za należące do klasy tego węzła liścia.

Oto kod do budowy naszych drzew decyzyjnych:

Nasz kod przyjmuje 2 dane wejściowe: dane i listę etykiet:

  • Najpierw tworzymy listę wszystkich etykiet klas w zbiorze danych i wywołujemy tę klasę list. Pierwszym warunkiem zatrzymania jest to, że jeśli wszystkie etykiety klas są takie same, zwracamy tę etykietę. Drugi warunek zatrzymania ma miejsce, gdy nie ma już więcej funkcji do podziału. Jeśli nie spełniamy warunków zatrzymania, korzystamy z funkcji selectBestFeatureToSplit, aby wybrać najlepszą funkcję.
  • Aby utworzyć drzewo, przechowujemy je w słowniku (myTree). Następnie otrzymujemy wszystkie unikalne wartości z zestawu danych dla naszej wybranej funkcji (bestFeat). Unikalny kod wartości wykorzystuje zestawy (UniqueVals).
  • Na koniec iterujemy wszystkie unikalne wartości z naszej wybranej funkcji i rekurencyjnie wywołujemy funkcję createTree () dla każdego podziału zestawu danych. Ta wartość jest wstawiana do słownika myTree, więc powstaje wiele zagnieżdżonych słowników reprezentujących nasze drzewo.

Wdrożenie poprzez Scikit-Learn

Teraz, gdy wiemy, jak zaimplementować algorytm od zera, skorzystaj z scikit-learn. W szczególności użyjemy klasy DecisionTreeClassifier. Pracując z zestawem danych tęczówki, najpierw importujemy dane i dzielimy je na część szkoleniową i testową. Następnie budujemy model przy użyciu domyślnego ustawienia pełnego rozwoju drzewa (rosnące drzewo, aż wszystkie liście będą czyste). Naprawiamy losowy stan w drzewie, który jest używany do wewnętrznego zrywania powiązań:

Uruchomienie modelu powinno dać nam dokładność zestawu testowego 95%, co oznacza, że ​​model poprawnie przewidział klasę dla 95% próbek w zestawie danych testowych.

Mocne i słabe strony

Główną zaletą korzystania z drzew decyzyjnych jest to, że intuicyjnie bardzo łatwo je wyjaśnić. Ściśle odzwierciedlają podejmowanie decyzji przez ludzi w porównaniu do innych metod regresji i klasyfikacji. Mogą być wyświetlane graficznie i mogą z łatwością obsługiwać predyktory jakościowe bez potrzeby tworzenia zmiennych zastępczych.

Kolejną ogromną zaletą jest to, że algorytmy są całkowicie niezmienne dla skalowania danych. Ponieważ każda funkcja jest przetwarzana osobno, a możliwe podziały danych nie zależą od skalowania, algorytmy drzewa decyzyjnego nie wymagają wstępnego przetwarzania, takiego jak normalizacja lub standaryzacja funkcji. W szczególności drzewa decyzyjne działają dobrze, gdy mamy funkcje o zupełnie innej skali lub połączenie funkcji binarnych i ciągłych.

Jednak drzewa decyzyjne na ogół nie mają tego samego poziomu dokładności prognozowania, co inne podejścia, ponieważ nie są one dość solidne. Niewielka zmiana danych może spowodować dużą zmianę w ostatecznym oszacowanym drzewie. Nawet przy użyciu przycinania wstępnego mają tendencję do przeładowywania i zapewniają słabą wydajność uogólnienia. Dlatego w większości aplikacji, agregując wiele drzew decyzyjnych, stosując metody takie jak tworzenie worków, losowe lasy i zwiększanie wydajności predykcyjnej drzew decyzyjnych można znacznie poprawić.

Źródła referencyjne:

  • Wprowadzenie do nauki statystycznej autorstwa Garetha Jamesa, Danieli Witten, Trevora Hastiego i Roberta Tibshirani (2014)
  • Machine Learning In Action autor: Peter Harrington (2012)
  • Wprowadzenie do uczenia maszynowego w języku Python autorstwa Sarah Guido i Andreasa Mullera (2016)

- -

Jeśli podobał ci się ten utwór, uwielbiam go, jeśli naciśniesz przycisk klaśnięcia , aby inni mogli się na niego natknąć. Mój własny kod możesz znaleźć na GitHub, a więcej moich tekstów i projektów na https://jameskle.com/. Możesz również śledzić mnie na Twitterze, e-mailem bezpośrednio lub znaleźć mnie na LinkedIn.