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 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ó
Nó
Cada nó 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 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-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 nó 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 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.
–
–
–
–
(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