//img.uscri.be/pth/d96296417ad4c5768a19290cbd52e0ba156b168d
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Fusion de connaissances imparfaites pour l'appariement de données géographiques : proposition d'une approche s'appuyant sur la théorie des fonctions de croyance, Imperfect knowledge fusion for matching geographical data : approach based on belief theory

De
268 pages
Sous la direction de Anne Ruas, Sébastien Mustière
Thèse soutenue le 24 octobre 2008: Paris Est
De nos jours, il existe de nombreuses bases de données géographiques (BDG) couvrant le même territoire. Les données géographiques sont modélisées différemment (par exemple une rivière peut être modélisée par une ligne ou bien par une surface), elles sont destinées à répondre à plusieurs applications (visualisation, analyse) et elles sont créées suivant des modes d’acquisition divers (sources, processus). Tous ces facteurs créent une indépendance entre les BDG, qui pose certains problèmes à la fois aux producteurs et aux utilisateurs. Ainsi, une solution est d’expliciter les relations entre les divers objets des bases de données, c'est-à-dire de mettre en correspondance des objets homologues représentant la même réalité. Ce processus est connu sous le nom d’appariement de données géographiques. La complexité du processus d’appariement fait que les approches existantes varient en fonction des besoins auxquels l'appariement répond, et dépendent des types de données à apparier (points, lignes ou surfaces) et du niveau de détail. Nous avons remarqué que la plupart des approches sont basées sur la géométrie et les relations topologiques des objets géographiques et très peu sont celles qui prennent en compte l’information descriptive des objets géographiques. De plus, pour la plupart des approches, les critères sont enchaînés et les connaissances sont à l’intérieur du processus. Suite à cette analyse, nous proposons une approche d’appariement de données qui est guidée par des connaissances et qui prend en compte tous les critères simultanément en exploitant à la fois la géométrie, l’information descriptive et les relations entre eux. Afin de formaliser les connaissances et de modéliser leurs imperfections (imprécision, incertitude et incomplétude), nous avons utilisé la théorie des fonctions de croyance [Shafer, 1976]. Notre approche d’appariement de données est composée de cinq étapes : après une sélection des candidats, nous initialisons les masses de croyance en analysant chaque candidat indépendamment des autres au moyen des différentes connaissances exprimées par divers critères d’appariement. Ensuite, nous fusionnons les critères d’appariement et les candidats. Enfin, une décision est prise. Nous avons testé notre approche sur des données réelles ayant des niveaux de détail différents représentant le relief (données ponctuelles) et les réseaux routiers (données linéaires)
-Appariement
-Données géographiques
-Fusion
-Connaissances
-Imperfection
-Comparaisons par paires Méthode des
-Géographie -- Bases de données
Nowadays, there are many geographic databases, (GDB), covering the same reality. The geographical data are represented differently (for example a river can be represented by a line or a polygon), they are used in different applications (visualisation, analysis) and they are created using various modes of acquisition (sources, processes). All these factors create independence between GDB, which causes problems for both producers and users. Thus, a solution is to clarify the relationships between various database objects, i.e. to match homologous objects, which represent the same reality. This process is known as spatial data matching. Because of the complexity of the matching process, the existing approaches depend on the types of data (points, lines or polygons) and the level of detail of the GDB. We realised, that most of the approaches are based on the geometry and the topology of the geographical objects, and very few approaches take into account the descriptive information of geographical objects. Besides, for most approaches, the criteria are applied one after the other and knowledge is contained within the process. Following this analysis, we proposed a matching approach that is guided by knowledge and takes into account all criteria at the same time exploiting the geometry, descriptive information and relations between geographical objects. In order to formalise knowledge and model their imperfections (imprecision, uncertainty and incompleteness), we used the Belief Theory [Shafer, 1976]. Our approach of the data matching is composed of five steps. After a selection of candidates, the masses of beliefs are initialised by analysing each candidate separately from the others using different knowledge expressed by various matching criteria. Then, the matching criteria and candidates are fusioned. Finally, a decision is taken. Our approach has been tested on real data having different levels of detail and representing relief (data points) and road networks (linear data)
-Matching
-Fusion
-Knowledge
-Geographical data
-Imperfection
Source: http://www.theses.fr/2008PEST0252/document
Voir plus Voir moins



THÈSE
pour obtenir le grade de
Docteur de l’Université Paris-Est
Spécialité : Sciences de l’Information Géographique
présentée et soutenue publiquement par
Ana-Maria OLTEANU
le 24 octobre 2008


Fusion de connaissances imparfaites pour l'appariement de
données géographiques
Proposition d'une approche s'appuyant sur la théorie des fonctions de
croyance
Jury :
Mme BOUCHON-MEUNIER Bernadette – Rapporteur, Directeur de recherche au CNRS
M. CLARAMUNT Christophe – Rapporteur, Professeur
M. MUSTIERE Sébastien – Co-Encadrant, Docteur
Mme REYNAUD Chantal – Examinateur, Professeur
Mme RUAS Anne – Directrice de thèse, HDR
Mme SERVIGNE Sylvie – Examinateur, Maître de conférence
Université Paris-Est – Ecole doctorale ICMS
Institut Géographique National - Laboratoire COGIT
tel-00469407, version 1 - 1 Apr 2010
2
tel-00469407, version 1 - 1 Apr 2010à ma mère, nouvelle étoile


à Olivier
3
tel-00469407, version 1 - 1 Apr 2010 4
tel-00469407, version 1 - 1 Apr 2010Remerciements
Je tiens d’abord à remercier Anne RUAS, directrice du laboratoire COGIT, pour
m’avoir accueillie au sein de son laboratoire. Je voudrais aussi la remercier pour avoir accepté
de diriger cette thèse, pour ses conseils avisés, sa disponibilité et son soutien.
Je remercie les membres du jury et tout particulièrement mes deux rapporteurs Mme
Bernadette BOUCHON-MEUNIER et M. Christophe CLARAMUNT, pour avoir accepté de
juger cette thèse, pour leurs remarques pertinentes et leurs questions très intéressantes.
Je tiens aussi à adresser un grand merci à Sébastien MUSTIERE pour la qualité de son
co-encadrement, ses multiples relectures de mes articles et bien évidemment de ce rapport de
thèse, ses conseils avisés et le soutien qu’il m’a apporté. Je lui témoigne tout mon respect et
ma gratitude.
Je souhaite aussi remercier l'ensemble des collègues du laboratoire COGIT que j’ai
côtoyés pendant trois ans. J’ai passé de très bons moments et j’ai beaucoup apprécié les divers
échanges tant au niveau professionnel qu’au niveau personnel, leur gentillesse, leur bonne
humeur. J’ai une pensée particulière pour mes collègues de bureau Cécile, Elisabeth et
Laurence. Je leurs remercie pour leur gentillesse, leurs mots d’encouragement et leurs
conseils.
Je ne peux pas oublier mes collègues sportifs et amis Dominique, Corina, Elodie,
Marie-Lise, Maryse et Patrick, avec qui j’ai partagé de bons moments en faisant le tour du
bois de Vincennes ou de la gymnastique. Ces parenthèses sportives ont été souvent une source
d’inspiration pour la thèse.
Je voudrais adresser un grand merci à mes relecteurs Olivier, Christian, Elodie,
Laurence et Sidonie.
Je remercie également ma famille et ma belle-famille pour leur aide et leur soutien.
Enfin, MERCI à toi Olivier, pour ta patience, ton soutien sans faille, ton aide, ton
écoute et surtout pour tout ce que tu m’apportes au quotidien.

5
tel-00469407, version 1 - 1 Apr 2010 6
tel-00469407, version 1 - 1 Apr 2010Résumé
De nos jours, il existe de nombreuses bases de données géographiques (BDG) couvrant le
même territoire. Les données géographiques sont modélisées différemment (par exemple une
rivière peut être modélisée par une ligne ou bien par une surface), elles sont destinées à
répondre à plusieurs applications (visualisation, analyse) et elles sont créées suivant des
modes d’acquisition divers (sources, processus). Tous ces facteurs créent une indépendance
entre les BDG, qui pose certains problèmes à la fois aux producteurs et aux utilisateurs.
Ainsi, une solution est d’expliciter les relations entre les divers objets des bases de
données, c'est-à-dire de mettre en correspondance des objets homologues représentant la
même réalité. Ce processus est connu sous le nom d’appariement de données géographiques.
La complexité du processus d’appariement fait que les approches existantes varient en
fonction des besoins auxquels l'appariement répond, et dépendent des types de données à
apparier (points, lignes ou surfaces) et du niveau de détail. Nous avons remarqué que la
plupart des approches sont basées sur la géométrie et les relations topologiques des objets
géographiques et très peu sont celles qui prennent en compte l’information descriptive des
objets géographiques. De plus, pour la plupart des approches, les critères sont enchaînés et les
connaissances sont à l’intérieur du processus.
Suite à cette analyse, nous proposons une approche d’appariement de données qui est
guidée par des connaissances et qui prend en compte tous les critères simultanément en
exploitant à la fois la géométrie, l’information descriptive et les relations entre eux. Afin de
formaliser les connaissances et de modéliser leurs imperfections (imprécision, incertitude et
incomplétude), nous avons utilisé la théorie des fonctions de croyance [Shafer, 1976].
Notre approche d’appariement de données est composée de cinq étapes : après une
sélection des candidats, nous initialisons les masses de croyance en analysant chaque candidat
indépendamment des autres au moyen des différentes connaissances exprimées par divers
critères d’appariement. Ensuite, nous fusionnons les critères d’appariement et les candidats.
Enfin, une décision est prise.
Nous avons testé notre approche sur des données réelles ayant des niveaux de détail
différents représentant le relief (données ponctuelles) et les réseaux routiers (données
linéaires).

Mots-clés : appariement, données géographiques, fusion, connaissances, imperfection
7
tel-00469407, version 1 - 1 Apr 2010Abstract
Nowadays, there are many geographic databases, (GDB), covering the same reality. The
geographical data are represented differently (for example a river can be represented by a line
or a polygon), they are used in different applications (visualisation, analysis) and they are
created using various modes of acquisition (sources, processes). All these factors create
independence between GDB, which causes problems for both producers and users.
Thus, a solution is to clarify the relationships between various database objects, i.e. to
match homologous objects, which represent the same reality. This process is known as spatial
data matching.
Because of the complexity of the matching process, the existing approaches depend on the
types of data (points, lines or polygons) and the level of detail of the GDB. We realised, that
most of the approaches are based on the geometry and the topology of the geographical
objects, and very few approaches take into account the descriptive information of
geographical objects. Besides, for most approaches, the criteria are applied one after the other
and knowledge is contained within the process.
Following this analysis, we proposed a matching approach that is guided by knowledge
and takes into account all criteria at the same time exploiting the geometry, descriptive
information and relations between geographical objects. In order to formalise knowledge and
model their imperfections (imprecision, uncertainty and incompleteness), we used the Belief
Theory [Shafer, 1976].
Our approach of the data matching is composed of five steps. After a selection of
candidates, the masses of beliefs are initialised by analysing each candidate separately from
the others using different knowledge expressed by various matching criteria. Then, the
matching criteria and candidates are fusioned. Finally, a decision is taken.
Our approach has been tested on real data having different levels of detail and representing
relief (data points) and road networks (linear data).

Keywords : matching, geographical data, fusion, knowledge, imperfection

8
tel-00469407, version 1 - 1 Apr 2010Table des matières
INTRODUCTION ..............................................................................................................24
A APPARIEMENT DE DONNEES GEOGRAPHIQUES ............................................32
A.1 L’APPARIEMENT, UN PROBLEME COMPLEXE ..............................................................32
A.2 L'APPARIEMENT, UN OUTIL POUR REPONDRE A PLUSIEURS BESOINS ..........................34
A.2.1 APPARIER POUR EVALUER LA QUALITE DES DONNEES GEOGRAPHIQUES.......................34
A.2.2 APPARIER POUR RECALER DES DONNEES GEOGRAPHIQUES..........................................36
A.2.3 APPARIER POUR METTRE A JOUR LES DONNEES GEOGRAPHIQUES.................................38
A.2.4 INTEGRATION DE BASES DE DONNEES GEOGRAPHIQUES HETEROGENES........................40
A.2.4.1 Pré-intégration ......................................................................................................41
A.2.4.2 Appariement des schémas et des données ..............................................................41
A.2.4.3 Intégration.............................................................................................................42
A.3 L’APPARIEMENT, UN OUTIL QUI DEPEND DES DONNEES GEOGRAPHIQUES ..................44
A.3.1 APPARIEMENT DE RESEAUX AU MEME NIVEAU DE DETAIL, APPROCHE DE [WALTER ET
FRITCH, 1999].......................................................................................................................44
A.3.2 APPARIEMENT DE RESEAUX A DES NIVEAUX DE DETAIL DIFFERENTS, APPROCHE DE
[MUSTIERE ET DEVOGELE, 2008]...........................................................................................46
A.3.3 APPARIEMENT DES JEUX DE DONNEES SURFACIQUES, APPROCHE DE [BEL HADJ ALI,
2001] 47
A.3.4 APPARIEMENT DE PLUS DE DEUX JEUX DE DONNEES, APPROCHE DE [SAMAL ET AL.,
2004] 48
A.4 CRITERES D’APPARIEMENT DE DONNEES ET LEUR COMBINAISON...............................49
A.4.1 DIFFERENTS CRITERES D’APPARIEMENT.....................................................................50
A.4.1.1 Critères géométriques............................................................................................50
A.4.1.2 Critères topologiques et de voisinage.....................................................................51
9
tel-00469407, version 1 - 1 Apr 2010A.4.1.3 Critères attributaires ..............................................................................................52
A.4.1.4 Bilan sur les critères d’appariement.......................................................................53
A.4.2 DIFFERENTES MESURES UTILISEES DANS LE PROCESSUS D’APPARIEMENT ....................54
A.4.2.1 Mesures comparant les géométries ........................................................................54
A.4.2.2 Evaluation de la ressemblance entre les toponymes ...............................................61
A.4.2.3 Evaluation de la ressemblance des concepts à travers la sémantique ......................63
A.4.2.4 Mesures utilisant les relations topologiques...........................................................64
A.4.3 LES ETAPES GENERALES DU PROCESSUS D’APPARIEMENT DE DONNEES GEOGRAPHIQUES
65
A.5 APPARIEMENT ET IMPERFECTION DANS LES DONNEES GEOGRAPHIQUES ...................70
A.6 CONCLUSION ET DEFINITION DU SUJET.......................................................................73
B IMPERFECTION, REPRESENTATION ET FUSION DES CONNAISSANCES...78
B.1 ANALYSE DES IMPERFECTIONS DES DONNEES GEOGRAPHIQUES.................................80
B.2 REPRESENTATION DE L'IMPERFECTION EN UTILISANT LA THEORIE DES FONCTIONS DE
CROYANCE ...........................................................................................................................82
B.2.1 MOTIVATION DU CHOIX DE LA THEORIE DES FONCTIONS DE CROYANCE.......................83
B.2.2 APERÇU SUR LES THEORIES DE L'INCERTAIN ...............................................................87
B.3 QUELQUES APPLICATIONS DE LA THEORIE DES FONCTIONS DE CROYANCE ................88
B.3.1 ANALYSE DE DONNEES ..............................................................................................89
B.3.2 TRAITEMENT D’IMAGE...............................................................................................90
B.3.3 GEOMATIQUE............................................................................................................91
B.4 CADRE GENERAL DE LA THEORIE DES FONCTIONS DE CROYANCE ..............................91
B.4.1 REPRESENTATION EXPLICITE DES CONNAISSANCES.....................................................92
B.4.2 INITIALISATION DES MASSES DE CROYANCE................................................................95
B.4.3 COMBINAISON DES SOURCES D’INFORMATION ............................................................96
B.4.4 ANALYSE ET REDISTRIBUTION DU CONFLIT.................................................................98
B.4.5 AFFAIBLISSEMENT DES SOURCES................................................................................99
B.4.6 DECISION................................................................................................................100
B.5 APPROCHES DES SOURCES SPECIALISEES..................................................................101
B.6 CONCLUSION ............................................................................................................103
10
tel-00469407, version 1 - 1 Apr 2010