Stosowane symboleL liczba klas
T drzewo decyzyjne
t węzeł drzewa
Tt poddrzewo drzewa T o korzeniu w węźle t
TL zbiór liści drzewa T
|TL| liczba liści drzewa T
m liczba przykładów
mi liczba przykładów, dla których dany atrybut przyjmuje wartość i-tą
mj liczba przykładów klasy cj
Stosowane symbole
L liczba klas
T drzewo decyzyjne
t węzeł drzewa
Tt poddrzewo drzewa T o korzeniu w węźle t
TL zbiór liści drzewa T
|TL| liczba liści drzewa T
m liczba przykładów
mi liczba przykładów, dla których dany atrybut przyjmuje wartość i-tą
mj liczba przykładów klasy cj
Decyzja rozłożona na szereg prostszych decyzji; w różnych etapach wykorzystywane są różne cechy i uwzględniane różne podzbiory klas. Schemat działania klasyfikatora przedstawia drzewo decyzyjne Podczas całego procesu decyzyjnego uwzględniane wszystkie cechy i klasy. jednoetapowa sekwencyjna Klasyfikacja
Drzewo decyzyjne
Pogoda tak nie Odległość < 20 km deszczowo słonecznie Działanie klasyfikatora wieloetapowego ilustruje drzewo decyzyjne.
Pojęcia: korzeń drzewa, węzeł wewnętrzny, węzeł końcowy (liść), gałąź, ścieżka.
Drzewo decyzyjne
Pogoda tak nie Odległość < 20 km deszczowo Odległość: 8
Pogoda: deszczowo słonecznie
Zalety drzew decyzyjnych
szybka klasyfikacja
zrozumiały proces decyzyjny
możliwość aproksymacji złożonych powierzchni decyzyjnych
możliwość stosowania cech różnego typu
efektywne z punktu widzenia przechowywania w pamięci
Wady drzew decyzyjnych
im więcej klas oraz im bardziej się one nakładają, tym większe drzewo decyzyjne
trudno zapewnić jednocześnie wysoką jakość klasyfikacji i małe rozmiary drzewa
w węzłach testowany jeden atrybut
lokalna optymalizacja
metody nieadaptacyjne
Konstrukcja drzewa decyzyjnego
1 1 1 1 2 2 2 2 2 2 2 2 2 y1 y2 a2 a1 2 a3 tak nie y2 < a1 1 tak nie y1 < a2 2 2 2 nie tak y2 < a1 1 nie y1< a3 tak 1 1 1 1 2 2 2 2 2 2 2 2 2 y1 y2 a1
Konstrukcja drzew decyzyjnych Jeden zbiór danych wiele możliwych drzew
Czym należy się kierować wybierając (konstruując) drzewo?
Kryteria optymalizacji
Lokalne Globalne - średnie prawdopodobieństwo błędu - średnia długość ścieżki - liczba węzłów drzewa stopień zróżnicowania danych - przyrost informacji - współczynnik przyrostu informacji i inne
Zstępująca konstrukcja drzew decyzyjnych
function Konstrukcja_drzewa(P-przykłady,t-węzeł)
if not kryterium_stopu then
podział_węzła t
for i=1 to n (n-liczba węzłów potomnych)
Konstrukcja_drzewa(Pi,ti)
else
utworzenie_liścia t
endif
end function
Utworzenie liścia Do węzła końcowego przypisuje się etykietę tej klasy, której obrazów najwięcej dociera do tego węzła.
Podział węzła - przykłady
tak nie yi > i 1. Cecha porównana z wartością progową (typowe dla atrybutów ciągłych). 2. Uwzględnione wszystkie możliwe wartości danego atrybutu (typowe dla atrybutów nominalnych). yi yi1 yi2 yik
Podział węzła
Najczęściej reguły decyzyjne budowane są na podstawie pojedynczych cech źródłowych. Prowadzi to do dzielenia przestrzeni cech hiperłaszczyznami prostopadłymi do osi cech.
Wybierając cechę można się kierować jedną ze znanych miar, np. przyrostem informacji, wskaźnikiem przyrostu informacji, wskaźnikiem zróżnicowania danych itd.
Podział węzła w przypadku atrybutów nominalnych
yi yi1 yi2 yik t t1 t2 tk 1. Dla każdego atrybutu yi oblicz wartość wybranej miary.
2. Wybierz atrybut optymalny w sensie powyższej miary.
3. Od danego węzła utwórz tyle gałęzi, ile różnych wartości przyjmuje atrybut yi.
Kryteria wyboru atrybutu
mierzące różnicę między zbiorem przykładów w węźle t a zbiorami przykładów w węzłach potomnych ze względu na rozkład częstości klas;
mierzące różnice między poszczególnymi zbiorami przykładów w węzłach potomnych ze względu na rozkład częstości klas;
mierzące statystyczną niezależność między rozkładem klas a podziałem zbioru przykładów na podzbiory.
Kryteria wyboru atrybutu – przyrost informacji
Przyrost informacji IM (information measure): Dla każdego atrybutu obliczamy wartość IM i wybieramy atrybut, dla którego wartość ta jest największa (H nie zależy od atrybutu, wystarczy porównywać drugi składnik). Miara IM preferuje atrybuty o dużej liczbie różnych wartości. y y1 yj yk H, m przykładów H1, m1 Hj, mj Hk, mk
Kryteria wyboru atrybutu – współczynnik przyrostu informacji
Współczynik przyrostu informacji GR (gain ratio): Dla każdego atrybutu obliczamy wartość GR i wybieramy atrybut, dla którego wartość ta jest największa.
Miara GR preferuje atrybuty o małej liczbie różnych wartości.
Kryteria wyboru atrybutu - miara zróżnicowania danych (Gini index)
Stopień zróżnicowania danych: Dla każdego atrybutu obliczamy i i wybieramy atrybut, dla którego wartość ta jest największa. Spadek zróżnicowania:
Kryteria wyboru atrybutu – statystyka 2
Statystyka 2 służy do porównywania rzeczywistych rozkładów z oczekiwanymi. Dla każdego atrybutu obliczamy 2 i wybieramy atrybut, dla którego wartość ta jest największa.
Kryteria wyboru atrybutu
Eksperymenty pokazują że:
przedstawione kryteria wyboru atrybutu nie wpływają na błąd klasyfikacji; można otrzymać równie dobre drzewa wybierając atrybuty w węzłach losowo, ale
przedstawione miary wpływają na rozmiary skonstruowanego drzewa (przed przycięciem); drzewa, dla których losowano atrybuty zawierają około dwa razy więcej węzłów;
przeważnie korzystając z miary GR otrzymuje się najmniejsze drzewa a za pomocą 2 największe;
na błąd klasyfikacji ma wpływ przycinanie drzewa.
Comments