Árvore de decisão

Indução de Árvores de Decisão
 Várias aplicações em Inteligência Artificial em tarefas de importância prática são baseadas na construção de um modelo de conhecimento que é utilizado por um especialista humano  O objetivo desta aula é fornecer conceitos básicos sobre indução de árvores de decisão
José Augusto Baranauskas Departamento de Física e Matemática – FFCLRP-USP Sala 226 – Bloco P2 – Fone (16) 3602-4361 E-mail: [e-mail] URL: http://www.fmrp.usp.br/augusto

Histórico
 1960 s
 1966: Hunt e colegas em psicologia usaram métodos de busca exaustiva em árvores de decisão para modelar o aprendizado de conceitos humanos

 1970 s
 1977: Breiman, Friedman, e colegas em estatística desenvolveram Classification And Regression Trees (CART)  1979: Primeiro trabalho de Quinlan com proto-ID3 (Induction of Decision Trees)

 1980 s
 1984: primeira publicação em massa do software CART (presente atualmente em vários produtos comerciais)  1986: Artigo de Quinlan sobre ID3  Variedade de melhorias: tratamento de ruído, atributos contínuos, atributos com valores desconhecidos, árvores oblíquas (não paralelas aos eixos), etc

 1990 s
 1993: Algoritmo atualizado de Quinlan: C4.5 (release 8)  Maior poder, heurísticas de controle de overfitting (C5.0, etc.); combinando DTs

2

TDIDT
 Os algoritmos de classificação cujo conhecimento adquirido é representado como Árvore de Decisão (DT) pertencem a família TDIDT (Top Down Induction of Decision Trees)  Árvore de Decisão: estrutura recursiva definida como:
 um nó folha que indica uma classe, ou  um nó de decisão contém um teste sobre o valor de um atributo. Cada resultado do teste leva a uma subárvore. Cada sub-árvore tem a mesma estrutura da árvore
3

DT para Jogar Tênis
 Atributos:
 Aparência: Sol, Nublado, Chuva  Umidade: Alta, Normal  Ventando: Forte, Fraco  Temperatura: Quente, Média, Fria  Classe (Conceito Alvo) – jogar tênis: Sim, Não

4

DT para