14-Aprendizagem_de_Arvores_de_Decisao

Prévia do material em texto

APRENDIZADO	
  POR	
  ÁRVORES	
  
DE	
  DECISÃO	
  
	
  
	
  
	
  
Modelos	
  básicos	
  para	
  aprendizado	
  
supervisionado	
  
¨  Muitos	
  algoritmos	
  de	
  aprendizagem	
  podem	
  ser	
  vistos	
  como	
  
derivados	
  de:	
  
¤  Classificadores	
  lineares	
  
¤  Classificadores	
  Bayesianos	
  
¤  Árvores	
  de	
  decisão	
  
Stuart	
  Russel	
  e	
  Peter	
  Norving	
  -­‐	
  “Inteligência	
  ArLficial”	
  -­‐	
  
cap	
  18.	
  
Aprendizagem	
  de	
  Árvores	
  de	
  Decisão	
  
Aprendizagem	
  de	
  Árvore	
  de	
  Decisão	
  
4	
  
n  A	
  representação	
  usada	
  é	
  uma	
  árvore	
  de	
  decisão,	
  com	
  um	
  
viés	
  para	
  árvores	
  de	
  decisão	
  simples.	
  
n  Faz	
  busca	
  no	
  espaço	
  de	
  árvores	
  de	
  decisão,	
  das	
  árvores	
  
simples	
  para	
  as	
  mais	
  complexos.	
  
n  Toma	
  como	
  entrada	
  um	
   	
  ou	
   	
  descrito	
  por	
  um	
  
conjunto	
  de	
   (propriedades).	
  
n  Retorna	
  uma	
   	
  –	
  o	
  valor	
  de	
  saída	
  previsto	
  de	
  acordo	
  
com	
  a	
  entrada.	
  
n  Os	
  atributos	
  de	
  entrada	
  e	
  o	
  valor	
  de	
  saída	
  podem	
  ser	
  
discretos	
  ou	
  conZnuos.	
  
Árvore	
  de	
  Decisão	
  
5	
  
n  É	
  uma	
  árvore	
  na	
  qual	
  cada	
  nó	
   é	
   	
  com	
  um	
  
.	
  
n  Os	
   	
  que	
  saem	
  de	
  um	
  nó	
  com	
  o	
   	
  são	
  rotulados	
  
com	
  cada	
  possível	
   .	
  
n  As	
   	
  da	
  árvore	
  são	
  rotuladas	
  com	
  a	
  
.	
  
n  Obtém	
  uma	
  decisão	
  executando	
  uma	
  sequência	
  de	
  testes.	
  
n  Cada	
  nó	
  não	
  folha	
  da	
  árvore	
  corresponde	
  a	
  um	
  teste	
  do	
  valor	
  
de	
  um	
  atributo.	
  
Exemplo	
  de	
  árvore	
  de	
  decisão	
  
6	
  
n  Esperar	
  ou	
  não	
  uma	
  mesa	
  em	
  um	
  restaurante?	
  
n  Objetivo:	
  aprender	
  uma	
  definição	
  para	
  o	
  
	
  (booleano).	
  
n  Atributos	
  disponíveis:	
  
n  Alterna,va:	
  há	
  um	
  outro	
  restaurante	
  apropriado	
  por	
  perto?	
  
n  Bar:	
  o	
  restaurante	
  tem	
  uma	
  área	
  de	
  bar	
  confortável	
  para	
  esperar?	
  
n  Sex/Sab:	
  hoje	
  é	
  sextas	
  ou	
  sábado?	
  
n  Faminto:	
  estamos	
  com	
  fome?	
  
n  Clientes:	
  quantas	
  pessoas	
  estão	
  no	
  restaurante?	
  
n  Preço:	
  a	
  faixa	
  de	
  preços	
  do	
  restaurante.	
  
n  Chovendo:	
  está	
  chovendo	
  do	
  lado	
  de	
  fora?	
  
n  Reserva:	
  fizemos	
  uma	
  reserva?	
  
n  Tipo:	
  qual	
  o	
  Lpo	
  do	
  restaurante?	
  
n  Espera	
  es,mada:	
  o	
  tempo	
  de	
  espera	
  esLmado	
  pelo	
  o	
  gerente.	
  
7	
  
Clientes? 
Bar? 
Sex/Sab? Reserva? 
Faminto? Alternativa? 
EsperaEstimada? 
Chovendo? 
Não Não 
Não 
Não 
Não 
Sim Sim Sim 
Sim 
Sim 
Sim 
Alternativa? 
Sim Sim 
Nenhum alguns cheio 
>60 30-60 10-30 0-10 
 Não Sim Não Sim 
Não Sim Não Sim Não Sim 
Não Sim Não Sim 
Árvore	
  de	
  decisão	
  para	
  o	
  problema	
  do	
  restaurante	
  -­‐	
  Russel	
  
Problemas	
  na	
  aprendizagem	
  de	
  árvore	
  de	
  
decisão	
  
¨  Tendo	
  em	
  conta	
  alguns	
  exemplos	
  de	
  treinamento,	
  que	
  árvore	
  de	
  
decisão	
  deve	
  ser	
  gerada?	
  
¨  Uma	
  árvore	
  de	
  decisão	
  pode	
  representar	
  qualquer	
  função	
  discreta	
  
dos	
  recursos	
  de	
  entrada.	
  
¨  Você	
  precisa	
  de	
  um	
  viés.	
  Exemplo,	
  preferir	
  a	
  árvore	
  menor.	
  Com	
  
menos	
  profundidade?	
  Com	
  menor	
  número	
  de	
  nós?	
  Quais	
  as	
  
árvores	
  são	
  os	
  melhores	
  previsores	
  de	
  dados	
  não	
  vistos	
  ainda?	
  
¨  Como	
  você	
  deve	
  construir	
  uma	
  árvore	
  de	
  decisão?	
  O	
  espaço	
  de	
  
árvores	
  de	
  decisão	
  é	
  demasiado	
  grande	
  para	
  a	
  pesquisa	
  
sistemáLca	
  pela	
  árvore	
  de	
  decisão	
  menor.	
  	
  
Expressividade	
  de	
  árvores	
  de	
  decisão	
  
9	
  
n  Qualquer	
  hipótese	
  de	
  árvore	
  de	
  decisão	
  específica	
  para	
  o	
  predicado	
  
objeLvo	
   pode	
  ser	
  vista	
  como	
  uma	
  asserção	
  da	
  forma:	
  
n  Onde	
  cada	
  condição	
  Pi(s)	
  é	
  uma	
  conjunção	
  de	
  testes	
  que	
  	
  correspondem	
  
a	
  um	
  caminho	
  da	
  raiz	
  até	
  uma	
  folha	
  da	
  árvore	
  com	
  resultado	
  posiLvo.	
  
Expressividade	
  de	
  árvores	
  de	
  decisão	
  
10	
  
n  Uma	
  árvore	
  de	
  decisão:	
  
n  Descreve	
  um	
  relacionamento	
  entre	
  o	
  predicado	
  objeLvo	
  e	
  alguma	
  
combinação	
  lógica	
  de	
  atributos.	
  
n  Árvores	
  de	
  decisão	
  não	
  podem	
  representar	
  testes	
  que	
  se	
  referem	
  
a	
  dois	
  ou	
  mais	
  objetos	
  diferentes.	
  
	
  Existe	
  um	
  restaurante	
  mais	
  barato	
  por	
  perto?	
  
n  Árvores	
  de	
  decisão	
  são	
  completamente	
  expressivas	
  dentro	
  da	
  
classe	
  de	
  linguagens	
  proposicionais.	
  
n  Qualquer	
  função	
  booleana	
  pode	
  ser	
  escrita	
  como	
  uma	
  árvore	
  de	
  decisão.
	
  	
  
Exemplo	
  de	
  árvore	
  de	
  decisão	
  
Programa	
  lógico	
  equivalente	
  
Expressividade	
  de	
  árvores	
  de	
  decisão	
  
13	
  
n  Para	
  qualquer	
  função	
  booleana	
  podemos	
  fazer	
  com	
  que	
  cada	
  linha	
  
da	
  Tabela	
  Verdade	
  =	
  	
  um	
  caminho	
  na	
  árvore.	
  
n  Representação	
  exponencialmente	
  grande.	
  
n  Tabela	
  Verdade	
  tem	
  um	
  número	
  exponencial	
  de	
  linhas.	
  
n  Árvores	
  de	
  decisão	
  podem	
  representar	
  muitas	
  funções	
  com	
  
árvores	
  muito	
  menores.	
  
n  Árvores	
  de	
  decisão	
  servem	
  para	
  alguns	
  Lpos	
  de	
  funções	
  e	
  não	
  são	
  
boas	
  para	
  outros:	
  
:	
  Função	
  paridade	
  e	
  Função	
  maioria	
  –	
  árvores	
  de	
  decisão	
  
exponencialmente	
  grande	
  no	
  tamanho	
  da	
  entrada.	
  
n  Infelizmente	
  não	
  existe	
  uma	
  espécie	
  de	
  representação	
  que	
  seja	
  
eficiente	
  para	
  todos	
  os	
  Lpos	
  de	
  funções.	
  
Problemas	
  apropriados	
  para	
  o	
  uso	
  de	
  árvores	
  
de	
  decisão	
  
14	
  
n  Instâncias	
  são	
  representadas	
  através	
  de	
  pares	
  atributo-­‐valor.	
  
n  Cada	
  atributo	
  assume	
  um	
  número	
  pequeno	
  de	
  possíveis	
  valores	
  
disjuntos	
  (por	
  exemplo,	
  Temperatura	
  =	
  	
  Quente,	
  Moderado,	
  Frio).	
  
n  A	
  função	
  tem	
  valores	
  discretos	
  (V/F,	
  	
  1/2/3).	
  
n  Os dados de treinamento permitem	
  descrições	
  disjuntas.	
  
n  Os	
  dados	
  de	
  treinamento	
  podem	
  conter	
  erros.	
  
n  Os	
  dados	
  de	
  treinamento	
  podem	
  conter	
  valores	
  de	
  atributos	
  
indefinidos.	
  
Aplicação	
  de	
  árvores	
  de	
  decisão	
  
15	
  
n  Muitos	
  problemas	
  práLcospossuem	
  as	
  caracterísLcas	
  para	
  
aplicação	
  de	
  árvores	
  de	
  decisão.	
  
n  Aprendizado	
  uLlizando	
  árvore	
  de	
  decisão	
  já	
  foi	
  aplicado	
  a	
  
problemas	
  como:	
  
n  Classificar	
  os	
  pacientes	
  médicos	
  pela	
  doença.	
  
n  Causa	
  de	
  maus	
  funcionamentos	
  de	
  equipamentos.	
  
n  A	
  probabilidade	
  de	
  candidatos	
  a	
  emprésLmo	
  ficarem	
  inadimplentes.	
  
n  Entre	
  outros...	
  
Induzindo	
  árvores	
  de	
  decisão	
  
16	
  
n  Induzindo	
  árvores	
  de	
  decisão	
  por	
  meio	
  de	
  exemplos.	
  
n  Um	
   	
  é	
  descrito	
  pelo	
   e	
  o	
  
.	
  
n  è	
  classificação	
  do	
  exemplo.	
  
n  Predicado	
  objeLvo	
  =	
  verdadeiro	
  è	
  exemplo	
  posiLvo.	
  
n  Predicado	
  objeLvo	
  =	
  falso	
  	
  	
  	
  	
  	
  	
  	
  	
  è	
  	
  exemplo	
  negaLvo.	
  
n  Um	
  conjunto	
  completo	
  de	
  exemplos	
  é	
  chamado	
  de	
  
.	
  
Induzindo	
  árvores	
  de	
  decisão	
  
17	
  
n  Encontrar	
  uma	
  AD(h(x))	
  que	
  concorde	
  com	
  o	
  conjunto	
  de	
  
treinamento	
  parece	
  dilcil,	
  mas	
  pode	
  ser	
  trivial.	
  
n  Podemos	
  construir	
  uma	
  AD	
  que	
  tem	
  um	
  caminho	
  para	
  uma	
  folha	
  
correspondente	
  a	
  cada	
  exemplo.	
  
n  Infelizmente	
  ela	
  não	
  terá	
  muito	
  a	
  informar	
  sobre	
  qualquer	
  outros	
  
casos	
  (não	
  fará	
  boas	
  generalizações).	
  
n  Ela	
  memoriza	
  as	
  observações,	
  mas	
  não	
  extrai	
  qualquer	
  padrão.	
  
O	
  problema	
  com	
  a	
  AD	
  trivial	
  
18	
  
n  Pela	
  Navalha	
  de	
  Ockham	
  devemos	
  encontrar	
  a	
  menor	
  AD	
  
consistente	
  com	
  os	
  exemplos	
  (intratável).	
  
n  Podemos	
  resolver	
  o	
  problema	
  intratável	
  uLlizando	
  algumas	
  
heurísLcas	
  para	
  encontrarmos	
  árvores	
  pequenas.	
  
n  Algoritmo	
  de	
  aprendizagem	
  em	
  árvore	
  de	
  decisão	
  
n  A	
  ideia	
  é	
  testar	
  o	
   –	
  aquele	
  que	
  faz	
  a	
  maior	
  
diferença	
  para	
  a	
  classificação	
  dos	
  exemplos.	
  
n  Obter	
  a	
  classificação	
  correta	
  com	
  um	
  pequeno	
  número	
  de	
  testes	
  è	
  
caminhos	
  curtos	
  e	
  árvore	
  pequenas.	
  
19	
  
Conjunto	
  de	
  treinamento	
  para	
  o	
  exemplo	
  do	
  restaurante	
  
Ex Alt Bar Sex Fam Cli Pre Chu Res Tipo Tem Meta
X1 Sim Não Não Sim Alg $$$ Não Sim Fra 0-10 Sim
X2 Sim Não Não Sim Che $ Não Não Tai 30-60 Não
X3 Não Sim Não Não Alg $ Não Não Ham 0-10 Sim
X4 Sim Não Sim Sim Che $ Sim Não Tai 10-30 Sim
X5 Sim Não Sim Não Che $$$ Não Sim Fra >60 Não
X6 Não Sim Não Sim Alg $$ Sim Sim Ita 0-10 Sim
X7 Não Sim Não Não Ne $ Sim Não Ham 0-10 Não
X8 Não Não Não Sim Alg $$ Sim Sim Tai 0-10 Sim
X9 Não Sim Sim Não Che $ Sim Não Ham >60 Não
X10 Sim Sim Sim Sim Che $$$ Não Sim Ita 10-30 Não
X11 Não Não Não Não Ne $ Não Não Tai 0-10 Não
X12 Sim Sim Sim Sim Che $ Não Não Ham 30-60 Sim
Aplicação	
  do	
  algoritmo	
  de	
  aprendizagem	
  
20	
  
Ex Alt Bar Sex
X1 Sim Não Não
X2 Sim Não Não
X3 Não Sim Não
X4 Sim Não Sim
X5 Sim Não Sim
X6 Não Sim Não
X7 Não Sim Não
X8 Não Não Não
X9 Não Sim Sim
X10 Sim Sim Sim
X11 Não Não Não
X12 Sim Sim Sim
Objetivo 
Sim 1 3 4 6 8 12 
Não 2 5 7 9 10 11 
alternativa? 
1 4 12 
2 5 10 
3 6 8 
7 9 11 
sim não 
Bar? 
3 6 12 
7 9 10 
1 4 8 
2 5 11 
sim não 
Sex/Sab? 
4 12 
5 9 10 
1 3 6 8 
2 7 11 
sim não 
Aplicação	
  do	
  algoritmo	
  de	
  aprendizagem	
  
21	
  
Ex Alt Bar Sex
X1 Sim Não Não
X2 Sim Não Não
X3 Não Sim Não
X4 Sim Não Sim
X5 Sim Não Sim
X6 Não Sim Não
X7 Não Sim Não
X8 Não Não Não
X9 Não Sim Sim
X10 Sim Sim Sim
X11 Não Não Não
X12 Sim Sim Sim
Objetivo 
Sim 1 3 4 6 8 12 
Não 2 5 7 9 10 11 
faminto? 
1 4 6 8 12 
2 10 
3 
5 7 9 11 
sim não 
clientes? 
 
7 11 
1 3 6 8 
 
nen alg cheio 
4 12 
2 5 9 10 preço? 
3 4 12 
2 7 9 11 
6 8 
 
$ $$ $$$ 
1 
5 10 
Exercício	
  
22	
  
n  Fazer	
  a	
  representação	
  dos	
  atributos	
  abaixo	
  da	
  forma	
  
especificada	
  anteriormente.	
  
n  Chovendo?	
  
n  Reserva?	
  
n  Tipo?	
  
n  Tempo	
  de	
  espera?	
  
n  Qual	
  é	
  o	
  atributo	
  que	
  separa	
  melhor	
  os	
  exemplos?	
  
Qual	
  é	
  o	
  atributo	
  que	
  melhor	
  separa	
  os	
  
exemplos?	
  
23	
  
n  O	
  quanto	
  cada	
  atributo	
  classifica:	
  
n  Alterna,va,	
  Bar,	
  Sex/Sab,	
  Faminto,	
  Chovendo,	
  Reserva,	
  Tipo:	
  zero	
  
exemplos.	
  
n  Clientes:	
  6	
  exemplos.	
  
n  Preço	
  e	
  Espera	
  es,mada:	
  2	
  exemplos.	
  
n  O	
  atributo	
   	
  classifica	
  6	
  exemplos.	
  
n  Então	
  ele	
  será	
  a	
  raiz	
  da	
  árvore	
  de	
  decisão:	
  
clientes? 
não 
7 11 
1 3 6 8 
sim 
nen alg cheio 
4 12 ? 
2 5 9 10 
Escolha	
  dos	
  atributos	
  
24	
  
n  Depois	
  da	
  escolha	
  do	
  atributo	
   ficamos	
  com	
  um	
  
conjunto	
  misto	
  de	
  exemplos	
  se	
  o	
  valor	
  for	
  cheio.	
  
n  Depois	
  que	
  o	
  primeiro	
  teste	
  de	
  atributo	
  separa	
  os	
  exemplos,	
  
cada	
  resultado	
  é	
  um	
  novo	
  problema	
  de	
  aprendizagem	
  em	
  
AD.	
  
n  Com	
  menos	
  exemplos	
  (os	
  que	
  ainda	
  não	
  foram	
  classificados	
  -­‐	
  2	
  5	
  9	
  10	
  
4	
  e	
  12)	
  e	
  um	
  atributo	
  a	
  menos	
  (Lra-­‐se	
  clientes).	
  
n  Exercício:	
  Aplique	
  o	
  algoritmo	
  de	
  aprendizagem	
  de	
  AD	
  
para	
  os	
  exemplos	
  anteriores.	
  
Nova	
  instância	
  do	
  problema	
  com	
  menos	
  
exemplos	
  e	
  menos	
  atributos	
  
25	
  
alternativa? 
4 12 
2 5 10 
 
9 
sim não 
Bar? 
12 
9 10 
4 
2 5 
sim não 
Sex/Sab? 
4 12 
5 9 10 
 
2 
sim não 
faminto? 
4 12 
2 10 
 
5 9 
sim não 
preço? 
4 12 
2 9 
 
5 10 
Chovendo? 
4 
9 
12 
2 5 10 
sim não 
Reserva? 
 
5 10 
4 12 
2 9 
sim não 
Tipo? 
4 
2 
Fra Tai Ita Ham 
12 
9 
 
5 
TempoEspera? 
4 
10 
12 
2 
10-30 30-60 >60 
$ $$$ 
 
10 
 
5 9 
Qual	
  é	
  o	
  atributo	
  que	
  melhor	
  separa	
  os	
  
exemplos	
  restantes?	
  
26	
  
n  Faminto,	
  preço,	
  reserva	
  e	
  ,po	
  classificam	
  2	
  exemplos.	
  
n  Podemos	
  escolher	
  qualquer	
  um	
  deles	
  (heurísLca	
  gulosa).	
  
Clientes? 
Faminto? Não 
7 11 
Sim 
1 3 6 8 
? 
Nenhum alguns cheio 
Não 
5 9 
Não Sim 
Casos	
  a	
  considerar	
  na	
  escolha	
  de	
  um	
  novo	
  
atributo	
  
27	
  
n  Se	
  existem	
  alguns	
  exemplos	
  posiLvos	
  e	
  alguns	
  negaLvos,	
  
escolha	
  o	
  melhor	
  atributo	
  para	
  dividi-­‐los.	
  
n  Se	
  todos	
  os	
  exemplos	
  restantes	
  forem	
  posiLvos	
  (ou	
  
negaLvos),terminamos.	
  
n  Se	
  não	
  resta	
  nenhum	
  atributo,	
  mas	
  há	
  exemplos	
  posiLvos	
  e	
  
negaLvos	
  –	
  descrições	
  iguais	
  com	
  classificações	
  diferentes	
  =	
  
nos	
  dados.	
  
Algoritmo ID3 (Inductive Decision Tree) 
Função APRENDIZAGEM-EM-AD (exemplos, atributos, padrão) retorna uma AD 
 entradas: exemplos, conjunto de exemplos 
 atributos, conjunto de atributos 
 padrão, valor-padrão para o predicado de objetivo 
 
 se exemplos é vazio então 
 retornar padrão 
 senão se todos os exemplos têm a mesma classificação então 
 retornar a classificação 
 senão se atributos é vazio então 
 retornar VALOR-DA-MAIORIA(exemplos) 
 senão 
 melhor ß ESCOLHER-ATRIBUTO(atributos, exemplo) 
 árvore ß uma nova ad com teste de raiz melhor 
 m ß VALOR-DA-MAIORIA(exemplosi) 
 para cada valor vi de melhor faça 
 exemplosi ß {elementos de exemplos com melhor = vi) 
 subárvore ß APRENDIZAGEM-EM-AD(exemplosi,atributos-melhor, m) 
 adicionar uma ramificação a árvore com rótulo vi e subárvore subárvore 
 retornar árvore 
Árvore	
  resultante	
  da	
  aplicação	
  do	
  algoritmo	
  ID3	
  
29	
  
Clientes? 
Faminto? Não Sim 
Tipo? 
Nenhum alguns cheio 
Não 
Sim Não Sim Sex/sab? 
Não Sim 
Não Sim 
 Fra Ita Tai Ham 
 Não Sim 
O	
  algoritmo	
  poderia	
  
encontrar	
  uma	
  AD	
  diferente	
  
para	
  o	
  mesmo	
  conjunto	
  de	
  
treinamento?	
  
	
   	
  Por	
  que?	
  
	
   	
  Qual	
  seria?	
  
A	
  árvore	
  resultante	
  
30	
  
n  É	
  diferente	
  da	
  árvore	
  original.	
  
n  Mas	
  a	
  hipótese	
  concorda	
  com	
  todos	
  os	
  exemplos	
  e	
  é	
  
consideravelmente	
  mais	
  simples	
  do	
  que	
  a	
  árvore	
  original.	
  
n  Chovendo	
  e	
  Reserva	
  ficaram	
  de	
  fora	
  porque	
  a	
  árvore	
  não	
  
necessita	
  deles	
  para	
  classificar	
  os	
  exemplos.	
  
n  Se	
  Lvéssemos	
  um	
  conjunto	
  de	
  treinamento	
  maior,	
  com	
  
certeza	
  a	
  árvore	
  ficaria	
  mais	
  parecida	
  com	
  a	
  original.	
  
Escolha	
  de	
  testes	
  de	
  atributos	
  
31	
  
n  Esquema	
  de	
  aprendizagem	
  da	
  AD:	
  
n  Projetado	
  para	
  minimizar	
  a	
  profundidade	
  da	
  árvore	
  final.	
  
:	
  escolher	
  o	
  atributo	
  que	
  melhor	
  fornece	
  uma	
  classificação	
  exata	
  
dos	
  exemplos.	
  
:	
  divide	
  os	
  exemplos	
  em	
  conjuntos	
  que	
  são	
  
todos	
  posiLvos	
  ou	
  todos	
  negaLvos.	
  
n  Clientes	
  não	
  é	
  perfeito,	
  mas	
  é	
  “bastante	
  bom”.	
  
:	
  deixa	
  os	
  conjuntos	
  de	
  exemplos	
  com	
  a	
  
mesma	
  proporção	
  do	
  conjunto	
  original.	
  
n  Tipo	
  é	
  um	
  atributo	
  “realmente	
  inúLl”.	
  
QuanLdade	
  de	
  informação	
  fornecida	
  pelo	
  
atributo	
  
32	
  
n  Como	
  medimos	
  um	
  “atributo	
  muito	
  bom”	
  ou	
  um	
  “atributo	
  
realmente	
  inúLl”?	
  
n  A	
  medida:	
  
n  Deve	
  ter	
  o	
  valor	
  máximo	
  quando	
  o	
  atributo	
  é	
  perfeito.	
  
n  E	
  o	
  valor	
  mínimo	
  quando	
  o	
  atributo	
  for	
  completamente	
  inúLl.	
  
n  Uma	
  medida	
  apropriada	
  seria	
  a	
  
fornecida	
  pelo	
  atributo.	
  
n  Isto	
  é	
  feito	
  por	
  meio	
  da	
  teoria	
  da	
  informação.	
  
Entropia	
  
33	
  
n  Medida	
  comumente	
  usada	
  na	
  teoria	
  da	
  informação.	
  
n  Caracteriza	
  a	
  impureza	
  de	
  uma	
  coleção	
  de	
  exemplos.	
  
n  Seja	
  S	
  uma	
  coleção	
  de	
  exemplos	
  posiLvos	
  e	
  negaLvos	
  de	
  
algum	
  conceito	
  objeLvo	
  lógico,	
  a	
  entropia	
  de	
  S:	
  
S
S
 em negativos exemplos de proporção a é Θp e
 em positivos exemplos de proporção a é p onde ⊕
ΘΘ⊕⊕ −−≡ pppp 22 loglog Entropia
Cálculo	
  de	
  Entropia	
  –	
  Exemplo	
  
34	
  
n  Suponha	
  que	
  S	
  seja	
  uma	
  coleção	
  de	
  14	
  exemplos	
  de	
  algum	
  conceito	
  
lógico:	
  
n  9	
  exemplos	
  são	
  posiLvos	
  e	
  5	
  são	
  negaLvos	
  [9+,	
  5-­‐]	
  
n  Entropia=0,	
  se	
  todos	
  os	
  exemplos	
  de	
  S	
  pertencem	
  à	
  mesma	
  classe	
  (todos	
  
posiLvos	
  ou	
  todos	
  negaLvos).	
  
n  Entropia=1,	
  quando	
  S	
  contém	
  um	
  número	
  igual	
  de	
  exemplos	
  posiLvos	
  e	
  
negaLvos	
  (exemplo	
  do	
  restaurante).	
  
n  Se	
  S	
  contém	
  números	
  desiguais	
  de	
  exemplos	
  posiLvos	
  e	
  negaLvos	
  a	
  
entropia	
  está	
  entre	
  0	
  e	
  1.	
  
0.940 5-]) ,9Entropia([
)145(log)145()149(log)149( 5-]) ,9Entropia([ 22
=+
−−≡+
Medida	
  de	
  Ganho	
  de	
  informação	
  
35	
  
n  A	
  medida	
  da	
  efeLvidade	
  de	
  um	
  atributo	
  para	
  classificar	
  os	
  
dados	
  de	
  treinamento	
  
=	
  redução	
  esperada	
  da	
  entropia	
  
causada	
  pelo	
  parLcionamento	
  dos	
  exemplos	
  de	
  S	
  por	
  um	
  
atributo	
  A	
  
( )
v. valor tem A atributo o qual o para S de osubconjunt o é vS -
 A.atributo
 o para valores possíveis os todos de conjunto o é valores(A) -
:onde
∑
∈
=
 valores(A) v
vS
S )Entropia(S - )Entropia(S A)Ganho(S, v
Medida	
  de	
  Ganho	
  de	
  informação	
  –	
  
Exemplo	
  para	
  o	
  atributo	
  Clientes	
  
36	
  
( )
0.5410.918 )( -0 )( -0 )( - 1 Clientes)Ganho(S,
0.918)()log(-)()log(- )Entropia(S
positivos) (todos 0)()log(-)()log(- )Entropia(S
negativos) (todos 0)()log(-)()log(- )Entropia(S
igual) é negativos e positivos de (# 1)()log(-)()log(- )Entropia(S
)Entropia(S )( - 
)Entropia(S )( -)Entropia(S )( - )Entropia(S Clientes)Ganho(S,
)Entropia(S - )Entropia(S Clientes)Ganho(S,
],4[2S ],0[4S ],2[0S ,6-][6 S
12
6
12
4
12
2
6
4
26
4
6
2
26
2
cheio
4
0
24
0
4
4
24
4
alguns
2
2
22
2
2
0
22
0
nenhum
12
6
212
6
12
6
212
6
cheio12
6
alguns12
4
nenhum12
2
 cheio) alguns, (nenhum, v
vS
S
cheioalgunsnenhum
v
==
==
==
==
===
=
=
−+=−+=−+=+=
∑
∈
clientes? 
 
7 11 
1 3 6 8 
 
nen alg cheio 
4 12 
2 5 9 10 
Medida	
  de	
  Ganho	
  de	
  informação	
  –	
  
Exemplo	
  para	
  o	
  atributo	
  Tipo	
  
37	
  
( )
0)1( )1-( )1-( )1-( - 1 Tipo)Ganho(S,
igual) é negativos e positivos
 exemplos de número o ossubconjunt os todos (em
1 )Entropia(S)Entropia(S )Entropia(S )Entropia(S
igual) é negativos e positivos exemplos de (# 1 )Entropia(S
)Entropia(S )( -)Entropia(S )( - 
)Entropia(S )( -)Entropia(S )( - )Entropia(S Tipo)Ganho(S,
)Entropia(S - )Entropia(S Tipo)Ganho(S,
],2[2S ],2[2S
 ],1[1S ],1[1S
 ,6-][6 S
12
4
12
4
12
2
12
2
HamTaiItaFra
Ham12
4
Tai12
4
Ita12
2
Fra12
2
 ) Hamburger Tailandês, Italiano, (Francês, v
vS
S
HamburgerTailandês
ItalianoFrancês
v
==
====
=
=
=
−+=−+=
−+=−+=
+=
∑
∈
Tipo? 
4 8 
2 11 
6 
10 
Fra Tai Ita Ham 
3 12 
7 9 
1 
5 
Conclusões	
  sobre	
  a	
  Medida	
  de	
  Ganho	
  de	
  
Informação	
  
38n  O	
  atributo	
  Clientes	
  é	
  melhor	
  do	
  que	
  o	
  atributo	
  Tipo.	
  
n  Clientes	
  tem	
  maior	
  ganho	
  de	
  informação	
  para	
  separar	
  os	
  exemplos.	
  
n  Tipo	
  é	
  um	
  atributo	
  inúLl	
  para	
  classificar	
  os	
  exemplos	
  	
  
n  Ganho(S,	
  Tipo)	
  =	
  0	
  
n  O	
  ganho	
  de	
  informação	
  deve	
  ser	
  calculado	
  para	
  todos	
  os	
  atributos	
  
e	
  o	
  conjunto	
  S	
  de	
  exemplos.	
  
n  Clientes	
  será	
  o	
  atributo	
  com	
  maior	
  ganho.	
  
n  Após	
  a	
  escolha	
  de	
  Clientes	
  como	
  a	
  raiz	
  da	
  árvore,	
  o	
  novo	
  conjunto	
  
S	
  se	
  torna	
  Scheio[2+,	
  4-­‐]	
  e	
  Entropia(Scheio)=0.918	
  
n  Novamente	
  o	
  ganho	
  de	
  informação	
  deve	
  ser	
  calculado	
  para	
  todos	
  os	
  
atributos	
  e	
  o	
  novo	
  conjunto	
  S.	
  
Exercício	
  
39	
  
n  Calcule o ganho de informação para os outros atributos 
do restaurante, considerando que o atributo Clientes já 
foi escolhido como raiz da árvore. 
n  Continue o algoritmo de aprendizagem calculando o 
ganho de informação para os atributos, para provar a 
árvore de decisão que foi induzida no slide 24. 
Como	
  avaliar	
  um	
  algoritmo	
  de	
  aprendizagem?	
  
40	
  
n  É	
  um	
  bom	
  algoritmo	
  se	
  ele	
  produz	
  hipóteses	
  que	
  classificam	
  
(predizem)	
  bem	
  exemplos	
  ainda	
  não	
  vistos.	
  
n  A	
   	
  é	
  boa	
  se	
  ela	
  se	
  torna	
  verdadeira.	
  
n  Como	
  avaliar	
  a	
  qualidade	
  de	
  uma	
  hipótese?	
  
n  Podemos	
  checar	
  sua	
  previsão	
  com	
  uma	
  classificação	
  correta	
  que	
  já	
  
conhecemos.	
  
n  Conjunto	
  de	
  exemplos	
  conhecidos	
  =	
   .	
  
Metodologia	
  para	
  avaliação	
  de	
  desempenho	
  de	
  
um	
  algoritmo	
  
41	
  
n  Coletar	
  um	
  grande	
  conjunto	
  de	
  exemplos.	
  
n  Dividi-­‐lo	
  em	
  dois	
  conjuntos	
  disjuntos:	
  
n  Conjunto	
  de	
  treinamento	
  e	
  conjunto	
  de	
  teste	
  
n  Aplicar	
  o	
  algoritmo	
  ao	
  conjunto	
  de	
  treinamento,	
  gerando	
  uma	
  
hipótese	
  h.	
  
n  Medir	
  a	
  quanLdade	
  de	
  exemplos	
  do	
  conjunto	
  de	
  teste	
  classificados	
  
corretamente	
  por	
  h.	
  
n  RepeLr	
  as	
  etapas	
  1	
  a	
  4	
  para:	
  
n  Diferentes	
  tamanhos	
  de	
  conjuntos	
  de	
  treinamento.	
  
n  Diferentes	
  conjuntos	
  de	
  treinamento	
  de	
  cada	
  tamanho.	
  
Curva	
  de	
  aprendizagem	
  
42	
  
n  É	
  traçada	
  com	
  o	
  conjunto	
  de	
  dados	
  obLdos	
  da	
  metodologia	
  
anterior.	
  
n  Conjunto	
  de	
  treinamento	
  aumenta	
  è	
  qualidade	
  da	
  previsão	
  
aumenta.	
  
n  Bom	
  sinal	
  de	
  que	
  existe	
  um	
  padrão	
  nos	
  dados	
  e	
  o	
  algoritmo	
  
está	
  capturando	
  este	
  padrão.	
  
Curva	
  de	
  aprendizagem	
  
43	
  
Ruído	
  e	
  superadaptação	
  (overfi4ng)	
  
44	
  
n  O	
  algoritmo	
  ID3	
  faz	
  crescer	
  cada	
  ramo	
  da	
  árvore	
  o	
  suficiente	
  
para	
  classificar	
  perfeitamente	
  os	
  exemplos	
  de	
  treino.	
  
n  Problemas:	
  
n  Quando	
  existe	
   ou	
   nos	
  dados,	
  ou	
  
n  Quando	
  o	
   não	
  
consLtuindo	
  uma	
  amostra	
  representaLva	
  da	
  verdadeira	
  função	
  
objeLvo.	
  
n  Nestes	
  casos	
  ID3	
  pode	
  produzir	
  árvores	
  que	
  se	
   	
  aos	
  
exemplos	
  de	
  treino	
  -­‐	
  isto	
  é,	
  aprendem	
  inclusive	
  os	
  ruídos	
  e	
  os	
  erros.	
  
Definição	
  de	
  superadaptação	
  
45	
  
n  A	
  superadaptação	
  afligi	
  todo	
  Lpo	
  de	
  algoritmo	
  de	
  
aprendizagem,	
  não	
  apenas	
  algoritmos	
  para	
  árvores	
  de	
  
decisão.	
  
o)treinament de conjunto do fora exemplos incluindo (i.e. exemplos
dos ãodistribuiç a toda sobre que do erro menor tem mas
treino, de exemplos os sobre que do erro menor tenha h que tal
, aalternativ hipótese alguma existe se treino de dados os
 hipótese Uma . hipóteses de espaço um Dado
hh
h
Hh
HhH
ʹ′
ʹ′
∈ʹ′
∈ overfit
Exemplo	
  de	
  superadaptação	
  
46	
  
Como	
  evitar	
  a	
  superadaptação	
  
47	
  
n  Fazer	
  a	
  árvore	
  parar	
  de	
  crescer	
  antes	
  que	
  ela	
  alcance	
  o	
  ponto	
  
onde	
  ela	
  classifique	
  perfeitamente	
  os	
  exemplos	
  de	
  treino.	
  
n  Para	
  isso	
  temos	
  que	
  acompanhar	
  as	
  porcentagens	
  de	
  previsões	
  
corretas	
  tanto	
  no	
  conjunto	
  de	
  teste	
  quanto	
  no	
  conjunto	
  de	
  
treinamento.	
  
n  Um	
  atributo	
  com	
  ganho	
  de	
  informação	
  perto	
  de	
  zero	
  tem	
  grandes	
  
indícios	
  de	
  ser	
  um	
  atributo	
  irrelevante.	
  
n  Quando	
  a	
  parLção	
  dos	
  dados	
  não	
  for	
  estaLsLcamente	
  significante,	
  
podemos	
  parar	
  o	
  crescimento	
  da	
  árvore.	
  
Como	
  evitar	
  a	
  superadaptação	
  
48	
  
n  PermiLr	
  que	
  a	
  árvore	
  “sobreajuste”	
  os	
  dados,	
  e	
  depois	
  podar	
  
os	
  atributos	
  irrelevantes.	
  
n  Podar	
  um	
  nó	
  de	
  decisão:	
  remover	
  a	
  subárvore	
  enraizada	
  naquele	
  nó,	
  
tornando–o	
  um	
  nó	
  folha.	
  
n  Atribuir	
  a	
  este	
  nó,	
  a	
  classificação	
  mais	
  comum	
  dos	
  exemplos	
  de	
  
treinamento	
  afiliados	
  com	
  aquele	
  nó.	
  
n  Nós	
  são	
  removidos	
  somente	
  se	
  a	
  árvore	
  podada	
  resultante	
  não	
  
apresenta	
  um	
  comportamento	
  pior	
  do	
  que	
  a	
  original	
  sobre	
  o	
  
conjunto	
  de	
  validação	
  (erro	
  de	
  poda	
  reduzido).	
  
Como	
  evitar	
  a	
  superadaptação	
  
49	
  
n  ParLcionar	
  os	
  dados	
  em	
  conjuntos	
  de	
  validação	
  e	
  
treinamento:	
  
n  Faça	
  até	
  que	
  uma	
  redução	
  (poda)	
  adicional	
  seja	
  prejudicial:	
  
n  1.	
  Avaliar	
  o	
  impacto	
  sobre	
  o	
  conjunto	
  de	
  validação	
  da	
  poda	
  de	
  cada	
  nó	
  
possível,	
  mais	
  aqueles	
  abaixo	
  dele.	
  
n  2.	
  Remover	
  “gulosamente”	
  aquele	
  que	
  melhora	
  mais	
  a	
  precisão	
  sobre	
  o	
  
conjunto	
  de	
  validação.	
  
Como	
  evitar	
  a	
  superadaptação	
  
50	
  
n  A	
   é	
  outra	
  técnica	
  que	
  reduz	
  a	
  
superadaptação.	
  
n  Ela	
  pode	
  ser	
  aplicada	
  a	
  qualquer	
  algoritmo	
  de	
  aprendizagem.	
  
n  A	
  ideia	
  é	
  esLmar	
  o	
  quanto	
  cada	
  hipótese	
  irá	
  esLmar	
  dados	
  não	
  vistos.	
  
n  Separa-­‐se	
  uma	
  fração	
  dos	
  dados	
  conhecidos	
  como	
  dados	
  de	
  	
  teste	
  e	
  
induz-­‐se	
  a	
  hipótese	
  com	
  o	
  restante	
  dos	
  dados.	
  
n  A	
  validação	
  cruzada	
  de	
  k	
  vias	
  significa	
  que	
  deve-­‐se	
  realizar	
  k	
  
experimentos	
  reservando	
  cada	
  vez	
  um	
  fração	
  1/k	
  diferente	
  dos	
  dados	
  
para	
  testes	
  e	
  calcular	
  a	
  média	
  dos	
  resultados.	
  
n  Valores	
  populares	
  de	
  k	
  são	
  5	
  e	
  10.	
  O	
  extremos	
  k	
  =	
  n	
  também	
  é	
  conhecido	
  
como	
  validação	
  cruzada	
  com	
  omissão	
  de	
  um.Aplicação	
  do	
  algoritmo	
  de	
  aprendizagem	
  
51	
  
Ex Cho Res
X1 Não Sim
X2 Não Não
X3 Não Não
X4 Sim Não
X5 Não Sim
X6 Sim Sim
X7 Sim Não
X8 Sim Sim
X9 Sim Não
X10 Não Sim
X11 Não Não
X12 Não Não
Meta 
Sim 1 3 4 6 8 12 
Não 2 5 7 9 10 11 
Chovendo? 
4 6 8 
7 9 
1 3 12 
2 5 10 11 
sim não 
Reserva? 
1 6 8 
5 10 
3 4 12 
2 7 9 11 
sim não 
Aplicação	
  do	
  algoritmo	
  de	
  aprendizagem	
  
52	
  
Ex Cho Res
X1 Não Sim
X2 Não Não
X3 Não Não
X4 Sim Não
X5 Não Sim
X6 Sim Sim
X7 Sim Não
X8 Sim Sim
X9 Sim Não
X10 Não Sim
X11 Não Não
X12 Não Não
Meta 
Sim 1 3 4 6 8 12 
Não 2 5 7 9 10 11 
Tipo? 
4 8 
2 11 
6 
10 
Fra Tai Ita Ham 
3 12 
7 9 
1 
5 TempoEspera? 
4 
10 
12 
2 
0-10 10-30 30-60 >60 
 
5 9 
1 3 6 8 
7 11