Podado de Reglas de Decisión

abril 16, 2008 in 1
Etiquetas: ECC, ECCUTPL, IAA, UTPL

Podado de Reglas de decisión

 Las reglas de decisión son formadas con el objetivo de poder describir un sistema en el cual pueden ocurrir diferentes eventos, estas reglas son un paradigma más genérico y flexible que los árboles de clasificación, son además fácilmente comprensibles y aplicables.

 Pruning

 Una forma de evaluar si una regla es buena es considerar la probabilidad de que una regla aleatoria nos de resultados iguales o mejores que la regla a considerar, basados en la mejora en ejemplos positivos cubiertos.

Generar reglas que cubran puros ejemplos positivos. Esta regla es probable que este sobre-especializada. Lo que se hace es que se elimina el último término que se añadió y se verifica si esta regla es mejor a la anterior (ver abajo). Este proceso se repite hasta que no existan mejoras (ver tabla 4.6).

 

Tabla 4.6: Algoritmo de podado de reglas.

Inicializa E al conjunto de ejemplos  Until E sea vacío do      Para cada clase C      Crea una regla perfecta para la clase C      Calcula la medida de probabilidad m(R) para la regla             y para la regla sin la última condición(R-)          Mientras m(R-) < m (R), elimina la última condición              de la regla y repite el proceso         De las reglas generadas, selecciona aquella con m(R)  menor         Elimina las instancias cubiertas por la regla

 

Este algoritmo no garantiza encontrar las mejores reglas por 3 razones principales:

 (i) el algoritmo para construir las reglas, no necesariamente produce las mejores reglas para ser reducidas,

(ii) la reducción de reglas empieza con la última condición, y no necesariamente es el mejor orden, y

(iii) la reducción de reglas termina cuando cambia la estimación, lo cual no garantiza que el seguir recortando pueda mejorar de nueva la estimación. [1]

 Sobre el tema específico de podado de reglas no hay mucha información, pero aquí un ejemplo de un algoritmo que aplica podado de reglas el Algoritmo de RIPPER, este algoritmo es una extensión del denominado IREP (Fϋrnkranz y Widner, 1994), a continuación pongo a consideración un extracto del artículo encontrado.

 

IREP (Incremental Reduced Error Pruning)

 El conjunto de reglas que se van a considerar en el algoritmo IREP (Fϋrnkranz y Widner, 1994) van a estar en forma normal disyuntiva. Conceptos básicos utilizados por IREP son los de regla (rule), conjunto de reglas (rule set) y regla parcial (partial rule).

 IREP necesita que el conjunto de casos o patrones etiquetados que denotamos por D se particione en dos. El primero de dichos subconjuntos D_pos va a contener el conjunto de patrones positivos, mientras que el segundo subconjunto D_neg va a contener el conjunto de patrones negativos. Además de esta partición es necesario subdividir cada uno de los subconjuntos anteriores (D_pos y D_neg) en otros dos subconjuntos. Es decir, a partir del conjunto de ejemplos positivos D_pos obtenemos D_{grow_pos} y D_{prune_pos} subconjuntos relacionados respectivamente con la construcción y el podado de las reglas.

 Procedure IREP

    Begin

       Ruleset=0;

       While D_Pos = D_{Grow_Pos} U D_{Prune_Pos}  ≠ 0 do

          /* Construir y podar una nueva regla */

           Dividir D en D_{Grow_Pos} U D_{Grow_Neg} U D_{Prune_Pos} U D_{Prune_Neg}

               Rule := GrowRule (D_{Grow_Pos} U D_{Grow_Neg})

               Rule := PruneRule (Rule, D_{Prune_Pos}; D_{Prune_Neg})

                If la tasa de error de Rule en D_{Prune_Pos} U D_{Prune_Neg} > 50%

The

  Return RuleSet

  Else

  Añadir Rule a RuleSet

   Borrar ejemplos abiertos por Rule de D

   End if

              End while

             Return RuleSet

          End

      Fig. 1. Pseudocódigo del Algoritmo IREP

  EL proceso de poda se efectúa por medio del procedimiento PruneRule. En este procedimiento PruneRule se plantea el borrado, de manera secuencial, y empezando por el último literal introducido a la regla en su fase de crecimiento. Se van a ir borrando (podando) literales mientras se mejore el criterio v(Rule; D_{prune_pos}; D_{prune_neg}), siendo

 

         v(Rule; D_{prune_pos}; D_{prune_neg}) =  Pos – neg / Pos + neg

      Con:

Pos número de ejemplos en D_{prune_pos}

Neg número de ejemplos en D_{prune_neg}

pos número de ejemplos positivos en D_{prune_pos} cubiertos por la regla

neg número de ejemplos negativos en D_{prune_neg} cubiertos por la regla

 

 RIPPER (Repeated Incremental Pruning Produce Error Reduc-tion)

 RIPPER fue introducido por Cohen (1995) y constituye una mejora del algoritmo

IREP. Las mejoras introducidas por RIPPER pueden resumirse en tres puntos:

 

1. Métrica alternativa para la fase de poda.

 Supongamos que la regla R1 cubre 2000 ejemplos positivos en Dprune_pos y 1000 ejemplos negativos en D_{prune_neg}. Igualmente la regla R2 cubre 1000 ejemplos positivos en Dprune_pos y 1 ejemplo negativo en D_{prune_neg}. Se puede ver de manera sencilla que independientemente de los valores de Pos y Neg, el criterio de poda utilizado por IREP va a preferir R1 a R2, ya que

 

 ( 2000 + (Neg _ 1000)  / Pos + Neg)  >  (1000 + (Neg _ 1) /  Pos + Neg)

Y sin embargo es intuitivo que la R2 es preferible a R1. Para corregir esta carencia RIPPER basa su poda en el criterio siguiente:

 

   v(Rule; D_{prune_pos}; D_{prune_neg}) =  Pos – neg / Pos + neg

 

 En tal caso tendríamos:

 

 (2000 – 1000)/3000  <    (1000 -1)/1001

 

 Y R2 se seleccionaría frente a R1.

2. Incorporación de un heurístico para determinar cuando parar el proceso de añadir reglas.

3. Posteriormente a todo el proceso visto para IREP, el algoritmo RIPPER efectúa una búsqueda local para optimizar el conjunto de reglas (rule set) de dos maneras diferentes:

 a) Reemplazando una regla Ri que forma parte del rule set {

R₁;…; R_i-1; R_i; R_i+1;  …;R_k} por R_i´ , siempre y cuando el rule set correspondiente tenga un menor error en la clasificación en D_{prune_pos} U D_{prune_neg.}

 

b) Revisar una determinada regla R_i añadiendo literales para que se consiga un menor error en D_{prune_pos} U D_{prune_neg.} [2]

 

 Para más información pueden ingresar a las siguientes direcciones:

 [1] http://ccc.inaoep.mx/~emorales/Cursos/KDD03/node30.html

 [2] Pedro Larrañaga, Iñaki Inza, Abdelmalik Moujahid Departamento de Ciencias de la Computación e Inteligencia Artificial Universidad del País Vasco-Euskal Herriko Unibertsitatea

 http://www.sc.ehu.es/ccwbayes/docencia/mmcc/docs/t11reglas.pdf