INF 1771 Inteligência Artificial  
Aula 14 Á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ó  
Nó  
Cada folha da árvore específica o  
valor a ser retornado se aquela folha  
for alcançada.  
Ramo  
Ramo  
Ramo  
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 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-60, > 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  
Obj.  
Esp.  
Atributos  
Exemplo  
Alt.  
Bar  
S/S  
Fam.  
Pes.  
Pre.  
Chov.  
Res.  
Tipo  
Est.  
X1  
X2  
Sim  
Não  
Não  
Sim  
Algumas  
Cheio  
$$$  
Não  
Sim  
Fran.  
Tai.  
0-10  
Sim  
Sim  
Não  
Sim  
Sim  
Não  
Não  
Não  
Não  
Sim  
Não  
Sim  
Não  
Sim  
Não  
Não  
Sim  
Sim  
Não  
Sim  
Sim  
Não  
Sim  
Não  
Não  
Sim  
Sim  
Não  
Não  
Não  
Sim  
Sim  
Não  
Sim  
Sim  
Não  
Sim  
Não  
Sim  
Não  
Sim  
Não  
Sim  
Não  
Sim  
$
Não  
Não  
Sim  
Não  
Sim  
Sim  
Sim  
Sim  
Não  
Não  
Não  
Não  
Não  
Não  
Sim  
Sim  
Não  
Sim  
Não  
Sim  
Não  
Não  
30-60 Não  
0-10 Sim  
10-30 Sim  
X3  
Algumas  
Cheio  
$
$
Ham.  
Tai.  
X4  
X5  
Cheio  
$$$  
$$  
$
Fran.  
Ital.  
>60  
Não  
Sim  
Não  
Sim  
Não  
X6  
Algumas  
Nenhuma  
Algumas  
Cheio  
0-10  
0-10  
0-10  
>60  
X7  
Ham.  
Tai.  
X8  
$$  
$
X9  
Ham.  
Ital.  
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
5
4
7
6
9
8
12  
10 11  
Tipo?  
Pessoas?  
Francês  
Italiano  
Tailandês  
Hamburger  
Nenhuma  
Algumas  
Cheio  
1
5
6
4
2
8
3
7
12  
9
1
3
6
8
4
2
12  
10  
11  
7
11  
5
9
10  
Tipo é um atributo ruim, pois ele deixa 4  
resultados sem nenhuma conclusão.  
Não  
Sim  
Famindo?  
Pessoas é um atributo bom, pois 2 resultados  
dele levam a conclusões diretas.  
Gerando Árvores de Decisão a partir de  
Exemplos  
Algoritmo:  
(1) Enquanto existirem exemplos positivos e negativos, deve-se escolher o  
melhor atributo para dividi-los.  
(2) Se todos os exemplos restantes forem positivos (ou todos negativos), então  
podemos responder Sim ou Não.  
(3) Se não existirem exemplos restantes, retorna um valor padrão calculado a  
partir da classificação da maioria dos atributos do pai.  
(4) Se não existirem atributo restantes, mas ainda existirem exemplos  
positivos e negativos temos um problema.  
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 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 nclasses é 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.  
(2) Gera-se uma hipótese h (árvore de decisão) com base no Conjunto de  
Treinamento.  
(3) Para cada exemplo do Conjunto de Teste, classifica-se o exemplo utilizando  
a árvore de decisão criada a partir do conjunto de treinamento.  
(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  
Leitura Complementar  
Russell, S. and Novig, P. Artificial Intelligence: a  
Modern Approach, 2nd Edition, Prentice-Hall,  
2003.  
Capítulo 18: Learning from Observations