IMAGE5 (2)

9.6.2. CART

Algorytm CART (ang. Classification and Regression Treeś) powstał na początku lat osiemdziesiątych, w wyniku pracy zespołu statystyków nad metodami klasyfikacji wzorcowej, które byłyby bardziej odporne niż klasyczne metody analizy dyskryminacyjnej (Breiman i in. 1984). Także on tworzy binarne drzewa klasyfikacyjne, opierając się jednak na innych niż CLS podstawach teoretycznych.

Działanie algorytmu CART polega na rekurencyjnym podziale obiektów z próby uczącej na dwa podzbiory na podstawie pytać typu „czy o e AT, gdzie A cz S. Jeśli odpowiedź na nie brzmi „tak”, to obiekty je spełniające tworzą jeden podzbiór, gdy zaś „nie”, to drugi. Można sformułować trzy zasady, którym podlega konstruowanie testu dla węzła drzewa:,

•    Każdy test opiera się na jednej zmiennej.

•    Dla cechy reprezentowanej przez zmienną ilościową x rozważane są wszystkie możliwe testy w postaci:

gdzie Ce R.

• Dla cechy.jakościowej y o wartościach należących do zbioru A — {a,. a₂,...,a_t) test ma postać:

f_r*czy y.e B,

gdzie B oznacza wszystkie podzbiory zbioru A.

Na przykład jeśli x_t oraz jr₃ są zmiennymi ilościowymi, a x₂‘ jest zmienną jakościową o wartościach ze zbioru {a_ti a₂,03 )> można rozważać następujący- zbiór możliwych testów:

czy *1 6    i

czy

Ich liczba jest śkodczona, gdyż np. w przypadku zmiennej ilościowej * w zbiorze uczącym znajduje-się najwyżej ir jej wartości (tyle jest obiektów): Istnieje zatem najwyźej n—1 różnych podziałów zbioru jej wartości na dwa przedziały-przez nierówność* < Ci gdzie C jest ustalana jako liczba, znajdująca się między parami kolejnych wartości X np.

C = (X¹/ -ł-X/+1 )/2» Z kolei dla zmiennej jakościowej y, która przyjmuje k

wartości, możliwych jest 2*^{- ł} - l różnych podziałów zbioru jej wartości na dwa podzbiory.

Problemzakoóczenia podziału |||c|u obiektów, tj. porządkowania wstępnego, został rozwiązany przez zastosowanie reguły heurystycznej, mówiącej ó tym, że' należy¹ zaniechać^J podziału, gdy nie następuje znaczący spadek stopnia zróżnicowania obiektów w badanym zbiorze,

9.63. ID3 oraz C4

Najbardziej znana i wielokrotnie omawiana metoda budowy , drzew klasyfikacyjnych to ID3 (ang. Induction ofDecision Trees), która powstała na przełomie lat siedemdziesiątych i osiemdziesiątych (Quinlan 1983). Inspirowana była systemem CLS oraz rezultatami prać nad indukcyjnymi metodami^: uczenia się; do wyboru cechy decydującej o podziale zbioru obiektów wykorzystano w niej funkcję entropii (9.3). r.\ W pierwszej wersji.‘algorytm ^:ID3 akceptował jedynie dwie klasy obiektów, tj.; zbiory zawierające przykłady. pozytywne i., przykłady negatywne (kontrprzykłady); Kolejne modyfikacje usuńmy jednak to ograniczenie, a-jego następca — algorytm G4 dodatkowo .umożliwia klasyfikację obiektów#: których cechy reprezentowane.- są za pomocą znuennych‘iloŚdowych'CQuihlan^l993)r: ••

Procedurat\$ytę)ru^; cechy będącej podstawą^spodziału wymaga wielo-; krotnego .przeszukiwania zbioru uczącego*, który musiałby mieścić się w pamięci ^operacyjnej ^komputera; ₅ Uniemożliwiałoby -[figi stosowanie ąlgorytmu^3|do większych zbiorów obiektów. Aby to przezwyciężyć, Quinlan zastosował tzw. okno; polega, tń na losowym wyborze pewnego podzbioru obiektów i zastosowaniu do niego algorytmu ID3. Utworzone w ten spośób.dtzewo jest.następmemodyfikówane. przez dodanie, do okna obiektów, których.skonstruowane drzewo; nie-klasyfikuje-:

Algorytm JD3 doskonale radzi sobie z obiektami symbolicznymi, ale w. praktyce często występująs sytuacje^gdy przedmiotem klasyfikacji są obiekty o cechach reprezentowanych także przez zmienne ilościowe. Jego następca, algorytm C4, stosuje testy w postaci x, $ C lub-Tj > C, których yitynikiem są dwa podzbiory: Oznacza: to dyskretyzację cechy ilościowej, ćdf odbywa się jednocześnie-z obliczaniem^: wartości funkcji jakości

Należy znaleźć taką wartość C, byfunkcja/(S, X) dawała największą wartość. Najpierw wartości analizowanej cechy ilościowej dla wszystkimi

183