La poda es una técnica de compresión de datos en algoritmos de búsqueda y aprendizaje automático que reduce el tamaño de los árboles de decisión eliminando secciones del árbol que no son críticas y redundantes para clasificar instancias. La poda reduce la complejidad del clasificador final y, por tanto, mejora la precisión predictiva mediante la reducción del sobreajuste .
Una de las cuestiones que surge en un algoritmo de árbol de decisión es el tamaño óptimo del árbol final. Un árbol que es demasiado grande corre el riesgo de sobreajustar los datos de entrenamiento y generalizar mal a nuevas muestras. Es posible que un árbol pequeño no capture 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 único nodo adicional reducirá drásticamente el error. Este problema se conoce como 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 proporcionan información adicional. [1]
La poda debería reducir el tamaño de un árbol de aprendizaje sin reducir la precisión predictiva medida por un conjunto de validación cruzada . Existen muchas técnicas de poda de árboles que se diferencian en la medida que se utiliza para optimizar el rendimiento.
Los procesos de poda se pueden dividir en dos tipos (prepoda y pospoda).
Los procedimientos de poda previa evitan una inducción completa del conjunto de entrenamiento reemplazando un criterio de parada () 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 una interrupción prematura no deseada de la inducción según el criterio stop ().
La pospoda (o simplemente poda) es la forma más común de simplificar los árboles. Aquí, los nodos y subárboles se reemplazan por hojas para reducir la complejidad. La poda no sólo puede reducir significativamente el tamaño sino también mejorar la precisión de la clasificación de objetos invisibles. Puede darse el caso de que la precisión de la asignación en el conjunto de trenes se deteriore, pero la precisión de las propiedades de clasificación del árbol aumente en general.
Los procedimientos se diferencian según 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). Siguiendo recursivamente 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 con este método no se pueden perder subárboles relevantes. Estos métodos incluyen poda de errores reducidos (REP), poda de complejidad de costo mínimo (MCCP) o poda de errores mínimos (MEP).
A diferencia del método ascendente, este método comienza en la raíz del árbol. Siguiendo la estructura siguiente, se lleva a cabo una verificació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 representantes es la poda de errores pesimista (PEP), que produce resultados bastante buenos con elementos invisibles.
Una de las formas más simples de poda es la poda de errores reducidos. 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 mantiene el cambio. Si bien es algo ingenuo, la reducción de errores tiene la ventaja de ser simple y rápida .
La poda de complejidad de costos genera una serie de árboles donde es el árbol inicial y es la raíz sola. En el paso , el árbol se crea eliminando un subárbol del árbol y reemplazándolo con un nodo hoja con el 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 que se ha creado la serie de árboles, se elige el mejor árbol mediante una precisión generalizada medida por un conjunto de entrenamiento o validación cruzada.
La poda podría aplicarse 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.
