Introdução: Árvores de decisão e a necessidade de pureza

Árvores de decisão são um dos algoritmos de aprendizagem supervisionado mais intuitivas e amplamente utilizados no aprendizado de máquina. Eles modelam decisões como uma estrutura de árvore, onde nós internos representam testes em recursos, ramos representam resultados desses testes e nós de folhas representam previsões finais. Se você está classificando se um e-mail é spam ou prevendo preços de casa, árvores de decisão oferecem uma abordagem transparente, legível pelo homem.

O desafio principal ao construir uma árvore de decisão é decidir onde para dividir os dados em cada nó. O algoritmo deve escolher o valor da funcionalidade e da divisão que melhor separa as classes alvo. É aqui que ]entropia entra. A entropia, emprestada da teoria da informação, fornece uma medida matemática de incerteza ou impureza em um conjunto de dados. Ao minimizar a entropia após cada divisão, as árvores de decisão criam subconjuntos cada vez mais homogêneos, levando a modelos precisos e eficientes.

O que é entropia? Uma medida de desordem

Na linguagem diária, a entropia refere- se à aleatoriedade ou caos. No contexto das árvores de decisão, a entropia quantifica a quantidade de imprevisibilidade num conjunto de dados em relação à variável- alvo. Se todos os exemplos num nó pertencem à mesma classe, o nó é ]puro e a sua entropia é zero. Por outro lado, se as classes forem uniformemente misturadas, a entropia atinge o seu máximo.

Para um problema de classificação binária (por exemplo, positivo vs negativo), a entropia é definida como:

Entropia = –p+ log2(p+) – p− log2(p−)

onde p+ é a proporção de exemplos positivos e p− = 1 – p+. A base de logaritmo 2 é usada porque a informação em bits é medida em binário. Quando há mais de duas classes, a fórmula generaliza para:

Entropia = –ē pi log2(pi)] para todas as classes i.

O valor resultante varia de 0 (perfeitamente puro) a log2( k) para classes k (imumidade máxima). Para um caso binário, a entropia máxima é de 1, 0 quando p+ = p− = 0, 5.

Um Exemplo Rápido

Considere um conjunto de dados de 10 amostras com 5 positivos e 5 negativos. Entropia = –0,5 log2(0,5) – 0,5 log2(0,5) = –0,5 * (–1) – 0,5 * (–1) = 0,5 + 0,5 = 1,0. Agora considere um conjunto de dados com 9 positivos e 1 negativo: entropia = –0,9 log2(0,9) – 0,1 log2(0,1) □ –0,9 * (–0,152) – 0,1 * (–3,322) □ 0,137 + 0,332 = 0,469. O segundo conjunto de dados é muito mais previsível.

Porquê a Base 2?

A escolha da base 2 está enraizada na teoria da informação de Claude Shannon. Um pouco é a unidade fundamental da informação, representando uma escolha binária. Usar a base 2 significa entropia dá o número médio de bits necessários para codificar a classe de uma amostra aleatória. Se você já conhece a distribuição, menor entropia significa que são necessários menos bits para comunicar o resultado.

Ganho de Informação: Como os guias de entropia se dividem

Simplesmente calcular a entropia não é suficiente; o objetivo é ]reduzir após dividir. O ganho de informação (IG) mede a redução esperada da entropia causada pela partição dos dados de acordo com uma funcionalidade. O recurso e o valor de divisão que produz o ganho de informação mais alto são escolhidos para o nó.

A fórmula para ganho de informação é:

Ganho de Informação = Entropia(pai) – □ ('Si' / □S') * Entropia(Si)[

onde S é o conjunto de dados dos pais, Si são os subconjuntos das crianças após a divisão, e . . . . . denota o número de amostras. A soma é uma média ponderada das entropias das crianças.

Exemplo trabalhado

Imagine um nó pai com 30 amostras: 16 classe A e 14 classe B. Entropia(pai) = –(16/30) log2(16/30) – (14/30) log2(14/30) . 0,996.

Agora considere uma divisão na Característica X que cria duas crianças: Child1 tem 20 amostras (15 A, 5 B) → entropia = –0,75 log2(0,75) – 0,25 log2(0,25) □ 0,811; Child2 tem 10 amostras (1 A, 9 B) → entropia = –0,1 log2(0,1) – 0,9 log2(0,9) □ 0,469. Entropia infantil ponderada = (20/30)* 0,811 + (10/30)* 0,469 □ 0,541 + 0,156 = 0,697. Ganho de informação = 0,996 – 0,697 = 0,299.

Se outra divisão produz maior IG, essa divisão é preferida. O algoritmo avalia todas as funcionalidades e possíveis limiares de divisão para encontrar o melhor.

Limitações de ganho de informação

O ganho de informação tende a favorecer características com muitos valores distintos (por exemplo, uma coluna ID única) porque dividir em tal característica cria muitas crianças puras, produzindo alto IG. Isso pode levar a uma sobreposição. Para contrariar isso, variantes como ]Gain Ratio (usado em C4.5) normalizam IG pela informação intrínseca da divisão. Outra abordagem é usar a Gini impureza[, que é computacionalmente mais barato e muitas vezes produz resultados semelhantes.

Comparando entropia com impureza Gini

A impureza Gini é um critério alternativo de divisão utilizado no algoritmo CART (Classificação e Árvores de Regressão). Mede a probabilidade de erro na classificação de uma amostra escolhida aleatoriamente se for rotulada aleatoriamente de acordo com a distribuição da classe no nó. A fórmula:

Gini = 1 – √ pi2

Para um caso binário, Gini = 2p+(1 – p+). O máximo de Gini é 0,5 (classes equilibradas) e o mínimo é 0 (puro).

Tanto a entropia como a impureza Gini são funções convexas, o que significa que se comportam de forma semelhante na prática. A escolha entre elas muitas vezes se resume à eficiência computacional: Gini não requer logaritmos, por isso pode ser ligeiramente mais rápida. Contudo, a entropia tem uma justificação teórico-informação mais forte. Muitas bibliotecas, incluindo o scikit- learn, podem escolher; empiricamente, as diferenças são pequenas.

Entropia nas Árvores de Regressão

Árvores de decisão também podem resolver problemas de regressão (prevendo valores contínuos). Em regressão, a entropia não é apropriada porque o alvo não é categórico. Ao invés disso, o algoritmo usa ] redução de variância] ou erro médio ao quadrado (MSE) como critério de divisão. A ideia é análoga: em cada nó, nós nos dividimos para minimizar a soma ponderada das variâncias dos nós filhos. Isto maximiza a homogeneidade dos valores-alvo em cada região.

Para regressão, a quantidade é frequentemente chamada ]mean squared error reduction ou total variância reduction[. O princípio é exatamente o mesmo que ganho de informação: mede a impureza (variância) do pai, depois a média ponderada das crianças, e maximiza a diferença.

Construindo uma árvore de decisão completa: Da raiz à folha

Agora que entendemos a entropia e o ganho de informação, vamos analisar como um algoritmo típico de aprendizagem de árvore de decisão (como ID3, C4.5, ou CART) constrói uma árvore:

  1. Iniciar com todo o conjunto de dados no nó raiz.
  2. Calcular a impureza da raiz usando entropia (para classificação) ou variância (para regressão).
  3. Para cada recurso, avaliar cada ponto de divisão possível (para características numéricas, valores de ordenação e considerar pontos médios entre valores distintos consecutivos; para características categóricas, considerar subconjuntos ou codificação de um-quente).
  4. Calcular ganho de informação (ou razão de ganho, redução de Gini, etc.) para cada divisão.
  5. Escolha a divisão que produz o maior ganho.
  6. Participação dos dados e repetindo recursivamente os passos 2–5 para cada nó filho.
  7. Critérios de paragem impedem o crescimento infinito: profundidade máxima, amostras mínimas por folha, diminuição mínima da impureza, ou quando todas as amostras de um nó pertencem a uma classe.
  8. Prune a árvore (quer pré-pruning via hiperparameters ou pós-pruning cortando ramos que não melhoram o desempenho em um conjunto de validação) para combater o excesso de ajuste.

Manuseamento de características categóricas e numéricas

A divisão baseada em entropia funciona para ambos os tipos de recursos, mas a abordagem difere:

  • Características numéricas: O algoritmo classifica os valores únicos e testa cada limiar possível. Para eficiência, muitas vezes só considera limiares entre valores ordenados consecutivos onde a etiqueta da classe muda.
  • Características categóricas: Para as divisões binárias, o algoritmo pode considerar agrupar categorias em dois subconjuntos.Para as divisões multidirecionais (como em ID3), cada categoria torna-se um ramo. No entanto, os dados de fragmentos multidirecionais dividem rapidamente e são propensos a sobre-ajustar, então a maioria das implementações modernas usam divisões binárias mesmo para características categóricas.

Manuseando valores em falta

Os conjuntos de dados do mundo real frequentemente contêm valores em falta. As árvores de decisão podem lidar com eles de várias maneiras:

  • Surrogar splits: Ao dividir em uma funcionalidade, uma funcionalidade de backup que melhor imita a split é usada para amostras que não possuem a característica primária.
  • Exactações fraccionais: Atribuir uma amostra a múltiplas crianças com pesos proporcionais à probabilidade de cada criança com base em dados não perdidos.
  • Simples imputation: Substituir valores em falta pelo modo ou mediana antes de construir a árvore.

Muitas bibliotecas, como o scikit-learn, não lidam com valores em falta internamente e esperam que eles sejam imputados de antemão. XGBoost e LightGBM, no entanto, aprendem a melhor direção para valores em falta durante o treinamento.

Superfit e poda

Uma árvore de decisão cultivada até a profundidade máxima irá memorizar perfeitamente os dados de treinamento, incluindo ruído, levando a uma má generalização. A redução da entropia continua até que cada folha seja pura, mas isso raramente beneficia o desempenho do teste. Duas estratégias principais de controle sobrefitting:

Pré-pruning (Paragem precoce)

Parar o crescimento da árvore antes de sobre-ajustar-se aplicando restrições: limite a profundidade máxima, exija um número mínimo de amostras por folha, ou exija uma redução mínima da impureza (por exemplo, a diminuição da entropia deve ser > 0,01). Estes hiperparametros são sintonizados usando validação cruzada.

Pós-aptidão (Poda de complexidade da base)

Crescer a árvore completamente, então remover ramos que adicionam pouco valor. O algoritmo considera um trade-off entre a complexidade da árvore (número de folhas) e erro de treino. Um parâmetro de complexidade (alfa) penaliza as folhas adicionais. O Scikit- learn ] oferece poda de custo-complexidade via .

Ambas as técnicas de poda ajudam a garantir que as divisões orientadas pela entropia não sejam muito granulares e que a árvore permaneça interpretável enquanto generaliza bem.

Entropia em Métodos de Conjunto

Enquanto uma única árvore de decisão pode ser instável (pequenas mudanças de dados podem resultar em uma árvore muito diferente), a entropia continua a ser um conceito fundamental em métodos de conjunto:

  • Florestas de Random: Construir muitas árvores usando amostras de bootstrap e subconjuntos de características aleatórias. Cada árvore normalmente usa entropia ou Gini para dividir. As previsões de médias florestais, reduzindo a variância.
  • Gradient Boosting: As árvores são construídas sequencialmente para corrigir erros de árvores anteriores. A entropia é usada como objetivo (via perda de entropia cruzada) para classificação de florestas em bibliotecas como o XGBoost.

Compreender a entropia ajuda a interpretar por que uma divisão em particular foi escolhida em qualquer árvore individual, o que é essencial para a análise de depuração de modelos e importância de recursos.

Considerações Práticas ao Usar a Entropia

Primeiro, computar entropia usando logaritmos cuidadosamente — evite log(0) indefinido definindo 0 log2(0) como 0. Segundo, esteja ciente de que os cálculos de entropia são sensíveis ao desequilíbrio de classes; um nó com 99% uma classe e 1% outra tem baixa entropia, mas pode não indicar uma boa divisão se a classe minoritária é importante. Nesse caso, classes de ponderação ou usando métricas alternativas (por exemplo, F1) para avaliação é aconselhável.

Também, árvores de decisão com entropia pode ser memória-intensiva para grandes conjuntos de dados porque eles avaliam todos os recursos e pontos divididos. Bibliotecas usam algoritmos como sort-and-scan[] para calcular entropia para recursos numéricos em O(n log n) tempo.

Referências externas para leitura mais profunda:

Além da classificação: Entropia e ganho de informação na seleção de recursos

A entropia não é usada apenas dentro de árvores de decisão — ela também pode ter técnicas de seleção. Informações Mutuais] entre o recurso e o alvo está diretamente relacionado com o ganho de informação. Você pode classificar as características por suas informações mútuas para reduzir a dimensionalidade antes de treinar outros modelos. Esta é uma alternativa não linear para a análise de correlação.

Por exemplo, se o recurso X tem alta informação mútua com o alvo Y, então saber X reduz substancialmente a incerteza sobre Y. Esta é exatamente a redução da entropia alcançada dividindo em X. Bibliotecas como o scikit-learn fornecem e .

Limitações das árvores de decisão baseadas em entropia

Apesar do seu poder, as árvores de decisão construídas com entropia têm alguns inconvenientes:

  • Instabilidade: Pequenas variações de conjuntos de dados podem alterar drasticamente a estrutura da árvore.
  • Bias para recursos com muitos níveis: O ganho de informação favorece recursos de alta cardioriedade. Ganhe relação ou usando apenas splits binários ajuda.
  • Pobre manipulação da estrutura aditiva: Árvores são modelos constantes em partes, por isso, elas lutam para aprender relações lineares.
  • Natureza de Greedy: O algoritmo torna as divisões localmente ótimas, o que pode não ser globalmente ótimo.

Na prática, combinar árvores de decisão baseadas em entropia com ajuste de hiperparametros e métodos de ensemble produz modelos robustos para muitos conjuntos de dados tabulares.

Conclusão: Entropia como uma Fundação para Dividimentos Perspicazes

A entropia fornece uma forma teórica-informação de princípios para avaliar a qualidade de uma divisão ao construir uma árvore de decisão. Ao medir o distúrbio em um conjunto de dados e objetivando reduzi-lo a cada passo, podemos construir árvores que particionem eficiente e com precisão o espaço de recursos. Se você é um estudante de aprendizagem de máquina ou um praticante que implante modelos, entender a entropia aprofunda sua compreensão de como as árvores de decisão “pensam”. Também se conecta a conceitos mais amplos como informação mútua, seleção de recursos e até compressão de dados.

Ao aplicar árvores de decisão, lembre-se que a entropia é uma ferramenta — não um fim. Emparelhe-a com técnicas de validação, poda e ensemble adequadas para desbloquear todo o seu potencial. E se você estiver gerenciando pipelines de dados para aprendizado de máquina, ferramentas como o Directus podem ajudá-lo a coletar, organizar e servir os conjuntos de dados de alta qualidade que dependem das árvores de decisão.