Algorithme D'Élimination Du Candidat
Considérez les ensembles de données de formation suivants..
+-------+-------+----------+-------------+
| Size | Color | Shape | Class/Label |
+=======+=======+==========+=============+
| big | red | circle | No |
| small | red | triangle | No |
| small | red | circle | Yes |
| big | blue | circle | No |
| small | blue | circle | Yes |
+-------+-------+----------+-------------+
Je voudrais comprendre comment l'algorithme se déroule quand il commence par un exemple négatif et quand deux exemples négatifs se rencontrent.
Ce n'est pas une question d'affectation en passant.
Exemples avec d'autres ensembles de données sont également les bienvenus! C'est pour comprendre la partie négative de l'algorithme.
1 réponses
Pour votre espace d'hypothèse (H) , vous commencez par vos ensembles d'hypothèses maximalement générales (G) et maximalement spécifiques (s):
G0 = {<?, ?, ?>}
S0 = {<0, 0, 0>}
Quand on vous présente un exemple négatif, vous devez supprimer de S toute hypothèse incompatible avec l'observation actuelle et remplacer toute hypothèse incohérente dans G par ses spécialisations minimales qui sont cohérentes avec l'observation mais toujours plus générales que certains membres de S.
Donc pour votre premier exemple (négatif), (big, red, circle), les spécialisations minimales rendraient l'Espace nouvelle hypothèse
G1 = {<small, ? , ?>, <?, blue, ?>, <?, ?, triangle>}
S1 = S0 = {<0, 0, 0>}
Notez que S n'a pas changé. Pour votre prochain exemple, (small, red, triangle), qui est également négatif, vous devrez vous spécialiser davantage G. notez que la deuxième hypothèse dans G1 ne correspond pas à la nouvelle observation, donc seules les première et troisième hypothèses dans G1 doivent être spécialisées. Cela donnerait
G2 = {<small, blue, ?>, <small, ?, circle>, <?, blue, ?>, <big, ?, triangle>, <?, blue, triangle>}
Cependant, puisque la première et la dernière hypothèse dans G2 ci-dessus sont des spécialisations de l'hypothèse du milieu (<?, blue, ?>), nous laissons tomber ces deux, donnant
G2 = {<small, ?, circle>, <?, blue, ?>, <big, ?, triangle>}
S2 = S1 = S0 = {<0, 0, 0>}
Pour l'observation positive (small, red, circle), vous devez généraliser S et supprimer tout ce qui est incohérent dans G, ce qui donne
G3 = {<small, ?, circle>}
S3 = {<small, red, circle>}
(big, blue, circle) est l'exemple négatif suivant. Mais comme il n'est pas compatible avec G, il n'y a rien à faire
G4 = G3 = {<small, ?, circle>}
S4 = S3 = {<small, red, circle>}
Enfin, vous avez l'exemple positif de (small, blue, circle), qui vous oblige à généraliser S pour le rendre cohérent avec l'exemple, en donnant
G5 = {<small, ?, circle>}
S5 = {<small, ?, circle>}
Puisque G et S sont égaux, vous ont appris le concept de "petits cercles".