Drzewa decyzyjne - omówienie - Algorytm

Nasza ocena:

3
Pobrań: 252
Wyświetleń: 3234
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
Drzewa decyzyjne - omówienie - Algorytm - strona 1 Drzewa decyzyjne - omówienie - Algorytm - strona 2 Drzewa decyzyjne - omówienie - Algorytm - strona 3

Fragment notatki:

Drzewa decyzyjne
Wymagania dla algorytmów drzew decyzyjnych
1. Algorytmy uczenia nadzorowanego-wymagają zdefiniowania zmiennej celu i
dostosowania zbioru uczącego zawierającego jej wartość
2. Zbiór uczący bogaty i różnorodny (drzewa uczą się przez przykłady- braki dla
podzbioru możliwego do określenia, klasyfikacja i przewidywanie problematyczne lub
niemożliwe)
3. Klasy zmiennej
4. Drzewa decyzyjne starają się stworzyć zbiór liści, które są najczystsze jak tylko to
możliwe, czyli gdy każdy z rekordów w danym liściu należy do danej klasy
5. Mierzenie jednorodności i niejednorodności czystości podziału
6. Algorytmy budowania drzew decyzyjnych

C5.0

CART (Classification and regresion…)

QUEST

CHAD
CART
 Drzewa binarne- dwie gałęzie z każdego węzła decyzyjnego
 CART rekurencyjnie dzieli rekordy ze zbioru uczącego na podzbiory rekordów z
podobnymi wartościami zmiennej celu
 Algorytm dla każdego węzła przeszukuje
 Drzewa mogą posiadać niejednorodne liście
 Współczynnik błędu klasyfikacji w liściu
 Dla całego drzewa współczynnik błędu jest liniowy, jako średnia ważona
pojedynczych współczynników błędów liści, z rogami równymi procentowi rekordów
na każdym liściu
Przycinanie:
 Usuwanie mało wiarygodnych gałęzi

Poprawia efektywność klasyfikacji

Poprawia zdolność klasyfikatora do klasyfikacji nowych przypadków
 Metody przycinania drzew decyzyjnych- bazują najczęściej na miarach statystycznych
np. MDL (Minimum Description Lenght), MCP (Minimal Cost-complexity Puning)
 Wstępne przycięcie drzewa (stop):
Drzewo jest przycinane poprzez wcześniejsze zatrzymanie procedury konstrukcji
drzewa (tj. wstrzymujemy dalsze dzielenie zbioru treningowego na części np.
warunek stopu polegający na przyjęciu minimalnej liczby elementów należących do
zbioru, które podlega dzieleniu).
 Przycinanie drzewa po zakończeniu konstrukcji, ucinamy gałęzie i wierzchołki po
zakończeniu procedury konstrukcji drzewa
C4.5
 Analizowany jest każdy węzeł decyzyjny i wybierany jest możliwy podział
 Model nie ogranicza się do binarnych podziałów
 Dla zmiennych jakościowych algorytm tworzy osobne gałęzie dla każdej wartości
algorytmu jakościowego
 Metoda mierzenia jednorodności podziału bazuje na pojęciu entropii
Zysk informacji lub redukcja entropii
 Załóżmy że mamy zmienną X , której k możliwych wartości ma
prawdopodobieństwo P1, P2, P3,…Pn. Jaka jest najmniejsza ilość bitów, średnia
na symbol, potrzebna do przesłania łańcucha symboli reprezentujących
obserwowane wartości X
 Entropia X zdefiniowana jako H(X)=-ΣPjlog2(Pj) = log2(0,5)=1 bit
 Załóżmy że mamy możliwy podział S, który dzieli zbiór uczący T na kilka
podzbiorów T1,T2,Tk, wtedy obliczone jako wartość suma entropii dla
pojedynczych podzbiorów:
Hs(T)=ΣPiHs(Ti)
 Zysk informacji-w każdym węźle algorytm C4.5 wybiera podział optymalny czyli
mający największy zysk informacji, zysk(S).
Reguły asocjacyjne
Analiza podobieństw
 Jest badaniem atrybutów lub cech, które są powiązane ze sobą
 Metody ... zobacz całą notatkę

Komentarze użytkowników (0)

Zaloguj się, aby dodać komentarz