F Le Ber
email: fleber@engees.u-strasbg.fr

M Benoît
email: benoit@mirecourt.inra.fr

C Schott
email: schott@mirecourt.inra.fr

J.-F Mari
email: jfmari@loria.fr

C Mignolet
email: mignolet@mirecourt.inra.fr

Présentation de CarottAge

CarottAge est un rétro acronyme construit à partir du mot carotte qui se traduit en markov en russe et du mot Âge. C'est aussi un procédé d'analyse de la constitution des sols. Faire un carottage d'un sol, c'est extraire par forage un cylindre représentatif des couches traversées afin d'étudier leurs successions et les dater.

CarottAge est le résultat d'un travail de fouille de données effectué par des agronomes de l'Inra SAD ASTER (Mirecourt) et des informaticiens du projet Orpailleur Loria et Inria Grand Est pour extraire des bases de données agricoles Ter-Uti des informations sur les successions de cultures pratiquées dans une région.

CarottAge s'appuie sur la théorie des chaînes de Markov cachées -HMM comme Hidden Markov Model -pour permettre l'analyse de successions d'observations quelconques continues ou discrètes. Ces modèles permettent de représenter des observations temporelles comme des successions d'états où les transitions entre états dépendent, suivant l'ordre du modèle, de l'état courant et des n états voisins.

Le logiciel calcule et affiche un signal dont l'analyse permet l'extraction et la datation de régularités temporelles et spatiales. Il est fourni sous forme d'une boîte à outils comportant plusieurs programmes indépendants ainsi qu'une application graphique qui permet de les enchaîner d'une façon interactive.

La première publication majeure de CarottAge se trouve dans la revue Ecological Modelling : Studying crop sequences with CarottAge, a HMMbased data mining software [START_REF] Ber | Studying Crop Sequences With CarrotAge, a HMM-Based Data Mining Software[END_REF] dont le pre-print est donné en annexe. Sa 1 lecture est vivement conseillée (désolé !) avant toute expérimentation.

Présentation des données Ter-Uti

Notre ensemble de données est constitué de l'enquête Ter-Uti qui est réalisée par un sondage à deux niveaux de granularité. Un premier tirage, réalisé par l'IGN, consiste à sélectionner des photos aériennes régulièrement réparties sur l'ensemble du territoire métropolitain. Les photos représentent chacune un carré de 2 km de côté et sont séparées en moyenne par 6 km. Un deuxième tirage, réalisé par les DRAF 1 , consiste à superposer sur chaque photo, une grille de 36 points. Compte tenu de la distance entre les photos, la représentativité d'un point est proche de 100 hectares. L'ensemble de ces sites est visité annuellement par des enquêteurs qui relèvent les occupations des sites. Pour plus de détails sur la grille Ter-Uti , on peut se reporter à [START_REF] Ledoux | De la photographie aérienne à la production de blé[END_REF].

Outre la séquence temporelle des occupations de chaque point, nous savons à quelle PRA il appartient et nous connaissons ses voisins, c'est-àdire la disposition relative de chaque point et de chaque photo aérienne. En revanche, nous ignorons la localisation précise des points pour des raisons de secret statistique.

Les services de statistique de la DRAF ont réparti les occupations en différentes classes (environ 80) qui vont de "marais salants, étangs d'eau saumâtre" à " peupliers épars" en passant par "superficie en herbe à faible productivité potentielle". Certaines de ces classes ne sont pas ou peu présentes dans les régions étudiées considérées aussi avons nous restreint le nombre de classes à 49, par regroupement ou suppression [START_REF] Benoît | Recherche des successions de cultures et de leurs évolutions : analyse par HMM des données Ter-Uti en Lorraine[END_REF]. (c) La photo aérienne et sa grille 6x6

Exemple pour débuter

Dans cette section, nous allons exécuter les différents outils de CarottAge sur le fichier de démonstration fourni short-example.txt. Comme décrit dans l'article [START_REF] Ber | Studying Crop Sequences With CarrotAge, a HMM-Based Data Mining Software[END_REF], la figure 1.2 montre bien la progression puis disparition de la jachère ainsi que l'érosion des prairies.

Visualisation de transitions entre cultures

Pour obtenir un résultat comparable à celui de la figure 2.1 page 23, il faut spécifier un nouveau modèle HMM dit " HMM ergodique avec états de Dirac". 1. spécification d'un modèle linéaire avec le même nombre d'états, à savoir 6 états : "blé", "orge", "colza", "maïs", "prairies + forêts" ainsi que l'état "?" qui joue le rôle de "container" et qui capturera toutes les exceptions (cf. Tab. 1.2).

2. transformation de ce HMM linéaire en ergodique par la commande lin to ergo. Toutes ces étapes sont regroupées dans le fichier do markov.bat (cf. Tab. 1.3).

estimation par la commande fwtInra

Utilisation de l'interface graphique CarottAge

L'archive contient une application graphique qui permet aussi d'enchaîner manuellement ces étapes en dispensant l'utilisateur de l'écriture des fichiers de commandes. Les résultats sont les mêmes dans les deux modes de fonctionnement : fichier "bat" ou interface graphique.

Première utilisation

A la première utilisation, CarottAge demande de choisir deux répertoires : un répertoire de travail qui contiendra les fichiers de données ainsi qu'un répertoire de binaires. Il est possible de revenir sur ces choix grâce à l'option Fichier.

Le choix du répertoire de travail

Le bon choix est le répertoire Mod/TerutiLucas ; Le choix du répertoire des binaires Le bon choix (et c'est le seul) est SrcPirenSpatial.

Le sous menu : données

Cette version de CarottAge traite des fichiers de données Ter-Uti élaborés à partir de données fournies par le Service central de la statistique agricole. Dans ce menu, il faut ici préciser où se situe le fichier short-example.txt (cf. Fig. 1.3). Ce menu permet aussi de se limiter à une période d'étude et d'appliquer un filtre d'extraction de points Ter-Uti , par exemple en précisant une liste de PRA ou de départements. Il faut pour cela avoir le fichier nouvelleFrance.txt.

Le sous menu : configuration

L'enquête Ter-Uti fournit une classification très précise de l'occupation du territoire. La centaine d'étiquettes différentes Ter-Uti doit être regroupée en un nombre bien inférieur de classes d'occupation du sol. Commencer par choisir dans ce sous menu : importer une configuration et choisir le fichier teruti1.cfg qui se trouve dans le dossier config. Par une série de glisser / insérer, on peut modifier ce regroupement. Avant de sortir de ce sous menu, valider la configuration, ce qui créera le fichiers des observations possibles.

Développements futurs

CarottAge a donné naissance à ARPEnTAg [START_REF] Mari | Time space stochastic modelling of agricultural landscapes for environmental issues[END_REF] car la recherche des successions de cultures dans un territoire a vite fait apparaître le besoin de pouvoir les localiser et faire apparaître des quartiers culturaux comme l'avait fait remarquer J.-P. Deffontaines [START_REF] Deffontaines | Managing rural areas. From pratices to model[END_REF].

Pour utiliser CarottAge sur d'autres jeux de données, il est nécessaire de créer un répertoire SrcMonProjet pour y dériver une classe à partir de Corpus0. Cela nécessite un travail de programmation en C++. Les explications pour y arriver dépassent le cadre de ce tutoriel et feront l'objet du Manuel du programmeur.

Chapter 2 Annexe

Studying crop sequences with CarrotAge, a HMM-based data mining software

Introduction

Sixty years after its launching through the "Marshall Plan", the European agriculture revolution is up again, but with some strong contradictions: water pollution, landscape uniformization, ethical crisis [START_REF] Fresco | Crop science: scientific and ethical challenge to meet human need[END_REF]. These harmful side-effects of agriculture could be aggravated if the evolution of agricultural practices continues following the current trends towards greater concentration, intensification and technicality. We focus on agricultural practices, from their choice by farmers decisions to their effects, as they continuously remodel the agricultural landscapes. The approach of farming systems as landscapes "builders" is a new one, but its background is the vision of land as resource for agriculture [START_REF] De Wit | Resource use efficiency in agriculture[END_REF][START_REF] Lardon | L'espace est aussi ailleurs[END_REF]. Agronomic measures specifically designed to maintain soil, water and air quality are necessary, including more severe regulations restricting intensification and the agricultural use of chemicals. For instance, keeping the nitrate content of drainage water to less than 50 mg.l-1 requires not only an optimized and reduced application of fertilizers, but also the planting of catch crops during the winter. Parts of the hydrological basins in many areas should be withdrawn from arable cropping and turned into grasslands or forests (several authors in [START_REF] Lemaire | Maîtrise de l'azote dans les agrosystèmes[END_REF]). Preventing runoff erosion and the associated pollution of surface water (especially by pesticides) needs grassland strips, ditches, or other structures placed in suitable strategic locations in a catchment. Again, similar conclusions could be drawn about many other environmental targets, such as biodiversity, or landscape quality and accessibility [START_REF] Boiffin | Cropping systems for the future[END_REF].

The farmer practices are the focus point of researchers who built tools to help their changes [START_REF] Benoît | Technical management: a central point for agronomy challenge[END_REF]. In this paper we propose a methodological approach of farmer practices involved in the land designing through land uses and land pattern changes. Actually, our approach combines agronomic and artificial intelligence methods. We rely on a land use data base, that we explore with a data mining approach, to find out spatial and temporal land patterns.

Mining sequential and spatial patterns is an active area of research in artificial intelligence. One basic problem in analyzing a sequence of items is to find frequent episodes, i.e. collections of events occurring frequently together. We rely on new numerical algorithms, based on high-order stochastic models -the second-order hidden Markov models (HMM2)capable to discover frequent sequences of events in temporal and spatial data. These algorithms can extract spatial and temporal regularities that can be explained by human experts and may constitute elements of a knowledge discovery process [START_REF] Mari | Temporal and spatial data mining with second-order hidden markov models[END_REF]. Thus, agronomists and computer scientist have designed a data mining software, named CarottAge, in order to extract crop sequences and patterns from land-use data bases. This software allows the user to specify the architecture of the Markov model according to the data and his objectives. Displaying tools have also been defined. CarottAge is used in several research projects, e.g. agronomists try to find out crop sequences in order to model nitrate loss due to agricultural activities. The paper is organized as follows. Part one is about the relationship between land and farmer practices and the modeling of crop rotations.

Part two is about HMM2 and the CarottAge software. Part three presents some results obtained by CarottAge on a French data base, and their analysis. Then we conclude and propose some perspectives.

An agronomic question 2.2.1 The relationships between land and agriculture

We want to focus on the mutual relationship between land and farmer practices: on the one hand, the current state of the land is a result of farming practices and changes in landscapes could not be decided without farmers participation, but on the other hand, the choice and location of cropping and grassland systems by farmers all over the world takes into account their own land characteristics [START_REF] Lardon | L'espace est aussi ailleurs[END_REF][START_REF] Le Moigne | Modelling the spatial organisation of land use in a farming territory. Example of a village in the Plateau Lorrain[END_REF]. This management of land by farmers is a part of the global technical management building agriculture [START_REF] Benoît | Technical management: a central point for agronomy challenge[END_REF] and is a factor of farm economical effectiveness [START_REF] Attonaty | Interactive simulation modelling in farm decision-making[END_REF]. The future of European land is based on this management [START_REF] Fresco | Future of the Land[END_REF]. Environmental issues may be converted into farming systems questions in which the activities of farmers and their changing location from the new picture is the focus point of problem solving [START_REF] Gaury | Systèmes de culture et teneurs en nitrates des eaux souterraines : Dynamique passée et actuelle en région de polyculture élevage sur le périmètre d'un gîte hydrominéral[END_REF][START_REF] Benoît | La place de l'agronomie dans la problématique environnementale[END_REF]. A number of new research tools such as remote-sensing data and Geographical Information Systems are now available to address this type of research [START_REF] Benoît | Agriculture et qualité de l'eau. une approche interdisciplinaire de la pollution par les nitrates d'un bassin d'alimentation[END_REF].

In most cases, farmers are seen to take into account the properties and layout of their land in deciding about the location of their cropping and grassland systems [START_REF] Morlon | Étude méthodologique d'un parcellaire d'exploitation agricole en tant que système[END_REF]. This relationship between farmers and their territory could be an individual or a collective one [START_REF] Gal | Coordination processes in a collectively managed cropping system: double cropping of irrigated rice in senegal[END_REF].

Land-use is managed by farmers

The land used by agriculture can be modeled as a complex and dynamic pattern of fields, including tilled plots and pastures. Sebillotte, in the 1st European Society of Agronomy Congress, defined the cropping system as a set of crop management procedures used on a homogeneously treated space inside a farm, which can be a field, or a part of field, or several fields. According to this definition, a given cropping system is a component of a farming system, and is identified (characterized) by the sequence of crops and corresponding technical operations [START_REF] Sebillotte | Some concepts for analysing farming and cropping systems and for understanding their different effects[END_REF].

The cropping system is a tool to characterize land use on the tilled part of farms [START_REF] Sebillotte | Système de culture, un concept opératoire pour les agronomes[END_REF]. However many farms have not only tilled crops but comprise also pastures. So if we want to reason at farm scale, it is necessary to generalize the concept of cropping system by including grasslands [START_REF] Gras | Le fait technique en agronomie. Activité agricole, concepts et méthodes d'étude[END_REF]. So we propose to name Agricultural Land Management System (ALMS) the system of crop and grassland management procedures used on a portion of land (which can be a field, or a part of field including its boundaries, or several fields). According to this definition, a given ALMS is a component of a farming system, and is identified (characterized) by the choices of the rotation of crops or grassland uses, the farmland structure and the location rules of the crop rotations and grassland uses. This definition should be completed by including also common items such as hedges, fences etc. that are components of the landscape and play a role in farm management [START_REF] Burel | Hedgerow network patterns and processes in france[END_REF]. For us, the ALMS is the basic unit of landscape design at farm scale. At a regional scale, other land uses and actors outside farms should be taken into account (forests, waters, wild areas) to complete the ALMS, according to the aims of the models (biodiversity management, water protection, leisure) as well as collective farmers' organizations [START_REF]Landschafts-modellierung für die Umweltplanung[END_REF][START_REF] Dabbert | Socio-economic analysis and modelling of agricultural water demands and land use[END_REF][START_REF] Herrmann | Ecological threshold values as indicators for biodiversity -economic and ecological consequences[END_REF][START_REF] Van Dijk | Soil erodibility parameters under various cropping systems of maize[END_REF][START_REF] Van Dijk | Retention of water and sediment by grass strips[END_REF].

A proposal of European notation for crop sequences identification

As a tool of representation and understanding of the interactions between agriculture, land and environment, agricultural land use management could be used as well for research as for management and negotiations in agro-environmental policies. The main topic in this way should be focused on land use changes [START_REF] Lambin | Land-use and land-cover change (LUCC): implementation strategy[END_REF][START_REF] Lambin | Dynamics of land-use and land-cover change in tropical regions[END_REF]. Although the agricultural practices we are familiar with are far from covering the whole range of existing systems, we shall propose a method for establishing a nomenclature of ALMS. The origin of these proposals lies in a number of monographs done for a large diversities of farms in a European research project1 [START_REF] Baudoux | On-farm effects and farmer attitudes towards agri-environmental programs: a case study in baden-wüttemberg[END_REF]. This first large range of landscape building monographs meets the work described in [START_REF] Morlon | Étude méthodologique d'un parcellaire d'exploitation agricole en tant que système[END_REF]. So, we propose a common notation of land use descriptions (Table 2.1) with two characteristics (i) description of the land uses as they are described, managed and decided by the actors, (ii) account of time scales as first organizational factor. All over Europe and each year, the farmers have to allocate their crops and grassland uses in their territory. This allocation is an important part of farmer decision that we have to model [START_REF] Cox | Some issues in the design of agricultural decision support systems[END_REF]. This annual adjustment between chosen crops and field plots results in different perennial rotations of crops and grassland use types [START_REF] Karlen | Crop rotations for the 21st century[END_REF]. Examples are:

• in Denmark: maize / maize / winter wheat / barley

• in south west France without irrigation: sunflower / winter wheat / barley

• in the East region of France: oil rapes / winter wheat

• in the plain of Rhine in Vorarlberg (Austria): maize / maize / temporary grassland for mowing (3 years).

These notations describe yearly sequence of crops or pasture uses as they are conceived by farmers: this has the advantages of corresponding to the planning structure of the farmer, which reasons rotations over several years, and to allow a stability of land use descriptions over years, whereas crop by crop descriptions would vary each year. However they lack the account of the logic behind the simple crop rotation description, although some hints may be given (such as maize for silage versus maize for sale) which complete the raw fact description, so these notations cannot yet be fully counted as ALMS nomenclature. In the future, our aim is to contribute to build a framework of farmer rules used to build rotations [START_REF] Boiffin | Cropping systems for the future[END_REF]. The first work done by [START_REF] Aubry | Modelling decision-making processes for annual crop management[END_REF] shows the importance of delay between two crops, sowing and harvesting dates, machinery choices.

Temporal Data Mining with HMM2

The purpose of pattern recognition is to specify as much models as there are classes to recognize. As opposite to pattern recognition, we do not have the knowledge of what to recognize but rather look for something regular to extract, hence the name data mining. Actually, data mining can be defined as the use of algorithms to extract information and patterns from databases [START_REF]Advances in Knowledge Discovery in Data Minig[END_REF][START_REF] Dunham | Data Mining[END_REF]. These algorithms are able to search the data and attempt to fit a model to the data, using some preference criteria. Data mining is a part of knowledge discovery processes that include four other steps: the selection of data, the preprocessing of data, the transformation of data, and the interpretation of the data mining results [START_REF] Dunham | Data Mining[END_REF].

In the present work, we specify one second-order Hidden Markov Model (HMM2) in order to model, in a more simple way, the unknown behavior of a crop sequence. We rely on the assumption that the land-use of a field at time t depends on the land-use of the same field at time t -1, t -2, etc. Each state of the HMM2 captures a stationary behavior and represents a class (a crop or a cropping pattern) where the observations are drawn with a known probability density function. Furthermore, we compute the a posteriori probabilities that the Markov chain goes through some states between certain time slots. These a posteriori probabilities can be plot as a function of time and determine a fuzzy classification in the states space. This classification can be interpreted by the agronomists wrt the evolution of crop patterns and crop sequences.

HMM2 definition and automatic estimation

The second order Hidden Markov Models are based on the probabilities and statistics theories. They are implemented with unsupervised training algorithms (like the EM algorithm [START_REF] Dempster | Maximum-Likelihood From Incomplete Data Via The EM Algorithm[END_REF]) that allow to estimate a model parameters from a corpus of observations and an initial model. The resulting model is capable to segment each sequence in stationary and transient parts and to build up a classification of the data together with the a posteriori probability of this classification. This characteristic makes the HMM2's appropriate to discover temporal and spatial regularities as it is shown in various areas (e.g. [START_REF] Benmiloud | Estimation des paramètres dans les chaînes de Markov cachées et segmentation d'images[END_REF][START_REF] Berndt | Finding Patterns in Time Series[END_REF][START_REF] Fine | The Hierarchical Hidden Markov Model: Analysis and Applications[END_REF][START_REF] Adibi | Self Similar Layered Hidden Markov Model[END_REF]). Furthermore, the very success of the HMMs is based on their robustness: even when the considered data do not suit a given HMM, its use can give interesting results. In a HMM2, the underlying state sequence is a second-order Markov chain. Therefore, the probability of a transition between two states at time t depends on the states in which the process was at time t -1 and t -2. A Markov chain is defined over a set of states -the crops in a field, or more generally the land-use categories in a place -that are unambiguously observed. The Markov chain specifies only one stochastic process, whereas in a HMM, the observation of a land-use category is not uniquely associated to a state but is rather a random variable whose conditional density depends on the current state at time t [START_REF] Baker | Stochastic Modeling for Automatic Speech Understanding[END_REF]. There is a doubly stochastic process:

• the former is hidden from the observer and is defined on a set of states;

• the latter is visible. It produces an observation, the land-use of a parcel, at each time slot depending on the probability density function that is defined on the state in which the Markov chain stays at time t. It is often said that the Markov chain governs the latter.

Thus, a HMM2 is specified by:

• a set of N states called S = {s 1 , . . . s N };

• a three dimensional matrix (a ijk ) over S 3 a ijk = Prob(q t = s k /q t-1 = s j , q t-2 = s i ) (2.1)

= Prob(q t = s k /q t-1 = s j , q t-2 = s i , q t-3 = ...)

with the constraints N k=1 a ijk = 1, ∀(i, j) ∈ [1, N ] 2 , and where q t is the current state at time t;

• a set of N discrete distributions: b i (.) is the distribution of observations associated to the state s i . This distribution may be parametric, non parametric or even given by an HMM.

The probability of the state sequence Q T 1 = q 1 , q 2 , ..., q T is defined as:

Prob(Q T 1 ) = Π q 1 a q 1 q 2 T t=3 a q t-2 q t-1 qt (2.2)
where ∀j, q j ∈ S, Π q 1 is the probability of state q 1 and a q 1 q 2 is the probability of the transition q 1 → q 2 (initialization of the model at times t = 1 and t = 2).

Given a sequence of observations O

T 1 = o 1 , o 2 , ..., o T , the joint state-output probability Prob(Q T 1 , O T 1 )
, is defined as:

Prob(Q T 1 , O T 1 ) = Π q 1 b q 1 (o 1 )a q 1 q 2 b q 2 (o 2 ) T t=3 a q t-2 q t-1 qt b qt (o t ). (2.
3)

The estimation of a HMM1 is usually done by the Baum-Welch algorithm which is related to the EM algorithm [START_REF] Dempster | Maximum-Likelihood From Incomplete Data Via The EM Algorithm[END_REF]. We have shown that a HMM2 can be estimated following the same way [START_REF] Mari | Automatic Word Recognition Based on Second-Order Hidden Markov Models[END_REF]. The estimation is an iterative process starting with an initial model and a corpus of sequences of observations that the HMM2 must fit. Usually, the initial model has equiprobable transition probabilities and an uniform distribution in each state. At each step, the Baum-Welch algorithm determines a new model in which the likelihood of the sequences of observation increases. Hence this estimation process converges to a local maximum, according to the maximum likelihood (ML) estimation criteria [START_REF] Dempster | Maximum-Likelihood From Incomplete Data Via The EM Algorithm[END_REF][START_REF] Mari | Probabilistic and Statistical Methods in Computer Science[END_REF]. To assess the final model, we use the Kullback-Leibler distance between the distributions associated to the states [START_REF] Tou | Pattern Recognition Principles[END_REF]. Two states that are too close are merged and the resulting model is re-trained.

Intuitively, the Baum-Welch algorithm counts the number of occurrences of each transition between the states and the number of occurrences of each observation in a given state in the training corpus. Each count is weighted by the probability of the alignment between the states and the observations (cf. Equation 2.3). The principles of this algorithm are detailed in the appendix.

CarottAge

CarottAge2 is a free software under a Gnu Public License that takes as input an array of discrete data -the rows represent the spatial sites and the columns the time slots -and builds a partition together with its a posteriori probability. CarottAge is written in C++ and runs under Unix and X11R6 systems. It has been designed specifically for mining land use data, based on HMM2. It is able to analyze temporal and spatial sequences of land use in a territory. Several models are available, we describe a few of them below. The CarottAge software is now used by agronomists -and also by geneticians for mining genomic data [START_REF] Hergalant | HMM, an Efficient Way to Detect Transcriptional Promoters in Bacterial Genomes[END_REF] without any assistance of the designers.

The functionalities of CarottAge

CarottAge get as an input preprocessed or transformed discrete data, represented within text files. Data mining is performed in four steps:

1. the editing of the initial model;

2. the iterative ML estimation using the Baum-Welch algorithm based on a corpus of sequences of observations;

3. the display of the model's parameters;

4. the display of the a posteriori transition probabilities.

The user has to write the initial model in two parts. The first part specifies the model's topology by means of a list of transitions between the states together with their relative weights. The second part defines the observations and gives the discrete probabilities over this set of observations. An example of a text file specifying a simple three statesleft to right -self loops HMM2, where the three states have a uniform distribution, is described in Table 2.2.

2 3 1 3 4 1 2 2 1 3 3 1 4 4 1 -1 -1 -1 equiprobable #state 2 equiprobable #state 3 equiprobable #state 4
Table 2.2: Initial model (lin3.mod): the first lines describe the transitions (a line is structured like: <origin> <extremity> <weight>), the last lines describe the distributions associated to the states. Here the hidden states are called 2, 3 and 4. The distributions are uniform.

Non-uniform distributions can be also defined. Then the state is described with a list of observations and their probabilities as follows:

1 wheat #state n which means that the state n contains only wheat, and that the probability of the other observations is null. CarottAge provides a program that builds a file containing the HMM2 according to the text file used as input.

The model is then estimated on a corpus of sequences represented by a matrix of observations. A typical command line is: estimate -n 3 lin3.mod -o lin3.mod1 lorraine.xls The input file lin3.mod (cf. Table 2.2) is estimated using the corpus specified by the file lorraine.xls. Three iterations are performed. The resulting model is stored in the output file lin3.mod1. Actually, this file records the a posteriori transition probabilities (see Equation 2.10 in the Appendix) between the states, and the distributions of observations associated to the states. A specific program has been developed for displaying the results of the model estimation (Figure 2.1). It displays both the model's parameters (especially the distributions) and the a posteriori probabilities of transitions between the states.

Models for mining land-use data

The role of the user is obviously crucial: it has to preprocess and transform the data, to define the initial model and to interpret the data mining results. Furthermore, these actions can be combined in a knowledge discovery process, where the data can be transformed in several ways and mined with various models. Actually, at the beginning of our work, the models were defined and experimented by the users (agronomists) and the computer scientists together [START_REF] Mari | Fouille de données agricoles par modèles de markov cachés[END_REF]. Then, the agronomists used CarottAge by themselves, and designed their own models, as shown in Section 2.4.2. A first model can be used for the extraction of temporal segments in which the distribution of the land-use categories is stationary. To do so, we have specified a HMM2 with n states with a left to right, self loops topology (see Figure 2.2). This means that we attempt to capture n periods of evolution in the land use dynamics, where n is chosen according to the length of the period. The results of this model are displayed within a table where the evolution of the cropping pattern of a region is visible (Figure 2.3). Here we see that the pastures are dominant at the beginning of the period, and then decrease and are replaced by wheat at the end of the period, while the surface of rapeseed is continuously growing. This table is actually a synthetic view of the eight years (1992 -99), pointing out the stable patterns and the main transitions. Another model has been designed for measuring the probability of a succession of three3 land-use categories. Actually, we have defined a specific state, called the Dirac state, whose distribution is zero except on a particular land-use category. Therefore, the transition probabilities between the Dirac states measure the probabilities between the land-use categories during a three years period. Figure 2 As results the user obtains a graphic showing the main transitions between Dirac and container states, i.e. the crop sequences in a region (Figure 2.5).

/ / % % ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ?>=< 89:; 3 / / % % ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ✾ ?>=< 89:; 4 _^]\ XYZ[ wheat 2 / / 9 9 r r r r r r r r r r r r r % % ❑ ❑ ❑ ❑ ❑ ❑ ❑ ❑ ❑ ❑ ❑ ❑ _^]\ XYZ[ wheat 3 / / 9 9 r r r r r r r r r r r r r % % ❑ ❑ ❑ ❑ ❑ ❑ ❑ ❑ ❑ ❑ ❑ ❑ _^]\ XYZ[ wheat 4 _^]\ XYZ[ maize 2 / / 9 9 s s s s s s s s s s s s B B ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ _^]\ XYZ[ maize 3 / / 9 9 s s s s s s s s s s s s B B ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ ✆ _^]\ XYZ[ maize 4
The user can choose the resolution level, and see all transitions or only the main transitions. In the graphic shown figure 2.5, six crops have been individualized (the container state is denoted by ?). The thickness of the lines represents the a posteriori probability of the transition between two crops (cf. Equation 2.10 in the Appendix). Diagonal lines mean that a crop is followed by another crop, e.g. rapeseed (denoted by colza) to wheat (denoted by ble), while horizontal lines mean that a crop is followed by itself, e.g. pastures (denoted by ppp in the figure). These tables are very useful for seeing the evolution of the land use in a region and for comparing regions. The models can be used on crop data, but also on sequences of crops, and allow to produce sets of tables showing the evolution or stability of land use. Compared to HMM1, HMM2 have the capability to model the transitions between Dirac states over a longer period -according to the farmer's practices-: three years compared to two years. Furthermore, these tables can be used as a support for field inquiries.

Finally, CarottAge allows the user to define various models, according to the data format and his purpose, as we see in the next part.

Using CarottAge for finding out crop sequences 2.4.1 The data base

The Ter-Uti data are collected by the French agriculture administration on the whole metropolitan territory. They represent the land use of the country on a one year basis. Two levels of resolution are achieved (Figure 2.6). A first sample consists in selecting aerial photographs. The French territory is segmented into 3820 meshes. Each of the meshes contains four photographs that cover each one only a square of 2 km. Secondly, on each photography, a 6 by 6 grid determines 36 sites that are inquired every year in June. The land-use category of these sites (wheat, corn, potato, forest, rocks . . . ) is logged in a matrix in which the rows are the sites of the country and the columns the time slots (from 1992 to 2003). Finally, one Ter-Uti site represents roughly 100 hectares [START_REF] Ledoux | De la photographie aérienne à la production de blé[END_REF].

Analyzing crop sequences in the Seine Basin

For thirty or forty years, the increasing human activities (domestic, industrial, agricultural) have gradually degraded the hydro-system of the Seine river, regarding water quality and biological population [START_REF] Meybeck | La Seine en son bassin, fonctionnement d'un système fluvial anthropisé[END_REF]. The nitrate contamination of groundwater and surface water is mainly caused by the evolution of agricultural activities, and related to their nature and to their organization inside the river watershed. The INRA team in Mirecourt is member of an interdisciplinary research program which aims to develop a tool for forecasting water quality in the Seine river watershed, based on assumptions upon agricultural changes. Thus, the INRA team analyses the agricultural activities in the watershed, their dynamics and their spatial organizations, focusing on the crop (temporal) rotations that are able to explain the risk of nitrate loss [START_REF] Mignolet | Spatial dynamics of agricultural practices on a basin territory: a retrospective study to implement models simulating nitrate flow. The case of the Seine basin[END_REF]. The data mining software CarottAge has been used on Ter-Uti data from the Seine watershed.

Results are presented and analyzed below for a small district.

Crop sequences in Saint-Quentinois

The diagram shown in figure 2.7 displays the main annual transitions between crops and their evolutions. The importance of the transition between two crops is expressed with the thickness of the line joining the two crops. One can see that, in this district, the wheat-based rotations are in a majority: (c) an air photography and its 6x6 grid • the main transitions are wheat-beet-wheat (1) and wheat-pea-wheat (2), which have the thickest lines (bottom of the diagram).

• the transitions beet-pea (3) appear between 1992 and 1995 and then disappear.

• transitions like wheat-barley (4), or barley-beet (5), appear from 1996 (actually, they exist before 1996 but with a probability smaller than 1.5%).

One can also notice that the other crops, like rapeseed, maize, potatoes or set-aside are mainly followed or preceded with wheat. Furthermore, the transitions wheat-wheat [START_REF] Benmiloud | Estimation des paramètres dans les chaînes de Markov cachées et segmentation d'images[END_REF] seem to grow between 1996 and 1998.

Three-crop sequences in Saint-Quentinois

In order to better examine the crop transitions, we transform the Ter-Uti data and apply CarottAge on tables representing couples, triples or even quadruples of crops. To minimize the data set, we have to select the main rotations, based on our first analysis, e.g., for crop triples, wheat-beet-wheat, wheat-pea-wheat, etc. Thus, we obtain a second diagram where the states represent triples of crops, which is more difficult to explain but confirms our first analysis (Figure 2.8). For example, if we follow the sequence of the crop triples starting from beet-wheat-beet in 1992-94, the main transition (1) leads to the wheat-beet-wheat triple. From this last triple, there are several possibilities: a first one goes towards the triple beet-wheat-wheat (2), a second one towards beet-wheat-barley (3), a third one, which has the greatest probability, towards beet-wheat-beet (4) and finally a fourth one towards beet-wheat-pea [START_REF] Baudoux | On-farm effects and farmer attitudes towards agri-environmental programs: a case study in baden-wüttemberg[END_REF]. Knowing that two triples are connected when they share two crops, we can synthesize the last transitions in the following way: (2) beet-wheat-beet-wheat-wheat, (3) beet-wheat-beet-wheat-barley, (4) beet-wheat-beet-wheat-beet, (5) beet-wheat-beet-wheat-pea. Furthermore we notice a repeated pattern in this diagram, that looks like a chain link: this pattern is composed with the repeated transitions between the triples wheat-beet-wheat and beet-wheat-beet, and reveals the existence of the quadruple succession beet-wheat-beet-wheat. Another pattern made of oblique lines can be found in this diagram: for example, the line starting from the beet-wheat-beet triple in 1992-94 connects to wheat-pea-wheat, then pea-wheat-beet, wheat-beet-wheat and finally to beet-wheat-beet or again to beet-wheat-pea. This connected sequence proves that all these triples belong to the same beet-wheat-pea-wheat four-crops succession.

Clustering the districts of the Seine Basin

The analysis of crop sequences and the determination of the main successions (double, triple or even quadruple successions, as shown before) are a basis for comparing and classifying agricultural territories. The small districts and the sub-watersheds of the Seine basin were compared and clustered thanks to statistical methods applied on the sets of crop triples that characterized each district or watershed. Finally we built a district typology clustering the similar districts wrt the crop successions. More precisely, the analysis of Ter-Uti data in the Seine Basin was performed following these steps.

1. Determination of the main crop successions in each small district, using CarottAge (model 2) as explained in Sections 2.4.2 and 2.4.2. The whole basin was characterized with 64 3 or 4-crops successions, for 143 districts. The crop successions were clustered within 6 main categories, according to their agronomic function (cereals, break crops, etc.).

2. Computation of the distribution of the crop successions in each small district, using CarottAge (model 1). The districts were thus characterized -for a period-with sets of crop successions and their probabilities. This map highlights the strong spatial structure of the distribution of crop sequences in the Seine Basin. This structure is to be related to big geological forms, as for example:

Analysis of the

• The districts classified into "Rs-W-B dominant" are on the Jurassic calcareous plateaux (east of the basin).

• The districts of the classes "temporary grassland dominant" correspond to the granitic mountains of Morvan (south-east of the basin).

• The districts of the class "Bt-W-Bt-W dominant" occupy the silty plateaux of Picardy (north of the basin).

Conclusion

We claim that the concept of crop sequences is relevant and can be useful: it will help research on agriculture/environment relations by providing types of land use that convey the farmer's strategy, independently of year to year changes that characterize crop rotations; these types of land use are stable over several years and can be related, on one side to field characteristics and constraints, and on the other side to environmental effects. It will facilitate discussions between farmers and other actors of rural territories by setting a common language and allowing an objective description of agricultural land use types. This concept, by considering the middle-term strategy of the farmer, frees itself from the infinite diversity of actual crop successions and facilitates the comparison between fields similarly managed in different farms, and hence facilitates the extension of cropping system research to the territorial and multi-year scales, which are relevant to environmental questions. The concept of agricultural land management system is a first step towards the precise description and classification of all types of land uses intervening in a region. In order to understand and manage the evolution of landscapes, it will be necessary to include non agricultural uses: forests, waters (in marshes, waters are subject to a particular type of collective management), roads and roadsides, etc. With respect to this purpose, CarottAge has proven useful for exploring large land use data bases and for revealing the temporal and spatial organization of land use, based on crop sequences [START_REF] Mari | Temporal and spatial data mining with second-order hidden markov models[END_REF]. Furthermore, CarottAge can also be used to investigate and visualize the crop sequences of a few specific farms or of a small territory. Besides, the diagrams resulting from CarottAge, showing the main crop transitions, are good graphical supports for discussing the evolution of land use. For example, they have been used during regional farm surveys to collect the knowledge of farmers and agricultural technicians about crop sequences. Finally, the results of our analysis can be linked to models of nitrate flow and used for the evaluation of water pollution risks in a watershed [START_REF] Mignolet | Spatial dynamics of agricultural practices on a basin territory: a retrospective study to implement models simulating nitrate flow. The case of the Seine basin[END_REF].

To resume, crop sequences are a pragmatic research object useful to explain land use changes, and we propose to apply our analysis method and the CarottAge software to understand the recent changes and to forecast the future new land uses [START_REF] Fresco | Future of the Land[END_REF][START_REF] Benoît | Farmers, landuse and groundwater quality: an interdisciplinary approach[END_REF]. So, logically, our work will take place in the international project LUCC4 [START_REF] Lambin | Land-use and land-cover change (LUCC): implementation strategy[END_REF].

To go further, we have to enlighten the farmers about the links between their objectives, their practices and the consequences of their practices [START_REF] Gras | Le fait technique en agronomie. Activité agricole, concepts et méthodes d'étude[END_REF]. A possible approach is to test different scenarios for the actors. Two types of scenarios may be developed based on the following argumentation: "What... if...", and "How... to...". Research methods to address these two types of scenarios taking into account the analysis of farmer practices and modeling of decision making are to be developed [START_REF] Affholder | Small scale farming diversity and bioeconomic variability: a modelling approach[END_REF][START_REF] Attonaty | Interactive simulation modelling in farm decision-making[END_REF]. The model-building process itself can serve as a tool to construct and discuss scenarios with the actors [START_REF] Cox | Some issues in the design of agricultural decision support systems[END_REF]. Two main model-building procedures are used: mathematical ones involving methods used in landscape ecology and linear programming, and graphic ones. We shall elaborate on the second procedure, since the first one is well known. For example, one research approach developed by geographers is to define a dictionary of spatial graphic symbols or chorems [START_REF] Brunet | La carte-modèle et les chorèmes[END_REF]. Using this form of qualitative modeling proves most useful in discussions with a wide number of people and enables us to build models of farmer practices in their spatial dimension [START_REF] Deffontaines | Managing rural areas. From pratices to model[END_REF]. A potential further development in this direction is the use of 3D visualization tools to facilitate the understanding of the land use and landscape changes (see [START_REF] Lovett | Landscape modelling and visualisation for environmental planning in intensive agricultural areas[END_REF] for an example).

To end with an ethical posture [START_REF] Jonas | Le principe de responsabilité. Une éthique pour la civilisation technologique "Das Prinzip Verantwortung[END_REF], we propose a new researcher behavior: investigating this type of issue we must not set out from the assumption that a farmer has voluntarily deteriorated the landscape parameter that is being investigated. This corresponds to the development of a decision agriculture [START_REF] Miflin | Sugar beet production: strategies for the future[END_REF] that is increasingly knowledge-based, and increasingly rooted in the information and communication sciences and technologies and to a sustainability trend with a new weight of land capabilities [START_REF] Vereijken | A methodic way to more sustainable farming systems[END_REF][START_REF] Jordan | Factorial Hidden Markov Models[END_REF]. We agree with [START_REF] Boiffin | Cropping systems for the future[END_REF]: "This does not, however, mean a technology-driven process of innovation, but on the contrary increased feedback of action and decision into the design of innovation. . . " mainly on land design management innovation!

Appendix: The Baum-Welch Algorithm

The Baum-Welch (or Forward-Backward) algorithm implements a HMM2's estimation following the maximum likelihood estimation criteria. Since many state sequences may generate a given output sequence, the probability that a model λ generates a sequence O T 1 = o 1 ,...,o T is given by the sum of the joint probabilities (given in equation 2.3, section 2.3.1) over all state sequences (i.e., the marginal density of output sequences). To avoid combinatorial explosion, a recursive computation can be used to evaluate the above sum. The forward probability is defined for all (j, k) ∈ [1, N ] 2 as: α t (j, k) = Prob(q t-1 = s j , q t = s k , O .., o T ) = j α T (j, N ). Another useful quantity is the backward function β t (i, j), defined as the probability of the partial observation sequence from t + 1 to T , given the transition (s i , s j ) between times t -1 and t. It can be expressed for all t ∈ [2, T -1] and for all (i, j) ∈ [1, N ] 2 by: β t (i, j) = Prob(O T t+1 = o t+1 , ..., o T /q t-1 = s i , q t = s j ).

(2.6)

The Markov assumption allows also the recursive computation of the backward probability as:

1. Initialization β T (i, j) = 1 ∀(i, j) ∈ [1, N ] (2.7)

Given an observation sequence o 1 , ..., o T , we define for all t ∈ [2, T -1] and for all (i, j, k) ∈ [1, N ] 3 , the value η t (i, j, k) as the probability of the transition s i -→ s j -→ s k between t -1 and t + 1 during the emission of the observation sequence: η t (i, j, k) = Prob(q t-1 = s i , q t = s j , q t+1 = s k /O T 1 = o 1 , ..., o T ).

(2.8)

We deduce for all t ∈ [2, T -1] and for all (i, j, k) ∈ [1, N ] 3 , η t (i, j, k) = α t (i, j)a ijk b k (o t+1 )β t+1 (j, k) / Prob(O T 1 = o 1 , ..., o T ).

(2.9)

As in the first order, we define Prob(q t-1 = s i , q t = s j /O T 1 = o 1 , ..., o T ) = ξ t (i, j) as the a posteriori probability that the stochastic process accomplishes the transition s i → s j between t -1 and t assuming the whole sequence. We obtain for all t ∈ [2, T -1] and for all (i, j) ∈ [1, N ] 2 : ξ t (i, j) = N k=1 η t (i, j, k).

(2.10)

When the training corpus is a set of sequences, we sum ξ t (i, j) over this set and plot this value as a function of t (i and j are dropped in the Y-axis). This illustrates the behavior of the stochastic process between states s i and s j at time t (see Figure 2.5).

The second-order ML estimate of a ijk is given by the equation:

a ijk = t η t (i, j, k) / k,t
η t (i, j, k).

(2.11)

If N is the number of states and T the sequence length, the Baum-Welch algorithm has a complexity of N 3 × T for a HMM2. Interested readers may refer to [START_REF] Dempster | Maximum-Likelihood From Incomplete Data Via The EM Algorithm[END_REF][START_REF] Mari | Probabilistic and Statistical Methods in Computer Science[END_REF] to find more specific details of the implementation of this algorithm.

Figure 1 . 1 :

 11 Figure 1.1: Description des données Ter-Uti : 3820 mailles quadrillent la France (toutes ne sont pas représentées), 4 photos aériennes sont choisies dans une maille, une grille 6x6 détermine 36 sites

Figure 1 . 2 :

 12 Figure 1.2: Visualisation des 3 pdf de lin3.txt

4 .

 4 visualisation du diagramme de Markov de la figure 2.3 page 25.

Figure 1 . 3 :

 13 Figure 1.3: Le menu : données

Figure 1 . 4 :

 14 Figure 1.4: Le menu : configuration après avoir importé teruti1.cfg

Figure 1 . 5 :

 15 Figure 1.5: Le menu : modèle. Visualisation d'un HMM ergodique à une colonne de 2 états

1. 5 . 6

 56 Le sous-menu : diagramme Ce sous-menu permet la visualisation des diagrammes de Markov (cf. Fig. 1.6) et leurs sauvegardes dans différents formats.

Figure 1 . 6 :

 16 Figure 1.6: Visualisation des transitions entre cultures

Figure 1 . 7 :

 17 Figure 1.7: Visualisation des pdf du modèle ergodique

Figure 2 . 1 :

 21 Figure 2.1: Displaying the results of CarottAge: the user can see the distributions associated to the states (table) and the a posteriori probabilities of transitions between states (diagonal and horizontal lines).

4 Figure 2 . 2 :

 422 Figure 2.2: Model 1: the HMM2 performs a data segmentation in three periods in which the observations are supposed stationary. This model is defined inTable 2.2.

Figure 2 . 4 :

 24 Figure 2.4: Model 2: the states denoted 2, 3 and 4 are associated to a distribution of land-use categories, as opposite to the states denoted with a specific land-use category. The number of columns determines the number of time intervals (periods). A connection without arrow means a two directional connection.

Figure 2 . 5 :

 25 Figure 2.5: Viewing the results of model 2 applied on land-use data of the Lorraine Region (years 1992 -1999).

  the 4 air photos in a mesh

Figure 2 . 6 :

 26 Figure 2.6: Collecting the Ter-Uti data: 3820 meshes square France, 4 air photographs are sampled in a mesh, a 6x6 grid determines 36 sites.

Figure 2 . 7 :

 27 Figure 2.7: Crop transitions between 1992 and 1999 in the district of Saint-Quentinois (North-east of France). Only the transitions whose probability is greater than 1.5% are displayed. The question mark denotes the container state.

Figure 2 . 8 :

 28 Figure 2.8: Transitions between triples of crops, 1992 -1997, in the district of Saint-Quentinois. Only the transitions whose probability is greater than 1.0 are displayed. The question mark denotes the container state.

Figure 2 . 9 :

 29 Figure 2.9: Map of the Seine Basin districts classified wrt their main crop sequences.

2

 2

2 .

 2 Recursion for T -1 ≥ t ≥ 1 β t (i, j) = N k=1 β t+1 (j, k).a ijk .b k (o t+1 ) ∀(i, j) ∈ [1, N ] 2 .

Table 1 .

 1 1: Chaque point est étiqueté par son département (dep) et sa PRA (petite région agricole)

	nLig=112806, annee1=1992, anneen=2003, nAttr=1, indeter=95, isHeader=1
	pt	dep	pra	photo	pti	92	93	94	. . .	00	01	02	03
	1	2	2034	8885	1	27	28	42	. . .	42	27	27	27
	2	2	2034	8885	2	27	33	27	. . .	40	27	27	42
	3	2	2034	8885	3	27	40	52	. . .	27	40	27	33
						. . .

(a) Le principe du maillage de base du territoire

  On trouve CarottAge pour traiter les données Ter-Uti sur le site du Loria 2 sous la forme d'une archive carottage-windows-teruti-V1.zip (Carottage pour windows et données Ter-Uti ). Cette version est paramétrée pour traiter des données Ter-Uti . Plusieurs dossiers sont fournis : SrcQt contient l'exécutable graphique carrotage.exe 3 dans le sous-répertoire SrcQt/debug ; SrcPirenSpatial contient les binaires exécutables compilés correspondant à tous les outils nécessaires pour traiter les données Ter-Uti pour la France entière ;

	1.3 Installation

config contient les fichiers de configuration Ter-Uti . Il s'agit de fichiers donnant la définition de la classification Ter-Uti : blé, orge, . . . ainsi que les regroupements que nous avons opérés comme "bois" et "eau" qui regroupent toutes les superficies en bois et eaux respectivement ; Mod contient les fichiers de l'espace de travail ( description de modèles, modèles initiaux et finaux; ...) ; Corpus contient le fichier de données Ter-Uti short-example.txt. Le fichier de données Ter-Uti NouvelleFrance.txt construit à partir des données Ter-Uti fournies par le Service de la Statistique et de la Prospective (SSP) du Ministère en charge de l'agriculture n'est pas inclus dans ce dossier car il n'est pas en Open Access. Toutefois, pour permettre une démonstration et vérifier la bonne installation du logiciel, ce fichier artificiel est fourni ; DLL est un dossier qui contient les DLL (Dynamic Link Libraries Qt pour Windows Xp ou 7). Pour faire fonctionner CarottAge, il faut modifier la variable PATH dans le menu System de Windows pour ajouter le chemin d'accès à ce dossier. On peut aussi copier les fichiers du répertoire DLL dans le répertoire SrcQt/debug.

  1.4.1 Segmentation de la période d'étudeIl s'agit d'étudier la dynamique de l'assolement de notre région. Une première solution consiste à déterminer autant d'assolements qu'il y a d'années de collecte d'occupation Ter-Uti . Une autre solution consiste à se limiter à un nombre limité de périodes -disons trois pour avoir une vue plus concise de l'évolution -et de laisser les HMM effectuer la meilleure 4 segmentation. Nous utiliserons le fichier short-example.txt pour obtenir des résultats comparables à ceux de la publication[START_REF] Ber | Studying Crop Sequences With CarrotAge, a HMM-Based Data Mining Software[END_REF]. Dans cette fouille de données, on s'intéresse aux observations formées d'une seule occupation du sol. Leurs définitions sont regroupées dans le fichier teruti1.cfg. Si on avait voulu travailler avec des triplets d'occupation, on aurait utilisé teruti3.cfg.

L'archive contient un fichier de commandes Windows do example.bat qui enchaîne les commandes : création de la description du HMM : le fichier lin3.lst est crée par la commande model-lin-gen.exe 3 comme décrit page 22. Ce fichier décrit la topologie du HMM (linéaire à trois états) ainsi que les densités de probabilités (pdf comme probability density function) qui sont ici uniformes ; inventaire des observations : le programme ter2indice-tempo parcourt le fichier short-example.txt afin d'inventorier toutes les observations possibles. L'inventaire est représenté par la liste bin-teruti1.lst ; création du Hmm : le programme editmodel crée le HMM à partir des fichiers lin3.lst et bin-teruti1.lst ; estimation du Hmm : le programme fwtInra joue le rôle de la commande estimate évoquée page 22 ; visualisation : le programme gviewmod construit le fichier lin3.txt qui donne des résultats comparables à ceux de la figure 2.3 page 25.

Table 1 .

 1 2: Description du HMM linéaire à 6 états dont 5 états de Dirac (fichier bocm.lst)

	0 1 1
	1 2 1
	2 3 1
	3 4 1
	4 5 1
	5 6 1
	6 7 1
	7 8 1
	2 2 1
	3 3 1
	4 4 1
	5 5 1
	6 6 1
	7 7 1
	-1 -1 -1
	{ble}
	{orge}
	{colza}
	{mais}
	{prairie +
	bois}
	equiprobable
	rem commandes pour realiser les exemples
	rem de Ecological Modeling "Studying Crop Sequence whith Carottage ..."
	rem Leber, Benoit, Schott, Mari, Mignolet
	rem 2006
	rem cultures simples teruti
	rem fichier teruti1.cfg
	rem executer dans Mod\TerutiLucas
	set CORPUS=../../Corpus/TerutiLucas/short-example.txt
	rem remplacer teruti1.cfg par le fichier de configuration correspondant
	rem creation du Hmm lineaire a 6 etats
	start /W ../../SrcPirenSpatialWindows/ter2indice-tempo.exe -t ../../config/teruti1.cfg %CORPUS% -o bin-teruti1.lst
	start /W ../../SrcPirenSpatialWindows/editmodel.exe -t ../../config/teruti1.cfg -d bocm.lst -i bin-teruti1.lst -o lin-bocm.mod
	rem transformation en ergodique
	start /W ../../SrcPirenSpatialWindows/lin_to_ergo.exe -t ../../config/teruti1.cfg lin-bocm.mod ergo-bocm.mod
	start /W ../../SrcPirenSpatialWindows/fwtInra.exe -t ../../config/teruti1.cfg -n 6 ergo-bocm.mod -o ergo-bocm.mod1 %CORPUS%
	start /W ../../SrcPirenSpatialWindows/gviewmod.exe -t ../../config/teruti1.cfg ergo-bocm.mod1 -o ergo-bocm.txt -m 10
	start /W ../../SrcPirenSpatialWindows/fwtInra.exe -t ../../config/teruti1.cfg -n 1 -x 2 ergo-bocm.mod1 -o ergo-bocm.gph %CORPUS%
	start /W ../../GviewGraph2_Qt\debug\GviewGraph.exe ../../config/teruti1.cfg ergo-bocm.gph 0.01 1991 2003
	Table 1.3: do markov.bat: fichier de commandes pour créer le diagramme
	de Markov de la figure 2.1

Table 2 .

 2 Examples of use of the proposed European cropping/grassland management systems are given in table 2.1. 1: Nomenclature of crops and grassland uses sequences. Each crop name (e.g. M, wW) or grassland-use cluster (e.g. hC -tPH2) represents a year of the sequence.

	For crops:
		M / wW / wB..ic /
	means	Maize / winter Wheat / winter Barley with intermediary
		crops in autumn after harvesting
	For grassland:
		.../ hC -tPH2 /...
	.../ /... means each year the uses are the same
	hC means	mowing for hay making
	tPH2 means	turning Pasture For Heifers 2 years old

  .[START_REF] Baker | Stochastic Modeling for Automatic Speech Understanding[END_REF] shows the topology of a HMM2 that has two kinds of states: Dirac states associated to the most land-use categories (wheat, maize, barley, . . . ) and container states associated to uniform distributions over the set of observations. The estimation process usually empties the container state of the land-use categories associated with Dirac states.

	state 2	state 3	state 4
	pastures 0.31 pastures 0.29 wheat	0.29
	wheat	0.22 wheat	0.26 pastures 0.27
	barley	0.16 rapeseed 0.14 rapeseed 0.17
	rapeseed 0.12 barley	0.11 barley	0.12
	maize	0.07 maize	0.08 maize	0.06
	set-aside 0.05 set-aside 0.05 orchard	0.02
	Figure 2.3: Viewing the results of model 1 applied on land-use data of the
	Lorraine Region (years 1992 -1999).
	?>=< 89:; 2

frequent

  table (districts × probabilities of crop-successions) using the Principal Component Analysis method. The projections of the districts on the fifteenth first eigenvectors were used to design a new table with 15 variables characterizing the districts.4. Clustering of the districts on the basis of this last table, using theHierarchical Ascendant Clustering method. The districts were clustered within twenty classes, which represented a good segmentation according to agronomists' expertise. The map of the Seine Basin, where the districts are colored according to this segmentation, is displayed in figure 2.9.

  t 1 = o 1 , ..., o t ).(2.4)This value represents the probability of starting from the initial state (s 1 ) and ending with the transition (s j , s k ) at time t and generating output o 1 ,...,o t using all possible state sequences in between. The Markov assumption allows the recursive computation of the forward probability for t ∈ [3, T ] as follows:α t (j, k) = (i, j).a ijk .b k (o t ).(2.5)Without any loss of generality, we can suppose that s N is the only final state, then the probability that the model generates the sequenceO T 1 = o 1 , ..., o T is Prob(O T 1 = o 1 , .

	N
	α t-1
	i=1

Direction Régionale de l'agriculture et de la Forêt.

http://www.loria.fr/˜jfmari/App

attention à l'orthographe anglaise

au sens du maximum de vraisemblance

Regional Guidelines to Support Sustainable Land Use by EC-Agri-environmental Programs (EAP), AIR 3 CT94-1296.

http://www.loria.fr/˜jfmari/App/

The number of steps is constrained by the memory of the HMM2 (2).

Land Use and Cover Changes.


domain: spi sdv

text:
Antonio Padilha
email: antonio.plb@lara.unb.br

Lanari Bo

Christine Azevedo Coste

Christian Geny

Philippe Poignet

Charles Fattal

Antônio Padilha

Lanari Bó

Christine Azevedo-Coste

On the Use of Fixed-Intensity Functional Electrical Stimulation for Attenuating Essential Tremor

Keywords: Essential Tremor, Functional Electrical Stimulation, Fixed-intensity stimulation

INTRODUCTION

Tremor, which concerns involuntary, approximately periodic, and roughly sinusoidal movement, is one of the most common movement disorders [Lyons and Pahwa, 2005]. In particular, Essential Tremor (ET) is a monosymptomatic pathology whose patients usually present postural tremor aggravated by voluntary movement, which thus considerably decreases their ability to perform simple daily tasks. Currently, the main available treatments for ET are based on drugs and invasive interventions, such as Deep Brain Stimulation (DBS). While the first lacks effectiveness, since limited positive outcome is obtained for many patients, the second still presents high cost and possibly produces side effects [Grimaldi and Manto, 2008].

In order to enable the development of new therapies, a suitable approach would be to investigate pathological tremor inner dynamics, such as in [Zhang et al., 2009], including the relation between central oscillators and peripheral mechanisms in the origin of ET. However, to our knowledge no results have been obtained using this methodology so far, and hence alternative treatments based on the use of assistive technology have been proposed. One example of such devices is the active upper limb exoskeleton [Rocon et al., 2007], an orthosis that is directly coupled to the joints and actuated in order to counteract tremor. The referred system presented satisfactory performance in preliminary trials; nevertheless its unwieldiness avoids practical use in daily life.

In order to directly actuate on the concerning trembling joints, an option would be to apply Functional Electrical Stimulation (FES). FES is based on the principle of delivering electric pulses to the muscle to produce contraction, either to move the limb or modulate the joint impedance by co-contraction [Popovic and Sinkjaer, 2000]. Comparing to active orthoses, FES systems are potentially lighter and smaller, and there is no need of adjusting the device for different users. However, in spite of its potential for different applications, practical use of FES still presents significant challenges [START_REF] Lynch | [END_REF], particularly when superficial electrodes are used.

From an engineering perspective, such FES systems must contain sensors that detect or estimate the time-varying tremor features. Based on this information, stimulation parameters may be modulated in real-time to reduce tremor, while minimizing interference in voluntary motion. In [START_REF] Bó | [END_REF], we have targeted the problem of tremor estimation in real-time. The current paper concerns the study of adequate FES actuation strategies to attenuate the effects of pathological tremor.

Pioneer studies in the topic [Prochazka et al., 1992] and also more recent studies, such as [START_REF] Maneski | [END_REF] and [Zhang et al., 2011], were based on applying FES to activate antagonist muscles in anti-phase with respect to trembling motion in order to reduce tremor amplitude. Using this strategy, it has been demonstrated experimentally that tremor attenuation using FES is feasible. Moreover, in some cases the positive effect was instantaneous and enduring.

Nevertheless, drawbacks of the method have come to light that still prevent current use in daily life by patients. First, these methods rely on FES-induced motion, which is a great obstacle for daily use due to difficulties concerning electrode placement and because muscle activation from surface electrodes change during forearm motion (i.e., for different forearm orientations, the same electrodes may be stimulating different muscle groups). Also, increase in tremor amplitude may occur due to errors in tremor phase estimation or in controller parameters, which may be aggravated if manual tuning of parameters before each use is required, as in [Prochazka et al., 1992]. Lastly, greater discomfort caused by time-varying stimulation intensity was felt by some patients.

An alternative to anti-phase stimulation is based on the idea of increasing the affected joint impedance using electrical stimulation and, in consequence of that, reducing tremor amplitude. The approach is inspired by strategies often employed by tremor patients in daily life, such as co-activating the muscles to amplify joint impedance and supporting the trembling limb against a fixed object, such as a table, or holding it with the unaffected hand. In terms of musculoskeletal dynamics, increasing joint impedance without producing any residual joint motion is possible when antagonist muscles deliver the same, but opposing torques to the joint. In this condition, joint impedance may be modulated by the muscles activation level due to both intrinsic and proprioceptive contributions to muscle active viscoelasticity [Winters and Crago, 2000].

Preliminary evaluation of this approach indicating good results has already been performed both in simulation [Bó et al., 2009], on healthy subjects [Bó and Poignet, 2010], and tremor patients [START_REF] Gallego | [END_REF]. It is a promising approach, since the applied stimulation might be more comfortable and produce less fatigue, due to the constant lowlevel stimulation applied. Furthermore, the resulting portable device may be simpler, which is an important advantage considering that tremor often propagates from proximal to distal joints. Nonetheless, in the referred works, a closedloop system that modulates the FES level based on the estimated tremor intensity is used. For that reason, time-varying stimulation due to the closed-loop system dynamics is applied, possibly preventing precise understanding and, more important, quantification of which phenomenon produced actual tremor attenuation.

In view of this situation, in this paper we propose a new experimental protocol for evaluating FES tremor attenuation in which fixed-intensity FES is applied on muscles acting on the trembling joint while a static task is performed. By maintaining the maximum number of variables fixed, we expect to attain accurate information on how this complex pathological motion may be compensated. Also, since the ultimate goal is not to completely suppress tremor, but instead to provide the greatest functional benefit, the proposed scheme may present the additional advantage of enabling the subject to easily adapt his/her motion patterns, since FES intensity is constant.

In order to perform a preliminary evaluation of the method, experiments with 10 ET patients were conducted. The trials featured an initial tremor characterization, where the stimulated muscles were chosen, and subsequent static tests using an open-loop FES system. Since the protocol was based on single-session experiments, patients could not provide an evaluation of functional benefit obtained in daily use. However, tremor amplitude attenuation could be quantified based on the obtained data and the feasibility of the approach was demonstrated. Furthermore, the obtained data illustrated heterogeneous phenomena, hence in this paper we are also focused on discussing their possible causes and potential advantages comparing to alternative methods.

MATERIALS AND METHOD

Participants -A group of 10 ET patients participated in the study. In Tab. 1, information concerning the participants is listed. The subjects were selected randomly from patients at the Centre Hospitalier Universitaire de Montpellier and they presented heterogeneous tremor features, both in terms of age of tremor onset and severity according to the Fahn-Tolosa-Marin tremor rating scale. None of the patients had experienced surface electrical stimulation beforehand. The study was conducted in accordance with the Declaration of Helsinki and all participants have signed informed consent, which was approved by the local ethical committee.

Design -The study was based in a within-subject design, which was designed to evaluate the feasibility of the proposed method. The experiments were limited to a single session, where participants were given a static motor task to perform. The relative tremor amplitude was measured during alternating periods when fixed-intensity FES applied to the wrist or fingers was turned on and off. Materials -The experimental setup consisted of a commercial stimulator, the Cefar Physio 4 (Cefar, Sweden), and motion sensing units composed of 3-axis accelerometer (MMA7260Q, Freescale, USA) and 2-axis gyrometer (IDG300, Invensense, United States) sampled at 100 Hz. The sensor box was placed using a fastening tape either on the fingers or on the hand, depending on the trembling joint. Within our setup, x axis was pointing distally, y axis medially, and z axis anteriorly. Self-adhesive round 3.2 cm electrodes were used in the experiment. For smaller muscles in the forearm, the electrodes were downsized to provide better selectivity. Since the stimulation intensity was set manually, we have also used electromyography (Biovision, Germany) coupled with the inertial sensors acquisition system. Based on the corresponding stimulation artifact, we could guarantee precise synchronization between FES and motion signals recorded using inertial sensors.

Procedure -Within the designed experimental protocol, firstly the pathological motion was analyzed using inertial sensors in order to designate the appropriate target joint(s) for stimulation (wrist, fingers, or thumb/index), as well as the concerned muscles. The joint presenting higher tremor amplitude, considering that tremor propagates from proximal to distal joints, was selected. Once these definitions were made, FES parameters were set for each muscle individually while the participants were performing a static motor task: to point to a target with the hand, maintaining the arm in full extension. Furthermore, the limb was not constrained in any possible degree of freedom (DOF). FES pulse width was fixed at 150 µs, and frequency at 40 Hz, while stimulation level was regulated manually using pulse amplitude (mA)

based on visual and tactile inspection of muscle contraction, but respecting patient subjective evaluation of discomfort.

The main goal for setting the stimulation parameters was to produce consistent isometric contraction, while avoiding reaching the motion threshold. Since multiple muscles may affect joint motion, within the initial setup different candidate muscles were stimulated, and the muscle(s) that presented most effective response based on visual inspection was selected for evaluation.

Following the initial setup, evaluation was based on the application of constant stimulation levels intermittently.

Stimulation duration was incremented progressively from approximately 10 up to 50 s to enable evaluation of different effects that may affect tremor attenuation. Periods in which FES was turned off lasted for at least 10 s, while longer intervals were employed when subjects were not able to reestablish static hand position immediately after stimulation. A sequence ranging from 5 to 7 stimulation periods were applied during each session. Before the stimulation trials started, the patients initiated the static task and remained in this position for at least 10 s in order to minimize transient effects.

If requested by the subject, resting periods were allowed between stimulation periods to limit overall muscle fatigue.

Furthermore, it was not possible in any stimulation trial to start stimulation directly at the assigned intensity. Instead, due to the limitations of the employed stimulator, current amplitude was increased until the target level was achieved, in a procedure that took approximately 5 s to complete. During the whole session, upper limb motion was measured using accelerometers and gyrometers.

Afterward, the resultant recorded motion was analyzed to enable comparison of tremor amplitude with and without FES and identify other emerged effects. The data used in the analysis were preprocessed (high-pass 10th-order Butterworth filter, cutoff frequency at 1 Hz) to remove low frequency components. Considering the tasks performed are static, the filtering was applied mainly to remove sensor bias from the signal.

RESULTS

The results obtained in the study are summarized in Tab. 2 and Figs. 1 and2. In addition to data related to tremor attenuation experiments, Tab. 2 also includes information concerning the target joint and the stimulated muscles, as well as a classification of the overall response to FES therapy in 3 classes: no positive effect, attenuation preceded by an adaptation phase and clear immediate attenuation. Tremor amplitude was computed using the Root Mean Square (RMS) value of the referred motion signal, while tremor attenuation is defined by the ratio

!"" -!" !"" (1)
where on and off concerns all periods in which stimulation was on and off, respectively. The results concerning the overall response to FES were obtained directly by analyzing the acquired motion signals, particularly the transient response when FES was turned on and off.

Concerning Tab. 2, the results illustrate the overall success of the method, particularly since in only 1 out of 10 patients the trials resulted in increasing tremor amplitude and in 1 out of 9 patients tremor attenuation was lower than 37%. b Most significant tremor attenuation concerns reduction in tremor amplitude on the sensor axis presenting higher tremor intensity before stimulation. For patient A, the minus sign indicates that the performance was worse when FES was on. The general performance of the method for all patients is also illustrated in Fig. 1. Data from all sensors and the corresponding mean tremor amplitude (represented by its RMS value) for the period in which FES was on and off is

shown. Since the fixed-level stimulation may displace the joint and affect the resulting plane of motion of tremor, evaluating all measured axes is important to verify if tremor has shifted to a different plane, which would thus prevent an effective functional benefit to the user.

Finally, in order to illustrate motion response with respect to time, pieces of data that contain representative effects to substantiate the Discussion are depicted in Fig. 2. The figure illustrates one case where clear immediate tremor attenuation was observed, as well as others where an adaptation phase was required and an extra instability emerged when the FES system was turned off. For each motion, the sensor presenting highest RMS value was chosen (accelerometer for Fig. 2(a) and gyrometer for Fig. 2(b) and 2(c)).

DISCUSSION

Based on the illustrated results, it may be concluded that tremor attenuation based on fixed-intensity FES is feasible, In (c), the sudden instability that occurs once the support from FES vanishes is illustrated. In all cases, the initial period when FES intensity is gradually increased is also depicted.

since in only 2 patients in a population of 10 a poor or limited performance was observed. In this section we present a qualitative discussion concerning the major related issues.

Clear immediate tremor attenuation was detected on patients presenting different tremor features (in terms of affected joint and tremor severity given by the Fahn-Tolosa-Marin tremor rating scale) and types of stimulation strategy Concerning the circumstances where attenuation was preceded by an adaptation phase (e.g., Fig. 2(b)), we believe that the performance was greatly influenced by involuntary reactions to the FES-induced contraction. Since none of the patients had any previous experience with FES, the effect is unsurprising. For this reason, we believe patients that presented an adaptation phase before tremor attenuation may greatly benefit from adequate training. It may be observed within the referred figure, for instance, that there was no adaptation phase in the second stimulation period. Indeed, the adoption of stimulation trials featuring different intervals has enabled observation of higher tremor attenuation for longer trials in some patients. Other observed negative effects may be potentially reduced with such previous practice, such as the sudden instability generated once the support from FES is removed (e.g., Fig. 2

(c)).

There were also 2 cases where no positive effect was observed during the experimental sessions, either due to tremor increase or no significant improvement. Considering that in just a few patients it was impossible to verify reduction in tremor amplitude using the proposed strategy, we believe that the lack of success in these sessions was caused by the limitations of the experimental protocol. For the other patients to whom the method has provided positive response, but considerable irregularity (as subjective judgment by the patient), it may also be the case that these experimental difficulties have affected the overall performance of the method.

Among the most significant weakness within the experimental protocol, one important difficulty was related to electrode placement in elderly patients, particularly when multiple muscles are stimulated (since stimulation diffusion increases considerably). Indeed, for most patients it is hard to imagine real-life applications without improved electrode technology, such as implantable or multi-pad electrodes, such as [Popovic-Bijelic et al., 2005].

Another significant issue is related to tremor inherent variability. Since the study was based on a within-subject experiment design where FES was the controlled variable, ideally all other aspects that affect the response should be kept constant. Indeed, intrinsic fluctuations of ET amplitude may greatly affect the computed tremor reduction.

Employing static tasks reduced the variability in tremor amplitude, but in some case fluctuations remained intense due to subject-specific features, such as voluntary contractions. A longer protocol involving multiple sessions would enable the patient to get used to FES, which was not possible in our study, since it was based on single sessions with each patient.

In view of those experimental limitations, our future work focuses on trials on patients based on multiple experimental sessions including improvements on the choice of muscle(s) to stimulate, as well as proper evaluation of the functional benefit provided by the method. A longer protocol, including an initial training period, may demonstrate if the negative effects observed in some patients may be suppressed. Finally, based on recorded motion and patient evaluation of fatigue and sensitivity, the following goal is to compare different compensation strategies in controlled scenarios.

Nevertheless, the proposed method has indeed demonstrated the feasibility of reducing tremor amplitude by applying fixed-level FES to the muscles acting on the concerned joint. Comparing with alternative systems, such as the anti-phase approach, the proposed method may indeed present some advantages. Firstly, the applied stimulation may be more comfortable and predictable, possibly increasing the acceptance ratio among potential users. The resulting device may also be more compact and simpler, requiring less sophisticated and cheaper hardware. Considering that tremor often propagates from proximal to distal joints, this may also be an important feature. Indeed, in anti-phase FES tremor compensation, unstable performance on proximal joints may increase tremor at the hand, while in the proposed method the effect of stimulation is intrinsically stabilizing. Furthermore, the results have also shown that tremor was not shifted to another plane of motion, which would indicate that the pathological motion was not actually compensated and consequently a great disadvantage of the method. Finally, an additional important result concerns the fact that not always clear immediate tremor reduction occurs. Indeed, due to the observed phenomena of adaptation periods to previous to tremor attenuation and sudden instability after stimulation, we infer that tremor compensation strategies based on FES should mandatorily include a training phase when the patient will be able to learn the motor patterns to use during stimulation.

Figure 1 :

 1 Figure 1: Tremor amplitude (RMS value) for all participating subjects measured at each sensor. a refers to accelerometer and g to gyrometer. RMS values are shown in m/s 2 and rad/s, respectively. The axes limits are not the same for all patients, reflecting the different levels of tremor severity.

Figure 2 :

 2 Figure 2: Motion signals from illustrative trials. In (a), clear immediate attenuation may be observed. The adaptation phase required to achieve better performance is depicted in (b).In (c), the sudden instability that occurs once the support from FES vanishes is illustrated. In all cases, the initial period when FES intensity is gradually increased is also depicted.

(

  single muscle or pair of antagonist muscles). This may indicate that separate phenomena are involved in the reduction of tremor amplitude, such as FES-induced co-contraction to increase joint impedance, reduction in tremor activity due to recruitment of muscle fibers presenting tremor activity or tremor attenuation due to unknown effects related to the stimulation of afferent pathways. Even though all these distinct hypotheses are plausible, based on the obtained data it is unrealistic to develop further conclusions due to the limited knowledge on ET muscle dynamics and the diversity between FES-induced muscle responses observed on different patients.

Table 1 :

 1 Descriptive data of all patients that participated in the study.

					Postural tremor at the
	Pat.	Gender	Age	Age at onset	dominant arm (Fahn-Tolosa-Marin tremor
					rating scale a )
	A	M	54	10	2
	B	F	78	15	3
	C	M	71	56	2
	D	M	57	6	3
	E	M	77	10	2
	F	M	75	73	3
	G	M	76	32	4
	H	M	71	1	2
	I	M	79	20	4
	J	F	65	60	2

a More severe tremors are represented by higher values of the Fahn-Tolosa-Marin tremor scale.

Table 2 :

 2 Data resulting from the experiments.

	Pat.	Target joint	Stimulated muscle(s) a	Most significant tremor attenuation [%] b	Overall response
	A B	Fingers Wrist	FDS FCU, ECU	-65.49 12.53	No positive effect
	C	Fingers	EDC, FDS, PT	94.68	Attenuation preceded
	D	Fingers	FCR	78.20	by an adaptation
	E	Thumb/index	AP, APB	72.07	phase
	F	Wrist	ECU, FCU	85.69
	G H	Wrist Wrist	PT EDC	41.73 37.18	Clear immediate attenuation
	I	Fingers	EDC	47.28
	J	Thumb/index	AP, APB	78.19

a FDS stands for flexor digitorum superficialis, FCU for flexor carpi ulnaris, ECU for extensor carpi ulnaris, EDC for extensor digitorum communis, PT for pronator teres, FCR for flexor carpi radialis, AP for adductor pollicis, APB for abductor pollicis brevis.

ACKNOWLEDGEMENTS

Neuromedics and the Agence Nationale de la Recherce, in the context of the TREMOR Project, supported this work.