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 regla

            y para la regla sin la última condición m(R-)

          Mientras m(R-) < m(R), elimina la última condición 

             de la regla y repite el proceso

      De las reglas generadas, selecciona aquellas 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%

Then

Return RuleSet

Else

Anadir 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)  >  1000 + (Neg _ 1)

 

    Pos + Neg                      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  <    1000 – 1

 

    3000                 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

 

 




    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: