Árvores de decisão

Selecção do atributo de teste

Podemos ver o domínio dos exemplos como uma fonte de mensagens, cada uma delas representando uma das classes possíveis.

Baseado na Teoria da Informação

• Entropia apriori:

• Entropia aposteriori, dado o valor de um atributo:

• Entropia global aposteriori:

Ganho de informação.

• Ou seja, redução da entropia

As probabilidades podem ser estimadas com base nos exemplos disponíveis.

Nota: Este método funciona mal quando os atributos têm muitos valores possíveis.

Razão do ganho

• 
• 
• Resolve o problema dos atributos com muitos valores.

• Quando H(Aj) se aproxima de zero, a razão do ganho fica instável; por isso, são excluídos à partida os atributos cujo ganho de informação seja inferior à média.

Critério GINI

Impureza apriori.

• 

Impureza aposteriori:

• 

Alguns problemas

Tratamento do ruído – por vezes, os exemplos de treino contém ruido, ou seja, particularidades não representativas do domínio que podem levar o algoritmo de aprendizagem a fazer uma generalização incorrecta.

Atributos numéricos – como usá-los nas regras ou nas árvores de decisão?

Atributos com valores não especificados nos exemplos.

Levar em conta o custo de cálculo de cada atributo.

Aprendizagem incremental.

Aprendizagem por indução em lógica de primeira ordem.

• FOIL

Tratamento do ruído

Parar a expansão da árvore quando o número de exemplos disponíveis é inferior a um dado limiar.

Ter um estimativa do erro, e parar a expansão quando a estimativa do erro começa a subir.

Ter um estimativa do erro, e parar a expansão quando essa estimativa sobe para além de um dado limiar.

Expandir completamente a àrvore e no fim podá-la.