Algoritme find-s

L'algoritme find-s és utilisat dins de l'àmbit de l'inteligència artificial. El seu us s'engloba en la busca d'hipòtesis o conceptes en ell donat un conjunt d'eixemples.

El conjunt d'eixemples deurà estar conformat per una série de tuplas de valors, cada u d'ells denominats atributs. Adicionalment un dels atributs ha de ser de tipo binari (sí/no, cert/fals, vàlit/inválido), el qual és l'atribut objectiu a classificar que diferencia el concepte. D'esta forma l'algoritme tracta d'obtindre una hipòtesis que siga la més específica als atributs en comú de tots els eixemples del conjunt d'entrenament que se li ha suministrat.

Una volta obtinguda l'hipòtesis es pot determinar si una nova instància la complix.

FIND-s realisa esta llabor prenent una tupla de valors en el mateix número d'atributs, menys el de l'atribut objectiu, que els d'entrenament. Pero de forma adicional definix un nou tipo de valors que pot adoptar un atribut.

• Ø, que representa cap valor. Est és el valor més específic possible.
• ?, que representa qualsevol valor. Est és el valor més general possible.

L'algoritme Find-S

Find-S (Eixemples)

   Siga inicialment l'hipòtesis més específica
   Per cada eixemple positiu d'Eixemples
        Si l'hipòtesis concorda en l'eixemple no fer res
        sino canviar l'hipòtesis per la menor generalisació de sí mateixa

Generalisacions i especialisació

L'hipòtesis més específica és aquella conformada per tota la tupla a Ø La menor generalisació consistix en realisar els següents canvis

• Si l'atribut de l'hipòtesis és Ø i el de l'eixemple conté un valor llavors es canvia pel del valor de l'eixemple
• Si en canvi l'hipòtesis conté un valor distint a Ø i el de l'eixemple atre valor distint llavors es modifica per una ?

Vore també

• Algoritme aneu3
• Algoritme de cobertura
• FOIL

Bibliografia

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