Drzewa klasyfikacyjne

Drzewa klasyfikacyjne – zbiorcza nazwa rodziny metod statystycznych z zakresu eksploracji danych, dokonujących za pomocą diagramów zwanych drzewami klasyfikacji obserwacji statystycznych, czyli podziału próby 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.

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.

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.

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ć 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.

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).

Bibliografia

• Jacek Koronacki, Jan Ćwik: Statystyczne systemy uczące się. Warszawa: Wydawnictwa Naukowo-Techniczne, 2005. ISBN 83-204-3157-3.brak strony w książce

• Eugeniusz Gatnar: Nieparametryczna metoda dyskryminacji i regresji. Warszawa: PWN, 2001. ISBN 83-011-3369-4.brak strony w książce

• Mariusz Łapczyński: Drzewa klasyfikacyjne i regresyjne w badaniach marketingowych. Kraków: Uniwersytet Ekonomiczny w Krakowie, 2010. ISBN 978-83-7252-508-1.brak strony w książce