Algorytm drzewa decyzyjnego — kompletny przewodnik

Ten artykuł został opublikowany jako część Blogathon Data Science

Do tej pory dowiedzieliśmy się o regresji liniowej, regresji logistycznej i były one dość trudne do zrozumienia. Zacznijmy teraz od drzewa decyzyjnego i zapewniam, że jest to prawdopodobnie najłatwiejszy algorytm w uczeniu maszynowym. Nie ma tu zbyt wiele matematyki. Ponieważ jest bardzo łatwy w użyciu i interpretacji, jest to jedna z najczęściej stosowanych i praktycznych metod wykorzystywanych w uczeniu maszynowym.

Spis treści

1. Czym jest drzewo decyzyjne?

2. Przykład drzewa decyzyjnego

3. Entropia

4. Zdobywanie informacji

5. Kiedy przestać dzielić?

6. Jak przestać przesadzać?

• maksymalna głębokość
• min_samples_split
• min_próbki_liść
• maks_funkcje

7. Przycinanie

• Po cięciu
• Przycinanie wstępne

8. Przypisy końcowe

Czym jest drzewo decyzyjne?

Jest to narzędzie, które ma aplikacje obejmujące kilka różnych obszarów. Drzewa decyzyjne mogą być wykorzystywane zarówno do problemów klasyfikacji, jak i regresji. Sama nazwa sugeruje, że używa schematu blokowego przypominającego strukturę drzewa, aby pokazać prognozy wynikające z serii podziałów opartych na funkcjach. Zaczyna się od węzła korzeniowego, a kończy decyzją podjętą przez liście.

1 Obraz

Zanim dowiemy się więcej o drzewach decyzyjnych, zapoznajmy się z niektórymi terminologiami.

Węzły główne – Jest to węzeł obecny na początku drzewa decyzyjnego z tego węzła, z którego populacja zaczyna się dzielić według różnych cech.

Węzły decyzyjne – węzły, które otrzymujemy po podzieleniu węzłów głównych nazywamy węzłem decyzyjnym

Węzły liściowe – węzły, w których dalszy podział nie jest możliwy, nazywamy węzłami liści lub węzłami końcowymi

Poddrzewo – tak jak mały fragment wykresu nazywa się podwykresem, podobnie podsekcja tego drzewa decyzyjnego nazywa się poddrzewem.

Przycinanie – to nic innego jak wycięcie niektórych węzłów, aby zapobiec nadmiernemu dopasowaniu.

2 Obraz

Przykład drzewa decyzyjnego

Zrozummy drzewa decyzyjne na przykładzie.

3 Obraz

Drzewa decyzyjne są odwrócone, co oznacza, że ​​korzeń znajduje się na górze, a następnie ten korzeń jest podzielony na kilka różnych węzłów. Drzewa decyzyjne są niczym innym jak zbiorem stwierdzeń jeśli-innych w terminologii laika. Sprawdza, czy warunek jest spełniony, a jeśli jest, to przechodzi do następnego węzła dołączonego do tej decyzji.

Na poniższym diagramie drzewo najpierw zapyta, jaka jest pogoda? Czy jest słonecznie, pochmurno czy deszczowo? Jeśli tak, przejdzie do następnej funkcji, czyli wilgotności i wiatru. Ponownie sprawdzi, czy jest silny wiatr, czy słaby, jeśli jest słaby wiatr i jest deszczowo to osoba może iść i pobawić się.

4 Obraz

Czy zauważyłeś coś na powyższym schemacie blokowym? Widzimy, że jeśli pogoda jest pochmurna wtedy musimy iść się bawić. Dlaczego nie podzielił się bardziej? Dlaczego na tym się zatrzymało?

Aby odpowiedzieć na to pytanie, musimy znać kilka innych pojęć, takich jak entropia, zysk informacji i indeks Giniego. Ale w uproszczeniu mogę tutaj powiedzieć, że dane wyjściowe dla zestawu danych treningowych są zawsze tak dla pochmurnej pogody, ponieważ nie ma tu nieporządku, nie musimy dalej dzielić węzła.

Celem uczenia maszynowego jest zmniejszenie niepewności lub zaburzeń ze zbioru danych, a do tego używamy drzew decyzyjnych.

Teraz musisz pomyśleć, skąd mam wiedzieć, jaki powinien być węzeł główny? jaki powinien być węzeł decyzyjny? kiedy powinienem przestać się dzielić? Aby to ustalić, istnieje metryka zwana „Entropią”, która jest ilością niepewności w zbiorze danych.

Entropia

Entropia to nic innego jak niepewność w naszym zbiorze danych lub miara nieporządku. Spróbuję to wyjaśnić na przykładzie.

Załóżmy, że masz grupę przyjaciół, którzy decydują, który film mogą wspólnie obejrzeć w niedzielę. Dostępne są 2 opcje dla filmów, jedna to "Lucy" a drugi to „Titanic” a teraz każdy musi powiedzieć swój wybór. Gdy wszyscy udzielą odpowiedzi, widzimy, że „Lucy” otrzymuje 4 głosy i „Titanic” otrzymuje 5 głosów. Który film teraz oglądamy? Czy nie jest trudno wybrać teraz 1 film, ponieważ głosy na oba filmy są nieco równe.

To jest dokładnie to, co nazywamy nieporządkiem, liczba głosów na oba filmy jest taka sama i tak naprawdę nie możemy zdecydować, który film powinniśmy obejrzeć. Byłoby o wiele łatwiej, gdyby głosów na „Lucy” było 8, a na „Titanica” 2. Tutaj można śmiało powiedzieć, że większość głosów jest na „Lucy”, więc wszyscy będą oglądać ten film.

W drzewie decyzyjnym wynik to najczęściej „tak” lub „nie”

Wzór na Entropię pokazano poniżej:

Tutaj p₊ jest prawdopodobieństwo pozytywnej klasy

p_- jest prawdopodobieństwo ujemnej klasy

S jest podzbiorem przykładu szkoleniowego

Jak drzewa decyzyjne wykorzystują Entropię?

Teraz wiemy, czym jest entropia i jaki jest jej wzór. Następnie musimy wiedzieć, jak dokładnie działa w tym algorytmie.

Entropia zasadniczo mierzy zanieczyszczenie węzła. Nieczystość to stopień przypadkowości; mówi, jak losowe są nasze dane. A czysty sub-split oznacza, że ​​albo powinieneś otrzymywać „tak”, albo powinieneś otrzymywać „nie”.

Załóżmy, że cecha początkowo ma 8 „tak” i 4 „nie”, po pierwszym podziale lewego węzła dostaje 5 „tak” i 2 „nie” podczas gdy prawy węzeł otrzymuje 3 „tak” i 2 „nie”.

Widzimy tutaj, że podział nie jest czysty, dlaczego? Ponieważ nadal możemy zobaczyć pewne klasy ujemne w obu węzłach. Aby stworzyć drzewo decyzyjne, musimy obliczyć zanieczyszczenie każdego podziału, a gdy czystość wynosi 100%, tworzymy go jako węzeł liścia.

Aby sprawdzić zanieczyszczenie cechy 2 i cechy 3, skorzystamy z pomocy dla formuły Entropia.

Źródło obrazu: Autor

W przypadku funkcji 3

Z samego drzewa wyraźnie widać, że lewy węzeł ma niższą entropię lub większą czystość niż prawy węzeł, ponieważ lewy węzeł ma większą liczbę „tak” i łatwo jest tutaj podjąć decyzję.

Zawsze pamiętaj, że im wyższa Entropia, tym niższa będzie czystość, a wyższa nieczystość.

Jak wspomniano wcześniej, celem uczenia maszynowego jest zmniejszenie niepewności lub zanieczyszczeń w zbiorze danych, tutaj za pomocą entropii uzyskujemy domieszkę konkretnego węzła, nie wiemy, czy entropia nadrzędna czy entropia konkretnego węzła spadła, czy nie.

W tym celu wprowadzamy nową metrykę o nazwie „Wzmocnienie informacji”, która mówi nam, jak bardzo spadła entropia rodzicielska po podzieleniu jej za pomocą jakiejś funkcji.

Zdobycie informacji

Zysk informacji mierzy zmniejszenie niepewności danej cechy i jest również decydującym czynnikiem, dla którego atrybut powinien zostać wybrany jako węzeł decyzyjny lub węzeł główny.

Jest to po prostu entropia pełnego zbioru danych – entropia zbioru danych z pewną cechą.

Aby to lepiej zrozumieć, rozważmy przykład:
Załóżmy, że cała nasza populacja ma łącznie 30 instancji. Zestaw danych ma przewidywać, czy dana osoba pójdzie na siłownię, czy nie. Powiedzmy, że 16 osób chodzi na siłownię, a 14 nie

Teraz mamy dwie funkcje, które pozwalają przewidzieć, czy pójdzie na siłownię, czy nie.

Cecha 1 to „Energia” który przyjmuje dwie wartości "wysoki i niski"

Cecha 2 to "Motywacja" który przyjmuje 3 wartości „Brak motywacji”, „Neutralny” i „Wysoce zmotywowany”.

Zobaczmy, jak nasze drzewo decyzyjne zostanie wykonane przy użyciu tych dwóch funkcji. Wykorzystamy zysk informacji, aby zdecydować, która funkcja powinna być węzłem głównym, a która powinna zostać umieszczona po podziale.

Źródło obrazu: Autor

Obliczmy entropię:

Aby zobaczyć średnią ważoną entropii każdego węzła, zrobimy co następuje:

Teraz mamy wartość E(Parent) i E(Parent|Energy), zysk informacji będzie wynosił:

Nasza entropia rodzicielska była bliska 0.99 i po przyjrzeniu się tej wartości przyrostu informacji możemy powiedzieć, że entropia zbioru danych zmniejszy się o 0.37, jeśli jako nasz węzeł główny ustawimy „Energia”.

Podobnie zrobimy to z drugą funkcją „Motywacja” i obliczymy jej zysk informacyjny.

Źródło obrazu: Autor

Obliczmy tutaj entropię:

Aby zobaczyć średnią ważoną entropii każdego węzła, zrobimy co następuje:

Teraz mamy wartość E(Parent) i E(Parent|Motivation), zysk informacji będzie wynosił:

Widzimy teraz, że funkcja „Energia” zapewnia większą redukcję, która wynosi 0.37 niż funkcja „Motywacja”. Dlatego wybierzemy cechę, która ma największy przyrost informacji, a następnie podzielimy węzeł na podstawie tej cechy.

W tym przykładzie „Energia” będzie naszym węzłem głównym i zrobimy to samo dla pod-węzłów. Tutaj widzimy, że gdy energia jest „wysoka”, entropia jest niska i możemy powiedzieć, że osoba na pewno pójdzie na siłownię, jeśli ma wysoką energię, ale co, jeśli energia jest niska? Ponownie podzielimy węzeł na podstawie nowej funkcji, którą jest „Motywacja”.

Kiedy przestać się dzielić?

Musisz zadać sobie to pytanie, kiedy przestaniemy uprawiać nasze drzewo? Zwykle zestawy danych w świecie rzeczywistym mają dużą liczbę funkcji, co skutkuje dużą liczbą podziałów, co z kolei daje ogromne drzewo. Takie drzewa wymagają czasu i mogą prowadzić do nadmiernego dopasowania. Oznacza to, że drzewo zapewni bardzo dobrą dokładność zestawu danych uczących, ale słabą dokładność danych testowych.

Istnieje wiele sposobów rozwiązania tego problemu poprzez dostrajanie hiperparametrów. Możemy ustawić maksymalną głębokość naszego drzewa decyzyjnego za pomocą maksymalna głębokość parametr. Im większa wartość maksymalna głębokość, tym bardziej złożone będzie Twoje drzewo. Błąd treningu zmniejszy się zejście z kursu, jeśli zwiększymy maksymalna głębokość wartość, ale kiedy nasze dane testowe pojawią się na obrazie, uzyskamy bardzo złą dokładność. Dlatego potrzebujesz wartości, która nie przesadzi, a także nie będzie pasować do naszych danych, a do tego możesz użyć GridSearchCV.

Innym sposobem jest ustawienie minimalnej liczby próbek dla każdego rozlania. Jest oznaczony przez min_samples_split. Tutaj określamy minimalną liczbę próbek wymaganą do rozlania. Na przykład do podjęcia decyzji możemy użyć minimum 10 próbek. Oznacza to, że jeśli węzeł ma mniej niż 10 próbek, to używając tego parametru, możemy zatrzymać dalszy podział tego węzła i uczynić go węzłem liścia.

Istnieje więcej hiperparametrów, takich jak :

min_próbki_liść – reprezentuje minimalną liczbę próbek, które muszą znajdować się w węźle liścia. Im bardziej zwiększasz liczbę, tym większa jest możliwość overfittingu.

maks_funkcje – pomaga nam zdecydować, jaką liczbę cech wziąć pod uwagę przy poszukiwaniu najlepszego podziału.

Aby dowiedzieć się więcej o tych hiperparametrach, możesz to przeczytać tutaj.

Przycinanie

To kolejna metoda, która może nam pomóc w uniknięciu nadmiernego dopasowania. Pomaga w poprawie wydajności drzewa poprzez wycinanie węzłów lub pod-węzłów, które nie są znaczące. Usuwa gałęzie o bardzo małym znaczeniu.

Istnieją głównie 2 sposoby przycinania:

(I) Przycinanie wstępne – możemy wcześniej zaprzestać uprawy drzewa, co oznacza, że ​​możemy przycinać/usuwać/wycinać węzeł, jeśli ma on małe znaczenie podczas wzrostu drzewo.

(II) Po cięciu – kiedyś nasz drzewo jest zbudowane do jego głębokości, możemy zacząć przycinać węzły na podstawie ich znaczenia.

Przypisy

Podsumowując, w tym artykule poznaliśmy drzewa decyzyjne. Na jakiej podstawie drzewo dzieli węzły i jak zapobiegać nadmiernemu dopasowaniu. dlaczego regresja liniowa nie działa w przypadku problemów z klasyfikacją.

W następnym artykule wyjaśnię losowe lasy, które są nową techniką unikania nadmiernego dopasowania.
Aby sprawdzić pełną implementację drzew decyzyjnych, zapoznaj się z moim Github magazyn.

Daj mi znać, jeśli masz jakieś pytania w komentarzach poniżej.

O autorze

Media pokazane w tym artykule nie są własnością Analytics Vidhya i są używane według uznania Autora.

Źródła obrazu

1. Obraz 1 – https://wiki.pathmind.com/decision-tree
2. Obraz 2 – https://wiki.pathmind.com/decision-tree
3. Obraz 3 – www.hackerearth.com
4. Obraz 4 – www.hackerearth.com

Związane z

Źródło: https://www.analyticsvidhya.com/blog/2021/08/decision-tree-algorithm/