10320 IMAGE8 (2)

cechy ilościowo. W zależności od tego czy wspomniany podział oparty jest na wartości jednej cech, czy kilku można wyróżnić;

—    drzewa jednowymiarowe (ang. unb/ariate trees),

—    drzewa wielowymiarowe (ang. multivariate trees), Jednowymiarowe drzewa klasyfikacyjne dzielą zbiory obiektów na

podstawie pojedynczych cech, tj. w oparciu o testy w postaci: x, < C, a wielowymiarowe na podstawie ich kombinacji liniowych: a₀ -f ]T<7, .v₍ > 0.

i

Metody te zostaną omówione dokładniej w dalszej części rozdziału.

Chociaż prace nad algorytmami tworzącymi drzewa klasyfikacyjne rozpoczęły się już w latach sześćdziesiątych, ich rozwój nastąpił dopiero w ostatnich dziesięciu latach. Najbardziej znane z nich zawiera tablica 9.1.

Tablica 9.1. Metody konstruowania drzew klasyfikacyjnych

. Nazwa algorytmu	Rok	Autorzy	Rodzaj drzewa	Sekwencje obiektów
cis '	1966	Hunt. Marin. Słone	binarne	nie
A CLS	1982	Paterson, Niblctt	binarne	nie
ID3 .	1983	Quinlan	dowolne	nie
j CART	1984	Brtiman, Friedman. Olshen, Słone	binarne
(ASSISTANT	198S	Kononenko	binarne	mc
IJD4	1986	Schlimmcr. FIsher	dowolne	tak
1 PIS	1986	Rendell	dowolne	nie
lot	1987	Ouirilan	dowolne	nie
1 GID3	1988	Cbeaz. Fayyad, Darii 1	dowolne	nie
j ms	1989	Ułgoff	dowolne	tak
(LMDT	1991	Brodley, Ułgoff	binarne, wielowymiarowe	nie
ICHAID	1993	SPSS Inc.	dowolne
[IND	1993	Buntine, Ganiana	dowolne	- nie'
jsADT	1993	Heat. Kasif, Salzberg	binarne, wielowymiarowe	nie fll
ISE-LEARN I	1993	Rym on	dowolne	nie • 1
[OC1 .	1994	Munhy	binarne, wielowymiarowe |	_nic,.

Należy zwrócić uwagę, "że niektóre z prezentowanych w tablicy 9.1 algorytmów łączą w sobie kilka rozwiązań, np. IND, którego autorami są Buntine i Caruana (1993) czy SE-LEARN Rymona (1993) zawierają procedury bezpośrednio zaczerpnięte z CLS czy CART, z ich Aukcjami oceny jakości podziału, metodami dychotomizacji cech ilościowych itd.

Inne zaś są ciągle rozwijane przez ich twórców; przykładem jest algorytm C4 Quinlana — efektem jest zmodyfikowana wersja o nazwie C4.8 (Quinlan 1996).

Niektóre z algorytmów wymienionych w tablicy 9.1 są algorytmami sekwencyjnymi, np. DD4 oraz ID5. Oznacza to, że drzewa klasyfikacyjne mogą być tworzone w sytuacji, gdy obiekty w próbie uczącej nie są dostępne jednocześnie, tj. pojawiają się kolejno. Znacznie obniża to koszty gromadzenia i przechowywania danych, wykorzystania pamięci komputera itd.

W przedstawionym zestawieniu znalazł się także algorytm CHAID rozpowszechniany jako jeden z modułów komercyjnego pakietu statystycznego SPSS (Magidson 1993). Jest on rozwinięciem znanych w statystyce od wielu lat metod detekcji interakcji: AID oraz THAID, tworzących pewną odmianę drzew klasyfikacyjnych⁴.

Poza algorytmami przedstawionymi wyżej powstały także komercyjne systemy wykorzystujące drzewa klasyfikacyjne. Pierwszym z nich był ACLS, następnie powstały Expeit-Ease, EX-TRAN itd„ rozpowszechniane pizeż Turing Institutc w Glasgow.

9.3; Proces tworzenia drzewa klasyfikacyjnego

Jak już wspomniano, tworzenie drzew klasyfikacyjnych odbywa się przez rekurencyjny podział zbioru uczącego na podzbiory aż do uzyskania ich jednorodności ze względu na przynależność obiektów do klas. Chodzi przy tym o. to, by takie drzewo było jak najmniejsze (miało minimalną liczbę węzłów), tj. by otrzymane reguły klasyfikacji były jak najprostsze.

Tworzenie drzewa klasyfikacyjnego na podstawie zbioru uczącego, tj. zbioru poprawnie sklasyfikowanych obiektów, odbywa się zgodnie ze strategią wspinaczki. Bardzo ogólna postać algorytmu składa się z następujących kroków:

1.    Mając zbiór obiektów S sprawdź, czy należą one do rej samej klasy. Jeśli tak, to zakończ pracę.

2,    W przeciwnym przypadku rozważ wszystkie możliwe podziały

| Ściśle biorąc, w odniesieniu do nich stosowana jest nazwa drzewa represyjne. Wiole się to | tradycyjną terminologią statystyczną, gdyż podział zbioru obiektów następuje w oparciu o zmienne niezależne, a „klasy” wyznaczają wartości zmiennej zależnej.