Drzewa klasyfikacyjne
Z Wikipedii
Drzewa klasyfikacyjne - zbiorcza nazwa rodziny metod statystycznych z zakresu data mining, dokonujących za pomocą diagramów zwanych drzewami klasyfikacji obserwacji statystycznych, czyli podziału próbki statystycznej na klasy obserwacji o podobnych właściwościach. Metoda drzew klasyfikacyjnych jest odmianą hierarchicznej analizy skupień.
Jeśli drzewo stosujemy do klasyfikowania realnych sytuacji, a wynikiem klasyfikacji jest decyzja, jaka ma być w danej sytuacji podjęta, drzewo jest też nazywane drzewem decyzyjnym.
Drzewo składa się z korzenia (przedstawianego, podobnie jak w matematyce i informatyce, zwykle u góry rysunku) oraz gałęzi prowadzących z korzenia do kolejnych węzłów. W każdym węźle sprawdzany jest pewien warunek dotyczący danej obserwacji, i na jego podstawie wybierana jest jedna z gałęzi prowadząca do kolejnego węzła piętro niżej. Na dole znajdują się liście, w których odczytujemy do której z klas należy przypisać daną obserwację. Klasyfikacja danej obserwacji polega na przejściu od korzenia do liścia i przypisaniu do tej obserwacji klasy zapisanej w danym liściu.
Spis treści |
[edytuj] Definicja formalna
Formalnie drzewo klasyfikacyjne jest acyklicznym spójnym grafem skierowanym. Każdemu jego węzłowi, będącemu liściem, przyporządkowane jest oznaczenie klasy, a każdej z gałęzi reguła decyzyjna, czyli warunek odnoszący się do wartości zmiennych w zbiorze wejściowym i mówiący w jakim przypadku należy pójść daną gałęzią.
W większości algorytmów warunki dla gałęzi wychodzących z jednego węzła muszą się uzupełniać tak, aby dla każdego możliwego wektora zmiennych w danej obserwacji jedna z nich i tylko jedna była spełniona. Istnieją też algorytmy, które zamiast warunków wyznaczają wagi dla poszczególnych gałęzi.
[edytuj] Postać danych
Dane zwykle mają postać tabeli, w której wierszach mamy obserwacje, a w kolumnach zmienne. Przykładowo w tabeli każdy wiersz może odpowiadać jednemu człowiekowi, a kolumny to różne zmienne określające go, np. wiek, wzrost, czy ciężar ciała.
[edytuj] Uczenie drzewa
Drzewo klasyfikacyjne ekspert może utworzyć "ręcznie", bez pomocy narzędzi statystycznych. W taki sposób czasem tworzone są np. drzewa klasyfikacyjne w przypadku gdy klasy dają się łatwo rozróżnić[1] i jest ich stosunkowo niewiele. W ten sposób tworzone były np. klucze do oznaczania gatunków w biologii, będące de facto wielkimi drzewami decyzyjnymi.
Zwykle jednak stosuje się specjalistyczne algorytmy statystyczne, które automatycznie dzielą próbę na kolejne podpróby, tworząc kolejne węzły drzewa.
[edytuj] Historia
Po raz pierwszy drzew klasyfikacyjnych zaczęli używać socjologowie. Prawdopodobnie pierwszą pracą w której użyto tej metody był artykuł J.N. Morgana i J.A. Sonquista z roku 1963 wydrukowany w Journal of the American Statistical Association, ale z zakresu socjologii.
Niezależnie odkrył je Quinlan w końcu lat 70. (powoływał się przy tym na wcześniejsze prace psychologów) i używał w dziedzinie uczenia maszynowego. Drzewa klasyfikacyjne i regresyjne spopularyzowała jednak dopiero w 1984 roku książka Breimana (zob. bibliografia).
[edytuj] Bibliografia
- Jacek Koronacki, Jan Ćwik: Statystyczne systemy uczące się. Warszawa: Wydawnictwa Naukowo-Techniczne, 2005. ISBN 83-204-3157-3.
Przypisy
- ↑ fachowo mówi się, że są dobrze separowalne