Sommaire
C'est quoi un graphe, M. Euler ?
Le concept mapping est une méthode qui a émergé des travaux de plusieurs universités dans le monde. Il serait vain de toutes les citer. L'Allemagne, l'Australie, la Nouvelle Zélande, les États-Unis, la France...En fait, il s'agit d'une représentation sémantique issue des vestiges de l'Intelligence Artificielle. L'idée est qu'un concept, une connaissance, et par extension toute manifestation de l'activité intellectuelle peut être représentée par un élément linguistique plus ou moins complexe. La particularité du concept-mapping (ou cartographie de concepts en français) est d'utiliser un ordonnancement en graphe mathématique : tout concept est en relation partielle ou totale avec des concepts voisins, sans forcément d'idée d'ordre. On met ainsi en lumière les liens qui existent d'un concept à l'autre, et on cherche à caractériser ces liens, soit de manière chiffrée (graphe pondéré), soit de manière sémantique ("Topic Map"). Une fois le graphe créé, on peut alors utiliser un traitement mathématique s'appuyant sur la théorie des graphes d'Euler, "Reinhardt" de son petit nom...La théorie des graphes est issue d'une question que se posait le savant dans la ville de Koenigsberg, en Allemagne : Il y a là-bas un fleuve qui la traverse avec des îles, un peu comme à Paris l'île Notre-Dame. Un réseau de ponts permet de passer d'une berge à l'autre, d'une île à l'autre. Y a-t-il une manière de circuler entre les ponts, en ne franchissant chaque pont qu'une seule fois, et en parcourant ainsi tous les ponts ?
Euler vint à inventer un langage formalisé pour représenter les îles et les ponts, et à utiliser ce langage pour compter et décrire les caractéristiques de ce réseau : c'est la naissance du graphe
De la représentation des connaissances : parlez-vous le "graphe" ?
Aujourd'hui nous disposons désormais de représentations typiques accompagnées d'algorithmes puissants qui servent dans différents domaines :
- Aide à la planification :
- Dans une gestion de projet, certains travaux ont une durée. Ils ne peuvent commencer si d'autres sont finis; de même, la bonne fin de ces travaux conditionnent le commencement d'autres travaux. L'interdépendance des travaux est un graphe, et certains logiciels professionnels permettent de repérer l'ensemble des travaux qui peuvent perturber tout le projet ou simplement le travail suivant, ils peuvent calculer des répartitions de ressources sur les travaux en fonction de différents critères.
- Aide à l'investigation :
- Les gendarmes et les cellules anti-terroristes utilisent cette méthode, où ils posent graphiquement sur la fenêtre du logiciel les éléments et indices qu'autrefois ils punaisaient sur des cartes papier. L'avantage du logiciel est de pouvoir manipuler beaucoup plus d'éléments à la fois en moins de temps; les enquêtes en sont prodigieusement accélérées. En outre, dotés d'algorithmes d'exploitation du graphe, ils peuvent en extraire des conclusions pertinentes qui auraient échappé à leur perspicacité.
utilisation du concept mapping en investigation et contre-terrorisme - Les documentalistes et les travailleurs de la connaissance,
- ceux qui de près ou de loin essaient de sauvegarder les connaissances d'entreprise et de les redistribuer opportunément à ceux qui en ont besoin, peuvent utiliser des structures à base de graphes sémantiques pour modéliser un ensemble de documents. Ainsi on fera la distinction entre un réseau sémantique, où les liens sont "nus", d'une "carte de sujets" (topic map) où les liens supportent des groupes verbaux. Les réseaux sémantiques permettent de rapprocher des thèmes et des mots-clés entre eux, et sont utilisés en Text Mining sous la forme de règles d'association.
- Un exemple personnel et amusant d'utilisation des graphes :
- j'avais proposé à mon cousin et sa future épouse d'utiliser un traceur de graphes pour organiser la répartition des invités autour des tables lors de leur mariage. Bon, concrètement, ça n'a pas été très utile, puisque madame connaissait par coeur tous les invités et était capable de les catégoriser mentalement; le problème restait séduisant malgré tout : il y a les gens qui veulent rester ensemble, ceux qui ne peuvent pas se sentir, ceux qu'on peut mettre ensemble mais qui seraient mieux ailleurs, etc...Ainsi, chaque fois qu'un problème a l'apparence d'un entrelacement, d'un jeu de taquin, le graphe est d'une aide précieuse en raison de sa nature graphique et pédagogique.
- Aide à la navigation
- Ces temps-ci, la publicité est faite pour ces petits boîtiers munis d'un écran que vous pouvez raccorder au GPS de votre voiture, s'il n'en possède pas un déjà. Sur l'écran, vous programmez l'endroit où vous voulez vous rendre, et le système vous guide par la vue ou par la voix dans les ruelles d'une ville et sur les autoroutes du pays sans broncher. Encore plus fort : si vous loupez un embranchement, la machine recalcule un itinéraire de rattrapage. Chaque carrefour, chaque lieu est représenté par un noeud, et chaque route est un lien. Les algorithmes qui tournent sont appelés "chercheurs de chemin" (pathfinders). Un autre exemple de navigation est celle sur Internet : le schéma qui relie les sites entre eux est appelé le Web Graph et est étudié scientifiquement, ce qui a permis de conclure qu'Internet a une structure de papillon. Certains sites, qui ne sont pointés ni ne pointent personne, sont libres d'accès mais réservés à de seuls initiés, et recèlent des trésors inimaginables...
On s'aperçoit sur les exemples précédents que le graphe est particulièrement recommandé pour les affaires relatives aux questions linguistiques ou sociales. C'est pour cette raison que les gestionnaires d'entreprises et les cadres supérieurs y trouvent un outil de prédilection. Par exemple, l'analyse de la qualité des rapports sociaux dans une entreprise est appelé un tensiogramme, qui n'est rien d'autre que le graphe du mariage...
La construction et l'utilisation du graphe
Alors, me direz-vous, si le graphe est un objet soutenu par une théorie scientifique, pourquoi parler de "concept mapping" ? Encore un terme de marketing ?A la décharge du marketing, je dirais que de choisir un terme spécifique pour désigner un ensemble de pratiques est un acte linguistique qui a une certaine influence sur le psychisme humain. On parle de "poser un signifiant sur un signifié", ou encore de "mettre des mots sur des choses et des émotions"...
Concrètement, lorsqu'on pratique le graphe en entreprise ou ailleurs, il ne s'agit pas de débarquer en disant : "coucou, nous allons faire de l'analyse spectrale de graphe...". Le concept mapping est une démarche relativement simple si l'on respecte quelques points :
- Le concept mapping est à l'opposé du Mind Mapping, c'est un travail réfléchi, pesé, jugé à l'aune des compétences et des références.
- Le concept mapping est un travail de groupe, dont la vocation est d'élaborer des synthèses de connaissances, des plans stratégiques et des solutions à des problèmes "insolubles".
- chaque expert commence par formuler une série d'assertions qui vont poser les connaissances requises. Ces connaissances, écrites sous forme de phrases simples, devront reformuler ce qui est compris du problème et ce qui en est connu. Des éléments de contexte peuvent être rajoutés.
- Les assertions vont être décortiquées grammaticalement, pour repérer ce qui est nominal, ce qui est verbal, et ce qui est circonstanciel (date, lieu, etc...)
- Chaque phrase devient alors un doublet du graphe, c'est-à-dire deux éléments nominaux reliés par une flèche verbale.
- Les éléments circonstanciels peuvent être soit de nouveaux noeuds, soit être des "étiquettes" des noeuds nominaux ou des liens existants. Cette convention doit absolument être posée dès le début des travaux, elle conditionne tous les traitements ultérieurs et est appelée le scénario d'analyse.
- L'expert est alors prêt à synthétiser son graphe, relatif à son expertise sur le problème ou le sujet.
- Puis tous les experts mettent en commun chacun de leurs graphes, en repérant les éléments communs d'un graphe à l'autre. Le graphe fusionné contient tous les éléments de chacun des graphes individuels, et chaque élément est lié aux autres par les liens présents dans chacun des graphes individuels. En fait, il s'agit d'un graphe consolidé, mais le résultat est plus qu'intéressant.
- Scientifiquement, il a été montré que l'esprit humain accumule les connaissances de cette manière, et que le graphe consolidé peut toujours recevoir de nouveaux graphes, c'est-à-dire de nouvelles connaissances. Pour apprendre, on ne part jamais de rien, et tout apprentissage est une consolidation d'un graphe existant.
Les méthodes d'exploitation du graphe
L'un des premiers travaux, et le plus simple, peut être de visualiser le graphe. En prenant du recul, physiquement, la simple scrutation du graphe permet d'avoir une vue exhaustive de la situation, d'interpréter et d'assimiler le contexte du problème. Cet acte anodin d'observer a l'immense avantage de mettre d'accord les spécialistes entre eux et de les faire converger constructivement vers une solution élaborée. C'est plus un travail de communication visuelle que d'analyse formelle du graphe, toutefois et à l'instar du data mining, c'est parfois la visualisation des données qui montre le chemin à suivre pour analyser le problème. A ne pas négliger donc...| un exemple de visualisation de graphes : l'applet Touchgraph |
|
Vous pouvez soit cliquer "droit" sur les noeuds, soit cliquer "gauche". En cliquant "droit", vous pouvez développer un noeud, "expand node" |
Une autre visualisation, peu pratiquée toutefois, consiste à décomposer le graphe consolidé dans un tableau, possédant autant de lignes qu'il y a de liens dans le graphe. Chaque ligne comportera trois colonnes minimum, avec l'élément de départ du lien, l'élément d'arrivée, et la caractéristique du lien. Le tableau sera classé dans l'ordre alphabétique. C'est un peu comme si vous preniez votre liste d'opérations sur votre compte où chaque transaction est un lien entre votre compte et celui de votre débiteur/créditeur. En classant alphabétiquement les intitulés d'opérations, vous repérez tout de suite les types d'opérations et leur volume d'échange. Vous savez où sont les chèques, les débits au commerçant, les retraits à la machine, etc...
Le premier algorithme que l'on emploie généralement s'appuie sur la recherche de "circuits fermés" et de "sous-graphes compacts". Je détiens une nébuleuse d'informations, alors mon graphe peut-il se décomposer en cellules plus ou moins indépendantes, qui communiqueraient entre elles par des passerelles ? Cela permet de décomposer le problème en zones, en catégories qu'il reste à nommer et à interpréter. Par ailleurs, l'examen des points de passage entre cellules permettra de repérer les facteurs cruciaux, typiquement les connaissances critiques qui conditionnent et articulent les problèmes entre eux. C'est sur ces points que l'attention doit se porter...
On peut également vouloir étudier la causalité qui relie deux éléments du graphe entre eux. Cela est représenté par le plus court chemin dans le graphe entre ces deux éléments, calculable par un algorithme d'Euler ou de Dijkstra. Une fois le chemin trouvé, il peut être possible de l'interpréter comme en généalogie : si B est le frère du cousin de mon arrière grande tante, qui est B pour moi ? On peut utiliser pour cela un moteur d'inférence
On peut alors tracer un schéma de points, avec en abscisse les influences, et en ordonnée les dépendances de chaque noeud. Le schéma permet de repérer directement quels sont les éléments qui influent sur le reste du graphe, et donc le contrôlent.
Supposons que le graphe a cinq éléments : on élève la matrice à la puissance "5" à l'aide d'un logiciel de calcul matriciel et on obtient le graphe des influences indirectes. Si A pointe sur B, et B pointe sur C, alors A pointe indirectement sur C. On peut alors calculer et représenter les influences et les dépendances du graphe indirect, et les comparer aux influences directes...
Du graphe à l'arbre
Arbre : graphe particulier, voir mind mapping.Les algorithmes "spanning tree" : Legendre, recouvrement minimal, etc...
Les algorithmes "MRO" : ordre d'exécution des classes et des règles dans un moteur d'inférence. Cas du Python. Notions d'ordre partiel, voir aussi "analyse multicritères"
Un graphe particulier : l'ontologie
Il existe une pratique particulière de concept mapping dont vous avez peut-être entendu parler : la création d'ontologie. Il s'agit d'une sorte de thésaurus, en fait un graphe "carte à sujets" qui a pour but de repérer et d'indexer des connaissances. Le travail de concept mapping comporte une étape supplémentaire, où chaque noeud du graphe sert d'étiquette, de référence vers un document, un répertoire, une image, etc...Ainsi la machine peut-elle effectuer des inférences et des repérages remarquables dans le graphe, et porter ces associations sur les documents étiquetés, permettant de faire des rapprochements de sens remarquables entre documents.
Dans ce cas, un graphe d'ontologie comportera des noeuds supplémentaires pour expliciter la nature du document. Généralement dans une ontologie, les types de noeuds et les types de liens sont en nombre limité, répartis par catégorie, ce qui permet de fixer des règles pour le moteur d'inférence. Cela fait toutefois des graphes volumineux, et délicats à concevoir et à modifier.
L'intérêt d'une telle structure est de pouvoir référencer la totalité des documents circulant dans l'entreprise, les livres, les documents de travail, les modèles de formulaires, les courriers électroniques, les notices, les plans, les images, etc...C'est la bonne programmation du moteur d'inférence qui permet de déterminer l'usage que l'on veut faire de cette représentation des connaissances.
On utilise des langages à balises pour décrire une ontologie, qui n'est pas sans rappeler HTML ou bien les codes de thésaurus. Typiquement, les langages RDF et OWL, normalisés par le W3C.
Retour à l'accueil
Remonter d'un niveau