Algoritmo de cobertura

El algoritmo de cobertura es utilizado dentro del ámbito de la inteligencia artificial. Su uso se engloba en la búsqueda de reglas en él dado un conjunto de ejemplos de entrenamiento.

El conjunto de ejemplos deberá estar conformado por una serie de tuplas de valores, cada uno de ellos denominados atributos. Uno de los atributos debe ser el objetivo, del cual se crearán las reglas que diferencien un valor de otro.

El objetivo del algoritmo de cobertura es la obtención de una regla de la forma:

SI conjunción de pares <atributo, valor> ENTONCES atributo-objetivo = valor

Donde la conjunción de pares <atributo, valor> es de la forma:

atributo = valor

El algoritmo

Aprendizaje-por-Cobertura(D, Atributo-objetivo, v)
  Hacer Reglas-aprendidas igual a vacío
  Hacer E igual a D
  Mientras E contenga ejemplos cuyo valor de Atributo-objetivo es v, hacer:
     Crear una regla R sin condiciones y conclusión Atributo-objetivo=v
     Mientras que haya en E ejemplos cubiertos por R incorrectamente
       o no queden atributos que usar, hacer:
        Elegir la MEJOR condición A=w para añadir a R, donde A es
          un atributo que no aparece en R y w es un valor de los
          posibles que puede tomar A
        Actualizar R añadiendo la condición A=w a R
     Incluir R en Reglas-aprendidas
     Actualizar E quitando los ejemplos cubiertos por R
  Devolver Reglas-Aprendidas

El algoritmo se compone de dos bucles anidados. El bucle externo busca la obtención de reglas el valor del atributo objetivo pasado v. El bucle interno construye la conjunción de pares <atributo, valor> que contengan ejemplos con dicho valor de objetivo y así crear la regla. Como en una pasada del bucle interno pueden quedar ejemplos sin cubrir se deben crear nuevas reglas para dicho par atributo-objetivo = valor

La ausencia de una condición se suele representar con el símbolo ?

Elección de la MEJOR condición

Para la elección de la mejor condición hay diversos métodos

• Mayor frecuencia relativa en ejemplos en los que el atributo objetivo contiene v
• Mayor ganancia de información por entropía:$\left\vert p\right\vert \left(\log _{2}{\frac {\left\vert p'\right\vert }{\left\vert t'\right\vert }}-\log _{2}{\frac {\left\vert p\right\vert }{\left\vert t\right\vert }}\right)$

Donde p y t son los conjuntos de casos positivos y totales. Los p' y t' son los conjuntos positivos y totales que quedarán una vez añadida la condición.

Ejemplo

Ej.	Edad	Diagnostico	Astigmatismo	Lágrima	Lente
E1	Joven	Miope	-	Reducida	Ninguna
E2	Joven	Miope	-	Normal	Blanda
E3	Joven	Miope	+	Reducida	Ninguna
E4	Joven	Miope	+	Normal	Rígida
E5	Joven	Hipermétrope	-	Reducida	Ninguna
E6	Joven	Hipermétrope	-	Normal	Blanda
E7	Joven	Hipermétrope	+	Reducida	Ninguna
E8	Joven	Hipermétrope	+	Normal	Rígida
E9	Pre-presbicia	Miope	-	Reducida	Ninguna
E10	Pre-presbicia	Miope	-	Normal	Blanda
E11	Pre-presbicia	Miope	+	Reducida	Ninguna
E12	Pre-presbicia	Miope	+	Normal	Rígida
E13	Pre-presbicia	Hipermétrope	-	Reducida	Ninguna
E14	Pre-presbicia	Hipermétrope	-	Normal	Blanda
E15	Pre-presbicia	Hipermétrope	+	Reducida	Ninguna
E16	Pre-presbicia	Hipermétrope	+	Normal	Ninguna
E17	Presbicia	Miope	-	Reducida	Ninguna
E18	Presbicia	Miope	-	Normal	Ninguna
E19	Presbicia	Miope	+	Reducida	Ninguna
E20	Presbicia	Miope	+	Normal	Rígida
E21	Presbicia	Hipermétrope	-	Reducida	Ninguna
E22	Presbicia	Hipermétrope	-	Normal	Blanda
E23	Presbicia	Hipermétrope	+	Reducida	Ninguna
E24	Presbicia	Hipermétrope	+	Normal	Ninguna

En la primera pasada de bucle externo para Lente = Rígida

Si ? Entonces Lente = Rígida

En la primera pasada del bucle interno la mejor frecuencia relativa hace escoger:

Si Astigmatismo = + Y ? Entonces Lente = Rígida

En la segunda pasada bucle interno la mejor frecuencia relativa hace escoger:

Si Astigmatismo = + Y Lágrima = Normal Y ? Entonces Lente = Rígida

Como la frecuencia relativa es 1 entonces se obtiene esta regla:

Si Astigmatismo = + Y Lágrima = Normal Entonces Lente = Rígida

Al haber casos de lente= Rígida sin cubrir se procede a continuar la búsqueda de nuevas reglas eliminando los casos ya usados en el bucle externo.

Véase también

• Algoritmo find-s
• Algoritmo id3
• FOIL

Bibliografía

• Mitchell, T.M. Machine Learning (McGraw-Hill, 1997)