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.
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.
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.
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].
où xi est la valeur de l'attribut Xi, ui est la valeur moyenne de Xi et yi est la valeur binaire correspondante.
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.
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]x 1 and [not]x 2 . . . then C
Les règles extraites doivent être précises et compréhensibles [4], [6]
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.
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.
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.
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é.
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
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)
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).
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]. 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.
1. Initialement R NM =, R FIN = 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, (i 0) 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 R NM 9. Les nouvelles règles sont insérées dans la classe i+1, 10. i i+1 11. si i< n alors aller à l'étape 5 sinon R FIN = R NM fsi 12. Déterminer quels sont les implicants premiers essentiels à partir de R FIN [14].
Fig.
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.
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<prem, (prem est une valeur définie par l'utilisateur) − Déplacer la règle dans E Sinon, l'algorithme fait des combinaisons des deux meilleurs règles au sens de précision, ce processus continu jusqu'à ce qu'on trouve un ensemble de règles vérifiant le critère précision >=maxaccuracy et NB<prem, cet ensemble de règles est déplacé dans E.
Notre système MC-RULEGEN est testé sur la base de données cancer du sein, nous avons utilisé le modèle PMC avec une seule couche cachée. Les résultats sont comparés avec d'autres approches.
Base de données cancer du sein [15]: Contient 699 exemples répartis sur 02 classes (458 pour bénigne et 241 pour maligne). Chaque exemple est composé de neufs attributs, chacun d'eux prend des valeurs entre 1 et 10. Les exemples sont utilisés dans l'apprentissage et le test.
Le meilleur résultat est obtenu en utilisant (table 1): 9 neurones dans la couche d'entrée, 03 neurones dans la couche cachée et deux neurones dans la couche de sortie, nous avons utilisé la fonction logistique entre les couches, le momentum = 0.95 et la fréquence d'apprentissage=0.4. Après 500 époques, le taux de classification est égale à 98%. Table 1. Liste des styles définis dans le présent document.
La taille de la population est initialisée à la valeur "popsize", celle du chromosome ( l'individu) est égale "indiv_length", le nombre de gènes (règles) dans le chromosome est égale à "rulesize". Chaque règle contient "sizeinput" attributs. La méthode de la roulette est utilisée dans la selection des individus. La prochaine génération est créee à partir de la population courante en utilisant les opérateurs de croisement (avec une probabilité pCross) et de mutation (avec une probabilité pMut). Les meilleurs chromosomes au sens de fitness survivent et participent à la création de la nouvelle population. La population continue à évoluer vers les meilleurs valeurs de fitness. Après plusieurs générations, l'algorithme converge vers le meilleur chromosome. La figure7 montre l'évolution des valeurs de la fonction fitness des meilleurs individus de chaque génération. La compréhensibilité dans chaque individu est calculée en comptant le nombre des attributs inactifs, si ce nombre augumente alors la compréhensibilité augmente. Nous avons utilisé dans notre travail les valeurs suivante: popsize=30, rulesize=15, sizeinput=9; indiv_length = sizeinput*rulesize; pMut=0.2; pCross=0.8; nombre de génération égale à 10000;
En appliquant la procédure d'optimisation, deux règles sont éliminées.
La table 2 montre les 03 meilleurs règles obtenues pour chaque classe. Pour la classe bénigne, en se basant sur la première règle, uniquement 5 parmi 229 d'exemples de test sont malclassées, si on rajoute à cette règle la deuxième, la précision saute à 100% (voir table 3), les autres règles sont alors omises.
Ce papier présente une nouvelle approche d'extraction de règles à partir d'un réseau de neurones. Notre approche combine les deux approches métaheuristiques (algorithme génétique) et les exactes (Quine Mc-cluskey) au sein d'un même système afin d'extraire les règles binaires de la forme if-then, les règles obtenues sont passées dans un système à base de règles pour raffinage. Les résultats expérimentaux montrent que notre approche MC-RULEGEN génère des règles de très haute performance.