3 2 Árvores de Decisão

Prévia do material em texto

FORMAÇÃO 
INTELIGÊNCIA 
ARTIFICIAL E MACHINE 
LEARNING
MACHINE LEARNING – ESTUDANDO ALGORITMOS
ÁRVOES DE DECISÃO PARTE II
Prof. Fernando Amaral –Todos os Diretos Reservados
Criando a Árvore de Decisão?
➢Temos 4 atributos “candidatos” a ser o nó raiz.
➢Qual devemos escolher?
➢Buscar o que tenha maior ganho de informação!
Entropia
Teoria da Informação
𝐸 𝑆 = − σ𝑖=1
𝑛 𝑝𝑖 log2 𝑝𝑖
Se todas as instancias de S pertencem a mesma classe E(S) = 0
Se S contem o mesmo número de instancia para cada classe, E(s) = 1
Cálculo da Entropia - Classe
𝐸 𝑆 = − σ𝑖=1
𝑛 𝑝𝑖 log2 𝑝𝑖
𝐸 𝑆 = −
9
14
log2
9
14
+ −
5
14
log2
5
14
𝐸 𝑆 = 0,94
Cálculo da Entropia - Outlook
𝐸 𝑆 = − σ𝑖=1
𝑛 𝑝𝑖 log2 𝑝𝑖
Outlook (sunny – para yes e no)
𝐸 𝑆 = −
2
5
log2
2
5
+ −
3
5
log2
3
5
= 0,97
Outlook (overcast – para yes e no)
𝐸 𝑆 = −
4
4
log2
4
4
+ −
0
4
log2
0
4
=0
Outlook (rainy – para yes e no)
𝐸 𝑆 = −
3
5
log2
3
5
+ −
2
5
log2
2
5
=0,97
Cálculo da Entropia - Temperature
𝐸 𝑆 = − σ𝑖=1
𝑛 𝑝𝑖 log2 𝑝𝑖
Temperature (hot – para yes e no)
𝐸 𝑆 = −
2
4
log2
2
4
+ −
2
4
log2
2
4
= 1
Temperature (mild – para yes e no)
𝐸 𝑆 = −
4
6
log2
4
6
+ −
2
6
log2
2
6
=0,91
Temperature (cold – para yes e no)
𝐸 𝑆 = −
3
4
log2
3
4
+ −
1
4
log2
1
4
=0,81
Cálculo da Entropia - Humidity
𝐸 𝑆 = − σ𝑖=1
𝑛 𝑝𝑖 log2 𝑝𝑖
Humidity (high – para yes e no)
𝐸 𝑆 = −
3
7
log2
3
7
+ −
4
7
log2
4
7
= 0,98
Humidity (normal – para yes e no)
𝐸 𝑆 = −
6
7
log2
6
7
+ −
1
7
log2
1
7
=0,59
Cálculo da Entropia - Windy
𝐸 𝑆 = − σ𝑖=1
𝑛 𝑝𝑖 log2 𝑝𝑖
Windy (True – para yes e no)
𝐸 𝑆 = −
3
6
log2
3
6
+ −
3
6
log2
3
6
= 1
Windy (False – para yes e no)
𝐸 𝑆 = −
6
8
log2
6
8
+ −
2
8
log2
2
8
=0,81
Ganho de Informação (Information Gain)
IG 𝑆, 𝐴 = 𝐸 𝑆 − σ𝑖=1
𝑛 𝑆𝑖
𝑆
𝐸 𝑆𝑖
Outlook
IG 𝑆, 𝐴 = 0,94 −
5
14
∗ 0,97 −
4
14
∗ 0 −
5
14
∗ 0,97 = 0,2471
Entropia 
Classe
Proporção 
sunny
Entropia
sunny
Proporção 
overcast
Entropia
overcast
Proporção 
rainy
Entropia
rainy
sunny overcast rainy
Ganho de Informação (Information Gain)
IG 𝑆, 𝐴 = 𝐸𝑛𝑡𝑟𝑜𝑝𝑖𝑎 𝑆 − σ𝑖=1
𝑛 𝑆𝑖
𝑆
𝐸𝑛𝑡𝑟𝑜𝑝𝑖𝑎 𝑆𝑖
Outlook
IG 𝑆, 𝐴 = 0,94 −
5
14
∗ 097 −
4
14
∗ 0 −
5
14
∗ 0,97 = 0,2471
Temperatures
IG 𝑆, 𝐴 = 0,94 −
4
14
∗ 1 −
6
14
∗ 0,91 −
4
14
∗ 0,81 = 0,0328
Humidy
IG 𝑆, 𝐴 = 0,94 −
7
14
∗ 0,97 −
7
14
∗ 0,59 = 0,16
Windy
IG 𝑆, 𝐴 = 0,94 −
6
14
∗ 1 −
8
14
∗ 0,81 = 0,048
Primeiro nodo
outlook
sunny rainyovercast
yes
Particionando sunny
outlook
sunny
rainyovercast
Entropia Classe
𝐸 𝑠𝑢𝑛𝑛𝑦 = −
3
5
log2
3
5
+ −
2
5
log2
2
5
= 0,97
yes
Cálculo da Entropia - Temperature
outlook
sunny
rainyovercast
Temperatura (hot para yes e no)
𝐸 𝑆 = −
0
2
log2
0
2
+ −
2
2
log2
2
2
= 0
Temperatura (mild para yes e no)
𝐸 𝑆 = −
1
2
log2
1
2
+ −
1
2
log2
1
2
= 1
Temperatura (cool para yes e no)
𝐸 𝑆 = −
1
1
log2
1
1
+ −
0
1
log2
0
1
= 0
yes
Cálculo da Entropia - Humidity
outlook
sunny
rainyovercast
Humidity (high para yes e no)
𝐸 𝑆 = −
0
3
log2
0
3
+ −
3
3
log2
3
3
= 0
Humidity (normal para yes e no)
𝐸 𝑆 = −
2
2
log2
2
2
+ −
0
2
log2
0
2
= 0
yes
Cálculo da Entropia - Windy
outlook
sunny
rainyovercast
windy (False para yes e no)
𝐸 𝑆 = −
1
3
log2
1
3
+ −
2
3
log2
2
3
= 0,91
Humidity (True para yes e no)
𝐸 𝑆 = −
1
2
log2
1
2
+ −
1
2
log2
1
2
= 1
yes
Ganho de Informação (Information Gain)
IG 𝑆, 𝐴 = 𝐸𝑛𝑡𝑟𝑜𝑝𝑖𝑎 𝑆 − σ𝑖=1
𝑛 𝑆𝑖
𝑆
𝐸𝑛𝑡𝑟𝑜𝑝𝑖𝑎 𝑆𝑖
Temperatures
IG 𝑆, 𝐴 = 0,97 −
2
5
∗ 0 −
2
5
∗ 1 −
1
5
∗ 0 = 0,57
Humidity
IG 𝑆, 𝐴 = 0,97 −
3
5
∗ 0 −
2
5
∗ 0 = 0,97
Windy
IG 𝑆, 𝐴 = 0,97 −
3
5
∗ 0,91 −
2
5
∗ 1 = 0,024
Próximo nodo
outlook
sunny rainyovercast
humdity
high normal
yes
yesno
Continuando
outlook
sunny rainyovercast
humidity
high rain
yes
yesno
Windy = 0,97
Continuando
outlook
sunny rainyovercast
humidity
high rain
yes
yesno
windy
False true
yes
no
Finalizando
outlook
sunny rainyovercast
humidity
high rain
yes
yesno
windy
False true
yes no