Como todos los modelos de aprendizaje automático supervisado, los árboles de decisión se entrenan para explicar un conjunto de ejemplos de entrenamiento. El entrenamiento óptimo de un árbol de decisiones un problema NP duro. Por lo tanto, el entrenamiento generalmente se realiza con heurística, un fácil de crear que ofrece un resultado no óptimo, pero árbol de decisión óptimo.
La mayoría de los algoritmos que se usan para entrenar árboles de decisión trabajan con una división codiciosa y conquistará la estrategia. El algoritmo comienza con la creación de un solo nodo (la raíz) y hace crecer el árbol de decisiones de manera recurrente y codiciosa.
En cada nodo, se evalúan y califican todas las condiciones posibles. El el algoritmo selecciona las opciones estado, es decir, la condición con la mayor de calidad. Por ahora, solo debes saber que la puntuación es una métrica que se correlaciona con tarea, y se seleccionan las condiciones para maximizar esa métrica.
Por ejemplo, en la Palmer Pingüinos más adelante en este curso; la mayoría de Adelia y Barbijo los pingüinos tienen una longitud superior a 16 mm, mientras que la mayoría de los pingüinos Papúa (Gentoo) los pingüinos tienen picos más pequeños. Por lo tanto, la condición bill_length_mm ≥ 16 hace predicciones casi perfectas para el Pingüinos Papúa, pero no puede diferenciarse entre Adelies y Barbijo. Es probable que el algoritmo elija esta condición.
Figura 7: El primer paso para cultivar un árbol.
Luego, el algoritmo se repite de forma independiente y recurrente en ambos nodos secundarios. Cuando no se encuentran condiciones satisfactorias, el nodo se convierte en una hoja. La hoja la predicción se determina como el valor de etiqueta más representativo en los ejemplos.
El algoritmo es el siguiente:
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)
Veamos los pasos para entrenar un árbol de decisión en más detalle.
Paso 1: Crea una raíz:
Paso 2: Amplíe el nodo n.o 1. La condición "x1 ≥ 1" en caso de que se haya encontrado. Se crean dos nodos secundarios:
Paso 3: Amplíe el nodo 2. No se encontraron condiciones que satisfagan las condiciones. Entonces, haz que el nodo en una hoja:
Paso 4: Amplíe el nodo 3. La condición "x2 ≥ 0.5" en caso de que se haya encontrado. Dos niños se crean los nodos.
Existen otros métodos para hacer crecer los árboles de decisión. Una alternativa popular es optimizar los nodos globalmente, en vez de usar una estrategia de dividir y vencer.
growing_strategy="BEST_FIRST_GLOBAL".
Consulta
la documentación para obtener más detalles.
Según la cantidad y el tipo de atributos de entrada, la cantidad de atributos las condiciones posibles para un nodo determinado pueden ser enormes, generalmente infinitas. Por ejemplo, dada una condición de umbral $\mathrm{feature}_i \geq t$, la combinación de todos los posible Valores límite para $t \in \mathbb{R}$ es infinito.
La rutina responsable de encontrar la mejor condición se denomina divisor. Como necesita probar muchas condiciones posibles, los divisores son el cuello de botella a la hora de entrenar un árbol de decisión.
La puntuación maximizada por el divisor depende de la tarea. Por ejemplo:
- Aumento de información y Gini (tanto que veremos más adelante) se usan comúnmente para la clasificación.
- El error cuadrático medio se usa comúnmente para la regresión.
Existen muchos algoritmos de divisor, cada uno con compatibilidad variable para lo siguiente:
- el tipo de atributos; por ejemplo, numéricos, categóricos, de texto
- La tarea; por ejemplo, clasificación binaria, análisis clasificación, regresión
- el tipo de condición; como condición de umbral, condición de incorporación, condición oblicua
- los criterios de regularización; por ejemplo, divisores exactos o aproximados para las condiciones de umbral
Además, hay variantes de divisor equivalentes con diferentes compensaciones en cuanto al uso de memoria y de CPU, la distribución de procesamiento, etcétera.