La poda es una técnica de compresión de datos en el aprendizaje automático y los algoritmos de búsqueda que reduce el tamaño de los árboles de decisión al eliminar las secciones del árbol que no son críticas y son redundantes para clasificar las instancias. La poda reduce la complejidad del clasificador final y, por lo tanto, mejora la precisión predictiva al reducir el sobreajuste .
Una de las preguntas que surgen en un algoritmo de árbol de decisión es el tamaño óptimo del árbol final. Un árbol demasiado grande corre el riesgo de sobreajustar los datos de entrenamiento y generalizar de forma deficiente a nuevas muestras. Un árbol pequeño podría no capturar información estructural importante sobre el espacio muestral. Sin embargo, es difícil saber cuándo debe detenerse un algoritmo de árbol porque es imposible saber si la adición de un solo nodo adicional reducirá drásticamente el error. Este problema se conoce como el efecto horizonte . Una estrategia común es hacer crecer el árbol hasta que cada nodo contenga una pequeña cantidad de instancias y luego utilizar la poda para eliminar los nodos que no brinden información adicional. [1]
La poda debe reducir el tamaño de un árbol de aprendizaje sin reducir la precisión predictiva, medida mediante un conjunto de validación cruzada . Existen muchas técnicas de poda de árboles que difieren en la medición que se utiliza para optimizar el rendimiento.
Los procesos de poda se pueden dividir en dos tipos (pre y post poda).
Los procedimientos de prepoda evitan una inducción completa del conjunto de entrenamiento al reemplazar un criterio stop() en el algoritmo de inducción (por ejemplo, profundidad máxima del árbol o ganancia de información (Attr)> minGain). Los métodos de prepoda se consideran más eficientes porque no inducen un conjunto completo, sino que los árboles permanecen pequeños desde el principio. Los métodos de prepoda comparten un problema común, el efecto horizonte. Esto debe entenderse como la terminación prematura no deseada de la inducción por el criterio stop().
La poda posterior (o simplemente poda) es la forma más común de simplificar los árboles. En este caso, los nodos y subárboles se reemplazan con hojas para reducir la complejidad. La poda no solo puede reducir significativamente el tamaño, sino que también mejora la precisión de la clasificación de objetos no vistos. Puede darse el caso de que la precisión de la asignación en el conjunto de entrenamiento se deteriore, pero la precisión de las propiedades de clasificación del árbol aumenta en general.
Los procedimientos se diferencian en función de su enfoque en el árbol (de arriba hacia abajo o de abajo hacia arriba).
Estos procedimientos comienzan en el último nodo del árbol (el punto más bajo). A continuación, de forma recursiva hacia arriba, determinan la relevancia de cada nodo individual. Si no se proporciona la relevancia para la clasificación, el nodo se elimina o se reemplaza por una hoja. La ventaja es que no se pueden perder subárboles relevantes con este método. Estos métodos incluyen la poda de error reducido (REP), la poda de complejidad de costo mínimo (MCCP) o la poda de error mínimo (MEP).
A diferencia del método ascendente, este método comienza en la raíz del árbol. Siguiendo la estructura que se muestra a continuación, se realiza una comprobación de relevancia que decide si un nodo es relevante para la clasificación de los n elementos o no. Al podar el árbol en un nodo interno, puede suceder que se elimine un subárbol completo (independientemente de su relevancia). Uno de estos ejemplos es la poda de errores pesimistas (PEP), que ofrece resultados bastante buenos con elementos no vistos.
Una de las formas más simples de poda es la poda de error reducido. Comenzando por las hojas, cada nodo se reemplaza con su clase más popular. Si la precisión de la predicción no se ve afectada, se conserva el cambio. Si bien es algo ingenua, la poda de error reducido tiene la ventaja de la simplicidad y la velocidad .
La poda de complejidad de costos genera una serie de árboles donde es el árbol inicial y es solo la raíz. En el paso , el árbol se crea eliminando un subárbol del árbol y reemplazándolo con un nodo de hoja con valor elegido como en el algoritmo de construcción del árbol. El subárbol que se elimina se elige de la siguiente manera:
La función define el árbol obtenido al podar los subárboles del árbol . Una vez creada la serie de árboles, se elige el mejor árbol por precisión generalizada medida por un conjunto de entrenamiento o validación cruzada.
La poda se puede aplicar en un esquema de compresión de un algoritmo de aprendizaje para eliminar los detalles redundantes sin comprometer el rendimiento del modelo. En las redes neuronales, la poda elimina neuronas enteras o capas de neuronas.
