IMAGE0 (2)

Najczęściej wykorzystywaną w algorytmach tworzących drzewa klasyfikacyjne funkcją zróżnicowania jest funkcja entropii:

IBllfcipBBH H11

Inną jest wskaźnik zróżnicowania Giniego: i-i

■

Ponieważ podział zbioru następuje w oparciu o wartości cech obiektów, należy wybrać tako, która daje najbardziej jednorodne podzbiory. Kryterium wyboru jest więc miarą porównującą stopień zróżnicowania , zbioru przed podziałem, i po nim.

S

Si S₂ ...    Sjn

RyŁ 9S. Poddał zbioru obiektów S

Jeśli cecha X o wartościach w_ltw₂, ..._yw_m dzieli zbiór S na podzbiory (rys. 9.5), z których każdy zawiera odpowiednio n_lt obiektów, to zróżnicowanie tych podzbiorów można oszacować stosując średnią ważoną:

" y-r

gdzie py to wektor prawdopodobieństw w zbiorze Sj. Jakość podziału . dokonanego na podstawie cechy X mierzy się za pomocą funkcji określonej w.definicji 9.4.

Definicja 9.4. Mając daną funkcję zróżnicowania q>, jakość podziafu zbioru S na podzbiory na podstawie wartości cechy X mierzy się za pomocą funkcji:

1(S,X) = <p(p)-z(S,X).

W literaturze można spotkać wiele propozycji różnorodnych miar stosowanych do oceny jakości podziału. Przykładem, miaiy odległości może być reguła podziału na 2 części (ang. twoing rule), wykorzystywana w algorytmie CART (tworzy on drzewa binarne):

Należy zatem wybrać taką cechę X, która daje największą, wartość

(9:6)

gdzie p_A oraz p_B to prawdopodobieństwa, że obiekt należy do podzbioru Są i S_B (S = S_A u 5«); pf,pf -— prawdopodobieństwa należenia obiektów znajdujących się w S_AiS_s do klasy K, (ponieważ ma ona charakter miary odległości; zróżnicowanie mierzy się stosując jej odwrotność).

W literaturze przedmiotu można znaleźć mele propozycji miar jakości podziału, jednak od czasu powstania algorytmu CLS najczęściej stosuje się funkcję entropii (9.3). Wiele eksperymentów porównawczych wskazuje, że jest to miara najbardziej uniwersalna, niezależna od charakteru zmiennych. Mimo to oparte na niej sposoby .oceny jakości podziału także pyły modyfikowane.

j V oryginalnej postaci w algorytmie ID3 stosowano do wyboru cechy d^ydCijąćej opodziale be^óśredńiofunkcję J(S,X), narwaną przyrostem informacji (ang. information gain). Okdżało się jednak, że faworyzuje ona cechy mające diczSejsźy zbiór wartości. Quinlan dokonał więc jej. normalizacji⁶:

(9.7}

uzyskując miarę nazyyżaną przez niego ilorazem przyrostu informacji (ang. gain ‘Vątfof. W formule (9p)^f'E(X) oznacza ilość ipfohnacji, jaką niesie cecha X:

Mjj

M0 = - 5i.P(Wf)log₂ (p(W/)),

(9.8)

gdzie p(wi) to prawdopodobieństwo, że cecha X przyjmuje wartość W/.

* Inne modyfikacje miar opartych na funkcji entropii rozważa także R.L. Maptaras w pracy (1991).-