Algoritmo de eliminación de candidatos
# Algoritmo de eliminación de candidatos

El algoritmo de eliminación de candidatos es utilizado dentro del ámbito de la inteligencia artificial. Su uso se engloba en la búsqueda de hipótesis o conceptos en él dado un conjunto de ejemplos de entrenamiento. Este algoritmo se puede expresar como una extensión del algoritmo find-s.

El conjunto de ejemplos deberá estar conformado por una serie de tuplas de valores, cada uno de ellos denominados atributos. Adicionalmente, uno de los atributos ha de ser de tipo binario (Sí/No, Cierto/Falso, Válido/Inválido), el cual es el atributo objetivo a clasificar que diferencia el concepto. De esta forma el algoritmo trata de obtener un intervalo de hipótesis flanqueadas por un límite más específico y un límite más general de forma que las nuevas instancias se consideran consistentes con el intervalo aprendido si están dentro de él.

Una vez obtenida el intervalo de hipótesis se puede determinar si una nueva instancia la cumple.

Eliminación de candidatos realiza esta labor tomando una tupla de valores con el mismo número de atributos, menos el del atributo objetivo, que los de entrenamiento. Pero de forma adicional define un nuevo tipo de valores que puede adoptar un atributo.

* Ø que representa ningún valor. Este es el valor más específico posible.
* ? que representa cualquier valor. Este es el valor más general posible.

## Espacio de versiones

El intervalo de hipótesis se denomina espacio de versiones. Para el correcto funcionamiento del algoritmo se define un orden de generalidad. de forma que dos hipótesis $h_{1}>_{g}h_{2}$ si $h_{1}$ es más general que $h_{2}$.

Los límites del intervalo se denominan Cota general (G) y Cota específica (S). Estos son conjuntos de tuplas.

## Orden de generalidad

De forma concreta una tupla es más específica que otra si contiene un mayor número de valores concretos o (Ø). O lo que es lo mismo, la que contiene el menor número interrogaciones representado cualquier valor posible.

## Generalizaciones y especializaciones

La hipótesis más específica es aquella conformada por toda la tupla a Ø La hipótesis más general es aquella conformada por toda la tupla a ?

Las generalizaciones minimales consisten en realizar los siguientes cambios en cada tupla de S

* Si el atributo de la hipótesis es Ø y el del ejemplo contiene un valor entonces se cambia por el del valor del ejemplo
* Si en cambio la hipótesis contiene un valor distinto a Ø y el del ejemplo otro valor distinto entonces se modifica por una ?

Las especializaciones minimales consisten en realizar los siguientes cambios en G

* Se crean nuevas tuplas por cada atributo que su valor ha permanecido constante.

## Clasificación de nuevas instancias

* Si es consistente con todo S, positivo
* Si no es consistente con ninguno de G, negativo
* En otro caso, voto mayoritario

## Un ejemplo

| Cielo | Temperatura | Humedad | Viento | Agua | Previsión | Hacer Deporte |
| - | - | - | - | - | - | - |
| Soleado | Templada | Normal | Fuerte | Templada | Igual | Sí |
| Soleado | Templada | Alta | Fuerte | Templada | Igual | Sí |
| Lluvia | Fría | Alta | Fuerte | Templada | Cambio | No |
| Soleado | Templada | Alta | Fuerte | Fría | Cambio | Sí |

Paso 0: S0 = {< ∅, ∅, ∅, ∅, ∅, ∅ >}, G0 = {<?, ?, ?, ?, ?, ? >}

Paso 1:

* Ejemplo positivo: < Sol, Templ, Normal, Fuerte, Templ, Igual >
* Nada que eliminar de G0
* Generalización minimal de S0: < Sol, Templ, Normal, Fuerte, Templ, Igual >

Esta generalización es más específica que la hipótesis de G0

* Luego:

S1 = {< Sol, Templ, Normal, Fuerte, Templ, Igual >} G1 = {<?, ?, ?, ?, ?, ? >}

Paso 2:

* Ejemplo positivo: < Sol, Templ, Alta, Fuerte, Templ, Igual >
* Nada que eliminar de G1
* Generalización minimal de S1: < Sol, Templ, ?, Fuerte, Templ, Igual >

Esta generalización es más específica que la hipótesis de G1

* Luego:

S2 = {< Sol, Templ, ?, Fuerte, Templ, Igual >} G2 = {<?, ?, ?, ?, ?, ? >}

Paso 3:

* Ejemplo negativo: < Lluvia, Fría, Alta, Fuerte, Templada, Cambio >
* Nada que eliminar de S2.
* Especializaciones minimales de G2 que son más generales que la hipótesis

de S2: < Sol, ?, ?, ?, ?, ? >, <?, Templ, ?, ?, ?, ? > y <?, ?, ?, ?, ?, Igual >.

* Luego:

S3 = {< Sol, Templ, ?, Fuerte, Templ, Igual >} G3 = {< Sol, ?, ?, ?, ?, ? >, <?, Templ, ?, ?, ?, ? >, <?, ?, ?, ?, ?, Igual >}

Paso 4:

* Ejemplo positivo: < Sol, Templ, Alta, Fuerte, Fría, Cambio >
* Eliminamos de G3 la hipótesis <?, ?, ?, ?, ?, Igual >
* Generalización minimal de S3: < Sol, Templ, ?, Fuerte, ?, ? >

Esta generalización es más específica que hipótesis de G3.

* Luego:

S4 = {< Sol, Templ, ?, Fuerte, ?, ? >} G4 = {< Sol, ?, ?, ?, ?, ? >, <?, Templ, ?, ?, ?, ? >}

