ArvoreDecisaoIndutiva

APRENDIZADO DE MÁQUINA: ÁRVORE DE DECISÃO INDUTIVA
Texto elaborado a partir de [Mitchell, Tom. “Machine Learning”, McGraw-Hill, 1997].

Árvore de Decisão Indutiva é um dos métodos de aprendizado simbólico mais amplamente utilizados e práticos para inferência indutiva.
É um método para aproximar funções discretas robustas a dados com ruído e que permite o aprendizado de expressões disjuntas. É descrito um algoritmo extensamente estudado, o ID3, o qual dá preferência às árvores pequenas, evitando árvores grandes. Esta característica faz uma espécie de generalização sobre os exemplos de aprendizado.
Este método de aprendizagem está entre os mais populares algoritmos de inferência indutiva e foi aplicado amplamente nas mais diversas tarefas, como, por exemplo, diagnosticar casos médicos e avaliar o risco de crédito de candidatos a empréstimo.
1.

REPRESENTAÇÃO DA ÁRVORE DE DECISÃO
As árvores de decisão classificam instâncias partindo da raiz da árvore para algum nodo folha que fornece a classe da instância. Cada nodo da árvore especifica o teste de algum atributo da instância, e cada arco alternativo que desce daquele nodo corresponde a um dos possíveis valores deste atributo. Uma instância é classificada começando no nodo raiz da árvore e testa o atributo relacionado a este nodo e segue o arco que corresponde ao valor do atributo na instância em questão. Este processo é repetido então para a sub-árvore abaixo até chegar a um nodo folha.
Abaixo é apresentada uma árvore de decisão típica. Esta árvore de decisão classifica os dias, conforme eles são satisfatórios ou não, para jogar tênis.
Perspectiva?
Ensolarado

Chuvoso
Nublado

Umidade?
Alta
Não

Vento?

Sim
Normal

Forte

Fraco

Sim

Não

Sim

Por exemplo, a instância (Perspectiva = Ensolarado, Temperatura = Quente, Umidade = Alta, Vento = Forte) seguirá o caminho mais à esquerda desta árvore de decisão e será classificada então como uma instância negativa (i.e., a árvore prediz que JogarTênis = não).
Em geral,