Árvores de Decisão
O primeiro tópico a ser abordado aqui no blog são as árvores
de decisão, sendo os mais conhecidos o algoritmo ID3 e no seu sucessor C4.5. Iremos implementar primeiramente a versão mais básica (ID3) e depois de pronto o modificaremos para que se torne o seu sucessor.
O nosso algoritmo básico constrói as árvores de decisão de
uma forma top-down (de cima para baixo), fazendo uma simples pergunta: "Qual
atributo deve ser usado?". Para responder isso cada atributo é testado
usando um método estatístico para determinar o ganho de informação que aquele atributo gera na hora de
classificar a nossa base de treinamento. Após a seleção esse atributo vira o
topo da árvore e cada valor que esse atributo pode assumir vira uma folha e a
base de dados é separada de acordo, o processo todo é repetido para cada
folha, usando apenas os exemplos associados a ela. Iremos usar a implementação greedy desse algoritmo, pois ele nunca
volta atrás para reconsiderar as escolhas feitas anteriormente.
Para a implementação de uma árvore de decisão
que aceite apenas valores booleanos como saída, teremos o seguinte
pseudocódigo:
IDE3 (Exemplos, atribuito_classificador, Atributos)
- Criar a folha inicial da árvore Root
- Se todos os objetos são positivos em Exemplos, retornar uma única folha com a saída verdadeira.
- Se todos os objetos são negativos em Exemplos, retornar uma única folha com a saída false.
- Se Atributos estiver vazio retornar uma única folha com a saída mais comum na base.
- Caso contrário faça:
- A recebe o atributo de Atributos que melhor classifica Exemplos.
- Root recebe A
- Para cada possível valor v de A teremos:
- Adicionar uma nova folha a A com o valor correspondente a v.
- Sendo X o resultado de Exemplos com os objetos que contenham v como atributo.
- Se o X gerado for vazio:
- Adicionar uma folha a Root com o valor mais comum da base.
- Caso contrário:
- ID3 (X, atribuito_classificador, Atributos – A).
- Término.
- Retorne Root.
Para medir qual atributo melhor classifica a base de dados vamos utilizar o cálculo de ganho de informação, você pode conferir uma descrição completa da equação nesse link.
Como todos algoritmos o ID3 possuí algumas limitações e capacidades, vamos ver abaixo algumas delas:
- O ID3 na sua forma inicial, e a que será implementada, não possui nenhuma forma de backtracking, portanto está sujeito a convergir para soluções ótimas locais. No caso do ID3, uma solução ótima local corresponde ao único caminho considerado pelo algoritmo.
- ID3 usa todos os exemplos do conjunto de treinamento a cada iteração, não importando o nível em que a árvore se encontra. Essa característica faz com que o ID3 seja muito menos suscetível a erros no conjunto de treinamento.
- O ID3 mantém apenas uma única solução, o que faz com que ele não seja capaz de otimizar os resultados obtidos.
Para encerrar esse post podemos ver abaixo um exemplo de resultado obtido com o ID3:
