INF 1771 Inteligência Artificial  
Aula 15 Árvores de Decisão  
Edirlei Soares de Lima  
<elima@inf.puc-rio.br>  
Árvores de Decisão  
Uma das formas de algoritmo de aprendizado  
mais simples e de maior sucesso.  
Uma árvore de decisão tem como entrada um  
objeto ou situação descritos por um conjunto de  
atributos e como saída uma “decisão”  
(previsão do valor de saída dada a entrada).  
Uma árvore de decisão toma as suas decisões  
através de uma sequência de testes.  
Árvores de Decisão  
Cada interno da árvore  
corresponde a um teste do valor de  
uma propriedade.  
Raiz  
Ramo  
Ramo  
Os ramos dos nós são rotulados  
com os resultados possíveis do  
teste.  
Nó  
Nó  
Ramo  
Cada nó folha da árvore especifica  
o valor a ser retornado se aquela  
folha for alcançada.  
Ramo  
Ramo  
Nó  
Folha  
Folha  
A representação de uma árvore de  
decisão é bem natural para os  
seres humanos.  
Ramo  
Ramo  
Exemplo Restaurante  
Problema: Esperar por uma mesa em um  
restaurante.  
O objetivo é aprender uma definição para o  
predicado “vai esperar”.  
Primeiramente é necessário definir quais  
atributos estão disponíveis para descrever  
alguns exemplos nesse domínio.  
Exemplo Restaurante  
Atributos:  
Alternativa: Verdadeiro se existe um restaurante alternativo  
adequado nas proximidades.  
Bar: Verdadeiro se o restaurante tem uma área de bar confortável  
para ficar esperando.  
Sex/Sab: Verdadeiro se o dia da semana for sexta ou sábado.  
Faminto: Verdadeiro se estamos com fome.  
Pessoas: Quantas pessoas estão no restaurante (os valores são  
Nenhuma, Algumas e Cheio).  
Preço: Preço do restaurante de ($, $ $, $$$).  
Chuva: Verdadeiro se está chovendo lá fora.  
Reserva: Verdadeiro se nós fizemos uma reserva.  
Tipo: Tipo de restaurante (Francês, Italiano, Tailandês,  
Hambúrguer).  
EstimativaEspera: Tempo de espera estimado (00-10, 10-30, 30-  
6
0, > 60 minutos).  
Exemplo Restaurante  
Pessoas?  
Nenhuma Algumas  
Cheio  
Não  
Sim  
EstimativaEspera?  
>
60  
30-60 10-30  
0-10  
Não  
Alternativa?  
Faminto?  
Sim  
Não  
Sim  
Não  
Sim  
Reserva?  
Sex/Sab?  
Sim  
Alternativa?  
Não  
Sim  
Não  
Sim  
Não  
Sim  
Bar?  
Sim Não  
Sim  
Sim  
Chovendo?  
Não  
Sim  
Sim  
Não  
Não  
Não  
Sim  
Sim  
Gerando Árvores de Decisão a partir de Exemplos  
É possível gerar uma árvore de decisão a partir de um  
conjunto de exemplos.  
Exemplos positivos são aqueles que levam a uma  
resposta positiva.  
Exemplo: “vai esperar” = Sim.  
Exemplos negativos são aqueles que levam a uma  
resposta negativa.  
Exemplo: “vai esperar” = Não.  
Conjunto de Treinamento  
Atributos  
Obj.  
Exemplo  
Alt.  
Bar  
S/S  
Fam.  
Pes.  
Pre.  
Chov.  
Res. Tipo  
Est.  
Esp.  
X1  
X2  
Sim  
Não  
Não  
Sim  
Algumas  
Cheio  
$$$  
Não  
Sim  
Não  
Não  
Não  
Sim  
Fran.  
Tai.  
0-10  
Sim  
Sim  
Não  
Sim  
Sim  
Não  
Sim  
Não  
Não  
Não  
Não  
Sim  
Sim  
Sim  
Não  
Sim  
Não  
$
Não  
Não  
Sim  
Não  
30-60 Não  
0-10 Sim  
10-30 Sim  
X3  
Algumas  
Cheio  
$
Ham.  
Tai.  
X4  
$
X5  
Cheio  
$$$  
Fran.  
>60  
Não  
X6  
Não  
Não  
Não  
Sim  
Sim  
Não  
Não  
Não  
Não  
Sim  
Não  
Sim  
Algumas  
Nenhuma  
Algumas  
$$  
$
Sim  
Sim  
Sim  
Sim  
Não  
Sim  
Ital.  
Ham.  
Tai.  
0-10  
0-10  
0-10  
Sim  
Não  
Sim  
X7  
X8  
$$  
X9  
Não  
Sim  
Não  
Sim  
Sim  
Sim  
Não  
Sim  
Sim  
Sim  
Não  
Sim  
Não  
Sim  
Não  
Sim  
Cheio  
$
Sim  
Não  
Não  
Não  
Não  
Sim  
Não  
Não  
Ham.  
Ital.  
>60  
Não  
X10  
X11  
X12  
Cheio  
$$$  
$
10-30 Não  
0-10 Não  
30-60 Sim  
Nenhuma  
Cheio  
Tai.  
$
Ham.  
Gerando Árvores de Decisão a partir de Exemplos  
Seguindo o principio de Ockham, devemos  
encontrar a menor árvore de decisão que seja  
consistente com os exemplos de treinamento.  
Qualquer fenómeno deve assumir apenas as premissas  
estritamente necessárias à explicação do fenómeno e eliminar  
todas as que não causariam qualquer diferença aparente nas  
predições da hipótese ou teoria.”  
A idéia básica do algoritmo é testar os atributos  
mais importantes primeiro.  
O atributo mais importante é aquele que faz mais diferença  
para a classificação de um exemplo.  
Dessa forma, esperamos conseguir a classificação  
correta com um pequeno número de testes.  
Gerando Árvores de Decisão a partir de Exemplos  
Conjunto de Treinamento  
1
2
3 4 6 8 12  
5 7 9 10 11  
Tipo?  
Pessoas?  
Francês  
Italiano Tailandês Hamburger  
Nenhuma  
Algumas  
Cheio  
1
5
6
4 8  
3 12  
7 9  
1
3 6 8  
4 12  
10  
2 11  
7
11  
2 5 9 10  
Famindo?  
Tipo é um atributo ruim, pois ele deixa 4  
resultados sem nenhuma conclusão.  
Não  
Sim  
Pessoas é um atributo bom, pois 2 resultados  
dele levam a conclusões diretas.  
Gerando Árvores de Decisão a partir de Exemplos  
Algoritmo:  
(
se escolher o melhor atributo para dividi-los.  
1) Enquanto existirem exemplos positivos e negativos, deve-  
(
negativos), então podemos responder Sim ou Não.  
2) Se todos os exemplos restantes forem positivos (ou todos  
(
padrão calculado a partir da classificação da maioria dos  
atributos do nó pai.  
3) Se não existirem exemplos restantes, retorna um valor  
(
exemplos positivos e negativos temos um problema.  
4) Se não existirem atributo restantes, mas ainda existirem  
Gerando Árvores de Decisão a partir de Exemplos  
Quando não existem atributos restantes, mas ainda  
existem exemplos positivos e negativos significa que:  
Esses exemplos têm exatamente a mesma descrição, mas  
classificações diferentes. Isso acontece quando alguns dos  
dados estão incorretos, ou seja há ruído nos dados.  
Também acontece quando os atributos não dão informação  
suficiente para descrever a situação completamente, ou  
quando o domínio é realmente não-determinístico.  
Uma saída simples do problema é a utilização de uma votação  
majoritária.  
Gerando Árvores de Decisão a partir de Exemplos  
Pessoas?  
Nenhuma Algumas  
Cheio  
Não  
Sim  
Faminto?  
Não  
Sim  
Não  
Tipo?  
Francês  
Italiano Hambúrguer Tailandês  
Sim  
Não  
Sim  
Sex/Sab?  
Não  
Sim  
Não  
Sim  
Escolhendo os Melhores Atributos  
Qual é o melhor atributo?  
[
29+, 35-]  
[
21+, 5-]  
[8+, 30-]  
Escolhendo os Melhores Atributos  
Entropia  
Caracteriza a (im)pureza de uma coleção arbitrária de  
exemplos.  
Dado uma coleção S contendo exemplos positivos (+) e  
negativos () de algum conceito alvo, a entropia de S  
relativa a esta classificação booleana é:  
Entropia(S) =-p+ log2 p+ - p- log2 p-  
p+ é a proporção de exemplos positivos em S.  
pé a proporção de exemplos negativos em S.  
Escolhendo os Melhores Atributos  
Exemplo: Sendo S uma coleção de 14 exemplos de  
treinamento de algum conceito boleano, incluindo 9  
exemplos positivos e 5 negativos [9+, 5-].  
A entropia de S relativa a classificação é:  
9
9 5  
5
Entropia([9+, 5-]) = - log2 - log2  
= 0.940  
1
4
14 14  
14  
A função entropia relativa a uma classificação varia  
entre 0 e 1.  
Escolhendo os Melhores Atributos  
Generalizando para o caso de um atributo  
alvo aceitar n diferentes valores, a entropia  
de S relativa a esta classificação de n–  
classes é definida como:  
n
Entropia(S) = pi log2 pi  
i=1  
Medindo Desempenho  
Um algoritmo de aprendizado é bom se ele  
produz hipóteses que conseguem prever a  
classificação de exemplos não vistos.  
A maneira mais simples de se medir o  
desempenho de um método de aprendizado  
é realizando a classificação de um conjunto  
de exemplos de teste.  
Medindo Desempenho  
Processo de avaliação:  
(1) Divide-se o conjunto total de exemplos conhecidos em dois  
conjuntos:  
Conjunto de Treinamento.  
Conjunto de Teste.  
(
Conjunto de Treinamento.  
2) Gera-se uma hipótese h (árvore de decisão) com base no  
(
exemplo utilizando a árvore de decisão criada a partir do  
conjunto de treinamento.  
3) Para cada exemplo do Conjunto de Teste, classifica-se o  
(
4) Verifica-se a quantidade de exemplos de teste classificados  
corretamente e calcula-se a porcentagem de acertos.  
5) Escolhe-se aleatoriamente um novo conjunto de exemplos  
(
de treinamento (normalmente com um numero maior de  
exemplos) e repete-se novamente o processo.  
Medindo Desempenho  
Tamanho do Conjunto de Treinamento