« Mining recurrent petterns in a dynamic attributed graph. Application to aquaculture Pond Monitoring by satellite images »

Soutenance de thèse de Cheng Zhi  (EDP-UNC, IFREMER) ouverte à tous.

Résumé

Dans cette thèse, nous nous sommes intéressés à l’analyse de données spatio-temporelles. Plusieurs algorithmes de fouille de données ont été développés pour extraire des modèles locaux (appelés aussi "motifs") tels que les motifs séquentiels ou les sous-graphes dynamiques pour analyser de telles données. Cependant, ces approches souffrent de plusieurs limitations lorsqu’on traite des phénomènes spatio-temporels complexes. Ces exemples de motifs ne prennent pas toutes les interactions spatio-temporelles possibles ou ne considèrent que des informations limitées sur les objets étudiés. Par exemple, les motifs séquentiels se concentrent sur les évolutions temporelles sans tenir compte des évolutions spatiales.

En outre, la plus part des algorithmes d’extraction de sous-graphes étudient des graphes dynamiques labélisés. Cependant, ils ne considèrent qu’un seul attribut par nœud et ignorent les autres caractéristiques des objets étudiés. Dans ce manuscrit, nous avons proposé d’étudier un graphe dynamique attribué pour fournir une représentation plus riche des phénomènes spatio-temporels. L’extraction de motifs dans des graphes dynamiques attribués est une tâche particulièrement complexe car la structure du graphe, les nœuds et les attributs associés à chaque nœud peuvent changer dans le temps. Pour cela, nous avons défini un nouveau domaine de motifs appelé motifs récurrents. Ces motifs, qui sont des séquences de sous-graphes connexes, représentent des évolutions récurrentes de sous-ensembles de nœuds associés à des sous-ensembles d’attributs. Pour extraire ces motifs, nous avons développé un nouvel algorithme, appelé RPMiner, utilisant une stratégie originale basée sur des intersections successives de composantes connexes apparaissant dans la séquence. Nous avons utilisé plusieurs contraintes pour réduire l’espace de recherche et rendre le calcul possible. Une étude expérimentale sur des jeux de données synthétiques et réels (données DBLP et données US Flight) montre la généricité de notre approche, l’intérêt des motifs extraits et l’efficacité de notre algorithme.

Nous avons effectué également une évaluation expérimentale de notre approche sur les données du projet INDESO. Pour cela, un processus KDD complet a été développé (du prétraitement des données à la visualisation et à l’interprétation des résultats). Il vise à mieux comprendre les pratiques des fermiers pour un développement durable de ces ressources côtières en Indonésie. Nous avons proposé tout d’abord une méthode automatique et robuste pour extraire des bassins d’aquacoles à partir d’images satellitaires à faible contraste. Nous avons appliqué ensuite un algorithme d’extraction de motifs séquentiels pour étudier les évolutions des bassins dans le temps et comprendre les pratiques des fermiers. En parallèle, nous avons également appliqué notre algorithme RPMiner, qui prend en compte à la fois les dimensions spatiales et temporelles. Enfin, nous avons pu donner des interprétations des motifs extraits (avec l’aides des experts an aquaculture) et avons comparé les résultats obtenus par ces deux approches.

Composition du jury de thèse

Sandra Bringay, Université de Montpellier
Philippe Fournier-Viger, Harbin Institute of Technology, Shenzhen Chine
Christophe Eugène Menkes, IRD Nouméa
Hugues Lemonnier, Ifremer Nouméa
Frédéric Flouvat, Université de la Nouvelle-Calédonie
Nazha Selmaoui-Folcher, Université de la Nouvelle-Calédonie

Contact

Zhi CHENG

zhi.cheng@etudiant.unc.ncL’article « Mining recurrent petterns in a dynamic attributed graph. Application to aquaculture Pond Monitoring by satellite images » est apparu en premier sur Université de la Nouvelle-Calédonie.