=Paper=
{{Paper
|id=Vol-547/paper-9
|storemode=property
|title=Elaboration d'un Système hybride Neuro-Génétique Pour le Diagnostic Médical
|pdfUrl=https://ceur-ws.org/Vol-547/11.pdf
|volume=Vol-547
|dblpUrl=https://dblp.org/rec/conf/ciia/YedjourBY09
}}
==Elaboration d'un Système hybride Neuro-Génétique Pour le Diagnostic Médical==
https://ceur-ws.org/Vol-547/11.pdf
Elaboration d'un Système hybride Neuro-Génétique
Pour le Diagnostic Médical
D.Yedjour*, A.Benyettou, H.Yedjour
Université des sciences et de la Technologie d'Oran
Faculté des sciences
Département d'Informatique
Email: dyedjour@yahoo.fr
Résumé: Les réseaux de neurones artificiels sont toujours considérés comme des boites noires, qui permettent après un
apprentissage à partir d’une base d’exemples incomplète, de classifier de nouveaux exemples, mais sans donner aucune
explication sur les résultats. Leurs connaissances sont codées de manière interne par les poids synaptiques, et ne sont pas
donc exprimées de manière compréhensible. Les algorithmes génétiques très performants dans les problèmes
d’exploration semblent être en mesure de rechercher dans l’espace des ensembles de règles, celui qui représentera le
mieux les connaissances d’un RNA. En revanche, ils sont inefficaces lorsqu'il s'agit de trouver la valeur exacte de
l'optimum dans cet espace or, c'est précisément ce que les algorithmes exacts d'optimisation réalisent le mieux. Nous
présentons dans cet article une nouvelle approche d'extraction de règles à partir d'un réseau de neurones permettant de
combiner les deux méthodes métaheuristiques et exactes au sein d'un même système.
Mots-clés: Réseaux de neurones, Algorithme génétique, Extraction de règles, Méthode de Quine Mc-Cluskey
1. Introduction
Les réseaux de neurones sont devenus un outil de plus en plus utilisé (industrie, parole, diagnostic médicale, finance,
traitement de signal et dans beaucoup d'autres problèmes), grâce à leur capacité d'apprendre et de généraliser, De plus ils
sont peu sensibles aux données approximatives et à la présence de données incorrectes dans la base d’exemple utilisée lors
de leur apprentissage. En revanche, les connaissances acquises lors de l’apprentissage sont stockées par le RNA dans sa
topologie et les poids de ses connexions, ce qui empêche toute justification des réponses du réseau. Nous pouvons dire que
le réseau est une sorte de « boite noire » [10]. Cependant l'extraction de règles pertinentes demeure importante si les
résultats du réseau de neurones sont utilisés comme théorie initiale dans des problèmes similaires [2]. Un system combinant
le modèle connexionniste et le raisonnement symbolique est dit système hybride intelligent [5]. Il existe deux approches
dans l’explicitation des connaissances d’un RNA. l’approche décompositionnelle qui tente d’analyser la topologie et les
poids des connexions d’un réseau afin d’en déduire des règles, on cite comme exemple RuleNet[9], RULEX[1], Subset [3],
Full–RE [12] , et l'approche pédagogique qui consiste non plus à s’intéresser aux unités d’un réseau, mais simplement à
analyser ses réponses par rapport aux entrées, on peut citer quelques travaux qui ont utilisé cette approche VIA(Validity
Internal analysis)[13], GEX(crisp Rule EXtraction) and REX (fuzzy Rule EXtraction) [6]. MulGEX [7], CGA[8], BIO-RE
(Binary Input-Output Rule Extraction) [12]. Dans cet article, on décrit une nouvelle méthode qui combine les algorithmes
métaheuristiques (algorithmes génétiques) avec les méthodes exactes (Quine-Mc-cluskey) afin d'extraire à partir d'un
réseau de neurones, les règles binaires de la forme if-then. Les algorithmes génétiques très performants dans les problèmes
d’exploration semblent être en mesure de rechercher dans l’espace des ensembles de règles, celui qui représentera le mieux
les connaissances d’un RNA. En revanche, ils sont inefficaces lorsqu'il s'agit de trouver la valeur exacte de l'optimum dans
cet espace. Or, c'est précisément ce que les algorithmes exacts d'optimisation réalisent le mieux. Il est donc naturel de
penser à associer un algorithme exact à l'algorithme génétique de façon à trouver la valeur exacte de l'optimum. On peut
aisément le faire en appliquant à la fin de l'algorithme génétique un algorithme exact sur le meilleur élément trouvé. Notre
système est testé sur la base de données cancer du sein de l'université de Californie. Les expériences montrent que notre
système donne de bons résultats.
2. SYSTEME MC-RULEGEN
La figure1 présente l’architecture de notre système MC-RULEGEN, il est décomposé en 04 modules: le module
perceptron multicouches, le module génétique, le module simplification de règles, et enfin le module system à base de
règles.
2.1. Module Apprentissage du réseau de neurones
Les données doivent être dans un format binaire, sinon une procédure de binarisation (1) sera appliqué sur les données
non-binaires [12].
1
1 si xi ≥ ui
yi = (1)
0 sin on
où xi est la valeur de l'attribut Xi, ui est la valeur moyenne de Xi et yi est la valeur binaire correspondante.
Règles finales
System
à base de règles
Règles
Initiales
Règles
Simplifiées
Module Module Règles
PMC Génétique Module
extraites Optimisation
règles
Extraction de règles via le module génétique
Exemples
D'apprentissage
Fig. 1 - Architecture du système MC-RULEGEN
Le PMC est appris à partir d'une base d'exemple, chaque vecteur d'entrée, est associe à un vecteur de sortie
(apprentissage supervisé), nous avons utilisé l'algorithme de la rétro-propagation. L'apprentissage sert à determiner les
valeurs optimales des poids (la matrice des poids), les connaissances du réseau sont contenues dans cette matrice. La phase
de l'apprentissage nécessite la manipulation de plusieurs paramètres (momentum, fonction d'activation, fréquence
d'apprentissage,..) afin d'aboutir au résultat voulu.
2.2. Module génétique
Les connaissances du réseau de neurones sont difficilement interprétables par un être humain. Pour remédier à cela, il
convient d’expliciter ces connaissances, c’est-à-dire les traduire sous une forme intelligible, une approche pédagogique
basé sur les algorithmes génétiques est utilisée. La règle extraite doit avoir la forme suivante
if [not]x1 and [not]x2 . . . then C
[.] est facultatif
Mesure de qualités des règles extraites
Les règles extraites doivent être précises et compréhensibles [4], [6]. La précision (2) mesure la proportion des
exemples correctement classés par la règle parmi tous les exemples d'apprentissage
nombre des exemples correcteme nt classés
p récision = (2)
nombre total des exemples
La fidélité se calcule de la manière suivante: chaque individu est passé dans le réseau de neurone pour classification, le
pourcentage des bonnes réponses est la valeur de la fidélité associé à l'individu. La compréhensibilité calcule le nombre de
règles ainsi que le nombre de prémisses dans chaque règle. Enfin la généralisation est définit par (3)
nombre de règles
Generalisa tion = 1 − (3)
nombre des exemples
Algorithme génétique pour l'extraction de règles
Les algorithmes génétiques (AG) sont des algorithmes d'optimisation s'appuyant sur des techniques dérivées de la
génétique et de l'évolution naturelle. ils utilisent la selection, le croisement et la mutation.
Algorithme
Générer aléatoirement une population initiale P(0),
Calculer la fonction fitness fi(m) pour chaque individu m de la population P(t),
Définir des probabilités de selection pour chaque individu m dans P(t),
Générer la nouvelle population P(t+1) en appliquant les opérateurs génétiques de croisement et de mutation,
Repéter l'étape 2 jusqu'à ce que le résultat final est le meilleur individu généré durant la recherche ou bien si
le nombre maximal de générations soit atteint.
2
Dans cet article, l'approche génétique est utilisée pour générer les règles symboliques interprétant le résultat du réseau
de neurones, c'est pourquoi ces règles doivent être représentées sous forme de chromosomes.
La forme du choromosomes
Le chromosome est composé d'un ensemble de gènes, chaque gène correspond à une règle, cela dit que le chromosome
code un ensemble de règles (figure2)
R1 R2 R3 R4 R5
1(-1)010 00010 10011 10110 1110(-1) Prémisses
Class0 Class1 Class1 Class0 Class0 Conclusions
Fig. 2 - Forme du chromosome dans MC-RULEGEN
-1 veux dure que l'attribut n'est pas activé.
0 veux dire que l'attribut x s'ecrit not (x) dans la règle générée
1 veux dire que l'attribut x s'ecrit (x) dans la règle générée
on suppose que les attributs se lisent de la gauche vers la droite alors le dernier gène devient :
if x1 and x2 and x3 and not(x4) then class0 , x1, x2 et x3 sont dits attributs positifs et x4 un attribut négatif, x5 un attribut
inactif
Population initiale
La population initiale de règles est choisie à partir de la table de vérité, qui doit contenir toutes les combinaisons
possibles de valeurs d'entrées (attributs), les valeurs de sorties sont générées aléatoirement.
Fonction fitness "mesure de performance"
La fonction fitness permet d'évaluer les individus (chromosomes), et donc de déterminer la qualité de la solution. Les
meilleurs individus sont mutés et croisés pour produire une nouvelle génération. Dans cet article deux mesures de fitness
sont utilisées: la fidélité et la compréhensibilité.
Opérateurs génétiques
Les trois opérateurs de base utilisés dans les AG sont: la selection, le croisement et la mutation. La méthode de la
selection utilisée est celle de la roulette (roulette wheel selection).
Croisement: permet de combiner deux chromosomes (parents) afin de produire un nouveau chromosome
(offspring). La figure 3 explique le croisement ( | est le point de croisement):
Chromosome 1 11011 | 00100110110
Chromosome 2 11011 | 11000011110
Offspring 1 11011 | 11000011110
Offspring 2 11011 | 00100110110
Fig. 3 - Exemple du croisement
Mutation: le rôle de la mutation est d’apporter «du nouveau» dans les chromosomes manipulées afin que la
recherche ne soit pas cloisonnée dans une partie de l’espace exploré. La mutation consiste juste à choisir
aléatoirement un caractère d’une chaîne et à le modifier. Dans notre travail, la mutation peut basculer de la valeur 1 à
0/(-1) ou de 0 à 1/(-1) ou -1 à 0/1. (voir figure 4)
1 0 1 1 -1
⇓
1 0 -1 1 -1
Fig. 4 - Exemple de la mutation
Evaluation de règles
C’est au cours de l’évaluation des règles que vont se réaliser les interactions entre le module génétique et le RNA. nous
avons modifié l'algorithme de la rétropropagation (developed by Rumelhart hinton, wiliams [11]), de telle sorte que les
attributs inactifs (valeur=-1) soient omis lors du calcul (voir figure5).
3
x1 x2 x3 x4 x5
1 0 -1 1 -1 Chromosome
⇓
Couche Sortie
Couche Cachée
1 2 3 4 5 Couche d'entrée
Fig. 5 - Algorithme de la rétropropagation modifié
2.3. Module d'optimisation de règles
L'ensemble de règles générée par AG (supposé optimal) est exprimé sous forme de chaînes de "un", de "zéro" ou de
"-1". On applique l'algorithme de Quine-McCluskey sur cet ensemble afin d'arriver à la solution exacte et simplifiée. La
méthode de Quine consiste, en partant de la décomposition canonique disjonctive de f, à utiliser systématiquement la
formule de simplification x + ¯ x = 1 plusieurs fois jusqu'à ce que aucune paire de termes ne peut être combinées [14].
Considérrons l’exemple suivant :
f(a, b, c) = a.b + b.c + a.c
La décomposition canonique disjonctive de f est :
f(a, b, c, d) = a.b.c + a.b.c + a.b.c + abc + abc +a b c
Algorithme de Quine modifié:
La méthode de quine MC-Cluskey permet de simplifier une fonction en partant de sa forme canonique, nous avons
modifié l'algorithme pour qu'il commence avec n'importe quels termes, cela permet de réduire la complexité de
l'algorithme.
Comment utiliser l'algorithme de Quine McCluskey dans notre approche:
1. Initialement RNM =, RFIN=
2. Regrouper les règles générées par le module génétique dans des classes,
chaque classe englobe tous les règles ayant le même nombre des attributs inactifs
(valeur=-1),
3. Numéroter chaque classe, ex: class0 contient les règles avec zéro (0)
attribut négatif, class1 contient les règles avec un seul (1) attribut négatif,
etc … (si le nombre des sous classes de la classe0=n nbre maximum de classes
(nbrclass)=n)
4. Trier chaque classe suivant le nombre des attributs positifs (valeur=1),
construire alors des sous classes, chacune d'elles contient les règles ayant le
même nombre de 1, deux sous classes de la classe i sont dites adjacentes si la
première contient m attributs positifs et la 2ème contient m+1 attributs positifs,
5. Commencer par la classe0, (i0)
6. Apparier les sous classes adjacentes de la classei deux à deux, appliquer la
règle x + ¯x (voir figure 6) ,
7. Les règles qui ont participé à la génération des nouvelles règles sont
marquées,
8. Les règles non marquées sont insérées dans RNM
9. Les nouvelles règles sont insérées dans la classe i+1,
10. ii+1
11. si i< n alors aller à l'étape 5 sinon RFIN= RNM fsi
12. Déterminer quels sont les implicants premiers essentiels à partir de RFIN
[14].
4
1 0 -1 1 -1 Règles
R1
du
R2 0 0 -1 1 -1 module
Règles
Ropt -1 0 -1 1 -1
Simplifiées
Fig. 6 - Exemple d'application de Quine Mc-cluskey sur les Règles extraites
Dans cet exemple les règles R1 et R2 sont extraites par le module génétique alors que Ropt est obtenu en appliquant
l'algorithme de Quine sur les deux règles
2.4. Système à base de règles
Les règles obtenues à partir des deux modules précédents (génétique et simplification) sont utilisées par le module
"système à base règle" dans le but d'obtenir un ensemble final et réduit de règles pertinentes qui couvre le maximum des
exemples de test.
Méthodologie:
On suppose que E= l'ensemble de règles finale, initialement E=,
pour chaque règle, la précision est calculée en comptant le nombre des exemples correctement classés par
cette règle,
les règles sont triées dans l'ordre décroissant, selon leurs valeurs de précision,
choisir les règles dont la précision est supérieur à la valeur maxaccuracy définie par l'utilisateur,
si cette règle existe alors:
− calculer NB le nombre de prémisses dans chaque règle de l'étape 3,
− Choisir uniquement les règles dont la valeur NB=maxaccuracy et NB