Como todos os modelos de machine learning supervisionado, as árvores de decisão são treinadas para explicar melhor um conjunto de exemplos de treinamento. O treinamento ideal de uma árvore de decisão é um problema difícil de NP. Portanto, o treinamento geralmente é feito usando heurística, um algoritmo de aprendizado fácil de criar que fornece uma árvore de decisão não ideal, mas próxima da ideal.
A maioria dos algoritmos usados para treinar árvores de decisão funciona com uma estratégia de dividir e conquistar. O algoritmo começa criando um único nó (a raiz) e aumenta a árvore de decisão de maneira recursiva e ambiciosa.
Em cada nó, todas as condições possíveis são avaliadas e pontuadas. O algoritmo seleciona a condição "melhor", ou seja, a condição com a maior pontuação. Por enquanto, saiba que a pontuação é uma métrica correlacionada à tarefa e as condições são selecionadas para maximizar essa métrica.
Por exemplo, no conjunto de dados Palmer Penguins (usado para exemplos de código posteriormente neste curso), a maioria dos pinguins Adelie e Chinstrap tem um comprimento de bico superior a 16 mm, enquanto a maioria dos pinguins Gentoo tem bicos menores. Portanto, a condição bill_length_mm ≥ 16 faz previsões quase perfeitas para os pinguins Gentoo, mas não consegue diferenciar entre Adelies e Chinstraps. O algoritmo provavelmente vai escolher essa condição.
Figura 7. O primeiro passo no cultivo de uma árvore.
Em seguida, o algoritmo é repetido de maneira recursiva e independente nos dois nós filhos. Quando nenhuma condição satisfatória é encontrada, o nó se torna uma folha. A previsão de folha é determinada como o valor de rótulo mais representativo nos exemplos.
O algoritmo é o seguinte:
def train_decision_tree(training_examples):
root = create_root() # Create a decision tree with a single empty root.
grow_tree(root, training_examples) # Grow the root node.
return root
def grow_tree(node, examples):
condition = find_best_condition(examples) # Find the best condition.
if condition is None:
# No satisfying conditions were found, therefore the grow of the branch stops.
set_leaf_prediction(node, examples)
return
# Create two childrens for the node.
positive_child, negative_child = split_node(node, condition)
# List the training examples used by each children.
negative_examples = [example for example in examples if not condition(example)]
positive_examples = [example for example in examples if condition(example)]
# Continue the growth of the children.
grow_tree(negative_child, negative_examples)
grow_tree(positive_child, positive_examples)
Vamos conferir em mais detalhes as etapas de treinamento de uma árvore de decisão específica.
Etapa 1:criar uma raiz:
Etapa 2:amplie o nó 1. A condição “x1 ≥ 1” foi encontrada. Dois nós filhos são criados:
Etapa 3: amplie o nó no 2. Nenhuma condição satisfatória foi encontrada. Então, transforme o nó em uma folha:
Etapa 4: amplie o nó 3. A condição “x2 ≥ 0,5” foi encontrada. Dois nós filhos serão criados.
Existem outros métodos para expandir as árvores de decisão. Uma alternativa conhecida é otimizar os nós globalmente em vez de usar uma estratégia de dividir e conquistar.
growing_strategy="BEST_FIRST_GLOBAL".
Consulte
a documentação para mais detalhes.
Dependendo do número e do tipo de atributos de entrada, o número de condições possíveis para um determinado nó pode ser enorme e geralmente infinito. Por exemplo, considerando uma condição limite $\mathrm{feature}_i \geq t$, a combinação de todos os valores possíveis para $t \in \mathbb{R}$ é infinita.
A rotina responsável por encontrar a melhor condição é chamada de divisor. Como é preciso testar muitas condições possíveis, os divisores são o gargalo ao treinar uma árvore de decisão.
A pontuação maximizada pelo divisor depende da tarefa. Exemplo:
- O ganho de informações e o Gini (ambos abordados posteriormente) são comumente usados para classificação.
- O erro quadrático médio é normalmente usado para regressão.
Há muitos algoritmos de divisor, cada um com suporte variável para:
- O tipo de atributos, por exemplo, numérico, categórico, texto
- A tarefa, por exemplo, classificação binária, classificação multiclasse,
- O tipo de condição, por exemplo, condição de limite, condição em uso, condição oblíqua
- Os critérios de regularização. Por exemplo, divisores exatos ou aproximados para condições de limite.
Além disso, há variantes de divisores equivalentes com compensações diferentes em relação ao uso de memória, uso da CPU, distribuição de computação e assim por diante.