Árvores de decisão são um dos algoritmos de aprendizado de máquina mais intuitivas e amplamente utilizados para classificação e regressão. Eles funcionam dividindo dados em ramos com base em valores de recursos, imitando a forma como os seres humanos tomam decisões. Enquanto bibliotecas como o skiit-learn tornam trivial a construção de árvores de decisão, implementar um do zero é uma excelente maneira para iniciantes entenderem o funcionamento interno do algoritmo. Este tutorial irá guiá-lo através da teoria e código, para que você possa construir sua própria árvore de decisão do zero para cima.

O que é uma árvore de decisão?

Uma árvore de decisão é uma estrutura semelhante a um fluxograma onde cada nó interno representa um teste em uma característica (por exemplo, “A idade é > 30 anos?”), cada ramo representa o resultado desse teste, e cada nó de folha possui uma etiqueta de classe ou valor contínuo. O objetivo é criar um modelo que predize uma variável-alvo aprendendo regras de decisão simples inferidas a partir dos recursos de dados. Árvores de decisão são populares porque são fáceis de interpretar e requerem pouco pré-processamento de dados (sem escala ou normalização).

A árvore é construída recursivamente: a partir da raiz, o algoritmo seleciona a melhor funcionalidade e ponto de divisão que separa os dados de forma mais limpa. Este processo é repetido em cada subconjunto até que uma condição de parada seja cumprida. Para mais fundo, a entrada da Wikipédia sobre a aprendizagem de árvore de decisão fornece uma visão geral sólida.

Conceitos Principais que Você Deve Compreender

Nós, ramos e folhas

O nó raiz contém todo o conjunto de dados de treinamento. Os nós internos testam uma característica e dividem os dados em dois ou mais nós filhos. Os ramos são as conexões que representam o resultado de um teste. Os nós de folhas (nós terminais) saem da previsão final – a classe mais comum em classificação ou o valor médio em regressão.

Critérios de separação

Para construir uma árvore, você precisa de uma forma de medir a qualidade de uma divisão potencial. Os critérios mais comuns são:

  • impureza Gini – usada na classificação para medir quantas vezes um elemento escolhido aleatoriamente seria rotulado incorretamente se fosse rotulado aleatoriamente de acordo com a distribuição das classes no subconjunto.
  • Entropia – mede a quantidade de desordem ou incerteza em um conjunto. O objetivo é minimizar a entropia após a divisão (ganho de informação).
  • Redução de variância – usado para árvores de regressão. Calcula a redução da variância (ou erro médio ao quadrado) alcançada pela divisão.

O algoritmo avalia cada possível divisão em cada recurso e escolhe aquele que produz a maior redução na impureza (ou ganho em informação).

Ganho e Razão de Ganho de Informação

O ganho de informação é a diferença entre a impureza do nó pai e a soma ponderada das impurezas das crianças. Embora simples, tende a favorecer as funcionalidades com muitos valores. A razão de ganho (usada em C4. 5) normaliza isto. Para este tutorial, vamos manter o ganho de informação padrão usando a impureza Gini, que é o padrão no CART (Classificação e Árvores de Regressão).

Construindo uma árvore de decisão passo a passo

1. Prepare seus dados

Você precisa de um conjunto de dados com funcionalidades e etiquetas de destino. Para simplificar, use um conjunto de dados de classificação binária com funcionalidades numéricas. Por exemplo:

  • Características:] Idade, Renda
  • Alvo: Aprovado (1) ou Não Aprovado (0)

Limpe os dados: manuseie valores em falta, remova duplicatas e garanta tipos numéricos. Árvores de decisão podem lidar com tipos de dados mistos, mas vamos nos manter numéricos para a implementação.

2. Defina uma função de critério de divisão

Iremos implementar a impureza Gini. O índice Gini para um conjunto de itens é:

onde p i é a proporção de itens na classe i. Para uma divisão binária, o Gini global é a média ponderada dos nós filhos.

3. Implementar a Avaliação em Dividido

Para cada recurso, ordene os valores únicos. Teste todos os limiares possíveis (ponto médio entre os valores ordenados consecutivos). Para cada limiar candidato, divida os dados em grupos esquerdo e direito, compute o Gini e rastreie a melhor divisão.

4. Construa a árvore recursivamente

Criar uma função que tome um subconjunto de dados e uma profundidade atual. Ele verifica as condições de parada (por exemplo, profundidade máxima alcançada, amostras mínimas por nó ou nenhum ganho de informação). Se uma condição for cumprida, crie um nó de folha com a classe da maioria. Caso contrário, encontre a melhor divisão e crie um nó interno, então chame recursivamente a função da esquerda e da direita.

5. Faça Predições

Uma vez que a árvore é construída, a previsão é simples: comece na raiz, siga os ramos avaliando os testes de características na nova amostra, e devolva o valor da folha onde você aterrissou.

Implementação completa em Python

Abaixo está uma implementação completa e mínima de uma árvore de decisão para classificação usando a impureza Gini. Este código é destinado à aprendizagem – não é otimizado para grandes conjuntos de dados.

import numpy as np
from collections import Counter

class DecisionTree:
 def __init__(self, max_depth=None, min_samples_split=2):
 self.max_depth = max_depth
 self.min_samples_split = min_samples_split
 self.tree = None

 def fit(self, X, y):
 dataset = np.column_stack((X, y))
 self.tree = self._grow_tree(dataset)

 def _grow_tree(self, dataset, depth=0):
 X, y = dataset[:, :-1], dataset[:, -1]
 n_samples, n_features = X.shape
 n_labels = len(np.unique(y))

 # Stopping conditions
 if (n_labels == 1 or depth == self.max_depth or n_samples < self.min_samples_split):
 leaf_value = Counter(y).most_common(1)[0][0]
 return {'leaf': True, 'value': leaf_value}

 best_feature, best_threshold = self._best_split(dataset, n_features)
 if best_feature is None:
 leaf_value = Counter(y).most_common(1)[0][0]
 return {'leaf': True, 'value': leaf_value}

 left_idx, right_idx = self._split(dataset[:, best_feature], best_threshold)
 left_subtree = self._grow_tree(dataset[left_idx], depth+1)
 right_subtree = self._grow_tree(dataset[right_idx], depth+1)
 return {'leaf': False,
 'feature': best_feature,
 'threshold': best_threshold,
 'left': left_subtree,
 'right': right_subtree}

 def _best_split(self, dataset, n_features):
 best_gini = float('inf')
 best_feature, best_threshold = None, None
 for feature in range(n_features):
 thresholds = np.unique(dataset[:, feature])
 for i in range(len(thresholds)-1):
 thresh = (thresholds[i] + thresholds[i+1]) / 2
 left_idx, right_idx = self._split(dataset[:, feature], thresh)
 if len(left_idx) == 0 or len(right_idx) == 0:
 continue
 gini = self._gini_gain(dataset, left_idx, right_idx)
 if gini < best_gini:
 best_gini = gini
 best_feature = feature
 best_threshold = thresh
 return best_feature, best_threshold

 def _split(self, values, threshold):
 left_idx = np.where(values <= threshold)[0]
 right_idx = np.where(values > threshold)[0]
 return left_idx, right_idx

 def _gini_gain(self, dataset, left_idx, right_idx):
 total = len(left_idx) + len(right_idx)
 gini_left = self._gini(dataset[left_idx, -1])
 gini_right = self._gini(dataset[right_idx, -1])
 return (len(left_idx)/total) * gini_left + (len(right_idx)/total) * gini_right

 def _gini(self, labels):
 _, counts = np.unique(labels, return_counts=True)
 p = counts / np.sum(counts)
 return 1 - np.sum(p**2)

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

 def _predict_row(self, x, node):
 if node['leaf']:
 return node['value']
 if x[node['feature']] <= node['threshold']:
 return self._predict_row(x, node['left'])
 else:
 return self._predict_row(x, node['right'])

Testando a Árvore

Use um conjunto de dados simples como o conjunto de dados íris clássico (duas características para classificação binária). O conjunto de dados scikit-learn Iris funciona bem. Compare a precisão da sua árvore com a para verificar a exatidão da sua árvore.

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

data = load_iris()
X = data.data[:100] # take only first two classes (binary)
y = data.target[:100]

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

tree = DecisionTree(max_depth=3)
tree.fit(X_train, y_train)
preds = tree.predict(X_test)
accuracy = np.mean(preds == y_test)
print(f'Accuracy: {accuracy:.2f}')

Técnicas avançadas para melhorar sua árvore

Poda para evitar o excesso de ajuste

Uma árvore totalmente cultivada pode memorizar o ruído nos dados de treino. A poda remove ramos que têm pouco poder preditivo. Os métodos comuns são pré-pruning (parando o crescimento precoce através de ] ou ]) e pós-pruning (crescendo a árvore inteira, em seguida, removendo ramos usando um conjunto de validação ou poda de custo-complexidade). Nossa implementação já suporta pré-pruning.

Manuseamento de recursos contínuos e categóricos

Para as características contínuas, utilizamos pontos médios entre valores ordenados como limiares. Para as características categóricas (por exemplo, “Color = vermelho/verde/azul”), cada categoria pode tornar-se um ramo separado (dividido multi-way) ou pode encodificar-los binários. A maioria das implementações modernas (como o scikit-learn) usam divisões binárias mesmo para características categóricas, avaliando todos os subconjuntos.

Lidando com Valores em Falta

Os dados do mundo real têm frequentemente valores em falta. Uma abordagem simples é atribuir valores em falta ao ramo mais frequente entre amostras de treino que têm o recurso. C4.5 usa um método probabilístico. Como este é um tutorial iniciante, assumimos que os dados estão completos.

Comparando com Bibliotecas e Leituras Adicionais

Enquanto construir do zero é educacional, os sistemas de produção usam bibliotecas como o scikit-learn que fornecem implementações C otimizadas. Você pode aprender mais com o oficial ]scikit-learn decision trees documentação. Para uma teoria mais profunda, o livro “The Elements of Statistical Learning” de Hastie, Tibshirani e Friedman é um recurso de autoridade. Outra excelente referência é o livro original CART de Breiman et al.

Conclusão

Construir uma árvore de decisão a partir do zero desmistifica um dos algoritmos mais fundamentais no aprendizado de máquina. Você aprendeu como um simples procedimento de divisão recursiva pode produzir um modelo poderoso. Ao escrever o código você mesmo, você obtém uma compreensão mais profunda das medidas de impureza, seleção de partes e os trade-offs entre viés e variância. Como um próximo passo, tente adicionar suporte de regressão, poda ou manipulação de características categóricas. As habilidades que você desenvolve aqui irão servir-lhe bem, assim como você passa para métodos mais complexos de conjuntos, como florestas aleatórias e aumento de gradientes.