El Overfitting es una dificultad práctica para los modelos de árboles de decisiones, y para cualquier otro modelo predictivo. Suele suceder cuando el algoritmo de aprendizaje continua desarrollando hipótesis que reducen el error del set de datos de entrenamiento, pero al costo de una mayor tasa de errores en el set de pruebas. Hay múltiples enfoques que se pueden utilizar para evitar el overfitting al construir árboles de decisión.
- Podado Previo que reducen el crecimiento del árbol prematuramente, antes de que clasifique completamente el set de entrenamiento.
- Podado Posterior que permite que el árbol termine de clasificar por completo el set de entrenamiento, para luego al finalizar podar el árbol.
En la práctica, el segundo enfoque de podar el árbol una vez terminado el proceso de clasificación tiene más éxito porque no es nada fácil estimar cuando éste debería dejar de crecer.
El paso más importante de la poda es la definición del criterio que se utilizará para determinar el tamaño final correcto del árbol. Para esto se utiliza uno de los siguientes métodos:
- Utilizar un conjunto de datos diferentes del de entrenamiento (llamado conjunto de validación) para evaluar los efectos de los nodos que quedaron luego de la poda.
- Construir el árbol utilizando el conjunto de entrenamiento y luego aplicar una prueba estadística para estimar si podar o expandir un nodo en particular tiene probabilidades de generar una mejora por encima del set de entrenamiento.
- Estimación de errores
- Prueba de significancia (ej. prueba Chi2)
- Principio del tamaño mínimo: Utilizar una medida explicita de la complejidad para codificar el conjunto de pruebas y el árbol de decisiones, deteniendo asi el crecimiento del árbol cuando su tamaño codificado (size(tree) + size(misclassifications(tree)) se vea disminuído.
El primer método es el enfoque más común. En este, los datos disponibles se separan en dos conjuntos de ejemplos: el de entrenamiento, que se utiliza para construir el árbol de decisiones, y el de validación, que se utiliza para evaluar el impacto de podar el árbol. El segundo método es también un enfoque común. Veamos qué es la estimación de errores y la prueba Chi2.
Podado posterior utilizando Estimación de Errores
La estimacion de errores para un subconjunto del arbol es el peso de la suma de los errores estimado para todas sus hojas. El error estimado (e) para un nodo se calcula:
En el siguiente ejemplo configuramos a Z a 0.69 con un nivel de certeza de un 75%.
La tasa de errores del nodo padre es de 0.46 y ya que la tasa de errores de sus hijos (0.51) aumenta luego de la división, no queremos quedarnos con los hijos.
Podado Posterior utilizando el test Chi2
En el test Chi2 construimos la tabla de frecuencias correspondiente y calculamos el valor Chi2 y su probabilidad.
| Bronze | Silver | Gold | |
| Bad | 4 | 1 | 4 |
| Good | 2 | 1 | 2 |
Chi2 = 0.21 Probabilidad = 0.90 grados de libertad=2
Si requerimos que la probabilidad tiene que ser menos que un límite definido (ej. 0.05), por lo tanto, decidimos no dividir el nodo.