Como todos os modelos de aprendizado de máquina 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 NP-difícil. Portanto, o treinamento geralmente é feito usando heurísticas, 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 divisão e conquista gananciosa. O algoritmo começa criando um único nó (a raiz) e cresce a árvore de decisão de forma recursiva e gananciosa.
Em cada nó, todas as condições possíveis são avaliadas e pontuadas. O algoritmo seleciona a "melhor" condição, ou seja, a condição com a maior pontuação. Por enquanto, saiba que a pontuação é uma métrica que se correlaciona com a tarefa, e as condições são selecionadas para maximizar essa métrica.
Por exemplo, no conjunto de dados Pingüim-de-palmeira, usado para exemplos de código mais adiante neste curso, a maioria dos pinguins-de-adélia e de-barriga-amarelada tem um comprimento de bico maior que 16 mm, enquanto a maioria dos pinguins-de-Gentoo tem bicos menores. Portanto, a condição bill_length_mm ≥ 16 faz previsões quase perfeitas para os pinguins-de-magalhães, mas não consegue diferenciar entre os pinguins-de-adélia e os de barba-de-chifres. O algoritmo provavelmente vai escolher essa condição.
Figura 7. A primeira etapa para o crescimento de uma árvore.
O algoritmo é repetido de forma 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 as etapas de treinamento de uma árvore de decisão específica com mais detalhes.
Etapa 1:crie uma raiz:
Etapa 2:desenvolva o nó 1. A condição "x1 ≥ 1" foi encontrada. Dois nós filhos são criados:
Etapa 3:adicione o nó 2. Nenhuma condição satisfatória foi encontrada. Portanto, transforme o nó em uma folha:
Etapa 4:desenvolver o nó 3. A condição "x2 ≥ 0,5" foi encontrada. Dois nós filhos são criados.
Existem outros métodos para desenvolver árvores de decisão. Uma alternativa comum é otimizar nós globalmente em vez de usar uma estratégia de divisão e conquista.
growing_strategy="BEST_FIRST_GLOBAL".
Consulte
a documentação para mais detalhes.
Dependendo do número e do tipo de elementos de entrada, o número de condições possíveis para um determinado nó pode ser enorme, geralmente infinito. Por exemplo, dada uma condição de limite $\mathrm{feature}_i \geq t$, a combinação de todos os valores de limite possíveis para $t \in \mathbb{R}$ é infinita.
A rotina responsável por encontrar a melhor condição é chamada de divisor. Como é necessário 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. Por exemplo:
- O ganho de informação e o Gini (ambos abordados mais adiante) são usados com frequência para classificação.
- O erro quadrático médio é comumente usado para regressão.
Há muitos algoritmos de divisão, cada um com suporte variado para:
- O tipo de recursos, por exemplo, numérico, categórico, texto
- A tarefa, por exemplo, classificação binária, classificação multiclasse ou regressão
- O tipo de condição, por exemplo, condição de limite, condição no conjunto, 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 equivalentes de divisores com diferentes compensações em relação ao uso de memória, uso de CPU, distribuição de computação e assim por diante.