Wstęp
Drzewa decyzyjne (DT) to nieparametryczna metoda nadzorowanego uczenia się stosowana do klasyfikacji i regresji. Celem jest stworzenie modelu, który przewiduje wartość zmiennej docelowej poprzez uczenie się prostych reguł decyzyjnych wywnioskowanych z cech danych.
Entropia
Celem treningu jest znalezienie najlepszych podziałów w węzłach, aby znaleźć najbardziej optymalne drzewo. Podziały są dokonywane przy użyciu pewnych kryteriów, takich jak: Entropia.
Istnieje wiele definicji entropii, np.:
-
Entropia odpowiada ilości informacji zawartej w źródle informacji.
-
Entropię można również postrzegać jako losowość lub miarę zaskoczenia w zestawie.
-
Entropia to miara, która mierzy nieprzewidywalność lub zanieczyszczenie systemu.
W drzewach decyzyjnych entropię będziemy uważać za miarę czystości wewnątrz węzła. Celem modelu drzewa decyzyjnego jest zmniejszenie entropii węzłów przy każdym podziale:
Dlatego chcemy zmaksymalizować różnicę między entropią węzła nadrzędnego a entropią węzłów podrzędnych. Ta różnica nazywana jest zyskiem informacji.
Entropię $H$ zbioru $X$ formułuje się matematycznie w następujący sposób:
$$ H(X) = - \sum\limits_{x \in X} p(x) \log p(x) $$
Zysk informacji
Zysk informacji to różnica między entropią węzła nadrzędnego a sumą ważoną entropii węzłów podrzędnych, dlatego można go sformułować w następujący sposób:
$$IG(Y, X) = H(Y) - \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x)$$
$$= H(Y) - \sum_{x \in unique(X)} \frac{X.count(x)}{len(X)} \times H(Y[X == x])$$
Gdzie:
-
$H(.)$ to entropia.
-
$Y$ to populacja przed podziałem, reprezentuje węzeł nadrzędny.
-
$X$ to zmienna, której chcemy użyć do podziału.
-
$x$ to unikalna wartość X.
-
$Y[X==x]$ to lista podzielona zawierająca tylko wartości $x$.
weźmy odpowiedni przykład:
Zamierzamy obliczyć przyrost informacji, dzieląc węzeł nadrzędny, używając wartości X:
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
\
Najpierw obliczamy entropię węzła nadrzędnego:
$$ H(parent) = - P(Y=Blue) \times \log P(Y=Blue) - P(Y=Yellow) \times \log P(Y=Yellow) $$
$$ = - \frac{11}{21} \times \log(\frac{11}{21}) - \frac{10}{21} \times \log(\frac{10}{21}) = 0.3 $$
\
Następnie obliczymy wewnętrzne prawdopodobieństwo każdego węzła podrzędnego po podziale, używając unikalnych wartości X:
$$ unique(X) = [Circle, Square] $$
$$ \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x) = P(Square|X) \times H(Y | X = Square) $$
$$ + P(Circle|X) \times H(Y | X = Circle) $$
$$ = \frac{9}{21} \times H(Y | X = Square) + \frac{12}{21} \times H(Y | X = Circle) $$
Jak na przykład:
-
$H(Y | X = Kwadrat)$ : reprezentuje entropię pierwszego węzła podrzędnego.
-
$H(Y | X = Circle)$ : reprezentuje entropię drugiego węzła podrzędnego.
\
Zaczynamy od pierwszego węzła potomnego:
$$ H(Y | X = Square) = - P(Y=Blue | X = Square) \times \log P(Y=Blue| X = Square) $$
$$ - P(Y=Yellow| X = Square) \times \log P(Y=Yellow| X = Square) $$
$$ = - \frac{7}{9} \times \log\frac{7}{9} - \frac{2}{9} \times \log\frac{2}{9} = 0.23 $$
\
A następnie drugi węzeł potomny:
$$ H(Y | X = Circle) = - P(Y=Blue | X = Circle) \times \log P(Y=Blue| X = Circle) $$
$$ - P(Y=Yellow| X = Circle) \times \log P(Y=Yellow| X = Circle) $$
$$ = - \frac{4}{12} \times \log\frac{4}{12} - \frac{8}{12} \times \log\frac{8}{12} = 0.28 $$
\
Na koniec podstawiamy entropie we wzorze na uzyskanie informacji:
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
$$ = 0.3 - \frac{9}{21} \times 0.23 - \frac{12}{21} \times 0.28 = 0.041 $$
\
\
Jak stwierdzono wcześniej, celem podziału węzła jest maksymalizacja przyrostu informacji, a tym samym zminimalizowanie entropii w powstałym węźle potomnym. Aby to zrobić, musimy spróbować podzielić węzeł na różne zestawy danych wejściowych $ X_1, X_2, \ldots, Xn $ i zachować tylko taki podział, który maksymalizuje przyrost informacji:
$$ X^{*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i) $$
Kiedy przestać dzielić
Podział węzłów w drzewach decyzyjnych jest rekurencyjny, dlatego muszą istnieć kryteria, których możemy użyć, aby zatrzymać dzielenie. Oto niektóre z najczęściej wdrażanych kryteriów:
-
Gdy węzeł jest czysty: H(węzeł) = 0. Dalsze dzielenie węzła nie ma sensu.
-
Maksymalna liczba głębokości: Możemy ustawić maksymalną głębokość, jaką może osiągnąć model, oznacza to, że nawet jeśli węzeł nie jest czysty, podział zostanie zatrzymany.
-
Minimalna liczba próbek na węzeł: Możemy również ustawić minimalną liczbę $N$ próbek na węzeł. Jeśli liczba próbek na węzeł jest równa $N$, przestajemy dzielić, nawet jeśli węzeł nie jest czysty.
Pod koniec uczenia (podziału) każdy węzeł, który opiera się na końcu drzewa decyzyjnego, nazywany jest „liścią”, ponieważ nie jest korzeniem żadnego poddrzewa. Każdy liść będzie reprezentował klasę plonu z największą liczbą próbek.
Wniosek
Drzewo decyzyjne to jeden z najbardziej znanych algorytmów uczenia maszynowego ze względu na swoją wydajność, intuicyjność działania i prostą implementację. Algorytm ten może być dalej używany z numerycznymi zmiennymi niezależnymi (drzewo decyzyjne Gaussa), a także można go rozszerzyć, aby rozwiązywać zadania regresyjne.
