close

Se connecter

Se connecter avec OpenID

Aq (Algorithme de l`étoile)

IntégréTéléchargement
Aq (Algorithme de l’étoile)
Jérôme AZÉ
LRI – équipe IA
Plan






Présentation de Aq
Algorithme
Un exemple
Défauts de la méthode
Solution apportée
Application à la génomique
DEA I3 - Module Génomique
2
Aq (Algorithme de l’étoile)
 Proposé par R. Michalski (1969)
 Problème :
 un ensemble d’attributs
 2 classes (POS, NEG)
 Objectif :
 Apprendre une description correcte et complète de
la classe POS
DEA I3 - Module Génomique
3
N EG
PO S
Ensemble d’apprentissage
E x e m ple s
A tt1
A tt2
A tt3
C lasse
E1
Y
N
R
+
E2
X
M
R
+
E3
Y
N
S
+
E4
X
N
R
+
F1
X
M
S
-
F2
Y
M
T
-
F3
Y
N
T
-
F4
Z
N
T
-
F5
Z
N
R
-
F6
X
N
S
-
DEA I3 - Module Génomique
4
Algorithme
 Diviser les exemples en deux sous ensembles
(POS, NEG)
 Choisir un exemple dans POS (le noyau)
 Trouver un ensemble de règles générales
caractérisant le noyau (l’étoile)
 Choisir la meilleure règle dans l’étoile
 Itérer s’il reste des exemples non couverts dans
POS
DEA I3 - Module Génomique
5
NEG
POS
Changement de
représentation (1/4)
E xe mp le s
A tt1
A tt2
A tt3
C lass e
E1
Y
N
R
+
E2
X
M
R
+
E3
Y
N
S
+
E4
X
N
R
+
F1
X
M
S
-
F2
Y
M
T
-
F3
Y
N
T
-
F4
Z
N
T
-
F5
Z
N
R
-
F6
X
N
S
-
DEA I3 - Module Génomique
M
N
F3 F4
F6 E3
T
S
R
E4 E1 F5
X Y Z
6
NEG
POS
Changement de
représentation (2/4)
E xe mp le s
A tt1
A tt2
A tt3
C lass e
E1
Y
N
R
+
E2
X
M
R
+
E3
Y
N
S
+
E4
X
N
R
+
F1
X
M
S
-
F2
Y
M
T
-
F3
Y
N
T
-
F4
Z
N
T
-
F5
Z
N
R
-
F6
X
N
S
-
M
N
F3 F4
F6 E3
E4 E1 F5
X Y Z
N
M
DEA I3 - Module Génomique
R
T
S
F2
F1
E2
X Y
T
S
R
Z
7
NEG
POS
Changement de
représentation (3/4)
E xe mp le s
A tt1
A tt2
A tt3
C lass e
E1
Y
N
R
+
E2
X
M
R
+
E3
Y
N
S
+
E4
X
N
R
+
F1
X
M
S
-
F2
Y
M
T
-
F3
Y
N
T
-
F4
Z
N
T
-
F5
Z
N
R
-
F6
X
N
S
-
A tt1
E2
E4
F1
X
F6
E1
E3
F2
F5
M
N
R
M
N
S
DEA I3 - Module Génomique
M
T
F3
Y
F4
Z
N
A tt2
A tt3
8
Changement de
représentation (4/4)
A tt1
NEG
POS
E xe mp le s
A tt2
A tt3
C lass e
E1
Y
N
R
+
E2
X
M
R
+
E3
Y
N
S
+
E4
X
N
R
+
F1
X
M
S
-
F2
Y
M
T
-
F3
Y
N
T
-
F4
Z
N
T
-
F5
Z
N
R
-
F6
X
N
S
-
A tt1
+
+
-
+
-
X
+
-
Y
-
Z
N
A tt2
-
M
N
R
M
N
S
M
T
A tt1
E2
E4
F1
X
F6
E1
E3
F2
F5
M
A tt3
DEA I3 - Module Génomique
N
R
M
N
S
M
T
F3
Y
F4
Z
N
A tt2
A tt3
9
Apprentissage (1/4)
N EG
PO S
 Choix du noyau : E1
E x e m ple s
A tt1
A tt2
A tt3
C lasse
E1
Y
N
R
+
E2
X
M
R
+
E3
Y
N
S
+
E4
X
N
R
+
F1
X
M
S
-
F2
Y
M
T
-
F3
Y
N
T
-
F4
Z
N
T
-
F5
Z
N
R
-
F6
X
N
S
-
 Génération de l ’étoile de E1 tel que F1 ne soit
pas couvert
DEA I3 - Module Génomique
10
Apprentissage (2/4)
 E1 :
F1
E1
• (Att1 = Y)
• (Att2 = N)
• (Att3 = R)
A tt1
+
+
-
X
-
+
+
-
-
 Négation de F1 :
M
N
M
R
N
S
M
T
-
Y
-
Z
N
A tt2
A tt3
• (Att1 = Y v Z)
• (Att2 = N)
• (Att3 = R v T)
DEA I3 - Module Génomique
11
Apprentissage (3/4)
 Prise en considération de F2
• Att3 = R
• (Att3 = (R v S)) & (Att1 = (Y v Z))
• Att2 = N
F2
A tt1
+
+
-
X
-
+
+
-
M
N
R
M
N
S
DEA I3 - Module Génomique
M
T
-
Y
-
Z
N
A tt2
A tt3
12
Apprentissage (4/4)
 Prise en considération de F3 (ou F4)
• (Att3 = R) & (Att1 = X v Y)
• (Att3 = (R v S)) & (Att1 = (Y v Z))
F3
A tt1
+
+
-
X
-
+
+
-
M
N
R
M
N
S
DEA I3 - Module Génomique
M
T
-
Y
-
Z
N
A tt2
F4
A tt3
13
Étoile de E1
 La spécialisation des règles conduit à :
R1’ : (att1 = X v Y) & (att3 = R)
R2’ : (att1 = Y) & (att3 = R v S)
A tt1
+
+
-
X
-
+
+
-
M
N
R
M
N
S
M
-
Y
-
Z
N
A tt2
T
DEA I3 - Module Génomique
A tt3
14
Critères de sélection des
règles dans l’étoile
 Maximiser le nombre d ’éléments couverts
par la règle retenue
 Minimiser le nombre d ’attributs de la
règle retenue
 Maximiser la capacité à généraliser de la
règle retenue
 ...
DEA I3 - Module Génomique
15
Critère et règle retenus
 Maximiser le nombre d’exemples couverts
 Règle retenue :
• R1’ : (att1 = X v Y) & (att3 = R)
A tt1
+
+
-
X
-
+
+
-
-
E3
M
N
R
M
N
S
M
-
Y
-
Z
N
A tt2
T
DEA I3 - Module Génomique
A tt3
16
Itération de l’algorithme
 Exemple non couvert par R1’ : E3
 Étoile de E3 :
• R : (att1 = Y) & (att3 = R v S)
A tt1
+
+
X
-
-
+
+
-
M
N
R
M
N
S
M
-
Y
-
Z
N
A tt2
T
DEA I3 - Module Génomique
A tt3
17
Résultat final
 Deux règles permettent de caractériser
POS par rapport à NEG
• R1 : (att1 = X v Y) & (att3 = R)
• R2 : (att1 = Y) & (att3 = R v S)
A tt1
+
+
-
X
-
+
+
-
M
N
R
M
N
S
M
-
Y
-
Z
N
A tt2
T
DEA I3 - Module Génomique
A tt3
18
Défauts de Aq
 Sensibilité au bruit dans les classes
 Sensibilité liée à l’imprécision du contexte
 Solution proposée par R. Michalski (1990)
• approche à deux niveaux (two-tiered
approach )
DEA I3 - Module Génomique
19
Approche à deux niveaux
(1/3)
 Idée :
• découper la description de la classe POS en
deux parties :
 Représentation de Base du Concept (RBC)
 Interprétation Inférentielle du Concept (IIC)
 Possibilité d’apprendre des concepts
flexibles
DEA I3 - Module Génomique
20
Approche à deux niveaux
(2/3)
 Algorithme
• Utiliser Aq pour obtenir l’ensemble initial de
règles
• Retenir la règle la plus importante (nombre
maximal d’éléments de POS couverts) : RBC
• Définir la procédure IIC pour reconnaître les
éléments de POS non couverts par RBC
DEA I3 - Module Génomique
21
Approche à deux niveaux
(3/3)
 Exemple
• BCR : si A1 & A2 & … & An alors POS
• IIC : au moins 3 conditions parmi A1, …, An
doivent être vérifiées
IIC
BCR
DEA I3 - Module Génomique
22
Application à la génomique
 Caractériser des gènes (ou des protéines)
par classes de fonctions
 Caractériser des séquences d’ADN (ou
d’ARN) selon certaines propriétés
DEA I3 - Module Génomique
23
Auteur
Document
Catégorie
Uncategorized
Affichages
4
Taille du fichier
212 KB
Étiquettes
1/--Pages
signaler