INF 1771 – Inteligência Artificial
Aula 13 – Á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 nó 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-])= - log - log2
= 0.940
2
14 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