Phase 02 - Lesson 04

Árvores de Decisão e Florestas Aleatórias

This lesson includes a graded coding exercise that runs in your browser, unlocked with lifetime access.

Uma árvore de decisão é apenas um fluxograma. Mas uma floresta deles é uma das ferramentas mais poderosas do ML.

Tipo: Construir Idioma: Python Pré-requisitos: Fase 1 (Lições 09 Teoria da Informação, 06 Probabilidade) Tempo: ~90 minutos

Objetivos de aprendizagem

• Implementar cálculos de impureza, entropia e ganho de informação de Gini para encontrar divisões ideais da árvore de decisão
• Construa um classificador de árvore de decisão do zero com controles de pré-remoção (profundidade máxima, amostras mínimas)
• Construir uma random forest usando amostragem bootstrap e randomização de recursos, e explicar por que isso reduz a variância
• Compare a importância do recurso MDI com a importância da permutação e identifique quando o MDI é tendencioso

O problema

Você tem dados tabulares. As linhas são amostras, as colunas são recursos e há uma coluna de destino que você deseja prever. Você poderia lançar uma rede neural nisso. Mas para dados tabulares, os modelos baseados em árvores (árvores de decisão, florestas aleatórias, árvores com gradiente aumentado) superam consistentemente o aprendizado profundo. Kaggle as competições em dados estruturados são dominadas por XGBoost e LightGBM, não por transformadores.

Por que? As árvores lidam com tipos de recursos mistos (numéricos e categóricos) sem pré-processamento. Eles lidam com relacionamentos não lineares sem engenharia de características. Eles são interpretáveis: você pode olhar para a árvore e ver exatamente por que uma previsão foi feita. E as florestas aleatórias, que têm em média muitas árvores, são altamente resistentes ao overfitting em conjuntos de dados de tamanho moderado.

Esta lição constrói árvores de decisão do zero usando divisão recursiva e, em seguida, constrói uma random forest no topo. Você implementará a matemática por trás dos critérios de divisão (impureza de Gini, entropia, ganho de informação) e entenderá por que um conjunto de alunos fracos se torna forte.

O Conceito

O que uma árvore de decisão faz

Uma árvore de decisão particiona o espaço de recursos em regiões retangulares, fazendo uma sequência de perguntas sim/não.

graph TD
    A["Age < 30?"] -->|Yes| B["Income > 50k?"]
    A -->|No| C["Credit Score > 700?"]
    B -->|Yes| D["Approve"]
    B -->|No| E["Deny"]
    C -->|Yes| F["Approve"]
    C -->|No| G["Deny"]

Cada nó interno testa um recurso em relação a um limite. Cada nó folha faz uma previsão. Para classificar um novo ponto de dados, você começa na raiz e segue os ramos até chegar a uma folha.

A árvore é construída de cima para baixo escolhendo, em cada nó, o recurso e o limite que melhor separam os dados. "Melhor" é definido por um critério de divisão.

Critérios de divisão: medição de impurezas

Em cada nó, temos um conjunto de amostras. Queremos dividi-los para que os nós filhos resultantes sejam tão "puros" quanto possível, o que significa que cada filho contém principalmente uma classe.

Impureza de Gini mede a probabilidade de que uma amostra escolhida aleatoriamente seria classificada incorretamente se fosse rotulada de acordo com a distribuição de classes naquele nó.

Gini(S) = 1 - sum(p_k^2)

where p_k is the proportion of class k in set S.

Para um nó puro (todos de uma classe), Gini = 0. Para uma divisão binária com classes 50/50, Gini = 0,5. Menor é melhor.

Example: 6 cats, 4 dogs

Gini = 1 - (0.6^2 + 0.4^2) = 1 - (0.36 + 0.16) = 0.48

Entropia mede o conteúdo de informação (desordem) em um nó. Abordado na Fase 1, Lição 09.

Entropy(S) = -sum(p_k * log2(p_k))

Para um nó puro, entropia = 0. Para uma divisão binária 50/50, entropia = 1,0. Menor é melhor.

Example: 6 cats, 4 dogs

Entropy = -(0.6 * log2(0.6) + 0.4 * log2(0.4))
        = -(0.6 * -0.737 + 0.4 * -1.322)
        = 0.442 + 0.529
        = 0.971 bits

Ganho de informação é a redução da impureza (entropia ou Gini) após uma divisão.

IG(S, feature, threshold) = Impurity(S) - weighted_avg(Impurity(S_left), Impurity(S_right))

where the weights are the proportions of samples in each child.

O algoritmo ganancioso em cada nó: experimente todos os recursos e todos os limites possíveis. Escolha o par (recurso, limite) que maximiza o ganho de informação.

Como funciona a divisão

Para um conjunto de dados com n recursos e m amostras no nó atual:

1. Para cada recurso j (j = 1 a n):
   • Classifique as amostras pelo recurso j
   • Experimente cada ponto médio entre valores distintos consecutivos como limite
   • Calcular o ganho de informação para cada limite
2. Selecione o recurso e o limite com o maior ganho de informação
3. Divida os dados em esquerda (recurso <= limite) e direita (recurso> limite)
4. Recorrência em cada criança

Esta abordagem gananciosa não garante a árvore globalmente ideal. Encontrar a árvore ideal é NP-difícil. Mas a divisão gananciosa funciona bem na prática.

Condições de parada

Sem condições de parada, a árvore cresce até que cada folha esteja pura (uma amostra por folha). Isso memoriza perfeitamente os dados de treinamento e generaliza terrivelmente.

A pré-poda interrompe a árvore antes que ela cresça totalmente:

• Profundidade máxima: pare de dividir quando a árvore atingir uma profundidade definida
• Mínimo de amostras por folha: pare se um nó tiver menos de k amostras
• Ganho mínimo de informação: pare se a melhor divisão melhorar a impureza em menos de um limite
• Máximo de nós folha: limite o número total de folhas

Pós-poda a árvore cresce inteira e depois a poda:

• Poda de complexidade de custo (usada por scikit-learn): adiciona uma penalidade proporcional ao número de folhas. Aumente a penalidade para obter árvores menores
• Redução de erros de remoção: remova uma subárvore se o erro de validação não aumentar

A pré-poda é mais simples e rápida. A pós-poda geralmente produz árvores melhores porque não interrompe prematuramente as divisões que podem levar a novas divisões úteis.

Árvores de decisão para regressão

Para regressão, a previsão da folha é a média dos valores alvo nessa folha. O critério de divisão também muda:

Redução de variância substitui ganho de informação:

VR(S, feature, threshold) = Var(S) - weighted_avg(Var(S_left), Var(S_right))

Escolha a divisão que reduz mais a variância. A árvore particiona o espaço de entrada em regiões e prevê uma constante (a média) em cada região.

Florestas aleatórias: o poder dos conjuntos

Uma única árvore de decisão apresenta alta variância. Pequenas alterações nos dados podem produzir árvores completamente diferentes. As florestas aleatórias corrigem isso calculando a média de muitas árvores.

graph TD
    D["Training Data"] --> B1["Bootstrap Sample 1"]
    D --> B2["Bootstrap Sample 2"]
    D --> B3["Bootstrap Sample 3"]
    D --> BN["Bootstrap Sample N"]
    B1 --> T1["Tree 1<br>(random feature subset)"]
    B2 --> T2["Tree 2<br>(random feature subset)"]
    B3 --> T3["Tree 3<br>(random feature subset)"]
    BN --> TN["Tree N<br>(random feature subset)"]
    T1 --> V["Aggregate Predictions<br>(majority vote or average)"]
    T2 --> V
    T3 --> V
    TN --> V

Duas fontes de aleatoriedade tornam as árvores diversas:

Bagging (agregação de bootstrap): Cada árvore é treinada em uma amostra de bootstrap, uma amostra aleatória com substituição dos dados de treinamento. Cerca de 63% das amostras originais aparecem em cada bootstrap (o restante são amostras prontas que podem ser usadas para validação).

Aleatorização de recursos: Em cada divisão, apenas um subconjunto aleatório de recursos é considerado. Para classificação, o padrão é sqrt(n_features). Para regressão, n_features/3. Isso evita que todas as árvores se dividam no mesmo recurso dominante.

O principal insight: calcular a média de muitas árvores decorrelacionadas reduz a variância sem aumentar o viés. Cada árvore individual pode ser medíocre. O conjunto é forte.

Importância do recurso

As florestas aleatórias fornecem naturalmente pontuações de importância de recurso. O método mais comum:

Diminuição Média de Impureza (MDI): Para cada recurso, some a redução total de impureza em todas as árvores e todos os nós onde esse recurso é usado. Os recursos que produzem maiores reduções de impurezas em divisões anteriores são mais importantes.

importance(feature_j) = sum over all nodes where feature_j is used:
    (n_samples_at_node / n_total_samples) * impurity_decrease

Isso é rápido (calculado durante o treinamento), mas direcionado para recursos de alta cardinalidade e recursos com muitos pontos de divisão possíveis.

Importância da permutação é a alternativa: embaralhe os valores de um recurso e meça o quanto a precisão do modelo cai. Mais confiável, mas mais lento.

Quando as árvores vencem as redes neurais

Árvores e florestas dominam as redes neurais em dados tabulares. Vários motivos:

As redes neurais vencem quando os dados possuem estrutura espacial ou sequencial (imagens, texto, áudio). Para tabelas planas de recursos, as árvores são o padrão.

Construa

Etapa 1: Impureza e entropia de Gini

Crie ambos os critérios de divisão do zero e verifique se eles concordam sobre quais divisões são boas.

import math

def gini_impurity(labels):
    n = len(labels)
    if n == 0:
        return 0.0
    counts = {}
    for label in labels:
        counts[label] = counts.get(label, 0) + 1
    return 1.0 - sum((c / n) ** 2 for c in counts.values())

def entropy(labels):
    n = len(labels)
    if n == 0:
        return 0.0
    counts = {}
    for label in labels:
        counts[label] = counts.get(label, 0) + 1
    return -sum(
        (c / n) * math.log2(c / n) for c in counts.values() if c > 0
    )

Passo 2: Encontre a melhor divisão

Experimente todos os recursos e todos os limites. Retorne aquele com maior ganho de informação.

def information_gain(parent_labels, left_labels, right_labels, criterion="gini"):
    measure = gini_impurity if criterion == "gini" else entropy
    n = len(parent_labels)
    n_left = len(left_labels)
    n_right = len(right_labels)
    if n_left == 0 or n_right == 0:
        return 0.0
    parent_impurity = measure(parent_labels)
    child_impurity = (
        (n_left / n) * measure(left_labels) +
        (n_right / n) * measure(right_labels)
    )
    return parent_impurity - child_impurity

Etapa 3: Construa a classe DecisionTree

Divisão recursiva, previsão e rastreamento de importância de recursos.

class DecisionTree:
    def __init__(self, max_depth=None, min_samples_split=2,
                 min_samples_leaf=1, criterion="gini",
                 max_features=None):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.min_samples_leaf = min_samples_leaf
        self.criterion = criterion
        self.max_features = max_features
        self.tree = None
        self.feature_importances_ = None

    def fit(self, X, y):
        self.n_features = len(X[0])
        self.feature_importances_ = [0.0] * self.n_features
        self.n_samples = len(X)
        self.tree = self._build(X, y, depth=0)
        total = sum(self.feature_importances_)
        if total > 0:
            self.feature_importances_ = [
                fi / total for fi in self.feature_importances_
            ]

    def predict(self, X):
        return [self._predict_one(x, self.tree) for x in X]

Etapa 4: Construa a classe RandomForest

Amostragem bootstrap, randomização de recursos e votação majoritária.

class RandomForest:
    def __init__(self, n_trees=100, max_depth=None,
                 min_samples_split=2, max_features="sqrt",
                 criterion="gini"):
        self.n_trees = n_trees
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.max_features = max_features
        self.criterion = criterion
        self.trees = []

    def fit(self, X, y):
        n = len(X)
        for _ in range(self.n_trees):
            indices = [random.randint(0, n - 1) for _ in range(n)]
            X_boot = [X[i] for i in indices]
            y_boot = [y[i] for i in indices]
            tree = DecisionTree(
                max_depth=self.max_depth,
                min_samples_split=self.min_samples_split,
                max_features=self.max_features,
                criterion=self.criterion,
            )
            tree.fit(X_boot, y_boot)
            self.trees.append(tree)

    def predict(self, X):
        all_preds = [tree.predict(X) for tree in self.trees]
        predictions = []
        for i in range(len(X)):
            votes = {}
            for preds in all_preds:
                v = preds[i]
                votes[v] = votes.get(v, 0) + 1
            predictions.append(max(votes, key=votes.get))
        return predictions

Veja code/trees.py para a implementação completa com todos os métodos auxiliares.

Use-o

Com scikit-learn, treinar uma random forest tem três linhas:

from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

X, y = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=42)

rf = RandomForestClassifier(n_estimators=100, random_state=42)
rf.fit(X_train, y_train)
print(f"Accuracy: {rf.score(X_test, y_test):.4f}")
print(f"Feature importances: {rf.feature_importances_}")

Na prática, árvores com gradiente aumentado (XGBoost, LightGBM, CatBoost) são frequentemente mais fortes do que florestas aleatórias porque constroem árvores sequencialmente, com cada árvore corrigindo os erros das anteriores. Mas as florestas aleatórias são mais difíceis de configurar incorretamente e quase não exigem ajuste de hiperparâmetros.

Envie

Esta lição produz outputs/prompt-tree-interpreter.md – um prompt que interpreta as divisões da árvore de decisão para as partes interessadas do negócio. Alimente-o com a estrutura de uma árvore treinada (profundidade, recursos, limites de divisão, precisão) e ele traduz o modelo em regras de linguagem simples, classifica a importância do recurso, sinaliza overfitting ou vazamento e recomenda as próximas etapas. Use-o sempre que precisar explicar um modelo baseado em árvore para alguém que não lê código.

Exercícios

1. Treine uma única árvore de decisão em um conjunto de dados 2D com 3 classes. Trace manualmente as divisões e desenhe os limites de decisão retangulares. Compare os limites em max_profundidade=2 vs max_profundidade=10.

2. Implementar divisão de redução de variância para árvores de regressão. Gere y = sin(x) + ruído para 200 pontos e ajuste sua árvore de regressão. Trace as previsões constantes por partes da árvore em relação à curva verdadeira.

3. Construa uma random forest com 1, 5, 10, 50 e 200 árvores. Trace a precisão do treinamento e a precisão do teste em relação ao número de árvores. Observe que a precisão do teste se estabiliza, mas não diminui (as florestas resistem ao overfitting).

4. Compare a impureza de Gini versus a entropia como critérios de divisão em 5 conjuntos de dados diferentes. Meça a precisão e a profundidade da árvore. Na maioria dos casos, eles produzem resultados quase idênticos. Explique por quê.

5. Implemente a importância da permutação. Compare-o com a importância do MDI em um conjunto de dados onde um recurso é ruído aleatório, mas tem alta cardinalidade. O MDI classificará altamente o recurso de ruído. A importância da permutação não.

Termos-chave

Leitura Adicional

• Breiman: Random Forests (2001) - o artigo florestal aleatório original
• Grinsztajn et al.: Por que os modelos baseados em árvore ainda superam o aprendizado profundo em dados tabulares? (2022) - comparação rigorosa de árvores versus redes neurais em tarefas tabulares
• scikit-learn Documentação das Árvores de Decisão - guia prático com ferramentas de visualização
• XGBoost: Um sistema de árvore escalável Boosting (Chen & Guestrin, 2016) - o papel de aumento de gradiente que domina Kaggle