Drzewa decyzyjne
[e-mail] 2009
Klasyfikacja
" Czynność podziału zbioru na podzbiory
nazwane klasami. Podziałem zbioru X nazywa
się każdy zupełny i rozłączny układ podzbiorów
tego zbioru.
" W wyniku klasyfikacji określamy nieznaną
wartość pewnego atrybutu obiektu,
wartość pewnego atrybutu obiektu,
przyjmującego skończoną liczbę wartości.
Drzewo decyzyjne
" Drzewo decyzyjne jest
to drzewo, w którym:
" węzły nie będące liśćmi
odpowiadajÄ… atrybutom
" gałęzie wychodzące z
takiego węzła odpowiadają
takiego węzła odpowiadają
wartościom tego atrybutu.
" liście odpowiadają
wartościom zmiennej
decyzyjnej (atrybutu
klasyfikujÄ…cego)
Zasady konstrukcji drzewa decyzyjnego
1. Punktem wyjścia jest korzeń drzewa, któremu odpowiada ciąg uczący T, w którym
znajdują się obserwacje, z których każda opisane jest atrybutami i zaklasyfikowana
jest do jednej z klas na podstawie pewnego wyróżnionego atrybutu (zmiennej
klasyfikujÄ…cej, decyzyjnej).
2. Konstrukcja drzewa opiera się na następującej procedurze powtarzanej
rekurencyjnie dla każdego węzła począwszy od korzenia:
" CiÄ…g danych uczÄ…cych T zawierajÄ…cy przynajmniej jeden element, przy czym
wszystkie elementy należą do tej samej klasy Cj. Drzewo decyzyjne dla T jest
liściem wskazującym na kategorię Cj.
liściem wskazującym na kategorię Cj.
" Ciąg uczący T nie zawiera żadnych elementów  podobnie jak w punkcie
poprzednim, drzewo dla T jest liściem jednak związany jest z klasą wyznaczoną
na podstawie poprzednika
" T zawiera elementy należące do różnych klas. Podział T na takie podzbiory, by
wszystkie elementy w ramach podzbioru należały do tej samej klasy (podzbiory
powinny być możliwie jednorodne). W oparciu o pojedynczy wybrany atrybut,
przeprowadzany jest test, który powoduje podział na rozłączne podzbiory.
Drzewo decyzyjne dla T jest węzłem zawierającym test i jedną gałąz
dla każdego
wyniku testu.
3. Po zakończeniu procedury generowania węzłów drzewa, może opcjonalnie nastąpić
przycinanie drzewa (zastąpienie całego poddrzewa pojedynczym liściem).
Algorytmy budowy drzew
" Elementy algorytmów budowania drzewa decyzyjnego:
" kryterium wyboru atrybutu używanego jako test w węz
le drzewa
" wyznaczenie wartości atrybutów dla gałęzi wychodzących z
węzła (rząd drzewa)
" Przykładowe algorytmy
" ID3 (Quinlan)
" C4.5 (Quinlan) rozszerzenie ID3 o brakujące wartości, atrybuty
ciągłe, obcinanie drzewa)
" CART (Classification And Regression Trees)  drzewo binarne.
" CHAID (Chi-squared Automatic Interaction Detector, 1980),
Wybór atrybutu testowego dla węzła
T  zbiór uczący, w którym każda obserwacja zaklasyfikowana jest według wartości atrybutu C do
jednej z k klas {C1, C2 ... Ck }
Entropia zbioru S:
k
freq (Ci ,T ) freq (Ci ,T )
Info (T ) = - log
" 2
T T
i=1
T1, T2...Tn - rozłączne podzbiory zbioru T, utworzone na podstawie pewnego testu t. Test jest
oparty o wartości atrybutu X.
Entropia zbioru przykładów ze względu na wynik r testu t jest definiowana jako ważona entropia
dla poszczególnych wyników testu:
n
T
r
Info (T ) = Å" Info (Ti ) ,
x "
T
r =1
Przyrost informacji wynikający z zastosowania testu opartego na wartościach atrybutu X do zbioru
przykładów:
Gain(X) = Info(T) - Infox(T)
Jako podstawę podziału zbioru obserwacji w węz
le wybieramy ten atrybut, dla którego Gain(X)
jest maksymalne.
Inne kryteria wyboru testu
Kryterium przyrostu informacji - tendencja do nieuzasadnionego preferowania testów o wielu
możliwych wynikach.
Współczynnik przyrostu informacji:
n
Ti Ti
Split _ Info(T ) = log2
"
" 2
T T
T T
i=1
Wartość mierzy równomierność, z jaką test t dzieli zbiór uczący na podzbiory. Jest ona duża jeśli
rozmiary podzbiorów wyznaczonych przez różne wyniki testu są zbliżone i maleje przy wyraz
nej
przewadze niektórych podzbiorów nad innymi.
Gain(X )
Gain _ ratio(X ) =
Split _ Info(X )
Algorytm Id3
Podział  atrybuty ciągłe
" Zbiór wartości, które przyjmuje atrybut sortujemy
{v1, v2,& vk}
" Rozważamy wszystkie (k-1) potencjalnych punktów
podziału: {v1, v2,& vi} {vi+1, vi+2,& vk}
" Wybieramy tą wartość podziału Z, dla którego kryterium
przyrostu informacji jest największe. Gałęzie opisane są
nie pojedynczymi wartościami atrybutu, lecz podzbiorami
wartości, wyznaczonymi przez punkt podziału Z.
Przykład
" Zbudować drzewo decyzyjne dla
wyznaczania wartości atrybutu C w
oparciu o wartości atrybutów A1, A2.
" CiÄ…g uczÄ…cy:
A1 A2 C
Y 1 C2
Y 2 C1
N 2 C2
N 2 C2
N 2 C1
A1 A2 C
A1 A2 C
A1 A2 C
A1 A2 C
A1 A2 C
2 2 3 3 2 3
ëÅ‚
Y 1 C2
Y 1 C2
Y 1 C2
Y 1 C2
Info(T) = -ëÅ‚ log2 öÅ‚ - log2 öÅ‚ = - Å"(-1,32) - Å"(-0,74) = 0,97
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
5 5 5 5 5 5
Y 2 C1
Y 2 C1
Y 2 C1
Y 2 C1
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
N 2 C2
N 2 C2
N 2 C2
N 2 C2
N 2 C2
N 2 C2
N 2 C2
N 2 C2
2 3
InfoA1(T) = Å" Info(TA1='Y ') + Info(TA1='N ')
N 2 C1
N 2 C1
N 2 C1
N 2 C1
5 5
N = 5
1 1 1 1
ëÅ‚
C1 2 (40%)
Info(TA1='Y ') = -ëÅ‚ log2 öÅ‚ - log2 öÅ‚ =1
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
C2 3 (60%)
2 2 2 2
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
2 2 1 1 2 1
ëÅ‚
Info(TA1='N ') = -ëÅ‚ log2 öÅ‚ - log2 öÅ‚ = - Å"(-0,59) - (-1,59) = 0,91
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
3 3 3 3 3 3
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
2 3
InfoA1(T) = Å"1+ Å"0,91 = 0,94
5 5
5 5
Gain(A1) = 0,97 - 0,94 = 0,03
1 4
InfoA2(T) = Å" Info(TA2=1) + Info(TA2=2)
5 5
1 1 1 1
ëÅ‚
Info(TA2=2) = -ëÅ‚ log2 öÅ‚ - log2 öÅ‚ =1
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
2 2 2 2
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
Info(TA2=1) = 0
1 4
InfoA2(T) = Å"0 + Å"1 = 0,8
5 5
Gain(A2) = 0,97 - 0,8 = 0,18
Podział następuje ze względu na A2, gdyż Gain(A2) > Gain(A1)
A1 A2 C
A1 A2 C
A1 A2 C
A1 A2 C
A1 A2 C
Y 1 C2
Y 1 C2
Y 1 C2
Y 1 C2
Y 2 C1
Y 2 C1
Y 2 C1
Y 2 C1
N 2 C2
N 2 C2
N 2 C2
N 2 C2
N 2 C2
N 2 C2
N 2 C2
N 2 C2
N 2 C1
N 2 C1
N 2 C1
N 2 C1
N = 5
C1 2 (40%)
C2 3 (60%)
A2
A2=2
A2=1
A1 A2 C
A1 A2 C
Y 2 C1
Y 1 C2
N 2 C2
N 2 C2
N 2 C1
N = 4 N = 1
C1 2 (50%) C1 0 (0%)
C2 2 (50%) C2 1 (100%)
A1 A2 C
1 1 1 1
ëÅ‚
Info(T ) = -ëÅ‚ log2 öÅ‚ - log2 öÅ‚ =1
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
Y 2 C1
2 2 2 2
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
N 2 C2
1 3
N 2 C2
InfoA1(T ) = Å" Info(TA1='Y ') + Info(TA1='N ')
4 4
N 2 C1
Info(TA1='Y ') = 0
2 2 1 1 2 1
ëÅ‚
Info(TA1='N ') = -ëÅ‚ log2 öÅ‚ - log2 öÅ‚ = - Å"(-0,59) - (-1,59) = 0,91
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
3 3 3 3 3 3
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
3
InfoA1(T ) = 0 + Å"0,91 = 0,68
4
4
Gain(A1) = 1- 0,68 = 0,32
4
InfoA2(T ) = Å" Info(TA2=2) + 0Å" Info(TA2=2)
4
1 1 1 1
ëÅ‚
Info(TA2=2) = -ëÅ‚ log2 öÅ‚ - log2 öÅ‚ =1
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
2 2 2 2
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
InfoA2(T ) =1
Gain(A2) = 1-1 = 0
Podział następuje ze względu na A1, gdyż Gain(A1) > Gain(A2)
A1 A2 C
A1 A2 C
A1 A2 C
A1 A2 C
A1 A2 C
Y 1 C2
Y 1 C2
Y 1 C2
Y 1 C2
Y 2 C1
Y 2 C1
Y 2 C1
Y 2 C1
N 2 C2
N 2 C2
N 2 C2
N 2 C2
N 2 C2
N 2 C2
N 2 C2
N 2 C2
N 2 C1
N 2 C1
N 2 C1
N 2 C1
N = 5
C1 2 (40%)
C2 3 (60%)
A2
A2=2
A2=1
A1 A2 C
A1 A2 C
Y 2 C1
Y 1 C2
N 2 C2
N 2 C2
N 2 C1
N = 4 N = 1
C1 2 (50%) C1 0 (0%)
C2 2 (50%) C2 1 (100%)
A1
A1=Y A1=N
A1 A2 C
A1 A2 C
Y 2 C1
N 2 C2
N 2 C2
N 2 C1
N = 1
N = 3
C1 1 (100%)
C1 1 (33%)
C2 0 (0%)
C2 2 (67%)
Szacowanie błędów klasyfikacji
" Współczynnik błędnej klasyfikacji
" Liść drzewa = decyzja => liczba rekordów
błędnie zaklasyfikowanych
" Stosunek liczby błędnie zaklasyfikowanych
obserwacji do wszystkich
obserwacji do wszystkich
Przycinanie drzewa (prunning)
" Obcinanie polega na zastąpieniu poddrzewa liściem, którym przypisuje się
etykietę kategorii najczęściej występującej wśród związanych z nim
przykładów.
" Nadmierne dopasowanie do danych trenujących (overfitted)  duży błąd dla
danych spoza ciÄ…gu uczÄ…cego
" Zbudowane drzewo ma zbyt dużą wysokość (niedopuszczalna złożoność
procedury klasyfikujÄ…cej)
" Począwszy od dołu drzewa, dla każdego poddrzewa nie będącego liściem:
" Obcinamy, jeżeli zastąpienie poddrzewa liściem z przypisaną kategorią
" Obcinamy, jeżeli zastąpienie poddrzewa liściem z przypisaną kategorią
reprezentowaną przez potomka o największej liczności zmniejsza błąd.
reprezentowaną przez potomka o największej liczności zmniejsza błąd.
Modyfikacja błędów dla rodziców.
" Estymacja błędu klasyfikacji:
" Szacowanie na podstawie błędu próbki na oddzielnym zbiorze przycinania,
złożonym z przykładów spoza zbioru trenującego.
" Szacowanie na podstawie błędu próbki na zbiorze trenującym.
Zadanie
" Na podstawie zbioru danych
treningowych ( ciÄ…gu
uczÄ…cego)
" Znalez
ć wartość podziału dla
atrybutu A
" Znalez
ć wartość podziału dla
atrybutu B
" Zbudować drzewo decyzyjne
" Jaki jest proporcja błędnych
Jaki jest proporcja błędnych
klasyfikacji dla ciÄ…gu
klasyfikacji dla ciÄ…gu
testowego ?
Literatura
" Paweł Cichosz  Systemy uczące się WNT
2000
" Hand David, Mannila Heikki, Smyth
Padhraic  Eksploracja danych , WNT 2005