Árvores de Decisão

Uma árvore de decisão classifica fazendo uma sequência de perguntas simples — comprimento da pétala ≤ 2,45? renda > 5.000? — caminhando da raiz até a folha. Formalizadas nos anos 1980 (CART: Breiman et al., 1984; ID3/C4.5: Quinlan, 1986/1993), as árvores se leem como fluxogramas que um especialista de domínio pode auditar, lidam com tipos de atributos mistos sem escalonamento e são o bloco de construção dos ensembles (random forests, gradient boosting) que dominam o ML tabular hoje.

Uma árvore de profundidade 2 na iris: dois limiares nas medidas de pétala já separam as espécies quase perfeitamente — e você lê por quê diretamente da figura.

Como uma árvore é crescida

As árvores são construídas de forma gananciosa (greedy), de cima para baixo (CART): em cada nó, testa-se todo atributo e todo limiar e escolhe-se a divisão que torna os dois filhos mais puros; recursivamente até uma regra de parada disparar.

Medindo a impureza

Para um nó com proporções de classe \(p_1, \dots, p_k\):

Impureza de Gini (padrão do CART) — a probabilidade de que dois sorteios aleatórios do nó discordem:

Entropia (família ID3) — incerteza da teoria da informação:

Ambas são 0 para um nó puro e máximas para uma mistura 50/50; na prática elas escolhem divisões quase idênticas (o Gini é um pouco mais barato — sem logaritmo).

Uma divisão candidata \(S\) do nó \(N\) em filhos \(L, R\) é pontuada pela redução de impureza (com entropia, chamada de ganho de informação):

Para árvores de regressão, a impureza é simplesmente a variância do alvo no nó — o erro quadrático médio (MSE, de mean squared error) — e cada folha prevê a média de suas amostras.

CRESCER(nó):
    se regra de parada (profundidade, mín amostras, pureza): faça folha
    para cada atributo j, cada limiar t:
        pontue a divisão x_j ≤ t pela redução de impureza Δ
    aplique a melhor divisão; CRESCER(esquerda); CRESCER(direita)

Ganancioso significa sem antevisão: a árvore nunca reconsidera uma divisão que compensaria dois níveis depois (padrões tipo XOR podem derrotá-la). Os ensembles compensam.

Sobreajuste: a doença crônica da árvore

Crescida sem limites, uma árvore continua dividindo até as folhas ficarem puras — isolando alegremente cada ponto ruidoso em sua própria folha. As árvores são aprendizes de baixo viés e alta variância: pequenas mudanças nos dados podem produzir uma árvore completamente diferente.

A árvore ilimitada (esquerda) esculpe ilhas retangulares em torno de pontos de ruído individuais; max_depth=4 (direita) captura a estrutura real. Note as fronteiras alinhadas aos eixos, em "escada" — as árvores dividem um atributo de cada vez.

Controlando a complexidade (todos são botões de viés–variância para validação cruzada):

• Pré-poda (pre-pruning): max_depth, min_samples_split, min_samples_leaf, min_impurity_decrease;
• Pós-poda (post-pruning): crescer totalmente e depois cortar ramos que não justificam sua complexidade — a poda por custo-complexidade minimiza \(\text{erro} + \alpha \cdot \#\text{folhas}\) (ccp_alpha), a versão em árvore da regularização.

from sklearn.tree import DecisionTreeClassifier

tree = DecisionTreeClassifier(max_depth=4, min_samples_leaf=5, random_state=0)
tree.fit(X_train, y_train)          # sem necessidade de escalonamento!
tree.feature_importances_           # importâncias baseadas em impureza (somam 1)

Perfil prático

Impureza, em um nó

O Gini de um nó é \(1 - \sum_c p_c^2\) — a probabilidade de dois pontos sorteados dele discordarem. Tome um nó com 6 da classe A e 4 da classe B:

Agora pontue dois cortes candidatos. A regra é a impureza ponderada dos filhos:

O corte 2 divide o nó exatamente ao meio e não consegue nada: os dois filhos têm a mesma mistura de classes do pai, então o ganho é exatamente zero. Um corte só vale a pena quando muda as proporções, que é todo o conteúdo do critério guloso.

O CART testa todo atributo e todo limiar, pontua cada um assim e fica com o melhor. Depois recorre. Veja acontecer:

Material de aula

Referências

• Quinlan, J. R. "Induction of Decision Trees." Machine Learning 1 (1986). DOI

Bibliografia completa do curso na página de referências.

Quiz