Poda de árboles de decisión

La poda es una técnica de compresión de datos en algoritmos de aprendizaje automático y búsqueda que reduce el tamaño de los árboles de decisión eliminando secciones no críticas y redundantes para clasificar 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 sobreajustarse a los datos de entrenamiento y de generalizar mal a nuevas muestras. Un árbol pequeño podría no capturar información estructural importante sobre el espacio de muestras . Sin embargo, es difícil determinar cuándo debe detenerse un algoritmo de árbol, ya que 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 consiste en hacer crecer el árbol hasta que cada nodo contenga un número pequeño de instancias y luego usar la poda para eliminar los nodos que no proporcionan información adicional. ^{[ 1 ]}

La poda debe reducir el tamaño de un árbol de aprendizaje sin disminuir la precisión predictiva, medida mediante un conjunto de validación cruzada . Existen diversas técnicas de poda de árboles que difieren en la métrica utilizada para optimizar el rendimiento.

Técnicas

Los procesos de poda se pueden dividir en dos tipos (prepoda y postpoda).

Los procedimientos de pre-poda evitan la inducción completa del conjunto de entrenamiento al reemplazar un criterio de parada () en el algoritmo de inducción (por ejemplo, profundidad máxima del árbol o ganancia de información (Attr) > ganancia mínima). Los métodos de pre-poda se consideran más eficientes porque no inducen un conjunto completo, sino que mantienen árboles pequeños desde el principio. Los métodos de pre-poda comparten un problema común: el efecto horizonte. Este se refiere a la terminación prematura no deseada de la inducción por el criterio de parada ().

La poda posterior (o simplemente poda) es la forma más común de simplificar árboles. En este proceso, los nodos y subárboles se reemplazan por hojas para reducir la complejidad. La poda no solo puede reducir significativamente el tamaño, sino también mejorar la precisión de la clasificación de objetos desconocidos. Si bien la precisión de la asignación en el conjunto de entrenamiento puede disminuir, 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).

Poda de abajo hacia arriba

Estos procedimientos comienzan en el último nodo del árbol (el punto más bajo). Siguiendo un proceso recursivo ascendente, determinan la relevancia de cada nodo. Si no se especifica 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 pierde ningún subárbol relevante. Entre estos métodos se incluyen la poda de error reducido (REP), la poda de complejidad de costo mínimo (MCCP) y la poda de error mínimo (MEP).

Poda de arriba hacia abajo

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 determina si un nodo es relevante para la clasificación de los n elementos. Al podar el árbol en un nodo interno, puede ocurrir que se elimine un subárbol completo (independientemente de su relevancia). Un ejemplo de esto es la poda de errores pesimistas (PEP), que ofrece muy buenos resultados con elementos no vistos.

Algoritmos de poda

Poda de errores reducida

Una de las formas más sencillas de poda es la poda de error reducido. Comenzando por las hojas, cada nodo se reemplaza por su clase más frecuente. Si la precisión de la predicción no se ve afectada, se mantiene el cambio. Aunque algo ingenua, la poda de error reducido tiene la ventaja de ser simple y rápida .

Poda de complejidad de costos

La poda de complejidad de costos genera una serie de árboles . $T_{0}\dots T_{m}$ ¿ Dónde ? $T_{0}$ ⁠ es el árbol inicial y ⁠ $T_{m}$ ⁠ es la raíz sola. En el paso ⁠ $i$ ⁠ , el árbol se crea eliminando un subárbol del árbol ⁠ $i-1$ y reemplazándolo con un nodo hoja con un valor elegido según el algoritmo de construcción del árbol. El subárbol que se elimina se elige de la siguiente manera:

Defina la tasa de error del árbol . $T$ sobre el conjunto de datos $S$ como $\operatorname {err} (T,S)$ .
El subárbol $t$ que minimiza ${\frac {\operatorname {err} (\operatorname {prune} (T,t),S)-\operatorname {err} (T,S)}{\left\vert \operatorname {leaves} (T)\right\vert -\left\vert \operatorname {leaves} (\operatorname {prune} (T,t))\right\vert }}$ es elegido para su eliminación.

La función $\operatorname {prune} (T,t)$ Define el árbol obtenido al podar los subárboles . $t$ del árbol $T$ Una vez creada la serie de árboles, se elige el mejor árbol en función de la precisión generalizada, medida mediante un conjunto de entrenamiento o validación cruzada.

Ejemplos

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. ^{[ 2 ]}

Véase también

Referencias

Pearl, Judea (1984). Heurísticas: Estrategias de búsqueda inteligentes para la resolución de problemas informáticos . Addison-Wesley. ISBN 978-0-201-05594-8.
Mansour, Y. (1997). "Poda pesimista de árboles de decisión basada en el tamaño del árbol" . Actas de la 14.ª Conferencia Internacional sobre Aprendizaje Automático . págs. 195–201 .
Breslow, LA; Aha, DW (1997). "Simplificando árboles de decisión: una revisión". The Knowledge Engineering Review . 12 (1): 1– 47. doi : 10.1017/S0269888997000015 . S2CID 18782652 .
Quinlan, JR (1986). "Inducción de árboles de decisión" . Aprendizaje automático . 1. Kluwer: 81–106 . doi : 10.1007/BF00116251 .

↑ Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2001). Los elementos del aprendizaje estadístico . Springer. págs. 269–272 . ISBN 0-387-95284-5.
↑ "Explorando la poda de redes neuronales con métodos de cribado" . arxiv.org . Consultado el 18 de mayo de 2026 .

Lecturas adicionales

Poda de árboles de decisión basada en MDL Archivado el 29/08/2017 en Wayback Machine
Poda de árboles de decisión mediante redes neuronales de retropropagación