As árvores de decisão são estruturas algorítmicas fundamentais na aprendizagem de máquina, empregadas tanto para classificação quanto para regressão. Elas operam por meio de uma hierarquia de nós, onde cada nó interno representa um teste sobre um atributo, as arestas denotam os possíveis resultados desses testes e os nós folha indicam as decisões finais. O processo de construção envolve a seleção de atributos, a divisão iterativa dos dados, a formação recursiva de subárvores e a definição de critérios de parada. Embora essas estruturas sejam intuitivas e facilmente interpretáveis, tendem a sofrer de sobreajuste, o que pode ser mitigado por técnicas como a poda.

Fluxo de Construção da Árvore

A tomada de decisão em uma árvore segue um caminho sequencial de testes atributo-a-atributo, onde cada teste refina o subconjunto de dados considerado. O objetivo é gerar um modelo com alta capacidade de generalização, ou seja, que performe bem em dados não vistos. Conceitos como pureza dos nós são cruciais: quanto mais homogêneo for um nó em termos de classes, mais puro ele é. Critérios como o ganho de informação, a taxa de ganho e o índice de Gini são usados para avaliar a qualidade das divisões.

Critérios de Divisão de Atributos

A seleção do melhor atributo para dividir um nó é guiada por métricas que maximizam a pureza descendente. As abordagens clássicas incluem:

• Ganho de Informação (ID3): Baseado na entropia, calcula a redução na incerteza após a divisão. Prefere atributos com muitos valores distintos, o que pode enviesar o modelo.
• Taxa de Ganho (C4.5): Refina o ganho de informação normalizando-o pelo valor intrínseco do atributo, reduzindo o viés para atributos com muitos valores.
• Índice de Gini (CART): Mede a probabilidade de classificação incorreta ao amostrar aleatoriamente dois elementos de um nó. Quanto menor o índice, maior a pureza.

Exemplo Prático de Cálculo de Ganho de Informação

O código a seguir calcula o ganho de informação para um conjunto de dados hipotético, utilizando a biblioteca Pandas e funções matemáticas personalizadas.

import pandas as pd
import numpy as np

# Conjunto de dados de exemplo
dataset = {
    'Clima': ['Ensolarado', 'Ensolarado', 'Nublado', 'Chuvoso', 'Chuvoso', 'Chuvoso', 'Nublado', 'Ensolarado', 'Ensolarado', 'Chuvoso'],
    'Temperatura': ['Quente', 'Quente', 'Quente', 'Morno', 'Frio', 'Frio', 'Frio', 'Morno', 'Frio', 'Morno'],
    'JogarTenis': ['Não', 'Não', 'Sim', 'Sim', 'Sim', 'Não', 'Sim', 'Não', 'Sim', 'Sim']
}

df = pd.DataFrame(dataset)

def entropy_calculation(series):
    probs = series.value_counts(normalize=True)
    return -np.sum(probs * np.log2(probs + 1e-10))

def information_gain_calculation(data, feature, target):
    total_entropy = entropy_calculation(data[target])
    groups = data.groupby(feature)[target]
    weighted_entropy = sum(len(subset)/len(data) * entropy_calculation(subset) for name, subset in groups)
    return total_entropy - weighted_entropy

gain_climate = information_gain_calculation(df, 'Clima', 'JogarTenis')
gain_temperature = information_gain_calculation(df, 'Temperatura', 'JogarTenis')
print(f"Ganho de Informação para Clima: {gain_climate:.4f}")
print(f"Ganho de Informação para Temperatura: {gain_temperature:.4f}")

Para resolver o viés em atributos com muitos valores, a taxa de ganho é utilizada. Veja uma implementação adaptada:

def gain_ratio_calculation(data, feature, target):
    ig = information_gain_calculation(data, feature, target)
    iv = -sum((len(subset)/len(data)) * np.log2(len(subset)/len(data)) for subset in data.groupby(feature)[target])
    return ig / iv if iv != 0 else 0

ratio_climate = gain_ratio_calculation(df, 'Clima', 'JogarTenis')
print(f"Taxa de Ganho para Clima: {ratio_climate:.4f}")

O índice de Gini oferece uma alternativa computacionalmente eficiente, sem operações logarítmicas pesadas:

def gini_index_calculation(series):
    probs = series.value_counts(normalize=True)
    return 1 - np.sum(probs ** 2)

def gini_for_feature(data, feature, target):
    total = len(data)
    gini = 0
    for value, group in data.groupby(feature)[target]:
        weight = len(group) / total
        gini += weight * gini_index_calculation(group)
    return gini

gini_climate = gini_for_feature(df, 'Clima', 'JogarTenis')
print(f"Índice de Gini para Clima: {gini_climate:.4f}")

Técnicas de Poda

As árvores de decisão podem se tornar complexas e memorizar ruídos nos dados de treinamento, levando ao sobreajuste. A poda reduz essa complexidade para melhorar a generalização:

• Pré-poda: Interrompe o crescimento da árvore durante a construção, usando heurísticas como profundidade máxima, número mínimo de amostras por folha ou melhoria mínima de pureza. É rápida mas pode causar subajuste se os limites forem muito restritivos.
• Pós-poda: Gera uma árvore completa e, em seguida, remove subárvores que não contribuem para a performance, avaliando em um conjunto de validação. É mais precisa mas requer mais recursos computacionais.

Aplicação com Scikit-Learn

O exemplo abaixo demonstra a construção de uma árvore de decisão para o conjunto de dados de vinhos, incluindo treino, avaliação e visualização.

from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
import graphviz
from sklearn import tree

# Carregamento e preparação dos dados
wine = load_wine()
features = pd.DataFrame(wine.data, columns=wine.feature_names)
labels = wine.target

train_feat, test_feat, train_lab, test_lab = train_test_split(features, labels, test_size=0.3, random_state=42)

# Inicialização e treinamento do modelo
dt_model = DecisionTreeClassifier(criterion='entropy', max_depth=4, min_samples_split=0.2, random_state=42)
dt_model.fit(train_feat, train_lab)

# Extração de propriedades do modelo
importances = dt_model.feature_importances_
depth = dt_model.get_depth()
leaf_count = dt_model.get_n_leaves()

# Avaliação e visualização
predictions = dt_model.predict(test_feat)
acc = accuracy_score(test_lab, predictions)
print(f"Acurácia no conjunto de teste: {acc:.2f}")

dot_graph = tree.export_graphviz(dt_model, out_file=None, feature_names=wine.feature_names,
                                 class_names=wine.target_names, filled=True, rounded=True)
graph = graphviz.Source(dot_graph)
graph.render("árvore_vinho", format="pdf", cleanup=True)

Este código ilustra como configurar parâmetros de poda, avaliar a importância dos atributos e exportar a árvore para uma representação visual. A acurácia e a estrutura da árvore fornecem insights sobre o desempenho e a complexidade do modelo.