IMAGE9 (2)

S_M- tak, by były one jak najbardziej

zbioru S na podzbiory St,S₂ jednorodne.

3.    Dokonaj oceny jakości każdego z tych podziałów zgodnie z przyjętym kryterium i wybierz najlepszy z nieb.

4.    Podziel zbiór S w wybrany sposób.

5.    Wykonaj kroki 1-4 rekurencyjnie dla każdego z podzbiorów. Graficzną ilustracje tego algorytmu przedstawia rys. 9.4.

Dokonywany w czwartym kroku algorytmu podział następuje w oparciu o charakterystykę obiektów, czyli wartości ich cech. Cecha będąca podstawą podziału nie może byó wybierana losowo, gdyż w takim przypadku drzewo klasyfikacyjne mogłoby mieć liczbę liści równą liczbie obiektów. Stąd do tego celu stosowane są różne miary, min. statystyczne, metody oparte na teorii informacji.itd. Wszystkie opierają się na założeniu; że istnieje związek między wartościami cech obiektów a ich przynależnością do określonej klasy.

Ponieważ budowane drzewo powinno byó jak najmniejsze, większośó algorytmów dodatkowo dokonuje porządkowania drzewa (ang. tree pruning), polegającego na usuwaniu tych jego fragmentów, które mają niewielkie znaczenie dla jakości rezultatów klasyfikacji.

Każdy algorytm tworzący drzewa klasyfikacyjne musi zatem rozwiązać trzy problemy:

Jak wybrać jedną lub kilka cech, w oparciu o które nastąpi podział zbioru obiektów?

—    Kiedy zakończyć podział powstałego podzbioru obiektów?

—    W jaki sposób przydzielić obiekty znajdujące się w liściu drzewa do pewnej klasy?

9.4. Miary jakości podziału

Jak już wielokrotnie wspominano, efektywność algorytmu tworzenia drzew klasyfikacyjnych zależy od [wyboru sposobu podziału zbiorów obiektów w węzłach drzewa, tj, pojedynczych cech lub ich kombinacji liniowych. Wybór ten jest dokonywany w oparciu o pewną miarę jakości podziału.

& ',*W praktyce stosuje się w tym celu albo miary jednorodności, albo miary zróżnicowania^$ podzbiorów uzyskanych w wyniku podziału. W pierwszym przypadku należy wybrać podział, który maksymalizuje wartość stosowanej miary, w drugim — podział, który minimalizuje jej wartpSć. Ponieważ miary jednorodności można traktować jako odwrotność miar oceniających heterogeniczność podzbiorów, wystarczy dokładniej omówić tylkó tę drugą grupę.

Niech S będzie zbiorem uczącym zawierającym obiekty o_L, oj,.... o„, które należą do jednej z klas , K¹*, -przy pzym liczebność .klasy jest oznaczana jako l_t. Dodatkowo dla każdego, zbioru obiektów można zbudować wektor prawdopodobieństwa przynależności do klas w postaci:

gdzie 2,’ pt = .j^.ljdjożną zatem pg^ić^eći że,pewien zbiór obiektów

jest jednorodny, jeśli-Br = 1, ...,lępi = 1. Natomiast jego maksymalne zróżnicowaniey^śtępuj^wtćdy.lgdy Vi =» 1, ...,k'p, = 1/n.

Definicja 9&L:)Runkcjdpf't

(9.2)

<p: [0,1]* ~>K

taka, te ę>(p) > 0 dla każdego wektora p, nazywa się funkcją zrói-nicowania, jeśli ma następujące własności: w lilsp/pł i= max    ...kpi =» jljgall

' 2). ę>(p) = min =Śjw/

₄ 3} jest funkcją    ;•

4) jest rótniczkowalna w całej dziedzinie,

^s W tekstach w języku angielskim występuje pojecie Impurity measures, etyli miary zanieczyszczenia.

171