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

De
Publié par

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
Publié le : mardi 1 novembre 2011
Lecture(s) : 17
Nombre de pages : 415
Voir plus Voir moins




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.3.1 Formalisations et enrichissements proposés 95
B.V.3.1.1 Présentation des formalisations et enrichissements proposés 95
B.V.3.1.2 Connaissances procédurales du modèle AGENT enrichi 98
B.V.3.2 Application de l’approche générale pour le modèle AGENT 102
B.V.3.3 Agents connaissance pour le modèle AGENT 102
B.VI BILAN 105
C CONSTITUTION DE L’EXPERIENCE : PRODUCTION DE TRACES D’EXECUTION 107
C.I INTRODUCTION 109
C.II CHOIX DE L’ECHANTILLON D’INSTANCES DU PROBLEME UTILISE POUR LA REVISION DES
CONNAISSANCES 111
C.II.1 PROBLEMATIQUE DU CHOIX DE L’ECHANTILLON UTILISE POUR PRODUIRE DE L’EXPERIENCE 111
C.II.2 APPROCHE PROPOSEE DE CHOIX DE L’ECHANTILLON DE REVISION 112
C.II.2.1 Phase de caractérisation des instances du problème d’optimisation 112
8
tel-00481927, version 1 - 7 May 2010C.II.2.2 Phase de définition des familles 113
C.II.2.3 Phase de choix des instances du problème 113
C.II.3 APPLICATION DE L’APPROCHE POUR LE SYSTEME AGENT 114
C.III CHOIX DU JEU DE CONNAISSANCES UTILISE LORS DE LA PRODUCTION DE TRACES 116
C.III.1 IMPORTANCE DU JEU DE CONNAISSANCES CHOISI LORS DE LA PRODUCTION DE TRACES 116
C.III.2 JEU DE CONNAISSANCES MINIMAL POUR LE MODELE AGENT 120
C.IV CONSTRUCTION DES BASES D’EXEMPLES 122
C.IV.1 INTRODUCTION 122
C.IV.2 CONSTRUCTION DES BASES D’EXEMPLES 123
C.IV.2.1 Forme des bases d’exemples 123
C.IV.2.2 Construction des bases d’exemples à partir des arbres d’états 124
C.IV.2.3 Construction de l’ensemble des meilleurs chemins 126
C.IV.3 EVALUATION DES JEUX DE MESURES 127
C.IV.3.1 Approche proposée d’évaluation des jeux de mesures 127
C.IV.3.2 Sélection des mesures pertinentes 128
C.IV.3.3 Discrétisation des mesures pertinentes 129
C.IV.3.4 Calcul de l’incohérence de la base d’exemples résultantes 130
C.IV.4 APPLICATION POUR LE SYSTEME AGENT 131
C.IV.4.1 Construction des bases d’exemples 131
C.IV.4.1.1 Introduction 131
C.IV.4.1.2 Connaissances relatives à la priorité des contraintes 132
C.IV.4.1.3 Connaissances relatives à l’application des actions 134
C.IV.4.1.4 Connaissance relative à l’optimalité des états 137
C.IV.4.1.5 Connaissance relative à la fin de cycle 139
C.IV.4.2 Evaluation des jeux de mesures 141
C.V BILAN 143
D REVISION DES CONNAISSANCES PROCEDURALES PAR ANALYSE DES TRACES
D’EXECUTION 145
D.I INTRODUCTION 147
D.II APPROCHE GENERALE DE REVISION PAR ANALYSE 149
D.II.1 PROBLEMATIQUES LIEES AU PROCESSUS DE REVISION PAR ANALYSE 149
D.II.2 PRESENTATION DE L’APPROCHE GENERALE DE REVISION PAR ANALYSE 150
D.II.2.1 Décomposition du processus général de révision par analyse 150
D.II.2.1.1 Approche générale 150
D.II.2.1.2 Application pour le modèle AGENT 154
D.II.2.2 Sous-processus de révision par analyse pour un groupe de connaissances 155
D.III REVISION PAR ANALYSE D’UN GROUPE DE CONNAISSANCES 157
D.III.1 INTRODUCTION 157
D.III.2 APPROCHE GENERIQUE DE REVISION PAR ANALYSE D’UN GROUPE DE CONNAISSANCES 157
D.III.2.1 Formalisation du problème considéré et approche proposée 157
D.III.2.2 Fonction d’évaluation de la pertinence du remplacement du jeu de connaissances
initial par un nouveau jeu de connaissances 158
D.III.2.3 Méthodes de résolution de problèmes en intelligence artificielle 160
D.III.2.3.1 Introduction 160
D.III.2.3.2 Métaheuristiques pour la résolution de problèmes 161
D.III.2.3.3 Bilan 164
D.III.2.4 Application dans le cadre du modèle AGENT 164
D.III.2.4.1 Révision de la connaissance sur la validité des états 164
D.III.2.4.2 Révision des connaissances sur la restriction d’application des actions 165
D.III.3 APPROCHE DE REVISION PAR ANALYSE POUR LES CONNAISSANCES REPRESENTEES SOUS FORME
DE BASES DE REGLES DE PRODUCTION 167
D.III.3.1Introduction 167
9
tel-00481927, version 1 - 7 May 2010D.III.3.2 Formalisation des connaissances considérées et problématique 167
D.III.3.2.1 Formalisation des règles considérées 167
D.III.3.2.2 Formalisation des bases de règles considérées 168
D.III.3.2.3 Problématique de la révision de bases de règles 169
D.III.3.3 Approche de révision par analyse des bases de règles 169
D.III.3.4 Partitionnement de l’espace des mesures 171
D.III.3.4.1 Introduction 171
D.III.3.4.2 Partitionnement par discrétisations indépendantes des mesures 173
D.III.3.4.3 Partitionnement par apprentissage et comparaison de règles 177
D.III.3.4.4 Conclusion sur le partitionnement de l’espace des mesures 181
D.III.3.5 Exploration de l’espace des connaissances possibles 181
D.III.3.5.1 Introduction 181
D.III.3.5.2 Taux de modification pour les bases de règles de BR 184
D.III.3.5.3 Recherche exhaustive simple 185
D.III.3.5.4 Approche par métaheuristique de recherche locale 186
D.III.3.5.5 Recherche par approche agents 187
D.III.3.5.6 Bilan de nos approches de recherche des meilleures affectations de conclusion 200
D.III.3.6 Simplification des bases de règles 201
D.III.3.7 Bilan sur nos approches de révision de bases de règles de BR 203
D.IV BILAN 205
E DIAGNOSTIC EN LIGNE DE LA QUALITE DES CONNAISSANCES PROCEDURALES
207
E.I INTRODUCTION 209
E.II PROBLEMATIQUE DU DIAGNOSTIC EN LIGNE DE LA QUALITE DES CONNAISSANCES
PROCEDURALES 210
E.II.1 DIFFICULTES DU DIAGNOSTIC EN LIGNE 210
E.II.2 PROBLEMATIQUE DU DIAGNOSTIC EN LIGNE 212
E.III APPROCHE PROPOSEE 213
E.III.1 PRINCIPE 213
E.III.2 ANALYSE D’UNE INSTANCE RESOLUE D’UN PROBLEME D’OPTIMISATION 214
E.III.3 ANALYSE DE L’HISTORIQUE 215
E.III.4 EVALUATION QUALITATIVE DU JEU DE CONNAISSANCES 217
E.III.4.1 Introduction 217
E.III.4.2 Evaluation qualitative du jeu de connaissances 218
E.III.4.2.1 Etat de l’art des méthodes d’analyse et de décision multicritère 218
E.III.4.2.2 Evaluation du jeu de connaissances par la méthode des fonctions de
croyance 219
E.III.4.2.3 Evaluation du jeu de connaissances par la méthode ELECTRE TRI 228
E.III.4.2.4 Conclusion sur l’évaluation qualitative du jeu de connaissances 234
E.III.4.3 Evaluation indépendante de la qualité des connaissances 235
E.III.5 BILAN SUR L’APPROCHE DE DIAGNOSTIC PROPOSEE 235
E.IV APPLICATION POUR LE MODELE AGENT 237
E.IV.1 LES AGENTS CONNAISSANCE ET L’AGENT DIAGNOSTIC 237
E.IV.2 ANALYSE DU RESULTAT D’UNE GENERALISATION D’UN AGENT GEOGRAPHIQUE 237
E.IV.3 ANALYSE DE L’HISTORIQUE 241
E.V BILAN 243
F EXPERIMENTATION ET EVALUATION DU MODELE COMPLET DE REVISION DES
CONNAISSANCES ET DU MODULE DE DIAGNOSTIC 245
F.I INTRODUCTION 247
10
tel-00481927, version 1 - 7 May 2010

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi