Arquitetura e Conceitos Centrais

Uma árvore de decisão opera como um fluxo de perguntas lógicas que particionam progressivamente um espaço de dados. Em vez do clássico jogo de adivinhação, pense em um sistema de aprovação de crédito bancário:

• Nó Raiz: O ponto de partida que avalia o atributo mais discriminativo (ex: "A renda é superior a X?").
• Nós Internos: Testes subsequentes aplicados aos subconjuntos de dados (ex: "O score de crédito é bom?").
• Nós Folha (Terminais): A conclusão do fluxo, entregando um rótulo de classe ou um valor numérico (ex: "Empréstimo Aprovado").
• Ramos: As transições que conectam os nós, ditadas pelos resultados dos testes.

Do ponto de vista algorítmico, essas estruturas se dividem em duas categorias principais:

• Árvores de Classificação: Destinadas a variáveis alvo discretas. A folha retorna a classe majoritária do particionamento.
• Árvores de Regressão: Focadas em alvos contínuos. A previsão é geralmente a média aritmética dos valores alvo presentes no nó folha.

Métricas de Impureza e Seleção de Atributos

O processo de construção (indução) depende da identificação recursiva do atributo que melhor segrega os dados. Para quantificar a "qualidade" de uma segregação, utilizamos métricas de impureza.

1. Quantificando a Impureza do Nó

Considerando um nó $t$ com amostras distribuídas em $C$ classes, onde $p(c|t)$ é a proporção da classe $c$:

• Índice de Gini: $Gini(t) = 1 - \sum_{c=1}^{C} [p(c|t)]^2$. Mede a probabilidade de classificar incorretamente um elemento se ele for rotulado aleatoriamente de acordo com a distribuição do nó. É computacionalmente leve e padrão no algoritmo CART.
• Entropia de Shannon: $H(t) = - \sum_{c=1}^{C} p(c|t) \log_2 p(c|t)$. Avalia o grau de desordem informacional. Tende a criar árvores mais balanceadas, mas exige cálculos logarítmicos.
• Erro de Classificação: $E(t) = 1 - \max(p(c|t))$. Raramente usado para o crescimento da árvore devido à sua insensibilidade a pequenas variações de pureza, sendo mais útil em etapas de poda.

2. Critérios de Divisão Ótima

O objetivo é maximizar a homogeneidade dos nós filhos em relação ao nó pai.

• Ganho de Informação (ID3): A diferença entre a entropia do nó pai e a soma ponderada das entropias dos filhos. Possui um viés inerente favorecendo atributos com alta cardinalidade (muitos valores únicos).
• Razão do Ganho (C4.5): Normaliza o Ganho de Informação dividindo-o pela "Informação Intrínseca" (entropia da própria divisão), penalizando atributos que fragmentam excessivamente os dados.
• Redução de Variância (CART Regressão): Substitui a entropia pela variância estatística, buscando divisões que minimizem o desvio padrão dos valores contínuos nos nós resultantes.

Engenharia de Atributos e Dados Ausentes

A natureza dos dados dita a estratégia de particionamento:

• Variáveis Categóricas: Podem gerar divisões binárias (um valor contra o resto) ou multi-vias (um ramo para cada categoria).
• Variáveis Contínuas: Exigem a busca por um ponto de corte (threshold). O algoritmo ordena os valores e testa os pontos médios entre observações adjacentes, selecionando o corte que otimiza a métrica de impureza.
• Valores Ausentes: Algoritmos modernos (como XGBoost) aprendem a direção padrão para dados faltantes durante o treino. Em implementações clássicas, as instâncias podem ser fracionadas proporcionalmente entre os ramos filhos (método de pesos de C4.5).

Controle de Complexidade: Poda e Critérios de Parada

Permitir que a árvore cresça até a pureza absoluta resulta em sobreajuste (overfitting). O controle é feito em duas frentes:

• Pré-poda (Early Stopping): Interrompe o crescimento durante a construção. Exige a definição de hiperparâmetros como profundidade máxima, número mínimo de amostras por folha ou ganho de informação mínimo.
• Pós-poda: A árvore é construída integralmente e, em seguida, ramos que não contribuem significativamente para a validação cruzada são colapsados em nós folha. A Poda de Complexidade de Custo (CCP) introduz um parâmetro $\alpha$ que equilibra a taxa de erro do modelo com o número total de folhas.

Evolução dos Algoritmos e Métodos de Ensemble

Os algoritmos fundadores moldaram o ecossistema atual:

• ID3: Pioneiro, restrito a atributos categóricos e propenso a overfitting.
• C4.5: Introduziu suporte a variáveis contínuas, dados ausentes e a Razão do Ganho.
• CART: Unificou classificação e regressão, impondo uma estrutura estritamente binária e utilizando o índice de Gini.

Devido à alta variância de uma única árvore (pequenas alterações nos dados de treino geram estruturas completamente diferentes), a indústria adota massivamente os Métodos de Ensemble:

• Bagging (Random Forest): Treina múltiplas árvores em paralelo com amostragem bootstrap e seleção aleatória de atributos, reduzindo a variância através da média ou votação.
• Boosting (Gradient Boosting, XGBoost): Treina árvores sequencialmente, onde cada novo modelo foca em corrigir os resíduos (erros) dos modelos anteriores, reduzindo o viés e a variância simultaneamente.

Implementação Prática em Java

Abaixo está uma implementação orientada a objetos de uma árvore de decisão para classificação, utilizando um conjunto de dados simulado de aprovação de empréstimos. O código utiliza estruturas baseadas em Map para flexibilidade de atributos e implementa o cálculo de Entropia e Ganho de Informação.

import java.util.*;
import java.util.stream.*;

public class DecisionTreeInducer {

    static class Instance {
        Map<String, String> features;
        String target;

        Instance(Map<String, String> features, String target) {
            this.features = features;
            this.target = target;
        }
    }

    interface Node {
        String predict(Instance instance);
        void display(String indent);
    }

    static class Leaf implements Node {
        private final String prediction;
        public Leaf(String prediction) { this.prediction = prediction; }
        public String predict(Instance instance) { return prediction; }
        public void display(String indent) { System.out.println(indent + "=> " + prediction); }
    }

    static class Split implements Node {
        private final String attribute;
        private final Map<String, Node> branches;
        private final Node fallback;

        public Split(String attribute, Map<String, Node> branches, Node fallback) {
            this.attribute = attribute;
            this.branches = branches;
            this.fallback = fallback;
        }

        public String predict(Instance instance) {
            String val = instance.features.get(attribute);
            Node next = branches.getOrDefault(val, fallback);
            return next != null ? next.predict(instance) : "Unknown";
        }

        public void display(String indent) {
            System.out.println(indent + "[" + attribute + "]");
            for (var entry : branches.entrySet()) {
                System.out.println(indent + "  ├── " + entry.getKey() + ":");
                entry.getValue().display(indent + "  │   ");
            }
            if (fallback != null) {
                System.out.println(indent + "  └── Default:");
                fallback.display(indent + "      ");
            }
        }
    }

    static class Inducer {
        private final int maxLevel;
        private final double minInfoGain;

        public Inducer(int maxLevel, double minInfoGain) {
            this.maxLevel = maxLevel;
            this.minInfoGain = minInfoGain;
        }

        public Node grow(List<Instance> dataset, List<String> attributes, int currentLevel) {
            String majority = getMajorityClass(dataset);
            if (isHomogeneous(dataset) || currentLevel >= maxLevel || attributes.isEmpty()) {
                return new Leaf(majority);
            }

            String bestAttr = findOptimalSplit(dataset, attributes);
            if (bestAttr == null) return new Leaf(majority);

            Map<String, List<Instance>> partitions = groupByAttribute(dataset, bestAttr);
            Map<String, Node> children = new HashMap<>();
            
            List<String> remainingAttrs = new ArrayList<>(attributes);
            remainingAttrs.remove(bestAttr);

            for (var partition : partitions.entrySet()) {
                children.put(partition.getKey(), grow(partition.getValue(), remainingAttrs, currentLevel + 1));
            }

            return new Split(bestAttr, children, new Leaf(majority));
        }

        private String findOptimalSplit(List<Instance> dataset, List<String> attributes) {
            String best = null;
            double maxGain = minInfoGain;
            double baseEntropy = computeEntropy(dataset);

            for (String attr : attributes) {
                double gain = baseEntropy - computeConditionalEntropy(dataset, attr);
                if (gain > maxGain) {
                    maxGain = gain;
                    best = attr;
                }
            }
            return best;
        }

        private double computeConditionalEntropy(List<Instance> dataset, String attr) {
            Map<String, List<Instance>> groups = groupByAttribute(dataset, attr);
            double weightedEntropy = 0.0;
            for (List<Instance> group : groups.values()) {
                double weight = (double) group.size() / dataset.size();
                weightedEntropy += weight * computeEntropy(group);
            }
            return weightedEntropy;
        }

        private double computeEntropy(List<Instance> dataset) {
            if (dataset.isEmpty()) return 0.0;
            Map<String, Long> counts = dataset.stream()
                .collect(Collectors.groupingBy(inst -> inst.target, Collectors.counting()));
            
            double entropy = 0.0;
            double total = dataset.size();
            for (long count : counts.values()) {
                double p = count / total;
                if (p > 0) entropy -= p * (Math.log(p) / Math.log(2));
            }
            return entropy;
        }

        private Map<String, List<Instance>> groupByAttribute(List<Instance> dataset, String attr) {
            return dataset.stream().collect(Collectors.groupingBy(inst -> inst.features.get(attr)));
        }

        private boolean isHomogeneous(List<Instance> dataset) {
            return dataset.stream().map(inst -> inst.target).distinct().count() <= 1;
        }

        private String getMajorityClass(List<Instance> dataset) {
            return dataset.stream()
                .collect(Collectors.groupingBy(inst -> inst.target, Collectors.counting()))
                .entrySet().stream()
                .max(Map.Entry.comparingByValue())
                .map(Map.Entry::getKey)
                .orElse("Unknown");
        }
    }

    public static void main(String[] args) {
        List<Instance> data = Arrays.asList(
            new Instance(Map.of("Income", "High", "Credit", "Good", "Debt", "Low"), "Approved"),
            new Instance(Map.of("Income", "High", "Credit", "Fair", "Debt", "High"), "Denied"),
            new Instance(Map.of("Income", "Medium", "Credit", "Good", "Debt", "Low"), "Approved"),
            new Instance(Map.of("Income", "Medium", "Credit", "Poor", "Debt", "High"), "Denied"),
            new Instance(Map.of("Income", "Low", "Credit", "Good", "Debt", "Low"), "Approved"),
            new Instance(Map.of("Income", "Low", "Credit", "Poor", "Debt", "High"), "Denied"),
            new Instance(Map.of("Income", "Medium", "Credit", "Fair", "Debt", "Low"), "Approved"),
            new Instance(Map.of("Income", "High", "Credit", "Poor", "Debt", "High"), "Denied"),
            new Instance(Map.of("Income", "Low", "Credit", "Fair", "Debt", "Low"), "Denied"),
            new Instance(Map.of("Income", "Medium", "Credit", "Good", "Debt", "High"), "Approved")
        );

        List<String> features = Arrays.asList("Income", "Credit", "Debt");
        Inducer inducer = new Inducer(5, 0.05);
        Node tree = inducer.grow(data, features, 0);

        System.out.println("Estrutura da Árvore Induzida:");
        tree.display("");

        Instance test = new Instance(Map.of("Income", "Medium", "Credit", "Fair", "Debt", "High"), "Unknown");
        System.out.println("\nPrevisão para novo cliente: " + tree.predict(test));
    }
}

Análise da Implementação

• Abstração de Dados: A classe Instance encapsula um mapa de atributos dinâmicos e um rótulo alvo, eliminando a necessidade de enumerar rigidamente as features.
• Polimorfismo de Nós: A interface Node é implementada por Leaf (nós terminais) e Split (nós de decisão), permitindo uma navegação recursiva limpa durante a predição e a impressão da topologia.
• Indução Recursiva: O método grow avalia as condições de parada (homogeneidade, profundidade máxima) antes de invocar findOptimalSplit, que calcula o ganho de informação para cada atributo disponível.
• Cálculo de Entropia: A função computeEntropy utiliza a API de Streams do Java para agrupar as contagens de classes e aplicar a fórmula logarítmica de Shannon.

Saída Esperada

Estrutura da Árvore Induzida:
[Credit]
  ├── Good:
  │   => Approved
  ├── Fair:
  │   [Income]
  │   ├── High:
  │   │   => Denied
  │   ├── Medium:
  │   │   [Debt]
  │   │   ├── Low:
  │   │   │   => Approved
  │   │   └── High:
  │   │       => Denied
  │   └── Low:
  │       => Denied
  └── Poor:
      => Denied

Previsão para novo cliente: Denied