3 Critérios de Divisão

Uma árvore de decisão não escolhe perguntas ao acaso. Em cada nó, ela procura o teste que melhor organiza os dados locais. Essa escolha depende de um critério de divisão, isto é, de uma medida numérica que avalia o quanto uma partição melhora a separação entre as classes ou reduz o erro.

3.1 Objetivos do capítulo

Ao final desta leitura, o leitor deve ser capaz de:

explicar o que significa pureza e impureza em um nó;
calcular entropia e impureza Gini em exemplos simples;
interpretar ganho de informação como redução de incerteza;
entender por que um atributo pode ser escolhido na raiz;
reconhecer os limites práticos de uma escolha gulosa.

3.2 O problema que o critério resolve

Suponha um conjunto com exemplos das classes A e B. Se o nó atual possui exemplos muito misturados, a incerteza sobre a classe correta é alta. O objetivo do algoritmo é encontrar uma divisão que gere filhos mais homogêneos.

Em outras palavras, a pergunta ideal é aquela que reduz a desordem do conjunto.

3.3 Pureza e impureza

Um nó puro contém exemplos de uma única classe. Um nó impuro contém classes misturadas.

Exemplos:

10 A e 0 B: nó totalmente puro;
9 A e 1 B: nó bastante puro;
6 A e 4 B: nó moderadamente impuro;
5 A e 5 B: nó altamente impuro.

A árvore prefere testes que levem de um nó impuro para filhos mais puros.

3.4 Entropia

A entropia vem da teoria da informação e mede a incerteza associada a uma distribuição de classes.

Para classificação binária:

\[ H(S) = -p_+ \log_2(p_+) - p_- \log_2(p_-) \]

onde:

p_+ é a proporção de exemplos positivos;
p_- é a proporção de exemplos negativos.
Interpretação intuitiva
Se todos os exemplos pertencem à mesma classe, a entropia é 0.
Se as classes estão equilibradas, a entropia é máxima.
Quanto maior a entropia, maior a incerteza sobre a classe de um exemplo escolhido ao acaso.

3.5 Tabela intuitiva de entropia

Antes de calcular um caso completo, vale observar o comportamento da medida em distribuições diferentes.

import math

def entropia_binaria(p):
    if p in (0, 1):
        return 0.0
    return -(p * math.log2(p) + (1 - p) * math.log2(1 - p))

for positivos, total in [(10, 10), (9, 10), (8, 10), (7, 10), (6, 10), (5, 10)]:
    p = positivos / total
    print(f"{positivos}/{total} positivos -> entropia = {entropia_binaria(p):.3f}")

10/10 positivos -> entropia = 0.000
9/10 positivos -> entropia = 0.469
8/10 positivos -> entropia = 0.722
7/10 positivos -> entropia = 0.881
6/10 positivos -> entropia = 0.971
5/10 positivos -> entropia = 1.000

– Leitura da tabela

10/10: nenhuma incerteza, entropia zero;
9/10: ainda há alta previsibilidade, entropia baixa;
5/10: máxima incerteza para o caso binário, entropia alta.

Essa progressão ajuda a entender por que um atributo que produz subconjuntos desequilibrados em favor de uma classe é valioso para a árvore.

3.6 Exemplo numérico detalhado de entropia

Suponha um nó com 14 exemplos, sendo 9 positivos e 5 negativos.

\[ p_+ = 9/14 \approx 0{,}643 \]

\[ p_- = 5/14 \approx 0{,}357 \]

Substituindo na fórmula:

\[ H(S) = -(0{,}643 \cdot \log_2 0{,}643 + 0{,}357 \cdot \log_2 0{,}357) \]

O resultado é aproximadamente 0.940.

p_pos = 9 / 14
p_neg = 5 / 14
entropia = -(p_pos * math.log2(p_pos) + p_neg * math.log2(p_neg))
print(round(entropia, 3))

0.94

Esse valor indica que o conjunto ainda possui mistura relevante entre classes. Não está no máximo de incerteza, mas tampouco está próximo da pureza total.

3.7 Ganho de informação

O ganho de informação mede a redução esperada na entropia depois da divisão por um atributo.

\[ Ganho(S, A) = H(S) - \sum_{v \in Valores(A)} \frac{|S_v|}{|S|} H(S_v) \]

A lógica é direta:

calculamos a entropia antes da divisão;
calculamos a média ponderada das entropias dos filhos;
subtraímos os dois valores.

Quanto maior o ganho, melhor foi a divisão.

3.8 Exemplo passo a passo de ganho de informação

Considere novamente o conjunto com 14 exemplos (9 positivos, 5 negativos). Suponha que um atributo particione esse conjunto em dois filhos:

Filho 1: 6 positivos e 2 negativos;
Filho 2: 3 positivos e 3 negativos.
Entropia do nó pai

Já vimos que:

\[ H(S) \approx 0.940 \]

Entropia do Filho 1

\[ H(S_1) = -(6/8)\log_2(6/8) - (2/8)\log_2(2/8) \]

Entropia do Filho 2

\[ H(S_2) = -(3/6)\log_2(3/6) - (3/6)\log_2(3/6) = 1.0 \]

Média ponderada após a divisão

\[ H_{após} = (8/14)H(S_1) + (6/14)H(S_2) \]

Ganho

\[ Ganho = H(S) - H_{após} \]

def entropia(pos, neg):
    total = pos + neg
    if pos == 0 or neg == 0:
        return 0.0
    p_pos = pos / total
    p_neg = neg / total
    return -(p_pos * math.log2(p_pos) + p_neg * math.log2(p_neg))

pai = entropia(9, 5)
filho_1 = entropia(6, 2)
filho_2 = entropia(3, 3)
entropia_após = (8/14) * filho_1 + (6/14) * filho_2
ganho = pai - entropia_após

print("Entropia pai:", round(pai, 3))
print("Entropia filho 1:", round(filho_1, 3))
print("Entropia filho 2:", round(filho_2, 3))
print("Entropia após divisão:", round(entropia_após, 3))
print("Ganho de informação:", round(ganho, 3))

Entropia pai: 0.94
Entropia filho 1: 0.811
Entropia filho 2: 1.0
Entropia após divisão: 0.892
Ganho de informação: 0.048

Interpretação do resultado

O ganho será positivo porque a divisão produziu pelo menos um subconjunto mais organizado do que o conjunto original. Se compararmos vários atributos, a árvore tende a escolher aquele com maior ganho.

3.9 Exemplo comparativo entre dois atributos

Imagine dois atributos candidatos no mesmo nó pai.

Atributo A: gera filhos (6+, 2-) e (3+, 3-).
Atributo B: gera filhos (4+, 1-) e (5+, 4-).

Embora ambos reduzam alguma incerteza, A pode produzir ganho maior se separar melhor as classes. Esse tipo de comparação é exatamente o que o algoritmo faz em cada etapa.

def ganho_informacao(pai_pos, pai_neg, filhos):
    total = pai_pos + pai_neg
    entropia_pai = entropia(pai_pos, pai_neg)
    entropia_filhos = 0.0
    for pos, neg in filhos:
        subtotal = pos + neg
        entropia_filhos += (subtotal / total) * entropia(pos, neg)
    return entropia_pai - entropia_filhos

print("Ganho atributo A:", round(ganho_informacao(9, 5, [(6, 2), (3, 3)]), 3))
print("Ganho atributo B:", round(ganho_informacao(9, 5, [(4, 1), (5, 4)]), 3))

Ganho atributo A: 0.048
Ganho atributo B: 0.045

3.10 Exemplo conceitual com o problema do tênis

Nos exemplos clássicos de indução, pergunta-se: qual atributo deve ir para a raiz? Se um atributo separa o conjunto em subconjuntos quase puros, ele tende a produzir alto ganho de informação. Por isso o ID3 adota esse critério para construir a árvore de maneira gulosa.

3.11 Impureza Gini

Outro critério muito usado é a impureza Gini.

\[ Gini(S) = 1 - \sum_i p_i^2 \]

Em classificação binária:

\[ Gini(S) = 1 - (p_+^2 + p_-^2) \]

Interpretação
Gini = 0 indica pureza total;
valores maiores indicam maior mistura entre classes;
na prática, é um critério extremamente popular por ser eficiente e funcionar muito bem.

3.12 Tabela intuitiva de Gini

def gini_binario(p):
    return 1 - (p**2 + (1 - p)**2)

for positivos, total in [(10, 10), (9, 10), (8, 10), (7, 10), (6, 10), (5, 10)]:
    p = positivos / total
    print(f"{positivos}/{total} positivos -> gini = {gini_binario(p):.3f}")

10/10 positivos -> gini = 0.000
9/10 positivos -> gini = 0.180
8/10 positivos -> gini = 0.320
7/10 positivos -> gini = 0.420
6/10 positivos -> gini = 0.480
5/10 positivos -> gini = 0.500

Observe que a lógica geral é a mesma da entropia: o valor cresce conforme o nó se aproxima de uma divisão equilibrada entre classes.

3.13 Exemplo detalhado de Gini

Considere 10 amostras: 6 da classe A e 4 da classe B.

\[ Gini = 1 - (0{,}6^2 + 0{,}4^2) = 1 - (0{,}36 + 0{,}16) = 0{,}48 \]

Agora compare com um nó mais puro: 9 da classe A e 1 da classe B.

\[ Gini = 1 - (0{,}9^2 + 0{,}1^2) = 1 - (0{,}81 + 0{,}01) = 0{,}18 \]

p_a = 6 / 10
p_b = 4 / 10
gini = 1 - (p_a**2 + p_b**2)
print(round(gini, 3))

p_a = 9 / 10
p_b = 1 / 10
gini = 1 - (p_a**2 + p_b**2)
print(round(gini, 3))

0.48
0.18

No segundo caso, o valor cai porque o nó está mais puro.

3.14 Entropia ou Gini?

Na prática, as duas medidas costumam produzir resultados parecidos. As diferenças principais são:

entropia tem interpretação mais ligada à informação;
Gini costuma ser computacionalmente simples e muito usado por padrão;
pequenas mudanças na árvore podem ocorrer dependendo do critério escolhido.

No scikit-learn, classificação aceita critérios como gini, entropy e log_loss.

3.15 Atributos categóricos e numéricos

Em problemas reais, nem sempre o atributo é categórico simples. Variáveis numéricas exigem encontrar um ponto de corte.

Exemplo:

idade <= 35.5
renda <= 4200
tempo_cliente <= 18.5

O algoritmo testa candidatos a corte e escolhe o que produz a melhor redução de impureza.

3.16 Por que a escolha é gulosa

Algoritmos clássicos de árvore, como ID3 e CART, fazem escolhas locais. Em cada nó, escolhem o melhor atributo naquele momento. Eles não exploram exaustivamente todas as árvores possíveis, porque isso seria computacionalmente inviável.

Essa estratégia gulosa funciona muito bem na prática, mas também explica por que uma pequena alteração nos dados pode mudar a estrutura da árvore.

3.17 Quando um atributo aparentemente bom engana

Um ponto importante da teoria clássica é que alguns atributos podem parecer bons por criarem muitas partições pequenas. Isso pode gerar ganho elevado no treino, mas baixa generalização. Por isso, a escolha do critério deve ser acompanhada por mecanismos de controle de complexidade, como profundidade máxima e poda.

3.18 Critérios em regressão

Quando a saída é numérica, o problema muda. Em vez de reduzir mistura de classes, queremos reduzir dispersão dos valores do alvo.

Critérios comuns incluem:

redução da variância;
erro quadrático médio;
erro absoluto em algumas variantes.

A ideia continua a mesma: separar os dados em grupos mais coerentes internamente.

3.19 Hiperparâmetros ligados a divisão

Os principais controles no scikit-learn são:

criterion: define a medida usada no nó;
splitter: geralmente best ou random;
max_depth: limita profundidade;
min_samples_split: mínimo de exemplos para tentar dividir;
min_samples_leaf: mínimo de exemplos por folha;
max_leaf_nodes: limita número total de folhas;
min_impurity_decrease: exige ganho mínimo para aceitar divisão.

Erros comuns

calcular entropia sem ponderar corretamente o tamanho dos filhos;
comparar divisões olhando apenas um subconjunto e não o ganho total;
esquecer que atributos com muitos valores podem parecer bons no treino;
tratar Gini e entropia como se um sempre fosse superior ao outro.

Resumo

Toda divisão em uma árvore de decisão tenta responder à mesma pergunta: “qual teste organiza melhor os dados neste ponto?”. Entropia, ganho de informação e Gini são formas matemáticas de transformar essa intuição em algoritmo.

Perguntas de revisão

O que significa um nó puro?
Como a entropia varia entre um nó puro e um nó equilibrado?
O que o ganho de informação mede exatamente?
Qual a intuição por trás da impureza Gini?
Por que a escolha local do melhor atributo é chamada de gulosa?