10 ID3, C4.5 e CART
Depois de entender os critérios de divisão, o passo seguinte é conectar esses critérios aos algoritmos clássicos de indução de árvores. Nesta etapa, três nomes aparecem com frequência na literatura e no ensino de aprendizado de máquina: ID3, C4.5 e CART.
Embora hoje muitas pessoas usem diretamente bibliotecas como scikit-learn, compreender esses algoritmos ajuda bastante a entender por que as árvores se comportam da forma que se comportam.
10.1 Objetivos do capítulo
Ao final deste capítulo, o leitor deve ser capaz de:
- descrever a lógica geral de indução top-down;
- explicar o papel do ganho de informação no ID3;
- reconhecer as melhorias introduzidas pelo C4.5;
- compreender a proposta do CART e sua relevância prática;
- diferenciar esses algoritmos em nível conceitual.
10.2 A ideia geral de indução top-down
A maior parte dos algoritmos clássicos constrói a árvore de cima para baixo.
- Começa-se com todos os exemplos no nó raiz.
- Escolhe-se o melhor atributo para dividir esse conjunto.
- Criam-se ramos para os resultados possíveis do teste.
- O processo é repetido recursivamente em cada subconjunto.
- A construção para quando os exemplos ficam suficientemente homogêneos, quando faltam atributos ou quando algum critério de parada é atingido.
Essa estratégia é chamada de gulosa porque a escolha do atributo é feita localmente, sem revisar todas as alternativas possíveis para a árvore inteira.
10.3 O algoritmo ID3
O ID3, associado a Quinlan, é um dos algoritmos mais clássicos de aprendizado de árvores de decisão. Seu critério principal é o ganho de informação.
10.3.1 Ideia central
Em cada nó, o ID3 escolhe o atributo que mais reduz a entropia do conjunto local.
10.3.2 Visão conceitual do procedimento
- se todos os exemplos do nó pertencem à mesma classe, cria-se uma folha;
- se não há mais atributos disponíveis, usa-se a classe majoritária;
- caso contrário, escolhe-se o melhor atributo segundo ganho de informação;
- o processo continua recursivamente em cada ramo.
10.3.3 Pseudocódigo conceitual
ID3(exemplos, atributos):
se todos os exemplos são da mesma classe:
retorna folha
se não restam atributos:
retorna folha com classe majoritária
escolhe o atributo com maior ganho de informação
cria um nó para esse atributo
para cada valor do atributo:
cria um ramo
chama ID3 para o subconjunto correspondente10.4 Forças do ID3
- alta clareza conceitual;
- forte valor didático;
- boa conexão entre teoria da informação e classificação;
- capacidade de construir regras simbólicas interpretáveis.
10.5 Limitações do ID3
Apesar de elegante, o ID3 possui limitações clássicas.
- foi pensado principalmente para classificação;
- lida de forma mais natural com atributos categóricos;
- pode favorecer atributos com muitos valores distintos;
- não é, por si só, um mecanismo completo de poda robusta, como nas variantes posteriores.
10.6 O problema do viés por muitos valores
Imagine dois atributos:
código_cliente, com muitos valores quase únicos;inadimplencia_previa, com poucos valores e forte significado.
Um atributo com muitos valores pode gerar partições pequenas demais e aparentar grande ganho no treino, mesmo sem generalizar bem. Esse tipo de problema motivou refinamentos posteriores.
10.7 C4.5
O C4.5 pode ser visto como uma extensão importante do ID3. Ele preserva a ideia de construção top-down, mas introduz mecanismos mais sofisticados para problemas reais.
10.7.1 Melhorias conceituais associadas ao C4.5
- tratamento mais flexível de atributos contínuos;
- melhor tratamento de valores ausentes;
- uso de critérios que reduzem o viés por atributos com muitos valores;
- poda posterior para melhorar generalização.
10.7.2 Gain ratio
Uma ideia frequentemente associada ao C4.5 é o uso do gain ratio, que ajusta o ganho de informação pela forma como o atributo divide os dados. Isso reduz a tendência de favorecer atributos com muitos valores.
Em termos intuitivos, o algoritmo pergunta não apenas “quanto esse atributo reduz a incerteza?”, mas também “essa redução veio de uma divisão razoável ou de uma fragmentação excessiva?”.
10.8 Tratamento de atributos contínuos
Em domínios reais, muitos atributos são numéricos: idade, renda, temperatura, saldo, tempo, consumo, score. O C4.5 considera pontos de corte e transforma um atributo contínuo em testes do tipo:
idade <= 35.5saldo <= 1200tempo_contrato <= 18
Essa ideia foi crucial para a aplicabilidade prática das árvores.
10.9 Poda no C4.5
A poda entra para reduzir complexidade e melhorar generalização. O algoritmo aceita que a árvore inicial possa crescer mais e, em seguida, remove ramos cuja contribuição não justifica a complexidade adicional.
10.10 CART
CART significa Classification and Regression Trees. Esse nome já sinaliza um diferencial importante: o algoritmo foi formulado tanto para classificação quanto para regressão.
10.10.1 Características conceituais do CART
- usa divisões binárias;
- pode ser aplicado à classificação e à regressão;
- popularizou a lógica de poda por custo-complexidade;
- está fortemente ligado a implementações modernas.
10.11 Divisões binárias
Enquanto alguns materiais didáticos apresentam árvores com vários ramos por atributo categórico, o CART trabalha de forma muito natural com divisões binárias. Isso significa que cada nó produz dois filhos.
Exemplos:
idade <= 35.5versusidade > 35.5;regiao in {sul, sudeste}versusregiao fora desse grupo.
Essa estrutura binária simplifica vários aspectos computacionais e aparece claramente em muitas bibliotecas atuais.
10.12 CART em classificação e regressão
No caso de classificação, o CART costuma usar medidas como Gini para avaliar a qualidade da divisão. Na regressão, usa critérios associados à redução da variância ou do erro.
Por isso, o CART se tornou particularmente influente na prática moderna e em famílias inteiras de modelos baseados em árvores.
10.13 Relação com o scikit-learn
Na prática, quando treinamos uma DecisionTreeClassifier ou DecisionTreeRegressor no scikit-learn, estamos muito mais próximos da família conceitual do CART do que do ID3 puro.
Isso significa que, mesmo estudando ID3 e C4.5, o leitor deve entender que a implementação corrente da biblioteca segue uma linha mais próxima de:
- divisões binárias;
- critérios como Gini e entropia para classificação;
- poda por custo-complexidade com
ccp_alpha.
10.14 Comparação conceitual resumida
10.14.1 ID3
- fortemente didático;
- usa ganho de informação;
- associado ao estudo clássico de indução;
- mais limitado diante de atributos contínuos e questões práticas modernas.
10.14.2 C4.5
- amplia o ID3;
- lida melhor com atributos contínuos e valores ausentes;
- introduz refinamentos como gain ratio;
- incorpora poda mais estruturada.
10.14.3 CART
- trabalha com divisões binárias;
- cobre classificação e regressão;
- tem enorme relevância prática;
- inspira bastante as implementações de uso corrente.
10.15 Por que estudar algoritmos clássicos se a biblioteca já faz tudo?
Porque a biblioteca treina a árvore, mas não substitui o entendimento.
Quem compreende ID3, C4.5 e CART consegue:
- interpretar melhor o comportamento do modelo;
- explicar por que determinado critério foi escolhido;
- identificar limitações de generalização;
- tomar decisões mais conscientes sobre hiperparâmetros e poda.
ID3, C4.5 e CART representam momentos centrais na evolução das árvores de decisão. O ID3 formaliza a indução top-down guiada por ganho de informação. O C4.5 amplia essa proposta para lidar melhor com problemas reais. O CART consolida uma abordagem extremamente prática, binária e aplicável tanto à classificação quanto à regressão.
No próximo capítulo, vamos sair da formulação algorítmica e voltar ao uso concreto em Python, observando como essas ideias aparecem em uma árvore treinada de fato.
- estudar apenas a API moderna e ignorar a intuição dos algoritmos clássicos;
- imaginar que ID3, C4.5 e CART são equivalentes em todos os detalhes;
- esquecer o problema do viés por atributos com muitos valores;
- supor que bibliotecas atuais implementam ID3 puro.
- Qual é a ideia central do ID3?
- O que o C4.5 melhora em relação ao ID3?
- Por que o CART é tão importante na prática moderna?
- Como as divisões binárias influenciam a estrutura da árvore?