Árvore de decisão

Aprendizagem de Máquina
Alessandro L. Koerich
Programa de Pós-Graduação em Informática Pontifícia Universidade Católica do Paraná (PUCPR)

ÁRVORES DE DECISÃO

Plano de Aula
• • • • • • Introdução Representação de Árvores de Decisão Algoritmo de Aprendizagem ID3 Entropia e Ganho de Informação Exemplos Aspectos na Aprendizagem de Árvores de Decisão • Resumo

Referências
• Duda R., Hart P., Stork D. Pattern Classification 2ed. Willey Interscience, 2002. Capítulo 8. • Mitchell T. Machine Learning. WCB McGraw– Hill, 1997. Capítulo 3.

Árvore

Introdução
• Aprendizagem de árvores de decisão é um método prático de aprendizagem indutiva. • É um método para a aproximação de funções de valor discreto • É um método relativamente robusto a ruídos nos dados • Utiliza um bias indutivo: preferência por árvores menores.

Introdução
• A função aprendida é representada por uma Árvore de Decisão. • Árvores de decisão também podem ser representadas como conjuntos de regras SE–ENTÃO (IF–THEN). • Aplicações: Diagnóstico médico, análise de risco de crédito, mineração de dados, etc.

Representação de Árvores de Decisão
• Árvores de decisão classificam instâncias ordenando–as árvore abaixo, a partir da raiz até alguma folha. • Cada nó da árvore especifica o teste de algum atributo da instância • Cada ramo partindo de um nó corresponde a um dos valores possíveis dos atributos.

Exemplo

Representação de Árvores de Decisão
• Uma instância é classificada inicialmente pelo nó raiz, testando o atributo especificado por este nó. • Em seguida, movendo-se através do ramo correspondendo ao valor do atributo no exemplo dado. • Este processo é repetido para a sub-árvore originada no novo nó.

Exemplo

Quando Considerar Árvores de Decisão
• Instâncias descritas por pares atributo–valor. Instâncias são descritas por um conjunto fixo de atributos (ex. Temperatura) e seus valores (ex. Quente, Morno, Frio) • A função alvo tem valores discretos de saída.