IMAGE6 (2)

wymagające niż funkcje dyskryminacyjne. W rezultacie powstał algorytm CART Breimana, Friedmana, Olshena i Stone'ą(1984). Ponieważ pozwalał on tworzyć jedynie drzewa binarne, i. to przede wszystkim dla obiektów o cechach ilościowych, nie był już później rozwijany.

Drzewo klasyfikacyjne składa się z korzenia, z którego wychodzą co najmniej dwie krawędzie do węzłów leżących na niższym poziomie. Z każdym węzłem związane jest pytanie o wartości cech, jeśli np. pewien obiekt je posiada, to przenosi się go w dół odpowiednią krawędzią. Węzły, z których nie wychodzą już żadne krawędzie, to liście, które reprezentują klasy.

Dwie podane niżej definicje zawierają bardziej formalne ujęcie terminologii dotyczącej drzew klasyfikacyjnych.

Definicja 9.1. Drzewo to graf bez cykli (pętli), w którym istnieje tylko jedna ścieżka między dwoma różnymi węzłami.

Inaczej mówiąc, drzewo jest grafem spójnym³ i bez cykli.- -

Definicja 9.2. Drzewo klasyfikacyjne to drzewo reprezentujące proces podziału zbioru obiektów na jednorodne klasy, jego wewnętrzne węzły opisują sposób dokonania tego podziału (w oparciu o wartości, cech obiektów), a liście odpowiadają klasom, do których należą obiekty. Z kolei krawędzie drzewa reprezentują wartości cech, ha podstawie których dokonano podziału.

Na podstawie drzewa klasyfikacyjnego można łatwo sformułować reguły przynależności obiektów do klas, np. drzewo pokazane na rys. 9.1 reprezentuje dwie takie reguły (po jednej dla każdej klasy):

— w przypadku spadku cen akcji: ^jeżeli stopa procentowa rośnie i zyski przedsiębiorstw spadają, to ceny akcji spadają". źtyrr- w przypadku wzrostu cen akcji: „jeżeli stopa procentowa spada lub jeżeli stopa procentowa rośnie i jednocześnie rosną zyski przedsiębiorstw, to ceny. akcji rosną”.

Z geometrycznego punktu-widzenia drzewa klasyfikacyjne Są podobne do liniowych funkcji dyskryminacyjnych, ponieważ także dzielą-wielowymiarową przestrzeń cech hiperpłaszczyznami po to, by wyodrębnić homogeniczne skupiska obiektów. W zależności od tego, czy drzewa mają

■ SpójnoSć grafu oznacza, to me mottu go przedstawić w postaci sumy grafdw- (Wilson

fpą&y    ^'WmmwttYr^SSSm in riiiT'

• Stopa , procentowa ?

Rys. 9.1. Proste drzewo klasyfikacyjne charakteryzujące sytuację na giełdzie

charakter jedno? ;ęzy wielowymiarowy, hiperpłaszczyzny te są równoległe lub ukośne względem: osi (Gatnar 1996b).

5®iSiRyśunek>^ przedstawia jednowymiarowe, drzewo klasyfikacyjne zbudowane ’dlac<ObiektóW£^    przez dwie cechy ilo

ściowe jc oraz y, Które- należą ido jednej; z trzech klas: a, b, c. Na rysunku zaznaczono także odpowiednie linie oddzielające klasy wiptótrzemicfeh^|l

Jak już wspomniano, drzewo klasyfikacyjne generuje zbiór reguł przynależności obiektów'db każdej z klas. Inaczej mówiąc, na drzewo

Rys. 9.2. Geometryczna interpretacja drzewa klasyfikacyjnego

m 1	b %		•kĄ
■■ni	b b	b
d	1 I b
	b	b	b

165