IMAGE3 (2)

klasyfikacyjne, nawet gdyby było bardzo duże, a następnie dokonać jego porządkowania (ang. post-pruning). Polega to na „obcinaniu” pewnych fragmentów drzew (czyli zamianie węzłów wewnętrznych na liście); tak, by wraz ze zmniejszaniem się jednorodności klas nie wzrastał błąd klasyfikacji (rys.. 9,6).

Najprostsze rozwiązanie problemu porządkowania drzewa klasyfikacyjnego polega na redukcji błędu klasyfikacji obiektów. Błąd ten jest liczony jako stosunek liczby obiektów błędnie przydzielonych do zbioru S_t (b,) do liczby wszystkich należących do niego obiektów:

Si    |§§|

I

W tym celu należy zbudować pełne drzewo klasyfikacyjne D, a następnie zastępować jego kolejne fragmenty (drzewa podrzędne) liśćmi, otrzymując sekwencję coraz mniejszych drzew: Z), ,D₂>    gdzie

/),+., uzyskano przez redukcję drzewa D„ a ostatnie z nich, tj. D_s, jest liściem.

. Decyzja o tym, który węzeł w drzewie D₍ zostanie zredukowany do liścia; odbywa się na podstawie zbioru testowego zawierającego obiekty poprawnie sklasyfikowane za pomocą drzewa D. Porównywana jest bowiem wielkość błędu klasyfikacji w Sytuacji, gdy każdy z jego wewnętrznych węzłów jest kolejno redukowany do liścia. Jeśli otrzymane drzewo daje błąd mniejszy lub równy, to staje się drzewem D_l+1.

Chociaż metoda ta generuje sekwencję drzew oraz wymaga utworzenia specjalnego zbioru testowego, ma istotną zaletę! Otóż ostatnie z utworzonych drzew jest najbardziej dokładne, a przy tym jest najmniejszym drzewem o tej dokładności klasyfikacji.

Kolejna metoda została zaproponowana w ramach, algorytmu CART; polega ona na minimalizacji funkcji F, będącej kombinacją liniową kosztu klasyfikacji K oraz złożoności drzewa Z (ang. minimal cost-complexity pruning):

F\D) =    .y.;. |    (9.21)

Porządkowanie drzewa odbywa się w dwóch etapach: najpierw tworzy się sekwencję drzew D_UD₂,    których każde jest oceniane, co

prowadzi do wyboru najlepszego, tj. dającego najmniejszą wartość funkcji kryterium (9,21), Stosując wprowadzony wcześniej zapis, koszt klasyfikacji

liczony jest jako K(Di) — bjn,, a Z(A) jest funkcją liczby liści w drzewie Z(Di) ~ /. Ponieważ w praktyce wartośd<ys= 1, pozostaje jedynie dobrać wartość drugiego parametru.

Jeśli pewien węzeł T drzewa D wraz ze wszystkimi węzłami podrzędnymi (których jest w) zostanie zredukowany do liścia (rys. 9.6), to takie drzewo Lf będzie błędnie klasyfikowało dodatkowo m obiektów, mając jednak o wf,--l węzłów mniej. Z/ dawałoby, taką samą wartość funkcji kryterium (9.21) jak A gdyby:.

;(9.22)

B =    _v

jg§ n(w-1)

Zatem tworząc drzewo A+ x na podstawie A należy zbadać wszystkie d&jya podrzędne wchodzące w skład A>,by znaleźć te z nich, które dają najmniejszą wąrtość^l zostaną one zastąpione liśćmi.

Drugi etap polega na wybraniu takiego drzewa spośród Di, A, które daje najmniejszy błąd klasyfikacji. Jednak, aby ocenić ten błąd, nie można posługiwać srę tym samym zbiorem uczącym, na podstawie którego powstało dr^wp. Zamiast niego należy wykorzystać zbiór- testowy zawierający k obiektów ,do dokonania klasyfikacji za pomocą, każdego drzewa A- Jeśli b oznacza najmniejszą liczbę błędnie sklasyfikowanych obiektów przeż każde drzewo,, to należy wybrać najmniejsze drzewo A> dla którego liczba błędów nie przekracza b-fS(b), gdzie S oznacza błąd standardowy:

,    «<?m

Jak widać, wadami tej metody są: wymaganie posiadania odrębnego zbioru testowego oraz fakt przerywania procedury, gdy zostaje Wybrane najlepsze drzewo-A/®*

■ Metoda pesymistyćżrtd (arig; pessimistic pran/hg)-polega na innym ujęciu błędu klasyfikacji korzystającym z modyfikacji rozkładu dwumianowego (Quinlan 1987). Zgodnie z tą poprawką zamiast h/ we wzorze (9.20); stosuje się. bi+0,5.

Jeżeli T jest fragmentem drzewa D (drzewem podrzędnym), którego / liści reprezentuje zbiory, zawierające-łącznie Sn,- obiektów, <z których Ebi zostało błędnie sklasyfikowanych, to bardziej pesymistyczne założenie głosi, że drzewo T może błędnie sklasyfikować EbrflfiL. obiektów.

179