Mining recurrent patterns in a dynamic attributed Graph. : Application on aquaculture pond monitoring by satellite images.

Extraction des motifs récurrents dans un graphe dynamique attribué. : Application au suivi des bassins d' aquaculture en Indonésie. 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. Cependant, ces approches souffrent de plusieurs limitations lorsqu 'on traite des phénomènes spatio-temporels complexes. Ces domaines de motifs ne prennent pas en compte 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 proposons 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 des sous-ensembles d'attributs associés à des sous-ensembles de nœuds. 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 (réseau de co-auteurs DBLP et données de trafic aérien 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 poussée de notre approche sur les données du projet INDESO (suivi de bassins aquacoles en Indonésie par imagerie satellitaire). Pour cela, un processus d' extraction de connaissances (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. Ce processus s'appuie tout d'abord sur une méthode automatique et robuste pour extraire les bassins d'aquacoles à partir d'images satellitaires à faible contraste. Ensuite, il utilise des méthodes d'extraction de motifs fréquents afin de mettre en avant certaines pratiques des fermiers. Pour cela, nous avons appliqué dans un premier temps un algorithme d'extraction de motifs séquentiels pour analyser l'évolution des bassins dans le temps et comprendre les pratiques des fermiers. En parallèle nous avons aussi appliqué notre algorithme RPMiner, qui prend en compte à la fois les dimensions spatiales et temporelles. Les motifs extraits ont été interprétés par des experts en aquaculture. Les résultats obtenus ont permis de confirmer certaines pratiques et d'en mettre en avant d'autres.