Algoritmos ID3, C4.5 e CART

ID3 – Iterative Dichotomizer 3

Segundo Quinlan (1986), o algoritmo consiste num processo de indução de árvores. A construção da árvore é realizada de cima para baixo (top-down), com o objetivo de escolher sempre o melhor atributo para cada nó de decisão da árvore. É um processo recursivo que após ter escolhido um atributo para um nó, começando pela raiz, aplica o mesmo algoritmo aos descendentes desse nó, até que certos critérios de paragem sejam verificados.

Uma das grandes vantagens do ID3 é a sua simplicidade, o seu processo de construção torna relativamente simples a compreensão do seu funcionamento.

A maior desvantagem do ID3 é que a árvore de decisão produzida é essencialmente imutável, não pode eficientemente reutilizar a árvore sem a reconstruir.

C4.5

Segundo Quilan (1993), é um método melhorado relativamente ao ID3 que, entre outros melhoramentos, combate o problema de overfitting, utilizando uma estratégia de poda de árvore.

Vantagem do C4.5 é que ele apresenta métodos de pós poda da árvore de decisão gerada, ou seja, realiza um busca de baixo para cima, e transforma em nós folhas aqueles nós que não representam nenhuma ganho significativo.

Desvantagem segundo Quinlan, é que quando as árvores de decisão ficam muito complexas sua compreensão fica comprometida, a alternativa, nesse caso seria construir uma regra para cada classe. Entretanto, o autor alerta que seu uso requer quantidades consideráveis de CPU e memória  para construí-las.

CART – Classification And Regression Trees

Segundo Breiman, Freidman, Stone e Olshen  (1984), CART permite a construção de árvores de decisão e árvores de regressão, realizando um particionamento recursivo binário do conjunto de dados e associando a cada nó-folha da árvore uma classe, no caso das árvores de decisão, ou um valor continuo, no caso das árvores de regressão.

É um algoritmo não paramétrico. Possui grande capacidade de pesquisa de relações entre dados, prevendo o tratamento de variáveis dependentes discretas, através da classificação, ou de variáveis continuas, pela regressão.

Vantagem do CART, pode utilizar variáveis independentes de diferentes tipos, desde continuas, ordinais e nominais, não obriga a realização de transformações de variáveis iniciais independentes (como a logaritmização ou normalização) pois o método tem bom comportamento para qualquer tipo de dados.

Desvantagem do CART, uma importante fraqueza é que não há nenhum intervalo de confiança ou probabilidade de acerto para a classificação prevista para um novo dado, usando a árvore de decisão gerada pelo algoritmo, tendo em vista que o CART não é baseado num modelo probabilístico.

Podem ocorrer árvores de decisão instáveis, onde pequenas modificações nos dados de treinamento podem produzir mudanças radicais, aumentando ou diminuindo a complexidade da sua estrutura.