Drzewo decyzyjne to narzędzie, powszechnie używane w Data Science do klasyfikacji. Jest również jednym z pierwszych koncepcji, którą należy opanować, aby zrozumieć bardziej złożone algorytmy jak lasy losowe. Poniżej zobaczymy, na czym polega drzewo decyzyjne i jak możemy je zastosować w praktyce.

Na potrzeby poniższego artykułu, skorzystamy ze znanego nam zbioru danych, zawierającego listę pasażerów statku Titanic, z informacją czy dana osoba przeżyła czy nie, oraz zmiennymi ją opisującymi:

http://analityk.edu.pl/zbior-danych-titanic-analiza-w-python/

Do czego może nam posłużyć drzewo decyzyjne

Naszym celem jest zbudowanie algorytmu, który na podstawie danych pasażera, przedstawi nam prawdopodobieństwo czy dana osoba przeżyje czy nie.

Przykładowo, posiadamy dane: Kobieta, wiek 30, klasa biletu – premium, port docelowy – Michigan. W rezultacie chcemy otrzymać informację: 1 – przeżyje, 0 – nie. W idealnym przypadku, nie tylko samo 0 czy 1, ale prawdopodobieństwo przeżycia, czyli jedynki – np 84%.

zero r algorytm

Większość pasażerów Titanica zginęła. Jeżeli spojrzymy na naszą listę pasażerów to dokładnie, 61 %. W związku, jeżeli dostaniemy dane nowego pasażera, możemy w ‚ślepo’ powiedzieć, że zginie i w około 61% przypadków, będziemy mieć rację.

Nie jest to najlepszy sposób predykcji, czy nowy pasażer zginie czy nie, ale ta wartość może pomóc nam się odnieść do jakości bardziej wyrafinowanych algorytmów, takich jak chociażby drzewo decyzyjne.

one r algorytm

Podejściem, które da nam lepsze efekty, jest podejście w którym wybieramy jeden parametr i dokonujemy predykcji na jego podstawie. Np płeć. Możemy powiedzieć, że jeżeli pasażer jest kobietą, to przeżyje i z 72% możemy spodziewać się, że będziemy mieli rację.

Znowu. Nie jest to jednak, najlepszy sposób predykcji, ale za to dobry wstęp do drzew decyzyjnych.

Czym są drzewa decyzyjne

Jest to prosta, lecz użyteczna w uczeniu maszynowym, koncepcja opierająca się o drzewo. Bardzo często stosowana do klasyfikacji, czyli przypisanie obserwacji zbioru danych do jednej z klas.

Na każdym węźle drzewa, dokonujemy podziały zbioru na 2 lub więcej mniejsze zbiory, mając na celu, jak najlepsze odseparowanie obserwacji należących do różnych klas.

Jak wygląda drzewo decyzyjne

Jeżeli dokonamy szybkiej analizy zbioru Titanic, za pomocą drzewa decyzyjnego, możemy otrzymać poniższy rezultat:

Drzewo decyzyjne
  • Pierwszą zmienną, którą algorytm wybrał do podziału zbioru to płeć. Widzimy że w przypadku kobiet, szanse na przeżycie wynosiły 72%
  • Następne, zarówno w przypadku kobiet, jak i mężczyzn, następną zmienną po dalszych podziałów zbiorów, mamy klasę biletu
  • A następnie, w przypadku gałęzi, dla kobiet, oraz klasy ekonomicznej, znaczenie miał port w którym osoba wsiadła na pokład. Możemy się domyślać, że zdecydowało to o odległości od kajut ratunkowych. Natomiast w przypadku gałęzi z mężczyznami, ilość dzieci oraz rodziców. Możemy się domyślać, że jest to skorelowane z wiekiem. Jeżeli mężczyzna, miał rodziców, to znaczy o jego młodym wieku i potencjalnym pierwszeństwie w zajęciu miejsca w kajucie ratunkowej.

Jak buduje się drzewo decyzyjne

Drzewo decyzyjne, dąży do wyboru takiego parametru podziału, oraz takich wartości podziału, aby w konsekwencji otrzymać ‚najlepszy’ podział.

‚Najlepszy’, mierzy się często za pomocą Gini Index lub Information Gain, opartym na entropii. Są to miary sprawdzające czystość podziału, czyli czy pozyskane poprzez podział liście drzewa, dają nam wartość. W idealnym przypadku, w wyniku podziału zbioru, za pomocą wybranego parametru, jeden liść zawierał by tylko i wyłącznie pasażerów którzy przeżyli, a drugi, tych którzy NIE przeżyli.

Następnie ponownie wybieramy parametr, oraz dokonujemy ponownego podziału, aby otrzymać jeszcze lepszy wynik.

Drzewo decyzyjne, możemy budować do momenty, w którym w każdym liść będzie w 100% czysty, czyli będzie zawierać obserwacje tylko i wyłącznie jednak klasy (przeżył lub nie).

W tedy jednak, drzewo będzie przeuczone (overfitted),

Poniżej, znajduje się drzewo decyzyjne, budowane do momentu, aż liście będą zawierać obserwację tylko jednej klasy:

 

Co oznacza, że osiągnęliśmy 100% skuteczność klasyfikacji czy ktoś zginie czy przeżyje, ale na zbiorze treningowym. Jeżeli użyli byśmy tego drzewa na nowych danych, to wynik był by prawdopodobnie gorszy. Drzewo decyzyjne jest przeuczone, a my dopatrzyliśmy się zależności które występują w zbiorze treningowym, ale prawdopodobnie po za nim, już nie.

Kiedy zatrzymujemy budowę drzewa decyzyjnego

W praktyce, budowę drzewa decyzyjnego, możemy zatrzymać w momencie kiedy:

  • Zbiór osiągnął minimalną liczbę obserwacji, np w liściu znajduje się mniej niż 5% wszystkich obserwacji
  • Nie mamy parametru, za pomocą którego, dalszy podział dałby nam lepszy wynik
  • Zbiór jest ‚czysty’, czyli zawiera obserwacje tylko jednego typu

Alternatywą jest ‚pruning’, czyli przycinanie. W tym podejściu, nie zatrzymujemy budowy drzewa, aby móc przyjrzeć się wszystkim znalezionym zależnościom, a następne eliminujemy te które uznamy za przeuczenie.

Reprezentacja drzewa decyzyjnego

Niewątpliwą zaletą drzew decyzyjnych, jest ich prosta reprezentacja w formie reguł if. Każdy liść, możemy zapisać, w przykładowy sposób:

if param1 > X and param2 < Y then probability = Z

W naszym przypadku, możemy powyższe drzewo, zapisać w postaci kilku reguł, wyglądających następująco:

Jeżeli pewnej obserwacji, dana reguła jest spełniona, zostaje jej przypisane prawdopodobieństwo, że należy do klasy o numerze 1. W naszym przypadku, oznacza to prawdopodobieństwo że osoba przeżyje.

Podsumowując

Najważniejszą zaletą drzewa decyzyjnego, jest jego prostota, która powoduje że jest to algorytm, którego działanie łatwo jest wytłumaczyć, a tym samym w łatwy sposób uzyskuje aprobatę i zgodę do implementacji w firmach.

jakość jego działania, oceniamy tak samo jak w przypadku innych algorytmów klasyfikacyjnych. Możemy użyć confusion matrix, wykresów ROC, Lift czy też profit curve.

Jest to ciągle bardzo popularna, obok regresji logistycznej, czy też SVM metoda klasyfikacji oraz podstawa budowy bardziej złożonych algorytmów takich jak lasy losowe.