Zrozumienie przez wdrożenie: drzewo decyzyjne

Zdjęcie autora

Wiele zaawansowanych modeli uczenia maszynowego, takich jak losowe lasy lub algorytmy wzmacniające gradient, takie jak XGBoost, CatBoost lub LightGBM (a nawet autoenkodery!) opierają się na kluczowym wspólnym składniku: drzewo decyzyjne!

Bez zrozumienia drzew decyzyjnych niemożliwe jest również zrozumienie żadnego z wyżej wymienionych zaawansowanych algorytmów workowania lub zwiększania gradientu, co jest hańbą dla każdego naukowca danych! Wyjaśnijmy więc wewnętrzne działanie drzewa decyzyjnego, implementując je w Pythonie.

W tym artykule dowiesz się

• dlaczego i jak drzewo decyzyjne dzieli dane,
• zdobywanie informacji i
• jak zaimplementować drzewa decyzyjne w Pythonie przy użyciu NumPy.

Kod znajdziesz na mój Github.

Drzewa decyzyjne opierają się na przewidywaniach rozsadzający w ułamku sekundy zbiór danych na mniejsze części w sposób rekurencyjny.

Zdjęcie autora

Na powyższym obrazku widać jeden przykład podziału — oryginalny zbiór danych zostaje podzielony na dwie części. W następnym kroku obie te części zostaną ponownie podzielone i tak dalej. Dzieje się tak, dopóki nie zostanie spełnione jakieś kryterium zatrzymania, np.

• jeśli podział powoduje, że część jest pusta
• jeśli została osiągnięta pewna głębokość rekurencji
• jeśli (po poprzednich podziałach) zbiór danych składa się tylko z kilku elementów, dzięki czemu dalsze podziały są niepotrzebne.

Jak znaleźć te podziały? I dlaczego nas to w ogóle obchodzi? Dowiedzmy Się.

Motywacja

Załóżmy, że chcemy rozwiązać a dwójkowy problem klasyfikacji którą tworzymy teraz sami:

import numpy as np
np.random.seed(0) X = np.random.randn(100, 2) # features
y = ((X[:, 0] > 0) * (X[:, 1] < 0)) # labels (0 and 1)

Dane dwuwymiarowe wyglądają następująco:

Zdjęcie autora

Widzimy, że istnieją dwie różne klasy — fioletowa w około 75% i żółta w około 25% przypadków. Jeśli podasz te dane do drzewa decyzyjnego klasyfikator, to drzewo ma początkowo następujące myśli:

„Istnieją dwie różne wytwórnie, co jest dla mnie zbyt chaotyczne. Chcę posprzątać ten bałagan, dzieląc dane na dwie części — te części powinny być czystsze niż poprzednie pełne dane”. — drzewo, które zyskało świadomość

I tak robi drzewo.

Zdjęcie autora

Drzewo decyduje się na podział w przybliżeniu wzdłuż x-oś. Powoduje to, że górna część danych jest teraz idealna czysty, co oznacza, że ​​tylko znajdujesz jedna klasa (w tym przypadku fioletowy).

Jednak dolna część jest nadal niechlujny, nawet bardziej chaotyczny niż wcześniej w pewnym sensie. Stosunek klas wynosił kiedyś około 75:25 w całym zbiorze danych, ale w tej mniejszej części wynosi około 50:50, co jest tak pomieszane, jak to tylko możliwe

 Uwaga: Tutaj nie ma znaczenia, że ​​fiolet i żółty są ładnie rozdzielone na zdjęciu. Tylko surowa ilość różnych etykiet w liczbie dwóch części.

Zdjęcie autora

Mimo to jest to wystarczająco dobre jako pierwszy krok dla drzewa, więc kontynuuje. Chociaż nie spowodowałoby to kolejnego podziału na górze, kleń część, może utworzyć kolejny podział w dolnej części, aby ją wyczyścić.

Zdjęcie autora

Et voilà, każda z trzech oddzielnych części jest całkowicie czysta, ponieważ na części znajdujemy tylko jeden kolor (etykieta).

Teraz naprawdę łatwo jest przewidywać: jeśli pojawi się nowy punkt danych, wystarczy sprawdzić, który z nich trzy części leży i nadaj mu odpowiedni kolor. To działa teraz tak dobrze, ponieważ każda część jest kleń. Łatwe, prawda?

Zdjęcie autora

Dobra, rozmawialiśmy o kleń i niechlujny dane, ale jak dotąd te słowa reprezentują tylko niejasne pojęcie. Aby cokolwiek zaimplementować, musimy znaleźć sposób na zdefiniowanie czystość.

Środki czystości

Załóżmy na przykład, że mamy jakieś etykiety

y_1 = [0, 0, 0, 0, 0, 0, 0, 0] y_2 = [1, 0, 0, 0, 0, 0, 1, 0]
y_3 = [1, 0, 1, 1, 0, 0, 1, 0]

Intuicyjnie, y₁ to najczystszy zestaw etykiet, po którym następuje y₂ , a następnie ty₃. Jak dotąd tak dobrze, ale jak możemy określić liczby na temat tego zachowania? Być może najłatwiejszą rzeczą, która przychodzi na myśl, jest:

Wystarczy policzyć ilość zer i ilość jedynek. Oblicz ich bezwzględną różnicę. Aby było ładniej, znormalizuj go, dzieląc przez długość tablic.

Na przykład, y₂ ma łącznie 8 wpisów — 6 zer i 2 jedynki. Stąd nasze niestandardowe zdefiniowane ocena czystości byłoby |6 – 2| / 8 = 0.5. Łatwo jest obliczyć, że wyniki czystości y₁ i ty₃ wynoszą odpowiednio 1.0 i 0.0. Tutaj możemy zobaczyć ogólny wzór:

Zdjęcie autora

Tutaj, n i n to odpowiednio liczby zer i jedynek, n = n₀ + n₁ jest długością tablicy i p₁ = n₁ / n to udział 1 etykiet.

Problem z tą formułą polega na tym, że tak jest specjalnie dostosowane do przypadku dwóch klas, ale bardzo często interesuje nas klasyfikacja wieloklasowa. Jedną z formuł, która działa całkiem dobrze, jest tzw Miara zanieczyszczenia Giniego:

Zdjęcie autora

lub ogólny przypadek:

Zdjęcie autora

Działa tak dobrze, że scikit-uczy się przyjęła go jako środek domyślny ITS DecisionTreeClassifier class.

Zdjęcie autora

 Uwaga: środki Giniego niechlujstwo zamiast czystości. Przykład: jeśli lista zawiera tylko jedną klasę (= bardzo czyste dane!), to wszystkie wyrazy w sumie są zerowe, stąd suma wynosi zero. W najgorszym przypadku wszystkie klasy pojawiają się dokładnie tyle razy, w którym to przypadku Gini wynosi 1–1/C gdzie C to liczba klas

Teraz, gdy mamy miarę czystości/bałaganu, zobaczmy, jak można jej użyć do znalezienia dobrych podziałów.

Znalezienie podziałów

Istnieje wiele podziałów, z których wybieramy, ale który jest dobry? Użyjmy ponownie naszego początkowego zbioru danych wraz z miarą zanieczyszczenia Giniego.

Zdjęcie autora

Nie będziemy teraz liczyć punktów, ale załóżmy, że 75% to fioletowe, a 25% to żółte. Używając definicji Giniego, zanieczyszczeniem całego zbioru danych jest

Zdjęcie autora

Jeśli podzielimy zestaw danych wzdłuż x-osi, jak poprzednio:

Zdjęcie autora

Połączenia górna część ma zanieczyszczenie Giniego 0.0 i dolnej części

Zdjęcie autora

Średnio te dwie części mają zanieczyszczenie Giniego wynoszące (0.0 + 0.5) / 2 = 0.25, co jest lepsze niż 0.375 całego zbioru danych z poprzedniego okresu. Możemy to również wyrazić w kategoriach tzw zdobywanie informacji:

Zysk informacyjny tego podziału wynosi 0.375 – 0.25 = 0.125.

To proste. Im wyższy zysk informacyjny (tzn. im mniejsze zanieczyszczenie Giniego), tym lepiej.

Uwaga: Innym równie dobrym podziałem początkowym byłby wzdłuż osi y.

Ważną rzeczą, o której należy pamiętać, jest to, że jest to przydatne zważyć zanieczyszczenia Giniego części według rozmiaru części. Załóżmy na przykład, że

• część 1 składa się z 50 punktów danych i ma zanieczyszczenie Giniego 0.0 i
• część 2 składa się z 450 punktów danych i ma zanieczyszczenie Giniego 0.5,

wtedy średnie zanieczyszczenie Giniego nie powinno wynosić (0.0 + 0.5) / 2 = 0.25, ale raczej 50 / (50 + 450) * 0.0 + 450 / (50 + 450) * 0.5 = 0.45.

Dobra, a jak znaleźć najlepszy podział? Prosta, ale otrzeźwiająca odpowiedź brzmi:

Po prostu wypróbuj wszystkie podziały i wybierz ten, który zapewnia największy przyrost informacji. Zasadniczo jest to podejście brutalnej siły.

Mówiąc dokładniej, używane są standardowe drzewa decyzyjne dzieli wzdłuż osi współrzędnych, tj xᵢ = do dla jakiejś funkcji i i próg c. Oznacza to, że

• jedna część podzielonych danych składa się ze wszystkich punktów danych x w xᵢ doi
• druga część wszystkich punktów x w xᵢ ≥ do.

Te proste zasady podziału sprawdziły się w praktyce, ale oczywiście możesz rozszerzyć tę logikę, aby utworzyć inne podziały (tj. ukośne linie, takie jak xᵢ + 2xⱼ = 3, na przykład).

Świetnie, to wszystkie składniki, których teraz potrzebujemy, aby zacząć!

Teraz zaimplementujemy drzewo decyzyjne. Ponieważ składa się z węzłów, zdefiniujmy a Node pierwsza klasa.

from dataclasses import dataclass @dataclass
class Node: feature: int = None # feature for the split value: float = None # split threshold OR final prediction left: np.array = None # store one part of the data right: np.array = None # store the other part of the data

Węzeł zna funkcję, której używa do podziału (feature), jak również wartość podziału (value). value służy również jako miejsce do przechowywania ostatecznej predykcji drzewa decyzyjnego. Ponieważ zbudujemy drzewo binarne, każdy węzeł musi znać swoje lewe i prawe dziecko, zgodnie z zapisem left i right .

Teraz zajmijmy się właściwą implementacją drzewa decyzyjnego. Sprawiam, że jest kompatybilny z scikit-learn, dlatego używam niektórych klas from sklearn.base . Jeśli jeszcze tego nie wiesz, przeczytaj mój artykuł na ten temat jak budować modele zgodne z scikit-learn.

Wdrażajmy!

import numpy as np
from sklearn.base import BaseEstimator, ClassifierMixin class DecisionTreeClassifier(BaseEstimator, ClassifierMixin): def __init__(self): self.root = Node() @staticmethod def _gini(y): """Gini impurity.""" counts = np.bincount(y) p = counts / counts.sum() return (p * (1 - p)).sum() def _split(self, X, y): """Bruteforce search over all features and splitting points.""" best_information_gain = float("-inf") best_feature = None best_split = None for feature in range(X.shape[1]): split_candidates = np.unique(X[:, feature]) for split in split_candidates: left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] information_gain = self._gini(y) - ( len(X_left) / len(X) * self._gini(y_left) + len(X_right) / len(X) * self._gini(y_right) ) if information_gain > best_information_gain: best_information_gain = information_gain best_feature = feature best_split = split return best_feature, best_split def _build_tree(self, X, y): """The heavy lifting.""" feature, split = self._split(X, y) left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] if len(X_left) == 0 or len(X_right) == 0: return Node(value=np.argmax(np.bincount(y))) else: return Node( feature, split, self._build_tree(X_left, y_left), self._build_tree(X_right, y_right), ) def _find_path(self, x, node): """Given a data point x, walk from the root to the corresponding leaf node. Output its value.""" if node.feature == None: return node.value else: if x[node.feature] node.value: return self._find_path(x, node.left) else: return self._find_path(x, node.right) def fit(self, X, y): self.root = self._build_tree(X, y) return self def predict(self, X): return np.array([self._find_path(x, self.root) for x in X])

I to wszystko! Teraz możesz robić wszystkie rzeczy, które kochasz w scikit-learn:

dt = DecisionTreeClassifier().fit(X, y)
print(dt.score(X, y)) # accuracy # Output
# 1.0

Ponieważ drzewo jest nieuregulowane, jest bardzo przepełnione, stąd doskonały wynik pociągu. Dokładność byłaby gorsza w przypadku niewidocznych danych. Możemy również sprawdzić, jak wygląda drzewo poprzez

print(dt.root) # Output (prettified manually):
# Node(
# feature=1,
# value=-0.14963454032767076,
# left=Node(
# feature=0,
# value=0.04575851730144607,
# left=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# ),
# right=Node(
# feature=None,
# value=1,
# left=None,
# right=None
# )
# ),
# right=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# )
# )

Jako obrazek to by było tak:

Zdjęcie autora

W tym artykule widzieliśmy szczegółowo, jak działają drzewa decyzyjne. Zaczęliśmy od kilku niejasnych, ale intuicyjnych pomysłów i przekształciliśmy je w formuły i algorytmy. Ostatecznie udało nam się zaimplementować drzewo decyzyjne od podstaw.

Jednak uwaga: nasze drzewo decyzyjne nie może być jeszcze uregulowane. Zwykle chcielibyśmy określić parametry takie jak

• maksymalna głębokość
• rozmiar liścia
• i minimalny zysk informacji

wśród wielu innych. Na szczęście te rzeczy nie są trudne do wdrożenia, co sprawia, że ​​jest to idealna praca domowa dla Ciebie. Na przykład, jeśli określisz leaf_size=10 jako parametru, wówczas węzły zawierające więcej niż 10 próbek nie powinny być już dzielone. Również ta implementacja jest nieefektywny. Zwykle nie chciałbyś przechowywać części zestawów danych w węzłach, a zamiast tego tylko indeksy. Więc twój (potencjalnie duży) zestaw danych jest w pamięci tylko raz.

Dobrą rzeczą jest to, że możesz teraz zaszaleć z tym szablonem drzewa decyzyjnego. Możesz:

• wdrożyć podziały po przekątnej, tj xᵢ + 2xⱼ = 3 zamiast po prostu xᵢ = 3,
• zmień logikę, która dzieje się wewnątrz liści, tj. możesz przeprowadzić regresję logistyczną w każdym liściu zamiast po prostu głosować większością, co daje ci drzewo liniowe
• zmień procedurę dzielenia, tzn. zamiast brutalnej siły, wypróbuj kilka losowych kombinacji i wybierz najlepszą, która daje klasyfikator pozadrzewny
• i więcej.

 
 
dr Robert Kübler jest analitykiem danych w Publicis Media i autorem w Towards Data Science.

 
Oryginalny. Przesłane za zgodą.
 

• Dystrybucja treści i PR oparta na SEO. Uzyskaj wzmocnienie już dziś.
• Platoblockchain. Web3 Inteligencja Metaverse. Wzmocniona wiedza. Dostęp tutaj.
• Źródło: https://www.kdnuggets.com/2023/02/understanding-implementing-decision-tree.html?utm_source=rss&utm_medium=rss&utm_campaign=understanding-by-implementing-decision-tree