Zakładam, że entropia została wspomniana w kontekście budowania drzew decyzyjnych .
Aby to zilustrować, wyobraź sobie zadanie uczenia się klasyfikowania imion w grupach mężczyzn i kobiet. Dostajemy listę nazw oznaczonych albo, malbo fchcemy nauczyć się modelu, który pasuje do danych i może być używany do przewidywania płci nowego, niewidocznego imienia.
name gender
----------------- Now we want to predict
Ashley f the gender of "Amro" (my name)
Brian m
Caroline f
David m
Pierwszym krokiem jest podjęcie decyzji, które cechy danych są istotne dla klasy docelowej, którą chcemy przewidzieć. Niektóre przykładowe funkcje to: pierwsza / ostatnia litera, długość, liczba samogłosek, czy kończy się samogłoską itp. Więc po wyodrębnieniu funkcji nasze dane wyglądają następująco:
# name ends-vowel num-vowels length gender
# ------------------------------------------------
Ashley 1 3 6 f
Brian 0 2 5 m
Caroline 1 4 8 f
David 0 2 5 m
Celem jest zbudowanie drzewa decyzyjnego . Przykładem drzewa byłoby:
length<7
| num-vowels<3: male
| num-vowels>=3
| | ends-vowel=1: female
| | ends-vowel=0: male
length>=7
| length=5: male
w zasadzie każdy węzeł reprezentuje test przeprowadzony na jednym atrybucie, a my przechodzimy w lewo lub w prawo w zależności od wyniku testu. Przemierzamy drzewo, aż dotrzemy do węzła liścia zawierającego prognozę klasy ( mlub f)
Więc jeśli uruchomimy nazwę Amro w tym drzewie, zaczniemy od przetestowania „ czy długość <7? ”, A odpowiedź brzmi „ tak” , więc schodzimy w dół tej gałęzi. Po rozgałęzieniu następny test „ jest liczbą samogłosek <3? ” Ponownie ocenia się na prawdę . Prowadzi to do oznaczenia węzła liścia m, a zatem prognoza jest męska ( tak się składa , że drzewo poprawnie przewidziało wynik ).
Drzewo decyzyjne jest zbudowane z góry na dół , ale pytanie brzmi, jak wybrać atrybut do podziału w każdym węźle? Odpowiedź brzmi: znajdź funkcję, która najlepiej dzieli klasę docelową na najczystsze możliwe węzły potomne (tj.: Węzły, które nie zawierają mieszanki zarówno męskiej, jak i żeńskiej, raczej czyste węzły tylko z jedną klasą).
Ta miara czystości nazywana jest informacją . Reprezentuje oczekiwaną ilość informacji, która byłaby potrzebna do określenia, czy nowe wystąpienie (imię) powinno zostać sklasyfikowane jako męskie czy żeńskie, biorąc pod uwagę przykład, który dotarł do węzła. Obliczamy to na podstawie liczby klas męskich i żeńskich w węźle.
Z drugiej strony entropia jest miarą zanieczyszczenia (wręcz przeciwnie). Jest zdefiniowany dla klasy binarnej o wartościacha/bjako:
Entropy = - p(a)*log(p(a)) - p(b)*log(p(b))
Ta binarna funkcja entropii jest przedstawiona na poniższym rysunku (zmienna losowa może przyjąć jedną z dwóch wartości). Osiąga ona maksimum, gdy prawdopodobieństwo jest p=1/2, co oznacza, że p(X=a)=0.5albo w podobny sposób p(X=b)=0.5o 50% / 50% szans na zarówno alub b(niepewność jest maksymalna). Funkcja entropii jest na poziomie zerowym minimum, gdy prawdopodobieństwo jest p=1lub p=0z całkowitą pewnością ( p(X=a)=1lub p(X=a)=0odpowiednio to drugie implikuje p(X=b)=1).
Oczywiście definicję entropii można uogólnić dla dyskretnej zmiennej losowej X o N wynikach (nie tylko dwóch):
( logwe wzorze jest zwykle brany jako logarytm do podstawy 2 )
Wróćmy do naszego zadania klasyfikacji nazw, spójrzmy na przykład. Wyobraź sobie, że w pewnym momencie procesu konstruowania drzewa rozważaliśmy następujący podział:
ends-vowel
[9m,5f] <--- the [..,..] notation represents the class
/ \ distribution of instances that reached a node
=1 =0
------- -------
[3m,4f] [6m,1f]
Jak widać, przed podziałem mieliśmy 9 mężczyzn i 5 kobiet, czyli P(m)=9/14i P(f)=5/14. Zgodnie z definicją entropii:
Entropy_before = - (5/14)*log2(5/14) - (9/14)*log2(9/14) = 0.9403
Następnie porównujemy go z entropią obliczoną po rozważeniu podziału, patrząc na dwie gałęzie podrzędne. W lewej gałęzi ends-vowel=1mamy:
Entropy_left = - (3/7)*log2(3/7) - (4/7)*log2(4/7) = 0.9852
i odpowiednią gałąź ends-vowel=0, mamy:
Entropy_right = - (6/7)*log2(6/7) - (1/7)*log2(1/7) = 0.5917
Łączymy lewą / prawą entropię przy użyciu liczby instancji w dół każdej gałęzi jako współczynnika wagi (7 instancji poszło w lewo, a 7 instancji poszło w prawo) i otrzymujemy ostatnią entropię po podziale:
Entropy_after = 7/14*Entropy_left + 7/14*Entropy_right = 0.7885
Teraz, porównując entropię przed i po podziale, uzyskujemy miarę przyrostu informacji lub ile informacji uzyskaliśmy dzięki podziałowi przy użyciu tej konkretnej funkcji:
Information_Gain = Entropy_before - Entropy_after = 0.1518
Możesz zinterpretować powyższe obliczenia w następujący sposób: wykonując podział za pomocą end-vowelsfunkcji, byliśmy w stanie zmniejszyć niepewność wyniku prognozy pod-drzewa o niewielką ilość 0,1518 (mierzoną w bitach jako jednostki informacji ).
W każdym węźle drzewa obliczenia są wykonywane dla każdej cechy, a cecha o największym zysku informacji jest wybierana do podziału w zachłanny sposób (faworyzując cechy, które dają czyste podziały z niską niepewnością / entropią). Ten proces jest stosowany rekurencyjnie od węzła głównego do dołu i zatrzymuje się, gdy węzeł liścia zawiera instancje o tej samej klasie (nie trzeba go dalej dzielić).
Zwróć uwagę, że pominąłem niektóre szczegóły, które wykraczają poza zakres tego postu, w tym sposób obsługi funkcji numerycznych , brakujących wartości , nadmiernego dopasowania i przycinania drzew itp.