Drzewa decyzyjne
Jacek Kluska
Politechnika Rzeszowska
2010
Jacek Kluska (Politechnika Rzeszowska)
2010
1 / 35
Przyk÷
ad drzewa
Nr
Aura
Temperatura
Wilgotno´s´c
Wiatr
Klasa
1
s÷
oneczna
wysoka
du·
za
nie
0
2
s÷
oneczna
wysoka
du·
za
tak
0
3
pochmurna
wysoka
du·
za
nie
1
4
deszczowa
´srednia
du·
za
nie
1
5
deszczowa
niska
normalna
nie
1
6
deszczowa
niska
normalna
tak
0
7
pochmurna
niska
normalna
tak
1
8
s÷
oneczna
´srednia
du·
za
nie
0
9
s÷
oneczna
niska
normalna
nie
1
10
deszczowa
´srednia
normalna
nie
1
11
s÷
oneczna
´srednia
normalna
tak
1
12
pochmurna
´srednia
du·
za
tak
1
13
pochmurna
wysoka
normalna
nie
1
14
deszczowa
´srednia
du·
za
tak
0
Jacek Kluska (Politechnika Rzeszowska)
2010
2 / 35
Przyk÷
ad drzewa - rozwi ¾
azanie
Jacek Kluska (Politechnika Rzeszowska)
2010
3 / 35
Przyk÷
ad - regu÷
y wynikaj ¾
ace z drzewa
Nr
Aura
Temperatura
Wilgotno´s´c
Wiatr
Klasa
1
s÷
oneczna
wysoka
du·
za
nie
0
2
s÷
oneczna
wysoka
du·
za
tak
0
3
pochmurna
wysoka
du·
za
nie
1
4
deszczowa
´srednia
du·
za
nie
1
5
deszczowa
niska
normalna
nie
1
6
deszczowa
niska
normalna
tak
0
7
pochmurna
niska
normalna
tak
1
8
s÷
oneczna
´srednia
du·
za
nie
0
9
s÷
oneczna
niska
normalna
nie
1
10
deszczowa
´srednia
normalna
nie
1
11
s÷
oneczna
´srednia
normalna
tak
1
12
pochmurna
´srednia
du·
za
tak
1
13
pochmurna
wysoka
normalna
nie
1
14
deszczowa
´srednia
du·
za
tak
0
R
1
: If Aura = pochmurna, then Klasa = 1
(4 przypadki)
Jacek Kluska (Politechnika Rzeszowska)
2010
4 / 35
Przyk÷
ad - regu÷
y wynikaj ¾
ace z drzewa - c.d.
Nr
Aura
Temperatura
Wilgotno´s´c
Wiatr
Klasa
1
s÷
oneczna
wysoka
du·
za
nie
0
2
s÷
oneczna
wysoka
du·
za
tak
0
3
pochmurna
wysoka
du·
za
nie
0
4
deszczowa
´srednia
du·
za
nie
1
5
deszczowa
niska
normalna
nie
1
6
deszczowa
niska
normalna
tak
0
7
pochmurna
niska
normalna
tak
1
8
s÷
oneczna
´srednia
du·
za
nie
0
9
s÷
oneczna
niska
normalna
nie
1
10
deszczowa
´srednia
normalna
nie
1
11
s÷
oneczna
´srednia
normalna
tak
1
12
pochmurna
´srednia
du·
za
tak
1
13
pochmurna
wysoka
normalna
nie
1
14
deszczowa
´srednia
du·
za
tak
0
R
2
: If Aura = s÷
oneczna,
^
Wilgotno´s´c = du·
za, then Klasa = 0
(3
przypadki)
Jacek Kluska (Politechnika Rzeszowska)
2010
5 / 35
Rekurencyjna de…nicja drzewa decyzyjnego
X - dziedzina atrybutów a
1
, . . . , a
n
.
C - zbiór kategorii.
R
t
-
f
r
1
, . . . , r
m
g
- zbiór mo·
zliwych wyników testu t.
Drzewo
1
Li´s´c z etykiet ¾
a d
2
C jest drzewem decyzyjnym.
2
Je´sli t : X
!
R
t
jest testem przeprowadzonym na warto´sciach
atrybutów przyk÷
adów o zbiorze mo·
zliwych wyników R
t
oraz
T
1
, . . . , T
m
s ¾
a drzewami decyzyjnymi, to w ¾
eze÷zawieraj ¾
acy test t, z
którego wychodzi m ga÷¾
ezi, przy czym dla i
=
1, . . . , m ga÷¾
a´z i -ta
odpowiada wynikowi r
i
i prowadzi do drzew T
t
, jest drzewem
decyzyjnym.
Jacek Kluska (Politechnika Rzeszowska)
2010
6 / 35
Za÷
o·
zenia: zmienne, klasy, typy zmiennych, kategorie
Zmienne = {Aura, Temperatura, Wilgotno´s´c, Wiatr, Klasa}
Zmienne s ¾
a ze zbioru sko´nczonego (categorical) - nie s ¾
a “ci ¾
ag÷
e".
Zmienne predykcyjne (predictors) = Atrybuty = {Aura, Temperatura,
Wilgotno´s´c, Wiatr}
Zmienne docelowe (target) = {Klasa}
Jacek Kluska (Politechnika Rzeszowska)
2010
7 / 35
Zst ¾
epuj ¾
aca budowa drzewa decyzyjnego (Top-Down
Induction of Decision Trees)
funkcja buduj_drzewo
(
P, d , S
)
P - zbiór przyk÷
adów etykietowanych kategoriami c,
Np. dla c
=
1 mamy P
1
, dla c
=
0 mamy P
0
,
P dotyczy ka·
zdej kolumny, np. dla c
=
1 i atrybutu “Aura” jest
P
1
Aura
=
P
1
Aura_sloneczna
[
P
1
Aura_pochmurna
[
P
1
Aura_deszczowa
d - etykieta kategorii,
S - zbiór mo·
zliwych testów;
zwraca: drzewo decyzyjne reprezentuj ¾
ace hipotez ¾
e przybli·
zaj ¾
ac ¾
a c na
zbiorze P;
Jacek Kluska (Politechnika Rzeszowska)
2010
8 / 35
Zst ¾
epuj ¾
aca budowa drzewa decyzyjnego (Top-Down
Induction of Decision Trees) - c.d.
1
If kryterium_stopu
(
P, S
)
2
utwórz li´s´c l;
3
d
l
:
=
kategoria
(
P, d
)
;
4
zwró´c l;
5
end
6
Utwórz w ¾
eze÷n;
7
t
n
:
=
wybierz_test
(
P, S
)
;
8
d :
=
kategoria
(
P, d
)
;
9
for
8
r
2
R
t
n
10
n
[
r
]
:
=
buduj_drrzewo
(
P
t
n
, d , S
f
t
n
g)
;
11
end
12
zwró´c n.
Jacek Kluska (Politechnika Rzeszowska)
2010
9 / 35
Testy atrybutów
t
(
x
) =
1
,
a
(
x
) =
v
0
oth.
t
(
x
) =
1
,
a
(
x
)
b
0
oth.
t
(
x
) =
1
,
a
(
x
)
2
V
0
oth.
Test powinien by´c dopasowany do problemu a drzewo w miar ¾
e mo·
zliwo´sci
proste.
Jacek Kluska (Politechnika Rzeszowska)
2010
10 / 35
Przyk÷
ad - który atrybut wybra´c do podzia÷
u?
Aura
.
#
&
deszczowa
pochmurna
sloneczna
0,0
-
0,0,0
1,1,1
1,1,1,1
1,1
5/14
=
0.3571
4/14
=
0.2857
5/14
=
0.3571
Temperatura
.
#
&
niska
srednia
wysoka
0
0,0
0,0
1,1,1
1,1,1,1
1,1
4/14
=
0.2857
6/14
=
0.4286
4/14
=
0.2857
Jacek Kluska (Politechnika Rzeszowska)
2010
11 / 35
Przyk÷
ad - który atrybut wybra´c do podzia÷
u? - c.d.
Wilgotnosc
.
&
duza
normalna
0,0,0,0
0
1,1,1
1,1,1,1,1,1
7/14
=
0.5
7/14
=
0.5
Wiatr
.
&
nie
tak
0,0,0
0,0,0
1,1,1,1,1,1
1,1,1
8/14
=
0.5714
6/14
=
0.4286
Jacek Kluska (Politechnika Rzeszowska)
2010
12 / 35
Teoria: informacja i entropia
Informacja zawarta w zbiorze etykietowanych przyk÷
adów P
I
(
P
) =
∑
d
2
C
P
d
j
P
j
log
2
P
d
j
P
j
.
(mo·
ze by´c inny log
( )
ale konsekwentnie).
Entropia zbioru przyk÷
adów P ze wzgl ¾
edu na wynik r testu t
E
t ,r
(
P
) =
∑
d
2
C
P
d
t ,r
j
P
t ,r
j
log
2
P
d
t ,r
j
P
t ,r
j
jest du·
za, je·
zeli w´sród przyk÷
adów ze zbioru P, dla których test t daje
wynik r , rozk÷
ad na kategorie jest równomierny.
Jacek Kluska (Politechnika Rzeszowska)
2010
13 / 35
Teoria: ´srednia wa·
zona entropii i przyrost informacji
Entropia zbioru przyk÷
adów P ze wzgl ¾
edu na test t jest ´sredni ¾
a wa·
zon ¾
a
entropii dla poszczególnych wyników testu:
E
t
(
P
) =
∑
r
2
R
t
j
P
t ,r
j
j
P
j
E
t ,r
(
P
)
, E
t
(
P
) =
∑
d
2
C
P
d
j
P
j
log
2
P
d
j
P
j
Przyrost informacji (information gain) po zastosowania testu t do zbioru
przyk÷
adów P:
g
t
(
P
) =
I
(
P
)
E
t
(
P
)
.
g
t
= inf. przed rozdzieleniem “minus” inf. po rozdzieleniu. Miara
ró·
znorodno´sci klas. W w ¾
e´zle wybieramy test maksymalizuj ¾
acy przyrost
informacji:
max
t
f
g
t
(
P
)g
.
Informacja I
(
P
)
nie zale·
zy od ocenianego testu (dla zbioru przyk÷
adów
P), czyli minimalizujemy entropi ¾
e E
t
(
P
)
, a wi ¾
ec maksymalizujemy
ró·
znorodno´s´c klas.
Jacek Kluska (Politechnika Rzeszowska)
2010
14 / 35
Interpretacja entropii
Dla dwuelementowego zbioru kategorii C
= f
0, 1
g
,przyjmuj ¾
ac
p
=
P
0
t ,r
j
P
t ,r
j
)
I
(
P
) =
E
(
P
)
, p
=
P
0
j
P
j
)
E
t ,r
(
P
) =
E
(
P
)
E
(
P
) =
p log
2
p
(
1
p
)
log
2
(
1
p
)
0.0 0.2 0.4 0.6
0.8 1.0
0.0
0.5
1.0
p
E(p)
Maksymalna entropia jest zawarta w zbiorze przyk÷
adów o równomiernym
rozk÷
adzie kategorii. E
=
0 dla p
=
0 lub p
=
1, czyli informacja(entropia)
jest tym mniejsza, im bardziej wyra´zna jest przewaga jednej kategorii nad
drug ¾
a (w ¾
eze÷bardziej “czysty”).
Jacek Kluska (Politechnika Rzeszowska)
2010
15 / 35
Przyk÷
ad - obliczenia dla atrybutu “Aura”
Liczno´sci zbiorów potrzebne do wyznaczenia wartosci przyrostu informacji
dla testu to·
zsamo´sciowego na warto´sciach atrybutu “aura”.
C
= f
0, 1
g
, P
1
= jf
3, 4, 5, 7, 9, 10, 11, 12, 13
gj =
9,
P
0
= jf
1, 2, 6, 8, 14
gj =
5
P
Aura_sloneczna
= jf
1, 2, 8, 9, 11
gj =
5
P
1
Aura_sloneczna
= jf
9, 11
gj =
2
P
0
Aura_sloneczna
= jf
1, 2, 8
gj =
3
P
Aura_pochmurna
= jf
3, 7, 12, 13
gj =
4
P
1
Aura_pochmurna
= jf
3, 7, 12, 13
gj =
4
P
0
Aura_pochmurna
= j
∅
j =
0
P
Aura_deszczowa
= jf
4, 5, 6, 10, 14
gj =
5
P
1
Aura_deszczowa
= jf
4, 5, 10
gj =
3
P
0
Aura_deszczowa
= jf
6, 14
gj =
2
Jacek Kluska (Politechnika Rzeszowska)
2010
16 / 35
Przyk÷
ad - obliczenia dla atrybutu “Aura” - c.d.
E
Aura_sloneczna
(
P
) =
j
2
j
j
5
j
log
2
j
2
j
j
5
j
j
3
j
j
5
j
log
2
j
3
j
j
5
j
=
0.971
E
Aura_pochmurna
(
P
) =
j
4
j
j
4
j
log
2
j
4
j
j
4
j
j
0
j
j
4
j
log
2
j
0
j
j
4
j
=
0
E
Aura_deszczowa
(
P
) =
j
3
j
j
5
j
log
2
j
3
j
j
5
j
j
2
j
j
5
j
log
2
j
2
j
j
5
j
=
0.971
Jacek Kluska (Politechnika Rzeszowska)
2010
17 / 35
Przyk÷
ad - obliczenia dla atrybutu “aura” - c.d.
Entropia zbioru przyk÷
adów P ze wzgl ¾
edu na test t jest ´sredni ¾
a wa·
zon ¾
a
entropii dla poszczególnych wyników testu:
E
Aura
(
P
) =
∑
r
2
R
t
j
P
t ,r
j
j
P
j
E
t ,r
(
P
) =
P
Aura_sloneczna
j
P
1
j + j
P
0
j
E
Aura_sloneczna
(
P
) +
P
Aura_pochmurna
j
P
1
j + j
P
0
j
E
Aura_pochmurna
(
P
) +
P
Aura_deszczowa
j
P
1
j + j
P
0
j
E
Aura_deszczowa
(
P
)
E
Aura
(
P
) =
5
9
+
5
0.971
+
4
9
+
5
0
+
5
9
+
5
0.971
=
0.694
Informacja zawarta w zbiorze etykietowanych przyk÷
adów P
I
(
P
) =
∑
d
2
C
P
d
j
P
j
log
2
P
d
j
P
j
=
P
1
j
P
j
log
2
P
1
j
P
j
P
0
j
P
j
log
2
P
0
j
P
j
=
9
14
log
2
9
14
5
14
log
2
5
14
=
0.940
Przyrost informacji dla atrybutu “Aura”:
g
t
(
P
) =
I
(
P
)
E
t
(
P
) =
0.940
0.694
=
0.246
Jacek Kluska (Politechnika Rzeszowska)
2010
18 / 35
Przyk÷
ad - obliczenia dla atrybutu “Temperatura”
Liczno´sci zbiorów potrzebne do wyznaczenia wartosci przyrostu informacji
dla testu to·
zsamo´sciowego na warto´sciach atrybutu “Temperatura”.
C
= f
0, 1
g
, P
1
= jf
3, 4, 5, 7, 9, 10, 11, 12, 13
gj =
9,
P
0
= jf
1, 2, 6, 8, 14
gj =
5
P
Temp_wysoka
= jf
1, 2, 3, 13
gj =
4
P
1
Temp_wysoka
= jf
3, 13
gj =
2
P
0
Temp_wysoka
= jf
1, 2
gj =
2
P
Temp_srednia
= jf
4, 8, 10, 11, 12, 14
gj =
6
P
1
Temp_srednia
= jf
4, 10, 11, 12
gj =
4
P
0
Temp_srednia
= jf
8, 14
gj =
2
P
Temp_niska
= jf
5, 6, 7, 9
gj =
4
P
1
Temp_niska
= jf
5, 7, 9
gj =
3
P
0
Temp_niska
= jf
6
gj =
1
Jacek Kluska (Politechnika Rzeszowska)
2010
19 / 35
Przyk÷
ad - obliczenia dla atrybutu “Temperatura” - c.d.
E
Temp_wysoka
(
P
) =
j
2
j
j
4
j
log
2
j
2
j
j
4
j
j
2
j
j
4
j
log
2
j
2
j
j
4
j
=
1
E
Temp_srednia
(
P
) =
j
4
j
j
6
j
log
2
j
4
j
j
6
j
j
2
j
j
6
j
log
2
j
2
j
j
6
j
=
0.918
E
Temp_niska
(
P
) =
j
3
j
j
4
j
log
2
j
3
j
j
4
j
j
1
j
j
4
j
log
2
j
1
j
j
4
j
=
0.811
Jacek Kluska (Politechnika Rzeszowska)
2010
20 / 35
Przyk÷
ad - obliczenia dla atrybutu “Temperatura” - c.d.
Entropia zbioru przyk÷
adów P ze wzgl ¾
edu na test t jest ´sredni ¾
a wa·
zon ¾
a
entropii dla poszczególnych wyników testu:
E
Temperatura
(
P
) =
∑
r
2
R
t
j
P
t ,r
j
j
P
j
E
t ,r
(
P
) =
P
Temp_wysoka
j
P
1
j + j
P
0
j
E
Temp_wysoka
(
P
) +
P
Temp_srednia
j
P
1
j + j
P
0
j
E
Temp_srednia
(
P
) +
P
Temp_niska
j
P
1
j + j
P
0
j
E
Temp_niska
(
P
)
E
Temperatura
(
P
) =
4
9
+
5
1
+
6
9
+
5
0.918
+
4
9
+
5
0.811
=
0.911
Informacja zawarta w zbiorze etykietowanych przyk÷
adów P
I
(
P
) =
∑
d
2
C
P
d
j
P
j
log
2
P
d
j
P
j
=
P
1
j
P
j
log
2
P
1
j
P
j
P
0
j
P
j
log
2
P
0
j
P
j
=
9
14
log
2
9
14
5
14
log
2
5
14
=
0.940
Przyrost informacji dla atrybutu “Temperatura”:
g
t
(
P
) =
I
(
P
)
E
t
(
P
) =
0.940
0.911
=
0.029
Jacek Kluska (Politechnika Rzeszowska)
2010
21 / 35
Przyk÷
ad - obliczenia dla atrybutu “Wilgotnosc” - c.d.
C
= f
0, 1
g
, P
1
= jf
3, 4, 5, 7, 9, 10, 11, 12, 13
gj =
9,
P
0
= jf
1, 2, 6, 8, 14
gj =
5
P
Wilgotnosc_duza
= jf
1, 2, 3, 4, 8, 12, 14
gj =
7
P
1
Wilgotnosc_duza
= jf
3, 4, 12
gj =
3
P
0
Wilgotnosc_duza
= jf
1, 2, 8, 14
gj =
4
P
Wilgotnosc_normalna
= jf
5, 6, 7, 9, 10, 11, 13
gj =
7
P
1
Wilgotnosc_normalna
= jf
6
gj =
1
P
0
Wilgotnosc_normalna
= jf
5, 7, 9, 10, 11, 13
gj =
6
E
Wilgotnosc_duza
(
P
) =
j
3
j
j
7
j
log
2
j
3
j
j
7
j
j
4
j
j
7
j
log
2
j
4
j
j
7
j
=
0.985
E
Wilgotnosc_normalna
(
P
) =
j
1
j
j
7
j
log
2
j
1
j
j
7
j
j
6
j
j
7
j
log
2
j
6
j
j
7
j
=
0.592
Jacek Kluska (Politechnika Rzeszowska)
2010
22 / 35
Przyk÷
ad - obliczenia dla atrybutu “Wilgotnosc” - c.d.
Entropia zbioru przyk÷
adów P ze wzgl ¾
edu na test t jest ´sredni ¾
a wa·
zon ¾
a
entropii dla poszczególnych wyników testu:
E
Wilgotnosc
(
P
) =
∑
r
2
R
t
j
P
t ,r
j
j
P
j
E
t ,r
(
P
) =
P
Wilgotnosc_duza
j
P
1
j + j
P
0
j
E
Wilgotnosc_duza
(
P
) +
P
Wilgotnosc_normalna
j
P
1
j + j
P
0
j
E
Wilgotnosc_normalna
(
P
)
E
Wilgotnosc
(
P
) =
7
9
+
5
0.985
+
7
9
+
5
0.592
=
0.788
Informacja zawarta w zbiorze etykietowanych przyk÷
adów P
I
(
P
) =
∑
d
2
C
P
d
j
P
j
log
2
P
d
j
P
j
=
P
1
j
P
j
log
2
P
1
j
P
j
P
0
j
P
j
log
2
P
0
j
P
j
=
9
14
log
2
9
14
5
14
log
2
5
14
=
0.940
Przyrost informacji dla atrybutu “Wilgotnosc”:
g
t
(
P
) =
I
(
P
)
E
t
(
P
) =
0.940
0.788
=
0.152
Jacek Kluska (Politechnika Rzeszowska)
2010
23 / 35
Przyk÷
ad - obliczenia dla atrybutu “Wiatr” - c.d.
C
= f
0, 1
g
P
1
= jf
3, 4, 5, 7, 9, 10, 11, 12, 13
gj =
9, P
0
= jf
1, 2, 6, 8, 14
gj =
5
P
Wiatr_nie
= jf
1, 3, 4, 5, 8, 9, 10, 13
gj =
8
P
1
Wiatr_nie
= jf
3, 4, 5, 9, 10, 13
gj =
6
P
0
Wiatr_nie
= jf
1, 8
gj =
2
P
Wiatr_tak
= jf
2, 6, 7, 11, 12, 14
gj =
6
P
1
Wiatr_tak
= jf
7, 11, 12
gj =
3
P
0
Wiatr_tak
= jf
2, 6, 14
gj =
3
E
Wiatr_nie
(
P
) =
j
6
j
j
8
j
log
2
j
6
j
j
8
j
j
2
j
j
8
j
log
2
j
2
j
j
8
j
=
0.811
E
Wiatr_tak
(
P
) =
j
3
j
j
6
j
log
2
j
3
j
j
6
j
j
3
j
j
6
j
log
2
j
3
j
j
6
j
=
1
Jacek Kluska (Politechnika Rzeszowska)
2010
24 / 35
Przyk÷
ad - obliczenia dla atrybutu “Wiatr” - c.d.
Entropia zbioru przyk÷
adów P ze wzgl ¾
edu na test t jest ´sredni ¾
a wa·
zon ¾
a
entropii dla poszczególnych wyników testu:
E
Wiatr
(
P
) =
∑
r
2
R
t
j
P
t ,r
j
j
P
j
E
t ,r
(
P
) =
P
Wiatr_nie
j
P
1
j + j
P
0
j
E
Wiatr_nie
(
P
) +
P
Wiatr_tak
j
P
1
j + j
P
0
j
E
Wiatr_tak
(
P
)
E
Wiatr
(
P
) =
8
9
+
5
0.811
+
6
9
+
5
1
=
0.892
Informacja zawarta w zbiorze etykietowanych przyk÷
adów P
I
(
P
) =
∑
d
2
C
P
d
j
P
j
log
2
P
d
j
P
j
=
P
1
j
P
j
log
2
P
1
j
P
j
P
0
j
P
j
log
2
P
0
j
P
j
=
9
14
log
2
9
14
5
14
log
2
5
14
=
0.940
Przyrost informacji dla atrybutu “Wiatr”:
g
t
(
P
) =
I
(
P
)
E
t
(
P
) =
0.940
0.892
=
0.048
Jacek Kluska (Politechnika Rzeszowska)
2010
25 / 35
Przyk÷
ad - przyrost informacji w wierzcho÷
ku 1
Przyrost informacji dla atrybutu “Aura”: g
t
(
P
) =
0.246
Przyrost informacji dla atrybutu “Temperatura”: g
t
(
P
) =
0.029
Przyrost informacji dla atrybutu “Wilgotnosc”: g
t
(
P
) =
0.152
Przyrost informacji dla atrybutu “Wiatr”: g
t
(
P
) =
0.048
W w ¾
e´zle 1 wybieramy test maksymalizuj ¾
acy przyrost informacji:
max
t
f
g
t
(
P
)g
.
Wniosek: Atrybut “Aura” maksymalizuje przyrost informacji
)
wybieramy do podzia÷
u.
Jacek Kluska (Politechnika Rzeszowska)
2010
26 / 35
Przyk÷
ad - dalszy podzia÷atrybutu “Aura”
Aura
sloneczna
.
Temperatura
wysoka
.
srednia
#
&
niska
Aura
sloneczna
.
Wilgotnosc
du·
za
.
normalna
#
Aura
sloneczna
.
Wiatr
nie
.
tak
#
Który podzia÷wybra´c?
Jacek Kluska (Politechnika Rzeszowska)
2010
27 / 35
Przyk÷
ad - dalszy podzia÷
Przyrost informacji dla atrybutu “Temperatura”: g
t
(
P
) =
0.571
Przyrost informacji dla atrybutu “Wilgotnosc”: g
t
(
P
) =
0.971
Przyrost informacji dla atrybutu “Wiatr”: g
t
(
P
) =
0.020
Wybieramy test maksymalizuj ¾
acy przyrost informacji:
max
t
f
g
t
(
P
)g
.
Wniosek: Atrybut “Wilgotnosc” maksymalizuje przyrost informacji
)
wybieramy do podzia÷
u.
Podzia÷w oparciu o zysk informacyjny (Interactive Dichotomizer
version 3, ID3).
Proces budowy drzewa zatrzymuje si ¾
e gdy spe÷
nione jest kryterium
stopu (np. dalszy podzia÷nie jest mo·
zliwy).
Jacek Kluska (Politechnika Rzeszowska)
2010
28 / 35
Drzewa decyzyjne - indeks Giniego
Zamiast minimalizacji entropii E
t ,r
(
P
) =
∑
d
2
C
p
d
t ,r
log
2
p
d
t ,r
lepiej jest minimalizowa´c indeks Giniego (Gini index):
G
t ,r
(
P
) =
∑
d
2
C
p
d
t ,r
1
p
d
t ,r
0.0
0.2 0.4
0.6 0.8
1.0
0.0
0.5
1.0
p
E,G
Wykresy: E
=
p log
2
p
(
1
p
)
log
2
(
1
p
)
, Q
=
2p
(
1
p
)
Jacek Kluska (Politechnika Rzeszowska)
2010
29 / 35
Drzewa decyzyjne - indeks Giniego: przyk÷
ad
Kl1:4
Kl2:4
p
L
.
p
R
&
Kl1:3
Kl1:1
Kl2:1
Kl2:3
Entropia: C
= f
1, 2
g
, P
=
8, P
1
=
4, P
2
=
4
Atrybut L: P
L
=
4, P
1
L
=
3, P
2
L
=
1
E
L,1
(
P
) =
j
3
j
j
4
j
log
2
j
3
j
j
4
j
j
1
j
j
4
j
log
2
j
1
j
j
4
j
=
0.81128
E
L,2
(
P
) =
j
1
j
j
4
j
log
2
j
1
j
j
4
j
j
3
j
j
4
j
log
2
j
3
j
j
4
j
=
0.81128
E
L
(
P
) =
P
1
L
j
P
L
j
E
L,1
(
P
) +
P
2
L
j
P
L
j
E
L,2
(
P
) =
0.81128
Jacek Kluska (Politechnika Rzeszowska)
2010
30 / 35
Drzewa decyzyjne - indeks Giniego: przyk÷
ad, c.d.
Kl1:4
Kl2:4
p
L
.
p
R
&
Kl1:3
Kl1:1
Kl2:1
Kl2:3
Atrybut R: P
R
=
4, P
1
R
=
1, P
2
R
=
3
E
R,1
(
P
) =
j
1
j
j
4
j
log
2
j
1
j
j
4
j
j
3
j
j
4
j
log
2
j
3
j
j
4
j
=
0.81128
E
R,2
(
P
) =
j
1
j
j
4
j
log
2
j
1
j
j
4
j
j
3
j
j
4
j
log
2
j
3
j
j
4
j
=
0.81128
E
R
(
P
) =
P
1
R
j
P
R
j
E
R,1
(
P
) +
P
2
R
j
P
R
j
E
R,2
(
P
) =
0.81128
Jacek Kluska (Politechnika Rzeszowska)
2010
31 / 35
Drzewa decyzyjne - indeks Giniego: przyk÷
ad, c.d.
Kl1:4
Kl2:4
p
L
.
p
R
&
Kl1:3
Kl1:1
Kl2:1
Kl2:3
Entropia: C
= f
1, 2
g
, P
=
8, P
1
=
4, P
2
=
4
Informacja zawarta w zbiorze etykietowanych przyk÷
adów P
I
(
P
) =
P
1
j
P
j
log
2
P
1
j
P
j
P
2
j
P
j
log
2
P
2
j
P
j
=
4
8
log
2
4
8
4
8
log
2
4
8
=
1.0
Przyrost informacji wed÷
ug entropii:
Lewy: g
t
(
P
) =
I
(
P
)
E
t
(
P
) =
1
0.81128
=
0.18872
Prawy: g
t
(
P
) =
I
(
P
)
E
t
(
P
) =
1
0.81128
=
0.18872
Jacek Kluska (Politechnika Rzeszowska)
2010
32 / 35
Drzewa decyzyjne - indeks Giniego: przyk÷
ad, c.d.
Kl1:4
Kl2:4
p
L
.
p
R
&
Kl1:3
Kl1:1
Kl2:1
Kl2:3
Gini: C
= f
1, 2
g
, P
=
8, P
1
=
4, P
2
=
4
Atrybut L: P
L
=
4, P
1
L
=
3, P
2
L
=
1
G
L,1
(
P
) =
2
3
4
1
3
4
=
0.375
G
L,2
(
P
) =
2
1
4
1
1
4
=
0.375
G
L
(
P
) =
P
1
L
j
P
L
j
G
L,1
(
P
) +
P
2
L
j
P
L
j
G
L,2
(
P
) =
0.375
Jacek Kluska (Politechnika Rzeszowska)
2010
33 / 35
Drzewa decyzyjne - indeks Giniego: przyk÷
ad, c.d.
Kl1:4
Kl2:4
p
L
.
p
R
&
Kl1:3
Kl1:1
Kl2:1
Kl2:3
Gini: C
= f
1, 2
g
, P
=
8, P
1
=
4, P
2
=
4
Atrybut R: P
R
=
4, P
1
R
=
1, P
2
R
=
3
G
R,1
(
P
) =
2
1
4
1
1
4
=
0.375
G
R,2
(
P
) =
2
3
4
1
3
4
=
0.375
G
R
(
P
) =
P
1
R
j
P
R
j
G
R,1
(
P
) +
P
2
R
j
P
R
j
G
R,2
(
P
) =
0.375
Jacek Kluska (Politechnika Rzeszowska)
2010
34 / 35
Drzewa decyzyjne - indeks Giniego: przyk÷
ad, c.d.
Kl1:4
Kl2:4
p
L
.
p
R
&
Kl1:3
Kl1:1
Kl2:1
Kl2:3
Gini: C
= f
1, 2
g
, P
=
8, P
1
=
4, P
2
=
4
Informacja zawarta w zbiorze etykietowanych przyk÷
adów P
I
G
(
P
) =
2
P
1
j
P
j
1
P
1
j
P
j
!
+
2
P
2
j
P
j
1
P
2
j
P
j
!
=
2
4
8
1
4
8
+
2
4
8
1
4
8
=
1.0
Przyrost informacji wed÷
ug indeksu Giniego jest wi ¾
ekszy ni·
z dla entropii:
Lewy: g
t
(
P
) =
I
G
(
P
)
G
L
(
P
) =
1
0.375
=
0.625
>
0.18872
Prawy: g
t
(
P
) =
I
G
(
P
)
G
R
(
P
) =
1
0.375
=
0.625
>
0.18872
Jacek Kluska (Politechnika Rzeszowska)
2010
35 / 35
Document Outline
- Przykład drzewa
- Przykład drzewa - rozwiazanie
- Przykład - reguły wynikajace z drzewa
- Przykład - reguły wynikajace z drzewa - c.d.
- Rekurencyjna definicja drzewa decyzyjnego
- Załozenia: zmienne, klasy, typy zmiennych, kategorie
- Zstepujaca budowa drzewa decyzyjnego (Top-Down Induction of Decision Trees)
- Zstepujaca budowa drzewa decyzyjnego (Top-Down Induction of Decision Trees) - c.d.
- Testy atrybutów
- Przykład - który atrybut wybrac do podziału?
- Przykład - który atrybut wybrac do podziału? - c.d.
- Teoria: informacja i entropia
- Teoria: srednia wazona entropii i przyrost informacji
- Interpretacja entropii
- Przykład - obliczenia dla atrybutu “Aura”
- Przykład - obliczenia dla atrybutu “Aura” - c.d.
- Przykład - obliczenia dla atrybutu “aura” - c.d.
- Przykład - obliczenia dla atrybutu “Temperatura”
- Przykład - obliczenia dla atrybutu “Temperatura” - c.d.
- Przykład - obliczenia dla atrybutu “Temperatura” - c.d.
- Przykład - obliczenia dla atrybutu “Wilgotnosc” - c.d.
- Przykład - obliczenia dla atrybutu “Wilgotnosc” - c.d.
- Przykład - obliczenia dla atrybutu “Wiatr” - c.d.
- Przykład - obliczenia dla atrybutu “Wiatr” - c.d.
- Przykład - przyrost informacji w wierzchołku 1
- Przykład - dalszy podział atrybutu “Aura”
- Przykład - dalszy podział
- Drzewa decyzyjne - indeks Giniego
- Drzewa decyzyjne - indeks Giniego: przykład
- Drzewa decyzyjne - indeks Giniego: przykład, c.d.
- Drzewa decyzyjne - indeks Giniego: przykład, c.d.
- Drzewa decyzyjne - indeks Giniego: przykład, c.d.
- Drzewa decyzyjne - indeks Giniego: przykład, c.d.
- Drzewa decyzyjne - indeks Giniego: przykład, c.d.
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
12 drzewko decyzyjne do identyfikacji ccp, Towaroznawstwo UR, SEMESTR VI, SBŻ
Drzewa decyzyjne 2009 id 143623 Nieznany
Drzewa decyzyjne 20090518
hd 06 drzewa decyzyjne id 19989 Nieznany
drzewa decyzyjne
więcej podobnych podstron