! ! ! ! ! ! ! ! ! ! ! ! Actes de l’atelier! ! ANAlyse de données ENVironnementales ! Approches mises en œuvre et retours d’expérience! ! ! ! ! conjointement au ! dix-neuvième congrès national sur la Reconnaissance de Formes et l'Intelligence Artificielle (RFIA'14)! ! ! ! ! Rouen - 1er Juillet 2014! ! ! ! ! ! ! ! ! ! ANAlyse de données ENVironnementales Approches mises en œuvre et retours d’expérience Organisation : Florence Le Ber, Université de Strasbourg/ENGEES, ICube Maguelonne Teisseire, Irstea, TETIS Comité de programme : Agnès Braud - ICube, Strasbourg Maroua Bouzid - Greyc, Caen Sandra Bringay - LIRMM, Montpellier Xavier Dolques - ICube, Strasbourg Jérôme Gensel - LIG, Grenoble Thomas Guyet - AgroCampus / Irisa, Rennes Dino Ienco - TETIS, Montpellier Medhi Kaytoue - LIRIS, Lyon Eric Kergosien - LIRMM / TETIS, Montpellier Christine Largouet - AgroCampus / Irisa, Rennes Thérèse Libourel - Espace-dev, Montpellier Véronique Masson - Irisa, Rennes Francois Pinet - IRSTEA Motive, Clermont-Ferrand Cyril de Runz - CReSTIC, Reims Nazha Selmaoui-Folcher - PPME, Nouméa Rémy Thibaud - IRENav, Brest Site web : Hugo Alatristas Salas - LIRMM, Montpellier Contenu de l'atelier Conférence invitée Marie-Odile Cordier : « Exploiter les résultats de simulation : un enjeu pour les modélisateurs et les décideurs » Articles Rouaa Wannous, Jamal Malki, Alain Bouju, Cecile Vincent : « Trajectory ontology inference over domain and temporal rules. Inference complexity analysis » Mickaël Fabrègue, Agnès Braud, Sandra Bringay, Florence Le Ber, Maguelonne Teisseire : « Recherche de motifs partiellement ordonnés clos discriminants pour caractériser l’état des milieux aquatiques » Antoine Cornuéjols, Antonin Duroy, Chantal Loyce, David Makowski, Christine Martin, Aurore Philibert : « Recherche de documents par apprentissage artificiel pour une méta-analyse sur les émissions d’un gaz à effet de serre » Thomas Guyet, Yves Moinard, René Quiniou : « Simuler l’assolement d’un paysage par reproduction des structures locales » ! ! Exploiter les résultats de simulation : un enjeu pour les modélisateurs et les décideurs Marie-Odile Cordier IRISA, Université de Rennes 1 [email protected] Résumé Dans cet exposé, je présenterai les travaux que nous avons fait en collaboration avec l'Inra depuis une quinzaine d'années, en insistant sur l'importance des modèles bien sûr, mais aussi des outils permettant d'exploiter les résultats obtenus dans un contexte d'aide à la décision. Je parlerai un peu plus précisément des travaux suivants : 1. Le projet Sacadeau s'appuie sur un modèle décisionnel couplé à un modèle biophysique dans le contexte du transfert de désherbants dans un bassin versant breton. La contribution principale est l'utilisation d'outils d'apprentissage symbolique pour explorer la base des résultats de simulations et en inférer des recommandations d'action pour minimiser les nuisances environnementales . 2. Les projets Ecomata et Patur'mata s'appuient sur un modèle de haut niveau décrit par un système à événements discrets et utilisent les outils de model-checking efficaces pour répondre à des requêtes sur ce type de modèles. Ceci permet d'évaluer des scénarios de type simulation prédictive (que se passera-t-il si on agit de telle ou telle manières) ou normative (quels chemins pour arriver à un but donné). Ceci a été appliqué à la gestion d'un écosystème halieutique et à la gestion du pâturage dans une exploitation. 3. Enfin, le projet N-Catch concerne l'exploitation des données de simulation de TNT (modèle spatialement explicite des flux de nitrates à l'échelle du bassin versant). Il propose l'utilisation d'un entrepôt de données qui permet l’agrégation et la visualisation des données de simulation. A partir de là il est possible de faire le l'aide à la décision sur la base d'analyses multicritères. ! Trajectory ontology inference over domain and temporal rules. Inference complexity analyzing Rouaa Wannous1 1 Jamal Malki1 Alain Bouju1 Cecile Vincent2 L3i laboratory , LIENSs laboratory, University of La Rochelle, France 2 LIENSs laboratory, University of La Rochelle, France {rwannous, jmalki, abouju, cvincent}@univ-lr.fr Abstract Capture devices rise a large scale trajectory data about moving object’s movements. These devices use different technologies like global navigation satellite system (GNSS), wireless communication, radio-frequency identification (RFID), and other sensors. Huge trajectory data are available. In this article, we are interested in these data, so we use an ontological data modeling approach to build a trajectory ontology. This ontology contains temporal concepts, so we map it to a temporal ontology. We present an implementation framework for declarative and imperative parts of ontology rules in a semantic data store. An inference mechanism is computed over these semantic data. The running time and memory of the inference increases very rapidly as a function of the data size. For this reason, we propose a two-tier inference filters on data. The primary filter analyzes the trajectory data considering all the possible domain constraints. The data analyzed are considered as the first knowledge base. These data is passed to the secondary filter. Then the latter computes the inference over the filtered trajectory data. The secondary filter results yield the final knowledge base where the user can query. Keywords Trajectory ontology modeling, Ontology inference, Temporal rules, Data filter algorithm. Résumé Les dispositifs de capture de trajectoires d’objets en mouvement produisent généralement des volumes de données très important. Ils se développent grâce á différentes technologies, telles que les systèmes de navigation globale par satellite (GNSS), les communications sans fil, l’identification par radio-fréquence (RFID) et d’autres types de capteurs. Nous nous intéressons dans cet article á ces larges volumes de données que nous organisons au sein de modèles ontologiques dans le but de construire une ontologie des trajectoires. Cette ontologie est interfacée avec une ontologie temporelle afin de gérer les concepts relatifs au temps. Nous présentons l’implémentation d’un framework pour les phases de déclaration et de mise en œuvre des règles au sein d’une base de données sémantiques. Un mécanisme d’inférence est lancé sur ces données sémantiques. Son temps d’exécution ainsi que sa charge en mémoire augmentent rapidement en fonction du volume de données. Afin de limiter ce problème, nous proposons un double filtre d’inférence sur les données. Le premier filtre analyse les données de trajectoire en prenant en compte toutes les contraintes de domaine possibles. Les données de sortie forment alors la première base de connaissances et sont transférées au deuxième filtre. Celui-ci effectue l’inférence sur ces données filtrées. Les données en sortie de ce second filtre forment la base de connaissances finales que l’utilisateur va pouvoir interroger. Mots Clef Modélisation de trajectoire, Règles temporelles, Inférence, filtrage de données. 1 Introduction Advances in information and communication technologies have encouraged collecting spatial, temporal and spatiotemporal data of moving objects [5]. The raw data captured, commonly called trajectories, traces moving objects from a departure point to a destination point as sequences of data (sample points captured, time of the capture). Raw trajectories don’t contain goals of traveling nor activities accomplished by the moving object. Large datasets need to be analyzed and modeled to tackle the user’s requirements. To answer these queries we need also to take into account the domain knowledge. This paper deals with marine mammals tracking applications, namely seal trajectories. Trajectory data are captured by sensors included in a tag glued to the fur of the animal behind the head. The captured trajectories consist of spatial, temporal and spatio-temporal data. Trajectories data can also contain some meta-data. These datasets are organized into sequences. Every sequence, mapped to a temporal interval, characterizes a defined state of the animal. In our application, we consider three main states of the seal : haulout, dive and cruise. Every state is related to seal’s activity. For example, a foraging activity occurs during dives. Our goal is to enrich trajectory data with semantics to extract more knowledge. In our previous work [15], we tackled trajectory data connected to other temporal and spatial source of information. We directly computed the inference over these data. The experimental results addressed the running time and memory problems over the ontology inference computation. Furthermore, we try to solve these problems by defining some domain constraints, time restrictions [9] and inference refinements [14]. The proposed refinements enhanced the inference computation, however, they do not definitely solve the inference problems. In the present work, we introduce a two-tier inference filters on trajectory data. In other words, two distinct operations are performed to enhance the inference : primary and secondary filter operations. The primary filter applies all the possible domain constraints over the captured data. So, the primary filter permits fast selection of the analyzed data to pass along to the secondary filter. The latter computes the inference over the data output of the primary filter. The global view of this work is detailed as the following steps : – Semantic trajectory data is an RDF dataset based on the ontology trajectory ; – For analyzing data, filtering or indexing could be applied. In our case, we carry out a place-of-interest process to analyze data. The analyzed data are stored in a knowledge repository ; – Secondary filter computes inferences over the data with the consideration of the domain knowledge ; – Semantic trajectory data and the new data inferred are stored in the knowledge repository ; This paper is organized as follows. Section 2 illustrates an overview of the ontological modeling approach used. This trajectory ontology contains temporal concepts, so Section 3 presents W3C OWL-Time ontology [7] which is mapped to our ontology. Section 4 details the implementation of the trajectory ontology, the domain ontology rules and the temporal rules. Section 5 addresses the complexity of the ontology inference over domain and temporal rules. Section 6 introduces the primary filter over trajectory data based on place-of-interest process. Section 7 evaluates the ontology inference over the filtered data. Section 8 summarizes recent work related to trajectory data modeling using ontology approach and some introduced solutions to tackle the problem of the inference complexity using data filtering. Finally, Section 9 concludes this paper. 2 2.1 Trajectory ontology modeling Trajectory domain ontology This paper considers trajectories of seals. The data comes from the LIENSs 1 (CNRS/University of La Rochelle) in collaboration with SMRU 2 . These laboratories work on marine mammals’ ecology. Trajectory data of seals between their haulout sites along the coasts of the English 1. http ://lienss.univ-larochelle.fr 2. SMRU : Sea Mammal Research Unit- http ://www.smru.stand.ac.uk Channel or in the Celtic and Irish seas are captured using GNSS systems. From the analysis of captured data, we define a seal trajectory ontology that we connect to the trajectory domain ontology. The trajectory domain ontology is our model used in many moving object applications. Details of the modeling approach is discussed in [11]. Figure 1 shows an extract of the seal trajectory ontology, called owlSealTrajectory. Table 1 gives a dictionary of its concepts. Thing Moving Object Domain Ontology Trajectory Domain Ontology hasTrajectory Mobile Object Trajectory hasSensor startPosition Sensor Position Sequence hasDeploy endPosition Deployment GeoSequence Seal Zone Dive Haulout Cruise Specific Sequence Summary CTD Seal Domain Ontology Seal Trajectory Ontology rdfs:subClassOf owl:objectProperty F IGURE 1 – Overview of the seal trajectory ontology 2.2 Seal trajectory ontology In this work, we propose a Semantic Domain Ontology (Figure 2) based on activities organized as general ones linked to trajectory, and a hierarchy of basic activities linked to sequences of the trajectory domain ontology. The Seal Domain Ontology (Figure 2) considers seal’s activities. According to the domain expert, the seal trajectory ontology sequences are associated with four main activities : resting, traveling, foraging and traveling-foraging. 3 Time ontology Seal trajectory ontology includes concepts that can be considered as temporal. For example, the concept Sequence is a temporal interval. To integrate temporal concepts and relationships in seal trajectory ontology, we choose a mapping approach between our ontology and the OWL-Time 3 ontology [7] developed by the World Wide Web Consortium (W3C). This mapping is detailed in our previous work [15]. An extract of the declarative part of this ontology is shown in figure 3 described in detail in [7]. We are mainly interested in the ProperInterval concept and its two properties hasBeginning and hasEnd. 3. http://www.w3.org/2006/time so Secwhich is lementaogy rules mplexity ral rules. ory data uates the summang using to tackle ata filterpresents a comes helle) in work on seals beEnglish ed using seal tratory doy is our Details Figure 1 y, called ry of its logy (Figure 2) based on activities organized as general ones linked to trajectory, and a hierarchy of basic activities linked to sequences of the trajectory domain ontology. The Seal Domain Ontology (Figure 2) considers seal’s activities. According to the domain expert, the seal trajectory ontology sequences are associated with four main activities: resting, traveling, foraging and traveling-foraging. 4 Table 1: Dictionary classes of the seal trajectory ontology TABLE 1 – Seal trajectory ontology dictionary Trajectory domain ontology Concept Description Trajectory logical form to represent sets of sequences Sequence spatio-temporal interval representing a capture GeoSequence spatial part of sequence Specific Se- metadata associated of a capture quence startPosition, object properties to represent the end and endPosition the beginning of a sequence Seal domain ontology Concept Description haulout a state seal where it is not in the water and wet for 40 seconds cruise a state seal where it is in the water and shallower than 1.5 meter dive a state seal where it is in the water and deeper than 1.5 m for 8 seconds CTD Conductivity-Temperature-Depth: metadata about marine environment Summary metadata about deployment’s conditions of the sensor dive_dur, data properties: dive duration, surface dusur_dur, ration and maximum depth of a dive max_depth TAD Time Allocation at Depth: data properties to define the shape of a seal’s dive [7]. 4.1 Thing 1 2 3 4 hasActivity Trajectory 5 Activity Trajectory Activity 6 7 8 hasBaseActivity Sequence BaseActivity 9 hasBaseActivity Trajectory Domain Ontology Sequence logy 10 Semantic Domain Ontology BaseActivity 11 ology Resting Ontology Traveling Trajectory Domain 12 Domain Ontology EXECUTE SEM_APIS.CREATE_RULEBASE(’sealActivities_rb’); INSERT INTO mdsys.semr_sealActivities_rb VALUES( ’foraging_rule’, ’(?diveObject rdf:type s:Dive ) (?diveObject s:max_depth ?maxDepth ) (?diveObject s:tad ?diveTAD ) (?diveObject s:dive_dur ?diveDur ) (?diveObject s:surf_dur ?surfaceDur ) (?diveObject s:seqHasActivity ?activityProberty )’, ’(maxDepth > 3) and (diveTAD > 0.9) and (surfaceDur/diveDur < 0.5)’, ’(?activityProberty rdf:type s:Foraging )’, SEM_ALIASES(SEM_ALIAS(’s’,’owlSealTrajectory#’))); Code 1 – Implementation of foraging rule Seal Domain Ontology logy and.ac.uk Traveling Semantic Foraging Foraging Seal trajectory ontology rules Seal trajectory ontology (Figure 2) considers seal’s activities. Each seal activity has both a declarative part and an imperative corresponding part. The imperative parts of activities are defined as rules in the ontology. A rule is an object that can be used by an inference process to query semantic data. Oracle Semantic Technologies is a rule-based system where rules are based on IF-THEN pattern and new assertions are placed into working memory. Thus, the rule-based system is said to be a deduction system. In deduction systems, the convention is to refer to each IF pattern an antecedent and to each THEN pattern a consequent. User-defined rules are defined using SEM_APIS.CREATE_RULEBASE procedure in a rulebase. Our rulebase is called sealActivities_rb. The system automatically associates a view called MDSYS.SEMR_rulebase-name to insert, delete or modify rules in a rulebase. Code 1 gives the foraging_rule definition based on the domain expert’s conditions. From line 4 to 10 of Code 1, we construct a subgraph and necessary variables needed by the IF part of foraging_rule. Line 11 gives the THEN part of the rule. Line 12 defines the namespace of ontology. Thing hasActivity Ontology rules Seal Trajectory Ontology Resting Traveling Traveling Foraging Foraging 4.2 Figure 2: Overview of Seal Trajectory Ontology Seal Domain Ontology Seal Trajectory Ontology F IGURE 2 – Overview of Seal Trajectory Ontology F IGURE 3 – A view of OWL-Time ontology Time ontology rules The OWL-Time ontology declares the 13 temporal interval relationships based on Allen algebra [1]. We implement the rule base owlTime_rb to hold the interval temporal relationships. For example, the code 2 presents the implementation of the imperative part of the intervalAfter_rule based on operations defined in the table TM_RelativePosition of the ISO/TC 211 specification about temporal schema [6]. In code 2, the line 10 expresses the condition that the beginning of the reference interval is bigger than the end of the argument interval. Line 11 is the consequent of rule. 5 Trajectory ontology inference Inferencing is the ability to make logical deductions based on rules defined in the ontology. Inferencing involves the use of rules, either supplied by the reasoner or defined by the user. At data level, inference is a process of discovering EXECUTE SEM_APIS.CREATE_RULEBASE(’owlTime_rb’) INSERT INTO mdsys.semr_owltime_rb VALUES(’intervalAfter_rule’, ’(?tObj1 rdf:type ot:ProperInterval ) (?tObj2 rdf:type owltime:ProperInterval ) (?tObj1 ot:hasEnd ?end1 ) (?end1 :inXSDDateTime ?endTime1 ) (?tObj2 ot:hasBeginning ?begin2 ) (?begin2 ot:inXSDDateTime ?beginTime2 )’, ’(beginTime2 > endTime1 )’, ’(?tObj2 owltime:intervalAfter ?tObj1 )’, SEM_ALIASES(SEM_ALIAS(’ot’,’http://www.w3.org/2006/ time#’))); 1 2 3 4 5 6 7 8 9 10 11 12 Code 2 – Implementation of intervalAfter rule In Oracle Semantic Technologies, an entailment contains precomputed data inferred from applying a specified set of rulebases to a specified set of semantic models. Code 3 creates an entailment over the seal trajectory and time models. This entailment uses a subset of OWL rules called OWLPrime [12], the seal trajectory and time ontologies rules. Other options are also required like number of rounds that the inference engine should run. In case of applying user-defined rules USER_RULES=T, the number of rounds should be assigned as default to REACH_CLOSURE. In our experiment, we measure the time needed to compute the entailment (Code 3) for different sets of real trajectory data for one seal. Its movements are captured from 16 June until 18 July 2011 and we have got 10 000 captured data. In this experiment, the seal activity rulebase contains only the foraging rule. So, the input data for the entailment are only dives. Figure 4 shows experiment results for the computation time in seconds needed by the entailment. For example, for 450 dives, the inference takes around 60 000 seconds (' 16.6 hours). 1 2 3 4 SEM_APIS.CREATE_ENTAILMENT(’owlSealTrajectory_idx’, SEM_MODELS(’owlSealTrajectory’,’owlTime’), SEM_RULEBASES(’OWLPrime’,’sealActivities_rb’, ’ owlTime_rb’), SEM_APIS.REACH_CLOSURE, NULL, ’USER_RULES=T’); Code 3 – Entailment over owlSealTrajectory and owlTime ontologies 6 Place Of Interest over trajectory data Our proposal is to analyze the captured data before computing the ontology inference. This analyzing is achieved by our primary filter. This filter considers trajectories which are segmented by the object positions. These positions changes and stays fixed. Spaccapietra [13] named the former moves and the latter stops. For this reason, a trajectory is seen as a sequence of moves going from one stop to the next one. Definition 1 (Stop) A stop is a part of a trajectory having a time interval and represented as a single point. new relationships, in our case, new triples. Inferencing, or computing entailment, is a major contribution of semantic technologies that differentiates them from other technologies. F IGURE 4 – Entailment computation time with all temporal rules and the foraging activity Definition 2 (Move) A move is a part of a trajectory represented as a spatio-temporal line. The primary filter defines interesting places for a moving object. The interesting places are related to where the moving object stays more and visits more. This filter is explained in Algorithm 1. This algorithm takes the two parts of a trajectory (move and stop) data as input and gives as output interesting places. The following definitions are used by the algorithm : Definition 3 (Neighbors) Neighbors for a point (pi ) are a list of points from the Move data where the distance between pi and any neighbor point is smaller than a fixed radius. Neighbor(pi ) = {(p j )nj=1 : pi , p j 2 Move, distance(pi , p j ) < radius}. Definition 4 (Peak) A peaki is a cardinality of the list Neighbor(pi ). (peaksi )ni=1 = #(Neighbor(pi ))ni=1 . Definition 5 (Points_Neighbors) Points_Neighbors are a list of points and their neighbors. Points_Neighbors = {(pi , Neighborsi )ni=1 : pi , Neighborsi 2 Move}. Definition 6 (Places) Placei is an interesting place which contains the Neighbor(pi ) and number of its visits (nVisits) by the moving object. Places = {(Neighborsi , nVisitsi )ni=1 : Neighborsi 2 Move, nVisitsi 2 number}. The first step of the primary filter, Algorithm 1 lines 59, gathers the move data into groups of neighbors. These groups are defined with respect to a radius. This radius is a fixed distance between two points to calculate the neighbors. The candidate of the radius is related to the application view of a trajectory, and it is taken as input for this algorithm. The output of the first step is Points_Neighbors. The second step of this filter, lines 10-16, defines the interesting places starting from the Points_Neighbors. In general, we could take all the members of the Points_Neighbors or we could apply a condition over the (Peak). For example, the application view 7 F IGURE 5 – Interesting and foraging places could be interesting in places which having 60 points and over, or could be interesting in any place having at least a point. For defining places, the coordinate of the group neighbors could be an interesting place with two condition. Every point belongs to a place should be far from the stop data more than the fixed radius. Any place should not have any neighbor place within the radius distance, otherwise we merge the two coordinates and increase the visits number. The result of this step (Places) is the output of this algorithm. To analyze our data, we consider the same datasets in Sect. 5. We pass these data to the Place Of Interest algorithm. This algorithm analyzes the data and gives as output the places and their visits, as shown in Fig 5 interesting places (1). Finally, the results of the primary filter are decreased the captured data from 10 000 into 6 170 interesting raw trajectories. Algorithm 1: The Place Of Interest algorithm Experimental results We analyze the trajectory data and define the interesting places. However, the main goal is to define foraging places among these them. This is the goal of the secondary filter. The secondary filter computes the entailment over the interesting places. This filter specifies foraging places and determines the number of foraging activity for each place, as shown in Figure 5 foraging places (2). We can notice that the places 1, 4, 5, 7 and 11 are not considered as foraging places. Places 2, 6 , 9 and 10 are the significant foraging places. By the normal inference ontology computation results, we could not be able to consider all the captured data. Actually, we compute the inference just for 500 raw data. However, using the primary filter and defining the interesting places help us to define foraging places over all the captured data. These inferred data are considered as the final knowledge data where the user can query. 8 Related work Data management techniques including modelling, indexing, inferencing and querying large data have been actively investigated during the last decade [16, 10, 8]. Most of these techniques are only interested in representing and querying moving object raw trajectories [17, 15, 3]. A conceptual view on trajectories is proposed by Spaccapietra et al. [13] in which trajectories are a set of stops, moves. Each part contains a set of semantic data. Based on this conceptual model, several studies have been proposed such as [2, 17]. Alvares et al. [2] proposed a trajectory data preprocessing method to integrate trajectories with the spatial. Their application concerned daily trips of employees from home to work and back. However, the scope of their paper is limited to the formal definition of semantic trajectories with the space and time without any implementation and evaluation. Yan et al. [17] proposed a trajectory computing platform which exploits spatio-semantic trajectory model. One of the layers of this platform is data preprocessing layer which cleanses the raw GPS feed, in terms of preliminary tasks such as outliers removal and regression-based smoothing. Based on a space-time ontology and events approach, Boulmakoul et al. [4] proposed a generic metamodel for trajectories to allow independent applications processing trajectories data benefit from a high level of interoperability, information sharing. Their approach is inspired by ontologies, however the proposed resulting system is pure database approach. Boulmakoul et al. have elaborated a meta-model to represent moving objects using a mapping ontology for locations. Actually, in extracting information from the instantiated model during the evaluation phase, they seem rely on a pure SQL-based approach not on semantic queries. Related to all those limitations in the state of the art, we define and implement two tier filters over trajectory data to clean and analyze the data and solve the computation problem. 9 Conclusion and future work In this work, we propose a modeling approach based on ontologies to build a trajectory ontology. Our approach considers three separated ontology models : a general trajectory domain model, a domain knowledge or semantic model and a temporal domain model. We map the spatial concepts in the trajectory ontology to the spatial ontology. To implement the declarative and imperative parts of the ontologies, we consider the framework of Oracle Semantic Data Store. To define the thematic and temporal reasoning, we implement rules related to the considered models. Thematic rules are based on domain trajectory activities and the temporal rules are based on Allen relationships. Then, we consider two-tier inference filters. In other words, two distinct operations are performed to enhance the inference : primary and secondary filter operations. The primary filter analyzes the trajectory data into places of interest. The secondary filter computes the ontology inference over the semantic trajectories using the ontology domain and temporal rules. The experimental results shows that we are able with the two- tier filters to answer user query over all the captured data, whereas we could not without it even compute the ontology inference. For the evaluation, we use a PC with Linux system over a processor i5-250M, 2.5GHz and 8G memory. For the future work, we look for a server PowerVault NX400 with processor E5-2420 at 1.90GHz 6 cores and 16Gb ram with 4 drives TB. Références [1] J. F. Allen. Maintaining knowledge about temporal intervals. Commun. ACM, 26(11) :832–843, 1983. [2] L. O. Alvares, V. Bogorny, B. Kuijpers, A. F. Macedo, B. Moelans, and A. Vaisman. A model for enriching trajectories with semantic geographical information. In Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems, pages 22 :1–22 :8. ACM, 2007. guage Information Processing, volume 3, pages 66– 85, 2004. [8] J. Malki, A. Bouju, and W. Mefteh. An ontological approach modeling and reasoning on trajectories. taking into account thematic, temporal and spatial rules. In TSI. Technique et Science Informatiques, volume 31/1-2012, pages 71–96, 2012. [9] J. Malki, R. Wannous, A. Bouju, and C. Vincent. Temporal reasoning in trajectories using an ontological modelling approach. Control and Cybernetics, pages 1–16, 2012. [10] P. Matthew. A framework to support spatial, temporal and thematic analytics over semantic web data. PhD thesis, Wright State University, 2008. [11] W. Mefteh. Approche ontologique pour la modelisation et le raisonnement sur les trajectoires. Prise en compte des aspects thematiques, temporels et saptiaux. PhD thesis, La Rochelle university, 2013. [12] Oracle. Oracle Database Semantic Technologies Developer’s guide 11g release 2, 2012. [13] S. Spaccapietra, C. Parent, M. Damiani, J. Demacedo, F. Porto, and C. Vangenot. A conceptual view on trajectories. Data and Knowledge Engineering, pages 126–146, 2008. [14] R. Wannous, J. Malki, A. Bouju, and C. Vincent. Modelling mobile object activities based on trajectory ontology rules considering spatial relationship rules. In Modeling Approaches and Algorithms for Advanced Computer Applications, volume 488 of Studies in Computational Intelligence, pages 249–258. Springer International Publishing, 2013. [15] R. Wannous, J. Malki, A. Bouju, and C. Vincent. Time integration in semantic trajectories using an ontological modelling approach. In New Trends in Databases and Information Systems, volume 185 of Advances in Intelligent Systems and Computing, pages 187–198. Springer Berlin Heidelberg, 2013. [3] M. Baglioni, J. Macedo, C. Renso, and M. Wachowicz. An ontology-based approach for the semantic modelling and reasoning on trajectories. In Advances in Conceptual Modeling - Challenges and Opportunities, volume 5232, pages 344–353. Springer Berlin/Heidelberg, 2008. [16] Z. Yan, D. Chakraborty, C. Parent, S. Spaccapietra, and K. Aberer. SeMiTri : A framework for semantic annotation of heterogeneous trajectories. In Proceedings of the 14th International Conference on Extending Database Technology, pages 259–270. ACM, 2011. [4] A. Boulmakoul, L. Karim, and A. Lbath. Moving object trajectories meta-model and spatio-temporal queries. In International Journal of Database Management Systems (IJDMS), volume 4, pages 35–54, 2012. [17] Z. Yan, C. Parent, S. Spaccapietra, and D. Chakraborty. A hybrid model and computing platform for spatio-semantic trajectories. In The Semantic Web : Research and Applications, pages 60–75. Springer Berlin/Heidelberg, 2010. [5] R. Güting and M. Schneider. Moving Objects Databases. Morgan Kaufmann, 2005. [6] ISO/TC_211. Geographic information – temporal schema, ISO 19108, 2002. [7] R. H. Jerry and P. Feng. An ontology of time for the semantic web. In ACM Transactions on Asian Lan- Recherche de motifs partiellement ordonnés clos discriminants pour caractériser l’état des milieux aquatiques M. Fabrègue1,2 1 A. Braud1 S. Bringay3 F. Le Ber1 M. Teisseire2 ICube, Université de Strasbourg, ENGEES, CNRS 2 IRSTEA, TETIS 3 LIRMM, Université Montpellier 2 ICUBE, 300 bd Sébastien Brant - CS 10413 - F-67412 Illkirch Cedex [email protected], [email protected] TETIS - 500 rue Jean-François Breton - F-34093 Montpellier Cedex 5 [email protected], [email protected] LIRMM - 161 rue Ada - CC477 - F-34095 Montpellier Cedex 5 [email protected] Résumé 1 Cet article présente un processus de fouille de données mis en œuvre pour extraire des connaissances d’un jeu de données concernant l’hydro-écologie des cours d’eau. L’approche s’appuie sur la recherche de motifs clos partiellement ordonnés, utilisés comme éléments discriminants pour relier les paramètres physico-chimiques et biologiques mesurés sur des stations de rivières. Pour chaque valeur d’un indice biologique, sont mis ainsi en évidence des séquences temporelles de valeurs de paramètres physico-chimiques ayant un impact sur la biologie. L’approche est mise en œuvre sur un jeu de données regroupant plusieurs milliers de stations de rivières. Le travail présenté ici se situe dans le cadre du projet Fresqueau 1 , qui a pour but de développer des méthodes de fouille de données pour étudier, comparer et exploiter l’ensemble des données disponibles permettant d’évaluer l’état d’un cours d’eau. Ces données sont relatives à la qualité de l’eau, l’hydrologie, les stations de mesure, etc. mais concernent également l’environnement des cours d’eau. Il s’agit en particulier des données physico-chimiques et biologiques produites par les agences de l’eau et l’O NEMA (Office National de l’Eau et des Milieux Aquatiques), qui se déclinent en trois sous-ensembles : Mots Clef Fouille de données, motifs clos partiellement ordonnés, mesure d’intérêt, hydro-écologie. Abstract This paper presents a data mining process implemented to extract original knowledge from hydro-ecological data. The approach is based on closed partially ordered patterns used as discriminant features to link physico-chemistry with biology in river sampling sites. For each bio-indicator quality value, we obtain a set of significant discriminant features. We use them to identify the impact of physicochemical characteristics on the biological dimensions. The approach has been experimented on a dataset of several thousands river sites. Keywords Data mining, Closed partially ordered patterns, Interestingness measure, Hydro-ecology. Introduction 1. données concernant l’état physico-chimique de l’eau et des sédiments ; macropolluants (nitrates, matières organiques, ...) et micropolluants (pesticides, ...) ; 2. données concernant l’état des peuplements biologiques floristiques et faunistiques : cet état est synthétisé dans des indices biologiques, parmi lesquels l’indice biologique global normalisé (IBGN) [1] est le plus fréquemment utilisé ; 3. données concernant l’état physique : il s’agit de l’hydromorphologie du cours d’eau (état des berges, du lit mineur, du lit majeur, ...) et des conditions hydrologiques (débits) et hydrauliques (vitesse, géométrie du cours d’eau). Ces données sont issues de résultats d’analyse de prélèvements effectués régulièrement sur les réseaux de mesure nationaux. Chaque station d’un réseau de mesure est ainsi caractérisée théoriquement par une note annuelle d’un ou plusieurs indices biologiques, et par des valeurs bimensuelles de paramètres physico-chimiques. Dans le cadre de 1. http://engees-fresqueau.unistra.fr/ Numéro Station 1 2 Mois / année 02/07 06/07 07/07 09/07 12/07 02/08 04/08 05/08 07/08 01/04 04/04 07/04 08/04 09/04 11/04 12/04 03/05 06/05 08/05 NH+ 4 NKJ NO2 PO34 0,088 0,154 0,062 0,043 2,331 0,117 0,004 - 0,672 1,235 0,040 0,023 0,146 7,993 1,414 0,0844 0,182 - 0,026 0,134 0,246 0,091 0,198 0,421 0,252 0,0310 0,012 - 0,043 0,168 0,025 0,046 0,325 0,132 0,188 0,067 0,137 0,035 - Phosphore total 0,032 0,011 0,006 0,003 0,009 0,093 0,066 0,078 0,034 - IBGN 17 12 8 10 TABLE 1 – Extrait du jeu de données avec différents paramètres physico-chimiques (ammonium, nitrate de Kjeldahl, nitrite, orthophosphate, phosphore total) et un indice biologique (IBGN) Fresqueau, nous travaillons sur les districts Rhin-Meuse et Rhône-Méditerranée et Corse, qui recouvrent respectivement 33.000 et 130.000 km2 et comptent ensemble 11.329 stations. Les données sont disponibles sur une dizaine d’années (2000-2010). Pour plus d’information sur les données collectées, le lecteur pourra se référer à [4]. Nous avons exploité ces données pour mettre en évidence des liens entre différentes métriques permettant de caractériser la qualité des cours d’eau, ici les métriques liées aux paramètres physico-chimiques et les métriques liées à la biologie. Nous avons en particulier cherché à mettre en évidence les valeurs des paramètres physico-chimiques précédant généralement dans le temps les valeurs des indices biologiques, en particulier l’IBGN. Notre démarche s’inscrit dans le domaine général de la fouille de motifs dans des séquences, domaine pour lequel de nombreuses méthodes et applications ont été développées [2, 12, 6, 15]. L’article présente brièvement les données, puis la méthode développée spécifiquement pour notre application et quelques résultats obtenus, avant de conclure. 2 Matériel et méthodes Nous avons exploité les données en utilisant une méthode décrite dans [11], qui recherche des motifs partiellement ordonnés clos (CPO-motifs) dans une base de séquences. Les CPO-motifs ont fait l’objet de différents travaux [14, 5]. Ils présentent un certain nombre d’avantages : 1. ils sont bien adaptés au caractère temporel des données ; 2. ils donnent plus d’information sur l’ordre entre élé- ments que les motifs séquentiels ; 3. ils sont représentés sous la forme de graphes acycliques, qui sont facilement lisibles par des experts. Le fait que les motifs soient clos permet de résumer au mieux les informations contenues dans une base de séquences. Malgré cela, la méthode produit encore trop de résultats et pour les réduire, nous utilisons des mesures d’intérêt [12] qui permettent alors de mettre en évidence des motifs discriminants que nous noterons DCPO-motifs par la suite. 2.1 Préparation des données Avant de mettre en œuvre cette méthode, différents prétraitements sont nécessaires. Nous utilisons l’exemple présenté dans le tableau 1 pour les expliquer. On remarque sur ce tableau que les données sont éparses : en particulier, alors que les paramètres physico-chimiques sont mesurés tous les deux mois par les agences de l’eau, l’IBGN est réalisé au mieux une fois l’an, en période d’étiage, donc généralement en été. Les données ont d’abord été discrétisées en utilisant la norme SEQ-Eau 2 , modifiée à la marge selon l’avis des hydro-écologues travaillant dans le projet Fresqueau. Cette discrétisation transforme les données initiales en cinq classes de qualité, "Très bon", "Bon", "Moyen", "Mauvais" and "Très mauvais" representées par cinq couleurs Bleu, Vert, Jaune, Orange et Rouge. Par exemple PO34 =0,026 appartient à la classe de qualité "Très bon"/Bleu et phos2. http://sierm.eaurmc.fr/eaux-superficielles/ fichiers-telechargeables/grilles-seq-eau-v2.pdf Sous-bases IBGNB IBGNJ IBGNR Séquences h(AZOT )(AZOTV ,PHOSB )i B h(AZOT ,PHOSV )(PHOSV )(AZOTJ ,PHOSB )i h(AZOTV ,PHOSV )(AZOTB ,PHOSV )i h(PHOSO )(AZOTO ,PHOSJ )(AZOTV ,PHOSJ )i h(AZOTV ,PHOSJ )(AZOTV ,PHOSB )(AZOTV )i h(AZOTO ,PHOSJ )(AZOTR ,PHOSO )(AZOTV ,PHOSJ )i h(PHOSO )(AZOTO ,PHOSJ )(AZOTV )i B TABLE 2 – Sous-bases de séquences associées à trois valeurs de l’indice IBGN phore total = 0,67 appartient à la classe de qualité "Moyen"/Jaune. La norme SEQ-Eau permet également de regrouper les paramètres initiaux en 15 macro-paramètres : ainsi les paramètres PO34 et phosphore total sont rassemblés en un seul paramètre qualitatif PHOS (matières phosphorées) qui prend la valeur la plus basse des deux ("Moyen"/Jaune sur l’exemple précédent). Les paramètres NH+ 4 , NJK et NO2 sont eux rassemblés dans le macroparamètre AZOT (matières azotées hors nitrate). A la suite de cette discrétisation, le jeu de données est transformé en séquences. Chaque valeur de paramètre constitue un item. Deux paramètres (ou plus) mesurés à la même date constituent un ensemble d’items ou itemset. Une succession d’itemsets constitue une séquence. Sur la station 1, par exemple, on a relevé la classe de qualité Vert pour le macro-paramètre PHOS en février 2007, la classe de qualité Bleu pour le macro-paramètre AZOT en juin 2007, la classe de qualité Vert pour AZOT et la classe de qualité Bleu pour PHOS en juillet 2007. L’indice IBGN mesuré en septembre de la même année a la valeur Bleu. Ainsi la station 1 est associée à la séquence h(PHOSV ) (AZOTB ) (AZOTV , PHOSB ) (IBGNB )i. Les séquences ainsi constituées sont ensuite segmentées selon des fenêtres de longueurs 2 à 6 mois, en amont d’une mesure de l’indice biologique. En effet, l’indice biologique intègre les événements physico-chimiques antérieurs sur une durée limitée, et c’est ce que nous cherchons à mettre en évidence. La base de séquences obtenue est alors subdivisée selon la valeur de l’IBGN concluant une séquence. Dans le tableau 2, trois valeurs d’indices sont considérées, Bleu, Jaune et Rouge. 2.2 AZOTO < $ < AZOTV / > : " PHOSO F IGURE 1 – Un exemple de motif partiellement ordonné tif l’englobant (présenté sur la figure 2) existe avec le même support. En effet l’item PHOSJ est présent dans toutes les séquences supportant P dans les sous-bases IBGNJ et IBGNR (voir tableau 2). AZOTO , PHOSJ ; % < AZOTV / > 8 $ PHOSO Extraction des motifs Cette étape est le cœur de notre proposition. Pour extraire les motifs des différentes sous-bases, nous avons utilisé une version adaptée de l’algorithme présenté dans [11]. La modification essentielle concerne l’utilisation de différents supports minimums, en fonction des sous-bases. Par exemple le motif représenté sur la figure 1 a un support de 0/2 dans la sous-base IBGNB , 1/3 dans la sous-base IBGNJ et 2/2 dans la sous-base IBGNR (voir tableau 2). De plus, nous ne considérons que les motifs partiellement ordonnés clos (CPO-motifs), ce qui permet d’extraire un ensemble plus petit de motifs sans perte d’information. Ainsi le motif P de la figure 1 ne sera pas retenu car un mo- F IGURE 2 – Un exemple de CPO-motif incluant le motif de la figure 1 2.3 Sélection des motifs Cette sélection s’effectue pour chaque sous-base selon trois critères : la fréquence, la discriminance et la redondance. Fréquence et discriminance sont des critères utilisés par l’algorithme pour limiter l’exploration, à l’issue de laquelle un sous-ensemble de motifs non redondants est sélectionné, selon une procédure définie ci-desous, pour être présenté à l’analyste. Fréquence d’un CPO-motif : elle est classiquement mesurée par le nombre de séquences de la sous-base qui contiennent le CPO-motif, rapporté au nombre total de séquences dans la sous-base. Lors de l’extraction des CPOmotifs, l’utilisation d’un support minimal permet de sélectionner les motifs fréquents. Discriminance d’un CPO-motif : elle est mesurée par un facteur de croissance généralisé à partir de celui proposé dans [9]. Un motif est discriminant pour une sous-base s’il est plus fréquent dans cette sous-base que dans toutes les autres. Plus formellement : Définition 1 Soit un motif partiellement ordonné clos P , une sous-base C et un ensemble de sous-bases EC ={C1 , C2 , . . . , Cn }, le taux de croissance généralisé de P dans C en référence à EC , dénoté GGR(P, C, EC ), est : 8 0, si suppC (P ) = 0 et max(suppC1 (P ), > > > > supp > C2 (P ), . . . , suppCn (P )) = 0 < 1, si suppC (P ) 6= 0 et max(suppC1 (P ), (1) > suppC2 (P ), . . . , suppCn (P )) = 0 > > > suppC (P ) > : max(supp (P ),supp (P ),...,supp (P )) sinon C1 C2 Cn où suppCi (P ) dénote le support du motif P dans la sousbase Ci . Un CPO-motif est discriminant si GGR(P, C, EC )> 1. Il est alors noté DCPO-motif pour "motif partiellement ordonné clos discriminant". Le calcul de la discriminance est fait au cours de l’extraction : pour chaque CPO-motif P extrait de la sous-base courante, on calcule son support dans les autres bases, ce qui permet de calculer en même temps le taux de croissance généralisé de P . Redondance d’un CPO-motif : elle est mesurée par le nombre de CPO-motifs décrivant le même ensemble de séquences. Plus précisément, à chaque CPO-motif est associé un sous-ensemble des séquences de la base, représenté comme une suite binaire de présence-absence de chaque séquence. On peut ainsi utiliser une distance de Hamming entre les ensembles associés à différents CPO-motifs : plus les motifs sont proches (donc couvrent approximativement le même sous-ensemble de séquences) plus ils sont redondants. et NGGR(P ) est son taux de croissance généralisé et normalisé dans la sous-base considérée et vis-à-vis des autres sous-bases. Le facteur 3 est introduit pour des raisons de normalisation. Cette procédure a une complexité de l’ordre de : k X1 i=0 i ⇥ (n i) ⇥ p + (n i) où n est le nombre de DCPO-motifs extraits de la sous-base B de taille p, et k > 0 le nombre de motifs à sélectionner parmi eux. A chaque étape, les i motifs déjà sélectionnés dans P sont comparés deux à deux aux n i motifs restants en calculant la distance de Hamming sur la base B. 3 Résultats Nous ne traitons ici que de l’indice IBGN, qui tient compte de la présence ou de l’absence de certaines espèces macroinvertébrées polluo-sensibles. Parmi les sites de la base de données ne sont donc retenus que ceux sur lesquels l’IBGN a été calculé et pour les périodes où il a été calculé. Le calcul de la note (entre 0, très mauvais état, et 20, très bon état), puis de la classe, est fondé sur l’inventaire de 128 espèces. La méthode est opérée en deux temps : extraction des CPO-motifs discriminants pour chaque sous-base, puis sélection d’un nombre restreint d’entre eux via l’indice IPB . Dans cette expérimentation, le même seuil de fréquence (égal à 10%) est utilisé pour toutes les sous-bases. La figure 3 donne le nombre (selon une échelle logarithmique) de DCPO-motifs extraits des cinq sous-bases associées aux classes de valeur de l’IBGN. Ces résultats déséquilibrés sont en partie liés aux nombres déséquilibrés de séquences dans les classes, en lien avec l’état observé des cours d’eau : les sous-bases les plus peuplées sont IBGNV (2405 séquences), lIBGNJ (1282) et IBGNB (1056). La sous-base IBGNO est plus faiblement peuplée (556 séquences), tandis que la sous-base IBGNR est quasi vide (89 séquences). Mais la diversité des motifs extraits des sousbases s’explique aussi par la diversité des valeurs de para- Combinaison des critères : les critères de fréquence, discriminance et redondance sont normalisés et combinés afin d’obtenir un ensemble restreint de CPO-motifs caractéristiques pour chaque sous-base. La procédure que nous utilisons consiste à sélectionner k motifs, pas-à-pas, en maximisant la valeur suivante, calculée sur le motif à sélectionner P en référence à un ensemble P de motifs déjà sélectionnés : IPB (P, P) = NMH(P, P) ⇥ Freq(P ) ⇥ NGGR(P ) ⇥ 3 (2) NMH(P, P) + Freq(P ) + NGGR(P ) où NMH(P, P) est la distance de Hamming normalisée minimale entre P et les motifs de l’ensemble P (distance initialisée à 1 pour P = ;), Freq(P ) est la fréquence de P F IGURE 3 – Nombres de CPO-motifs extraits des sousbases IBGN (classes de valeur Bleu, Vert, Jaune, Orange et Rouge), avec un support minimum de 1/10 < / > / MINER MOOXR F IGURE 6 – Un DCPO-motif de la sous-base IBGNR (mêmes paramètres mais de classes différentes que dans la figure 5) AZOTJ < $ < F IGURE 4 – Visualisation dans un plan factoriel des 20 DCPO-motifs sélectionnés parmi les motifs extraits de la sous-base IBGNR mètres menant à une même classe d’IBGN. C’est pourquoi il est intéressant de mettre en œuvre la procédure de sélection décrite plus haut, permettant de choisir des DCPOmotifs qui mettent en évidence cette variété. Nous avons donc sélectionné 20 DCPO-motifs pour chaque sous-base. La figure 4 représente leur distribution vis-à-vis des DCPO-motifs extraits dans la sous-base IBGNR , dans le plan factoriel construit sur la distance de Hamming entre motifs. Chaque DCPO-motif est représenté par un cercle dont le diamètre représente la fréquence du motif et le niveau de gris la discriminance. On observe sur cette projection que ces 20 DCPO-motifs sont assez bien répartis parmi les motifs extraits de la sous-base, respectant ainsi le critère de non redondance. Les figures 5 et 6 présentent deux DCPO-motifs extraits des sous-bases associées aux états "Très bon" (IBGNB ) et "Très mauvais" (IBGNR ). Les deux macro-paramètres MINE et MOOX représentent respectivement la minéralisation de l’eau et les matières organiques et oxydables présentes dans l’eau. On remarque ici que les classes des macro-paramètres correspondent exactement aux classes de l’indice biologique. Ce n’est pas forcément le cas pour les autres indices – non présentés dans cet article. < / MINEB MOOXB / > F IGURE 5 – Un DCPO-motif de la sous-base IBGNB , associant les macro-paramètres "minéralisation de l’eau" et "matières organiques et oxydables" La figure 7 présente un DCPO-motif caractéristique de la sous-base IBGNO . On observe ici que différentes séquences mènent à la classe "Mauvais état" de cet indice. Le paramètre TEMP (température) est peu pertinent car peu variable sur les données considérées. En revanche les / TEMPB / TEMPB /5 > " MOOXJ F IGURE 7 – Un DCPO-motif de la sous-base IBGNO , associant les macro-paramètres "température de l’eau", "matières azotées hors nitrate" et "matières organiques et oxydables" macro-paramètres AZOT et MOOX – pour des valeurs moyennes (Jaune) – ont visiblement un effet dégradant sur l’état mesuré par l’IBGN. 4 Autres travaux De nombreux travaux ont porté sur l’exploitation de données hydro-écologiques. Classiquement les hydroécologues utilisent des approches statistiques. Des approches de fouille de données ont également été mises en œuvre, arbres de décision [7], réseaux de neurones [8], ou treillis de Galois [3]. Ces travaux ont généralement pour objectif de mettre en relation des caractéristiques physiques ou physico-chimiques des rivières et les populations de taxons (faune ou flore) qui les habitent. Ainsi, certains auteurs [7] utilisent des arbres de décision pour prédire l’adéquation des habitats (caractérisés par des paramètres physiques et physico-chimiques) d’une rivère en Grèce à certains macro-invertébrés. Le modèle des arbres de régression multiple a été utilisé pour étudier l’impact des conditions physico-chimiques du milieu sur les communautés de diatomées (algues microscopiques) dans un lac macédonien [13]. Avec les mêmes techniques, d’autres auteurs [10] ont cherché à prédire des valeurs de paramètres physico-chimiques à partir de paramètres biologiques (abondance des taxons). A notre connaissance, aucune étude n’a porté sur l’utilisation d’algorithmes de recherche de motifs dans les séquences, avec l’objectif d’extraire les relations temporelles entre les paramètres physico-chimiques et les indices biologiques, comme nous le proposons ici. 5 Conclusion Le travail présenté ici a pour but de mettre en évidence les liens temporels entre les valeurs de paramètres physicochimiques et d’indices biologiques. Nous avons développé pour cela une méthode originale d’extraction de motifs partiellement ordonnés clos. De plus nous avons mis en œuvre une procédure de sélection des motifs s’appuyant sur trois critères combinés, et permettant ainsi d’obtenir des résultats exploitables par l’analyste et représentatifs du jeu de données initial. La méthode a été exploitée avec succès sur un jeu de données important (15 macro-paramètres et environ 5000 séquences pour l’IBGN, mais davantage, de l’ordre de 10.000, quand on considère tous les indices biologiques), ce qui prouve de plus sa pertinence pour la fouille de données massives. Par la suite, l’étude sera étendue aux données hydroécologiques collectées sur l’ensemble du territoire français et éventuellement à d’autres indices biologiques ou d’autres paramètres physiques. La méthode devra également être testée sur des jeux de données aux caractéristiques diverses, afin d’en éprouver la stabilité. rence on Data Engineering, ICDE 2008, pages 169– 178, 2008. [7] Eleni Dakou, Tom D’Heygere, Andy P. Dedecker, Peter L.M. Goethals, Maria Lazaridou-Dimitriadou, and Niels Pauw. Decision Tree Models for Prediction of Macroinvertebrate Taxa in the River Axios (Northern Greece). Aquatic Ecology, 41 :399–411, 2007. [8] Andy P. Dedecker, Peter L.M. Goethals, Wim Gabriels, and Niels De Pauw. Optimization of Artificial Neural Network (ANN) model design for prediction of macroinvertebrates in the Zwalm river basin (Flanders, Belgium). Ecological Modelling, 174 :161–173, 2004. [9] Guozhu Dong and Jinyan Li. Efficient Mining of Emerging Patterns : Discovering Trends and Differences. In Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD, pages 43–52, 1999. Remerciements [10] Sašo Džeroski, Damjan Demšar, and Jasna Grbovi´c. Predicting chemical parameters of river water quality from bioindicator data. Applied Intelligence, 13(1) :7–17, 2000. Cette recherche est financée par l’Agence Nationale de la Recherche dans le cadre du projet ANR 11 MONU 14 Fresqueau. Nous remercions chaleureusement les hydroécologues participant au projet, en particulier Corinne Grac (UMR LIVE, ENGEES) et Danielle Levet (Aquascop). [11] Mickaël Fabrègue, Agnès Braud, Sandra Bringay, Florence Ber, and Maguelonne Teisseire. Orderspan : Mining closed partially ordered patterns. In Advances in Intelligent Data Analysis XII, LNCS 8207, pages 186–197. 2013. Références [12] Liqiang Geng and Howard J. Hamilton. Interestingness measures for data mining : A survey. ACM Computing Survey, 38(3), 2006. [1] AFNOR. Qualité de l’eau : détermination de l’Indice Biologique Global Normalisé (IBGN). XP T90-350, 2004. [2] Rakesh Agrawal and Ramakrishnan Srikant. Mining sequential patterns. In International Conference on Data Engineering, ICDE, pages 3–14, 1995. [3] Aurélie Bertaux, Florence Le Ber, Agnès Braud, and Michèle Trémolières. Identifying Ecological Traits : A Concrete FCA-Based Approach. In Formal Concept Analysis, volume 5548, pages 224–236, 2009. [4] Agnès Braud, Sandra Bringay, Flavie Cernesson, Xavier Dolques, Mickaël Fabrègue, Corinne Grac, Nathalie Lalande, Florence Le Ber, and Maguelonne Teisseire. Une expérience de constitution d’un système d’information multi-sources pour l’étude de la qualité de l’eau. In Atelier "Systèmes d’Information pour l’environnement", Inforsid 2014, Lyon, 2014. [5] Gemma Casas-Garriga. Summarizing Sequential Data with Closed Partial Orders. In SIAM International Conference on Data Mining, Newport Beach, CA, SDM PR119, pages 1–12, 2005. [6] Hong Cheng, Xifeng Yan, Jiawei Han, and Philip S. Yu. Direct Discriminative Pattern Mining for Effective Classification. In IEEE 24th International Confe- [13] Dragi Kocev, Andreja Naumoski, Kosta Mitreski, Svetislav Krsti´c, and Sašo Džeroski. Learning habitat models for the diatom community in Lake Prespa. Ecological Modelling, 221(2) :330–337, 2010. [14] Jian Pei, Haixun Wang, Jian Liu, Ke Wang, Jianyong Wang, and Philip S. Yu. Discovering Frequent Closed Partial Orders from Strings. IEEE Transactions on Knowledge and Data Engineering, 2006. [15] Miao Wang, Xue-qun Shang, and Zhan-huai Li. Sequential Pattern Mining for Protein Function Prediction. In Advanced Data Mining and Applications, volume 5139 of ADMA, pages 652–658. 2008. Recherche de documents par apprentissage artificiel pour une méta-analyse sur les émissions d’un gaz à effet de serre A. Cornuéjols1 1 Ch. Loyce2 AgroParisTech, département MMIP et INRA UMR-518 2 3 A. Duroy 1 D. Makowski 3 A. Philibert3 16, rue Claude Bernard, F-75231 Paris Cedex 5 (France) AgroParisTech, Dept. SIAFEE, UMR Agronomie INRA / AgroParisTech UMR 211 INRA AgroParisTech Ch. Martin1 78850 Thiverval-Grignon, France 78850 Thiverval-Grignon, France {antoine.cornuejols,christine.martin}@agroparistech.fr Résumé 1 La méta-analyse est un outil puissant pour réaliser des synthèses quantitatives d’articles scientifiques traitant d’un sujet commun, par exemple l’estimation des émissions de gaz à effet de serre. La qualité d’une méta-analyse dépend de plusieurs facteurs, et notamment de la qualité de la recherche bibliographique. Celle-ci génère fréquemment une liste de plusieurs centaines voire plusieurs milliers d’articles. En général, seule une petite partie de ces articles inclut des données exploitables. Dans ce cas, le tri manuel des articles et l’extraction des données constituent des étapes longues (souvent plusieurs mois) et fastidieuses. Ce papier décrit une technique permettant d’automatiser le tri des articles par apprentissage artificiel dans le but de réaliser des méta-analyses portant par exemple sur des problématiques environnementales. Prédire l’évolution et les risques liés à des systèmes mettant en jeu des interactions complexes est un défi. Les enjeux sont particulièrement évidents dans l’estimation du changement climatique, des risques sanitaires, de l’utilisation des ressources naturelles ou des politiques agricoles. Étant donnée l’importance croissante de ces questions pour nos sociétés, il est fréquent qu’existe déjà un (très) grand nombre d’études. Celles-ci sont cependant le plus souvent parcellaires et locales aussi bien d’un point de vue spatial que temporel. Prises séparément, il est difficile d’en extraire un scénario précis, ou même une estimation fiable de quelques paramètres clés, comme, par exemple, l’estimation des émissions de gaz à effet de serre (N2 O en particulier) par les sols agricoles. Nous avons besoin de solutions permettant de faciliter le tri des sources scientifiques, d’augmenter la fiabilité de ce tri et de rendre les procédures utilisées pour les exploiter plus transparentes. La méta-analyse est une méthode permettant de réaliser des revues quantitatives de la littérature scientifique. Elle consiste à réaliser une analyse statistique d’un jeu de données constitué d’un nombre plus ou moins grand d’expérimentations traitant du même sujet. Cependant, la qualité d’une méta-analyse est en grande partie dépendante de la pertinence et de la complétude du corpus d’études rassemblé au préalable. Ce papier présente une démarche générique pour opérer une sélection des articles pertinents. Elle est illustrée pour une méta-analyse cherchant à estimer la part des doses d’engrais azotés apportés sur les sols agricoles qui se retrouve convertie en N2 O, un puissant gaz à effet de serre 1 . Mots Clef Apprentissage Artificiel, méta-analyse, réchauffement climatique Abstract Meta-analysis is a powerful tool to perform quantitative syntheses from scientific articles related to some given question such as what is the amount of nitrous oxide coming from fertilizers that ends up as a greenhouse effect agent ? The quality of a meta-analysis is greatly dependent upon the relevance and completeness of the prior bibliographical search. It is common that a first search yields hundreds or thousands of potentially relevant papers. In general, however, only a small number of these articles turn out to be of interest. Their filtering out mobilizes human experts for long periods of time and the process is subject to many and difficult to control defects. This paper describes an automatic process based on machine learning techniques that help to screen the vast amount of literature on a subject. Keywords Machine Learning, Meta-Analysis, Information Retrieval, Global Warming. Introduction Principe de l’approche. Étant donnée la masse des documents désormais disponibles dans l’univers numérique, ainsi que la complexité de chaque document par rapport à l’information recherchée se rapportant à un paramètre, une démarche raisonnable consiste à recourir à une séquence d’opérations destinées à raffiner la recherche. 1. Sélection des articles par mots-clés. Soit Smc , l’ensemble des articles retenus ainsi. 1. Son pouvoir de réchauffement global sur 100 ans est 310 fois plus élevé qu’une masse équivalente de CO2 [4]. 2. Apprentissage portant sur les abstracts des documents à trier (trois phases) : – Apprentissage d’une redescription des abstracts qui diminue le nombre de descripteurs afin de rendre la tâche d’apprentissage réalisable – Étiquetage par l’expert de N articles parmi ceux retenus à l’étape précédente (Smc ), de telle manière qu’environ N/2 de ces articles soient étiquetés comme valides (contenant l’information recherchée pour la méta-analyse), et que les autres soient étiquetés négativement 2 . – Apprentissage supervisé d’une règle de décision permettant, sur la base des abstracts redécrits, de distinguer les articles probablement pertinents de ceux qui ne le sont probablement pas. non d’un mot dans le texte, parfois avec une information aussi sur la fréquence. Une difficulté est alors que la taille du vocabulaire implique des représentations dont la taille est aisément de l’ordre de plusieurs milliers, et donc souvent d’un ou deux ordres de grandeur supérieur au nombre d’exemples d’appprentissage disponible. Il faut donc réduire très notoirement la dimension de l’espace de représentation, tout en conservant autant que possible l’information utile. Les grandes étapes de prétraitement de textes classique sont les suivantes. 3. Apprentissage pour chercher l’information dans le contenu des articles retenus après filtrage sur les abstracts. 2.2 La suite de ce papier est consacrée à la deuxième étape (section 2). Le souci récurrent à chaque étape est d’éliminer au maximum les articles non pertinents (les faux positifs) tout en conservant cependant tous (ou le plus possible) les articles pertinents (vrais positifs). Or ces deux objectifs sont contradictoires. 2 2.1 Traitement des abstracts Du texte à une représentation vectorielle La source d’information la plus riche et la plus discriminante étant les abstracts, c’est sur eux que doit prioritairement porter la méthode de filtrage. Cependant, si les experts sont incapables de fournir une telle règle, ils sont néanmoins aptes à étiqueter les abstracts (et les documents associés) en deux classes : positif et négatif, ou « pertinent » et « non pertinent ». Il devient dès lors tentant de recourir à des techniques d’apprentissage artificiel supervisé pour essayer de découvrir de manière automatique une règle de décision dont la performance en reconnaissance se rapproche si possible de celle des experts. Il n’existe pas encore de méthode d’apprentissage supervisé capable de s’appliquer à des textes quelconques. Ceuxci sont en effet à la fois semi-structurés, avec une ligne argumentative non contrainte et une longueur variable, tout en impliquant potentiellement un vocabulaire considérable, de l’ordre de plusieurs dizaines de milliers de mots (en comptant les terminaisons et variations diverses). Il n’est donc pas possible de fournir en entrée à des systèmes d’apprentissage classiques des textes sous leur forme brute. C’est pourquoi a été imaginée une approche radicale consistant à « projeter » un texte sur l’espace des mots du vocabulaire du domaine d’intérêt. Dans cette approche en « sac de mots » (bag-of-words), la structure du texte est ignorée et ne subsiste que l’information sur la présence ou 2. Pour favoriser l’apprentissage, il est généralement préférable que les classes soient équilibrées dans l’échantillon d’apprentissage. 1. 2. 3. 4. Étape de reconnaissance des mots. Le retrait des mots standards (stopwords). La lemmatisation. Le stemming. Sélection d’attributs Si les traitements purement textuels permettent un gain appréciable en terme de réduction de taille de vocabulaire (souvent une division par 3 ou 4 du nombre de « mots »), cela n’est généralement pas suffisant pour permettre la mise en œuvre de techniques d’apprentissage. Il faut donc compléter ces traitements par des analyses fondées sur des mesures statistiques. L’analyse tf-idf est l’une d’elle. Elle consiste à retirer les termes ne permettant pas, au vu d’une analyse statistique, de discriminer les textes au sein d’une collection de documents. Mais d’autres analyses sont spécifiquement dédiées à la découverte des attributs de description qui sont les plus corrélés à la distinction en classes selon certains critères. Parmi les méthodes de sélection d’attributs (feature selection), on distingue généralement les méthodes de filtre (filter methods) qui évaluent la pertinence de chaque attribut ou descripteur indépendamment, et sans tenir compte de la méthode de classification supervisée utilisée en aval. Les méthodes de filtre calculent un score à chaque attribut de description indépendamment. Nous avons utilisée une méthode basée sur une mesure d’entropie : la mdl-entropie [3]. 2.3 Recodage structuré et supervisé Cependant, au lieu de redécrire les données grâce à des techniques de sélection décrites dans la section précédente, il peut être judicieux de procéder à un changement de représentation permettant si possible de rendre compte, au moins en partie, de la structure des textes étudiés. Un moyen simple pour commencer à tenir compte de cette structure est de considérer non pas des mots isolés mais des ensembles de mots (motifs) particuliers pour décrire les documents. Une technique classique est de calculer les ngrams fréquents. On généralise les n-grams par les « motifs fréquents » qui ne sont pas tenus d’être composés d’éléments contigus. Soit A l’ensemble des descripteurs ai issus des étapes présentées en section 2.1. Un motif m est alors défini comme un sous-ensemble de A et un motif m est dit présent dans un document si tous les descripteurs qui le composent y figurent au moins une fois. Étant donné un motif m et une 2.4 Recherche d’une règle de discrimination par apprentissage supervisé Après l’étape de sélection ou de recodage des attributs de description des documents, ne doit subsister qu’un petit vocabulaire de termes à l’aide duquel sont décrits les documents. Il est préférable que la taille du vocabulaire ainsi déterminée soit inférieure au nombre de documents de l’ensemble d’apprentissage. Tout document, d’apprentissage ou à classer, est alors codé soit en signalant pour chaque attribut si il est présent ou non dans le document : codage booléen, soit en reportant le nombre d’occurrences de chaque attribut dans le document : codage par fréquence. Une fois le codage obtenu, supposé aussi concis et néanmoins informatif que souhaitable, il devient possible de recourir à des techniques d’apprentissage artificiel supervisé pour rechercher des règles de décision permettant de distinguer les documents pertinents de ceux qui ne le sont pas. Ainsi, à partir d’un corpus d’entraînement S = {(dj , yj )}1jm de m documents dj étiquetés dans une classe yj par un expert, un algorithme d’apprentissage supervisé induit une règle de décision h(·) qui à partir d’un document d lui associe une étiquette y = h(d). De nombreuses techniques d’apprentissage supervisé existent (voir [2]). Les plus classiques incluent : l’apprentissage par plus proches voisins, l’apprentissage bayésien naïf, l’apprentissage par réseaux de neurones artificiels, l’apprentissage par arbres de décision, les méthodes à noyaux dont les SVM (Séparateurs à Vastes Marges), et des méthodes de méta-apprentissage comme le boosting ou le bagging. Ces algorithmes ont des propriétés propres et présentent des avantages et inconvénients les rendant plus ou moins adaptés à une utilisation donnée (voir le tableau 2.4). De plus, le choix parmi ces méthodes doit aussi prendre en compte les critères importants pour l’application visée, à savoir par exemple : – La robustesse au bruit dans les données (données mal décrites, présence de données aberrantes, ...) SVM thè se) non tell lin igi éai b de ilit re é gra n de Be dim soi nd ens ’a ion pri ori Fac f o ilit rt éd up ara mé Gé tra nér ge alis de atio la m n/ éth Mu ins ode ltiens cla i b ilit sse éa ub rui t , in n( hyp o Naïve Bayes Arbre de décis. Réseau de neur. Esp ace p p p p p enc e éci sio de d k-ppv Tra nsp ar Rè gle fréquence minimale fmin servant de seuil de décision, on dit que m est fréquent si et seulement si sa fréquence parmi les documents concernés est supérieure à fmin . L’algorithme Apriori [2], ou l’une de ses variantes, permet de calculer l’ensemble des motifs fréquents pour tout ensemble de documents fournis en entrée. En sélectionnant les « motifs fermés fréquents » indépendamment sur chaque classe de documents que l’on souhaite pouvoir identifier (pertinent et non pertinent) on obtient une nouvelle « base » de descripteurs de dimension d’autant plus faible que la table initiale est creuse et que le seuil choisi est élevé. Il faut néanmoins veiller à ce que chaque document soit décrit par au moins un descripteur. Il y a donc un compromis à trouver au niveau de seuil de sélection pour, d’une part, réduire au maximum le nombre de descripteurs et, d’autre part, en conserver suffisamment pour que chaque exemple disponible initialement reste utilisable pour la suite des traitements. -p -p -p p p p - -p -p -p p p p p p p - TABLE 1 – Comparaison de certaines propriétés de méthodes d’apprentissage supervisé classiques. – La capacité à traiter des données numériques et/ou de nature symbolique – La capacité à traiter des données décrites dans un espace de grande dimension – L’intelligibilité des règles de décision produites – La complexité calculatoire (temps calcul et espace mémoire nécessaires) 3 Application : Estimation des émissions de N2 O par les sols agricoles Dans ses rapports successifs sur le réchauffement climatique, et concernant plus particulièrement les calculs d’émission de gaz à effet de serre dans l’atmosphère, le Groupe d’Experts Intergouvernemental sur l’Évolution du Climat (GIEC) a d’abord considéré que 1,25% des doses d’engrais azoté appliquées aux sols cultivés est converti en N2 O [1]. Plus récemment, le GIEC a revu ce taux d’émission à la baisse (1%) suite à une nouvelle méta-analyse [5]. Or l’impact de cet écart d’estimation est considérable sur les scénarios de réchauffement climatique. Il est donc crucial de parvenir à l’estimation la plus fiable et la plus précise possible, et cela dépend d’abord de la qualité du corpus de sources scientifiques rassemblé. Ce papier étudie l’estimation des émissions de N2 O liées aux quantités d’engrais azotés apportées aux cultures. 3.1 Corpus La production mondiale d’articles scientifiques est en croissance vertigineuse depuis de nombreuses années (⇠470 000 en 1988 contre ⇠990 000 en 2008 selon le rapport de l’UNESCO sur la science 2010). La plus grande partie de cette production est désormais potentiellement accessible sur Internet et il existe différents sites Internet as- surant le référencement de ces publications. Parmi ceux-ci, l’un des acteurs majeurs du marché est le Web of Science (Thomson Reuters) qui regroupe de multiples domaines scientifiques au sein de ses bases de données. La recherche de documents sur le Web of Science s’effectue en précisant une thématique et des mots-clés. Par exemple, la requête avec les mots-clés « nitrous oxide » et « crop » retourne environ 1400 articles. Partant des 1400 articles sélectionnés grâce à la première requête par mots-clés sur le Web of Science, les experts ont étudié les abstracts de 44 articles, étiquetant 20 d’entre eux comme « non-pertinent » et 24 comme « pertinent » formant ainsi le corpus utilisable pour l’entraînement et l’évaluation de notre méthode à chacune de ces étapes : d’abord filtrage sur la base des abstracts puis sur la base des contenus par l’analyse des légendes des figures et des tableaux. Les fichiers PDF correspondant à ces documents représentent un spectre assez large de documents types liés à la thématique de recherche sur les émissions de gaz à effets de serre. Ils sont issus d’une dizaine de revues scientifiques différentes parmi les plus représentées dans le domaine de la biologie (Elsevier, etc.). Leur examen montre que l’agencement des parties de document ainsi que les formalismes utilisés sont très variés selon les publications, ce qui représente un défi supplémentaire pour la mise au point d’une méthode générique de récupération du contenu d’un document sous format PDF 3 . 3.2 Mise en œuvre de la méthode Le retrait de mots-standard (stop-words), la lemmatisation et le stemming ont été réalisés sur ces 44 abstracts, ramenant le nombre de termes de description à 1413. Afin d’examiner comment varie la richesse du vocabulaire, ainsi que sa redondance, dans les abstracts, nous avons tracé la courbe du nombre t de termes différents en fonction du nombre n d’abstracts étudiés. Cette courbe a été obtenue par tirages aléatoires répétés de k abstracts parmi les 44 étiquetés avec calcul de la moyenne et de l’écart-type (voir Figure 1). La courbe, d’allure concave, montre que le nombre de termes croît sub-linéairement avec le nombre d’abstracts. Cependant, même s’il y a donc redondance, les mêmes termes étant utilisés dans plusieurs abstracts, il y a introduction significative de nouveaux termes (environ 30) encore au 42ème abstract. Une fois cette première étape de réduction de la dimension des abstracts effectuée, les expériences réalisées avaient plusieurs objectifs : 1. Déterminer le nombre optimal d’abstracts à étiqueter pour obtenir une bonne performance de discrimination entre articles prometteurs et articles à rejeter. Étant donné le coût en temps expert de l’étiquetage des articles et la tendance des experts humains à augmenter leur taux d’erreur d’étiquetage avec le nombre 3. Faute de place, nous ne détaillons pas la méthode mise au point pour cette extraction, qui a cependant représenté une bonne moitié de notre travail et dont la qualité est cruciale pour le reste de l’analyse. F IGURE 1 – Nombre moyen d’attributs n (et écart-type) en fonction du nombre k d’abstracts considéré pour 100 tirages aléatoires à traiter, il est souhaitable de limiter au maximum la taille requise du corpus d’entraînement. 2. Mesurer l’effet des changements de représentation en comparant trois situations : – performance sans changement de représentation (pas de réduction au delà de la première étape) – performance en utilisant la méthode de codage par mdl-entropie – performance en utilisant le recodage par motifs fréquents 3. Comparer les performances sur ce problème de diverses méthodes de classification supervisée. Nous avons comparé trois méthodes ayant des fondements différents : – Les arbres de décision – Le classifieur naïf de Bayes – Les séparateurs à vastes marges (SVM), ici avec un noyau à base radiale 3.3 Résultats Sélection des attributs et recodage par motifs Aussi bien les méthodes de recodage par sélection d’attributs (mdl-entropie) que les méthodes par construction de nouveaux descripteurs (motifs fréquents) dépendent du corpus d’entraînement. Il était donc important d’analyser l’impact de la taille du corpus d’entraînement (le nombre d’abstracts) sur le recodage obtenu. La méthode de sélection de descripteurs par mdl-entropie apparaît satisfaisante à trois titres. Elle conduit à un codage de petite dimension, celui-ci est stable puisque les mêmes descripteurs sont sélectionnés lors des tirages, enfin les descripteurs sélectionnés semblent pertinents comme l’indique la présence de termes liés à des unités de mesure (« kg », « ha »), qui sont effectivement des cibles de la méta-analyse. Le recodage par motifs fréquents présente grossièrement les mêmes caractéristiques : stabilité des motifs, pertinence apparente, mais les nouveaux descripteurs ressortent en plus grand nombre, nombre qui varie fortement en fonction du taux de couverture utilisé. Il est notable que 80 à 90 % des motifs retenus proviennent des documents de la classe « pertinent » tandis que seulement 10 à 20 % sont issus des documents non pertinents avec une intersection assez faible entre ces deux ensembles. Cela démontre que les documents « non pertinent » exploitent un vocabulaire plus diversifié et sont plus hétérogènes que les documents « pertinent ». Comparaison des méthodes de classification supervisée et nombre optimal de documents à étiqueter Une méthode de filtrage de documents pertinents sera performante et donc utilisée si elle demande aux experts un effort d’étiquetage faible, c’est-à-dire portant sur peu de documents, et si cela permet néanmoins d’obtenir une règle de classification efficace, ce qui veut dire en premier lieu maximisant le rappel (peu de faux négatifs) sans que cela soit trop au détriment de la précision (aussi peu que possible de faux positifs). Nous avons comparé les performances des trois classifieurs : Séparateurs à Vastes Marges (SVM) (noyau gaussien avec = 0.5), arbres de décision (C4.5) et Naïve Bayes (NB) en termes de rappel et précision en faisant varier le codage utilisé. Sans recodage (après lemmatisation et stemming), les performances ont été obtenues par répétition de tirages de n abstracts d’entraînement (avec équirépartition de « pertinent » et « non pertinent » dans les ensembles d’apprentissage et de validation). On a fait varier n de 10 à 42 (auquel cas il reste 2 abstracts de validation : un « pertinent » et un « non pertinent »). Avec recodage, la procédure est la même. Pour chaque valeur de n considérée, on a répété 100 tirages aléatoires de n abstracts parmi les 44 étiquetés par les experts. Pour chaque tirage, le codage est calculé (parfois avec plusieurs valeurs de support pour le codage par motifs fréquents), puis utilisé pour coder les exemples d’entraînement et de test. La performance en rappel et précision est alors obtenue pour chaque valeur de n par calcul de la moyenne sur les 100 répétitions. Les meilleurs résultats ont été obtenus avec les SVM. Sans recodage Rappel (n = 20) (n = 40) Précision (n = 20) (n = 40) SVM 68% 80% 80% 90% Avec le recodage par motifs fréquents : motifs fréquents SVM C4.5 NB Rappel (n = 20) 87% 96% 96% (n = 40) 96% 100% 98% 74% v62% 54% v83% 65% 55% Précision (n = 20) (n = 40) De ces tableaux, il est possible de tirer les conclusions suivantes : 1. Le recodage améliore sensiblement les performances. 2. Le recodage par motifs fréquents est le plus performant, alors même qu’il implique un plus grand nombre de descripteurs que le codage par mdlentropie. Cela peut être dû à ce que ce codage capture mieux les structures du texte. Plus probablement, cela est dû au fait que le codage lui-même distingue déjà beaucoup les deux classes de textes. 3. Il est possible d’obtenir un rappel de quasiment 100% par recodage par motifs fréquents (support 0.5) et utilisation des arbres de décision, avec une précision qui est alors de 65%. 4. Il est possible d’obtenir une bien meilleure précision en utilisant les SVM (83%), mais c’est au prix d’un rappel de 96% ce qui peut être rédhibitoire dans une tâche de méta-analyse qui ne veut pas laisser passer de documents pertinents. 5. On obtient déjà d’excellents résultats à partir de 20 abstracts d’entraînement. L’amélioration des performances étant faible ensuite. La méthode qui maximise le rappel est donc celle qui repose sur un recodage par motifs fréquents et une classification supervisée par arbres de décision, avec apprentissage sur au moins une vingtaine d’articles. Dans un contexte dans lequel on peut estimer à 10% environ la proportion des articles pertinents (soit environ 150 sur 1440 articles sélectionnés sur la base des mots clés), trois stratégies sont intéressantes à comparer pour évaluer l’effort demandé aux experts. Toutes les trois reposant sur un recodage par motifs fréquents, le plus performant. 1. Utilisation d’un corpus d’entraînement de 40 abstracts (20 « pertinent » et 20 « non pertinent ») et apprentissage d’arbres de décision. Le rappel est alors de 100% et la précision de 65%. La matrice de confusion est alors proche de : Avec le recodage issue de la méthode mdl-entropie : mdl-entropie SVM C4.5 NB Rappel (n = 20) 76% 80% 70% (n = 40) 90% 90% 86% Précision (n = 20) 72% 72% 68% (n = 40) 75% 74% 74% XXX XXXRéelle XXX Estimée + + (P) (N) VP = 144 FP = 144 0.35 ⇡ 78 0.65 FN = 0 VN = 1218 Pour obtenir 40 abstracts d’entraînement, dont 20 positifs (« pertinents »), les experts ont du préalablement examiné environ 200 documents. Après filtrage par recodage et apprentissage d’une règle de décision, il en ont encore 222-20 soit environ 200 à examiner pour finalement découvrir les 144 documents pertinents. Au total, les experts auront étiqueté environ 400 documents, soit environ 28% des 1440 documents initiaux. 2. Utilisation d’un corpus d’entraînement de 20 abstracts (10 « pertinent » et 10 « non pertinent ») et apprentissage d’arbres de décision. Le rappel est alors de 96% et la précision de 62%. La matrice de confusion est alors proche de : XX XXX Réelle XXX Estimée X + (P) + VP = 138 ⇡ 85 FP = 144 0.35 0.65 FN = 6 VN = 1211 (N) Avec cette stratégie, les experts doivent préalablement examiner environ 100 documents pour obtenir le corpus d’entraînement, puis encore 128 + 85 ⇡ 215 documents, soit au total 315 documents, ou 22% des 1440 documents initiaux. Le prix à payer pour cet effort moindre que dans la stratégie précédente est de courir le risque de manquer 6 documents pertinents. 3. Utilisation d’un corpus d’entraînement de 40 abstracts (20 « pertinent » et 20 « non pertinent ») et apprentissage par Séparateurs à Vastes Marges. Le rappel est alors de 96% et la précision de 83%. La matrice de confusion est alors proche de : XXX XXXRéelle XXX Estimée + 4 Conclusion et perspectives Étant donnée la globalité, tant spatiale que temporelle, des processus environnementaux, c’est une multitude d’études fragmentaires et partielles qu’il faut savoir prendre en compte. Seul un processus automatisé défini avec soin peut à la fois permettre d’en faire l’analyse et de garantir l’objectivité et la reproductibilité de celle-ci. Ce papier a présenté une méthode visant à aider les experts à faire le tri des articles scientifiques portant sur une question donnée pour n’avoir à analyser que les articles pertinents : seulement ceux-ci mais tous ceux-ci. Le souci est de maximiser le rappel tout en ayant une bonne précision. De notre étude, il ressort que le recodage par motifs fréquents est le plus performant, couplé à un apprentissage par arbre de décision ou par Séparateurs à Vastes Marges (SVM). La méthodologie décrite a été testée sur un problème d’estimation d’émission de gaz à effet de serre, le N2 O, par kilo d’engrais épandu sur les terres agricoles. Elle a permis de voir qu’à partir d’environ 10 articles étiquetés « pertinent » et 10 « non pertinent », il était possible d’apprendre une règle de décision portant sur les abstracts permettant d’éliminer environ 80% des articles potentiels (ici 1440) sans risque (quasiment) d’éliminer des faux négatifs. Remerciements. Nous remercions le Conseil Scientifique d’AgroParisTech pour le soutien au projet ExtraEx dans le cadre de l’appel d’offre annuel en 2012 sur les projets scientifiques, ainsi que le soutien par le Réseau National des Systèmes Complexes lors de l’appel à Réseaux pour l’année 2013. Références [1] Bouwman, A. (1996). Direct emission of nitrous oxide from agricultural soils. Nutrient cycling in agroecosystems 46(1), 53–70. [2] Cornuéjols, A. and L. Miclet (2010). Apprentissage Artificiel. Concepts et algorithmes (2nd Ed.). Eyrolles. + (P) (N) VP = 138 FP = 144 0.17 ⇡ 29 0.83 FN = 6 VN = 1267 Avec cette stratégie, les experts doivent préalablement examiner environ 200 documents pour obtenir le corpus d’entraînement, puis encore 128 + 29 ⇡ 160 documents, soit au total 360 documents, ou 25% des 1440 documents initiaux. Cette stratégie est à michemin des deux précédentes en termes d’effort demandé aux experts. On voit que les trois stratégies permettent une économie très sensible du travail demandé aux experts en terme d’examen des documents sans conduire à un taux de faux négatifs important (moins de 4%). [3] Kohavi, R. and M. Sahami (1996). Error-based and entropy-based discretization of continuous features. In Proceedings of the second international conference on knowledge discovery and data mining, pp. 114–119. [4] Mosier, A., J. Duxbury, J. Freney, O. Heinemeyer, and K. Minami (1998). Assessing and mitigating N2O emissions from agricultural soils. Climatic Change 40(1), 7–38. [5] Stehfest, E. and L. Bouwman (2006). N2O and no emission from agricultural fields and soils under natural vegetation : summarizing available measurement data and modeling of global annual emissions. Nutrient Cycling in Agroecosystems 74, 207–228. Simuler l’assolement d’un paysage par reproduction des structures locales T. Guyet1,3 1 Y. Moinard2,3 R. Quiniou2,3 AGROCAMPUS-OUEST/IRISA UMR 6079, Rennes 2 Inria [email protected], [email protected], [email protected] Résumé Le développement d’outils pour la simulation de paysages virtuels est un enjeu important pour l’étude des relations croisées entre les paysages, les processus biophysiques et leurs acteurs. L’approche suivie dans ce travail consiste à engendrer des paysages réalistes en s’intéressant à reproduire des structures locales caractéristiques d’un paysage réel. Cet article propose la démarche générale de la simulation de paysage en deux étapes principales : 1) la fouille de motifs fréquents et 2) la recomposition d’un paysage réaliste à l’aide de méthodes de programmation logique (ASP) incluant la génération de l’assolement. Nous présentons quelques résultats de simulation et des règles expertes qui peuvent être utilisées pour contraindre la génération. Mots Clef Graphe, ASP, programmation logique, simulation, paysage Abstract The development of tools for the simulation of virtual landscapes is an important issue for the study of the relationships between landscape, biophysical processes and their actors. Our approach generates realistic landscapes by reproducing characteristic local structures of a real landscape. This paper proposes the general approach of the simulation landscape in two main steps : 1) the extraction of frequent patterns and 2) the reconstruction of a realistic landscape using the method of logic programming (ASP) including generation crops. We present some simulation results and expert rules that can be used to constrain the generation. Keywords Graph, ASP, logic programming, simulation, landscape 1 Introduction De plus en plus de recherches en agronomie s’intéressent aux processus agro-écologiques en interaction avec un paysage. Mais les agronomes ne disposent généralement pas d’une variété importante de paysages réels pour identifier les interrelations entre les caractéristiques de paysage et les processus agro-écologique. La simulation de paysages virtuels, réalistes et paramétrables doit pallier ce manque de données réelles. Ces paysages virtuels serviront de support à la simulation du processus étudié pour comprendre les interactions entre paysage et processus. Nous définissons un paysage agricole comme l’organisation spatiale d’éléments paysagers naturels (p. ex. parcelles agricoles, haies, plans d’eau) ou artificiels (p. ex. bâtiments, routes) avec lequel interagissent des acteurs aussi divers que des agriculteurs, des insectes, la faune en général, la végétation naturelle et cultivée, etc. Un paysage virtuel est une représentation numérique d’un paysage. L’approche de simulation de paysage réaliste que nous mettons en œuvre est inspirée de Le Ber et al. [9]. Cette méthode de simulation neutre de paysage consiste à extraire des caractéristiques des paysages et de les reproduire dans les paysages simulés. La méthode est dite “neutre” par opposition aux modèles décisionnels qui s’appuient sur la modélisation des acteurs et de leurs pratiques pour générer les paysages (p. ex. Akplogan et al. [1] ou Bergez et al. [3]). La méthodes de Lazrak et al. [8] proposent une approche combinant la modélisation des acteurs et la modélisation stochastique de la dynamique d’organisation spatiale et temporelle des paysages agricoles. Nos travaux s’intéressent à la génération d’un assolement pour un paysage agricole, c’est-à-dire à l’attribution des types de culture (blé, prairie, maïs, etc.) à chaque parcelle agricole d’un paysage. Pour les besoins d’études agronomiques portant sur des populations animales vivant dans les haies et talus, nous cherchons à reproduire les caractéristiques organisationnelles des paysages agricoles, i.e. d’avoir des colocalisations de parcelles réalistes. Le processus général présenté dans cet article est illustré par la figure 1. Le processus comprend trois étapes principales : 1. extraction des structures caractéristiques d’un parcellaire réel. On construit également l’ensemble des structures “nues” (sans attribution d’occupation du sol) 2. décomposer un parcellaire nu (à assoler) en sousstructures 3. attribuer les occupations du sol des nœuds aux par- F IGURE 1 – Processus de simulation d’une occupation du sol en trois étapes : 1) l’extraction de structures caractéristiques d’un paysage, 2) la décomposition du nouveau parcellaire à assoler et 3) l’attribuer d’une occupation du sol. celles correspondantes Dans nos travaux précédents, nous avons mis en place une méthode d’extraction des colocalisations de parcelles, appelées par la suite structures, à partir d’un paysage numérique représenté sous la forme d’un graphe d’adjacence des parcelles [6]. D’autre part, nous nous sommes intéressés à la formalisation du problème de la simulation d’un assolement [7]. La simulation de l’assolement y est vue comme un problème combinatoire de décomposition du graphe de parcelles par des structures. Dans cet article, nous mettons en œuvre ces travaux pour générer effectivement des paysages agricoles. Nous revenons pour cela sur les étapes d’extraction de structures et de recomposition d’un graphe puis nous présentons la génération de l’assolement. Cette génération est effectuée sous contraintes ajoutées par l’expert. 2 Représentation des paysages sous la forme d’un graphe Dans notre approche, un paysage est représenté par un graphe dont les nœuds sont des parcelles agricoles et dont les arcs sont des relations spatiales entre les parcelles agricoles [6]. Cette représentation met en exergue des structures dans le paysage (i.e. des colocalisations de parcelles). Le graphe est construit à partir d’un parcellaire agricole qui décrit la géométrie et l’occupation du sol des parcelles. Les sommets du graphe représentent les parcelles. Ils sont caractérisés par un attribut qualitatif qui donne l’occupation du sol (p. ex. prairie, blé, forêt, bâtiment, route, etc. les données comprennent 20 types d’occupations du sol au total). Les arêtes du graphe indiquent une relation d’adjacence entre deux parcelles. L’information spatiale n’est conservée qu’au travers de l’existence de ces arrêtes. La relation d’adjacence a été adaptée pour tenir compte des données. En particulier, nous faisons en sorte que deux parcelles situées de part et d’autre d’une route, d’un chemin, d’une voie ferrée ou d’une haie soient considérées comme adjacentes dans le graphe. Les arêtes du graphe sont nonorientées et ne sont décrites par aucun attribut. Dans la suite, nous notons G = hV, E, µi un graphe où V est l’ensemble des nœuds du graphe, E ⇢ V ⇥ V l’ensemble des arcs du graphe et µ : V 7! ⌃ la fonction attribuant une occupation du sol à un nœud (⌃ représentant l’ensemble des occupations du sol). 3 Fouille de structures fréquentes L’utilisation de méthodes de fouille de sous-graphes fréquents extrait des sous-graphes récurrents dans un paysage. Ces sous-graphes caractérisent le paysage. Nous avons adapté les algorithmes de fouille de sous-graphes à notre problématique dans un outil appelé G EO S PAN. Cet algorithme est une adaptation de l’algorithme G S PAN [10]. Nous avons repris la méthode d’énumération de sousgraphes mais nous y avons intégré la méthode d’énumération de sous-graphes de Bringmann et Nijssen [4]. La définition du seuil de fréquence minimum requis pour identifier un motif comme intéressant a également été adaptée. La distribution des occupations du sol d’un parcellaire est fortement déséquilibrée. En particulier, les prairies sont très fortement sur-représentées. Avec de telles caractéristiques, les méthodes classiques de fouille de sousgraphes sont limitées par la sur-représentation de motifs comportant uniquement (ou très majoritairement) des prairies. À nombre d’occurrences égal, les motifs comportant des occupations du sol plus fréquemment rencontrées sont donc moins intéressants que ceux qui comportent des occupations du sol plus rares. La fonction de seuil de fréquence minimum ⌧ (m) pour un motif m est définie ci-dessous. Un motif m est fréquent si le nombre de ses occurrences est supérieur à ⌧ (m). 8 si ⇢(m) < 1 < 1 ⇢(m) si 1 < ⇢(m) < ⌧ (m) = : si ⇢(m) > avec, ⇢(m) = ↵ ⇥ min (f (µ (n))) + n2V (m) ⇥ |V (m)|2 où V (m) est l’ensemble des nœuds du motif m, |V (m)| le nombre de ces nœuds, et f (os) est la fréquence de l’occupation du sol os 2 ⌃ dans le graphe. ↵ et sont deux nouveaux paramètres, et désigne le seuil de fréquence habituellement fixé pour les algorithmes de fouille de données. Le seuil d’un motif ⌧ (m) est donc fonction de la fréquence de l’occupation du sol la moins fréquente dans le graphe, et de la taille du motif. Si on considère une fonction de la forme ↵ ⇥ minn2V (m) (f (µ(n))) + (|V (m)|) où ↵ 2 [0, 1] et (|V (m)|) est une fonction du nombre de sommets dans le motif, alors le critère de fréquence d’un motif devient de plus en plus strict à mesure que le motif grandit. Une telle manière d’adapter le seuil de fréquence est compatible avec la propriété d’anti-monotonie de la mesure de support. Une fonction croissant rapidement associée à un seuil maximum important ne gardera que des petits motifs. Une fonction croissant rapidement associée à un seuil maximum bas gardera les petits motifs contenant des sommets peu fréquents en permettant d’avoir des motifs plus grands avec des sommets fréquents. L’utilisation d’un seuil dépendant d’une fonction quadratique du nombre de nœuds est un bon compromis entre les temps de calcul et la diversité des motifs. Le résultat de la méthode de fouille de sous-graphes fréquents est un ensemble N de graphes attribués connexes. Pour le processus de génération, nous construisons également un ensemble de structures nues S à partir des structures de N (en supprimant leurs attributs). Tous les graphes sont distincts (i.e. il n’y a aucune paire de structures qui soient isomorphes). En revanche, si nous considérons ces structures sans leurs attributs (structures nues), il existe des structures nues isomorphes. Un seul exemplaire de structure nue isomorphe est conservé dans S. 4 4.1 Décomposition optimale graphe par des structures d’un Présentation du problème Soit G = hV, Ei un graphe représentant un parcellaire agricole nu (sans ses occupations du sol) et S un ensemble de structures nues. Une instance IS d’une structure S = hVS , ES i 2 S dans un graphe G est un sous-graphe de G isomorphe à la structure S : tout sommet de IS est un sommet de G et tout arc de IS est un arc E de G. Une décomposition du graphe G par S est un ensemble d’instances de S tel que chaque nœud de G est associé à une seule et unique instance. Une décomposition optimale est une décomposition comportant le nombre minimal d’instances (décomposition par un ensemble d’instances les plus grandes possible). La décomposition n’est pas nécessairement possible dans le cas général. En revanche, quel que soit le graphe G, si S contient la structure-singletons (constituées d’un unique nœud), alors la décomposition triviale en autant d’instances-singleton que de nœuds est possible, et donc une décomposition optimale existe. La décomposition optimale n’est bien sûr pas nécessairement unique. Cette tâche de décomposition peut s’apparenter à une coloration de graphe, mais nous n’avons pas connaissance d’une solution algorithmique concernant ce problème de décomposition. 4.2 Représentation du problème en ASP La programmation par ensembles réponses [2] (abrégé ici par l’acronyme anglais ASP, “answer set programming”) est proche de l’idéal de la programmation déclarative : le problème est le programme. La solution est un ensemble de modèles particuliers appelés ensembles réponses. Les moteurs de résolution des programmes ASP s’appuient sur des solveurs de contraintes efficaces. En pratique, nous utilisons l’outil clingo4 [5]. Le graphe et les structures sont représentés à l’aide des cinq prédicats node/1, edge/2, structure/1, snode/2, sedge/3 de la façon suivante : — node(X) : X est un nœud du graphe — edge(X,Y) : le graphe comporte un arc entre les nœuds X et Y — structure(S) : S est une structure — snode(S,P) : P est un nœud de la structure S — sedge(S,P,Q) : la structure S contient un arc entre les nœuds P et Q La représentation d’une solution au problème de décomposition d’un graphe par un ensemble de structures utilise les prédicats instance/2 et sgraph/3 : — instance(I,S) : I désigne une instance de la structure S dans le graphe. — sgraph(I, X, P) : le nœud X du graphe est associé au nœud P de l’instance I . L’ensemble des atomes sgraph décrit ainsi la décomposition du graphe en sous-graphes. La figure 2 illustre un AS, i.e. un modèle qui représente une décomposition optimale. 4.3 Résolution avec ASP Le programme ASP est composé de trois parties : 1. La partie “génération” consiste à générer des modèles potentiels, sans que ceux-ci répondent nécessairement à toutes les contraintes du problème. 2. La partie “contraintes” formalise les contraintes qui doivent être vérifiées par les solutions générées. Les Algorithme 1: Programme ASP de résolution d’une décomposition optimale d’un graphe par un ensemble de structures 1 2 3 F IGURE 2 – Illustration d’un AS. À gauche : le graphe, à droite : les instances. Les traits fins entre les nœuds des instances et les nœuds du graphe illustrent les atomes sgraph. 4 5 6 7 3. La partie “optimisation” définit les contraintes d’optimisation visant à identifier les solutions “les meilleures” par rapport aux critères choisis. Le principe de la génération (ligne 2 à 4) est de fixer un nombre d’instances K, et d’engendrer les atomes instance pour associer chacune de ces instances à une structure. L’ensemble des combinaisons de structures est ainsi exploré (p. ex. pour 2 structures : K instances de S1 et 0 de S2 , K 1 instances de S1 et 1 de S2 , etc.). Ceci est effectué pour toutes les valeurs de K possibles, i.e. de 1 au nombre de nœuds du graphe (ligne 1). 10 11 12 La contrainte de correspondance entre la structure et un sous-graphe de G est exprimée, lignes 27 et 28, à l’aide du nombre d’arcs d’un nœud X : { sgraph(I, Y, Q): edge(X,Y ), sedge(S, P, Q)} désigne l’ensemble des nœuds Y du graphe pour lesquels 1) il existe un arc entre X et Y pour la struc- % Contrainte sur le nombre de noeuds suminstance(I, L) : snumber(S,L), instance(I,S). : M { node(N) }, M=Tot+1, Tot=#sum{ L : suminstance(I, L) }. : { node(N) } M, M=Tot 1, Tot=#sum{ L : suminstance(I, L) }. 13 14 15 % Génération des correspondances L { sgraph(I, X, P): node(X), snode(S,P) } L : instance(I,S). snumber(S,L), 16 17 18 19 20 % Contraintes d’unicité des correspondances entre noeuds : sgraph(I,X,P), sgraph(I,Y,P), X<Y. : sgraph(I,X,P), sgraph(J,X,Q), Q<P. : sgraph(I,X,P), sgraph(J,X,Q), I<J. 21 22 : not sgraph(_,N,_), node(N,_). 23 24 25 26 Les contraintes sont ensuite exprimées par des règles “sans tête” pour exprimer “il n’est pas possible que”. La ligne 18 indique qu’un même nœud P d’une instance I ne peut pas être attribué à deux nœuds différents du graphe. Les contraintes d’unicité (lignes 18 à 22) assurent l’existence d’une bijection entre l’ensemble des nœuds des structures générées, et l’ensemble des nœuds du graphe G. Les lignes 19 et 20 indiquent la réciproque : un nœud du graphe est couvert par un unique nœud d’une unique instance. La ligne 22 indique que chaque nœud du graphe G doit correspondre à un nœud d’une structure générée. Cette contrainte élimine les solutions partielles où un nœud du graphe G ne figure dans aucun des atomes sgraph générés. Ces quatre contraintes imposent un nombre total de nœuds des structures égal au nombre de nœuds du graphe. Néanmoins, nous ajoutons les lignes 10 à 12 pour rendre explicite la contrainte sur la somme des nombres de nœuds des instances. Celle-ci est donc redondante, mais elle peut être utilisée en amont de la génération des atomes sgraph et ainsi élimine-t-elle très tôt des AS potentiels non valides. L’égalité s’exprime ici comme l’impossibilité des deux inégalités strictes (ligne 11 – élimine les cas avec un cardinal supérieur ou égal à M – et ligne 12 – élimine les cas avec un cardinal inférieur ou égal à M). % snumber donne le nombre de noeuds dans la structure S snumber(S, L) : L = #count{ N : snode(S,N) }, structure(S). 8 9 solutions générées qui ne satisfont pas toutes les conditions sont éliminées. % Génération des instances, nnode(NN) : nombre de noeuds du graphe 1{ nbinstances(1..NN): nnode(NN) } 1. instid (1.. K) : nbinstances(K). 1{ instance(I,S) : structure(S) } 1 : instid( I ) . 27 28 % L est le degré du noeud P dans la structure S sdegree(S, P, L) : L= #count{ N : sedge(S, P, N) }, structure( S), snode(S, P). % Contraintes de correspondance entre les arcs des graphes : { sgraph(I, Y, Q): edge(X,Y), sedge(S, P, Q) } M , instance(I , S), sgraph(I, X, P), sdegree(S, P, L), M=L 1. : M { sgraph(I, Y, Q): edge(X,Y), sedge(S, P, Q) }, instance(I, S), sgraph(I, X, P), sdegree(S, P, L), M=L+1. 29 30 31 32 %Optimisation nbinstances(L) : L={instance(I,S)}. #minimize { L : nbinstances(L) }. ture S dont I est une instance, et 2) il existe un arc entre P et Q. La taille de cet ensemble doit être exactement le degré du nœud correspondant dans la structure. Notons que par construction on a la correspondance dans un sens, et donc vérifier cette égalité assure la correspondance bijective. Finalement, la partie optimisation, lignes 31 et 32, précise que seuls les modèles dont le nombre d’instances est minimal sont calculés. Pour plus de détails sur la méthode et les choix de résolution, nous invitons le lecteur à consulter [7]. 5 Reconstruction d’un assolement avec ASP Le principe de la génération de l’occupation du sol est de faire correspondre les instances qui décomposent le graphe à des structures attribuées. Les attributs des structures donnent l’occupation du sol aux nœuds correspondants. Comme une instance est déjà associée à une structure nue, il s’agit de sélectionner une structure attribuée isomorphe à la structure nue de l’instance pour en déduire l’occupation du sol (OS). L’intérêt d’intégrer cette sélection à la résolution ASP est de lier la génération de l’organisation structurelle à celle de l’assolement. En effet, nous ajoutons la possibilité de définir des règles expertes sur la disposition des occupations du sol et celle de définir a priori l’occupation du sol de certains nœuds. Cette dernière fonctionnalité permet, par exemple, de fixer des nœuds correspondant à des "parcelles" d’eau, de route ou de bâti, mais éventuellement d’autres parcelles cultivées. Ceci permet d’utiliser notre outil pour compléter une occupation du sol plutôt que de générer intégralement un parcellaire. Nous présentons tout d’abord la génération des attributs, puis nous introduisons la définition de règles expertes pour améliorer le réalisme de l’attribution des parcelles. 5.1 ture dans l’atome asnode(AS,P,B). Ceci est exprimé par la négation d’avoir A différent de B. Si ce n’est pas le cas, le modèle n’est pas valide : il faut que le solveur ASP teste une autre attribution pour l’instance de ce nœud, voire qu’il modifie l’organisation des structures dans leur globalité. 1 2 3 4 5 Pour construire l’assolement, nous ajoutons les règles cidessous au programme précédent. La première règle sélectionne un type de structure attribuée pour chacune des instances qui sont générées par le programme précédent. Les deux règles suivantes permettent d’attribuer des OS uniques aux nœuds du graphe. La première de ces deux règles concerne les nœuds pour lesquels nous ne disposons pas d’information a priori (node_allocated(N) n’est pas défini). Dans ce cas, un atome gnode est généré à partir des informations de la structure attribuée de l’instance. La seconde règle concerne les nœuds pour lesquels l’OS est fixée a priori. Dans ce cas, il faut s’assurer que la structure attribuée utilisée correspond bien au nœud. Pour que les structures générées soient cohérentes, il est nécessaire que l’OS A corresponde avec l’allocation définie par la struc- gnode(N,A) : asnode(AS,P,A), selectedAS(AS,I), sgraph(I,N, P), not node_allocated(N). : gnode(N,A), node_allocated(N), asnode(AS,P,B), selectedAS(AS,I), sgraph(I,N,P), instance(I,S), A!=B. L’utilisation du même argument P dans sgraph (numéro du nœud dans la structure nue) et dans asnode (numéro du nœud dans la structure attribuée) impose l’égalité des numéros de nœuds et impose assure l’isomorphisme des deux structures. Génération d’attributs d’occupation du sol Nous complétons le programme précédent par des faits et règles pour générer les occupations du sol (OS) de chacun des nœuds. Nous introduisons pour cela de nouveaux prédicats : — asstructure(AS,S) : AS est une structure attribuée isomorphe à une structure nue S — asnode(AS,P,A) : A est l’OS du nœud P dans la structure AS — gnode(N,A) : A est l’OS au nœud N du grand graphe. — node_allocated(N) : le nœud N du parcellaire a une OS fixé a priori — selectedAS(AS,I) : l’instance I est associée à la structure attribuée AS Les atomes des prédicats asstructure/2 et asnode/3 sont générés automatiquement à partir des graphes obtenus par la méthode de fouille de données. Pour chaque structure nue, nous disposons d’un ensemble de structures attribuées dont les OS sont données par asnode/3. Les atomes du prédicat gnode/2 sont générés par le programme ASP, mais lors d’un assolement partiel – pour lequel certaines parcelles ont des OS fixées a priori – des atomes de gnode/2 et de node_allocated/1 sont fournis. %Sélection du graphe attribué pour chaque instance 1{ selectedAS(AS,I) : attstructure(AS,S) } 1 : instance(I,S). 5.2 Ajout de contraintes expertes L’un des intérêts d’utiliser la programmation logique est de pouvoir exprimer facilement des connaissances expertes sur l’organisation du paysage sous forme de règles. Les experts peuvent ainsi tester de nouvelles règles liées à l’organisation du paysage. Les agronomes pourraient ainsi s’intéresser à évaluer quel pourrait être l’influence sur le paysage de l’ajout d’une interdiction de cultiver des céréales à proximité immédiate d’un cours d’eau. D’autres connaissances expertes proviennent de la connaissance des pratiques agricoles. Nous donnons deux exemples illustrant l’utilisation de ces règles. Il faut, par exemple, éviter de mettre des cultures de céréales à côté de surfaces boisées pour éviter que ces cultures soient détériorées par les animaux. Cette règle peut s’exprimer ainsi : 1 2 3 % 8 code les céréales, 7 le maïs et 3 la forêt : edge(X,Y), gnode(X,8), gnode(Y,3). : edge(X,Y), gnode(X,7), gnode(Y,3). La représentation des nœuds précédente permettait de se focaliser sur le problème de la génération de l’assolement. Mais il est également possible de compléter la description des nœuds par des attributs complémentaires. À titre d’exemple, l’ajout d’atomes surface(N,T) (où N est le numéro d’un nœud et T est la surface de la parcelle) permettrait d’ajouter une contrainte sur la surface totale de prairie qui doit être au moins de 300ha sur l’ensemble du parcellaire : 1 2 % 61 code les prairies : #sum{ T : surface(N,T), gnode(N, 61) } 300 Ces deux exemples ne sont que des illustrations simples des règles expertes qu’il est possible d’écrire pour contraindre la génération des assolements. Leur expression est aisée et ASP offre une expressivité importante. Pour l’expert agronome, il suffit d’ajouter les contraintes souhaitées sans avoir à modifier le reste du programme. La résolution se chargera alors de trouver une organisation des parcelles agricoles qui respectent à la fois les structures locales et les règles expertes. 6 Résultats de génération structures ne comportaient que des parcelles de céréales ou de prairies à côté des forêts, le nouvel assolement ne fait quasiment pas apparaître de maïs. Dans ces expérimentations, nous utilisons des données issues de la Zone Atelier Armorique 1 située au nord de Rennes. Nous présentons ici des résultats de génération d’assolements comme résultat de l’ensemble du processus : construction des structures par fouille de graphe et génération d’une occupation du sol par résolution ASP. Pour la construction des structures à l’aide de la méthode de fouille de graphe, nous avons utilisé un jeu de données comportant 62 parcelles agricoles. Nous n’utilisons que les parcelles de culture et de forêt à cette étape. Les paramètres utilisés pour la fouille de graphe sont = 10, ↵ = = 1 et nous limitons l’exploration aux graphes comportant au maximum 3 arcs. Le nombre de structures attribuées est de 71 pour 5 structures nues différentes (sans compter la structure-singleton). La figure 3 illustre le parcellaire original dont nous nous servons pour illustrer la génération de l’assolement. Dans cette illustration, les parcelles en blanc sont des parcelles cultivées que nous cherchons à assoler. Les parcelles vertes correspondent à des forêts, les parcelles grisées sont des habitations ou des routes. Elles sont utilisées pour tester l’assolement partiel. F IGURE 4 – Exemple de paysages générés à partir, en haut, du paysage nu et, en bas, du paysage partiellement nu. En vert foncé : les forêts, en vert clair : les prairies, en jaune : le maïs, en orange : les autres céréales, en grisé : routes et habitations. Pour améliorer cet assolement, nous ajoutons des règles expertes pour interdire l’utilisation de parcelles de maïs ou de céréales à proximité des forêts (voir règles de la section précédente). La figure 5 (en haut) illustre le résultat obtenu. Il n’y a plus aucune parcelle de céréales voisine de la forêt, mais nous nous retrouvons avec une sur-représentation de parcelles de forêt. Nous ajoutons alors une contrainte sur le nombre maximal de parcelles de forêt par les règles ci-dessous pour obtenir le résultat de la figure 5 (en bas). F IGURE 3 – Paysage en entrée, partiellement nu (forêt, habitat et routes conservées) La figure 4 illustre le résultat obtenu par la génération sans utilisation de règles expertes. Le premier assolement est obtenu à partir du parcellaire nu (sans forêt ni route). On remarque, en particulier que la route a été transformée en forêt. Le parcellaire fait apparaître majoritairement des cultures de céréales (maïs et autres) et des prairies, qui sont les cultures les plus représentées dans le parcellaire réel. Les parcelles de forêt sont également utilisées, car présentes dans le jeu de structures utilisé. Le second assolement considère le parcellaire partiellement nu de la figure 3. Dans ce cas, dans la mesure où les 1. Une zone atelier est une zone d’étude de long terme sur laquelle des recherches pluri-disciplinaires sont menées. 1 2 3 4 % décompte du nombre de parcelles de forêt ngnode(L,3) : L=#count{ X : gnode(X,3) }. % ne pas pas avoir plus de 14 parcelles de forêt : ngnode(L,3), L>14. 7 Discussion et conclusions Dans ce travail, nous avons présenté le cadre général de la simulation de paysages agricoles qui reproduisent des organisations structurelles souhaitées. Les résultats de cette approche ont illustré la capacité de notre proposition à générer des occupations du sol en te- sonnables, mais des parcellaires comportant des tailles supérieures peuvent conduire à une explosion combinatoire et, en particulier, à un besoin de mémoire très important. L’utilisation des contraintes expertes facilite la résolution avec des solutions simples, mais le calcul d’une solution optimale nécessite beaucoup de temps de calcul. Une amélioration des temps de calcul pour un passage à l’échelle dans la génération de l’assolement reste un défi important. Il s’agit, en particulier, d’améliorer l’étape de décomposition d’un graphe par des structures. Références [1] M. Akplogan, S. de Givry, J-Ph. Métivier, G. Quesnel, A. Joannon, and F. Garcia. Solving the crop allocation problem using hard and soft constraints. RAIRO - Operations Research, 47(2) :151–172, 2013. [2] C. Baral. Knowledge representation, reasoning and declarative problem solving. Cambridge university press, 2003. [3] J.E. Bergez, N. Colbach, O. Crespo, F. Garcia, M.H. Jeuffroy, E. Justes, C. Loyce, N. Munier-Jolain, and W. Sadok. Designing crop management systems by simulation. European Journal of Agronomy, 32(1) :3 – 9, 2010. F IGURE 5 – Exemple de paysages générés à partir du paysage partiellement nu avec règles sur les céréales et le maïs. Dans le second cas, nous avons contraint le nombre de parcelles de forêts. nant compte à la fois des caractéristiques locales d’un paysage et également de contraintes exprimées par un expert. Les contraintes présentées illustrent la grande expressivité de l’ASP. Les règles peuvent facilement porter sur les nombres de parcelles, sur les surfaces cultivées et la prise en compte des territoires d’exploitation pourrait être envisagée. Une contrainte de l’approche pourrait être son caractère déterministe. Dans le cadre d’une étude agronomique, il est intéressant de disposer de plusieurs paysages pour effectuer plusieurs simulations avec les mêmes caractéristiques de paysage. Le déterminisme du solveur n’est pas limitant par rapport à cette question. En effet, le solveur clingo donne la possibilité de récupérer plusieurs ou toutes les solutions à un problème. Il est possible d’utiliser de manière aléatoire tous ces modèles possibles. L’outil doit néanmoins être testé et évalué par des agronomes. L’approche de résolution proposée contient néanmoins toujours des redondances liées à la combinatoire du problème de décomposition. Les temps de calcul nécessaire pour la résolution de l’ensemble des contraintes croît rapidement avec le nombre de parcelles du parcellaire à assoler ou avec le nombre de structures utilisées. Dans le cas des exemples proposés (46 parcelles), les temps de résolution permettant d’obtenir les premières solutions (non-optimales) sont rai- [4] B. Bringmann and S. Nijssen. What is frequent in a single graph ? In Proceedings of the 12th Pacific-Asia conference on Advances in knowledge discovery and data mining, pages 858–863. Springer-Verlag, 2008. [5] M. Gebser, R. Kaminski, B. Kaufmann, M. Ostrowski, T. Schaub, and M. Schneider. Potassco : The Potsdam answer set solving collection. AI Communications, 24(2) :107–124, 2011. [6] Th. Guyet. Fouille de données spatiales pour la caractérisation spatiale de paysages en lien avec des fonctionnalités agro-écologiques. In Spatial Analysis and GEOmatics (SAGEO’10), page 3, 2010. [7] Th. Guyet and Y. Moinard. Programmation par ensembles réponses pour simuler l’assolement d’un paysage. In Reconnaissance de Formes et Intelligence Artificielle (RFIA’14), page 7, 2014. [8] Mari J.-F. Lazrak E. G., Schaller N. Extraction de connaissances agronomiques par fouille des voisinages entre occupations du sol. In Atelier EGC/FDC, 2011. [9] F. Le Ber, C. Lavigne, K. Adamczyk, F. Angevin, N. Colbach, J-F. Mari, and H. Monod. Neutral modelling of agricultural landscapes by tessellation methods - application for gene flow simulation. Ecological Modelling, 220 :3536–3545, 2009. [10] X. Yan and J. Han. gSpan : Graph-based substructure pattern mining. In Proceedings of the 2002 IEEE International Conference on Data Mining, pages 721–. IEEE Computer Society, 2002.
© Copyright 2024 ExpyDoc
