IMAGE6 (2)

xi >c

xi < ę

^    : ■;    ^!*f«i:

Rys. 918; Dyskreiyzacja cechy ilościowej X w algorytmie C4

obiektów w zbiorze uczącym porządkuje się rosnąco (rys. 9.8), a następnie sprawdza wartość funkcji jakości podziału J(S_tX) dla wszystkich możliwych podziałów tego przedziału na dwie części. Wybiera się ten, który daje największą wartość J(S,X).

9.6.4. ASSISTANT

Algorytm ASSISTANT powstał na podstawie XD3; stosuje się w nim ciekawy mechanizm dychotomizacji cech jakościowych, który powodował, że budowane drzewa klasyfikacyjne były mniejsze, przy podobnym poziomie błędu klasyfikacji, jak w przypadku algorytmu Quinlana (Cestnik i im 1987).

WJD3 dokonuje się podziału zbioru obiektów w oparciu o pewną cechę jakościową i tworzy tyle podzbiorów, ile wartości ma wybrana cecha; Natomiast w ASSISTANT łączy się wszystkie wartości cechy w dwa takie zbiory, które dają największą wartość funkcji jakości podziału

Metodę tę przejął także. Quinlan, którego algorytm C4 może dokonać takiej operacji na żądanie użytkownika¹.

9.6.5. CHAID

Metoda detekcji interakcji CHAID (ang. Chisquared Automatic Interaction Detector) tworzy drzewa klasyfikacyjne w nieco inny sposób niż omawiane wyżej metody. Algorytm ten powstał na gruncie statystyki, a więc bardziej odpowiednie byłoby nazywanie drzew klasyfikacyjnych drzewami regresyjnymi, gdyż rozważany jest model y — f(x_t ,x₂,... ,x„) ’_y w którym y jest zmienną zależną (objaśnianą), natomiast xi,x₂, ...,x„ są zmiennymi niezależnymi (objaśniającymi). Wartości cechy, jakościowej y wyznaczają klasy, do których należą obiekty ze zbioru uczącego (Magidson 1993).

Najpierw dla każdej ze zmiennych objaśniających buduje się tablicę kontyngencji ze zmienną objaśnianą y r oblicza wartość statystyki z¹. Następnie w oparciu o tę statystykę łączy się wartości„ cechyM\które nie wykazują istotnej statystycznie, różnicy, przy czym realizowane jest to inaczej dla cech nominalnych, a inaczej dla porządkowych Wyboru cechy X/ decydującej o podziale zbioru obiektów na podzbiory dokonuje się także w oparciu o statystykę jt², .czyli chodzi' p>:(ęięecjię, która jest. najbardziej związana ze zmienną objaśnianą y. Ściśle biorąc, chodzi o cechę, dla której prawdopodobieństwo tego, że obserwowany związek między nią a y wystąpiłby wtedy, gdy. obie cechy .byłyby statystycznie niezależne, jest najmniejsze. Jako wartość graniczną tego prawdopodobieństwa przyjmuje się d = 0,05⁸.

9.6.Ó. Pozostałe metody

System IND, którego autorami są W. Buntine i R. Caruana, łączy w sobie Mika algorytmów budowy drzew klasyfikacyjnych (Buntine, Caruana 1993). Przede wszystkim są to: CART, ID3, C4 oraz metody: bayesowska, MML Wallace’a i Patricka², a także metoda opaim uu grafach,decyzyjnych 01iviera i Wallace’a. IND składa się z czterech modułów: manipulacji danymi² tworzenia dntew klasyfikacyjnych, testowania ich oraz graficznej

.^-INieco inne. rozwiązanie zaproponował R. Rymon w ramach swojego algorytmu- SErLeam. (ang. ■ Set-Enumeration) (Rymon 1993):-' Jest: on pewnego rodzaju uogólnieniem przedstawionych wcześniej /algorytmów budujących drzewa klasyfikacyjne² tzn. test- dzielący zbiór obiektów w pewnym węźle drzewa jest oparty nie na jednej cesze, lecz na kilku. W efekcie, ten. sam obiekt może znaleźć się w kilku liściach (klasach) drzewa jednocześnie. Tworzy się więc klasy nierozłączne.

W pewnym sensie: następcą algotytmn. ID3 jest ID£, stworzony przez J.C. Schlimmera i D.Fishera (1986). Dokonuje on analizy rozkładu wartości cech dla każdego z • węzłów drzewa. Następnie stosując miarę entropii z teorii informacji wybiera „najlepszą” cechę i dokonuje względem niej podziwu obiektów w węźle. Z kolei jeśli jakiś węzeł w wyniku podziału utracił wysoką wartość informaęj^ną, cały fragment drzewa w nim

185

1

Dokładniej chodzi o program C4.5. w którym procedura ta jest realizowana po włączenia jednej z opcji (Qoinlan 1993)..

2

Algorytm ,CHAID realizowany w ramach pakietu statystycznego SPSS stosuje