Algoritmo FIND-S - pregunta simple

Question

El algoritmo FIND-S es probablemente uno de los algoritmos de aprendizaje automático más simples. Sin embargo, no puedo encontrar muchos ejemplos por ahí. Solo los ejemplos estándar de "sol, lluvia, pelota de béisbol" que siempre se utilizan en el aprendizaje automático. Por favor, podría alguien ayudarme con esta aplicación (es una pregunta del examen pasado en aprendizaje automático).

hipótesis son de la forma a <= x <= b, c <= y <= d donde x y y son puntos en un plano x,y y c y d son cualquier número entero. Básicamente, estas hipótesis definen rectángulos en el espacio x,y.

Estos son los ejemplos de entrenamiento, donde - es un ejemplo negativo y + es un ejemplo positivo y los pares son los x,y coordenadas:

+ 4, 4 
+ 5, 3 
+ 6, 5 
- 1, 3 
- 2, 6 
- 5, 1 
- 5, 8 
- 9, 4 

Todo lo que quiero hacer es aplicar FIND-S a esta ¡ejemplo! ¡Debe ser simple! O bien algunos consejos o una solución sería increíble.

Gracias.

Answer 1

Find-S busca la hipótesis más restrictiva (es decir, la más "específica") que se ajusta a todos los ejemplos positivos (los negativos se ignoran).

En su caso, hay una interpretación gráfica obvia: "encontrar el rectángulo más pequeño que contiene todos los '+' coordenadas" ...

... lo que sería a = 4, b = 6, c = 3, d = 5.

El algoritmo para hacerlo sería algo como esto:

Define a hypothesis rectangle h[a,b,c,d], and initialise it to [-,-,-,-] 
for each + example e { 
    if e is not within h { 
     enlarge h to be just big enough to hold e (and all previous e's) 
    } else { do nothing: h already contains e } 
} 

Si damos un paso a través de este con su conjunto de entrenamiento, obtenemos:

0. h = [-,-,-,-] // initial value 
1. h = [4,4,4,4] // (4,4) is not in h: change h so it just contains (4,4) 
2. h = [4,5,3,4] // (5,3) is not in h, so enlarge h to fit (4,4) and (5,3) 
3. h = [4,6,3,5] // (6,5) is not in h, so enlarge again 
4. // no more positive examples left, so we're done.