Use uma árvore de decisão para descrever um procedimento ótimo para identificar um pássaro
dentre as seis espécies a seguir, usando apenas perguntas “sim ou não”. Explique como você sabe que o seu procedimento é ótimo.
Espécies
Fatos
Yellow Warbler
Quase todo amarelo, cabeça da mesma cor.
Wilsoiis Warbler
Quase todo amarelo, cabeça preta, dorso verde-oliva.
American Goldfinch
Quase todo amarelo, cabeça preta, dorso amarelo.
Oak Titmouse
Quase todo cinza, com penacho.
Hutton's Vireo
Quase todo cinza, dorso verde-oliva, sem penacho.
Blue-gray Gnatcatcher
Quase todo cinza, dorso cinza-escuro, sem penacho.
Espécies | Fatos |
Yellow Warbler | Quase todo amarelo, cabeça da mesma cor. |
Wilsoiis Warbler | Quase todo amarelo, cabeça preta, dorso verde-oliva. |
American Goldfinch | Quase todo amarelo, cabeça preta, dorso amarelo. |
Oak Titmouse | Quase todo cinza, com penacho. |
Hutton's Vireo | Quase todo cinza, dorso verde-oliva, sem penacho. |
Blue-gray Gnatcatcher | Quase todo cinza, dorso cinza-escuro, sem penacho. |
Passo 1
O enunciado pede um procedimento de classificação por meio de perguntas “sim ou não” para distinguir seis espécies de pássaros. O conteúdo envolvido é o de árvores de decisão binárias e noções básicas de informação (bits) para medir quantas perguntas são necessárias em piores casos.
Passo 2
Cada pergunta “sim ou não” fornece no máximo
bit de informação. Para escolher uma dentre
espécies, precisamos de pelo menos
perguntas em qualquer árvore de decisão, pois
.
Passo 3
Para maximizar o balanceamento, a primeira pergunta deve dividir o conjunto em dois grupos de tamanho o mais igual possível. Uma escolha natural é:
“O pássaro é quase todo amarelo?”
Se “Sim”, restam exatamente
espécies amarelas.
Se “Não”, restam exatamente
espécies acinzentadas.
“O pássaro é quase todo amarelo?”
Passo 4
Ramo “Sim” (
amarelos). Pergunta seguinte:
“A cabeça é preta?”
Se “Não”, sobra apenas o Yellow Warbler (toda amarela e cabeça amarela).
Se “Sim”, sobra um par
.
“A cabeça é preta?”
Passo 5
Para distinguir essas duas espécies com cabeça preta, perguntamos:
“O dorso é verde-oliva?”
Se “Sim”, é Wilson’s Warbler (dorso verde-oliva).
Se “Não”, é American Goldfinch (dorso amarelo).
“O dorso é verde-oliva?”
Passo 6
Ramo “Não” à primeira pergunta (
acinzentados). Pergunta seguinte:
“O pássaro tem penacho?”
Se “Sim”, é Oak Titmouse (único com penacho).
Se “Não”, restam
.
“O pássaro tem penacho?”
Para esse par, fazemos:
“O dorso é verde-oliva?”
Se “Sim”, é Hutton’s Vireo.
Se “Não”, é Blue-gray Gnatcatcher (dorso cinza-escuro).
“O dorso é verde-oliva?”
Passo 7
Essa árvore tem profundidade máxima
, igual ao limite inferior
. Logo não é possível usar menos perguntas em pior caso, o que prova que o procedimento é ótimo.
Resposta
Árvore de decisão ótima (máximo de
perguntas):
– Sim
– Sim
– Não
– Não
– Sim
– Não