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
Wyszukiwarka
Podobne podstrony:
DRZEWA DECYZYJNE
Wersja do oddania, Rozdzial 5 - Drzewa decyzyjne, Rozdział III
L3 drzewa decyzyjne
L3 drzewa decyzyjne klucz
drzewa decyzyjne
Drzewa decyzyjne
Drzewa decyzyjne wprowadzenie 20061206
minswd L3, drzewa decyzyjne
Drzewa decyzyjne 2009 id 143623 Nieznany
hd 06 drzewa decyzyjne id 19989 Nieznany
12 Drzewa Decyzyjne
drzewa decyzyjne
więcej podobnych podstron