Podado de Reglas de Decisión

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 Dpos va a contener el conjunto de patrones positivos, mientras que el segundo subconjunto Dneg va a contener el conjunto de patrones negativos. Además de esta partición es necesario subdividir cada uno de los subconjuntos anteriores (Dpos y Dneg) en otros dos subconjuntos. Es decir, a partir del conjunto de ejemplos positivos Dpos obtenemos Dgrow_pos y Dprune_pos subconjuntos relacionados respectivamente con la construcción y el podado de las reglas.

 Procedure IREP

    Begin

       Ruleset=0;

       While DPos = DGrow_Pos U DPrune_Pos  ≠ 0 do

          /* Construir y podar una nueva regla */

           Dividir D en DGrow_Pos U DGrow_Neg U DPrune_Pos U DPrune_Neg

               Rule := GrowRule (DGrow_Pos U DGrow_Neg)

               Rule := PruneRule (Rule, DPrune_Pos; DPrune_Neg)

                If la tasa de error de Rule en DPrune_Pos U DPrune_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; Dprune_pos; Dprune_neg), siendo

 

         v(Rule; Dprune_pos; Dprune_neg) =  Pos – neg / Pos + neg

      Con:

Pos número de ejemplos en Dprune_pos

Neg número de ejemplos en Dprune_neg

pos número de ejemplos positivos en Dprune_pos cubiertos por la regla

neg número de ejemplos negativos en Dprune_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 Dprune_neg. Igualmente la regla R2 cubre 1000 ejemplos positivos en Dprune_pos y 1 ejemplo negativo en Dprune_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; Dprune_pos; Dprune_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 {

R1;…; Ri-1; Ri; Ri+1;  …;Rk} por Ri´ , siempre y cuando el rule set correspondiente tenga un menor error en la clasificación en Dprune_pos U Dprune_neg.

 

b) Revisar una determinada regla Ri añadiendo literales para que se consiga un menor error en Dprune_pos U Dprune_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

 

 


  1. Choco

    Hey!! Muchas gracias por este breve artículo. Tenemos que hacer un trabajo sobre los algoritmos IREP y RIPPER entre otros y se agracede un poco de informacion en español. ^_^




Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s



A %d blogueros les gusta esto: