Entreposage de documents multimédias : Comparaison de structures

Abstract

Le volume de documents multimédias disponible aujourd’hui, et qui ne cesse d’augmenter, constitue une source d’information importante. Cependant, toute cette information serait sans intérêt si elle n’est pas exploitée efficacement. Gérer et exploiter de telles sources nécessite d’avoir à disposition des outils automatiques permettant de faciliter l’accès à des granules (l'information fine) documentaires, indépendamment de l’hétérogénéité sous-jacentes de ces documents en termes de type, taille, format, contenu, structure, etc. La classification automatique est une solution qui permet d’organiser et de structurer une large collection de documents afin de réduire l’espace de recherche et par conséquent d’améliorer les performances du processus d’accès à l’information. Les approches qui ont abordé la classification documentaire se distinguent par le modèle utilisé pour représenter les documents et par la démarche utilisée pour classer ces documents. S’agissant des documents multimédias, la problématique de classification découle de la complexité de leur représentation. En effet, un document multimédia est composé de plusieurs objets de différentes natures : image, texte, son, etc. Il est multi-structuré par essence ; issu de la composition de plusieurs sous-documents et chaque sous-document aune ou plusieurs structures. Ces structures peuvent être de même nature ou de natures différentes (structure physique, logique, temporelle, etc). La multi-structuralité induit des relations complexes et multiples entre deux mêmes composants d’un document. Il est donc nécessaire d’utiliser un modèle de représentation riche afin de pouvoir classer les documents à structures multiples. Les travaux de recherche que nous avons menés au cours de cette thèse visent ainsi à étudier les modèles de représentation des documents multimédias à structures multiples et à développer des outils capables de traiter de grandes masses de données en prenant en compte les contraintes liées au partage de sous structures (sous-graphes) par des structures hétérogènes. Une des problématiques principales est de savoir comparer deux documents multi-structurés, et en conséquence de pouvoir comparer des structures de documents afin d’évaluer leur similarité. Nous nous sommes intéressés à la représentation des structures documentaires à l’aide des graphes. Comparer structurellement deux documents revient donc à comparer les graphes qui les représentent. Les méthodes classiques de comparaison de documents sont basées sur les similarités dites de «surface» : un modèle de similarité basé sur les propriétés descriptives des objets sans tenir compte des relations entre ces propriétés. Ces méthodes ne tiennent pas compte de l’information implicite qui est véhiculée par la structure documentaire. Cependant, les mêmes composants structurels peuvent ne pas avoir le même rôle, ni la même importance dans deux documents différents. Nous pensons que les informations apportées par les relations structurelles présentent un intérêt incontournable dans un processus de comparaison. Nous montrons, par conséquent, que les mesures standards existantes ne peuvent pas répondre efficacement à notre problématique. Pour évaluer la similarité entre deux graphes, nous proposons unenouvelle mesure de similarité structurelle basée sur l’isomorphisme de (sous) graphes. En théorie des graphes, l’isomorphisme de sous-graphes induits permet de démontrer qu’un graphe est inclus dans un autre, alors que l’isomorphisme de sous-graphes partiels permet de déterminer l’intersection entre deux graphes. Cependant, la recherche d’isomorphisme de sous-graphes est un problème bien connu pour être combinatoire. Ce problème combinatoire rend la plupart des approches limitées à des graphes de petite taille. Pour réduire le coût combinatoire, nous proposons de considérer un graphe comme un ensemble de chemins. Comparer deux graphes revient donc à comparer les chemins qui les composent, en utilisant un modèle à alignement structurel. La mesure proposée reflète la structure des graphes comparés dans le sens où l’on tient compte à la fois de la position des nœuds, de l’ordre des nœuds frères et des liens entre ces nœuds. Pour valider les propositions présentées dans ce mémoire de thèse, nous avons développé un outil de classification automatique non-supervisée d’un corpus de documents à structures multiples. Ainsi, la classification structurelle au sens où nous l’entendons permet de créer des classes appelées vues génériques représentant des documents structurellement proches (thèses, articles scientifiques, documentaires, rapports médicaux, etc).Les classes ne sont pas connues a priori, elles sont calculées automatiquement lors de l’intégration des documents, à partir de la mesure de similarité proposée. Le processus de classification doit permettre l’évaluation de la similarité d’une structure quelconque d’un document donné, avec chacune des vues génériques de l’entrepôt documentaire. Ceci pose des problèmes de temps de calculs et d’efficience de nos algorithmes. Nous avons proposé de restreindre l’espace de comparaison en utilisant une présélection des vues génériques susceptibles d’être similaires avec la structure du document à intégrer. Cela permet d’optimiser le temps de réponse de nos algorithmes de comparaison sans pour autant altérer la qualité de la classification. Dans nos expérimentations, nous avons étudié les performances de nos algorithmes de classification en termes de qualité des classes générées et de temps de réponse.