Révision automatique des connaissances guidant l'exploration informée d'arbres d'états : application au contexte de la généralisation de données géographiques, Automatic revision of knowledge guiding informed search tree exploration : application to the context of geographic data generalisation

Patrick Taillandier

Description

Sous la direction de Alexis Drogoul
Thèse soutenue le 02 décembre 2008: Paris Est
Cette thèse traite de la révision automatique des connaissances contenues dans les systèmes fonctionnant par exploration informée d'arbres d'états. Ces systèmes, de par leur performance, sont employés dans de nombreux domaines applicatifs. En particulier, des travaux ont proposés d’utiliser cette approche dans le cadre de l'automatisation de la généralisation de données géographiques. La généralisation de données géographique s'intéresse à la dérivation, à partir de données géographiques détaillées, de données moins détaillées adaptées à un besoin particulier (e.g. changement d'échelle). Son automatisation, enjeu majeur pour les agences cartographiques telles que l'Institut Géographique National (IGN), est particulièrement complexe. Les performances des systèmes basés sur l’exploration informée d'arbres d'états sont directement dépendantes de la qualité de leurs connaissances (heuristiques). Or, la définition et la mise à jour de ces dernières s'avèrent généralement fastidieuses. Dans le cadre de cette thèse, nous proposons une approche de révision hors ligne des connaissances basée sur le traçage du système et sur l'analyse de ces traces. Ces traces sont ainsi utilisées par un module de révision qui est chargé d'explorer l'espace des connaissances possibles et d'en modifier en conséquence les connaissances du système. Des outils de diagnostic en ligne de la qualité des connaissances permettent de déterminer quand déclencher le processus de révision hors ligne des connaissances. Pour chaque méthode et approche que nous présentons, une mise en oeuvre est détaillée et expérimentée dans le cadre de l'automatisation de la généralisation de données géographiques
-Révision des connaissances
-Exploration informée d'arbres d'états
-Diagnostic de la qualité des connaissances
-Généralisation de données géographiques
-Systèmes d'information géographique
This work deals with automatic knowledge revision in systems based on an informed tree search strategy. Because of their efficiency, these systems are used in numerous fields. In particular, some literature work uses this approach for the automation of geographic data generalisation. Geographic data generalisation is the process that derives data adapted to specific needs (e.g. map scale) from too detailed geographic data. Its automation, which is a major issue for national mapping agencies like Institut Géographique National (IGN), is particularly complex. The performances of systems based on informed tree search are directly dependant on their knowledge (heuristics) quality. Unfortunately, most of the time, knowledge definition and update are fastidious. In this work, we propose an offline knowledge revision approach based on the system logging and on the analysis of these logs. Thus, the logs are used by a revision module which is in charge of the system knowledge revision by knowledge space exploration. Tools for online knowledge quality diagnosis allow to determine when the offline knowledge process should be activated. For each method and each approach presented, an implementation is proposed in the context of geographic data generalisation
-Knowledge revision
-Informed tree search strategy
-Quality knowledge diagnosis
-Geographic data generalisation
Source: http://www.theses.fr/2008PEST0258/document

Sujets

• Système d'information géographique

Informations

• Publié par: Thesee
• Nombre de lectures: 19
• Langue: Français
• Poids de l'ouvrage: 24 Mo

Extrait

Université Paris-Est
Ecole doctorale ICMS

Thèse
pour obtenir le grade de Docteur de l’Université Paris-Est
Spécialité : Informatique

Patrick TAILLANDIER
Révision automatique des connaissances guidant
l’exploration informée d’arbres d’états
Application au contexte de la généralisation de données géographiques









Soutenue le 2 décembre 2008 devant le jury composé de :
Pr. Antoine Cornuéjols Rapporteur
Pr. Alexis Drogoul Directeur
Dr. Cécile Duchêne Encadrante
Pr. Alain Mille Examinateur
Dr. Nicolas Regnauld Examinateur
Pr. Jean-Daniel Zucker Rapporteur
tel-00481927, version 1 - 7 May 2010
2
tel-00481927, version 1 - 7 May 2010Remerciements
Parce que parfois un beau dessin vaut mieux qu’un long discours…



3
tel-00481927, version 1 - 7 May 2010Résumé


Cette thèse traite de la révision automatique des connaissances contenues dans les systèmes
fonctionnant par exploration informée d'arbres d'états. Ces systèmes, de par leur performance,
sont employés dans de nombreux domaines applicatifs. En particulier, des travaux ont
proposés d’utiliser cette approche dans le cadre de l'automatisation de la généralisation de
données géographiques. La généralisation de données géographique s'intéresse à la dérivation,
à partir de données géographiques détaillées, de données moins détaillées adaptées à un
besoin particulier (e.g. changement d'échelle). Son automatisation, enjeu majeur pour les
agences cartographiques telles que l'Institut Géographique National (IGN), est
particulièrement complexe.
Les performances des systèmes basés sur l’exploration informée d'arbres d'états sont
directement dépendantes de la qualité de leurs connaissances (heuristiques). Or, la définition
et la mise à jour de ces dernières s'avèrent généralement fastidieuses.
Dans le cadre de cette thèse, nous proposons une approche de révision hors ligne des
connaissances basée sur le traçage du système et sur l'analyse de ces traces. Ces traces sont
ainsi utilisées par un module de révision qui est chargé d'explorer l'espace des connaissances
possibles et d'en modifier en conséquence les connaissances du système. Des outils de
diagnostic en ligne de la qualité des connaissances permettent de déterminer quand déclencher
le processus de révision hors ligne des connaissances. Pour chaque méthode et approche que
nous présentons, une mise en œuvre est détaillée et expérimentée dans le cadre de
l'automatisation de la généralisation de données géographiques.

Mots clefs : révision des connaissances, exploration informée d'arbres d'états, diagnostic de la
qualité des connaissances, généralisation de données géographiques.
4
tel-00481927, version 1 - 7 May 2010Abstract


This work deals with automatic knowledge revision in systems based on an informed tree
search strategy. Because of their efficiency, these systems are used in numerous fields. In
particular, some literature work uses this approach for the automation of geographic data
generalisation. Geographic data generalisation is the process that derives data adapted to
specific needs (e.g. map scale) from too detailed geographic data. Its automation, which is a
major issue for national mapping agencies like Institut Géographique National (IGN), is
particularly complex.

The performances of systems based on informed tree search are directly dependant on their
knowledge (heuristics) quality. Unfortunately, most of the time, knowledge definition and
update are fastidious.

In this work, we propose an offline knowledge revision approach based on the system logging
and on the analysis of these logs. Thus, the logs are used by a revision module which is in
charge of the system knowledge revision by knowledge space exploration. Tools for online
knowledge quality diagnosis allow to determine when the offline knowledge process should
be activated. For each method and each approach presented, an implementation is proposed in
the context of geographic data generalisation.

Keywords: knowledge revision, informed tree search strategy, quality knowledge diagnosis,
geographic data generalisation.
5
tel-00481927, version 1 - 7 May 2010
6
tel-00481927, version 1 - 7 May 2010Table des matières
INTRODUCTION 21
CONTEXTE GENERAL 23
Exploration informée d’arbres d’états 23
Généralisation de données géographiques 24
OBJECTIFS DE LA THESE 25
PLAN 25
REMARQUES SUR LE VOCABULAIRE ET LES NOTATIONS 27
A CONTEXTE APPLICATIF : LA GENERALISATION DE DONNEES GEOGRAPHIQUES
29
A.I INTRODUCTION 31
A.II LA GENERALISATION DE DONNEES GEOGRAPHIQUES 33
A.II.1 REPRESENTATION NUMERIQUE DE L’INFORMATION GEOGRAPHIQUE 33
A.II.1.1 Modes de représentation des données géographiques 33
A.II.1.2 Base de données géographique 34
A.II.1.3 Système d’information géographique 34
A.II.2 LA GENERALISATION DE DONNEES GEOGRAPHIQUES 35
A.II.2.1 Echelle et niveau de détail 35
A.II.2.2 Généralisation de données géographiques 36
A.II.2.3 Généralisation cartographique 36
A.II.2.4 Contraintes et conflits cartographiques 37
A.II.2.5 Opérations de généralisation 38
A.III L’AUTOMATISATION DE LA GENERALISATION DE DONNEES GEOGRAPHIQUES 40
A.III.1 ENJEU DE L’AUTOMATISATION DE LA GENERALISATION 40
A.III.2 PROBLEMATIQUE DE L’AUTOMATISATION DE LA GENERALISATION 40
A.III.2.1 Algorithmes de généralisation et outils d’analyse spatiale 40
A.III.2.2 Passage de l’algorithme au processus 41
A.III.3 SEQUENCE PREDEFINIE 42
A.III.4 APPROCHES GLOBALES 43
A.III.4.1 Approches par minimisation 43
A.III.4.2 Approches par optimisation globale 44
A.III.5 APPROCHES LOCALES 45
A.III.5.1 Principes 45
A.III.5.2 Approches basées sur le paradigme agent 46
A.IV LE MODELE AGENT : UN MODELE DE GENERALISATION AUTOMATIQUE FONCTIONNANT
PAR EXPLORATION INFORMEE D’ARBRES D’ETATS 49
A.IV.1 PRINCIPE GENERAL 49
A.IV.2 LES CONTRAINTES 50
A.IV.3 CYCLE D’ACTIONS 52
A.IV.4 CONNAISSANCES PROCEDURALES EN JEU 55
A.V ENJEU DE LA REVISION DES CONNAISSANCES PROCEDURALES DANS LES SYSTEMES DE
GENERALISATION FONCTIONNANT PAR EXPLORATION INFORMEE D’ARBRES D’ETATS 57
A.V.1 AMELIORATION DE L’EFFICIENCE ET DE L’EFFICACITE 57
7
tel-00481927, version 1 - 7 May 2010A.V.2 EVOLUTIVITE DU SYSTEME 58
A.VI OBJECTIF DE LA THESE 59
B PROBLEMATIQUE ET APPROCHE GENERALE 61
B.I INTRODUCTION 63
B.II ACQUISITION ET REVISION AUTOMATIQUE DE CONNAISSANCES 64
B.II.1 ACQUISITION ET REVISION DES CONNAISSANCES EN INTELLIGENCE ARTIFICIELLE 64
B.II.1.1 Introduction 64
B.II.1.2 Généralités sur l’apprentissage artificiel 65
B.II.1.3 L’apprentissage supervisé 66
B.II.1.4 Caractérisation d’un problème d’apprentissage 69
B.II.1.5 Révision des connaissances en intelligence artificielle 70
B.II.2 ACQUISITION ET REVISION DES CONNAISSANCES DANS LE CADRE DE LA GENERALISATION DE
DONNEES GEOGRAPHIQUES 74
B.II.3 BILAN 77
B.III REVISION PAR L’EXPERIENCE DES CONNAISSANCES PROCEDURALES D’UN SYSTEME
FONCTIONNANT PAR EXPLORATION INFORMEE D’ARBRES D’ETATS : FORMALISATION 79
B.III.1 SYSTEME FONCTIONNANT PAR EXPLORATION INFORMEE D’ARBRES D’ETATS 79
B.III.1.1 Problème d’optimisation 79
B.III.1.2 Système de résolution de problèmes fonctionnant par exploration informée d’arbres
d’états 81
B.III.2 REVISION PAR L’EXPERIENCE DES CONNAISSANCES PROCEDURALES 83
B.III.2.1 Evaluation des performances d’un système fonctionnant par exploration d’arbres
d’états 83
B.III.2.2 Objectif de la révision 85
B.IV REVISION PAR L’EXPERIENCE DES CONNAISSANCES PROCEDURALES D’UN SYSTEME
FONCTIONNANT PAR EXPLORATION INFORMEE D’ARBRES D’ETATS : PROBLEMATIQUES 86
B.IV.1 PROBLEMES LIES AU DIAGNOSTIC DES CONNAISSANCES 86
B.IV.2 PROBLEMES LIES A L’ACQUISITION DE CONNAISSANCES 87
B.IV.3 PROBLEMES LIES A LA REVISION DES CONNAISSANCES 88
B.V APPROCHE ET MODELE GENERAUX DE REVISION DES CONNAISSANCES PROPOSES 90
B.V.1 APPROCHE GENERALE PROPOSEE POUR LA REVISION DES CONNAISSANCES PROCEDURALES 90
B.V.1.1 Introduction 90
B.V.1.1 Processus de révision des connaissances 91
B.V.1.2 Module de diagnostic 92
B.V.2 MODELISATION AGENT DES CONNAISSANCES 92
B.V.3 APPLICATION DANS LE CADRE DU MODELE AGENT 95
B.V