1310109186

dochody

b"—r~"^

piskie wysokie średnie

tak

średnje^

j | student | .tak    ]

J

tak

Rysunek 2: Drzewo decyzyjne dla pojęcia "kupuję komputer".

Zbiór 8 przykładów składa się z 3 przykładów decyzji Tak i 5 na decyzję Nie. Odpowiednie prawdopodobieństwa są równe ptak = 3/8 oraz p_ni_e = 5/8. Wartość entropii związanej z binarną klasyfikacją rozważanego zbioru przykładów jest następująca:

Ent(S) = -(3/8) lg₂(3/8) - (5/8) łg₂(5/8) = 0.531 + 0.424 = 0.955

. Jeśli wybierzemy atrybut dochody do zbudowania korzenia drzewa, a ma on 3 wartości: {niskie,rednie,wysokie}.

Pierwszy podzbiór S_n^_s^_e = {4,5,7} zawiera 3 przykłady, które należą do klasy decyzyjnej Nie.

Drugi podzbiór S£_red_ni_e — {1,2,6,8} zawiera po 2 przykłady z obu klas, podczas, gdy podzbiór S_Wy_SOj^_e = {3} złożony jest z jednego przykłady z klasy Tak.

Wartość entropii warunkowej ze względu na ten atrybut jest następująca: Ent(S\dochody) = § * Ent(S_niskie) + f *Ent(S_średnie) + § * Ent(S_wysokie) = 2„(—0*log₂0—l*log₂ l)+|(-|*log₂|-i*log₂|)+|*(-0*log₂0-l*log₂l) = 0 + 0.5 + 0 = 0.5 Przyrost informacji:

GainInformation{S, dochody) = Ent(S) — Ent{S\dochody) = 0.955 — 0.5 = 0.455.

Wartości miar przyrostu informacji wynikających z zastosowania pozostałych atrybutów do budowy korzenia drzewa są następujące:

Gain(S, student) = 0.348 oraz Gain(S, płeć) = 0.004.

Podzbiory przykładów przypisane gałęziom odpowiadającym wartościom niskie oraz wysokie mają jednoznaczne przydziały do klas decyzyjnych, dlatego te gałęzie można zakończyć liśćmi etykietowanymi odpowiednio klasami tak i nie. W przypadku podzbiorów przykładów S_red_nie = (1, 2,6,8} należy rekurencyjnie wywołać algorytm. Z dwóch rozważanych atrybutów korzystniejszy przyrost informacji pozwala osiągnąć atrybut student, którego wartości jednoznacznie rozdzielają podzbiór przykładów na klasę tak (przykłady 1,6) oraz klasę nie (odpowiednio pozostałe przykłady 2,8) .

3.1.1 Problem z miarą Information Gain

Niestety miara przyrostu informacji (ang. gain) mając dwa atrybuty do wyboru, wybierze ten o większej liczbie wartości. Nie jest to pożądana właściwość,

5