Como todos os modelos de machine learning supervisionado, as árvores de decisão são treinadas explicar 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 com o uso da heurística, algoritmo de aprendizado fácil de criar que oferece um resultado não ideal, ideal, árvore de decisão.
A maioria dos algoritmos usados para treinar árvores de decisão funciona com uma divisão e conquistar. O algoritmo começa criando um único nó (a raiz) e aumenta a árvore de decisão de forma recursiva e gananciosa.
Em cada nó, todas as condições possíveis são avaliadas e pontuadas. A o algoritmo seleciona o "melhor" ou seja, a condição com a maior de qualidade. Por enquanto, saiba apenas que a pontuação é uma métrica correlacionada com o tarefa, e as condições são selecionadas para maximizar essa métrica.
Por exemplo, na Palmer Pinguins conjunto de dados (usado para exemplos de código posteriormente neste curso), a maioria dos dados de Adelie e Chinstrap pinguins têm um bico maior que 16 mm, enquanto a maior parte do os pinguins têm bicos menores. Portanto, a condição bill_length_mm ≥ 16 faz previsões quase perfeitas para o Pinguins Gentoo, mas não conseguem diferenciar entre Adelies e Chinstraps. O algoritmo provavelmente escolherá essa condição.
Figura 7. O primeiro passo para o cultivo de uma árvore. .
O algoritmo se repete de forma recursiva e independente nos dois nós filhos. Quando nenhuma condição satisfatória é encontrada, o nó se torna uma folha. A folha previsão é 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 passar pelas etapas de treinamento de uma árvore de decisão específica mais detalhes.
Etapa 1: criar uma raiz
Etapa 2:aumente o nó 1. A condição "x1 ≥ 1" foi encontrado. Dois nós filhos são criados:
Etapa 3:aumente o nó 2. Nenhuma condição satisfatória foi encontrada. Então, torne o nó em uma folha:
Etapa 4: aumente o nó no 3. A condição "x2 ≥ 0,5" foi encontrado. Duas crianças nós são criados.
Existem outros métodos para desenvolver árvores de decisão. Uma alternativa popular é otimizar nós globalmente em vez de usar uma estratégia de divisão e conquista.
growing_strategy="BEST_FIRST_GLOBAL".
Consulte
consulte a documentação para saber mais.
Dependendo do número e do tipo dos atributos de entrada, a quantidade as condições possíveis para um determinado nó podem ser enormes, geralmente infinitas. Por exemplo, considerando uma condição de limite $\mathrm{feature}_i \geq t$, a combinação de todas as possível valores de limite para $t \in \mathbb{R}$ é infinito.
A rotina responsável por encontrar a melhor condição é chamada de divisor. Como é preciso testar várias 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:
- Ganho de informações e Gini (ambas abordadas 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 variado para:
- O tipo de atributos. como numéricos, categóricos, de texto,
- A tarefa. como classificação binária, classes classificação, regressão,
- O tipo de condição. por exemplo, condição de limite, condição "in-set" condição oblíqua
- Os critérios de regularização por exemplo, divisores exatos ou aproximados das condições de limite
Além disso, há variantes de divisor equivalentes com diferentes vantagens em relação ao uso da memória, da CPU, da distribuição da computação e assim por diante.