Anne Gégout-Petit

Shuxian Li

Two-step centered spatio-temporal auto-logistic regression model

Keywords: Spatio-temporal modelling, autologistic model, Markov random field, largescale, small-scale model structure, binary response

In our study, we focus on spatio-temporal causal auto-logistic model and proposed a two-step-centered parametrization version of it. We study the existence of the joint law according to the conditional marginals. The simulation study show that the one-step model can not reflect the temporal data structure when both spatial and temporal dependance are strong, while for the two-step model, there is an adequate agreement between the data structure and the temporal large-scale structure. The results of estimation for simulated lattices over years were performed by expectation-maximization (EM) pseudo-likelihood in two stages. They show that under the two-step centered parametrization, the inference for parameters of both temporal and spatial regressions are accurate, while under one-step centered parametrization their inference are always conflicting.

Introduction

Since spatial and spatio-temporal binary data are commonly existing in nature, the models on such data had drawn large interests of scientists from various fields such as ecology, epidemiology and image analysis, during past years. 40 years ago, Besag [START_REF] Besag | Spatial interaction and the statistical analysis of lattice systems[END_REF] firstly proposed an auto-logistic model for spatial binary data, assuming a simple dependence on surrounding neighbors. This model was proved to be very useful and then was extended in order to integrate the regression on the covariates [START_REF] Gumpertz | Autologistic model of spatial pattern of phytophthora epidemic in bell pepper: effects of soil variables on disease presence[END_REF][START_REF] Huffer | Markov chain monte carlo for autologistic regression models with application to the distribution of plant species[END_REF] and temporal dependance as in [START_REF] Zhu | Modeling spatial-temporal binary data using markov random fields[END_REF].

However, the non-centered parametrization of the auto-logistic regression models present parameter interpretation difficulties across varying levels of statistical dependence. This problem has been first pointed out by Caragea [START_REF] Caragea | Autologistic models with interpretable parameters[END_REF] who proposed a centered parametrization for spatial auto-logistic regression model to overcome this difficulty. Wang [START_REF] Wang | Analysis of binary data via a centered spatial-temporal autologistic regression model[END_REF] developed a centered spatiotemporal auto-logistic regression model but (probably due to constrain about existence of the joint law) this model depends both on the past and future and is not well adapted to real world problems modelling.

In this paper, we propose a two-step centered auto-logistic causal model and will show its advantage over the existing centered parametrization for the auto-logistic models only depending on the past. We tackle the existence of the joint distribution but present the expectationmaximization pseudo-likelihood estimation in two steps. The paper is organized as follows: first of all, after a brief introduction about auto-logistic models and the interest to center them in some cases, we will present the two-step centered auto-logistic model. Then we show several simulations to compare the spatio-temporal auto-logistic model depending on past under onestep and two-step centered parametrization. Afterward we present the results of estimation via maximization of the pseudo-likelihood.

Centered autologistic models

We are interested by a set of variables Z = {Z i : i = 1, ..., n} indexed by a lattice with n points denoted by S = {1, . . . , n}. A spatial auto-model for Z is given by the n marginal conditional laws of the Z i 's given the other variables {Z j , j = i]}. If Z i is binary, we speak about auto-logistic model and we have to model the p i = P(Z i = 1|Z j , j = i) for 1 ≤ i ≤ n. Hammesley-Clifford theorem (see for instance [START_REF] Besag | Spatial interaction and the statistical analysis of lattice systems[END_REF] or [START_REF] Gaetan | Modélisation et statistique spatiales[END_REF]) makes the link between auto-model and Markov Random Field and gives some conditions for the existence of the joint law. If probability p i does not depend on the whole set of variables {Z j , j = i]} but only on the neighborhood of i denoted by N i , we have p i = P(Z i = 1|Z j , j ∈ N i ) and the N i 's are link to the structure of cliques of the Markov Random Field.

In 1997, Gumpertz followed by many other papers, introduce covariates in the model leading to

p i = exp(X T i β + j∈N i β ij Z j ) 1 + exp(X T i β + j∈N i β ij Z j ) ⇔ logit(p i ) = X T i β largescale + j∈N i β ij Z j smallscale
where large-scale component is the overall level of a process given also by covariates and the small-scale component take into account high-order parts of the data structure like variances or covariances. Owever, Caragea [START_REF] Caragea | Autologistic models with interpretable parameters[END_REF] made the remark that if we put

c i = exp(X T i β) 1 + exp(X T i β) (independent case), then log[ p i /(1-p i ) c i /(1-c i ) ] = j∈N i β ij Z j ,
and odds of Z i = 1 relative to the independence model increases for any nonzero neighbors, and can never decrease. It is not reasonable if most of neighbors are zeros and could bias the realizations towards 1. For this reason, they proposed the centered model [START_REF] Bee | Approximate maximum likelihood estimation of the autologistic model[END_REF] in 2009 that allows the p i 's to increase or decrease around the mean behavior (large scale) of the model.

logit(p i ) = X T i β + ρ j∈N i (Z j - exp(X T j β) 1 + exp(X T j β) ) (1)
We study now the opportunity to propose an autologistic spatio-temporal model that is centered in two steps, the first one according to the current covariates and the second one according to the regression on the past. It is given by the marginal conditional laws [Z i,t |Z j,t ; j = i, Z t-1 , X t ] = [Z i,t |Z j,t : j ∈ N i , Z i,t-1 , X t ] and where the status at point i is influenced by the past at point i and the the current neighborhood status of N i . More precisely:

logit(p i,t ) = X T i,t β reg covariates + ρ 2 Z i,t-1 reg past + ρ 1 j∈N i Z j,t - exp(X T j,t β + ρ 2 Z ij,t-1 ) 1 + exp(X T i,t β + ρ 2 Z j,t-1 ) auto-reg centered (2)
To prove the existence of the joint law of the Z i,t , we have to consider the process as a Markov chain of Markov field. Framework of Guyon-Hardouin [START_REF] Guyon | Markov chain markov field dynamics: models and statistics[END_REF] is useful for this and allows us to express the transition probabilities from value y to value z according to the covariates at time t. They are given by

P(y, z | F X t ) = C(y, F X t ) exp( i∈S z i X T i,t β + ρ 1 1 j∈N i z i z j instantaneous + i∈S z i (ρ 2 y i -ρ 1 j∈N i exp(X T j,t β + ρ 2 y j ) 1 + exp(X T j,t β + ρ 2 y j ) past ))
3 Simulation and inference

We will use Perfect sampling preceded by a Gibbs sampling step for the burn-in to simulate data and compare the large scale structure measured by the mean overall the points of the lattice in model ( 2) and the following one-step model

logit(p i,t ) = X T i,t β + ρ 2 Z i,t-1 + ρ 1 j∈N i Z j,t - exp(X T j,t β) 1 + exp(X T i,t β) (3)
Simulation were performed on a 20 × 20 lattice and we find that this centering is fairly accurate to capture the small-scale effect. For inference, because of the intractable constant in joint distribution, we deal with the pseudo-likelihood and a Expectation Maximisation algorithm to infer the parameters. We give in Tables 1 and2 the result of inference and see that the two-step centered model is more suitable for estimation.

β 1 β 2 ρ 1 ρ 2 mean -

Discussion

In this chapter, we developed a two-step centered spatio-temporal auto-logistic regression model to fit the binary spatio-temporal data over a lattice with exogenous covariates. The marginal data structure of the model under such centered parametrization can better reflect the largescale structure, and in this way, the correct interpretation of the parameters is ensured. The objective of the work is to use it for the analysis of epidemiological data about esca disease for vines. But lattice in this context are very large (around 2000 vines over 12 years).We have to develop more adapted methods of inference. Here we benefited the easy calculation of pseudo-likelihood function to obtain a numerical estimation of the model which is statistically imperfect. In perspective, several methods based on approximation likelihood could be tried to estimate our models. Recently, Bee [START_REF] Bee | Approximate maximum likelihood estimation of the autologistic model[END_REF] proposed a AMLE (Approximate Maximize Likelihood Estimation) which is very interesting for our case. The advantage of AMLE method is since the only requirement of approximating maximum likelihood estimates is the ability to simulate the model to be estimated. It does not need to evaluate the likelihood function, only sufficient statistics but no joint distribution need to be clarified. When the inference of this model will be improved and adapted to large data set, we will apply the model to esca data in order to test the dependence on neighbors and the effects of environmental covariates.

Bibliographie

Table 1 :

 1 One-step centered model simulation estimated by PL, (true values in the brackets).

		1.7917(-1.5) 0.2322(0.5) 0.1941(0.8) 0.8400(0.8)
	variance 0.0221	0.0013	0.0421	0.0159
		β 1	β 2	ρ 1	ρ 2
	mean	-1.4835(-1.5) 0.5167(0.5) 0.7858(0.8) 0.7994(0.8)
	variance 0.0117	0.0057	0.0061	0.0084

Table 2 :

 2 two-step centered model simulation estimated by PL, (true values in the brackets).


Elias Egho

Dominique Gay

Marc Boullé

Nicolas Voisine

Fabrice Clérot

A parameter-free approach for mining robust sequential classification rules

Sequential data is generated in many domains of science and technology. Although many studies have been carried out for sequence classification in the past decade, the problem is still a challenge; particularly for pattern-based methods. We identify two important issues related to pattern-based sequence classification which motivate the present work: the curse of parameter tuning and the instability of common interestingness measures. To alleviate these issues, we suggest a new approach and framework for mining sequential rule patterns for classification purpose. We introduce a space of rule pattern models and a prior distribution defined on this model space. From this model space, we define a Bayesian criterion for evaluating the interest of sequential patterns. We also develop a parameter-free algorithm to efficiently mine sequential patterns from the model space. Extensive experiments show that (i) the new criterion identifies interesting and robust patterns, (ii) the direct use of the mined rules as new features in a classification process demonstrates higher inductive performance than the state-of-the-art sequential pattern based classifiers.

I. INTRODUCTION

Sequence classification [START_REF] Xing | A brief survey on sequence classification[END_REF] has many real-world applications in a broad range of domains, such as biology [START_REF] Deshpande | Evaluation of techniques for classifying biological sequences[END_REF], [START_REF] She | Frequent-subsequence-based prediction of outer membrane proteins[END_REF], text mining [START_REF] Sebastiani | Machine learning in automated text categorization[END_REF] or web mining [START_REF] Tan | Discovery of web robot sessions based on their navigational patterns[END_REF]. Mining sequential rules for classification has become very popular since the resulting classifier might be interpretable by the domain analyst. A sequential rule is an expression that takes the form of π : s → c i where s is the body sequence of the rule and c i is a value of a class attribute. One can interpret π as "when event sequence s is observed for an object, then it is often an object of class c i ". An incoming unseen object, that matches a discovered rule pattern, will be more likely of the class indicated by the rule. Adopting the strategy of the pioneering work for transactional data on "Classification Based on Associations" (CBA) [START_REF] Liu | Integrating classification and association rule mining[END_REF], several rule-based approaches have been suggested for sequence classification. Generally, pattern-based classification methods [START_REF] Zimmermann | Supervised pattern mining and applications to classification[END_REF] follow a similar strategy: firstly, a sequential rule set is mined w.r.t. an interestingness measure; secondly, either a dedicated classifier, like a decision list or a Maximum Entropy model, is built upon a selected subset of the mined rules [START_REF] Tseng | CBS: A new classification method by using sequential patterns[END_REF], [START_REF] Zhou | Itemset based sequence classification[END_REF], [START_REF] Holat | Sequence classification based on delta-free sequential patterns[END_REF] or the mined rules are directly used as new features in a classification process [START_REF] Lesh | Mining features for sequence classification[END_REF], [START_REF] Deng | An occurrence based approach to mine emerging sequences[END_REF], [START_REF] Lam | Mining compressing sequential patterns[END_REF]. While most of the existing approaches generally lead to good inductive performance, we now highlight two of their weaknesses, namely the curse of parameter tuning and the instability of the interestingness measures.

The curse of parameter tuning. Most of the existing approaches need parameter tuning. One has to set an interestingness measure threshold (sometimes also with a frequency threshold and a gap constraint) for the mining phase, then choose the number of rules for the final set used for classification. Unfortunately, setting parameters is not an easy task -each application data could require a specific setting. The associated dilemma is well-known: for large data sets, low frequency thresholds lead to an untractable task or a huge number of output patterns many of which are spurious; while high frequency thresholds produce too few patterns with low class-discrimination power. Moreover, the predictive performance of rule-based classifiers highly depends on these settings [START_REF] Coenen | The effect of threshold values on association rule based classification accuracy[END_REF].

The instability of interestingness measures. We justify this claim by considering a motivation example, let us consider three widely used measures for evaluating sequential rules: confidence, growth rate and lift. One can easily show that rule patterns extracted according to these measures are not individually robust. In figure 1, we plot test values of confidence (resp. growth rate) against train values of each mined rule pattern (one point per pattern) for the skater data set [START_REF] Mörchen | Efficient mining of understandable patterns from multivariate interval time series[END_REF]. We observe very blurred scatter plots, meaning that interestingness measures values are severely unstable from train to test data: a "good" rule w.r.t. an interestingness measure in training phase may turn out to be weak in test phase. Particularly, the top-1000 rules obtained from training data according to each considered measure are clearly not anymore the top-1000 when evaluated on test data. Thus, it could be misleading to bet on such rules for classifying new incoming objects. These two weaknesses suggest that there is room for improving inductive performance and ergonomy of patternbased sequence classification methods. The main contributions of this work tackle these two problems and are summarized as follows:

Towards a robust criterion for evaluating sequential classification rules. We embrace the Bayes theory and suggest a Bayesian criterion, called level, for identifying interesting and robust sequential classification rules. Our suggested framework has been already successfully instantiated for several data mining tasks such as supervised discretization [START_REF] Boullé | MODL: A bayes optimal discretization method for continuous attributes[END_REF] and classification rule mining in transactional data sets [START_REF] Gay | A bayesian approach for classification rule mining in quantitative databases[END_REF]. The level criterion is based on the a posteriori probability of a rule model given the data and does not require any wise threshold setting.

A parameter-free approach for mining sequential classification rules. We discuss and present a new algorithm MiSeRe for Mining Sequential Classification Rules. The main features of MiSeRe are: (i) it is user parameter-free, (ii) it employs an instance-based randomized strategy that promotes diversity mining, (iii) it uses a bitset representation and the Boolean operations, to efficiently mine the sequential classification rules and (iiii) it is anytime -the more time the user grants to the task, the more it learns.

To validate our contributions, we perform an extensive experimental evaluation on a variety of datasets, including biological sequences, web usage logs and text sequences. The main results are unequivocal: (i) the suggested Bayesian criterion identifies interesting and robust sequential patterns; (ii) using the extracted sequential rules as new features in a classification process outperforms state-of-the-art sequential rule-based classifiers in terms of predictive performance.

II. PRELIMINARIES

Let I = {e 1 , e 2 , • • • , e m } be a finite set of m distinct items. A sequence s over I is an ordered list s = s 1 , • • • , s s , where

s i ∈ I; (1 ≤ i ≤ s , s ∈ N). A sequence s = s 1 • • • s s is a subsequence of s = s 1 . . . s s , denoted by s s, if there exist indices 1 ≤ i 1 < i 2 < • • • < i s ≤ s such that s z = s iz
for all z = 1 . . . s and s ≤ s . s is said to be a supersequence of s . T(I) will denote the (infinite) set of all possible sequences over I. Let C = {c 1 , • • • , c j } be a finite set of j distinct classes. A labeled sequential data set D over I is a finite set of triples (sid, s, c) with sid is a sequence identifier, s is a sequence (s ∈ T(I)) and c is a class value (c ∈ C). The set D ci ⊆ D contains all sequences that have the same class label c i (i.e., D = ∪ j i=1 D ci ). The following notations will be used in the rest of the paper: Definition 1: (Support of a sequence) Let D be a labeled sequential data set and let s be a sequence. The support of s in D, denoted f (s), is defined as:

f (s) = |{(sid , s , c ) ∈ D|s s }| sid sequence class 1 abadc c1 2 acbe c1 3 badcb c2 4 eef cbc c2 TABLE I. D: A TINY LABELED SEQUENTIAL DATA SET AS AN EXAMPLE.
The value of n -f (s) can be written as f (s). The support of s in D c is noted f c (s) and f c (s) stands for n c -f c (s).

Definition 2 (Standard Classification Rule Model): Let D be a labeled sequential data set with j classes. A sequential classification rule π is an expression of the form:

π : s → f c1 (s), f c2 (s), • • • , f cj (s)
where s is a sequence, called body of the rule, and

f ci (s) is the support of s in each D ci , i = 1 • • • j.
This definition of classification rule is slightly different from the usual definition where the consequent is a class value. It refers to the notion of distribution rule [START_REF] Jorge | Distribution rules with numeric attributes of interest[END_REF] and allows us to access the whole frequency information within the contingency table of a rule π -which is needed for the development of our framework.

Example 1: We use the sequence database D in Table I as an example. It contains four data sequences (i.e., n = 4) over the set of items I = {a, b, c, d, e, f } (i.e., m = 6). C = {c 1 , c 2 } is the set of classes, j equals to 2. The longest sequence of D is s = eef cbc (i.e., s = max ), max equals to 6 while k s equals to 4. Sequence aad is a subsequence of abadc . Given a sequence s = ab , we have

f (s) = 3, f (s) = 1, f c1 (s) = 2, f c1 (s) = 0, f c2 (s) = 1 and f c2 (s) = 1. π : ab → f c1 ( ab ) = 2, f c2 ( ab ) = 1 is a sequential classification rule.

III. BAYESIAN FRAMEWORK FOR SEQUENTIAL PATTERN

Standard classification rule evaluation criterions aim at selecting general rules (e.g., based on the frequency constraint) and informative rules that characterize classes (e.g., based on confidence or growth rate). However the trade-off between generality and informativeness is difficult to achieve and usually rely on manual parameter tuning. Using a Bayesian approach, we aim at obtaining a statistical evaluation criterion with the expectation of automatically and optimally finding the best trade-off between generality and informativeness.

Following the framework introduced by [START_REF] Boullé | MODL: A bayes optimal discretization method for continuous attributes[END_REF], from a Bayesian point of view, the problem of sequential classification pattern mining is formulated as a model selection problem. To choose the "best" sequential rule model from the model space, we use a Bayesian Maximum A Posteriori approach: we look for maximizing p(π|D), the posterior probability of a rule model π given the data D. According to Bayes rule p(π|D) is given as :

p(π|D) = p(π, D) p(D) = p(π) × p(D|π) p(D)
Considering that p(D) is constant in the current optimization problem, it goes back to the maximization of the expression p(π) × p(D|π). The evaluation criterion, called cost, is based on the negative logarithm of p(π|D) and is expressed as follows:

cost(π) = -log(p(π) prior × p(D | π) likelihood ) ∝ -log(p(π | D) posterior )
Now to choose the best rule for data D, we have to minimize the cost of a sequential classification rule.

To compute the prior p(π), we complement Definition 2 of sequential classification rules with a hierarchy of parameters that uniquely identifies a given rule in the rule model space:

Definition 3: (Standard Classification Rule Model) A se- quential classification rule or (SCRM) π : s → f c1 (s), f c2 (s), • • • , f cj (s) is defined by:
• the constituent items of the rule body s.

• the order of occurrence the items in the body s.

• the class distribution inside and outside of the body s.

Our working model space is then the space all SCRMs. Considering the hierarchy of parameters from the definition of SCRM, we use the following hierarchical prior distribution on SCRM models:

1) the number of distinct items ks in a rule body s is uniformly distributed between 0 and m.

2)

the length of the sequence s in a rule body is uniformly distributed between 0 and max.

3)

for a given number ks of items, every subset of ks distinct items of the m items is equiprobable.

4)

for a given number of distinct items ks and for a given number of items in sequence s, every ordered set of s items of the ks distinct items is equiprobable. 5) every distribution of the class values is equiprobable, in and outside of the body.

6)

the distributions of class values in and outside of the body are independent.

Notice that such a prior is uniform at each stage of the hierarchy; it does not mean that the hierarchical prior is a uniform prior over the rule space, which would be equivalent to a maximum likelihood approach. From the definition of the model space and its prior distribution, we can now give an expression of the prior probability (p(π)) of a rule model and the probability (p(D | π)) of the data given a model π, i.e. the likelihood of π.

Prior probability. The prior probability of a rule model π is:

p(π) = p(s) × p(f (s)) × p({f ci (s)} j i=1 {f ci (s)} j i=1 |f (s), f (s))
Expanding each term of the prior turns into an enumeration problem. The first two hypotheses assume uniform distribution, which lead to m + 1 and max + 1 enumeration terms. The third hypothesis assume the equiprobability of every set of k s constituent distinct items of the sequence body. The number of combinations m ks is a natural candidate to compute this prior term, however it is symmetric. Adding new items (beyond m/2) to the body makes the rule more probable, which is an undesired effect. Indeed, adding spurious items is favored even if it has an insignificant impact on the likelihood of the model. To obtain simpler models, we prefer a parsimonious prior that increases with k s : considering a multinomial distribution with q independent trials and m equiprobable outcomes, the likelihood of a draw with counts (q 1 , . . . , q m ) such that m i=1 q i = q is q! q1!...qm! i ( 1 m ) qi . If we keep only the draws for which all items are distinct, we obtain q! m q . The fourth hypothesis promotes the equiprobability of every ordered set of s items over k s distinct items; here we use the exponential term k s s . We now have p(s):

p(s) = 1 m + 1 × 1 max + 1 × k s ! m ks × 1 k s s (1)
Considering the last two hypotheses, enumerating the distributions of the j classes in and outside of the body is a combinatorial problem:

p({f ci (s)} j i=1 |f (s), f (s)) = 1 f (s)+j-1 j-1 (2)
p({f ci (s)} j i=1 |f (s), f (s)) = 1 f (s)+j-1 j-1 (3)
Likelihood The probability of the data given the rule model p(D|π) is the probability of observing the data inside and outside of the rule body (w.r.t. f (s) and f (s)) given the multinomial distribution:

p(D|π) = 1 f (s)! j i=1 fc i (s)! × 1 f (s)! j i=1 fc i (s)! (4)
The complete and exact definition of the cost of SCRM is then:

cost(π) = log(m + 1) + log( max + 1) +log( m ks k s ! ) + log(k s s ) +log f (s) + j -1 j -1 + log f (s) + j -1 j -1 +log(f (s)!) - j i=1 log(f ci (s)!) +log(f (s)!) - j i=1 log(f ci (s)!)
The amplitude of the cost values depends on the number n of sequences and the number m of items in the data set. For convenience, we defined a normalized criterion, called level, which plays the role of an interestingness measure to evaluate and compare SCRMs.

Definition 4 (Level): Given a SCRM π, the level of π is defined as:

level(π) = 1 - cost(π) cost(π ∅ )
where cost(π ∅ ) is the cost of the null model (i.e. default rule with empty sequence body). The cost of the default rule π ∅ is formally:

cost(π ∅ ) = log(m + 1) + log( max + 1) + log n + j -1 j -1 +log(n!) - j i=1 log(n ci !)
The level naturally highlights the border between the interesting patterns and the irrelevant ones. Indeed, rules π such that level(π) ≤ 0, are less probable than the default rule π ∅ . Then using them to explain the data by characterizing classes of sequence objects is more costly than using π ∅ ; such rules are considered spurious. Rules such that 0 < level(π) ≤ 1 highlight the interesting patterns. In fact, rules with lowest cost (highest level) are the most probable arising from the data and show correlations between the rule body and the class attribute.

IV. MINING SEQUENTIAL CLASSIFICATION RULES

Mining sequential patterns [START_REF] Agrawal | Mining sequential patterns[END_REF] is a NP-hard problem. The good pruning properties of frequency measure and condensed representations of frequent patterns [START_REF] Mannila | Multiple uses of frequent sets and condensed representations (extended abstract)[END_REF] allows to save computational time though the problem remains hard for large-scale data sets (see [START_REF] Baralis | Compact representations of sequential classification rules[END_REF] for the case of sequential classification rules). Our level evaluation criterion does not hold as good properties as the frequency. Thus, if we look for the whole set of SCRM with positive level values, an exhaustive exploration of the search space is not conceivable. Indeed, the size of the search space is exponential with m the number of items: max i=1 m i ≡ O(m max ). That's why we opt for a simpler and more realistic formulation of the problem: "Mining with diversity a subset of SCRMs with positive level values".

π : s → fc 1 (s ), • • • , fc j (s ) ; 10 if level(π) > 0 ∧ π ∈ R then 11 R = R ∪ {π} 12 return R;
In the following, we describe our algorithm MiSeRe for Mining Sequential Classification Rules. Firstly, we generate all SCRMs whose body is made of one single item, such rules with positive level values are chosen (Lines 2-3). The stopping condition Line 4 refers to the running time that the end-user provides to the mining process. At each iteration of the main loop (Lines 4-11), a SCRM is built and when time is up, the process ends and the current rule set is output. We randomly choose one sequence s from the labeled sequential database D (Line 5). Then, we count the number of all subsequences that can be generated for s (denoted as ads), we employ the efficient counting procedure presented in [START_REF] Elzinga | Algorithms for subsequence combinatorics[END_REF]. The inner loop (Lines 7-11) generates randomly log(ads) subsequences of the chosen sequence s to promote diversity instead of exhaustiveness for the coverage of s . This generation (Line 8) is done by randomly removing z items from s where z is between 1 and s -2. Then, the rule π is built based on the generated subsequence s . Finally, the rule π is added to the rule set if its level value is positive and it is not already in R. The main challenge in this algorithm is "how to efficiently compute the distribution of the sequence s in each class; i.e., f c1 (s), • • • f cj (s)". To achieve this task, we use a bitset representation and Boolean operations presented in [START_REF] Ayres | Sequential pattern mining using a bitmap representation[END_REF] and we benefit from the BitSet1 class in Java in order to efficiently deal with the bitset. Using a bitset representation allows us to mine one rule π in time complexity O( s × n × log(n)).

Classification procedure. We suggest to use the SCRMs mined with MiSeRe as new features to recode the sequential data set D into a binary transactional labeled data set. A new binary feature is created for each mined rule π, and takes value 1 for an object (sid, s, c) if s if a supersequence of the body sequence of π; 0 otherwise. This procedure presents two advantages: (i), the full arsenal of existing classification algorithms can be applied to this new recoded data set; (ii), in some real-world data, the sequences are only a part of the description of data objects (together with e.g., classical categorical/numerical attributes): thus, replacing the sequential part of the description of the data by relevant binary features enriches the data before using a classification algorithm.

V. EXPERIMENTS

In this section, we empirically evaluate our approach.The experiments are designed to discuss the following questions: Q1: Is level a stable and robust interestingness measure compared with classical measures? And does it avoid spurious patterns? Q2: What about the predictive performance of wellknown classification algorithms on benchmark data recoded using SCRMs mined with MiSeRe? Q3: How does the predictive performance of our approach evolve w.r.t. the number of rules extracted? And, what about the time-efficiency of MiSeRe? Q4: How does the predictive performance of our approach compare with state-of-the-art rule-based classifiers?

For empirical evaluation, we chose 11 real-life data sets briefly described in [START_REF]Companion website. MiSeRe: Mining sequential classification rules[END_REF]. We also carried out experiments on a large marketing database from the French Telecom company Orange containing sequential information about the behavior of 76564 customers to predict their propensity to churn. Due to page limitations, we report a detailed interactive visualization of all the results as well as the JAVA code of MiSeRe are publicly available from [START_REF]Companion website. MiSeRe: Mining sequential classification rules[END_REF].

A. Stability of the level criterion

To evaluate the stability and robustness of an interestingness measure, we perform train-test experiments. Each data set is in divide in two parts: 50% for training and 50% for testing. Then, for each mined rule, train and test values are compared. We extract frequent sequential patterns from training data set by applying cSPADE [START_REF] Zaki | Sequence mining in categorical domains: Incorporating constraints[END_REF] with a minimum support of 2% and maximum gap of 2. Sequential classification rules are then generated from these patterns. We compute the level values of the mined rules for train and test set as well as the values of three well-known measures: confidence, growth rate and lift. Notice that for the motivating example skater data of the introduction (figure 1), the level values computed for the mined rules are perceptibly more stable than confidence and growth rate as shown in figure 2. The same observations stand for the other data sets. To have a global view of the stability of the studied measures on the benchmark data sets, we study the rank agreement of the measure values in the train-test experiments. For a given data set and for each measure, we rank the mined rules according to their measure values in train and test data. Then, the agreement between train and test ranks is analyzed using Spearman correlation coefficient [START_REF] Myers | Research Design and Statistical Analysis[END_REF]. Figure 3 shows that level has the high train-test correlation (coefficient value near 1) and is stable while the other measures have a weak correlation from train to test data and are thus unstable. The robustness of the level measure is also studied with the help of the following experiment. For each data set, we randomly assign a class label c ∈ C to each sequence while respecting the original class distribution. As our method MiSeRe is controlled by a running time constraint, we run MiSeRe for 30 minutes for all data sets with random labels. As a result, not one single rule could be extracted as all have a negative level value. Conversely, for most of the data sets, we still could find some sequential classification rules with high confidence, growth rate or lift. Thus, it can be concluded that level is a robust measure, it discovers no spurious patterns and avoids overfitting.

B. Predictive performance of our approach

To evaluate the predictive performance of our approach, we employ several standard classifiers on the benchmark data sets recoded using SCRMs obtained with MiSeRe. We use Naïve Bayes (NB), Random Forest (RF), Decision Tree (C4.5 alias J48), Support Vector Machine (SVM), lazy classifier IBk (a k-Nearest Neighbor) available from the Weka package [START_REF] Hall | The WEKA data mining software: an update[END_REF] -all with default parameter values -and the Selective Naïve Bayes2 (SNB) [START_REF] Boullé | Compression-based averaging of selective naive bayes classifiers[END_REF]. The predictive performance results are all obtained with stratified 10-fold cross validation: MiSeRe operates only on the training data folds.

Although MiSeRe is anytime, for convenience, we set a number of rules to be extracted, say 2 10 , i.e., 1024 rules. We apply the Friedman test and a post-hoc Nemenyi test as suggested by [START_REF] Demšar | Statistical comparisons of classifiers over multiple data sets[END_REF] for comparisons of classifiers over multiple data sets (at significance test α = 0.05 for both tests). The nullhypothesis is rejected, meaning the compared classifiers are not equivalent in terms of accuracy. The result of the Nemenyi test is represented by the critical difference (CD) chart shown in figure 4 with CD 2.2735 and where the mean rank of each classifier is plotted. Even if none of the six classifiers is singled out, the chart highlights two different groups of classifiers: {SVM, J48, IBk, NB} between which there is no statistical difference of performance; and {SNB, RF}, although they are not statistically better than SVM, they outperform the others. Thus, our recommendation is to use MiSeRe coupled with either SNB or RF. Since, SNB is Bayesian and parameterfree, meeting the characteristics of our framework, we will use SNB-MiSeRe for further inductive performance comparisons with state-of-the-art rule based classifiers below. Results for MiSeRe coupled with another classifier are available from [START_REF]Companion website. MiSeRe: Mining sequential classification rules[END_REF].

C. Effectiveness and efficiency of MiSeRe

Our mining method MiSeRe is controlled by a running time constraint during which a certain number of rules are mined. This section studies the predictive performance of SNB-MiSeRe classification system w.r.t. the number of extracted rules. Figure 5 shows the performance in terms of accuracy of SNB-MiSeRe based on ρ rules (ρ = 2 α ; α ∈ [0; 14]). From this figure, it can be observed that the predictive performance increases with the number of rules. Then, it becomes rather stable beyond few hundred of rules. Finally, we can conclude that the accuracy generally reache a plateau with about a few hundreds of mined rules for most of the data sets. (1) cSPADE [START_REF] Zaki | Sequence mining in categorical domains: Incorporating constraints[END_REF], (2) SCII [START_REF] Zhou | Itemset based sequence classification[END_REF], (3) Gokrimp [START_REF] Lam | Mining compressing sequential patterns[END_REF], and (4)

DeFFeD [START_REF] Holat | Sequence classification based on delta-free sequential patterns[END_REF]. The parameters were set for each algorithm as indicated in the original papers. Afterwards, these algorithms extract sequential rules from each training data. Then, we employ six classifiers previously mentioned on the benchmark data sets recorded using sequential classification rules obtained with MiSeRe, cSPADE, SCII, Gokrimp and DeFFeD. Figure 6 shows the average accuracy results per data set obtained with stratified 10-fold cross-validation when we combine SNB with all the extraction methods. The difference of performance between SNB-MiSeRe and other methods is clearly noticeable because SNB-MiSeRe always has the highest accuracy. Another experiment was conducted for comparing the performance of SNB-MiSeRe classifier with four state-of-the-art competitive rule-based classifiers: SCII Match, SCII CBA [START_REF] Zhou | Itemset based sequence classification[END_REF], BayesFM [START_REF] Lesh | Mining features for sequence classification[END_REF] and CBS [START_REF] Tseng | CBS: A new classification method by using sequential patterns[END_REF]. In this experiment we found that there is a difference of performance between SNB-MiSeRe and the other competitors as SNB-MiSeRe always scores the highest accuracy [START_REF]Companion website. MiSeRe: Mining sequential classification rules[END_REF].

VI. CONCLUSION AND FUTURE WORK

This paper focuses on the important problem of mining sequential rule patterns for classification purpose. We present a new interestingness measure (level) that allows us to naturally mark out interesting and robust classification rules. We develop a parameter-free algorithm that efficiently mines interesting and robust rules. Using the extracted rules as new features in a classification process has demonstrated strong predictive performance. The empirical experiments show that our system demonstrates highly competitive inductive performance compared with state-of-the-art rule-based classifiers while being highly resilient to spurious patterns. As future work, we plan to extend our approach for a labeled multidimensional sequential data set.

Fig. 1 .

 1 Fig. 1. Comparison of confidence (resp. growth rate) values for sequential classification rules in a train-test experiment: 50% train / 50% test for the skater data set.

• m :

 m Number of items in I. • j: Number of classes in C. • n: Number of triples (sid, s, c) in D. • nc: Number of triples (sid, s, c) in Dc. • s: Number of items in the sequence s. • ks: Number of distinct items in the sequence s, (ks ≤ s).

•

  max: Number of items in the longest sequence of D.

Algorithm 1 : 2 S 3 R 4 while ¬ StoppingCondition do 5 s= 6 ads=

 123456 MiSeRe input : D, a Labeled Sequential Data Set output: R, a Set of SCRMs 1 begin ={s = s1 ; s1 ∈ I} ; ={π : s → fc 1 (s), • • • , fc j (s); s ∈ S ∧ level(π) > 0} ; ChooseRandomSequence(D) ; ComputeNumberOfSubsequences(s) ;

7 for i = 1 8 s

 718 to log(ads) do = GenerateRandomSubsequence(s) ;

9

 9

Fig. 2 .

 2 Fig. 2. Level values for mined rules in a train-test experiment for the skater data .

Fig. 3 .

 3 Fig. 3. Agreement between train rank and test rank of the mined rules according to measure values for benchmark data sets.

Fig. 4 .

 4 Fig. 4.Critical difference of performance between various classifiers on data using extracted SCRMs.

Fig. 5 .

 5 Fig. 5. Evolution of accuracy results per data set w.r.t. number of rules mined

Fig. 6 .

 6 Fig. 6. Comparisons of accuracy results w.r.t. various several extraction methods.

http://docs.oracle.com/javase/7/docs/api/java/util/BitSet.html

http://www.khiops.com


Olivier Lacombe

Jonas Ruh

Dennis Brown

Faramarz Nilfouroushan

& Faramarz Nilfouroushan

published or not. The documents may come

Introduction: tectonic evolution and mechanics of basementinvolved fold-and-thrust belts basement fault reactivation may induce localization of thrusts and folds, result in the incorporation of crystalline thrust sheets into the fold-and-thrust belt, cause out-of-sequence thrusting and folding of shallow thrust sheets, and lead to the development of accommodation structures such as lateral ramps.

In some cases, however, extensional faults may not exist in the basement, or may not get reactivated despite being suitably oriented. In fact, reactivation of extensional faults is a highly selective process that depends not only on the orientation of the faults with respect to the applied stress field and on the friction along the fault planes, but also on the contrast of strength between the inherited fault zones and the surrounding crustal rocks. This points toward the importance of rheology : not only is the rheology of a structurally homogenous crust markedly different from that of a crust in which pre-existing fault zones are suitably oriented for reactivation, but even in a pre-fractured crust, brittle thickness and strength are strongly dependent on the nature of the geotherm. More generally, basement involvement in shortening requires/reflects an overall specific thermo-mechanical behavior of the lithosphere, e.g, a young thermo-tectonic age, so the lithosphere is generally rather hot, hence mechanically weak.

Basement-involvement in fold-and-thrust belts also raises the questions of the way the orogen is mechanically coupled to the foreland and how far-field orogenic stresses are transmitted into the foreland through the crust and mantle lithosphere. These questions hold not only for common fold-and-thrust belts that developed on the lower plate, but also for those foldand-thrust belts that formed within the upper plate. In both cases, far-field stresses have been shown to extend well far into the plate, more than 1000 km inboard from the active margin. The Appalachians, the active Sierras Pampeanas, and the Laramide uplifts are examples of this. In the case of the latter two famous examples, that illustrate basement-involved deformation in the retro-foreland, even more specific boundary conditions appear to be necessary to transfer stresses far into the upper plate, like those encountered in flat-slab subduction setting that is often associated to high shear stresses along the subduction interface.

This special issue of Geological Magazine presents a collection of 19 papers dealing with different aspects of basement-involved fold-and-thrust belts. Some of these contributions were presented as part of a session devoted to the tectonic evolution and mechanics of basement-involved fold-thrust belts at the 2015 European Geosciences Union General Assembly in Vienna (Austria). The aim of this session was to assemble a broad group of Earth scientists interested in the thick-skinned style of deformation in fold-and-thrust belts spanning a broad array of tectonic settings, geographical locations, and geological times. This volume presents a collection of some of the diverse research that is currently being carried out on this topic. We believe that these studies contribute to a better understanding not only of fold-andthrust belts in particular, but also of orogenic processes and of the rheology of the continental lithosphere in general.

The table of content of the Special Issue covers a large range of contributions, including general considerations on the involvement of the basement in shortening in fold-and-thrust belts, analogue and numerical modelling of basement-involved fold-and-thrust belts, fractures in basement-cored anticlines, as well as a number of regional studies, with papers dealing with well-known fold-and-thrust-belts such as the Andes, the Alps, the Carpathians, the Zagros, the Alborz, the Caledonides, China and Taiwan.

* General

Lacombe and Bellahsen provide a review of the state of knowledge on basement-involved shortening in foreland fold-and-thrust belts on the basis of the examination of selected Cenozoic They go on to briefly discuss the possible mechanical conditions for reactivation of faults that are oriented at a high angle to the convergence and the implications of this for the recent tectonics of Taiwan.

  orogens. After describing how structural interpretations of fold-and-thrust belts have evolved through time, the authors address how and the extent to which basement tectonics influence their geometry and their kinematics, and emphasize the key control exerted by lithosphere rheology, including structural and thermal inheritance, and local/regional boundary conditions on the occurrence of thick-skinned tectonics in the outer parts of orogens.* Analogue and numerical modelling approaches of basement-involved fold-and-thrust beltsLafosse et al. present a series of thermo-mechanical numerical models to evaluate the role of burial in the inhibition of pre-existing extensional faults during inversion processes. They compare their modeling results to the style of inversion of inherited half-grabens in the external Western Alps. They show that the role of the temperature, especially through tectonic burial, is critical for the inversion of extensional faults inherited from former rifts or passive margin in mountain belts. Koyi et al. investigate the effect of strike-slip faulting in the basement on the structural evolution of overlying evolving fold-and-thrust belts. Analogue modelling results show that observed deformation within the cover sequence depends on the temporal relation between basement and cover sequence deformation. They furthermore provide a detailed comparison to the Zagros and Alborz Mountains, where basement block rotation has been suggested to affect the structural evolution of the mountain belts. Burberry and Palu demonstrate a series of analogue experiments to illustrate the reactivation potential of preexisting deep-seated structures during compression. Additionally, they studied the effect of coupling/decoupling between cover and lower section on the structural evolution of fold-andthrust belts. Comparison to the southern Sawtooth Range, Montana, leads to predictions of underlying active inherited faults. Yu and Koyi conduct analogue experiments in order to reconstruct the evolution of the Bohai Bay Basin, China. They argue that previous kinematic explanations do not fully support natural observations and propose a two-stage tectonic model, from extension to rotation, to explain the Cenozoic structural evolution and complexities. * Fractures in basement-cored anticlines Laubach et al. report an analysis of fractures in the Cretaceous Frontier Formation sandstones in the basement-involved (Laramide) Table Rock anticline, Wyoming. They study fracturehosted porosity and quartz distribution along with crack-seal texture and fluid inclusion assemblage sequences in isolated, bridging quartz deposits and show that open fractures can persist through protracted burial and uplift in foreland basins. Fractures oriented at a high angle to current maximum compressive stress remain open and are weak mechanical discontinuities for millions of years even at great depth. * Regional case studies (1): Andes In their first paper, Branellec et al. performed a structural study of the basement-involved Malargue fold-and-thrust-belt, focusing on the relationships between basement and cover deformation with respect to paleogeography and structural inheritance. They propose a new cross-section along the Rio Grande valley together with a kinematic scenario of deformation propagation. In their second paper, Branellec et al. use satellite imagery and field observations to investigate two active faults located on the eastern border of the San Rafael Block (Argentina) close to, or within the epicentral area of the Villa Atuel destructive earthquake that occurred in the San Rafael area on May, 30th 1929. Geological and morphological observations reveal a late Pleistocene activity and show that the southern Mendoza Province is still undergoing shortening. Mescua et al. focus on a segment of the Andean foreland fold and thrust belt between 30º and 36º S, where they propose that the composition of the basement and the geometry of extensional basins, features inherited from the Precambrian to Early Mesozoic geologic history of the western Gondwana/South American margin, controlled Andean upper-crustal deformation and determined the development of thick-and thin-skinned belts and shortening localization. Martino et al. conduct a structural study in the Sierras Pampeanas of Córdoba (Argentina) and propose that oblique lineaments probably correlated with the pan-Gondwanan trend and which deeply affect the crust down to the Moho controlled, together with Paleozoic ductile shear zones, nucleation and development of Tertiary brittle faulting. They also show that while in Sierras Pampeanas it has been traditionally considered that high-angle reverse faults limit mountain range blocks, in some places low angle reverse faults (thrusts) may have also produced block uplifts. Perez et al. propose a balanced cross-section across the Eastern Cordillera and Subandean Zone of southern Peru and provide constraints on Cenozoic Andean shortening accommodated by thick-and thin-skinned retroarc fold-thrust belts. They further propose that earliest Andean deformation and structural compartmentalization of the Eastern Cordillera was linked to selective inversion of inherited Permo-Triassic basementinvolved normal faults that guided subsequent thick-and thin-skinned deformation. Low temperature thermochronology data supports Eocene to late Miocene exhumation, likely driven by normal fault reactivation and protracted Eastern Cordillera deformation. Bellahsen et al. report surficial structural data along the eastern side of the Sierra de Pie de Palo (Sierras Pampeanas) in the Andes of Argentina. They propose that at the Sierra scale, the current rounded shape of the Andean structure is the result of Plio-Quaternary amplification of a pre-Andean inherited antiform which is related to an East-verging fault-propagation fold instead of a West-verging fault-bend fold. They further propose a model of deformation of mica-rich foliated basement rocks at shallow depth where foliation-parallel slip can act as the main folding mechanism. Japas et al. integrate new and available structural, kinematic, geophysical and paleomagnetic data from the Neogene Sierra de los Colorados, Argentina, to investigate the effect of basement-involvement in the Pampean flat-slab segment of the southern Central Andes. They detected three different kinematic populations documented in the Neogene sedimentary sequence, shifting from a thin-skinned towards a thick-skinned mode of deformation. The initiation of basement-involved deformation is interpreted to be related to local magma-induced mechanical weakening and/or strong interplate coupling as a result of flat-slab subduction. Fuentes et al. provide new insight into the structural and tectonic evolution of the Malargüe fold-and-thrust belt located in the Argentine Andes. With new data of the synorogenic foreland basin fill combined with structural cross sections and surface maps, they constrain the temporal and geometric linkage between basement faults and the overlying thin-skinned thrust belt. Furthermore, they offer fresh input leading towards understanding related hydrocarbon systems in the area. * Regional case studies (2): Alps and alpine-type belts Pfiffner reports thin-skinned, thin-skinned basement-involved and thick-skinned styles of deformation in the Alps. He shows that thin-skinned tectonics associated with evaporite detachment occurred early during orogenesis, followed by basement-involved thin-skinned tectonics in the Penninic nappe system due to originally thinned continental crust that was heated and subducted to great depths. The earlier formed thrusts were subsequently intricately folded. Thick-skinned tectonics involving the entire upper crust took place in the latest collision phase in the Helvetic-Dauphinois nappe system, possibly related to a deep crustal detachment controlled by the breakdown of feldspar and formation of phyllonites. Granado et al. provide evidence from reflection seismic datasets, cross section construction and calculated fault displacement profiles that are integrated with gravity data, recent and historic earthquakes, lithospheric rheology, and thermochronological studies to look at involvement of crystalline basement by basement fault reactivation (in extension and shortening modes) beneath and ahead of the external parts of Alpine-Carpathian thin-skinned fold-and-thrust belt. *Regional case studies (3): Caledonides and Taiwan Rice and Anderson examine three models for restoring basement rocks coring tectonic windows in the Scandinavian Caledonides using balanced cross-sections and branch-line restorations of four transects.Despite along-strike variability in the geology of the four transects, they suggest that the basement in these transects is allochthonous. Yang et al. present the preorogenic fault architecture of the Eurasian margin and then investigate how selected faults become reactivated by far-field stress to the west of the deformation front of the Taiwan orogen, or become reactivated as strike-slip faults or thrusts within the foreland fold-and-thrust belt.

Acknowledgements. The Guest Editor team would like to acknowledge the reviewers who have played an important part in maintaining a high level of rigour to the contributions. Journal Editor-in-Chief Mark Allen is warmly thanked for his support.