To tylko jedna z 3 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
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)