Drzewa decyzyjne
[e-mail] 2006
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,
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ą
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.
" 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
Tr
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
"
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
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
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
Przedział ufności o poziomie ufności 1-p dla parametru
p rozkładu dwumianowego:
N  liczba prób, p  prawdopodobieństwo sukcesu w
pojedynczej próbie.
P nie jest znana, do jej oszacowania na podstawie
eksperymentu
Yp  estymator  liczba sukcesów do liczby wykonanych
prób,
Przedział ufności dla estymatora:
Klasyfikowanie przykładów ma cechy próby
Bernoullliego: sukcesem jest pomyłka w klasyfikacji.
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ą
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
klasyfikacji dla ciÄ…gu
testowego ?
Literatura
Paweł Cichosz  Systemy uczące się WNT
2000
Hand David, Mannila Heikki, Smyth
Padhraic  Eksploracja danych , WNT 2005