Al igual que todos los modelos de aprendizaje automático supervisado, los árboles de decisión se entrenan para explicar mejor un conjunto de ejemplos de entrenamiento. El entrenamiento óptimo de un árbol de decisiones es un problema NP duro. Por lo tanto, el entrenamiento generalmente se realiza mediante una heurística, un algoritmo de aprendizaje fácil de crear que proporciona un árbol de decisión no óptimo, pero cercano a óptimo.
La mayoría de los algoritmos que se usan para entrenar los árboles de decisiones funcionan con una estrategia voraz de dividir y vencer. El algoritmo comienza con la creación de un solo nodo (la raíz) y expande el árbol de decisión de manera recurrente y codiciosa.
En cada nodo, se evalúan y califican todas las condiciones posibles. El algoritmo selecciona la “mejor” condición, es decir, la condición con la puntuación más alta. Por ahora, solo debes saber que la puntuación es una métrica que se correlaciona con la tarea y que se seleccionan condiciones para maximizar esa métrica.
Por ejemplo, en el conjunto de datos Palmer Penguins (que se usa para ejemplos de código más adelante en este curso), la mayoría de los pingüinos Adelia y Barbijo tienen una longitud de pico superior a 16 mm, mientras que la mayoría de los pingüinos Papúa tienen picos más pequeños. Por lo tanto, la condición bill_length_mm ≥ 16 hace predicciones casi perfectas para los pingüinos Gentoo, pero no puede diferenciar entre Adelies y Barbijo (Chinstraps). Es probable que el algoritmo elija esta condición.
Figura 7: El primer paso para hacer crecer un árbol.
Luego, el algoritmo se repite de manera independiente y recurrente en ambos nodos secundarios. Cuando no se encuentran condiciones que satisfagan las políticas, el nodo se convierte en una hoja. La predicción de la hoja 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)
Repasemos con más detalle los pasos para entrenar un árbol de decisión en particular.
Paso 1: Crea una raíz:
Paso 2: Amplía el nodo 1. Se encontró la condición "x1 ≥ 1". Se crean dos nodos secundarios:
Paso 3: Amplía el nodo n° 2. No se encontraron condiciones que satisfagan los requisitos. Por lo tanto, convierte el nodo en una hoja:
Paso 4: Amplía el nodo 3. Se encontró la condición "x2 ≥ 0.5". Se crean dos nodos secundarios.
Existen otros métodos para hacer crecer los árboles de decisiones. Una alternativa popular es optimizar los nodos a nivel global en lugar 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 condiciones posibles para un nodo determinado puede ser enorme; generalmente, infinita. Por ejemplo, dada una condición de umbral $\mathrm{feature}_i \geq t$, la combinación de todos los valores de umbral posibles para $t \in \mathbb{R}$ es infinita.
La rutina responsable de encontrar la mejor condición se denomina divisor. Debido a que necesita probar muchas condiciones posibles, los divisores son el cuello de botella cuando se entrena un árbol de decisión.
La puntuación que maximiza el divisor depende de la tarea. Por ejemplo:
- La obtención de información y Gini (ambos temas más adelante) se usan por lo general para la clasificación.
- El error cuadrático medio se usa comúnmente para la regresión.
Existen muchos algoritmos divisores, 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, clasificación de clases múltiples, regresión
- El tipo de condición; por ejemplo, condición de umbral, condición configurada, condición oblicua
- Los criterios de regularización; por ejemplo, divisores exactos o aproximados para condiciones de umbral
Además, existen variantes de divisor equivalentes con diferentes compensaciones con respecto al uso de memoria, el uso de CPU, la distribución de procesamiento, etcétera.