IMAGE5

Rozdział 9

Drzewa klasyfikacyjne 91 Podstawowe określenia

Draga z omawianych w tej części książki metod konstruowania reguł klasyfikacji jest oparta na drzewach klasyfikacyjnych^{1 2} i polega na stopniowym podziale zbioru obiektów na podzbiory tak długo, aż zostanie osiągniętą ich jednorodność ze względu na przynależność do klas.

Drzewa klasyfikacyjne powstały na początku lat osiemdziesiątych w wyniku poszukiwania metod naśladujących uczenie się i rozwiązywanie problemów przez ludzi; Główne idee pochodzą jednak z lat sześćdziesiątych, kiedy to powstał pomysł wykorzystania konstrukcji typu dizewo (nazywano je drzewami decyzyjnymi) do reprezentowania procesu jra&l*$tif|§Mro    i P.J. Stone zbudowali wtedy

algorytm CLS (ang. Coneept Leaming System) (Hunt i in. 1966). Zgodnie z ich podejściem pojęcie to reguła decyzyjna, która zastosowana do charakterystyki obiektu mówi o tym, czy należy on do określonej klasy (teprezentowanej przez nazwę). Algorytm CU stał się inspiracją prowadzenia dalszych badań w tym kierunku, nie tylko na gruncie psychologii.

Najważniejszym etapem w rozwoju prezentowanych metod było pojawienie się algorytmu ID3 Quinlana (1983), którego udane zastosowania praktyczne zwróciły uwagę na drzewa klasyfikacyjne jako wygodne narzędzie klasyfikacji danych³. W tym samym czasie na gruncie statystyki podjęto poszukiwania metod klasyfikacji wzorcowej, które byłyby mniej

1

‘ Często w literaturze stosuje się także nazwę drzewa decyzyjne (ang. dećiswn trees).

2

Algorytm ID3 by) w następnych latach wielokrotnie modyfikowany aż do .pojawienia

3

sit w 1996 r. jego ostatniej wersji o nazwie C4.8 (Quinlan 1996).