Algoritme de cobertura

El algoritme de cobertura és utilisat dins de l'àmbit de l'inteligència artificial. El seu us s'engloba en la busca de regles en ell donat un conjunt d'eixemples d'entrenament.

L'objectiu de l'algoritme de cobertura és l'obtenció d'una regla de la forma: SI conjunció de parells <atribut, valor> ENTONCES atribut-objectiu = valor

A on la conjunció de parells <atribut, valor> és de la forma:

atribut = valor

L'algoritme

Aprenentage-per-Cobertura(D, Atribut-objectiu, v)
  Fer Regles-depreses igual a buit
  Fer I igual a
  D Mentres I continga eixemples el valor dels quals d'Atribut-objectiu és v, fer:
     Crear una regla R sense condicions i conclusió Atribut-objectiu=v
     Mentres que hi haja en I eixemples coberts per R incorrectament
       i queden atributs que usar, fer:
        Elegir la MEJOR condició A=w per a afegir a R, a on A
          és un atribut que no apareix en R i w és un valor dels
          possibles que pot prendre A
        Actualisar R afegint la condició A=w a
     R Incloure R en Regles-depreses
     Actualisar I llevant els eixemples coberts per
  R Tornar Regles-Depreses

L'algoritme es compon de dos bucles anidados. El bucle extern busca l'obtenció de regles el valor de l'atribut objectiu passat v. El bucle intern construïx la conjunció de parells <atribut, valor> que continguen eixemples en dit valor d'objectiu i aixina crear la regla. Com en una passada del bucle intern poden quedar eixemples sense cobrir es deuen crear noves regles per a dit parell atribut-objectiu = valor

L'absència d'una condició se sol representar en el símbol ?

Elecció de la MEJOR condició

Per a l'elecció de la millor condició hi ha diversos métodos

• Major freqüència relativa en eixemples en els que l'atribut objectiu conté v
• Major guany d'informació per entropía:$\left|p\right|({\log }_2\frac{\left|p^{\prime }\right|}{\left|t^{\prime }\right|}-{\log }_2\frac{\left|p\right|}{\left|t\right|})$

A on p i t són els conjunts de casos positius i totals. Els p' i t' són els conjunts positius i totals que quedaran una volta afegida la condició.

Vore també

• Algoritme find-s
• Algoritme aneu3
• FOIL

Bibliografia

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