IMAGE7 (2)

takie można patrzeć jak na zbiór reguł klasyfikacji w dysjunkcyjncj postaci normalnej (8.S).

Ścieżka prowadząca od korzenia do liścia reprezentuje koniunkcję testów (kompleks), jeśli zaś do tej samej klasy prowadzi kilka ścieżek, to można je traktować jako składniki alternatywy. Na przykład drzewo na rys. 9.2 zawiera trzy reguły klasyfikacji;

1)    y    < 2,1 ::> a,

2)    (y >3,5 aj: > 2,1)v(y <3,5; aj: < 2,9) ::> b,

HS| <3,5aj::> 2,9 ::> c.

Wykorzystanie utworzonego drzewa do klasyfikacji nowego obiektu polega na tym, że poczynając od korzenia przechodzi się od wierzchołka do wierzchołka wzdłuż krawędzi drzewa odpowiadających wartościom cech klasyfikowanego obiektu. Warto zauważyć, że w związku z tym najczęściej nie jest wymagana znajomość wszystkich cech obiektu!'

Na przykład mając drzewo klasyfikacyjne pokazane na rys. 9.3 oraz wniosek, w którym osoba ubiegająca się o kredyt deklaruje, że ma 30% własnych środków na inwestycję, stałe zatrudnienie oraz miesięczne dochody brutto wynoszące 500 złotych, można określić jego przynależność do klasy odrzucić lub do klasy przyjąć przez wykonanie testów w kolejnych węzłach drzewa. W tym celu należy poruszać się począwszy od korzenia, wzdłuż krawędzi drzewa, aż do jednego z liści.

Ry*- 93. Przykład drzewa klasyfikacyjnego dla wniosków kredytowych

Rozważany wniosek.kredytowy zostanie przydzielony do.klasy odrzucić, ponieważ po sprawdzeniu wartości cechy „własne środki” należy przejść wzdłuż gałęzi ,,< 50%^ do> węzła, w którym sprawdzana jest wartość cechy „stała praca”. Następnie wzdłuż krawędzi „tak" do węda „dochody’’, w którym wynik sprawdzianu prowadzi do liścia odrzucić.

Metody

Wszystkie metody tworzące drzewa klasyfikacyjne mają bardzo podobną konstrukcję. Można powiedzieć, że oparte są na rozwiązaniach, jałde zawierały trzy pierwsze algorytmy: CLŚ, 1D3 oraz CART. Różnice dotyczą postaci funkcji oceniającej jakość podziału, sposobu klasyfikacji obiektów o brakujących wartościach cech itd. .

Metody, w oparciu o które,tworzy się drzewa klasyfikacyjne, można dzielić na kilka sposobów. Najbardziej elementarny jest podział na drzewa binarne i niebiname. Binarne drzewo klasyfikacyjne charakteryzuje .się tym, że z"każdego jego wewnętrznego węzła wychodzą jedynie dwie krawędzie, czyli każdy zbiór obiektów dzieli się na dwa rozłączne podzbiory. Pierwsze algorytmy, tj. CLŚ oraz CART tworzyły wyłącznie drzewa tęgo. typu,

Drzewa binarne najczęściej występują w przypadku klasyfikacji obiektów o cechach ilościowych, gdyż wtedy dokonuje się dyskretyzacji zbioru ich wartości przez jego podział na dwie części. Testy w węzłach drzewa mają postać nierówności < C, gdzie C jest ustaloną liczbą. Również w przypadku, gdy zbiór wartości cech jakościowych składa się z dWÓch elementów, utworzone dla. nich drzewo klasyfikacyjne może być drzewem binarnym. Przykłady drzew binarnych znajdują się na rys. 9.1 oraz 92,

Z kolei drzewa mające przynajmniej jeden węzeł, z którego wychodzą więcej niż dwie krawędzie (czyli zbiór jest dzielony na więcej niż dwa rozłączne podzbiory), są nazywane drzewami niebinamymi. Najczęściej występują one w przypadku klasyfikacji obiektów o cechach jakościowych, które mają odpowiednio liczne zbiory wartości. Przykład takiego drzewa zawiera rys. 9.4 (s; 17Ó).. ;

Kolejne rozróżnienie związane jest z postacią testu w węźle drzewa, w oparciu o który dokonywany jest podział zbioru obiektów. Dotyczy ono jednak jedynie drzew binarnych oraz obiektów charakteryzowanych przez

167