Soutenance mémoire
Problématique
On peut décrire un paysage par les éléments qui le compose (tels que des parcelles agricoles, des routes, des bâtiments, des forêts. . .) et les relations qui les lient (distance, adjacence. . .). Le but du stage est d’identifier des profils caractéristiques de paysages propices à l’étalement urbain, i.e. la progression spatiale des surfaces artificialisées (routes, bâtiments. . .), pour expliquer l’urbanisation d’une région.
Pour cela, des cartes ont été obtenues par des méthodes de télédétection en 1992, 2000 et 2010 pour Lorient. La figure 1 correspond à une image de Lorient en 1992 avec analyse de l’occupation du sol (les surfaces en rouge sont celles identifiées comme étant du bâti). Une analyse diachronique des images identifie les parcelles cadastrales de 2000 comme positives ou négatives selon que l’on ait observé ou non un étalement urbain entre 2000 et 2010. On cherche à apprendre à partir de ces cartes comment classifier n’importe quel nouvel exemple : sur une carte a priori inconnue, y aura-t-il étalement urbain dans les années à venir ?
Nous avons donc un problème d’apprentissage supervisé. De nombreuses techniques existent pour les données qui se présentent sous forme de liste d’attributs, mais les cartes ne sont pas réductibles à de telles structures de données : il y aurait une trop grande perte d’information à utiliser un nombre fixe d’attributs pour décrire une carte.
Un premier moyen de représenter des données spatiales est d’utiliser des graphes étiquetés de manière à laisser en évidence la caractéristique spatiale (par exemple, un nœud peut être étiqueté par son type, c’est-à-dire s’il représente une route, un bâtiment, etc., et une arête par une précision sémantique de la relation qui lie deux objets spatiaux, comme l’adjacence). Cette structure de graphe peut être étendue en incluant un certain nombre de relations observables, voire en utilisant un modèle purement relationnel, très expressif, utilisant des relations implicites (par exemple, en composant des relations).
Le but est non seulement d’obtenir un classifieur qui prédit si une zone sera urbanisée ou non, mais aussi que l’on puisse comprendre la décision dudit classifieur, que l’on puisse l’interpréter pour expliquer l’étalement urbain.
Ainsi, ce qu’on appellera l’interprétabilité du modèle doit être un critère pour le choix de l’approche retenue.
Approches
La problématique suggère la recherche d’une solution donnant des résultats interprétables facilement. Les solutions étudiées dans la littérature en amont du stage sont donc mentionnées dans cette section selon le pouvoir d’interprétabilité dont elles sont dotées. Les graphes étant une forme plus simple que la représentation logique, on mentionne donc en premier les travaux sur les graphes, dont les techniques de fouille, l’utilisation de méthodes à noyau pour graphes et des modèles d’arbres de décision adaptés aux graphes, avant d’étudier le cas de la programmation logique inductive.
Méthodes de fouilles de motifs pour caractériser les graphes
La fouille de données consiste à chercher des caractéristiques fréquentes dans le jeu de données, ces caractéristiques pouvant être utilisées a posteriori pour discriminer les données. Si les données sont sous forme de graphes, on peut, par exemple, chercher les sous-graphes fréquents.
Dans le domaine de la fouille de graphes, il existe quelques travaux qui se sont intéressés à la prise en compte d’une information spatiale.
Apriori-based Graph Mining (AGM) [19] est une adaptation de l’algorithme Apriori pour la fouille de graphes. Apriori est un algorithme de fouille de données qui extrait des règles d’associations fréquentes. AGM permet d’extraire des sous-graphes fréquents et des règles d’associations entre ceuxci (par exemple, la présence d’un motif implique la présence d’un autre).
Il s’est révélé efficace (relire l’article pour plus de précision) sur une étude de composés moléculaires. (reciter l’article ? ou ne le citer qu’à la fin de ce paragraphe ?)
La géométrie étant une information de nature spatiale, on peut citer les travaux portant sur les graphes géométriques (les nœuds ont des coordonnées, donc des configurations géométriques sont présentes) tels que ceux de M. Kuramochi et G. Karypis [20], et H.Arimura, T. Uno et S. Shimozono [4]. M. Kuramochi et G. Karypis ont développé un algorithme, gFSG, également inspiré d’Apriori qui recherche les sous-graphes géométriques fréquents, autorisant les transformations simples (translations, rotations, changements d’échelle) et en admettant une tolérance sur la mesure de similarité. Il peut être utilisé avec de très grandes bases de données de graphes représentant notamment des données spatiales.
H.Arimura, T. Uno et S. Shimozono ont conçu un algorithme ne devant retenir que les sous-graphes géométriques de taille maximale, gFSG présentant pour eux le risque de trouver trop de sous-graphes.
J. Huan et al. [18] ont une approche plus orientée théorie de l’information. Ils définissent une information mutuelle entre deux graphes qui leur permet d’introduire la notion de sous-graphe k-cohérent : tout sous-graphe de taille k dont l’information mutuelle avec le graphe d’origine est supérieur à un seuil strictement positif. Le but devient alors d’extraire tous les sous-graphes kcohérents. À l’aide de SVM (Support Vector Machines, cf. 2.2) pour classifier des familles de protéines, leur approche donne de bons résultats.
Arbres de décision
Les arbres de décision sont des classifieurs discriminants facilement interprétables par l’être humain : le principe est de faire suivre une série de tests, hiérarchiquement ordonnés par un arbre, à l’objet considéré en empruntant le chemin (partant de la racine) correspondant aux résultats de ces tests pour finalement arriver à une feuille qui donne sa classe (ici, un test correspond à la présence d’un sous-graphe).
L’apprentissage d’arbre de décision consiste à diviser récursivement, et le plus efficacement possible, les exemples de l’ensemble d’apprentissage par des tests jusqu’à n’avoir plus que des sous-ensembles d’exemples tous (ou presque) de la même classe.
Dans toutes les méthodes, trois opérateurs sont majeurs :
– décider si un nœud est terminal (i.e. s’il peut être étiqueté comme une feuille de l’arbre).
– si un nœud n’est pas terminal, lui associer un test
– si un nœud est terminal, lui associer une classe
La sélection du test associé à un nœud est une étape essentielle. Dans le cas général des données structurées sous forme de liste d’attributs, cela correspond à trouver un attribut de partage. On utilise alors une fonction d’évaluation qui favorise les attributs discriminants. Cette fonction mesure le gain en information des attributs en utilisant en général des critères statistiques comme l’entropie.
GBI (Graph-Based Induction) est une technique d’apprentissage efficace qui extrait des motifs (sous-graphes) fréquents sur des graphes de manière gloutonne. Il est possible de construire en suivant cette approche des arbresde décision pour graphes ([14], [25]).
Programmation Logique Inductive
La PLI [24] est une technique d’apprentissage supervisé qui permet d’induire des hypothèses, ou règles, à partir d’exemples. Ces exemples sont étiquetés positifs ou négatifs selon qu’ils représentent ou non des observations du concept à inférer. La PLI permet en particulier de dépasser certaines limites des formalismes de représentation des connaissances dans les systèmes d’apprentissage en utilisant la logique du premier ordre. Cette modélisation permet de rendre compte plus naturellement des relations entre objets.
La PLI met en œuvre l’induction en logique des prédicats qui est utilisée comme langage de représentation des exemples (faits Prolog) et des hypothèses (clauses de Horn). L’inférence de nouvelles règles correspond à une recherche de clauses dans un espace organisé selon une relation de généralité. Les algorithmes de recherche descendante, comme Foil, partent d’une clause générale vers des clauses plus spécifiques en utilisant des opérations comme l’ajout de littéraux à la clause de départ ou l’application de substitution pour transformer des variables en constantes ou pour unifier plusieurs variables. Les clauses ainsi générées sont ensuite testées sur les exemples de façon à généraliser le maximum d’exemples positifs et peu ou pas d’exemplesnégatifs.
En PLI, la taille de l’espace de recherche rend nécessaire l’utilisation d’heuristiques afin de guider le parcours de l’espace au cours de la recherche.
Un type d’heuristique très utilisé concerne les fonctions d’évaluation, qui mesure en quelque sorte l’utilité de chaque clause examinée. L’utilité d’une hypothèse peut s’exprimer par la quantité d’information apportée, par la compression de la base de connaissance réalisée ou par son pouvoir de discrimination comme l’heuristique Gain de Foil (First-Order Inductive Learner ).
Matériel et méthode
L’approche retenue pour le stage est une adaptation de UnMASC [13] à notre problématique. Deux critères, l’expressivité de la méthode (surtout avec l’introduction d’agrégats) et son interprétabilité, ont conduit à ce choix.
Le processus de parallélisation peut aussi permettre d’alléger les temps de calcul.
Dans la suite de cette section, on détaillera la génération de la base d’exemples à partir des données utilisées, des “cartes” de Lorient de 2000et 2010 traitées et annotées, puis on expliquera l’algorithme d’inférence derègles.
Construction d’un jeu d’apprentissage
Afin de répondre au problème, il est nécessaire d’obtenir des données et de les structurer de manière à pouvoir les traiter. Cette section explique l’origine de nos cartes (images de télédétection) et la construction d’un jeu d’exemples de classification.
Sources et format d’origine
Les données sont issues d’images obtenues par télédétection de la ville de Lorient en 2000 et 2010. Ces données ont été acquises et traitées par le laboratoire PSN dans le cadre du projet PayTal (www.paytal.fr).
Ces images sont analysées pour décomposer les différentes occupations du sol. Onze catégories sont distinguées : sol artificiel, voie de communication, eau, forêt de feuillus, forêt de conifères, zones agricoles, végétation seminaturelle/prairie, sol nu, kaolin/sol nu clair, plage, estran. La figure 5(a) illustre le résultat de l’analyse de la décomposition du sol sur une carte de Lorient en 2000 (les bâtiments, en rouge, sont concentrés au centre de l’image).
Les images sont ensuite vectorisées à l’aide du cadastre de 2010. À chaque parcelle ainsi délimitée est attribuée son occupation du sol selon l’occupation majoritaire du sol dans la parcelle cadastrale considérée. La figure 5(b) montre le résultat de ce découpage par rapport à la figure 5(a). Le procédé donne aux parcelles un degré d’“urbanisation” compris entre -1 et 1 portant sur la différence de surface urbanisée entre 2000 et 2010 :
Ce degré donne la classe de la parcelle : une parcelle de 2000 est classée positivement (i.e. considérée comme urbanisée en 2010) si d urb > 0. La figure 5(c) illustre l’attribution des classes sur des parcelles de Lorient. Le degré est normalisé pour être inchangé selon l’échelle considérée (car on considère des nombres de pixels). La normalisation choisie évite d’avoir des valeurs considérées comme nulles car trop petites (par exemple si la normalisation était faite par rapport à l’aire de la parcelle).
Construction d’un graphe
À partir des opérations précédentes, un grand graphe est construit : les nœuds représentent les parcelles et sont munis des attributs déjà calculés (classe d’occupation du sol, urbanisation positive/négative, attributs statuant si la parcelle est un parc naturel, une zone commerciale ou une école), ainsi que des attributs ajoutés tels que le périmètre et l’aire de la parcelle.
Les arêtes désignent les relations entre les parcelles : adjacence, distance entre les barycentres des parcelles. . .).
Cette étape limite l’approche à l’utilisation de relations binaires.
La figure 6 montre un exemple de construction de graphe. Les nœuds sont situés aux centroïdes des parcelles associées. Seule la relation d’adjacence est exprimée par les arêtes. Bien que ce ne soit pas représenté, les nœuds sont étiquetés notamment avec le type d’occupation du sol de la parcelle (couleur de la parcelle).
Construction de la base d’exemples
Le graphe construit précédemment ne peut pas être utilisé directement pour la classification. Pour l’apprentissage supervisé, il est nécessaire de construire un ensemble de zones dont certaines représentent des exemples positifs et d’autres des exemples négatifs. Deux questions se posent alors : comment segmenter le zones et attribuer une classe (positive ou négative) aux zones obtenues.
Plusieurs types d’extraction de zones ont été envisagés :
– faire un pavage de l’espace, et définir une zone comme l’ensemble des parcelles inclues dans un élément du pavage.
– sélectionner une parcelle et considérer toutes les parcelles situées dans un certain rayon du centre de la parcelle sélectionnée.
– sélectionner un point et considérer toutes les parcelles situées dans un certain rayon de ce point.
Dans tous les cas, on obtient pour chaque zone un sous-graphe dont les nœuds sont les nœuds associés aux parcelles que la zone contient et les arêtes sont toutes les arêtes entre les différentes paires de nœuds du sous-graphe qui sont définies dans le graphe principal.
Différentes possibilités ont été évoquées pour l’attribution des classes aux zones ainsi choisies :
Algorithme d’inférence de règles
Les règles sont générées de manière incrémentale, littéral par littéral.
Le choix du littéral à ajouter à la règle en cours se fait par génération des littéraux possibles, selon les prédicats disponibles (P dans l’algorithme 2) et les variables existantes dans la règle en cours, puis l’un d’eux est sélectionné selon le gain apporté. Afin de caractériser les instances, au moins l’un des paramètres d’un nouveau littéral est une variable déjà utilisée dans un des littéraux de la règle.
En Prolog, l’ordre des littéraux dans la conjonction importe : le système cherchera à trouver des valeurs pour les variables d’abord pour satisfaire le premier littéral de la règle avant de satisfaire la suite de la règle de la même manière. L’objectif est d’abord de trouver des règles pour caractériser les instances. Ainsi, toute règle commence par le littéral instance appliqué sur une variable (ligne 3 de l’algorithme 2). Au cours de l’algorithme, on manipule un ensemble E qui contient l’ensemble des séquences de termes qui peuvent être paramètres du littéral à ajouter en queue de règle : chacune de ces séquences de termes contient au moins une variable qui apparait déjà dans la règle, les autres éléments pouvant être des variables déjà présentes ou non dans la règle et des constantes.
Si n est l’arité maximale des prédicats, les séquences de E contiennent 1 à n termes. E est initialisé (ligne 5) avec la séquence de longueur 1 {G} et des séquences contenant G et des constantes. L’opération en ligne 6 à augmenter E des tuples contenant des variables que l’on peut introduire. Lors de la première extension, la séquence de taille n {G, X0, . . . , X n−1 } (l’ordre importe, ce sont des paramètres de fonctions booléennes) est notamment ajoutée. Cet ensemble est augmenté à chaque fois qu’au moins une nouvelle variable est effectivement introduite dans la règle.
Outils et implémentation
Afin de pouvoir mettre en place l’architecture parallèle de l’algorithme, l’un des langages choisis est C++ en sa version C++11, munie d’une bibliothèque thread permettant une implémentation efficace simplement.
Afin de gérer la partie logique du travail, le langage Prolog intervient éga-17 lement naturellement. Il existe plusieurs implémentations de Prolog. Devant le besoin d’inclure du code Prolog à l’intérieur du code C++, l’implémentation choisie devait permettre une interface entre C++ et Prolog. Trois outils, SICStus Prolog, SWI-Prolog et YAP (Yet Another Prolog), ont été testés.
Les critères de choix ont été le respect d’une norme Prolog (ISO-Prolog, que les trois implémentations testées reconnaissent), les performances du système, la disponibilité (licence publique/privée) et l’interfaçage avec le C++[10]. Ainsi, pour ces trois derniers points, le choix s’est porté sur YAP. Malheureusement, YAP supporte mal d’être utilisé en parallèle. Il n’y a donc pas, au jour de la date de rendu de ce rapport, d’implémentation parallèle fonctionnelle. Néanmoins, l’implémentation série est fonctionnelle.
Les agrégats n’ont pas encore été effectivement implémentés. Un moyen de les considérer serait de les définir dans Prolog à l’aide du prédicat setof qui permet d’obtenir les substitutions d’un ensemble de variables précisées qui permettent de vérifier une règle. L’utiliser permet de réaliser un agrégat de variables sur lesquelles on peut faire diverses opérations. Le code 3 montre un moyen de définir le prédicat distance moyenne : définition de la moyenne d’une liste (lignes 1–3), redéfinition du prédicat permettant d’obtenir le ne élément d’une liste (lignes 5–6), définition d’un prédicat permettant d’obtenir la liste des n es éléments des listes d’une liste de listes (lignes 8–9) et (enfin !) définition du prédicat de distance moyenne. Afin de gérer les instances qu’il faut encore considérer lors de la construction de nouvelles règles, à l’initialisation de notre programme, un fait do(gX) est enregistré pour chaque instance gX . Pour retirer les exemples positifs des exemples à traiter (ligne 16 de l’algorithme 2) après la finalisation d’une règle r, le fait do(gX) est annulé pour toutes les instances positives qui vérifient r.
Notre programme ne garde pas en mémoire l’ensemble des tuples qui vérifient une règle r mais garde néanmoins trace des instances qui vérifient r. Chaque règle est identifiée par un indice qui lui est propre. À chaque fois qu’il est établi qu’une instance g i vérifie la règle r j d’indice j , le fait checkrule(gi,rj) est enregistré. Le prédicat checkrule(G, rj ), placé en tête d’une règle fille de r j , permet au système Prolog d’unifier l’identifiant de sous-graphe G uniquement avec des identifiants de sous-graphe qui vérifient r j . Ce prédicat est également utilisé au point précédent pour rechercher directement les instances positives qui vérifient la règle nouvellement créée.
Quelques règles
Avec les prédicats de 4.1, des règles peuvent être générées à partir d’un jeu d’exemples. Néanmoins, les résultats obtenus ne sont pas très satisfaisants dans l’ensemble. Une règle générée couvre souvent un seul ou deux exemples positifs. Les dernières règles générées couvrent parfois beaucoup d’exemples négatifs. Par exemple, pour un jeu de 200 instances, dont 70 positives, 41 règles ont été générées et la dernière règle couvrait 70 instances négatives pour 6 instances positives alors non couvertes par les règles précédentes.
Quelques améliorations sont possibles pour obtenir des résultats satisfaisants. Plusieurs attributs mentionnés en section 3 (la parcelle est-elle une école ? un centre commercial ? un parc naturel ?) pourraient être utilisés à l’aide de prédicats adaptés. Aucun agrégat n’a encore été introduit. L’ensemble E de l’algorithme 2 est très général, on peut tenter d’avoir un ensemble de suite de termes admissibles propre à chaque littéral. Les constantes ne devraient pas être statiques mais dépendre des données (par exemple, lorsqu’un prédicat, comme perimeter introduit une variable numérique, analyser les différentes valeurs qui peuvent être prises en fonction de la classe de l’instance). < n’est jamais sélectionné. On peut former des littéraux doubles en associant des prédicats introduisant des variables numériques et le prédicat de comparaison <. Les contraintes empêchant l’éventuelle sélection d’une règle sont peut-être trop fortes et méritent peut-être d’être un peu détendues (par exemple, autoriser que les tuples vérifiant une règle rgm grandmère d’une règle r sont extensibles en tuples vérifiant r, mais l’interdire pour la règle arrière-grand-mère).
Quelques chiffres
L’utilisation mémoire et le temps d’exécution ont été testés pour les conditions de 4.1, de 10 à 200 instances dans le jeu d’exemples (par pas de de 10) et un seuil de distance maximale entre les centroïdes des parcelles et le centroïde de la parcelle centrale compris entre 500 et 4000 (par pas de 500) (plus le seuil est élevé, plus la quantité d’information d’un exemple sera conséquente). Une dizaine d’heures de calcul sur un ordinateur disposant de 4Go de mémoire vive et d’un processeur cadencé à 2GHz ont été nécessaires afin d’obtenir ces mesures. Pour des raisons de lisibilités, seules quatre courbes sont présentes sur chaque graphique.
Conclusion
Les paysages sont des organisations spatiales d’éléments paysagers : ils peuvent être représentés par des graphes ou par la liste des relations qui les décrit. Lors de ce stage, une approche basée sur la PLI a été choisie afin de répondre à un problème d’apprentissage supervisé : peut-on caractériser les paysages qui vont subir une urbanisation dans l’avenir ? Ce choix a été fait en fonction des critères d’expressivité et d’interprétabilité du modèle. Un algorithme proche de Foil a été implémenté afin de générer un ensemble de règles répondant à la problématique sur des jeux d’exemples obtenus grâce à une analyse diachronique de cartes de Lorient entre 2000 et 2010.
Ces cartes ont subi différents traitements (analyse de la composition du sol, segmentation en parcelles, segmentation en sous-graphe et conversion enprogramme Prolog) pour servir de jeux d’exemples.
Malgré des performances techniques satisfaisantes (temps de calcul et occupation mémoire), l’implémentation courante produit par contre des résultats peu expressifs à cause du peu de prédicats que l’on admet dans les règles. Il manque notamment les prédicats-agrégats qui résument des situations, par exemple en imposant un minorant d’un ensemble de distance.
La gestion des prédicats s’appliquant sur des paramètres numériques est à améliorer. Il faut encore trouver un moyen de paralléliser l’implémentation malgré le support de Prolog choisi (YAP) afin d’avoir des temps de calculs encore meilleurs
|
Table des matières
1 Problématique
2 Approches
2.1 Méthodes de fouilles de motifs pour caractériser les graphes
2.2 Méthodes à noyaux spécifiques aux graphes
2.3 Arbres de décision
2.4 Programmation Logique Inductive
3 Matériel et méthode
3.1 Construction d’un jeu d’apprentissage
3.1.1 Sources et format d’origine
3.1.2 Construction d’un graphe
3.1.3 Construction de la base d’exemples
3.2 Inférence de règles
3.2.1 Définitions
3.2.2 Algorithme d’inférence de règles
3.3 Outils et implémentation
4 Expérimentations
4.1 Conditions
4.2 Quelques règles
4.3 Quelques chiffres
5 Conclusion
A Quelques rappels de logique pour la PLI
A.1 Définitions
A.2 Conventions de Prolog
