11. 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”.

---