Entropia i przyrost informacji w drzewach decyzyjnych

proste spojrzenie na niektóre kluczowe koncepcje teorii informacji i ich wykorzystanie podczas budowania algorytmu drzewa decyzyjnego.

Jakie kryteria powinien stosować algorytm drzewa decyzyjnego do dzielenia zmiennych / kolumn?

przed zbudowaniem algorytmu drzewa decyzyjnego pierwszym krokiem jest odpowiedź na to pytanie. Przyjrzyjmy się jednemu ze sposobów odpowiedzi na to pytanie. Aby to zrobić, będziemy musieli zrozumieć użycie kilku kluczowych pojęć z teorii informacji.

przyjrzyjmy się tej metodzie, wykonując następujące kroki:

przyjrzyjmy się krótko, czym jest drzewo decyzyjne.
Zdefiniuj i zbadaj wzór na entropię.
omów, czym jest Bit w teorii informacji.
definiuje zysk informacji i wykorzystuje entropię do jej obliczenia.
napisz kilka podstawowych funkcji Pythona używając powyższych pojęć.

w naukach o danych algorytm drzewa decyzyjnego jest nadzorowanym algorytmem uczenia się dla problemów klasyfikacji lub regresji. Naszym ostatecznym celem jest wykorzystanie danych historycznych do przewidywania wyników. W przeciwieństwie do regresji liniowej, drzewa decyzyjne mogą odbierać nieliniowe interakcje między zmiennymi w danych.

spójrzmy na bardzo proste drzewo decyzyjne. Poniżej znajduje się przepływ pracy, który można wykorzystać do podjęcia decyzji o tym, czy zjeść ciasteczko z masłem orzechowym, czy nie.

przykład drzewa decyzyjnego na temat tego, czy aby zjeść ciastko

w tym przykładzie drzewo decyzyjne może stwierdzić, że należy jeść ciastko tylko wtedy, gdy spełnione są określone kryteria. To jest ostateczny cel drzewa decyzyjnego. Chcemy podejmować decyzje (podziały) do czasu spełnienia określonych kryteriów. Po spotkaniu możemy go użyć do klasyfikacji lub przewidywania. Ten przykład jest bardzo podstawowy przy użyciu tylko dwóch zmiennych (alergia, rujnowanie obiadu). Ale jeśli masz zestaw danych z tysiącami zmiennych / kolumn, jak zdecydować, które zmienne / kolumny są najbardziej wydajne do podziału na? Popularnym sposobem rozwiązania tego problemu, zwłaszcza jeśli używa się algorytmu ID3, jest wykorzystanie entropii i przyrostu informacji.

zadanie

powiedzmy, że mamy pewne dane i chcemy je wykorzystać do wykonania quizu online, który przewiduje coś o przyjmującym quiz. Po przyjrzeniu się relacjom w danych zdecydowaliśmy się użyć algorytmu drzewa decyzyjnego. Jeśli nigdy nie byłeś wciągnięty w quiz online, możesz zobaczyć setki przykładów tutaj. Celem quizu będzie odgadnięcie, czy gracz quizu pochodzi z jednego ze środkowych Stanów Ameryki. Pytania w quizie będą się obracać wokół tego, czy lubią określony rodzaj jedzenia, czy nie. Poniżej znajduje się mały fikcyjny zbiór danych z piętnastu wpisów. Każdy wpis zawiera odpowiedzi na serię pytań. Większość pytań dotyczy tego, czy podobał im się określony rodzaj jedzenia, w którym uczestnik odpowiedział (1) na tak lub (0) Na razie. Ostatnia kolumna („midwest?”) jest naszą docelową kolumną, co oznacza, że po zbudowaniu drzewa decyzyjnego jest to klasyfikacja, którą staramy się odgadnąć.

jest dziesięć osób, które mieszkają na Środkowym Zachodzie i pięć osób, które nie. jeśli ktoś miałby cię zapytać, jak mieszana jest kolumna, możesz powiedzieć, że była w pewnym sensie mieszana, z większością(2/3) osób ze Środkowego Zachodu. Entropia daje nam sposób na kwantyfikację odpowiedzi „jakby mieszanej”. Im bardziej mieszane są (1) s I (0)S w kolumnie, tym wyższa Entropia. Jeśli ” midwest?”gdyby równe ilości (1) s I (0)S nasza Entropia byłaby równa 1. Jeśli ” midwest?”składa się tylko z (1)s Entropia będzie równa 0.

do obliczenia entropii możemy użyć następującego wzoru:

przejdźmy przez każdy krok wzoru i Oblicz entropię dla „Midwest?”kolumna.

musimy iterować każdą unikalną wartość w jednej kolumnie i przypisać ją do i. W tym przykładzie mamy 2 przypadki (c)w ” midwest?”kolumna, albo (0) albo (1).
następnie obliczamy prawdopodobieństwo wystąpienia tej wartości w danych. W przypadku (1) prawdopodobieństwo wynosi 10/15. W przypadku (0) prawdopodobieństwo wynosi 5/15.
bierzemy prawdopodobieństwo każdego przypadku i mnożymy je przez logarytm o podstawie 2 prawdopodobieństwa. 2 jest najczęstszą podstawą, ponieważ Entropia jest mierzona w bitach (więcej o tym później). Pełne wyjaśnienie dlaczego 2 jest używane jest poza zakresem tego postu, ale użytkownik na Stack exchange oferuje dobre wyjaśnienie. W przypadku(1) otrzymujemy 10/15*log2(10/15). W przypadku (0) otrzymujemy 5/15 * log2(5/15).
następnie bierzemy nasz produkt z każdego przypadku powyżej i sumujemy go razem. W tym przykładzie, 10/15*log2(10/15) + 5/15 * log2(5/15).
na koniec zanegujemy sumę całkowitą z góry, — (10/15*log2(10/15) + 5/15*log2(5/15)).

Po zebraniu wszystkich kroków otrzymujemy poniżej:

nasza ostateczna Entropia jest .918278. Co to naprawdę znaczy?

teoria informacji i trochę informacji

idąc dalej ważne będzie zrozumienie pojęcia bit. W teorii informacji bit jest uważany za liczbę binarną reprezentującą 0 dla braku informacji i 1 dla pełnego bitu informacji. Możemy przedstawić bit informacji jako liczbę binarną, ponieważ ma ona wartość (1) lub (0). Załóżmy, że istnieje równe prawdopodobieństwo, że jutro będzie padać (1) lub że nie będzie padać(0). Jeśli powiem ci, że jutro będzie padać, dam ci jedną informację.

entropię możemy też traktować jako informację. Załóżmy, że mamy załadowaną sześcioboczną matrycę, która zawsze ląduje na (3). Za każdym razem, gdy toczymy kostkę, z góry wiemy, że wynikiem będzie (3). Nie otrzymujemy nowych informacji, obracając matrycę, więc Entropia wynosi 0. Z drugiej strony, jeśli kość jest daleko i rzucamy (3), to była 1/6 szansy na toczenie (3). Teraz zdobyliśmy informacje. Tak więc obracanie matrycy daje nam jedną informację — po której stronie wylądował numer.

aby głębiej zagłębić się w koncepcję informacji, możesz przeczytać więcej tutaj.

otrzymujemy mniej niż jeden ” bit ” informacji — tylko .918278-bo jest więcej (1) s w „midwest?”kolumna niż (0) s. oznacza to, że gdybyśmy przewidywali nową wartość, moglibyśmy odgadnąć, że odpowiedź jest (1) i częściej mieć rację niż błąd (ponieważ istnieje prawdopodobieństwo 2/3 odpowiedzi jako 1). Dzięki tej wiedzy uzyskujemy mniej niż pełny ” bit ” informacji, gdy obserwujemy nową wartość.

Korzystanie z entropii do podejmowania decyzji

naszym celem jest znalezienie najlepszych zmiennych / kolumn do podziału podczas budowania drzewa decyzyjnego. Ostatecznie chcemy dzielić zmienne / kolumny, aż nasza mieszana kolumna docelowa nie będzie już mieszana.

przyjrzyjmy się na przykład entropii „midwest?”kolumna po podzieleniu zbioru danych na” potato_salad?”kolumna.

POWYŻEJ nasz zbiór danych jest podzielony na dwie sekcje. Po lewej stronie wszyscy, którzy lubią sałatkę ziemniaczaną. Po prawej stronie wszyscy, którzy nie. wypełniamy fokus na lewej stronie, która ma teraz siedem osób ze Środkowego Zachodu i dwie osoby, które nie są. używając wzoru na entropię w lewej kolumnie podziału Środkowego Zachodu, Nowa Entropia jest .764204. To jest świetne! Naszym celem jest obniżenie entropii i wyszliśmy z .918278 do764204. Ale nie możemy na tym poprzestać, jeśli spojrzymy na prawą kolumnę, nasza Entropia poszła w górę, ponieważ są równe (1) s I (0)s. potrzebujemy sposobu, aby zobaczyć, jak zmienia się Entropia po obu stronach podziału. Formuła pozyskiwania informacji to zrobi. Daje nam to liczbę, aby określić, ile bitów informacji uzyskaliśmy za każdym razem, gdy dzielimy nasze dane.

wzmocnienie informacji

wcześniej ustaliliśmy, że chcemy podziałów, które obniżają entropię naszej docelowej kolumny. Kiedy podzielimy się na ” potato_salad?”widzieliśmy tę entropię na Środkowym Zachodzie?”zszedł na lewą stronę. Teraz musimy zrozumieć całkowitą entropię obniżoną, gdy spojrzymy na obie strony podziału. Spójrzmy na zysk informacji.

zysk informacji będzie korzystał z następującego wzoru:

podzielmy się tym, co tu się dzieje.

wrócimy do naszego ” potato_salad?”przykład. Zmienne w powyższym wzorze będą reprezentować:

t = Target, nasz „midwest?”column
a = the variable ( column) we are testing, „potato_salad?”
v = każda wartość w a, każda wartość w „ziemnio_salad?”kolumna

najpierw obliczymy entropię pierwotną dla (T) przed podziałem,.918278
następnie dla każdej unikalnej wartości (v) w zmiennej (a) obliczamy liczbę wierszy, w których (A) przyjmuje wartość (v) i dzielimy ją przez całkowitą liczbę wierszy. Za ” potato_salad?”kolumna otrzymujemy 9/15 dla unikalnej wartości (1) i 6/15 dla unikalnej wartości (0).
następnie mnożymy wyniki przez entropię wierszy, w których (A) jest (v). Dla lewego podziału (split na 1 dla ” potato_salad?”) dostajemy 9/15 * .764204. Dla prawej strony podziału (split na 0 dla ” potato_salad?”) otrzymujemy 6/15 * 1 .
dodajemy wszystkie te podzbiory razem, 9/14*.764204 + 6/15 = .8585224.

5. Następnie odejmujemy od ogólnej entropii, aby uzyskać przyrost informacji .918278 -.8585224 = .059754

059754. Co nam to mówi?

oto alternatywne Wyjaśnienie. Znajdujemy entropię każdego zbioru po podziale, ważąc ją przez liczbę elementów w każdym podziale, a następnie odejmując od bieżącej entropii. Jeśli wynik jest dodatni, obniżyliśmy entropię z naszym podziałem. Im wyższy wynik, tym bardziej obniżyliśmy entropię.

kończymy z059754 zyskowo059754 bity informacji dzieląc nasz zbiór danych na ” potato_salad?”zmienna / kolumna. Nasz przyrost informacji jest niski, ale nadal jest dodatni, ponieważ obniżyliśmy entropię po lewej stronie podziału.

teraz musimy powtórzyć ten proces dla każdej kolumny, której używamy. Zamiast robić to ręcznie, napiszmy trochę kodu Pythona.

Podsumowując to wszystko za pomocą Pythona

teraz, gdy rozumiemy zysk informacji, potrzebujemy sposobu na powtórzenie tego procesu, aby znaleźć zmienną / kolumnę o największym zysku informacji. Aby to zrobić, możemy stworzyć kilka prostych funkcji w Pythonie.

Importowanie danych

zamieńmy naszą powyższą tabelę w ramkę danych za pomocą biblioteki Python pandas. Zaimportujemy pandy i użyjemy funkcji read_csv () do utworzenia ramki danych o nazwie „midwest”.

import pandas as pd
midwest = pd.read_csv('midwes.csv')

funkcja Pythona dla entropii

dla tej funkcji potrzebujemy biblioteki NumPy do użycia funkcji bincount() i modułu matematycznego do użycia funkcji log ().

import numpy
import math

następnie zdefiniujemy naszą funkcję jednym parametrem. Podany argument będzie szeregiem, listą lub tablicą NumPy, w której próbujemy obliczyć entropię.

def calc_entropy(column):

będziemy musieli znaleźć procent każdego przypadku w kolumnie. Możemy użyć numpy.funkcja bincount () do tego celu. Zwracaną wartością jest tablica NumPy, która będzie przechowywać liczbę każdej unikalnej wartości z kolumny, która została przekazana jako argument.

counts = numpy.bincount(column)

będziemy przechowywać prawdopodobieństwo każdej unikalnej wartości dzieląc tablicę „counts” przez długość kolumny.

probabilities = counts / len(column)

możemy wtedy zainicjalizować zmienną o nazwie „Entropia” i ustawić ją na 0.

entropy = 0

następnie możemy użyć „pętli for”, aby przejrzeć każde Prawdopodobieństwo z naszej tablicy prawdopodobieństwa i pomnożyć je przez logarytm o podstawie 2 prawdopodobieństwa za pomocą matematyki.funkcja log (). Następnie dodaj każdy przypadek do naszej przechowywanej zmiennej entropii. * upewnij się, że Twoje prawdopodobieństwo jest większe niż 0, w przeciwnym razie log(0) zwróci undefined

for prob in probabilities:
if prob > 0:
endtropy += prob * math.log(prob,2)

na koniec zwrócimy naszą negowaną zmienną entropii.

return -entropy

wszyscy razem:

świetnie! Teraz możemy zbudować funkcję do obliczania zysku informacji.

funkcja Pythona do pozyskiwania informacji

musimy zdefiniować funkcję, która będzie miała trzy parametry, jeden dla całego zbioru danych, jeden dla nazwy kolumny, na której chcemy się podzielić, i jeden dla nazwy naszej docelowej kolumny.

def calc_information_gain(data, split_name, target_name):

następnie możemy użyć funkcji entropii z poprzedniej, aby obliczyć pierwotną entropię naszej docelowej kolumny.

orginal_entropy = calc_entropy(data)

teraz musimy podzielić naszą kolumnę.

*w tym przykładzie użyjemy tylko zmiennych/kolumn z dwoma unikalnymi. Jeśli chcesz podzielić na zmienną / kolumnę, taką jak „wiek”, istnieje kilka sposobów, aby to zrobić. Jednym ze sposobów jest podział na każdą unikalną wartość. Innym sposobem jest uproszczenie obliczania zysku z informacji i uproszczenie podziału, nie dzieląc dla każdej unikalnej wartości. Zamiast tego można znaleźć medianę dla zmiennej/coumn dzielonej na. Wszelkie wiersze, w których wartość zmiennej jest poniżej mediany, trafią do lewej gałęzi, a pozostałe wiersze do prawej gałęzi. Aby obliczyć zysk informacji, będziemy musieli obliczyć entropie tylko dla dwóch podzbiorów. Nie będziemy przechodzić przez tę metodę, ale po dokonaniu podziału na medianę reszta kroków będzie taka sama, jak opisano poniżej.

ponieważ kolumny, z którymi pracujemy, mają tylko dwie unikalne wartości, zrobimy lewy split i prawy split.

zaczniemy od użycia pand.Seria.unique() aby dać nam tablicę unikalnych wartości w kolumnie

values = data.unique()

następnie utworzymy lewy i prawy podział za pomocą „values”.

left_split = data == values]
right_split = data == values]

teraz możemy zainicjować zmienną, aby odjąć od naszej pierwotnej entropii.

to_subtract = 0

następnie przejdziemy przez każdy podzbiór utworzony przez nasz podział, obliczymy prawdopodobieństwo podzbioru, a następnie dodamy iloczyn prawdopodobieństwa i entropii kolumny docelowej podzbiorów.

for subset in :
prob = (subset.shape / data.shape)
to_subtract += prob * calc_entropy(subset)

wreszcie możemy zwrócić różnicę to_subract odejmowaną od pierwotnej entropii.

return original_entropy - to_subtract

cała funkcja znajduje się poniżej.

funkcja Pythona dla najwyższego zysku informacji

nasza końcowa funkcja będzie taka, która zwróci nazwę zmiennej/kolumny o najwyższym zysku informacji.

jak wspomniano wcześniej, w tym przykładzie używamy tylko kolumn z dwiema unikalnymi wartościami. Będziemy przechowywać te nazwy kolumn na liście do użycia w funkcji. Aby przejść do rzeczy, kodujemy to w tym przykładzie, ale w dużym zbiorze danych najlepiej byłoby napisać kod, aby zbudować tę listę dynamicznie w oparciu o kryteria, których używamy do wyboru kolumn.

columns =

zawińmy ostatni krok w funkcję, abyśmy mogli go ponownie użyć w razie potrzeby. Będzie miał JEDEN parametr, listę kolumn, dla których chcemy znaleźć najwyższy zysk informacji.

def highest_info_gain(columns):

wprowadzimy pusty słownik do przechowywania naszych informacji.

information_gains = {}

a następnie możemy iterować przez listę kolumn i zapisać wynik w naszym słowniku information_gains.

for col in columns:
information_gain = calc_information_gain(midwest, col, 'midwest?)
information_gains = information_gain

wreszcie możemy zwrócić klucz o najwyższej wartości w naszym słowniku.

return max(information_gains, key=information_gains.get)

wszyscy razem:

Po wykonaniu naszej ostatecznej funkcji

print(highest_info_gain(midwest, columns, 'midwest?'))
//sushi

widzimy zmienną/kolumnę z największy przyrost informacji to ” sushi?’.poniżej przedstawiamy podział na sushi:

podział naszego zbioru danych na kolumnę sushi

Nasz lewy podział ma dwie osoby na sześć ze Środkowego Zachodu. Prawy podział ma 8 z 9 osób ze Środkowego Zachodu. To był skuteczny podział i obniżył naszą entropię po obu stronach. Gdybyśmy mieli kontynuować, użylibyśmy rekurencji do dzielenia każdego podziału z celem zakończenia każdej gałęzi z entropią zera.

wnioski

drzewa decyzyjne mogą być użytecznym algorytmem uczenia maszynowego do pobierania nieliniowych interakcji między zmiennymi w danych. W tym przykładzie przyjrzeliśmy się początkowym etapom algorytmu klasyfikacji drzewa decyzyjnego. Następnie przyjrzeliśmy się trzem pojęciom teorii informacji: entropii, bitu i zysku informacji. Korzystając z tych koncepcji byliśmy w stanie zbudować kilka funkcji w Pythonie, aby zdecydować, które zmienne/kolumny są najbardziej wydajne do podziału. Z mocnym zrozumieniem tych koncepcji, możemy iść do przodu, aby zbudować drzewo decyzyjne.