Sujet : Extraction de connaissances par la combinaison de la visualisation et de techniques de routage

Responsable : Nicolas Hanusse et Noel Novelli
Téléphone : 05 4000 2604
e-mail : hanusse,novelli@labri.fr
Site Web : http://www.labri.fr/~hanusse
Equipe : Combinatoire et Algorithmique

Présentation du sujet :

Les techniques d’analyses de données basées sur les statistiques, apprentissage automatique, intelligence artificielle sont très utilisées en industrie. Mais la croissance des données étudiées est telle que les résultats obtenus deviennent eux-mêmes de taille exponentielle et sont présentés sous la forme de listes interminables. Sans technique d’interaction efficace, l’utilisateur ne peut pas obtenir d’information pertinente et originale.

Les très récentes avancées sur la visualisation de grandes masses de données, la découverte de propriétés des données issues de la réalité (dites de "petit-monde") laissent entrevoir de nouvelles techniques pour la recherche d’information et la fouille de données (plus généralement l’extraction de connaissances). Notre approche est novatrice et consiste à combiner 1/ des méthodes automatiques, issues de protocoles de communication dans les réseaux (routage) et de la modélisation des données par des graphes à 2/ des techniques de visualisation de données et de navigation visuelle.

L’originalité de ce sujet est de considérer que le routage, la recherche d’information et la fouille de données peuvent être perçus comme des problèmes analogues – des requêtes dans un réseau, graphe ou bases de données - mais avec des objectifs et hypothèses de plus en plus flous. Dans les deux premiers cas, l’utilisateur « sait » quand il est arrivé (terminologie routage) et il est capable de déterminer si l’information obtenue est celle recherchée. Dans le contexte du routage, on connaît l’adresse de la destination et la difficulté est de trouver un chemin pour s’y rendre. Pour la recherche d’information, la localisation de la destination est inconnue mais des indications peuvent être glanées en chemin pour la trouver. En ce qui concerne la fouille de données, non seulement il ne connaît pas la destination mais il n’est pas capable d’exprimer une requête précise ou de définir ce qu’est une information pertinente. Par exemple, trouver des scènes analogues entre films diffé rents n’est pas facilement exprimable et les techniques d’indexation vidéo trop peu efficaces. Autre problème : toute méthode automatique aura tendance à proposer des centaines, voir des milliers de résultats répondant à une requête qui, même classés, deviennent inexploitables dans les faits. Les moteurs de recherche peuvent retourner de grandes listes classées suivant un indice de pertinence mais seules les premières lignes sont effectivement lues.

Nous proposons d’adapter des techniques de routage les plus performantes à la fouille de données. L’utilisateur est considéré comme une entité naviguant dans un réseau. Chaque point du réseau correspond à une information et deux informations sont reliées si elles sont « similaires ». Dans le cadre du routage, les nœuds possèdent une table de routage indiquant pour chaque destination le prochain nœud voisin à atteindre. De nombreuses études théoriques montrent comment réduire les tables de routage tout en assurant le routage par des courts chemins. Le principe consiste à stocker judicieusement qu’un nombre restreint de destinations, proches du nœud courant. L’objectif est de proposer à l’utilisateur une visualisation des données « proches » de l’information sur lequel il se situe. Cette vision locale doit correspondre de manière analogue à des tables compactes de routage. La validation de cette approche se fera sur des données réelles en comparant les techniques existantes.

Mot-clés : Visualisation d'informations, routage, algorithmique de graphes, base de données, fouille de données

Commentaires :
Ce sujet est proposé dans le cadre du projet Navgraphe. cf. http://www.labri.fr/~hanusse/Navgraphe