Árvore de decisão – o poder surpreendente das regras de decisão aninhadas

 (mlu-explain.github.io)
3 pontos por GN⁺ 2026-03-02 | 1 comentários | Compartilhar no WhatsApp
  • Estrutura que particiona repetidamente o espaço de características para classificar dados, escolhendo em cada etapa a divisão com maior ganho de informação
  • Usa a entropia (Entropy) para medir a pureza (purity) dos dados e, com base nisso, calcula o ganho de informação (Information Gain)
  • O algoritmo ID3 encontra o ponto de divisão ideal calculando a diferença de entropia entre o nó pai e os nós filhos, expandindo a árvore recursivamente
  • Também é possível usar a impureza de Gini no lugar da entropia, e os dois métodos normalmente mostram resultados semelhantes, mas com eficiência computacional diferente
  • Divisões excessivas causam overfitting e instabilidade, por isso isso é mitigado com poda (pruning) ou Random Forest

Conceitos básicos de árvores de decisão

  • A árvore de decisão divide os dados de cima para baixo e, em cada etapa, aplica regras condicionais para separar os dados em regiões bem distinguidas
    • Cada divisão é determinada por uma característica (feature) específica e um limiar (cutoff value)
    • O objetivo é criar nós puros em que as classes fiquem bem separadas na classificação

Definição e propriedades da entropia (Entropy)

  • A entropia é uma métrica que mede a incerteza da informação, definida para uma probabilidade (p_i) como (H = -\sum p_i \log_2(p_i))
  • Principais propriedades
    1. Quando apenas um evento tem probabilidade 1 e os demais 0, (H=0), ou seja, não há incerteza
    2. Quando todos os eventos têm a mesma probabilidade, a entropia atinge o máximo e representa o estado mais impuro
    3. Quanto mais uniforme a distribuição de probabilidades, maior a entropia
  • Portanto, nós puros têm entropia 0, enquanto nós mistos têm valores altos de entropia

Ganho de informação (Information Gain) e o algoritmo ID3

  • O ganho de informação é calculado pela diferença de entropia antes e depois da divisão e representa a eficiência da partição dos dados
    • Fórmula: (\Delta IG = H_{\text{parent}} - \frac{1}{N}\sum N_{\text{child}} \cdot H_{\text{child}})
  • Etapas do algoritmo ID3
    1. Calcular a entropia de cada característica
    2. Dividir o conjunto de dados usando vários critérios de divisão e calcular o ganho de informação
    3. Selecionar a divisão com maior ganho de informação para criar o nó de decisão
    4. Criar um nó folha quando não for mais possível dividir
    5. Executar o processo recursivamente para todos os subconjuntos, interrompendo quando todos os elementos pertencerem à mesma classe
  • Por exemplo, a condição Diameter ≤ 0.45 foi escolhida como a primeira divisão porque apresentou o maior ganho de informação, 0.574

Impureza de Gini e medida alternativa

  • A impureza de Gini (Gini impurity) é uma alternativa à entropia, sendo outra forma de medir a impureza da informação
    • Como não exige cálculo de logaritmo, tem maior velocidade de cálculo
    • Em conjuntos de dados desbalanceados, a entropia pode ser uma escolha mais criteriosa
  • Em geral, os dois métodos produzem resultados semelhantes

Problemas de overfitting e instabilidade

  • Como o algoritmo ID3 continua dividindo para minimizar a entropia, a árvore pode ficar excessivamente profunda
    • Isso provoca overfitting, reduzindo a capacidade de generalização em dados novos
  • Também existe o problema de instabilidade (alta variância), em que pequenas mudanças nos dados podem alterar bastante a estrutura da árvore
    • Exemplo: mesmo adicionando um pequeno ruído gaussiano a 5% dos dados de treinamento, pode ser gerada uma árvore completamente diferente
  • Como solução, a poda (pruning) pode limitar a profundidade da árvore, o número de folhas, a quantidade mínima de amostras etc.

Expansão para Random Forest

  • Para reduzir a instabilidade de uma única árvore de decisão, usa-se uma abordagem que treina várias árvores com diferentes amostras de dados e combina suas previsões
    • Essa abordagem é a Random Forest, que oferece alta estabilidade e bom desempenho de generalização
  • Isso compensa as desvantagens das árvores de decisão e é avaliado como um dos algoritmos de machine learning mais bem-sucedidos até hoje

Conclusão e aprendizado adicional

  • A árvore de decisão é um modelo fácil de interpretar, rápido de treinar e com pré-processamento simples
  • No entanto, para resolver os problemas de overfitting e instabilidade, são necessárias poda ou técnicas de ensemble
  • O texto não aborda árvores para regressão, preferência por end-cut, hiperparâmetros etc., e recomenda aprendizado adicional por meio de materiais relacionados

Leituras relacionadas

1 comentários

 
GN⁺ 2026-03-02
Comentários do Hacker News

  • A arma secreta que funcionou muito bem para mim ao treinar classificadores foi primeiro treinar um bom classificador linear
    Depois, usar a saída não limiarizada desse classificador como uma dimensão adicional de característica para treinar uma árvore de decisão, e então envolver isso em um sistema de árvores com boosting
    Assim, o modelo linear compensa as fraquezas da árvore de decisão e, por outro lado, a árvore lida com as partes em que o modelo linear tem dificuldade
    Também dá para considerar rotação dos dados ou normalização dos eixos, mas na maioria das vezes isso não foi necessário
    No entanto, quando as características são muito esparsas, a árvore tem dificuldade para encontrar pontos de divisão

    • Pensando bem, isso é uma abordagem parecida com a usada em aprendizado por reforço
      Você adiciona cálculos ao estado bruto (raw state) para criar um estado observado (observed state) e então treina com isso
      Por exemplo, no jogo da cobrinha, em vez de usar só as coordenadas da cobra, você também calcula características derivadas, como o número de rotas de fuga
    • O calcanhar de Aquiles das árvores de decisão é, no fim das contas, a engenharia de atributos
      Se você não limpar os dados e projetar bem as características, o resultado fica muito pior do que em modelos caixa-preta como redes neurais
      Ironicamente, redes neurais encontram essas características latentes sozinhas, mas é difícil interpretar por que funcionam desse jeito
    • Existem várias variações de árvores para diferentes objetivos
      Oblique Decision Tree, Model Tree (M5), Logistic Model Tree (LMT) e Hierarchical Mixture of Experts (HME) são alguns exemplos
    • Fiquei curioso sobre o que exatamente significa a expressão “as regiões de rótulo igual têm uma estrutura particionada”
    • Essa ideia também se parece com o ponto central do artigo sobre IRM de Arjovsky, Bottou e outros

  • Quando eu trabalhava no CERN por volta de 2010, o classificador mais popular era o Boosted Decision Tree
    Isso acontecia por causa do equilíbrio entre explicabilidade e poder de representação, e na época havia uma resistência cultural a usar redes neurais em análise de física
    Hoje os tempos mudaram bastante

    • Essa mudança me preocupa um pouco
      Na física, entender o mecanismo causal é mais importante do que simplesmente ajustar bem uma curva
      É como o sistema de epiciclos de Ptolomeu, que se ajustava melhor ao movimento dos astros, mas não explicava a causa
    • Eu também venho da física teórica e, ao usar árvores de decisão em outras áreas, achei que a “explicabilidade” delas é um pouco superestimada
      Basta a profundidade aumentar um pouco para virar quase uma selva impossível de interpretar
      Com redes neurais acontece algo parecido: dá para seguir as operações internas, mas no fim ainda não dá para saber por que aquela decisão foi tomada
    • Fiquei curioso se Boosted Decision Tree e Boosted Random Forest são a mesma coisa

  • Há também uma explicação de Random Forest no mesmo site → mlu-explain/random-forest

  • Fato interessante: uma rede neural de 1 bit (single-bit neural network) é, na prática, uma árvore de decisão
    Em teoria, a maioria das redes neurais pode ser “compilada” em cadeias de if-else, mas ainda não está claro em que condições isso funciona bem

    • Li o artigo “redes neurais são árvores de decisão” (arXiv:2210.05189), mas na prática a árvore fica enorme
      Parece mais uma expansão do conceito, então é difícil ver isso como um mapeamento direto
      Seria bom explicar melhor em que sentido exatamente isso está sendo dito
    • Fiquei curioso se existe algum software ou artigo que faça essa conversão de fato. Parece um projeto de fim de semana divertido

  • A maior vantagem das árvores de decisão é a velocidade
    Em um ambiente de baixa latência, tentei substituir classificadores baseados em árvore por pequenas redes neurais, mas as redes neurais tinham precisão um pouco maior e latência de inferência mais de 100 vezes maior

    • Além disso, uma árvore de decisão única é fácil de portar diretamente para dispositivos de borda
      Já árvores com boosting ou bagging são complexas, e outros algoritmos clássicos de ML também têm portabilidade menor

  • Em algum livro-texto de ML (provavelmente o ESL), árvores de decisão eram descritas assim
    “São interpretáveis, rápidas, funcionam bem com vários tipos de dados, são pouco sensíveis a escalonamento e têm poucos parâmetros de ajuste, mas... não funcionam tão bem”
    Claro, bagging e boosting podem compensar essa desvantagem, mas nesse processo elas perdem parte das vantagens originais

  • Eu realmente gosto de árvores de decisão. É meu algoritmo clássico de ML favorito
    Cheguei a fazer uma implementação paralela puramente funcional em GNU Guile → link para o código
    Só que o Guile não tem algo como NumPy ou DataFrame, então a representação dos dados fica ineficiente

    • Fiquei curioso sobre em que pontos NumPy ou DataFrame são melhores que Guile
      Guile é adequado para manipulação de árvores, então parece natural para implementar árvores de decisão
      Ainda assim, compilar para código de máquina provavelmente seria mais eficiente
      Como referência, também vale olhar o Lush(https://lush.sourceforge.net/) e o aiscm(https://wedesoft.github.io/aiscm/)

  • A tomada de decisão ambígua de especialistas muitas vezes também pode ser modelada com árvores de decisão simples ou cadeias de decisão
    O próprio especialista acha que o processo é complexo, mas em muitos casos uma árvore simples explica melhor
    Antigamente, regressão ou clustering baseado em distância pareciam mais sofisticados, mas árvores são muito mais eficazes
    Isso é discutido em detalhes no capítulo 7 de Oxford Handbook of Expertise

    • Em uma visualização que vi no passado, as decisões eram mostradas como uma partição do espaço em um plano 2D
      No fim, uma árvore de decisão é uma estrutura que divide o espaço de possibilidades, como uma kD-Tree, e atribui uma ação a cada região
      O julgamento sutil de especialistas vem da delicadeza das fronteiras, mas as árvores ainda oferecem uma aproximação muito boa

  • O site é interessante e a apresentação estava boa
    Mas o contraste de cores de alguns textos era baixo demais, então ficava difícil ler

    • Também pensei a mesma coisa. O Reader View do Firefox ajuda bastante
      Acessibilidade não é só para pessoas com deficiência, é um elemento básico para melhorar a legibilidade

  • Hoje em dia, na era do deep learning, árvores de decisão estão sendo subestimadas
    Mas elas ainda são interpretáveis, rápidas e práticas o bastante
    Eu criei um sistema de pontuação para análise de sites baseado em árvore,
    que avalia condições como “há meta description?”, “carrega em menos de 3 segundos?”, “é responsivo no mobile?”
    O usuário entende imediatamente por que recebeu aquela pontuação
    Explicar por que uma rede neural deu nota 73 é impossível, mas com árvores isso é fácil