Metody konstrukcji drzew decyzyjnych. Zadanie i metody klasyfikacji.
Metoda ta polega na stworzeniu tzw. drzewa decyzyjnego . Drzewo decyzyjne jest to graf, którego korzeń
utworzony jest przez wybrany atrybut, a poszczególne gałęzie reprezentują wartości tego atrybutu. Na następnych poziomach znajdują się kolejne atrybuty, zaś na najniższym poziomie węzły charakteryzują poszczególne klasy. Zagadnienie optymalnego drzewa decyzyjnego rozwiązuje się za pomocą entropii pewnego elementowego zbioru. Entropia jest to pewna miara informacji zawartej w zjawisku, która w przypadkowy sposób może przyjmować n-stanów. Drzewo decyzyjne może być traktowane jako źródło informacji generujące informacje o przynależności do klasy danego obiektu.
Drzewo decyzji: Ogólne => Szczegółowe
węzeł - test atrybutu
rozgałęzienie - wartość atrybutu lub podzbiór
liście - przypisane do klas
Testy: podział pojedynczej cechy, lub kombinacji
Attrybut={wartośći} lub Attrybut < wartośći
Kryteria: maksymalizacja ilości informacji, maksymalizacja liczby
poprawnie podzielonych obiektów, „czystość” węzła
Przycinanie: usuń gałęzie, które zawierają zbyt mało przypadków
prostsze drzewo może lepiej generalizować
oceń optymalną złożoność na zbiorze walidacyjnym.
Kryterium stopu: osiągnięta dokładność podziałów, zbyt wiele gałęzi.
Generyczny algorytm TDIDT
TDIDT - Top Down Iterative Decision Tree
function DT(E: zbiór przykładów) returns drzewo;
T' := buduj_drzewo(E);
T := obetnij_drzewo(T');
return T;
Tworzenie drzewa: szukanie w przestrzeni hipotez.
ID3 - podział w oparciu o zysk informacyjny.
Lepsze mniejsze drzewo.
Dość odporne na szum.
Lokalne minima.
1R - 1R: najprostsze drzewo (Holte 1993), niezłe rezultaty.
Jeden poziom, atrybuty nominalne.
C 4.5 Typowy algorytm TDIDT , jedno z najbardziej popularnych DT
Wyróżniamy drzewa: proste i skośne.
Zalety DT (drzew decyzyjnych):
Zwykle bardzo dobre wyniki w porównaniu z innymi klasyfikatorami.
Łatwe w użyciu, prawie nie mają parametrów do ustawiania.
Dane nominalne lub numeryczne.
Zastosowania: klasyfikacja i regresja.
Prawie wszystkie pakiety Data Mining mają drzewa decyzji.
Problemy z DT:
mało danych, duża liczba ciągłych cech; niższe partie drzewa mają b. mało danych, przypadkowe podziały;nie wszystkie koncepcje dają się dobrze ująć za pomocą DT, np. „większość jest za”.