64384 IMAGE4 (2)

Zatem gdy T zostanie zastąpione liściem, to będzie dokonywać błędnej klasyfikacji m obiektów ze zbioru uczącego. Omawiana metoda redukuje drzewo podrzędne do Uścia, gdy spełniony jest warunek:

jg¹' ^JJggg

Metoda ta sprawdza wszystkie drzewa podrzędne, ale nic podlegają terali elementy tych z nich, które są usuwane. Zaletą tej metody jest szybkość wynikająca z faktu, że każdy fragment drzewa 7”jest sprawdzany najwyżej raz. Nie wymaga ona także oddzielnego zbioru testowego, jak w przypadku poprzednich metod.

Na koniec należy wspomnieć o tym,' że większość omawianych tu metod może także klasyfikować obiekty o nieznanych wartościach pewnych cech (przypadek, gdy dysponuje się danymi niepełnymi). W takiej sytuacji stosuje się zwykle jedno z trzech rozwiązali:

- — brak obserwacji traktuje się jako jedną z dozwolonych wartości, np. „brak”,

— zastępuje się brakującą wartość cechy jakąś inną, np. najczęstszą. Kg przydziela się takiej cesze kolejne, zaobserwowane u innych obiektów, wartości podczas obliczania funkcji jakości podziału J(S, X).

9.6. Charakterystyka wybranych metod

Najważniejsze dla rozwoju metod klasyfikacji wzorcowej opartej na drzewach klasyfikacyjnych były trzy algorytmy: CLS, CART oraz Id3i Z tego powodu warto je nieco bliżej przedstawić. Duże znaczenie, miał także algorytm ASSISTANT, którego niektóre rozwiązania przejęły inne algorytmy, np, C4 Quinlana. Z kolei CHAID jest przykładem nieco innego podejścia do drzew klasyfikacyjnych; które powstało na gruncie Statystyki.

9.d.L pŁS .

W wyniku prowadzonych w iatach sześćdziesiątych prac nad indukcyjnymi metodami tworzenia pojęć powstał algorytm CLS (ang, Concept Leaming System) (Hunt i in. 1966). Opiera się'On' na założeniu, że klasyfikowane

obiekty -mogą należeć do jednej % dwóch klas: przykładów pozytywnych (AT*) i przykładów negatywnych (AT^-) tworzonego pojęcia. Algorytm ten tworzy drzewa klasyfikacyjne, które' minimalizują koszt klasyfikacji obiektu. Jeśli chodu o konstrukcję pojęć, to algorytm CLS tworzy je w postaci dysjunkcyjncj.

Budując drzewo, CLS stosuje strategię podobną'do strategii wspinaczki, przeszukując w każdym kroku przestrzeń możliwych drzew i starając się znaleźć najlepszy (w sensie wspomnianego, kosztu klasyfikacji) podział na następnym poziomie drzewa. Ponieważ testy w węzłach drzewa mają postać pytań, np;:.

@^#-raą wartość x_t,

powstają drzewa binarne, w których z każdego węzła mogą wychodzić jedynie dwie krawędzie: „tak” i „nie”, jak to pokazano nzrys. 9.7.

Rys. 9.7. Tworzenie drzewa binarnego przez CLS

'-'Algorytm CLS składa się 'z następujących kroków:’^'

1. ^jMając zbiór obiektów i? —    .i'. ,o„} sprawdź, czy wszystkie z nich należą do klasy K* (wtedy utwórz liść „tak"), czy do klasy K~ (wtedy utwórz liść „nie”). W przeciwnym ;przypadku wybierz cechę X o wartościach x,, i utwórz węzeł.

2.    Podziel zbiór S na podzbiory 5,, S₂, zgodnie Z wartościami

cećbyX:-'

3; Wykonaj kroki L-2 dlakplejnych podzbiorów Sn..., S*.

Najważniejszym problemem jest wybór-:cećhy determinującej podział zbjoru obiektów,^któ|^ musi najlepiej różnicować obiekty należące do klas K* oraz^F-^.CES wybiera taką cechę; X, która najlepiej różnicuje obiekty należące do klasy K+ i klasy tj. najczęściej wysypuje W zbiorze przykładów pozytywnych. H