Admin CliCours
Approches Bio-inspirées pour la Fouille de Données en Ingénierie de Logiciels
Méthodes bio-inspirées de Fouille de données
Dans ce chapitre, nous allons discuter des méthodes de Data Mining et nous allons aborder, plus précisément, des techniques auxquelles nous nous intéressons et qui trouvent leur racines dans la biologie, tels que les réseaux de neurones ainsi que les systèmes immunitaires artificiels (Artificial Immune System AIS). Le premier groupe s’inspire des cellules qui forment un réseau à l’intérieur du cerveau humain, et lui donnent la capacité d’analyser et d’évoluer dans son environnement, ainsi que la mémoire pour se rappeler des expériences passées pour apprendre et se développer. Les systèmes immunitaires artificiels encapsulent les agents cellulaires responsables de la protection des humains de leurs environnements remplis de bactéries et de virus, et par conséquent, leur permettre de se prévenir des maladies. Le monde de l’information, d’internet et des échanges considérables de données électroniques, voilà le résumé du 21ème siècle… une multitude de bases de données prêtes à être utilisées à des fins commerciales ou d’ingénierie, extraites de plusieurs domaines de la vie quotidienne : transactions de vente, Trading, descriptions de produits, expériences scientifiques, observations techniques et surveillance de l’environnement, sans oublier les réseaux sociaux [HAN 12]. Dans le dessein d’exploiter ces données et trouver une information utile (knowledge) ou un pattern sous-jacent, nous avons besoin d’outils d’analyse puissants afin de minimiser les erreurs, ainsi que la perte considérable de temps et de ressources. Ces outils appartiennent à la famille de méthodes de fouille de données (Data Mining) [WAN 03- HAN 12-HAN 15- TAN 16] qui pourrait être définie comme suit : « Data Mining (DM): Un ensemble de méthodes et outils servant à découvrir des modèles et des connaissances pertinentes à partir de grandes quantités de données. Ces données sont généralement encapsulées en bases de données, entrepôts de données (data Warehouse), Web et d’autres référentiels d’informations… [HAN12].» Les méthodes d’exploration de données peuvent être divisées en deux groupes distincts (Figure 1.1) : Les méthodes descriptives, et les techniques prédictives. Ces dernières réalisent une induction sur les données étudiées afin de faire des prédictions, comme classer les personnes susceptibles d’avoir la grippe selon leur lieu de résidence. Alors que les méthodes descriptives se centrent sur la découverte des relations et les patterns qui peuvent relier les instances d’une base de données étudiée, exposant ainsi ses propriétés [WAN 03]. 19 Figure 1.1-Taxonomie des méthodes de fouille des donnés La méthode la plus populaire dans l’exploration de données est la classification, où le but est de trouver un modèle ou une fonction permettant la distinction (ou discrimination) d’un ou plusieurs concepts appelés classes, se trouvant dans les données, cela à partir d’un ensemble d’apprentissage (dans lequel l’étiquette de la classe est connue) afin de prédire la classe des instances inconnues (ou ensemble de test) [BIS 06-HAN 12-TAN 16]. Le modèle construit peut se présenter sous plusieurs formes, telles qu’un ensemble de règle If-Then, une formule mathématique, un arbre de décision ou un réseau de neurones [HAN 12]. Ces représentations sont les résultats d’un groupe particulier d’algorithmes, nommées techniques d’apprentissage automatique (Machine Learning). 1.2 Apprentissage automatique (Machine Learning) Un algorithme est une suite finie d’opérations ordonnées devant être suivies pour résoudre un problème donné [KLE 06]. Le rôle d’un ingénieur en informatique est de trouver l’algorithme adéquat pour accomplir une certaine tâche telle que le tri, la recherche ou la cryptographie… Il s’avère parfois difficile, ou même impossible, de trouver une solution algorithmique à notre problème. C’est le cas, par exemple pour la reconnaissance des visages, la détection de cellules cancéreuses ou la reconnaissance de l’écriture manuscrite, par contre, nous avons assez de données qui résultent d’enregistrements passés, tels que des images médicales ou des photos familiales, qui peuvent nous donner une issue approximative à notre problème. De ce fait, nous aurons besoin d’algorithmes capable d’extraire des connaissances pertinentes à partir de ces données brutes, ces algorithmes sont le résultat du mariage entre l’intelligence artificielle (IA) et le Data mining (DM) qui sont les méthodes d’apprentissage automatique (Machine learning) [ALP 14] (Figure 1.2). Apprendre à partir de l’expérience passée, représentée sous forme de base de données est le rôle des méthodes d’apprentissage automatique, qui donnent ainsi aux machines la capacité d’apprendre et d’évoluer, au fil du temps, dans leur environnement [COR 11-ALP 14-SHA 14]. Concrètement, un ensemble S de données, appelé ensemble d’entrainement (ou d’apprentissage) est présenté à l’algorithme d’apprentissage, ce qui va permettre à la méthode d’extraire, par inférence, une connaissance sous forme de modèle. Cce modèle est une fonction, qui va prédire la classe inconnue des instances non étiquetées constituant ensemble de test ; c’est ce que nous appelons une généralisation [BIS 06-COR 11]. En outre, si le résultat de la généralisation est un ensemble discret de cas, comme la reconnaissance des lettres de l’alphabet, il s’agit de classification. D’un autre côté, si les sorties sont une ou plusieurs variables continues, comme la prédiction du nombre de jours pour la construction d’un immeuble, là nous nous intéressons à la régression [BIS 06-SHA 14]. Figure 1.3-Exemple d’un résultat d’une méthode d’apprentissage Exemple : « Dans le but d’évaluer le risque qu’un judoka1 subisse une blessure lors d’une compétition, une méthode d’apprentissage artificiel a été appliquée sur une base 1 Le judo est un art martial japonais crée par Jigorō Kanō en 1882, appelé aussi la voie de la souplesse, c’est le sport favori de l’auteur de la thèse 21 d’apprentissage, où ses instances sont représenté par leur âge ainsi que leurs poids, séparé en deux classe, la première étiquette (non blessé) informe que le judoka n’a jamais été blessé, alors que la deuxième, indique que le sportif a été déjà blessé dans sa carrière. Le modèle appris par l’algorithme est illustré par la Figure 1.3, où la connaissance extraite à partir des donnés, nous renseigner que : « plus le judoka est âgé, plus il a de risque de se blesser ». Le nombre de domaines qui requièrent l’aide des méthodes d’apprentissage est presque illimité, par conséquent, il existe différentes approches d’apprentissage artificiel pour s’adapter au mieux au problème étudié. En effet, l’implémentation d’une technique d’apprentissage automatique peut être effectué selon l’un des trois paradigmes suivants (Figure 1.4) [BIS 06 –COR 11-ALP 14]: L’apprentissage supervisé (Supervised Learning) : Dans ce paradigme, les exemples d’apprentissage sont étiquetés afin d’identifier la classe à laquelle ils appartiennent. Le but de l’algorithme est de classifier correctement les nouveaux exemples dans les classes définies dans la phase d’apprentissage. Comme l’illustre notre exemple précédent (Figure 1.3). L’apprentissage non supervisé (Unsupervised Learning ou clustering) : le principe est de diviser un groupe hétérogène de données, en sous-groupes de manière que les données considérées comme les plus similaires soient associées au sein d’un groupe homogène appelé cluster, par contre les données considérées comme différentes se retrouvent dans d’autres clusters distincts, sans intervention d’un superviseur. Ce paradigme est généralement utilisé pour la détection des anomalies (une instance qui n’appartient à aucun des clusters construit par l’algorithme). L’apprentissage par renforcement (Reinforcement Learning) : ce mode d’apprentissage suit un processus stochastique pour trouver la séquence d’actions appropriées à effectuer pour que l’agent apprenant change d’état. Contrairement à l’apprentissage supervisé, l’apprenant ne reçoit pas d’exemples de sorties optimales, mais doit plutôt découvrir, par un processus d’essais/erreurs, le meilleur schéma à suivre pour accomplir une tache donné, tout en maximisant les récompenses fournies par le superviseur. Un robot qui cherche à trouver sa sortie d’une chambre, à chaque pas au hasard (une action) le robot change d’état, s’il est proche de la sortie par rapport à l’état précédent, il reçoit une récompense jusqu’à trouver le bon chemin à suivre pour quitter la pièce (maximiser le nombre de récompenses). L’inspiration humaine trouve souvent son origine dans la nature et les interactions biologiques, c’est notamment le cas pour l’informatique et, plus précisément, l’apprentissage automatique. L’outil principale qui permet à l’humain d’apprendre et mémoriser n’étant autre que le cerveau, l’humain va chercher à faire reproduire les mécanismes d’apprentissage et de mémorisation par les ordinateurs, d’où la naissance des réseaux de neurones artificiels que nous allons aborder dans la section 1.3. Un autre phénomène intéressant dans le corps humain est la capacité de se protéger des maladies et de prospérer dans son environnement, parfois dangereux. Le système immunitaire est responsable de cette protection et constitue, depuis plusieurs années, une nouvelle source d’inspiration passionnante pour les chercheurs en apprentissage automatique. Ceci a donné naissance aux Systèmes Immunitaires Artificiel 22 (AIS) qui représentent le centre d’intérêt de notre thèse, et que nous allons essayer de présenter dans la section 1.4.
Les réseaux de neurones artificiels
Le cerveau humain est une incroyable machine constituée de plusieurs milliards de neurones interconnectés (Figure 1.5), lui donnant la capacité d’apprendre, reconnaitre et s’adapter à son environnement. Ainsi, c’est devenu une grande source d’inspiration pour les chercheurs en IA, qui veulent implémenter et automatiser ces tâches quotidiennes. Une tâche telle que la reconnaissance d’un nombre écrit à la main est presque intuitive pour l’homme. Par contre, écrire un algorithme spécifique pour doter l’ordinateur d’une telle fonctionnalité est presque impossible, car l’humain lui-même est incapable de décrire comment il arrive à traiter et mémoriser les informations qui lui parviennent, même s’il connait l’entité responsable de ce processus [NIE 15]. Même s’il est admis qu’un neurone est moins rapide et plus simple qu’un processeur, la puissance du cerveau lui vient de son inter-connectivité qui lie un très large ensemble de neurones au niveau des synapses [ALP 14]. Ainsi, le cerveau est capable de traiter l’information d’une façon parallèle et distribuer la mémoire d’une manière passive dans tout le Machine Learning Supervisé Machine à vecteurs de support (SVM) Réseau de neurones Arbre de décision Système immunitaire artificiel Non supervisé Héarchique single-link Ward Partitionnelle K-moyenne X-moyenne Renforcement Monte Carlo Q-learning 23 réseau neuronal. D’une manière plus simple, le noyau est considéré comme responsable des tâches dites intelligentes, alors que la mémoire se trouve dans les synapses qui lient les neurones au niveau des dendrites et des axones [COR 11-NIE 15]. Figure 1.5 Les composants d’un neurone biologique [1] Au début des années 60, ces éléments ont donné naissance aux méthodes les plus populaires da l’apprentissage automatique qui est les réseaux de neurones atrificiels (Artificial neural networks), composé de plusieurs neurones reliés entre eux.
L’algorithme du Perceptron
Le Perceptron (Figure 1.6) est considéré comme le premier modèle d’apprentissage automatique introduit Frank Rosenblatt [ROS 61], c’est la représentation la plus simple d’un réseau de neuronal (ANN) [ KLE 06-NIE 15]. L’algorithme du Perceptron simule le travail d’un seul neurone, il a en amont un ou plusieurs entrées Xi ={x1,x2,x3,….xn} et chacune d’elles est associée à un poids W i ={w1, w2,w3,….wn}. Dans le cas de notre exemple vu dans la section 1.2, x1 représente l’âge et x2 le poids d’un judoka, ajouter à cela la connexion biaisé x0 où l’entrée est toujours initialisée à 0 et son poids w0=1 afin de généraliser l’algorithme et s’éloigner du point d’origine .
INTRODUCTION |
