FACENS – Engenharia da Computação
Inteligência Artificial
Árvores de Decisão
Aprendizado de Máquina – Tópicos
• Definições
• Algoritmos
• Exemplo
Árvores de Decisão - Definições
• Uma árvore de decisão utiliza uma estratégia de
dividir-para-conquistar:
— um problema complexo é decomposto em subproblemas mais simples.
— recursivamente a mesma estratégia é aplicada a
cada subproblema.
• Discriminação de uma árvore vem da:
— Divisão do espaço definido pelos atributos em subespaços.
— A cada sub-espaço é associada uma classe.
• Algoritmos
—ID3, CART, C4.5
Árvores de Decisão - Definições
• Possui regras para classificar dados usando
atributos.
• A árvore possui nós de decisão e nós folhas.
• Um nó de decisão é basicamente uma escolha
entre N possibilidades (arcos). Cada um destes
arcos possui um dos possíveis valores do
atributo.
• Um nó folha é um resultado da classificação da
árvore.
Árvores de Decisão - Exemplo
Jogar Tenis?
Tempo
ensolarado
chuvoso
Umidade
Não
nublado
Vento
alta
normal
forte
fraco
Não
Sim
Não
Sim
Árvores de Decisão – ID3
• Um algoritmo para construir uma árvore de
decisão.
• Proposto por J. Ross Quinlan in 1979.
• Utiliza da Teoria da Informação de Shannon
(1948).
• Constrói a árvore em uma estrutura top down.
• O conceito de ganho de informação é usado
para selecionar os atributos mais significativos
para a classificação.
Árvores de Decisão – ID3
• Um algoritmo para construir uma árvore de
decisão.
• Proposto por J. Ross Quinlan in 1979.
• Utiliza da Teoria da Informação de Shannon
(1948).
• Constrói a árvore em uma estrutura top down.
• O conceito de ganho de informação é usado
para selecionar os atributos mais significativos
para a classificação.
Árvores de Decisão – Entropia
• Uma fórmula para calcular o quanto uma
amostra é homogênea.
• Uma amostra completamente homogênia tem
entropia zero.
• Uma amostra completamente heterogência tem
entropia 1.
• A fórmula da entropia é:
Árvores de Decisão – Ganho de Informação
• Uma fórmula para calcular o quanto uma
amostra é homogênea.
• Uma amostra completamente homogênia tem
entropia zero.
• Uma amostra completamente heterogência tem
entropia 1.
• A fórmula da entropia é:
Árvores de Decisão – Ganho de Informação
• O ganho de informação é baseado na redução de
entropia depois que um conjunto de dados é dividido a
partir de um atributo.
• Qual atributo gera os ramos mais homogêneos?
— Primeira calcula-se a entropia total do conjunto de dados
— O conjunto de dados é então dividido usando os diferentes
atributos
— A entropia de cada ramo é calculada e subtraída da entropia
total antes da divisão
— O resultado é o ganho de informação (IG)
— O atributo com o maior IG é escolhido como nó de decisão
• Se o ramo tiver entropia zero, ele é um nó folha
• O processo se repete recursivamente
Árvores de Decisão – Exemplo
Pessoa
Cabelo
(cm)
Peso
Idade Classe
Homer
0
100
36
M
Marge
25
60
34
F
Bart
5
20
10
M
Lisa
25
50
8
F
Maggie
10
8
1
F
Abe
3
70
70
M
Selma
20
55
41
F
Otto
25
65
38
M
Krusty
15
90
45
M
E(S )  
 p 
p
 
log2 
pn
p

n


 n 
n

log2 
pn
p

n


E(4F,5M) = -(4/9)log2(4/9) - (5/9)log2(5/9)
= 0.9911
sim
não
Cabelo <= 12?
Dividindo por
Cabelo
Ganho( A)  E( Atual)   E(Subconjunt
os)
Ganho(Cabelo <= 12) = 0.9911 – (4/9 * 0.8113 + 5/9 * 0.9710 ) = 0.0911
E(S )  
 p 
p
 
log2 
pn
p

n


 n 
n

log2 
pn
p

n


E(4F,5M) = -(4/9)log2(4/9) - (5/9)log2(5/9)
= 0.9911
sim
não
Peso <= 60?
Dividindo por
Peso
Ganho( A)  E( Atual)   E(Subconjunt
os)
Ganho(Peso <= 60) = 0.9911 – (5/9 * 0.7219 + 4/9 * 0 ) = 0.5900
E(S )  
 p 
p
 
log2 
pn
p

n


 n 
n

log2 
pn
p

n


E(4F,5M) = -(4/9)log2(4/9) - (5/9)log2(5/9)
= 0.9911
sim
não
Idade <= 40?
Dividindo por
Idade
Ganho( A)  E( Atual)   E(Subconjunt
os)
Ganho(Idade <= 40) = 0.9911 – (6/9 * 1 + 3/9 * 0.9183 ) = 0.0183
Árvores de Decisão – Exemplo
• Dos três atributos, peso foi o
melhor. Entretanto, nem todos
foram classificados corretamente.
• Sendo assim, rodamos o processo
de novo para o subconjunto da
esquerda!
sim
não
Peso <= 60?
• Como classificar estes novos
casos?
sim
não
Cabelo <= 12?
We need don’t need to keep the data
around, just the test conditions.
Weight <= 160?
yes
How would
these people
be classified?
no
Hair Length <= 2?
yes
Male
no
Female
Male
Referências
• Quinlan, J.R. 1986, Machine Learning, 1, 81
• http://www2.cs.uregina.ca/~dbd/cs831/notes/ml/dtrees/4_dtrees2.ht
ml
• Professor Sin-Min Lee, SJSU.
http://cs.sjsu.edu/~lee/cs157b/cs157b.html
• ID3 Algorithm. Allan Neymark. CS157B – Spring 2007.