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:
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:
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 (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.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: k = nº de clases 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.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 dónde: NT es el número de hojas para el subárbol T, 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 | 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:
|
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.