- 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 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
Contenido
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 y 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-AprendidasEl 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:
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
Bibliografía
- Mitchell, T.M. Machine Learning (McGraw-Hill, 1997)
Categoría:- Algoritmos de búsqueda
Wikimedia foundation. 2010.
