L’intelligence collective des lymphocytes : système immunitaire

Télécharger le fichier pdf d’un mémoire de fin d’études

Intelligence en essaim, auto-organisation et sys-tèmes complexes

L’auto-organisation : concept fondateur de l’intelligence en essaim

Le processus d’auto-organisation est à l’origine de ce que l’on dénomme l’in-telligence collective. L’intelligence collective possède des capacités cognitives col-lectives évoluées qui émergent de capacités cognitives individuelles limitées. Le concept d’auto-organisation est essentiel pour comprendre ces phénomènes Her-mann Haken [Haken 2008] définit l’auto-organisation par la manière suivante : «L’auto-organisation est la formation spontanée, souvent avec un objectif appa-rent, de structures spatio-temporelles, temporelles, spatiales ou de fonctions dans les systèmes constitués de peu ou de nombreux composants. En physique et biolo-gie, l’auto-organisation apparait dans les systèmes ouverts loin de l’équilibre ther-modynamique».
Dans [Théraulaz 1997], les auteurs donnent la définition suivante de l’auto-organisation : «Auto-organisation est tout processus au cours duquel des structures émergent au niveau collectif (ou plus généralement l’apparition d’une structure à l’échelle N + 1 à partir d’une dynamique définie à l’échelle N), à partir de la multitude des interactions entre individus, sans être codées explicitement au niveau individuel».

Mécanismes de l’auto-organisation biologique

L’intelligence en essaim est un domaine fortement bio-inspiré, ce processus de l’inspiration biologique passe naturellement par la connaissance de l’analyse biolo-gique des mécanismes impliqués dans un phénomène naturel. En biologie animale, les phénomènes d’auto-organisation sont les plus spectaculaires et facilement ob-servables (colonies de fourmis, nuées d’oiseaux, bancs de poissons, etc). Les bio-logistes s’accordent sur la définition de l’auto-organisation [Camazine 2001b] sui-vante : «L’auto-organisation biologique possède des mécanismes qui le justifient : parmi les mécanismes responsables de l’auto-organisation biologique, on retrouve des mécanismes fondamentaux mis en exergue en cybernétique, à savoir les méca-nismes de rétroactions positives et négatives considérées comme des modes d’in-teraction entre entités formant le système biologique [Camazine 2001a].»
La possibilité d’échange d’informations, par le biais de modifications de l’en-vironnement, se nomme la stigmergie [Grassé 1959, Theraulaz 1995]. Elle est un concept né des études de Grassé en 1959 sur la construction de termitières [Grassé 1959]. On peut différencier en fait deux classes principales de stigmergie [Bonabeau 1999a]. La stigmergie qualitative, par exemple : la présence d’un trou dans une surface plane sera comblée pour retrouver la planéité de la surface, la planéité (nouveau stimulus) déclenche à son tour la construction de cellules pour l’élevage des larves
de la colonie. La stigmergie à base de phéromone est considérée comme quantita-tive : elle ne change a priori pas de nature au cours de la stimulation et le compor-tement de la colonie, est gouverné par la concentration de phéromone présente sur l’objet de construction. Ces mécanismes biologiques fondamentaux étant décrits, les principales propriétés des phénomènes biologiques d’auto-organisation sont les suivants [Camazine 2003] :
– La dynamique des processus, dont les éléments constitutifs sont en interac-tion permanente pour maintenir l’auto-organisation du système. Ces proces-sus dynamiques sont de nature non linéaire ;
– Des propriétés nouvelles émergentes, non présentes au sein des parties élé-mentaires et non simplement liées à leurs propriétés élémentaires (formation d’amas chez certaines larves d’insectes par exemple). De plus ces proces-sus peuvent mettre en oeuvre des mécanismes localement simples mais qui produisent à grande échelle des résultats complexes ;
– Présence des paramètres : certains paramètres liés au fonctionnement biolo-gique (la composition chimique d’une phéromone par exemple) et d’autres de nature physique (par exemple la volatilité d’une phéromone, la tempéra-ture, son évaporation) peuvent avoir un fort impact sur les processus d’auto-organisation. Cette dépendance paramétrique renforce aussi le rôle et l’im-portance de l’environnement.
L’auto-organisation se prête bien à l’étude des insectes sociaux qui montrent des comportements collectifs complexes issus de comportements individuels simples. On peut regrouper les processus d’auto-organisation chez les insectes sociaux en quatre groupes tant leur diversité est importante :
– Le recrutement et l’exploitation collective de sources de nourriture : le four-ragement met à jour des stratégies qui permettent aux insectes une grande adaptation à leur milieu ;
– La division du travail et l’organisation des rôles sociaux à l’intérieur d’une même société, on peut observer différentes castes spécialisées dans un certain nombre de taches (élevage du couvain, recherche de nourriture, construction du nid, etc) ;
– L’organisation de l’environnement : la construction du nid est un symbole de l’organisation distribuée des insectes. Le nid est construit sans que les in-sectes soient dirigés, ils répondent à un certain nombre de stimuli provenant de leur environnement ;
– La reconnaissance inter-individuelle : chaque fourmi est capable d’identi-fier ses congénères tout en participant elle même à l’identité de sa colonie (l’échange d’aliments entre les individus d’une même colonie, la trophalaxie, est un exemple d’acte altruiste permettant en plus d’homogénéiser l’identité de la colonie, l’identité coloniale). Les explications du mécanisme de re-connaissance ne sont pas encore parfaitement établies. Cependant, il s’avère qu’il y ait à la fois une composante génétique et une composante acquise par apprentissage. Un réseau de neurones a par exemple été utilisé pour repro-duire ce mécanisme d’apprentissage puis de différenciation entre les compo-
Fourmis réelles comme source d’inspiration 20 sés chimiques, dans le cas des termites [Bagnères 1998].

Auto-organisation en intelligence artificielle

Les premiers champs de l’informatique à avoir exploité les phénomènes d’auto-organisation sont les algorithmes évolutionnaires [Rechenberg 1973], [Beyer 2002], [Holland 1992]. L’intérêt de l’approche informatique tient à son utilisation exten-sive de la notion d’agent qu’elle développe par ailleurs et qui est particulièrement adaptée à l’étude des phénomènes d’auto-organisation. L’auto-organisation est un phénomène décrit dans plusieurs disciplines, notamment en physique [Nicolis 1977], [Prigogine 1971] et en biologie [Camazine 2001a].
Une définition a été proposée par [Camazine 2001a] : «L’auto-organisation caractérise un processus au cours duquel une structure émerge au niveau global uniquement d’un grand nombre d’interactions entre les composants de niveau local du système. De plus, les règles spécifiant les interac-tions entre composants du système sont suivies en utilisant uniquement des infor-mations locales, sans référence a la structure globale.»
Stephanie Forrest utilise la notion d’agent pour définir la computation émer-gente [Forrest 1991] qui est constituée par les éléments suivants :
– Un ensemble d’agents programmés explicitement : un micro-programme lo-cal à l’agent définit son comportement localement (typiquement les auto-mates cellulaires) ;
– Des interactions entre ces agents, réglées par leur propre programme, qui ont pour résultante la formation d’un schéma global (pattern) au niveau macro-scopique ;
– L’interprétation naturelle de ces schémas comme du calcul.
Dans cette définition entrent plusieurs domaines de développement de l’informa-tique : les modèles connexionnistes, les automates cellulaires, les modèles biolo-giques, les systèmes classifieurs, les modèles de vie artificielles, et les modèles de coopération dans les systèmes sociaux sans autorité centralisée. Forrest [Forrest 1991] insiste sur le fait que la computation émergente concerne des processus de calcul non linéaires. La non linéarité est communément considérée comme caractéristique dans le formalisme mathématique de description des systèmes complexes

Les systèmes complexes pour l’intelligence en essaim

L’intelligence en essaim constitue désormais un domaine à part entière de l’in-telligence artificielle distribuée. Les problématiques qu’elle soulève touchent cependant à de nombreux autres domaines scientifiques. En particulier le concept d’essaim trouve pleinement sa place au sein de la science dites des «systèmes com-plexes».
Plusieurs auteurs ont défini les systèmes complexes de façon variable, mais on retrouve systématiquement une définition commune : un système complexe est constitué d’un grand nombre d’entités en interaction mutuelle, et éventuellement en interaction avec un environnement, dont le comportement global émerge de façon non linéaire du niveau local. Pour certains auteurs, la non linéarité est essentielle pour exprimer la complexité même si le nombre d’entités est faible. L’intelligence en essaim vise à fournir une grandeur quantifiable de l’auto-organisation des systèmes. Une science s’est développée autour de cette problé-matique portant le nom de science des systèmes complexes qui a pour objectif de théoriser les phénomènes d’auto-organisation. La question cruciale est donc de comprendre comment les composants d’un système émergent entre eux pour pro-duire une structure complexe. Rodolphe Charrier [Rodolphe 2009] présente ainsi la conception, les caractéristiques et les applications d’un modèle original, le système multi-agent logistique (SMAL), pour le domaine de l’intelligence en essaim. Le SMAL trouve son origine en modélisation des systèmes complexes : il est en effet issu des réseaux d’itérations logistiques couplées qui est adapté dans le modèle de calcul au schéma «influence-réaction» des systèmes multi-agents.
Nino Boccara dans la préface de son ouvrage dédié aux systèmes complexes [Boccara 2004] propose la définition à base d’agents suivante : «Bien qu’il n’existe pas de définition universellement acceptée pour définir un système complexe, la plupart des chercheurs décrirait comme complexe un système d’agents liés les uns aux autres qui exhibent un comportement global émergent non pas imposé par un contrôleur central, mais résultant des interactions entre les agents. Ces agents peuvent être des insectes, des oiseaux, des personnes, ou des entreprises, et leur nombre peut varier d’une centaine à un million».
Les systèmes complexes présentent des types de comportement qui sont dans une large mesure indépendante de la nature de l’élément individuel, on peut citer par exemple :
– Les étoiles dans une galaxie,
– Les composantes d’une atmosphère planétaire,
– Les habitants d’une ville,
– Les voitures dans un embouteillage de la circulation,
– Les insectes sociaux dans une colonie,
– Les courants dans un liquide en mouvement,
– Les cellules dans un organisme multicellulaire,
Fourmis réelles comme source d’inspiration 22
– Les gènes dans un réseau,
– Les groupes de molécules dans un milieu réactif,
– Les atomes magnétiques dans un verre de spin.

Champs de l’intelligence en essaim

L’intelligence collective des lymphocytes : système immu-nitaire

Le système immunitaire est responsable de la protection de l’organisme contre les «agressions» d’organismes extérieurs. La réponse immunitaire est basée sur le principe de la sélection clonale, appelé aussi, théorie du choix clonal [De Castro 2000a]. L’immunologie a pour objet, l’étude du système immunitaire. Ce système, composé d’organes, de cellules et de molécules, assure le maintien de l’intégrité de l’organisme qu’il défend. Ainsi, il peut être défini comme étant, l’ensemble des mécanismes biologiques permettant à l’organisme de reconnaître et de tolérer ce qui lui appartient en propre (le soi), et de reconnaître et de rejeter ce qui lui est étranger (le non soi) : les substances étrangères ou les agents infec-tieux auxquels il est exposé, mais aussi, ses propres constituants altérés (comme les cellules tumorales). Ce mécanisme de reconnaissance intelligent a été modélisé pour donner naissance au système immunitaire artificiel AIS (Artificial Immune System) [Timmis 2000] et [Timmis 2001].
Ces systèmes disposent de propriétés complexes car ils sont capables de géné-rer des solutions et de les sélectionner en fonction de leur efficacité selon des heu-ristiques originales [Azzag 2000]. Une description des fondements théoriques et de nombreuses applications des systèmes immunitaires artificiels peut être trouvée dans [De Castro 1999], [Dasgupta 1997] et [Dasgupta 1999]. Le principe des sys-tèmes immunitaires est appliqué au problème de classification [De Castro 2000b]. D’autres modèles plus complexes existent. Ainsi dans [Timmis 2002] le système utilise plusieurs niveaux de cellules et d’interaction (anticorps, lymphocytes, cel-lules de mémorisation). Dans [Nasaroui 2002], ce même système est généralisé et amélioré en utilisant des fonctions d’appartenance floue plutôt qu’une distance euclidienne et un seuil.

L’intelligence artificielle distribuée et systèmes multi-agents

Le principe de l’intelligence collective de plusieurs entités simples en inter-action desquelles émerge à un niveau collectif une structure complexe (qualifiée d’intelligente) est présent dans différentes disciplines : biologie, physique, infor-matique, etc. Dans ces domaines, différents modèles ont vu le jour pour décrire et analyser de tels systèmes. En informatique, les systèmes multi-agents réactifs (b) Le robot Sahabot développé par Lambrinos et al. [Lambrinos 2000] pour tester les hypothèses sur la navigation de la fourmi Cataglyphis. (c) William Gray Walter et son robot ELSIE rentrant à son poste de rechargement [Holland 1992]. (d) Le robot Insbot développé dans le cadre du projet européen Leurre pour interagir avec un groupe de blatte Periplaneta americana [Halloy 2007].
offrent un cadre conceptuel permettant la représentation et la simulation de tels systèmes. Une manière de concevoir de tels systèmes est donc d’effectuer un lien entre comportement individuel et réponse collective est de s’inspirer des phéno-mènes existants en biologie, notamment dans le cadre des sociétés d’insectes. Une telle approche fournit des solutions dont les caractéristiques essentielles sont :
– Dynamique : le système s’organise en fonction de son contexte courant et il est capable de s’adapter continuellement aux variations de celui-ci ;
– Décentralisé : il n’y a pas besoin d’une entité centralisatrice dictant ce que doit faire chaque agent, on s’affranchit des problèmes de goulot d’étrangle-ment, de construction et maintenance d’une représentation globale ainsi que des problèmes de dysfonctionnement de cette entité centralisatrice ;
– Simple : le modèle individuel est relativement simple et nécessite des efforts de conception moindre.
Dans le cadre de l’organisation de système multi-agents, envisager un collec-tif pose alors le problème d’organiser les différentes activités des agents afin que globalement ce collectif se comporte comme un tout cohérent et réponde aux exi-gences qui lui sont fixées en fonction des capacités propres à chacun, des caracté-ristiques changeantes de leur environnement, etc. Ce problème d’organisation fait l’objet de nombreuses études dans le cadre des systèmes multi-agents.
– Pour les agents cognitifs ceux-ci sont dotés de moyens de représentation, de raisonnement et de communication élaborés. Ils peuvent ainsi représenter la tâche à résoudre, les compétences des autres, raisonner sur les conséquences de leurs actions et interagir de manière élaborée avec les autres ;
– Dans le cas réactif les agents n’ont pas ou peu de représentation des autres, ils possèdent des mécanismes de décision de type stimulus-réponse et inter-agissent via leur environnement avec les autres. Ils ne disposent que d’infor-mations locales. Dans ce second cas, les agents ne peuvent être réellement qualifiés d’intelligents individuellement mais la société qu’ils forment peut l’être. On parle alors de systèmes multi-agents réactifs ou d’intelligence en essaim.

Propriétés biologiques des fourmis réelles et ap-plication en informatique

Les différentes problématiques posées par les systèmes biologiques sont une source importante d’inspiration pour la conception des systèmes artificiels. Millo-nas [Millonas 1993] a tiré de la métaphore fourmi une proposition de caractérisa-tion en cinq principes des systèmes d’intelligence en essaim.
– Principe de proximité : ce premier principe pose la nécessité d’une capacité des entités du groupe à répondre dans une localité spatiale et temporelle aux signaux/stimuli de l’environnement. Cela implique une capacité de calcul lo-cal, calcul dont l’objectif est de décider d’un comportement qui maximiserait au mieux l’utilité pour l’activité du groupe entier (par exemple le fourrage-ment, la construction d’un nid, le déplacement de groupe,…),
– Principe de qualité : le groupe doit pouvoir répondre aussi à des critères de qualité par rapport à l’objectif recherché (qualité de la source de nourriture, de l’emplacement du nid, …). Il s’agit là d’optimiser un critère de qualité pour l’essaim,
– Principe de réponse diversifiée : le groupe doit pouvoir répondre dynami-quement aux éventuels changements de l’environnement, et donc diversifier autant que possible ses modes de fonctionnement,
– Principe de stabilité : ce principe vient compléter et limiter le précédent. Le groupe doit également maintenir une forme de stabilité afin d’éviter de basculer d’un mode de fonctionnement à l’autre au moindre changement de l’environnement, ce qui serait une perte d’énergie considérable,
– Principe d’adaptabilité : le changement de mode de fonctionnement, lorsque le mode courant n’est plus suffisamment satisfaisant, s’opère par adaptation à une nouvelle situation environnementale.

La division du travail

Une caractéristique fondamentale des insectes sociaux est la division du travail. Dans le cadre de la division du travail, la fréquence des interactions entre les indi-vidus dépend de leur âge, de la fonction qu’ils remplissent dans la colonie, et des déplacements associés. Les tâches que doivent accomplir les ouvrières sont en effet multiples :
– La récolte du nourriture,
– L’entretien et défense du nid,
– La construction du nid,
– L’élevage des couvains,
– L’entretien des larves et leur approvisionnement en nourriture.
Les chercheurs ont essayé de relier les comportements des ouvrières à leurs caractéristiques individuelles. Le premier paramètre caractérisant les ouvrières est leur morphologie. La variation de taille peut être continue ou discontinue, donnant alors des castes distinctes. L’âge des ouvrières est un autre facteur important dans la division du travail. Les jeunes ouvrières assurent le soin au couvain au centre du nid, puis remplissent peu à peu des tâches plus périphériques, comme l’entretien du nid et occupent à la fin de leur vie le rôle de fourrageuses. Ces deux facteurs, âge et morphologie, n’expliquent cependant qu’une partie de la division du travail entre les ouvrières. Il a été mis en évidence que certains groupes d’individus se spécia-lisent dynamiquement pour une tâche particulière [Grassé 1939]. Toutes ces acti-vités, dont l’importance est variable dans le temps et l’espace, doivent être assurés simultanément pour la survie et le développement de la colonie. C’est essentielle-ment la plasticité de l’organisation déployée par les fourmis qui nous intéresse.

La communication chez les fourmis

Les insectes sociaux en général, et les fourmis en particulier, ont développé des mécanismes de communication très élaborés (voir [Breed 1998] pour les insectes sociaux et pour les animaux en général [Brossut 1996]). On distingue dans la communication quatre types de signaux selon leur nature : sonore, tactile et chimique. Il a été défini quelques types de réponse mettant en oeuvre une forme de communica-tion [Holldobler 1990] : l’alarme, le recrutement (pour une source de nourriture ou un site de nidification), la reconnaissance des apparentés ou de caste, le marquage du territoire et du nid, et la reproduction (diffiérenciation du sexe, de l’espèce, de la colonie…). On connaît quand deux fourmis se rencontrent, elles communiquent entre elles avec leurs antennes. En fait elles se touchent pour échanger des in-formations sur leur visa chimique. Chez les insectes, la communication chimique est fondamentale. Les phéromones (mélange d’hydrocarbures) sont à la base de la communication de nombreuses espèces. Les différentes applications informa-tiques qui découlent des capacités de communication des fourmis se retrouvent par exemple en optimisation combinatoire où la coopération stigmergétique s’applique parfaitement à la recherche du plus court chemin dans un graphe.
Le déplacement grâce à des repères chimiques est une des originalités com-portementales que l’on retrouve des mammifères (ex : rat [Galef 1996]) aux uni-cellulaires (ex : [Burchard 1982]) en passant par les insectes sociaux (fourmis : [Holldobler 1990], termites : [Grassé 1959]). Ces substances chimiques communé-ment appelées phéromones sont libérées par un animal dans son milieu, et vont af-fecter le comportement ou la physiologie des individus de la même espèce [Karlson 1958, Passera 1958]). Il existe différents types de phéromones. Les phéromones qui conduisent à un déplacement collectif d’individus peuvent être soit des phéromones d’alarmes soit des phéromones de pistes. De nombreux algorithmes sont inspirés du compor-tement de masse des fourmis pour la recherche de nourriture : les phéromones de pistes. Chaque fourmi dépose des phéromones à l’aide de son abdomen pour tracer des pistes et suivre un chemin. Il en résulte un phénomène auto-catalytique. En ef-fet, plus une piste est suivie et plus il y a de phéromones et plus il y a de fourmis. Notons que ces phéromones s’évaporent au cours du temps.
Les travaux de Deneubourg et al. [Deneubourg 1990] montrent que le plus court chemin pour atteindre une source de nourriture finira pas être emprunté par presque toutes les fourmis puisque les phéromones sont déposés plus vite sur ce plus court chemin. La reconnaissance chimique par les phéromones est utilisée dans de nom-breuses situations dans lesquelles les fourmis peuvent être confrontées. Les fourmis peuvent également émettre des phéromones d’alarmes, grâce à des glandes situées près des mandibules. Ce sont des molécules très volatiles qui induisent un compor-tement agressif chez leurs congénères : les ouvrières prennent alors des attitudes menaçantes, et attaquent l’ennemi. Par exemple, lorsqu’une fourmi se sent en dan-ger ou a trouvé une proie vivante trop grosse pour elle, elle rejette un nombre im-portant de phéromones, pour que ses congénaires puissent remarquer le signal de loin. Les autres fourmis s’approchent donc de la proie, mais le taux de phéromones étant trop fort pour elles, elles restent en retrait. Un nombre important de fourmis va donc s’agglutiner à proximité et lorsque que le taux de phéromones devient plus faible (du à l’évaporation), elles attaquent toutes ensemble la proie.

La construction du nid chez les fourmis

L’une des manifestations les plus fascinantes de l’auto-organisation des socié-tés d’insectes est leur capacité à construire collectivement des nids dont l’architec-ture peut également être très complexe. Les insectes organisés en sociétés comme les abeilles, fourmis, guêpes et termites sont capables de construire collectivement des nids d’une remarquable complexité. Ces productions collectives cohérentes ne pourraient exister sans une forme de coordination entre les individus. Guy Therau-laz et al. [Theraulaz 1995], prenant pour exemple la construction collective chez les guêpes, ont développé un modèle numérique permettant de reproduire les dif-férentes phases de construction d’un nid. Dans ce modèle, les insectes sont re-présentés par des agents qui obéissent à des règles simples et n’interagissent pas directement entre eux. Il apparaît dans le cadre de ce modèle, que seuls certains enchaînements de comportements possédant des propriétés spécifiques produisent des architectures cohérentes et que l’ensemble de ces programmes correspond à un répertoire fort restreint de formes. Les architectures obtenues, correspondant à celles produites par les sociétés de guêpes, tendent à démontrer que pour fabriquer un nid collectif, ces insectes n’ont pas besoin de communiquer directement entre eux : ils se coordonnent à travers l’architecture qu’ils construisent.
Dès la fin des années 1950, Pierre-Paul Grassé [Grassé 1939] avait montré que, chez les termites, la régulation de l’activité bâtisseuse ne dépendait pas directement des insectes, mais des constructions elles-mêmes. Il a étudié les différentes étapes de la reconstruction du nid chez les termites et il s’agit là sans doute d’une des premières observations de l’ordre par fluctuations. Ses études l’ont conduit à for-muler la théorie de la stigmergie qui explicite l’intersection animal-travail. Deneu-bourg [Deneubourg 1977] a étudié la construction du nid chez les termites. L’appa-rition des piliers dans une termitière pouvant être expliquée par l’amplification de multiples fluctuations chaotiques : la structure, modèle d’équilibre des forces par sa stabilité, nait de l’amplification de multiples déséquilibres. La construction des nids de guêpes est aussi un modèle d’action collective où les agents répondent plus particulièrement à des stimuli issus de certaines configurations dans la structure [Bonabeau 1999a]. Ainsi les fourmis construisent collectivement des nids dont la taille importante en comparant avec celle des individus et à l’architecture parfois très complexe. Leur capacité à coordonner plusieurs milliers d’individus pour bâtir leurs nids.

Le rassemblement d’objets

Le tri du couvain est l’un des exemples d’intelligence collective qui représente un phénomène de l’auto-organisation [Camazine 2001a], observé chez certaines colonies de fourmis (lasius niger [Depickére 2004], leptothorax [Franks 1992], Phei-dole pallidula ou Messor sancta [Deneubourg 1991]). Ces colonies organisent le couvain en un unique amas de larves, et, notamment chez la fourmi leptothorax uni-fasciatus, ce couvain est constitué d’anneaux concentriques rassemblant des larves de types différents : les plus petites au centre et les plus grosses en périphérie. Il est important de noter que cette structure est utile à la collectivité, en permettant par exemple aux larves matures d’être nourries en priorité [Franks 1992].
Dans la nature, les fourmis offrent un modèle stimulant pour le problème du partionnement. L’exemple du tri collectif du couvain ou de la constitution de cime-tières sont les plus marquants. Certains travaux expérimentaux montrent que cer-taines espèces de fourmis sont capables d’organiser spatialement divers éléments du couvain : les oeufs, les larves et les nymphes [Deneubourg 1990, Franks 1992]. Dans un article de Bonabeau [Bonabeau 1999a] paru dans la revue de vulgarisa-tion scientifique «Pour la Science», l’algorithme du tri du couvain est décrit ainsi : «Chez les fourmis Messor sancta, les ouvrières nettoient les nids en entassant à l’extérieur les cadavres. Dans des nids artificiels reproduits en laboratoire, elles regroupent en quelques heures des corps dispersés de façon aléatoire […]. De la même manière, les ouvrières de l’espèce Leptothorax unifasciatus trient systéma-tiquement les larves et les oeufs. Les petites larves sont regroupées avec les oeufs, les pupes et les prépupes (des stades intermédiaires dans le développement des in-sectes) sont autour, elles-mêmes entourées par les larves les plus grandes». Les fourmis réelles offrent un modèle stimulant pour le problème du partitionnement et de la classification. La constitution de cimetières, le tri collectif du couvain quand il est dérangé, et le rassemblement des oeufs en fonction de leur état de développe-ment, sont les exemples les plus marquants.
Les premiers modèles informatiques sont ceux de [Lumer 1994b]. D’autres tra-vaux ont été proposés [Monmarché 2000b]. L’auteur propose ainsi, avec l’algo-rithme AntClass, de découvrir automatiquement un ensemble de classes dans des données numériques sans en connaître le nombre a priori. La figure 1.4 illustre, à travers quatre images, l’expérience menée par Deneubourg et ses collègues [Deneubourg 1990] qui a consisté à analyser dans un couvain, le comportement des fourmis de l’espèce Messor sancta.

Taxonomie des méthodes de classification ou clustering

L’apprentissage automatique correspond au domaine se consacrant au déve-loppement d’algorithmes permettant à une machine d’apprendre à partir d’un en-semble de données, d’y extraire des concepts et patrons caractérisant ces données. Les algorithmes issus de ce domaine sont maintenant utilisés dans de nombreuses disciplines telles que la bioinformatique, la recherche d’information et le forage de données, etc.
Le processus de classification peut être résumé par le fait de grouper des objets ensemble selon des critères. Quand nous désignons, par exemple, d’un coté les êtres humains et de l’autre les animaux (chez les fourmis ou les abeilles, etc.), nous effectuons une classification, et ceci de manière tout à fait naturelle.
La figure 2.1 présente les différentes variantes que l’on peut trouver parmi les méthodes de classification [Jain 1988] qui peuvent être organisées en fonction de leurs types :
– La classification non exclusive représente les méthodes de classification qui intégrent un objet dans plusieurs classes suivant un degré d’appartenance. Au contraire, la classification exclusive trie les objets de façon à ce qu’ils n’appartiennent qu’à une unique classe ;
– La classification supervisée (classification en anglais) représente les méthodes qui apprennent, à partir d’un échantillon de données déjà classées, à classer des données du même type que l’échantillon. A l’inverse, la classification non supervisée (clustering en anglais) peut passer par une phase d’apprentis-sage, mais le jeu de données utilisé pour cette phase n’est pas déjà classé ;
– La classification hiérarchique permet de construire une séquence de parti-
Classification non supervisée 42
tions imbriquées, c’est à dire qu’une classe a des sous-classes, et que ces sous-classes contiennent elles aussi des sous-classes, ainsi de suite jusqu’à ce qu’un seuil soit atteint. A l’opposé, un partitionnement ne construit qu’une seule partition de données.

Métrique et distance

La classification non supervisée se base sur le calcul d’une distance comme une mesure de similarité. Elle nécessite la résolution de ce problème : il faut définir une mesure de distance qui permet d’évaluer le niveau de similitude entre les objets à classifier. La mesure de distance la plus répandue est la distance euclidienne, mais il est possible d’utiliser d’autres distances.
L’objectif de l’analyse de données par partitionnement est de «séparer» un en-semble E composé de n objets en m partitions.
Les objets d’une même partition ont une forte similitude entre eux, et peu de simili-tude avec les objets des autres partitions. Pour mesurer cette similarité ou dissimila-rité entre objets, une notion de distance, selon la nature des données, est nécessaire. Si ces objets sont exprimés par des variables numériques tel que l’âge, le nombre de sujets, …, des distances telles que la distance Euclidienne, la distance de Manhat-tan, la distance de Chebyshev, la distance de Minkowski, …, sont utilisées de pré-férence. Cependant, pour représenter de simples distances entre variables de même catégorie comme les couleurs, les familles d’animaux, le sexe, …, on se tournera vers la distance de Jaccard ou de Hamming par exemple [Ralambondrainy 1995].

Types de données en classification

En classification, les données peuvent se présenter sous différentes formes :
– Données quantitatives : Elles fournissent une information enrichie et appro-fondie ; elles reposent sur quelques individus ou quelques cas. Elles sont utiles quand on cherche à expliquer le comment et le pourquoi (Exemples : salaires, montants des achats, âge, …) ;
– Données qualitatives (catégorielles) : Elles proviennent le plus souvent d’études de petite taille. Elles se reposent sur l’expérience d’un groupe très restreint d’individus. Citons à ce propos l’exemple du groupe sanguin associé à une personne (O, A, B, AB) ou bien le niveau d’études d’une personne (BAC, BAC+4, ingénieur, docteur). Lorsque ces variables prennent seulement deux modalités on parle alors des variables binaires ;
– Données textuelles : Elles regroupent les textes non codés écrits en langage naturel.

Méthodes non hiérarchiques

La classification non hiérarchique ou partitionnement, aboutit à la décomposi-tion de l’ensemble de tous les individus en m ensembles disjoints ou classes d’équi-valence ; le nombre m de classes est fixé.
Etant donné un ensemble d’objets décrits par un nombre fixe d’attributs, l’objec-tif d’une tâche de classification non supervisée [Gordon 1996], [Kaufman L. 1990] consiste à proposer une partition des objets en k sous-ensembles où le paramètre k est le nombre de regroupements attendus par l’utilisateur.
Une variation de cette tâche est de ne pas utiliser le nombre attendu de re-groupements comme une donnée du problème. Dans ce cas, l’algorithme construit plusieurs partitions candidates et choisit la meilleure. Dans le cas du clustering par partition, plusieurs méthodes se distinguent fortement [Candillier 2006] :
– Le clustering statistique est basé sur l’hypothèse que les données ont été gé-nérées en suivant une certaine loi de distribution, le but étant alors de trouver les paramètres de cette distribution, ainsi que les paramètres cachés détermi-nant l’appartenance des objets aux différentes composantes de cette loi ;
– Le clustering basé sur les K-moyennes est une méthode très souvent utili-sée, que l’on détaille ensuite ;
– Le clustering stochastique consiste à parcourir l’espace des partitions pos-sibles selon certaines heuristiques, et à sélectionner celle qui optimise un critère donné ;
Classification non supervisée 44
– Le clustering basé sur la densité a pour but d’identifier dans l’espace les zones de forte densité entourées par des zones de faible densité pour la fonc-tion des clusters ;
– Le clustering basé sur les grilles utilise une grille pour partitionner l’espace de description des objets en différentes cellules, puis identifie les ensembles de cellules denses connectées pour former les clusters ;
– Le clustering basé sur les graphes consiste à former le graphe connectant les objets entre eux et dont la somme des valeurs des arcs, correspond aux distances entre les objets, est minimale, puis à supprimer les arcs de valeurs maximales pour former les clusters ;

Méthode K-Means

Parmi les algorithmes de partitionnement que nous allons développer dans cette section est la méthode des k-Means. Contrairement aux méthodes hiérarchiques largement basées sur les mesures de similarités, les algorithmes de k-Means néces-sitent des mesures de distance pour déterminer la distance qui sépare les individus à classer. Cette méthode est encore appelée algorithme des centres mobiles. Ce type d’algorithme, où la classe est représentée par son centre de gravité, a été étudié par plusieurs auteurs. L’algorithme k-Means mis au point par MacQueen en 1967 [MacQueen 1967] est l’un des algorithmes de clustering les plus connus. Il est basé sur la méthode des centroides (ou centres de gravité).
Ce type d’algorithme, où la classe est représentée par son centre de gravité, a été étudié par plusieurs auteurs, à savoir (Bonner, 1964 [Bonner 1964], Celeux et al., 1989 [Celeux 1989]). Le principe de cette méthode est le suivant :
• Itération 1 : tantque l’inertie intraclasse ne s’est pas stabilisée faire ;
• Itération 2 : générer une nouvelle partition A’ en affectant chaque objet à la classe dont le centre est le plus proche ;
• Itération 3 : calculer les centres de gravité des classes de la nouvelle par-tition A’ ;
• Itération 4 : A ← A’ ;
• Itération 5 : fintanque ;
• Itération 6 : retourner A.
on peut montrer que d’une itération à l’autre (i.e. d’une partition à l’autre), l’inertie intraclasse IW décroit ce qui entraine la convergence de l’algorithme [Jain 1988]. L’algorithme k-Means (figure 2.2) assez simple à utiliser et assez efficace (très ra-pide) de classification non hiérarchique est l’algorithme des centres mobiles. Il se propose de prendre au hasard un centre pour chaque classe au début de l’algorithme, puis de parcourir tous les points et de les affecter à la classe dont il est le plus proche du centre. A chaque itération, les centres des classes sont recalculés, puis on recommence jusqu’à arriver à des classes stables. Il présente quelques in-convénients également : il faut déterminer le nombre de classes que l’on veut au départ, ce qui est assez difficile, et l’algorithme est très dépendant des centres choi-sis au départ (aléatoirement dans la version classique). De plus, il ne détecte bien que les classes de formes sphériques (il donne une mauvaise classification sur les classes ellipsoïdes allongées par exemple, etc.).
Cette figure ci-après illustre le fonctionnement générique de la méthode des K-Means.

Table des matières

Introduction
1 Fourmis réelles comme source d’inspiration 
1.1 Introduction
1.2 La bio-inspiration et l’intelligence en essaim
1.3 Intelligence en essaim, auto-organisation et systèmes complexes
1.3.1 L’auto-organisation : concept fondateur de l’intelligence en essaim
1.3.2 Les systèmes complexes pour l’intelligence en essaim
1.4 Champs de l’intelligence en essaim
1.4.1 L’intelligence collective des lymphocytes : système immunitaire
1.4.2 Robotique en essaim
1.4.3 L’intelligence artificielle distribuée et systèmes multi-agents
1.5 Propriétés biologiques des fourmis réelles et application en informatique
1.5.1 La division du travail
1.5.2 La communication chez les fourmis
1.5.3 La construction du nid chez les fourmis
1.5.4 Le rassemblement d’objets
1.5.5 Auto-assemblage chez les fourmis réelles
1.5.6 La stratégie de prédation
1.5.7 Reconnaissance chimique des fourmis réelles
1.6 Conclusion
2 Classification non supervisée 
2.1 Introduction
2.2 La classification
2.2.1 Contexte de la classification
2.2.2 Définition du problème
2.2.3 Taxonomie des méthodes de classification ou clustering
2.2.4 Métrique et distance
2.2.5 Types de données en classification
2.3 Méthodes non hiérarchiques
2.3.1 Méthode K-Means
2.4 Méthodes hiérarchiques
2.4.1 Classification Hiérarchique Ascendante
2.4.2 Classification Hiérarchique Descendante
2.5 Classification incrémentale et flux de données
2.5.1 L’algorithme BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies)
2.5.2 L’algorithme CURE (Clustering Using REpresentatives) . 51
2.5.3 L’algorithme COBWEB
2.5.4 L’algorithme CluStream
2.5.5 L’algorithme DenStream
2.5.6 L’algorithme D-Stream
2.5.7 L’algorithme ClusTree
2.6 Les méthodes à base de grille
2.6.1 Les cartes auto-organisatrices (Self Organizing Maps) de Kohonen
2.7 Approches biomimétiques pour la classification
2.7.1 Fourmis artificielles
2.7.2 Autres approches biomimétiques : les algorithmes d’optimisation
2.7.3 Les algorithmes de classification automatique par fourmis artificielles
2.8 Méthodes de clusetring basées sur les graphes
2.8.1 Les graphes de voisinage et les méthodes de visualisation des graphes
2.8.2 CHAMELEON
2.8.3 Propagation d’Affinité
2.8.4 NG + CHL : Méthode à deux niveaux basée sur les graphes
2.8.5 Méthodes biomimétiques et les graphes
2.9 Conclusion
3 L’algorithme initial CL-Ant 
3.1 Introduction
3.2 Le principe général de l’algorithme CL-Ant
3.2.1 Fourmis artificielles : principes
3.2.2 Description de l’algorithme
3.3 Expérimentations et résultats
3.3.1 Mesures d’évaluation
3.3.2 Les jeux de données et la mesure de similarité
3.3.3 Résultats
3.4 Visualisation des résultats
3.5 Conclusion
4 Extension de l’algorithme CL-Ant : version incrémentale 
4.1 Introduction
4.2 Rappel des principes généraux de notre modèle de fourmis
4.3 Description de l’algorithme CL-AntInc
4.3.1 Principes
4.3.2 Choix de l’échantillon initial
4.3.3 Les phases de classification
4.4 Etude expérimentale et validation
4.4.1 Jeux de données utilisés
4.4.2 Résultats
4.5 Visualisation
4.6 Conclusion
5 Étude comparative 
5.1 Introduction
5.2 Algorithmes étudiés : comparaison avec des méthodes traditionnelles
5.2.1 Expérimentations
5.2.2 Comparaison avec les méthodes classiques
5.2.3 Temps d’exécution
5.3 Comparaison avec des méthodes de flux
5.3.1 Expérimentations
5.3.2 Étude comparative par les données numériques
5.3.3 Temps d’exécution
5.4 Étude de la Complexité
5.5 Propriétés de l’algorithme
5.6 Conclusion
Conclusion générale 
A Publications scientifiques 
Bibliographie

Télécharger le rapport complet