Extraction de connaissances à partir de grands graphes spatio-temporels – application à hydroécologi

When:
25/05/2021 – 26/05/2021 all-day
2021-05-25T02:00:00+02:00
2021-05-26T02:00:00+02:00

Offre en lien avec l’Action/le Réseau : – — –/– — –

Laboratoire/Entreprise : ICube, Strasbourg
Durée : 3 ans
Contact : florence.leber@engees.unistra.fr
Date limite de publication : 2021-05-25

Contexte :
aloriser les grandes masses de données spatio-temporelles disponibles en Sciences de l’environnement est crucial. Ceci nécessite de concevoir et développer de nouvelles approches innovantes aptes à traiter conjointement les aspects spatiaux et les aspects temporels, ce qui n’est que peu le cas avec les méthodes actuelles. Si les graphes, outils puissants à la fois théoriquement et méthodologiquement, sont utilisés pour modéliser des phénomènes temporels ou spatiaux, les méthodes actuelles de fouille, d’analyse et d’extraction de connaissances n’exploitent, en général, qu’une seule dimension de l’information, spatiale versus temporelle. Cela implique souvent une perte de précision et possibilité d’interprétation des résultats [1]. Notre équipe travaille depuis de nombreuses années en collaboration avec des hydro-écologistes sur l’évaluation de la qualité des hydro-écosystèmes. Ce travail a été l’objet de plusieurs projets, dont le projet ANR Fresqueau 2011-2015 (engees-fresqueau.unistra.fr). Nous travaillons également en étroite collaboration avec le SERTIT (Service Régional de Traitement d’Image et de Télédétection, sertit.u-strasbg.fr), dont le but est de produire de l’information géographique à partir des images satellites. Cette collaboration a également fait l’objet de plusieurs projets comme par exemple le projet R&T A2CNES (2017-2018) financé par le CNES. Au travers de ces différentes collaborations, nous avons pu manipuler et fouiller des données nombreuses et variées, tant en termes d’informations apportées de que formats de données. Afin d’extraire des connaissances pertinentes de ces données, en combinant à la fois les aspects spatiaux et temporels, nous nous intéressons maintenant au modèle des graphes spatio-temporels [2].

Sujet :
L’objectif général de la thèse est d’étudier et développer des techniques pour extraire des connaissances à partir de grands graphes spatio-temporels. Différentes questions devront être abordées de manière itérative.
• Simplification : les graphes étant de grande taille, il sera nécessaire de les simplifier (par exemple, regrouper des sommets dans un super-sommet représentant l’évolution globale de cet ensemble de sommets [3]), de les segmenter, sur une base experte, ou de choisir une autre représentation plus synthétique, pour réduire leur taille et les exploiter ou les visualiser plus facilement.
• Recherche de motifs : il s’agira de rechercher des motifs spatio-temporels définis par un expert (par exemple une évolution temporelle typique de l’urbanisation pour un ensemble de parcelle voisines) ou faire apparaître des répétitions fréquentes dans un ou plusieurs graphes. La recherche de motifs pourra se faire de manière inexacte, en s’appuyant sur des distances d’édition de graphes [4] et/ou sur des méthodes de recherche récursives [5].
• Synthèse interprétable : il s’agira de coupler recherche de motifs et connaissances du domaine afin de synthétiser un graphe spatio-temporel par un graphe de motifs étiquetés, représentatifs de phénomènes intéressant l’expert.
• Généralisation : dans le graphe initialement simplifié, chaque sous-graphe correspondant à un motif pourra être analysé par les méthodes développées pour finalement obtenir une hiérarchie de graphes-motifs permettant de visualiser de plus en plus finement les phénomènes ayant eu lieu.
En conclusion, le pipeline générique développé visera à répondre à des problématiques actuelles liées à la valorisation de grandes masses de données spatio-temporelles en télédétection [6,7] et hydroécologie [8].

Références
[1] ATLURI, Gowtham, KARPATNE, Anuj, et KUMAR, Vipin. Spatio-temporal data mining: A survey of problems and methods. ACM Computing Surveys (CSUR), 2018, vol. 51, no 4, p. 83.
[2] DEL MONDO, Géraldine, RODRÍGUEZ, M. Andrea, CLARAMUNT, Christophe, et al. Modeling consistency of spatio-temporal graphs. Data & Knowledge Engineering, 2013, vol. 84, p. 59-80.
[3] NABTI, Chems Edinne. Subgraph Isomorphism Search In Massive Graph Data. 2017. Thèse de doctorat. Lyon.
[4] GAO, Xinbo, XIAO, Bing, TAO, Dacheng, et al. A survey of graph edit distance. Pattern Analysis and applications, 2010, vol. 13, no 1, p. 113-129.
[5] SHOKOUFANDEH, Ali, BRETZNER, Lars, MACRINI, Diego, et al. The representation and matching of categorical shape. Computer Vision and Image Understanding, 2006, vol. 103, no 2, p. 139-154.
[6] BHATT, Mehul et WALLGRÜN, Jan Oliver. Geospatial narratives and their spatio-temporal dynamics: Commonsense reasoning for high-level analyses in geographic information systems. ISPRS International Journal of Geo-Information, 2014, vol. 3, no 1, p. 166-205.
[7] LEBORGNE, Aurélie, MEYER, Adrien, GIRAUD, Henri, LE BER, Florence, MARC-ZWECKER, Stella. Un graphe spatio-temporel pour modéliser l’évolution de parcelles agricoles. p. 1-13, SAGEO, Nov 2019, Clermont-Ferrand, France
[8] NICA, Cristina, BRAUD, Agnès, LE BER, Florence. Exploring Heterogeneous Sequential Data on River Networks with Relational Concept Analysis. In 23rd International Conference on Conceptual Structures, Proceedings. Jun 2018, Edimbourg, United Kingdom.

Profil du candidat :
Master 2 en Informatique ou équivalent, 12 de moyenne minimum, très bon classement (selon critères de l’école doctorale)

Formation et compétences requises :
Formation en logique, graphes et programmation
Curiosité, capacité à appréhender différents domaines et à interagir avec les experts de ces domaines

Adresse d’emploi :
ICube UMR 7357 – Laboratoire des sciences de l’ingénieur, de l’informatique et de l’imagerie
300 bd Sébastien Brant – CS 10413 – F-67412 Illkirch Cedex –