Métodos de Poda

Como dijimos anteriormente en los árboles de decisión, la poda consiste en eliminar una rama de un nodo transformándolo en una hoja (terminal), asignándole la clasificación más común de los ejemplos de entrenamiento considerados en ese nodo. Se pueden aplicar dos tipos:

 

  • La poda previa: El árbol se poda periódicamente antes de completar el conjunto de entrenamiento, el objetivo es detener el crecimiento antes de que se ajuste al conjunto de entrenamiento y produzca hojas con muestras muy pequeñas. En cada etapa de división se verifica el error de validación cruzada, sí éste no disminuye lo suficiente nos detenemos. El inconveniente con el que nos podemos encontrar es pararnos demasiado pronto y no obtener ningún beneficio, por otro lado, podemos reducir el error de forma más significativa.
  • La poda posterior: El árbol se desarrolla por completo y luego se poda. Esta forma de trabajo necesita más cálculo, pero conduce a un árbol más ajustado. En la práctica se usa más esta técnica debido a que es difícil estimar cuándo se debe detener el crecimiento del árbol.

La poda previa y posterior también pueden usarse juntas. Los árboles con poda posterior son más rigurosos desde el punto de vista matemático, por lo que son, como mínimo, tan buenos como los de poda previa. La poda previa es una solución rápida y nos sugiere esta pregunta ¿por qué construir un árbol solo para podarlo de nuevo?. Ambos tipos estiman el riesgo de clasificación errónea de cada nodo y el subárbol que pende de él. Si la tasa de error para el nodo terminal no es mayor que el error correspondiente para el subárbol, entonces el subárbol se reemplaza por un terminal/hoja. Las diferencias entre los métodos de poda se deben principalmente a la estimación de la tasa de clasificación errónea, ya que la estimación natural sobre la base de los datos de entrenamiento es demasiado optimista y conduce a árboles de gran tamaño.

 

Los distintos métodos se han desarrollado para resolver el dilema de la detención en la creación del árbol, ¿somos estrictos y generamos árboles pequeños y poco ajustados o los ajustamos mucho y los creamos grandes?. El objetivo siempre es reducir la complejidad, simplificar, y hacer más correcto el tráfico en el árbol sin disminuir la precisión de la clasificación. Una de las estrategias que más se suele seguir es hacer crecer el árbol deteniendo el proceso de división solo cuando se alcanza un tamaño prefijado, entonces, el árbol se poda. De todas formas, aún no se puede decir que un método u otro pueda ser el mejor.

 

Métodos, Algoritmos de Poda
Año Acrónimo Autor Comentario
1.984 CCP

Leo Breiman,

Richard A. Olshen,

Charles J. Stone y

Jerome Friedman

Cost–Complexity Pruning. Se introdujo en el marco de la aplicación de CART. También se conoce como poda de enlace más débil o poda por error de complejidad. Se realiza en dos etapas:

1-En la primera tomamos una secuencia de subárboles, {T0, T1, … Tk} de los datos de entrenamiento. Siendo:

  • T0 el árbol original.
  • Tk la raíz del árbol
  • Ti+1 se obtiene por reemplazo de uno o más subárboles de Ti , cortando las ramas que muestren el menor incremento en la tasa de error por hoja/terminal podado.

2-Se elige el mejor árbol según una estimación de las tasas de error reales.

Por ejemplo, tomamos el subárbol T utilizado para clasificar cada uno de los N casos en el conjunto de entrenamiento, E como los ejemplos clasificados erróneamente si el subárbol T se reemplaza por la mejor hoja y NT el número de hojas en el subárbol T. La siguiente ecuación nos daría el costo-complejidad total del subárbol T:

Costo-complejidad = (E / N) + α * NT

α es el costo de una hoja adicional en el árbol y da la reducción del error por hoja.

Si el subárbol se recorta, el nuevo árbol clasificará incorrectamente M casos más, pero tendrá NT -1 hojas menos.

El mismo Costo-complejidad se obtendrá cuando α = (M / (N * (NT – 1)). A partir de esta ecuación se puede calcular α para cada subárbol y los subárboles con el valor más pequeño de α se seleccionan para la poda.

 1.984 MCCP Leo Breiman Minimal Cost-Complexity Pruning. Poda mínima de complejidad de costos Este método también se conoce como el algoritmo de poda de CART. Consiste en dos pasos:
  1. Genera una serie de árboles cada vez más podados {T0, T1, T2, …, Tn}.
  2. Selecciona el mejor árbol con la tasa de error más baja en un conjunto de pruebas separado.

Con respecto al primer paso, Ti + 1 se obtiene de Ti al recortar todos los nodos que tienen el aumento más bajo en la tasa de error por hoja cortada que se denota α

R (t) es la tasa de error si el nodo se recorta, entonces se convierte en una hoja que pertenece a una sola clase.

R (Tt) es la tasa de error si el nodo no se ha eliminado. Representa el promedio de las tasas de error en las hojas ponderadas por el número de ejemplos en cada hoja.

NT es el número de hojas

 

El método opera de la siguiente forma:

  1. Calcula α para cada nodo (no terminal) (excepto la raíz) en Ti.
  2. Pode todos los nodos con el valor más pequeño de α, obteniendo así el árbol Ti + 1.
  3. Repite este proceso hasta que solo quede la raíz para obtener una serie de árboles podados.
  4. El siguiente paso es seleccionar uno de estos como el árbol final. El criterio para la selección del árbol final es la tasa más baja de clasificación errónea en un conjunto de datos independientes. Esta selección se basa únicamente en la precisión del conjunto de pruebas.
1.986 MEP Timothy Niblett e Ivan Bratko

Minimum Error Pruning. Es un enfoque de poda posterior, de abajo hacia arriba, que busca un solo árbol que reduzca la tasa de error esperada. Suponiendo que hay k clases para un conjunto de datos cuyo número es n y nc es la clase c con el mayor número de datos, si se predice que todos los ejemplos futuros estarán en la clase c, se utiliza la siguiente ecuación para predecir la tasa de error esperada:Dónde:

k = nº de clases
nt = nº de ejemplos en el nodo t
nt, c = nº de ejemplos asignados a la clase c en el nodo t

El método consiste en los siguientes pasos:

En cada nodo, no terminal, se calcula la tasa de error esperado si ese subárbol es podado.

Se calcula la tasa de error esperada para ese nodo si el subárbol no se poda

Si la poda del nodo conduce a una mayor tasa de error esperada, entonces se mantiene el subárbol en caso contrario, lo podamos.

 

Goran Cestnik y Bratko mejoraron esta versión y la versión más reciente supera dos problemas del método original: Sesgo optimista y dependencia de la tasa de error esperada en el número de clases.

1.987 REP J. Ross Quinlan Reduced Error Pruning. Es una de las estrategias de poda más simples de poda posterior. En la actualidad se utiliza poco, ya que tiene la desventaja de requerir un conjunto separado de datos divididos para entrenamiento y validación de la poda. Además, se considera una estrategia demasiado agresiva que sobre poda el árbol, eliminando partes relevantes del mismo. Su forma de actuar es desde abajo hacia arriba verificando que cada nodo, no terminal, puede ser reemplazado con la clase más frecuente sin reducir la precisión, en este caso lo poda. El procedimiento continúa hasta que cualquier otra poda disminuya la precisión. Tiene una complejidad O (n4)
1.987 CVP John Mingers Critical Value Prune. La poda de valor crítico es un método de poda posterior que trabaja con una variedad de medidas de selección de nodos. La idea es establecer un umbral, valor crítico, que define el nivel en el que tiene lugar la poda. Tiene dos pasos:
  1. Primero se especifica el umbral. Un nodo interno del árbol se elimina si el valor obtenido por la medida de selección no supera el umbral. Este nodo no se considera importante, porque el valor de la medida de selección obtenida en la etapa de creación del árbol estima su fuerza. La repetición de este procedimiento, utilizando valores críticos crecientes, produce una serie de árboles podados
  2. El mejor árbol se selecciona sobre la base de la capacidad predictiva similar a MCCP.
1.989 MDL Jorma Rissanen, Ross Quinlan y R. L. Rivest Minimum Description Length Pruning. Este método mide el tamaño del árbol por medio del número de bits necesarios para codificarlo. Elige árboles que pueden codificarse con menos bits.
1.986-1.993 PEP J. Ross Quinlan

Pessimistic Error Pruning. Error pesimista de la poda. El método de poda posterior propuesto por Quinlan en el contexto de ID3. Quinlan encontró que es optimista usar un conjunto de entrenamiento para probar la tasa de error, porque los árboles de decisión se han adaptado al conjunto de entrenamiento. En este caso, la tasa de error puede ser 0. Si se utilizan datos distintos del conjunto de entrenamiento, la tasa de error aumentará dramáticamente Para resolver este problema se utilizó la corrección de continuidad (estadística) de la distribución binomial para obtener una tasa de error que es más realista. Usa las siguientes ecuaciones para obtener el número de errores de clasificación:

(1)     n'(t) = e(t) + (1/2) ; n'(t) es el número de errores de clasificación para el nodo t
(2)     n'(Tt) = e(Tt ) + (NT/2) ; n'(Tt)  es el número de errores de clasificación para el subárbol T.

dónde:

NT es el número de hojas para el subárbol T,
e (t) es el número de errores de clasificación en el nodo t,
e (Tt) es el número de errores de clasificación para el subárbol T.
1/2 es una constante que Indica la contribución de una hoja a la complejidad del árbol.

Este método es mucho más rápido que el «Reduced Error Pruning» y también proporciona precisiones más altas, sin utilizar no usa validación cruzada.

1.993 EBP J. Ross Quinlan Error–based Pruning. Es una poda posterior basada en errores, es una evolución de PEP, aparece en C4.5. Al igual que en la poda pesimista, la tasa de error se estima utilizando el límite superior del intervalo de confianza estadística para las proporciones. Utiliza un parámetro denominado, el factor de certeza, que afecta al tamaño del árbol podado, sí el ajuste no es correcto, da como resultado árboles grandes que pueden continuar creciendo aunque no haya un aumento en la precisión, por contra, sí el factor de certeza es adecuado produce árboles de tamaño adecuado con buena precisión en comparación con REP.
1.994-6 OPT Ivan Bratko, Marko Bohanec y Hussein Almuallim

Optimal Pruning. La podada óptima tiene una la complejidad de O (| hojas (T) |2), donde T es el árbol de decisión inicial. Almuallim introdujo una mejora de OPT llamada OPT-2, que también realiza una poda óptima. Sin embargo, las complejidades de tiempo y espacio de OPT-2 son:

O ( | hojas (T ∗) | × | interno (T) | )

Donde (T ∗) es el árbol de decisiones objetivo (podado) y T es el árbol de decisión inicial.

Como el árbol podado es habitualmente mucho más pequeño que el árbol inicial y el número de nodos internos es más pequeño que el número de hojas, OPT-2 suele ser más eficiente que OPT en términos de complejidad computacional.

 2.006 FBP Xiaoming Huo, Seoung Bum Kim, Kwok-Leung Tsui y Shuchun Wang Frontier-Based Tree-Pruning. Este método tiene un orden de complejidad computacional comparable a la poda CCP, pero tiene la ventaja de proporcionar un espectro completo de información. Con CV (Validación Cruzada) genera mejores clasificadores en simulaciones, en comparación con otros métodos.
2.012 PAV Linkai Luo,Hong Peng, Weihang Lv,
Yan Zhang y Xiaodong Zhang
Product of the Accuracy and the Volume. El algoritmo se basa en el riesgo estructural del nodo de hoja. El riesgo estructural se mide por el producto de la precisión y el volumen (PAV) en el nodo de la hoja. Los experimentos comparativos con el algoritmo de poda de complejidad de costos utilizando el algoritmo de validación cruzada (CCP-CV) en algunos conjuntos de datos de referencia muestran que la poda de PAV reduce en gran medida el costo de tiempo de CCP-CV, mientras que la precisión de la prueba de poda  es cercana a la de CCP-CV.
Algoritmos que acomodan la generación de árboles.
1.993 MLPC Multi-Level Pruned Classifier. Es el algoritmo de poda que se implementó posteriormente a la creación del C4.5. En este caso el C4.5 con poda se denomina algoritmo de clasificador de niveles múltiples (MLPC). Trabaja de arriba hacia abajo con poda previa antes de construir el árbol y se detiene en un nivel pre-establecido. Al principio todos los ejemplos de entrenamiento se mantienen en la raíz. Luego los ejemplos se dividen de forma recursiva en función de los atributos previamente seleccionados. El atributo que provoca la división lo hace sobre la medida de entropía y solo considera los atributos que tienen mayor contribución en la clasificación, por lo que el número de reglas generadas son menores, esto disminuye el tiempo de clasificación.
1.994 IREP Johannes Furnkranz y Gerhard Widner Incremental Reduced Error Pruning. Surge como mejora de REP. Integra la pre-poda y la post-poda durante el aprendizaje para el descenso progresivo de la reducción de errores.
1.995 RIPPER William W. Cohen Repeated Incremental Pruning Produce Error Reduction. Es una mejora del algoritmo IREP, ofrece un tiempo de capacitación menor para pequeños conjunto de datos. Aprende las reglas directamente de los datos no de la construcción del árbol.
2.001 Soft-pruning Boonserm Kijsirikul y K. Chongkasemwongse Poda suave. Proponen que la poda sea a través de una red neuronal con retrocesión. Los resultados comparados con C4.5 muestran que funciona mejor tanto en los árboles podados y no podados del C4.5. La desventaja está en la pérdida de la facilidad de interpretación de los árboles originales.
2.002 DIP Bruno Cremilleux y Dominique Fournier Depth-Impurity Pruning. Utiliza un índice que denominan de «Calidad» que realiza una compensación entre las impurezas y la profundidad de las hojas. El método de poda es capaz de mantener subárboles que no disminuyen la tasa de error, pero señalan poblaciones de interés específico.
2.003 IREP++ Oliver Dain, Robert K. Cunningham y Stephen Boyer Incremental Reduced Error Pruning ++. Es un algoritmo de aprendizaje de reglas similar a RIPPER e IREP.  Provee conjuntos de reglas más rápidamente que los anteriores y el concepto objetivo es más fácil de entender por los humanos ( if-then,  Si-Entonces).
2.007 MIP

Cha Zhang y

Paul Viola

Multiple-Instance Pruning. El algoritmo calcula un conjunto de umbrales que terminan el cálculo sin reducción en la tasa de detección o aumento en la tasa de falsos positivos en los datos de entrenamiento. El algoritmo se basa en dos ideas clave:
  • Los ejemplos que están destinados a ser rechazados por el clasificador se pueden recortar de forma segura antes de tiempo.
  •  El proceso es automático y no requiere supuestos de distribuciones de probabilidad, independencia estadística u objetivos de rechazo intermedios.

One thought on “Métodos de Poda

  1. Estupendo. Si otros trabajos fueran tan buenos como este, no estaría dando vueltas y perdiendo el tiempo. Claro y sintético que te abre la puerta a muchas cosas relacionadas. Debéis poner una opción de donaciones o que os financien y ampliar estos temas. Me ha salvado la asignatura.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *