Poda de árboles de decisión - Decision tree pruning

Antes y después de la poda

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 al eliminar secciones del árbol que no son críticas y son 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 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 de 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 solo 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 usar la poda para eliminar los nodos que no brindan información adicional.

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 para la poda de árboles que difieren en la medición que se utiliza para optimizar el rendimiento.

Técnicas

Los procesos de poda se pueden dividir en dos tipos (pre y post poda).

Los procedimientos previos a la poda evitan una inducción completa del conjunto de entrenamiento reemplazando 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 de parada ().

La poda posterior (o simplemente la poda) es la forma más común de simplificar árboles. Aquí, los nodos y subárboles se reemplazan con hojas para reducir la complejidad. La poda no solo puede reducir significativamente el tamaño, sino también mejorar la precisión de clasificación de los 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 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 recursivamente hacia arriba, determinan la relevancia de cada nodo individual. Si no se da 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 errores reducidos (REP), la poda de complejidad de costo mínimo (MCCP) o la poda de errores mínimos (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 siguiente, se lleva a cabo una verificación de relevancia que decide si un nodo es relevante para la clasificación de todos 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 error pesimista (PEP), que brinda resultados bastante buenos con elementos invisibles.

Algoritmos de poda

Poda de errores reducida

Una de las formas más simples de poda es la poda con 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, el cambio se mantiene. Aunque es algo ingenuo, la reducción de errores tiene la ventaja de la simplicidad y la velocidad .

Poda de complejidad de costos

La poda por complejidad de costos genera una serie de árboles donde está el árbol inicial y solo la raíz. 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:

  1. Defina la tasa de error del árbol sobre el conjunto de datos como .
  2. El subárbol que minimiza se elige para su eliminación.

La función define el árbol obtenido al podar los subárboles del árbol . Una vez que se ha creado la serie de árboles, el mejor árbol se elige mediante la precisión generalizada medida por un conjunto de entrenamiento o validación cruzada.

Ver también

Referencias

  • Pearl, Judea (1984). Heurística . Addison-Wesley.
  • Mansour, Y. (1997). "Poda de árboles de decisión pesimista basada en el tamaño del árbol" . Proc. XIV Congreso Internacional de Machine Learning . págs. 195–201.
  • Breslow, LA; Ajá, DW (1997). "Simplificación de árboles de decisión: una encuesta". La revisión de la ingeniería del conocimiento . 12 (1): 1–47. doi : 10.1017 / S0269888997000015 .
  • Quinlan, JR (1986). "Inducción de árboles de decisión" . Aprendizaje automático . Editores académicos de Kluwer. 1 : 81-106. doi : 10.1007 / BF00116251 .

Otras lecturas

enlaces externos