Á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 (MSE) do alvo no nó, 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

Material de aula

Quiz