FIND-S Algorithm - question simple

Question

L'algorithme FIND-S est probablement l'un des algorithmes d'apprentissage automatique les plus simples. Cependant, je ne peux pas trouver beaucoup d'exemples là-bas. Juste les exemples standard «ensoleillés, pluvieux, de jeu-balle» qui sont toujours utilisés dans l'apprentissage automatique. S'il vous plaît quelqu'un pourrait m'aider avec cette application (c'est une question d'examen passé en apprentissage automatique).

Hypotheses sont de la forme a <= x <= b, c <= y <= d où x et y sont des points dans un plan x,y et c et d sont un entier quelconque. Fondamentalement, ces hypothèses définissent des rectangles dans l'espace x,y.

Ce sont les exemples de formation où - est un exemple négatif et + est un exemple positif et les paires sont les coordonnées x,y:

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

Tout ce que je veux faire est d'appliquer FIND-S à cette Exemple! Ça doit être simple! Soit quelques conseils ou une solution serait génial.

Merci.

Answer 1

Find-S recherche l'hypothèse la plus restrictive (c.-à-d. La plus «spécifique») qui correspond à tous les exemples positifs (les négatifs sont ignorés).

Dans votre cas, il y a une interprétation graphique évidente: "trouver le plus petit rectangle qui contient toutes les '+' coordonnées" ...

... qui serait a = 4, b = 6, c = 3, d = 5.

L'algorithme pour le faire serait quelque chose comme ceci:

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 nous faisons un pas à travers avec votre jeu de formation, nous obtenons:

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.