Drzewa decyzyjne
Jacek Kluska
Politechnika Rzeszowska
2010
Jacek Kluska (Politechnika Rzeszowska)
2010
1 / 35
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