Drzewa decyzyjne
marcin.mazurek@wat.edu.pl 2009
Drzewa decyzyjne
marcin.mazurek@wat.edu.pl 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 C
j.
Drzewo decyzyjne dla T jest
liściem wskazującym na kategorię C
j.
liściem wskazującym na kategorię C
j.
•
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łąź 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ęź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 {C
1
, C
2
... C
k
}
Entropia zbioru S:
T
T
C
freq
T
T
C
freq
T
Info
i
k
i
i
)
,
(
log
)
,
(
)
(
1
2
∑
=
−
=
T
1
, T
2
...T
n
- 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
r
i
r
x
T
Info
T
T
T
Info
1
)
(
)
(
,
Przyrost informacji wynikający z zastosowania testu opartego na wartościach atrybutu X do zbioru
przykładów:
Gain(X) = Info(T) - Info
x
(T)
Jako podstawę podziału zbioru obserwacji w węź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:
T
T
T
T
T
Info
Split
i
n
i
∑
=
2
log
)
(
_
T
T
i
∑
=1
2
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 wyraźnej
przewadze niektórych podzbiorów nad innymi.
)
(
_
)
(
)
(
_
X
Split
X
Gain
X
ratio
Gain
Info
=
Algorytm Id3
Podział – atrybuty ciągłe
•
Zbiór wartości, które przyjmuje atrybut sortujemy
{v
1
, v
2
,… v
k
}
•
Rozważamy wszystkie (k-1) potencjalnych punktów
podziału: {v
1
, v
2
,… v
i
} {v
i+1
, v
i+2
,… v
k
}
•
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
Y
1
C2
Y
2
C1
N
2
C2
N
2
C2
N
2
C1
A1
A2
C
Y
1
C2
Y
2
C1
N
2
C2
N
2
C2
N
2
C1
A1
A1
A1
A2
A2
A2
C
C
C
Y
Y
1
1
C2
C2
Y
Y
2
2
C1
C1
N
N
2
2
C2
C2
N
N
2
2
C2
C2
N
N
2
2
C1
C1
N = 5
C1 2 (40%)
C2 3 (60%)
97
,
0
)
74
,
0
(
5
3
)
32
,
1
(
5
2
5
3
log
5
3
5
2
log
5
2
)
(
2
2
=
−
⋅
−
−
⋅
−
=
−
−
=
T
Info
94
,
0
91
,
0
5
3
1
5
2
)
(
91
,
0
)
59
,
1
(
3
1
)
59
,
0
(
3
2
3
1
log
3
1
3
2
log
3
2
)
(
1
2
1
log
2
1
2
1
log
2
1
)
(
)
(
5
3
)
(
5
2
)
(
1
2
2
'
'
1
2
2
'
'
1
'
'
1
'
'
1
1
=
⋅
+
⋅
=
=
−
−
−
⋅
−
=
−
−
=
=
−
−
=
+
⋅
=
=
=
=
=
T
Info
T
Info
T
Info
T
Info
T
Info
T
Info
A
N
A
Y
A
N
A
Y
A
A
0,03
0,94
-
0,97
Gain(A1)
5
5
=
=
0,18
0,8
-
0,97
Gain(A2)
8
,
0
1
5
4
0
5
1
)
(
0
)
(
1
2
1
log
2
1
2
1
log
2
1
)
(
)
(
5
4
)
(
5
1
)
(
2
1
2
2
2
2
2
2
2
1
2
2
=
=
=
⋅
+
⋅
=
=
=
−
−
=
+
⋅
=
=
=
=
=
T
Info
T
Info
T
Info
T
Info
T
Info
T
Info
A
A
A
A
A
A
Podział następuje ze względu na A2, gdyż Gain(A2) > Gain(A1)
A1
A2
C
Y
1
C2
Y
2
C1
N
2
C2
N
2
C2
N
2
C1
A1
A2
C
Y
1
C2
Y
2
C1
N
2
C2
N
2
C2
N
2
C1
A1
A1
A1
A2
A2
A2
C
C
C
Y
Y
1
1
C2
C2
Y
Y
2
2
C1
C1
N
N
2
2
C2
C2
N
N
2
2
C2
C2
N
N
2
2
C1
C1
N = 5
C1 2 (40%)
C2 3 (60%)
A2
N = 4
C1 2 (50%)
C2 2 (50%)
A2=2
A2=1
N = 1
C1 0 (0%)
C2 1 (100%)
A1
A2
C
Y
2
C1
N
2
C2
N
2
C2
N
2
C1
A1
A2
C
Y
1
C2
A1
A2
C
Y
2
C1
N
2
C2
N
2
C2
N
2
C1
1
2
1
log
2
1
2
1
log
2
1
)
(
2
2
=
−
−
=
T
Info
68
,
0
91
,
0
4
3
0
)
(
91
,
0
)
59
,
1
(
3
1
)
59
,
0
(
3
2
3
1
log
3
1
3
2
log
3
2
)
(
0
)
(
)
(
4
3
)
(
4
1
)
(
1
2
2
'
'
1
'
'
1
'
'
1
'
'
1
1
=
⋅
+
=
=
−
−
−
⋅
−
=
−
−
=
=
+
⋅
=
=
=
=
=
T
Info
T
Info
T
Info
T
Info
T
Info
T
Info
A
N
A
Y
A
N
A
Y
A
A
0,32
0,68
-
1
Gain(A1)
4
=
=
0
1
-
1
Gain(A2)
1
)
(
1
2
1
log
2
1
2
1
log
2
1
)
(
)
(
0
)
(
4
4
)
(
2
2
2
2
2
2
2
2
2
2
=
=
=
=
−
−
=
⋅
+
⋅
=
=
=
=
T
Info
T
Info
T
Info
T
Info
T
Info
A
A
A
A
A
Podział następuje ze względu na A1, gdyż Gain(A1) > Gain(A2)
A1
A2
C
Y
1
C2
Y
2
C1
N
2
C2
N
2
C2
N
2
C1
A1
A2
C
Y
1
C2
Y
2
C1
N
2
C2
N
2
C2
N
2
C1
A1
A1
A1
A2
A2
A2
C
C
C
Y
Y
1
1
C2
C2
Y
Y
2
2
C1
C1
N
N
2
2
C2
C2
N
N
2
2
C2
C2
N
N
2
2
C1
C1
N = 5
C1 2 (40%)
C2 3 (60%)
A2
A2=2
A2=1
A1
A2
C
Y
2
C1
N
2
C2
N
2
C2
A1
A2
C
Y
1
C2
N = 4
C1 2 (50% )
C2 2 (50% )
N = 1
C1 0 (0% )
C2 1 (100% )
N
2
C1
N = 1
C1 1 (100% )
C2 0 (0% )
A1
A1=Y
A1=N
N = 3
C1 1 (33% )
C2 2 (67% )
A1
A2
C
N
2
C2
N
2
C2
N
2
C1
A1
A2
C
Y
2
C1
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ą
reprezentowaną przez potomka o największej liczności zmniejsza błąd.
•
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)
•
Znaleźć wartość podziału dla
atrybutu A
•
Znaleźć wartość podziału dla
atrybutu B
•
Zbudować drzewo decyzyjne
•
Jaki jest proporcja błędnych
klasyfikacji dla ciągu
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