Reza Akbarinia

Florent Masseglia

FMU: Fast Mining of Probabilistic Frequent Itemsets in Uncertain Data Streams

Discovering Probabilistic Frequent Itemsets (PFI) in uncertain data is very challenging since algorithms designed for deterministic data are not applicable in this context. The problem is even more difficult for uncertain data streams where massive frequent updates need be taken into account while respecting data stream constraints. In this paper, we propose FMU (Fast Mining of Uncertain data streams), the first solution for exact PFI mining in data streams with sliding windows. FMU allows updating the frequentness probability of an itemset whenever a transaction is added or removed from the observation window. Using these update operations, we are able to extract PFI in sliding windows with very low response times. Furthermore, our method is exact, meaning that we are able to discover the exact probabilistic frequentness distribution function for any monitored itemset, at any time. We implemented FMU and conducted an extensive experimental evaluation over synthetic and real-world data sets; the results illustrate its efficiency.

Introduction

Dealing with uncertainty has gained increasing attention these past few years in both static and streaming data management and mining [START_REF] Bernecker | Probabilistic frequent itemset mining in uncertain databases[END_REF][START_REF] Leung | Efficient algorithms for the mining of constrained frequent patterns from uncertain data[END_REF][START_REF] Akbarinia | Efficient Evaluation of SUM Queries Over Probabilistic Data[END_REF][START_REF] Leung | Mining of frequent itemsets from streams of uncertain data[END_REF][START_REF] Leung | Frequent itemset mining of uncertain data streams using the damped window model[END_REF]. There are many possible reasons for uncertainty, such as noise occurring when data are collected, noise injected for privacy reasons, semantics of the results of a search engine (often ambiguous), etc. Thus, many sensitive domains now involve massive uncertain data. For instance, scientific applications are producing every day very large sets of experimental and simulation data, so much so that Jim Gray has identified their management and analysis as the "Fourth Paradigm" [START_REF] Hey | The fourth paradigm : data-intensive scientific discovery[END_REF]. Example 1 illustrates a collection of uncertain data, where each record is associated to a probability of occurrence.

Example 1. Recently, China lent two pandas to France (i.e. Huan Huan and Yuan Zi) for ten years. Let us imagine the monitoring of these two pandas by means of sensors. In our scenario, these sensors gather physiological data (blood pressure, temperature, etc.) and transform it into possible activities thanks to a given model. For instance, the rule {pressure = [100..150], temperature = [80..90] → sleeping, 75%} means that with a blood pressure between 100 and 150mmHg, and a body temperature between 80 and 90 Fahrenheit, the probability that a Panda is sleeping is 75%. Figure 1 illustrates the activities inferred for the pandas. We can observe, for instance, that Yuan Zi was eating at 9am, with a probability of 40%.

With the probabilistic approach illustrated by Example 1, there are two cases for each uncertain record: either it really occurred in the real world or it did not. A reliable framework for handling such uncertainty lies in the theory of "possible worlds" [START_REF] Dalvi | Efficient query evaluation on probabilistic databases[END_REF] where each unique combination of records' existence corresponds to a possible world. Unfortunately, there is a combinatorial explosion in the number of possible worlds (n records, each associated to 2 possible values of existence, leading to 2 n possible worlds). Therefore, in this context, frequent itemset mining [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF] must be carefully adapted. Finding the number of occurrences of an itemset X in a database D (also called the support of X in D) is at the core of frequent itemset mining. In the literature, we find two main support measures for uncertain data: Expected Support [START_REF] Chui | Mining frequent itemsets from uncertain data[END_REF] (an approximate measure of support) and Probabilistic Support [START_REF] Bernecker | Probabilistic frequent itemset mining in uncertain databases[END_REF] (that is an exact measure of support in uncertain data). We work with Probabilistic Support since it gives exact results 1 . And we propose a solution for Probabilistic Frequent Itemset (PFI) mining in data streams using this measure of interest.

There are several ways to observe a data stream, two important ones being batches and sliding windows [START_REF] Kranen | Harnessing the strengths of anytime algorithms for constant data streams[END_REF]. Both techniques have pros and cons. Batches allow fast processing but the result is available only after the batch has been fulfilled (which is not compatible with real time constraints). Sliding windows allow maintaining the result any time the stream is updated, but they need more CPU. Today, existing methods for uncertain data stream mining are batch-based and work with Expected Support [START_REF] Zhang | Finding frequent items in probabilistic data[END_REF][START_REF] Leung | Mining of frequent itemsets from streams of uncertain data[END_REF][START_REF] Leung | Frequent itemset mining of uncertain data streams using the damped window model[END_REF]. However, working with sliding windows is a major matter for numerous monitoring applications where handling "anytime queries" is crucial. Let us consider, for instance, a patient's electrocardiogram that is monitored in real time because alarms must be triggered as soon as an abnormal behavior is detected. This kind of constraints is very important when security is at stake (health monitoring, intrusion detection, prediction of natural disasters, etc.) and surveillance must be done in an ongoing fashion. Meanwhile, since a data stream cannot be observed as a whole in main memory, and because related applications call for ongoing processes, an observation window is often needed.

The main challenge, with sliding windows, is to update the support of monitored itemsets upon transaction arrival or removal. We introduce FMU (Fast Mining of Uncertain data streams), a framework adopting the exact approach while meeting the time limitations of data stream environments. To the best of our knowledge, FMU is the first solution for PFI mining in a sliding window over uncertain data streams.

Although our approach works on both statistical dependent and independent data (we discuss this point in Section 3) we describe it for independent data for simplicity of presentation. Our contributions are the following:

• We define a new model for uncertain data streams, where an item may have multiple occurrence (each associated to a probability) for one transaction. • We propose a new approach for computing probabilistic support by recursion on the transactions. This approach allows to develop efficient algorithms for updating probabilistic support after any modification in the sliding window. • We propose new algorithms for probabilistic frequent itemset mining with sliding windows, where transactions are inserted or deleted. Our algorithms allow updating the new probabilistic support of any monitored itemset with a low complexity since it doesn't need to scan the whole sliding window from scratch.

Our experiments show the feasibility of our approach, which is able to discover and manage PFI in data streams with response time that are up to several orders of magnitude faster than baseline methods of the literature employed in a sliding window context.

Problem Definition

We now describe the problem we address with formal definitions of the uncertainty model we adopt, probabilistic itemset mining and uncertain data streams. Our notations are summarized by Figure 5.

2.1. Uncertain Data. Let I be a set of literals. I is also called the vocabulary. An event e i is a tuple e i =< Oid, ts, x, P > where i is the identifier of the event, Oid is an object identifier, ts is a timestamp, x ∈ I is an item and P is an existential probability P ∈ [0, 1] denoting the probability that e i occurs.

Example 2. Consider the data given by Figure 1, the first two events for Huan Huan are: e 1 =< Huan Huan, 8, sleeping, 0.3 > and e 3 =< Huan Huan, 9, eating, 0.3 >.

Definition 1. An uncertain item x is an item that appears in an event, the probability of x is the probability of its event.

Definition 2. An uncertain transaction t is a set of pairs (x, P ) for an object such that x is an uncertain item and P is the probability of the event of x. P (x ∈ t) is the probability of existence of x in t. An uncertain database is a set of uncertain transactions. An uncertain database can be treated as a set of deterministic databases, called possible worlds. The possible worlds are generated from the possible instances of transactions. Let w be a possible world, then the instance of a transaction t in w is denoted by t w . Figure 3 shows the possible worlds for the database in Figure 2. In this database, the instance of transaction t 1 in w 3 is {sleeping}, and that of transaction t 2 is {drinking}. For each possible world w, there is probability P (w) that is computed based on the probability of its transaction instances. The sum of the probabilities of all possible worlds of a database is equal to one.

In the case of independence of events, the probability of a given world is computed as P (w) = t∈I P (t w ), where P (t w ) is the probability of t's instance in w. P (t w ) is computed as follows:

P (t w ) = ( x∈tw (P (x ∈ t)) × ( x / ∈tw (1 -P (x ∈ t)))
Intuitively, we multiply the existential probability of t items that are present in t w by the probability of absence of those that are not present in t w .

Example 4. In the possible worlds shown in Figure 3, the probability of w 4 is equal to the occurrence of eating and sleeping for transaction t 1 , drinking for t 2 , and the nonoccurrence of eating for t 2 . Thus P (w 4 ) = (0.3 × 0.3 × 1) × (1 -0.4) = 0.054.

2.2. Probabilistic Frequent Itemsets. The problem of frequent itemset mining from a set of transactions T , as defined in [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF], aims at extracting the itemsets that occur in a sufficient number of transactions in T . This is based on the number of transactions in T where an itemset X appears (i.e. the support of X in T ). In the deterministic context, computing this support is straightforward (with a scan over T ). In uncertain databases, however, the support varies from one possible world to another. For this reason, the support of an itemset in an uncertain database, introduced in [START_REF] Bernecker | Probabilistic frequent itemset mining in uncertain databases[END_REF], is given as a probability distribution function. In other words, each possible value i ∈ {0, . . . , |T |} for the support of X is associated to a probability that is the probability that X has this support in the uncertain database. Definition 3 gives a more formal definition of this notion.

Definition 3. Let W be the set of possible worlds and S X,w be the support of X ∈ I in world w ∈ W . The probability P X,T (i) that X has support i in the set of uncertain transactions T is given by:

P X,T (i) = w∈W,S X,w =i P (w) (1)
The probability distribution function P X,T (i)

for i ∈ [0..|T |] is called the probabilistic support of X.
Example 5. In the possible worlds given by Figure 3, we have P eating,T (1) = P (w 2 ) + P (w 4 ) + P (w 5 ) + P (w 7 ) = 0.46. In other words, the probability that exactly one Panda is eating between 9am and 10am is 46%.

Definition

4. Given a support value i, the probability P ≥X,T (i) that an itemset X has at least i occurrences in T , is given by:

P ≥X,T (i) = |T | j=i P X,T (j) (2)
Given minSup and minP rob, a user minimum support and minimum probability, and T a set of uncertain transactions, an itemset X is a probabilistic frequent itemset (PFI) iff P ≥X,D (minSup) ≥ minP rob. P ≥X,D (minSup) is also called the frequentness probability of X. Example 6. Figure 4 gives the probability distribution function of the itemset "eating". The probability that "eating" has support of at least 1 is given by P eating,T (1)+P eating,T (2) = 0.46 + 0.12 = 0.58. In other words, the probability that at least one panda was eating between 9am and 10am is 58%. Set of all items X, x Itemset X ⊆ I, and x ∈ X an item S X,w Support (number of occurrences) of X in world w P X,T (i) Probability that the support of X in the set of transactions T is i P ≥X,T (i) Probability that the support of X in the set of transactions T is at least i

P (X ⊆ t)
Probability that itemset X is a subset of a transaction t In many applications, the data production rate is so high that their analysis in real time with traditional methods is impossible. Sensor networks, Web usage data, scientific instruments or bio-informatics, to name a few, have added to this situation. Because of their rate, data streams should often be observed through a limited observation window and their analysis is highly constrained (e.g. "in real-time", "with ongoing queries", "with no access to outdated data", etc.). There are several models for this observation, including sliding windows [START_REF] Zhang | ABS: The anti bouncing model for usage data streams[END_REF] . Definition 5 gives a formal definition of this notion.

Definition 5. An event data stream (or data stream) is an unbounded stream of ordered events. Given n, the maximum number of events to maintain in memory, a sliding window over a data stream contains the last n events from the stream.

The problem of probabilistic frequent itemset mining in a sliding window is to extract the set of probabilistic frequent itemsets after each update. The updates occur when a new event is added to the stream and the oldest one is removed from the sliding window.

PFI Mining in Sliding Windows

We now introduce FMU, our framework for PFI mining in uncertain data streams with a sliding window SW . FMU allows monitoring the probabilistic support of all the itemsets of SW in real time, as opposed to the batch model where these results are obtained only when a batch is complete. However, the main challenge in this approach consists in updating the probabilistic support of an itemset X when a transaction t is added to, or removed from, the stream. In particular, updating the probabilistic support upon transaction removal is crucial. We give our solution for this step in Section 3.5. In deterministic data, this operation is simple, we just check if X ⊆ t and update its support consequently. In the context of possible worlds, there is no such straightforward approach and the challenge is to update the probabilistic support as fast as possible in order to match the constraints of streaming environments.

Before describing our solution, we mention that one of its requirements is to know P (X ⊆ t), the probability that itemset X is included in transaction t. In the case of independent items, it can be computed as P (X ⊆ t) = |X| i=1 P (x i ∈ t). In the case where items of transaction t are dependent, for computing P (X ⊆ t) we have to take into account the rules defined on the dependency of items. For example, if two items x 1 and x 2 have a mutual exclusion dependency, then the probability that X = {x 1 , x 2 , . . . } is a subset of a transaction t is zero.

P (x i ∈ t) = 1 -n j=1 (1 -P (x i j , t)). Example 7.
Consider the stream of events illustrated in Figure 1 and SW , the sliding window limited to the last 6 events. Figure 6 illustrates the content of SW from 11am (i.e. e 3 to e 8 ) to 12am (i.e. e 5 to e 10 ). In this example, when e 9 is added, we update the probability of sleeping for Huan Huan but we do not need to remove any item from SW . Then, after e 10 , we add marking to the uncertain transaction of Yuan Zi and e 3 , the oldest event, must be removed.

3.2.

Computing Frequentness Probability. For computing the probability that an itemset X is frequent, we need to sum up the probabilities of all supports i for i > minsup. In other words, we have P ≥X,T (minsup) = |T | i=minsup P X,T (i), where P X,T (i) is the probability of support i for X in T . Notice that the sum of the probabilities in each row is equal to one. Therefore, we have:

P ≥X,T (minsup) = (1 - minsup-1 i=0 P X,T (i)) (3)
We use Equation 3 for computing the frequentness probability of itemsets. To update the frequentness probabilities after inserting/deleting a transaction, we need to be able to compute and update the probability of support i (0 ≤ i ≤ minSup -1) for an itemset X after inserting/deleting a transaction to/from the sliding window.

Our approach for computing the probabilistic support of itemsets uses a recursion on transactions. Using it, we propose our algorithms for updating the probabilistic supports in the sliding window after inserting or deleting transactions.

Recursion On Transactions.

Let X be an itemset, DB n be an uncertain database involving transactions T = {t 1 , . . . , t n }, and P X,T (i) be the probability that the support of X, in the set of transactions T , is i. We develop an approach for computing P X,T (i) by doing recursion on the number of transactions.

3.3.1.

Base. Let us first consider the recursion base. Consider DB 1 be a database that involves only transaction t 1 . In this database, the support of X can be zero or one.

The support of X in DB 1 is 1 with probability P (X ⊆ t 1 ) , and its support is 0 with probability (1 -P (X ⊆ t 1 )). Thus, for the probabilistic support of X in DB 1 , we have the following formula:

P X,{t 1 } (i) =    P (X ⊆ t 1 )
for i=1; (1 -P (X ⊆ t 1 )) for i=0; 0 for i > 1

Recursion

Step. Assume we have DB n-1 , a database involving the transactions t 1 , . . . , t n-1 . We construct DB n by adding transaction t n to DB n-1 . If X ⊆ t n then the probability of support i for X in DB n is exactly the same as that in DB n-1 . If X ⊆ t n then two cases can lead to a support of i for X in DB n :

(1) X ⊆ t n in DB n and the support of X in DB n-1 is equal to i -1. Thus, we have:

P X,T (i) = P X,T -{tn} (i -1) × (P (X ⊆ t n )).
(2) X t n and the support of X in DB n-1 is equal to i. Thus, we have:

P X,T (i) = P X,T -{tn} (i) × (1 -P (X ⊆ t n )).
Then, the probability of support i for X in a database containing t 1 , . . . , t n is computed based on theorem 1.

Theorem 1. Given an itemset X and a set of transactions T = {t 1 , . . . , t n-1 , t n }, the probabilistic support of X in T can be computed based on the probabilistic support in T -{t n } by using the following equation:

P X,T (i) = P X,T -{tn} (i -1) × (P (X ⊆ t n )) +P X,T -{tn} (i) × (1 -P (X ⊆ t n )) (4)
Proof. Implied by the above discussion.

3.4.

Updating Probabilistic Support after Inserting a Transaction. To efficiently support data mining over uncertain data streams, we need to update efficiently the probabilistic support of itemsets after each update. Here, we deal with the insertion of a new transaction to the sliding window. The case of transaction removal will be addressed in Section 3.5.

After inserting a new transaction to the sliding window, the probabilistic support can be updated as follows (see Algorithm 1). Let P X,T [0..|SW |] be an array such that P X,T [i] shows the probability of support i for itemset X in a set of transactions T . |SW | is the maximum support of a transaction in the sliding window, i.e. the size of the window. Given P X,T , we generate an array P X,T +{t} such that P X,T +{t} [i] shows the probability of support i for X in T + {t}. Algorithm 1 shows the steps for filling the array P X,T +{t} . It considers two main cases: either T is empty or T is not empty (so P X,T is available). In the first case, we have only one transaction in the sliding window. Thus, our algorithm initializes P X,T +{t} using the base of our recursive formula (described in Section 3.3.1) by setting P X,T +{t} [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF] = P (X ⊆ t) and P X,T +{t} [0] = 1 -P (X ⊆ t). In the second case, i.e. where T is not empty, the algorithm computes the values of P X,T +{t} based on those in P X,T by using our recursive formula (i.e. Equation 4) as follows:

P X,T +{t} [i] = (P X,T [i -1] × P (X ⊆ t)) + (P X,T [i] × (1 -P (X ⊆ t)))
When P (X ⊆ t) = 0 we can simply ignore the transaction since it has no impact on the support, thus we have P X,T +{t} = P X,T . Recall that for computing the frequentness probability of itemsets, we need to know only the probability of supports between zero and minSup -1. This is the reason why in our algorithm we fill the array only for the values that are lower than minSup. Example 8 illustrates our algorithm.

Example 8. Figure 7 shows the execution of our algorithm over the database shown in Figure 2, with X=eating. Recall that, in this database, we have: P (X ⊆ t 1 ) = 0.3 and P (X ⊆ t 2 ) = 0.4. Initially T = {}, then we add t 1 and afterwards t 2 to it. In the fist row, the algorithm sets the probabilistic supports for T = {t 1 }. Thus, we have

P X,T +{t 1 } [1] = P (X ⊆ t 1 ) = 0.3 and P X,T +{t 1 } [0] = (1 -P (X ⊆ t 1 )) = 1 -0.3 = 0.7.
The probabilities in the second row are computed using our recursive definition. For example, P X,{t 3.5. Updating Probabilistic Support after Deleting a Transaction. Assume we have the probabilistic support of an itemset X for a set of transactions T , then the question is: "how to compute the probabilistic support in T -{t} ?" One might think that the probabilistic support i for X in T -{t} (i.e. P X,T -{t} (i)) could be computed as P X,T (i -1)/P (X ⊆ t) + P X,T (i)/(1 -P (X ⊆ t)). Unfortunately, this formula will not work. For example, if we use it for computing P eating,{t 1 } (1) after deleting transaction t 2 from the database used in Example 8, then we obtain 0.42 × 0.4 + 0.46 × 0.6 = 0.444, Algorithm 1 Updating the probabilistic support of an itemset X when a transaction is inserted into the sliding window. Input: X: itemset; t: new transaction; T : set of transactions before arrival of t; P X,T : an array containing probabilistic support of X in T Output: P X,T +{t} : an array containing probabilistic supports for X in T + {t}

1 ,t 2 } [1] = (P X,{t 1 } [0] × P (X ⊆ t 2 )) + (P X,{t 1 } [1] × (1 -P (X ⊆ t 2 )) = (0.
1: if |T | = 0 then 2:
P X,T +{t} [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF] = P (X ⊆ t)

3: P X,T +{t} [0] = 1 -P (X ⊆ t) 4: else 5: if P (X ⊆ t) = 0 then 6: P X,T +{t} = P X,T 7: else 8: P X,T +{t} [0] = P X,T [0] × (1 -P (X ⊆ t)) 9: k = min{minSup -1, |T |}; 10: for i = 1..k do 11: P X,T +{t} [i] = (P X,T [i -1] × P (X ⊆ t)) + (P X,T [i] × (1 -P (X ⊆ t))) 12:
end for

13: if minSup -1 > |T | then 14: P X,T +{t} [|T | + 1] = (P X,T [|T |] × P (X ⊆ t)) 15: end if 16:
end if 17: end if 18: return P X,T +{t} whereas the value of P eating,{t 1 } (1) is equal to 0.3 (see Figure 7). To solve the problem of updating the probabilistic support of X in T -{t}, we develop the following theorem: Theorem 2. Let X be an itemset, T a set of transactions, and P X,T an array denoting the probabilistic support of X in T . Assume we delete a transaction t from T . Let P X,T -{t} (i) be the probability for X to have support i in T -{t}, then P X,T -{t} (i) can be computed as:

P X,T -{t} (i) = P X,T (i)-(P X,T -{t} (i-1)×P (X⊆t)) 1-P (X⊆t) if P (X ⊆ t) = 1; P X,T (i + 1)
otherwise;

Proof. In the case where P (X ⊆ t) = 1, it is obvious that by removing t from T , the support of X is reduced by one. Thus, the probability of support i in T -{t} is equal to the probability of support i + 1 in T . For the case where P (X ⊆ t) = 1, it is sufficient to show that:

P X,T -{t} (i) × (1 -P (X ⊆ t)) = P X,T (i) -(P X,T -{t} (i -1) × P (X ⊆ t)).
For this, we expand the right side of this equation by using Equation 4 in Section 3.3.2. We replace P X,T (i) by its equivalent, that is:

P X,T -{t} (i -1) × (P (X ⊆ t)) + P X,T -{t} (i) × (1 -P (X ⊆ t))
Thus, we have:

P X,T (i) -(P X,T -{t} (i -1) × P (X ⊆ t)) = P X,T -{t} (i-1)×(P (X ⊆ t))+P X,T -{t} (i)×(1-P (X ⊆ t))-(P X,T -{t} (i-1)×P (X ⊆ t)) = P X,T -{t} (i) × (1 -P (X ⊆ t))
Theorem 2 suggests to compute P X,T -{t} (i) based on P X,T (i) and P X,T -{t} (i -1). To develop an algorithm based on this theorem, we need to compute P X,T -{t} (0) that is the probability of support 0 for X in T -{t}. This can be done as follows. We use the fact that when a transaction t is added to the sliding window, the probability of support 0 is multiplied by the probability of absence of t. Thus, when t is removed from T , to compute P X,T -{t} (0) we can divide P X,T (0) by (1 -P (X ⊆ t)), if P (X ⊆ t) = 1. In other words, we have:

P X,T -{t} (0) = P X,T (0) 1 -P (X ⊆ t) , f orP (X ⊆ t) = 1 (5)
Equation 5 works iff P (X ⊆ t) = 1. In the case where P (X ⊆ t) = 1, we can compute P X,T -{t} (0) by simply multiplying the probability of absence of all transactions contained in the sliding window. Thus, we have:

P X,T -{t} (0) = t j ∈(T -{t}) (1 -P (X ⊆ t j )) (6)
Equation 6 works even in the cases where P (X ⊆ t) = 1. But, in those cases, we prefer to use Equation 5 because it leads to a more efficient computation of P X,T -{t} (0).

Based on Theorem 2 and Equations 5 and 6, we develop Algorithm 2 that updates the probabilistic support after removing a transaction from a sliding window. Recall that for finding frequent itemsets, we need only to compute the probabilistic supports for values that are lower than minSup. This is why the "for loop" in the algorithm (started at Line 10) is from 1 to min{minSup -1, |T | -1}. For updating the probabilistic support of an itemset X after deleting a transaction from the sliding window, Algorithm 2 has the same time and space complexity as Algorithm 1.

Experiments

We evaluate the performance of FMU by a thorough comparison to existing algorithms in the literature that use Probabilistic Support in exact [START_REF] Bernecker | Probabilistic frequent itemset mining in uncertain databases[END_REF] and approximate [START_REF] Wang | Accelerating probabilistic frequent itemset mining: a model-based approach[END_REF] mining. Since we do not find sliding window approaches in the literature, we have implemented these algorithms as follows: each time an event is added or removed from the sliding window, the algorithm runs, from scratch, on the content of the updated sliding window. PFIM is the algorithm of [START_REF] Bernecker | Probabilistic frequent itemset mining in uncertain databases[END_REF] implemented with all the optimizations (including the 0-1 optimization). However, due to extremely high response time in batch mode, we implemented two other versions of this algorithm. In PFIM-50% the discovery is not Algorithm 2 Updating the probabilistic support of an itemset X after deleting a transaction. Input: X: itemset; t: deleted transaction; T : set of transactions before delete; P X,T : an array containing probabilistic support of X in T Output: P X,T -{t} : an array containing probabilistic supports for X in T -{t} 1: if P (X ⊆ t) = 0 then 2:

P X,T -{t} = P X,T 3: else 4: if P (X ⊆ t) ¡ 1 then 5: P X,T -{t} [0] = P X,T [0] 1-P (X⊆t) 6: else 7: P X,T -{t} [0] = t j ∈(T -{t}) (1 -P (X ⊆ t j )) 8: end if 9: k = min{minSup -1, |T | -1}; 10: for i = 1..k do 11: if P (X ⊆ t) = 1 then 12: P X,T -{t} [i] = P X,T [i + 1] 13: else 14: P X,T -{t} [i] = P X,T [i]-(P X,T -{t} [i-1]×P (X⊆t)) 1-P (X⊆t)
15:

end if

16:
end for 17: end if 18: return P X,T -{t} performed for each event but for each two events (only 50% of the events are considered). In PFIM-25%, the discovery on the sliding window is performed each 4 events. Eventually, Poisson is the algorithm of [START_REF] Wang | Accelerating probabilistic frequent itemset mining: a model-based approach[END_REF] (that allows approximate PFI mining) running on the whole sliding window after each update. A discussion of these algorithms is given in Section 5.

We use two datasets for these experiments: a synthetic one (by the IBM2 generator) and a real one (the "accident" dataset from the FMI repository3 ). The synthetic dataset contains 38 millions of events, 8 millions of transactions and 100 items. The accidents dataset contains 11 millions of events, 340K transactions and 468 items. We have added an existential probability P ∈]0..1] to each event in these datasets, with a uniform distribution. For both datasets, minSup has been set to 30% of the window size and minP rob to 40%. We have implemented two versions of FMU. The first one is "Dynamic-FMU" (d-FMU in our experiments). In this version, when a new candidate itemset is generated, it's frequentness probability will be checked over the next updates in the stream thanks to Algorithms 1 and 2. This is the fastest approach but it implies a delay in the pattern discovery (similar to the delay described in [START_REF] Teng | A Regression-Based Temporal Pattern Mining Scheme for Data Streams[END_REF]). The second version is "Exact-FMU" (e-FMU in our experiments). Here, each time a candidate itemset is generated it is immediately verified, from scratch, over all the transactions maintained in the current sliding window with Algorithm 1. Besides that, the probabilistic support of all existing itemsets is maintained at each update thanks to Algorithms 1 and 2. e-FMU guarantees an exact PFI discovery at any point in the stream. However, this is done at the price of a higher time complexity compared to d-FMU.

4.1. Feasibility. Figure 8 shows the time needed by each algorithm to extract the PFI in a growing sliding window SW . The size of SW grows from 0 to 5000 transactions for the synthetic dataset and from 0 to 10000 for the accident dataset. This corresponds to the initialization of the stream. We observe that the response time of d Figure 9 shows the time needed by each algorithm to process 100 events, while the transaction data is fed in a pass-through fashion. Although probabilistic supports are maintained after each update in the cases of d-FMU, e-FMU, Poisson and PFIM, we report the time for 100 events because the response time of d-FMU, for only one event, would always be 0s. That time is recorded as the number of processed events increases, from the 100 th event to the 50000 th one in the case of synthetic dataset (100000 th for accident dataset). We observe that d-FMU needs less than 0.05s to update the supports of the monitored itemsets in memory for each 100 updates to the stream. e-FMU needs more time (up to 1s) since it has to scan SW when new candidate itemsets are generated. Depending on the dataset, Poisson is faster or slower that PFIM-25%. This is due to the difference in density between these datasets, where Poisson can extract itemsets that are not frequent (slowing down the extraction process). Over the synthetic dataset, the time needed by e-FMU is 5 times faster than Poisson (while extracting exact probabilistic support, whereas Poisson gives an approximation with Expected Support) and up to 20 times faster than PFIM. We also observe that d-FMU is very close to 0s. In fact, in our experimental data, d-FMU appears to run up to two orders of magnitude faster than PFIM on the accident dataset to process 100 events. The global response time of d-FMU, as the stream passes through, is several orders of magnitude lower than that of PFIM.

4.2. Scalability. Figure 10 shows the running times of each algorithm for a full sliding window. More precisely, when a sliding window SW is full (after initialization), we measure the time needed to process |SW | events. This time is measured for an increasing size of SW . Our experiments clearly show that d-FMU incurs very few overhead to the computations needed for maintaining the data structures. We can observe, for instance, that when |W S| = 5000 in the synthetic dataset, e-FMU needs 14s to process 5000 events, when Poisson takes 29s. These results confirm those shown in Figure 9 where Poisson needs approximately 0.6s (and approximately 0.3s for e-FMU) to process 100 events. Expected Support. Uncertain data mining is a recent research topic that is gaining increasing attention [START_REF] Leung | Efficient algorithms for the mining of constrained frequent patterns from uncertain data[END_REF][START_REF] Calders | Approximation of frequentness probability of itemsets in uncertain data[END_REF][START_REF] Sun | Mining uncertain data with probabilistic guarantees[END_REF][START_REF] Leung | Frequent itemset mining of uncertain data streams using the damped window model[END_REF][START_REF]Mining frequent patterns from univariate uncertain data[END_REF]. In [START_REF] Chui | Mining frequent itemsets from uncertain data[END_REF], the problem of itemset mining from uncertain data is introduced and the authors propose the notion of Expected Support as a first solution. Let P (X ⊆ t) be the probability that itemset X is included in transaction t, the Expected Support ES(X) of X in database D is given by: ES(X) = |D| j=1 P (X, t j ). This support is then used as a frequency measure (compared to a user minimum threshold) in U-Apriori, a level-wise approach based on the Apriori principle for frequent itemset mining.

Probabilistic Support. In [START_REF] Bernecker | Probabilistic frequent itemset mining in uncertain databases[END_REF], the authors introduce the notion of probabilistic support which is an exact measure of an itemset support in the possible world model. Their idea is to find the probability that an itemset X has support i by using Definition 4. The authors propose to compute the frequentness probability of an itemset X with a dynamic programming approach inspired from [START_REF] Yi | Efficient processing of top-k queries in uncertain databases with x-relations[END_REF]. Actually, a number of contributions to probabilistic data management and querying problems have shown the relevance of dynamic programming for this purpose [START_REF] Yi | Efficient processing of top-k queries in uncertain databases with x-relations[END_REF][START_REF] Akbarinia | Efficient Evaluation of SUM Queries Over Probabilistic Data[END_REF][START_REF] Bernecker | Probabilistic frequent itemset mining in uncertain databases[END_REF]. These papers rely on a divide and conquer approach that avoids enumerating all the possible worlds. The principle is to consider processing a request on a dataset T as a recursion on subsets of T . This principle has been applied to the problems of Top k queries [START_REF] Yi | Efficient processing of top-k queries in uncertain databases with x-relations[END_REF] or aggregate queries [START_REF] Akbarinia | Efficient Evaluation of SUM Queries Over Probabilistic Data[END_REF] in uncertain databases. It has also been exploited in [START_REF] Bernecker | Probabilistic frequent itemset mining in uncertain databases[END_REF] in order to avoid enumerating the whole set of possible worlds and speed-up the extraction of exact probabilistic frequent itemsets. However, their approach is incremental in the support (i.e. the transaction set is fixed and each iteration of their recursion allows computing the support probability of an itemset for an increasing support). Therefore, we believe that adapting this method to data streams would be very difficult, since we need a method that would be incremental in the transactions as proposed in Section 3.4 (each iteration should allow computing the support probability after reading a new transaction). Some approximation methods for the probabilistic support of an itemset have also been proposed. The idea of [START_REF] Wang | Accelerating probabilistic frequent itemset mining: a model-based approach[END_REF] is to approximate the support distribution function by means of a Poisson law. In [START_REF] Calders | Approximation of frequentness probability of itemsets in uncertain data[END_REF], the authors propose another approximation of frequentness probability based on the central limit theorem. The main drawbacks of these approaches are to use Expected Support as a measure of probabilistic frequentness [START_REF] Wang | Accelerating probabilistic frequent itemset mining: a model-based approach[END_REF] and to work only on statistical dependent data [START_REF] Wang | Accelerating probabilistic frequent itemset mining: a model-based approach[END_REF][START_REF] Calders | Approximation of frequentness probability of itemsets in uncertain data[END_REF]. We discuss these points in Section 6.

Uncertain Data Streams. Itemset mining in data streams is an important topic of knowledge discovery [START_REF] Teng | A Regression-Based Temporal Pattern Mining Scheme for Data Streams[END_REF][START_REF] Giannella | Mining Frequent Patterns in Data Streams at Multiple Time Granularities[END_REF]. Mainly, we find contributions on the extraction techniques and the data models, such as batches [START_REF] Giannella | Mining Frequent Patterns in Data Streams at Multiple Time Granularities[END_REF] or sliding windows [START_REF] Teng | A Regression-Based Temporal Pattern Mining Scheme for Data Streams[END_REF][START_REF] Zhang | ABS: The anti bouncing model for usage data streams[END_REF]. In [START_REF] Kranen | Harnessing the strengths of anytime algorithms for constant data streams[END_REF], we find a comparative study of these models. In [START_REF] Zhang | Finding frequent items in probabilistic data[END_REF], the authors propose to extract frequent items in probabilistic data. Their approaches allow finding items (itemsets of only one item) in static data and likely frequent items in data streams. [START_REF] Leung | Mining of frequent itemsets from streams of uncertain data[END_REF] proposes to extract frequent itemset from streaming uncertain data by means of Expected Support and a batch model. In [START_REF] Leung | Frequent itemset mining of uncertain data streams using the damped window model[END_REF], we find a batch-based approach to extract frequent itemsets using Expected Support in uncertain data streams with a technique inspired from [START_REF] Giannella | Mining Frequent Patterns in Data Streams at Multiple Time Granularities[END_REF].

Despite the interest of exact PFI mining with sliding windows [START_REF] Kranen | Harnessing the strengths of anytime algorithms for constant data streams[END_REF][START_REF] Zhang | ABS: The anti bouncing model for usage data streams[END_REF], we do not find any proposal in the literature for such an approach. As we discuss in Section 3, the main challenge in this context is to update the probabilistic support of an itemset when a transaction is added to or removed from the window. Our work is therefore motivated by the needs and challenges of providing an approach that is able to i) extract PFI from data streams; ii) use sliding windows and update the support of an itemset upon transaction insertion or removal; and iii) work with statistical dependent and independent data.

Limitations of Expected Support and Approximate Approaches

In the literature, we find interesting approaches using Expected support or estimating the Probabilistic Support of an itemset. These approaches have low complexity, allowing fast processing, but building on such estimations has drawbacks that motivate us for proposing a method that works with Probabilistic Support.

Let us consider the support count of sleeping in the Pandas' activities given by Figure 1. Sleeping is very important for Pandas and monitoring the frequency of this activity allows preventing health problems. The Expected Support of sleeping for Huan Huan is 0.3 + 0.3 + 0.3 = 0.9 and it is the same for Yuan Zi (only one occurrence, with a probability of 0.9). Therefore, with the same parameters, if sleeping is found frequent for Huan Huan under Expected Support, then it will also be found frequent for Yuan Zi. The fact that Huan Huan is sleeping three times a day and Yuan Zi only once does not make any difference for Expected Support. Furthermore, by using the same parameters that make sleeping a frequent item for both pandas' activities, we will find that drinking, grooming and growling are also frequent for Yuan Zi (as well as sleeping and courting for Huan Huan).

Another issue of approximate approaches [START_REF] Wang | Accelerating probabilistic frequent itemset mining: a model-based approach[END_REF][START_REF] Calders | Approximation of frequentness probability of itemsets in uncertain data[END_REF] is that they can not work correctly on dependent data. Actually, many real world applications involve dependent data and require careful attention. Consider road traffic monitoring applications and speed cameras. It is possible that an observed vehicle is a tractor. It is also possible that a vehicle speed is 90Mph. However, it is not possible that a tractor is observed at 90Mph. Therefore, a world w containing a transaction t where a vehicle is a tractor and the speed is 90Mph does not exist. This probability of zero can be given to the model of exact approaches, whereas existing approximate methods cannot take it into account.

Conclusion

In this paper, we proposed FMU, the first solution for exact PFI mining in data streams with sliding windows. FMU allows computing the exact probabilistic support of an itemset whenever a transaction is added or removed from the observation window. Compared to non-incremental algorithms, that need to scan the whole sliding window after each update, our approach shows very low time complexity. Through an extensive experimental evaluation on synthetic and real datasets, we observed that FMU is up to several orders of magnitude faster than a traditional approach, adapted to sliding windows,

Figure 1 .

 1 Figure 1. Panda's activities inferred from body sensor data

Figure 3 .

 3 Figure 3. Possible worlds for the database illustrated in Figure 2

Figure 4 .

 4 Figure 4. The probabilistic support of "eating" in the database of figure 2

Figure 5 .

 5 Figure 5. Description of Notations

Figure 7 .

 7 Figure 7. Computing the probabilistic support of eating in the uncertain database of Figure 2

Figure 8 .

 8 Figure 8. Initialization time (filling SW ) on synthetic (top) and accident (bottom) datasets

Figure 9 .

 9 Figure 9. Processing times for 100 events on synthetic (top) and accident (bottom) datasets

Figure 10 .

 10 Figure 10. Processing time for |SW | events with increasing size of SW on synthetic (top) and accident (bottom) datasets

  Sliding Window Model. Our sliding window model maintains a set of uncertain transactions in memory. When the stream produces a new event e i =< Oid, time, x, P >, the corresponding object in the model is either created or updated in the window. With streaming data, an item x may occur at several points in time and each occurrence is associated to a probability. Therefore, we must give a reliable probability of existence of x, by taking each probability of occurrence into account. To that end, we consider P (x ∈ t) as the probability that at least one occurrence of x exists in t (i.e. 1 minus the probability that x does not exist in t). Let x i 1 , . . . , x in be the occurrences of x i in t, then we compute P (x ∈ t) as follows :

	Panda	Sliding window of size 6, after e 8
	Huan Huan	(eating, 0.3); (sleeping, 0.3); (grooming, 0.4)
	Yuan Zi	(eating, 0.4); (drinking, 1); (grooming, 0.9)
		Sliding window of size 6, after
		e 9
	Huan Huan	(eating, 0.3); (sleeping, 0.51); (grooming, 0.4)
	Yuan Zi	(eating, 0.4); (drinking, 1); (grooming, 0.9)
		Sliding window of size 6, after
		e 10
	Huan Huan (sleeping, 0.51); (grooming, 0.4)
	Yuan Zi	(eating, 0.4); (drinking, 1); (grooming, 0.9); (marking, 0.4)

Figure 6. Sliding windows of size 6 from e 3 to e 10 3.1.

  -FMU increases barely since it needs very few calculations. e-FMU increases more clearly, since it must scan SW each time a new candidate is proposed. Meanwhile, all the versions of PFIM and Poisson have much higher response times. d-FMU needs 7.34s to fill SW for the accident dataset, where PFIM needs 618s. Furthermore, we can see that Poisson is faster than all versions of PFIM after a number of transactions, but not for the first ones. This is due to the large number of infrequent patterns extracted by Poisson, caused by the approximation of Expected Support. Actually, for the first hundreds of transactions, Poisson may extract up to 146 PFI while the real number of PFI is 36 at most. Such a large number of erroneous PFI is a cause of unnecessary computations and high response times.

We give detailed motivations for this choice in Section 6.

http://www.cs.loyola.edu/ cgiannel/assoc gen.html

http://fimi.ua.ac.be/data/


Elise Arnaud

Pierre-Yves Longaretti

Emmanuel Prados

Peter Sturm

MODELLING FOR LOCAL SCALE SUSTAINABILITY AND DECISION-MAKING SUPPORT: REFLECTIONS AND DIFFICULTIES

This paper is about integrated modelling for decision-making support to sustainability policies at local scales. By "local scales" we mean sub-national scales like cities, employment catchment areas, or slightly larger scales like départements and régions, for France. The goal of this article is to share a certain number of our motivations, outlooks and experiences we acquired via the creation of our research group, which tackles this complex topic. In a first step, we identify three scientific domains that we consider to play a key role in local scale sustainability and for which improvement in available knowledge is crucial. In a second part, we discuss challenges and difficulties one is confronted with when one wants to work on the context considered here.

Sustainability at local scale and modelling

Sustainable development is often formulated in terms of a required balance between the environmental, economic and social dimensions, but public policies addressing sustainability are in practice dominantly oriented towards environmental issues in Western countries. However, the numerous and interrelated pressures exerted by human activity on the environment make the identification of sustainable development pathways arduous in a context of complex and sometimes conflicting stakeholder and socio-ecological interactions.

The sustainability of urban areas is one of the key issues of this century. As focal points of human activity, urban areas concentrate and amplify environmental pressures in a direct or indirect way. Urbanization is a global process, with more than half the human population living in cities, an ever-increasing trend. Furthermore, urban sprawl is a ubiquitous phenomenon showing no sign of slackening yet, even in countries where rural depopulation has long been stabilized. Urban sprawl in industrialized countries is largely driven by residential peri-urban growth. This phenomenon has both social and environmental consequences, like an increased vulnerability of some population categories or a fragmentation of ecological habitat, as it implies an increase in daily mobility. In a context of high dependency on private cars and uncertainty on energy prices, this translates into an increased vulnerability of some population categories. It also induces an increase in greenhouse gas emissions, as well as an irreversible loss of crop-land and a fragmentation of ecological habitat, with negative effects on biodiversity. Controlling urban sprawl is therefore a key sustainability issue and the increasing concerns about climate change and upheaval in the market price of fossil fuels raise many questions about urban energy consumptions while reviving the debate on the desirable urban structures and their determinants.

The issues just described require a panel of policy measures at all institutional levels, as they illustrate the existence of both local-local and local-global feedback loops. The regional (sub-national) and more local levels are of particular importance for the transition to sustainability, especially in a "think global/act local" approach that is up to now mostly oriented towards local climate and territorial energy plans. In this context, more local decision levels have real political and economic leverage, and are more and more proactive on sustainability issues, either independently or in coordination through nationwide or European networks.

Advances on those problems are hampered by multiple bottlenecks of various kinds; some are social, others are economic or political (…) but a number of them are also scientific, as lack of knowledge does not allow us to understand the phenomena involved and to identify the main drivers and sources of problems, as well as appropriate leverages for public policy. Proposing reliable alternatives is a challenge in such a context. These difficulties are moreover amplified by the strong interdependence of the various dimensions of the problem. Interdisciplinary and systemic integration appears to be fundamental to make progress on sustainability issues. Modelling appears as an efficient tool to promote scientific communication and structure stakeholder interactions on sustainability issues.

The goal of this article is to share a certain number of our motivations and outlooks about integrated modelling for decision-making support to sustainability policies at local scales. In a first step, we identify three scientific domains that we consider to play a key role in local scale sustainability and for which improvement in available knowledge is crucial: urban economy, and related transportation and land use issues; material flow analysis and ecological accounting; and ecosystem services modelling. We think that these domains are basic building blocks that are indispensable in order to carry out an integrated analysis and practical courses of action on these issues. Of course, our objective here is not to list all important domains -we are far from being exhaustive -but to offer a perspective on what might be best bets for a correct identification of first steps towards an effective sustainability transition. The above three scientific domains make up the core of the research project of our group, STEEP 1 , a team of INRIA Grenoble Rhône-Alpes, and of SOCLE3 2 , an informal interdisciplinary group gathering a number of researchers covering all key fields to bring off such a project. In a second part, we discuss the challenges and difficulties one is confronted with when one wants to work on the context considered here. As an example, we also mention briefly how we manage them in our project.

Key domains in a perspective of integrated modelling at local scales

As mentioned above, three key domains have been identified; they are essential mainstays in local decision-making support based on systemic sustainability analyses. These domains are presented here, ordered from socio-economic aspects to more environmental ones.

Urban economy and integrated land use and transport modelling

Modern urban regions are highly complex entities. The understanding of the phenomena underlying urban sprawl and peri-urbanization is a key element to control the dynamics structuring urban space. Clearly, urban transport systems are intricately linked to urban structure and the distribution of activities, i.e., to land use. Urbanization generally implies an increase in travel demand. Cities have traditionally met this additional demand by expanding the transportation supply, through new highways and transit lines. In turn, an improvement of the accessibility of ever-farther land leads to an expansion of urban development, resulting in a significant feedback loop between transportation infrastructure and land use, one of the main causes of urban sprawl.

Several models have been developed in the field of urban economics to understand the complex relationship between transportation and land use and to facilitate the urban planning process [Iacono'08]. Researchers have sought to better model the functioning of cities by developing tools that can simulate the supply and demand of transport and land use, the real estate market, and the behavior of economic agents. Land use and transport integrated (LUTI) modelling provides a means to illustrate prospective exercises in urban planning. These models constitute invaluable analysis tools for planners working on transportation and urban projects. They enable the simulation of public policies and the quantification of indicators describing the evolution of urban structure. Key factors such as transport congestion, energy consumption, CO2 emissions etc., can be evaluated or estimated, and different urban development scenarios can be tested in a quantitative manner.

Yet, very few local authorities in charge of planning issues make use of these strategic models, mostly because they are difficult to calibrate and validate, two critical steps where systematic improvement would increase the level of confidence in the obtained results. These limitations prevent dissemination in local agencies. It is therefore crucial to meet the need for better calibration (estimation of model parameters based collected data) and validation strategies and algorithms.

Ecological accounting and material flow analysis

One of the major issues in the assessment of the long-term sustainability of urban areas is related to the concept of "imported sustainability". Indeed, any city brings from the outside most of its material and energy resources, and rejects to the outside the waste produced by its activity. The modern era has seen a dramatic increase in both volume and variety of these material flows and consumption as well as in distance of origin and destination of these flows, usually accompanied by a spectacular increase in the associated environmental impacts. A realistic assessment of the sustainability of urban areas requires quantifying both local and distant environmental impacts; greenhouse gas emissions are only one aspect of this question.

In order to produce such an assessment for a given territory or urban area, one must first establish different types of ecological accounting: one must identify and quantify the different types of material and energy uses on the one hand, and the different types of impact associated with these uses [Billen'08]. The first task is the object of Material Flow Analysis (MFA), while the second is more directly related to the logic of Life Cycle Analysis (LCA). One of the major challenges here is to obtain reliable MFA data at the région and département scales, either directly, or through appropriate disaggregation techniques. The MFA methodology is now quite established at the national level, but still in its infancy at the regional or urban ones. The major difficulty is that economic accounting is nearly always performed in monetary units and not physical ones, and specific databases must be created to this effect, from a number of diverse data sources. On the impact side, the major difficulty is due to the fact that quite a few of the relevant flows are difficult to track throughout the planet in the modern globalized economy, and related impacts difficult to quantify. Finally, relevant decision help tools must be constructed, for decision-makers to evaluate social/environmental trade-offs.

It is nowadays essential to progress on this theme with three major aims in mind: 1) creating comprehensive databases enabling such analyses; 2) developing methodologies and models resolving scaling issues, and developing algorithms allowing to rigorously and automatically obtain the adequate assessments (in particular through an understanding and a careful treatment of the main sources of uncertainty); 3) providing a synthetic analysis of environmental impacts associated with the major material flows, at various geographic levels (employment catchment area, département and région, for France).

Eco-system services

Long-term sustainability is closely related to the underlying ecosystems, on various fronts: production of renewable resources (either energy or biomass), waste and pollutant resorption, local and global climate regulations etc. These various functions constitute the "ecosystem services" provided to society by our natural environment [Daily'97,Kareiva'07]. The reduction of the adverse impacts of urban areas on the environment is linked not only to limiting urban sprawl and making more efficient use of the available resources, but also to developing a better grasp of the interrelations between urban/peri-urban areas and their agricultural and semi-natural surroundings. In particular, reducing distant impacts while making a better use of local resources is a major challenge for the coming decades. In this context, it is important to develop generic modelling frameworks for ecosystem services, and to study their behavior under various scenarios of coupled urban/environment evolutions.

Challenges and difficulties

The modelling envisioned in our research group aims at combining a number of different aspects of economic analyses and analyses of the environmental impact associated with urban/rural/natural areas coupled evolutions under various social and environmental drivers. The required level of systemic and interdisciplinary analysis is one of the strongest and most ambitious points of this research, but also constitutes its most challenging aspect. The first aspect of this issue relates obviously to the various backgrounds of the involved researchers. Indeed, economists specialized e.g. in territorial economics have at first little common background with experts of the impact of climate change on the migration of species, except their desire to build a common framework. In our experience, the key point is not simply to elaborate a common vocabulary, but to develop an insider's look into the internal logics of the various lines of questioning involved. This is in fact a particularly rewarding experience, both in terms of widening everyone's scope and breadth of analysis, but also in strictly practical terms; indeed, quite often in this type of interdisciplinary project, the problem is to identify the right level of complexity one must aim at to construct a modelling framework that is both informative for researchers as well as for stakeholders, and yet still manageable. The most important problem is not expertise, but integration of knowledge.

Data collection is critical for this type of research, and the relevant data are often, if not proprietary, at least confidential, and accessible only under the conclusion of confidentiality agreements with the organizations and institutions in charge of the constitution of the databases at the local level (nationwide data are in general more easily accessible, but naturally less detailed). In this respect, our project benefits in particular from its close partnership with the promoter of the ANR AETIC project3 , and from various collaborations that are now in an advanced stage of discussion, for socio-economical data collection and sharing; on another front, one of the project partners (LECA, Laboratoire d'Ecologie Alpine4 , Grenoble) in particular has a strong expertise on natural/agricultural ecosystems data collection, and numerous partnerships for access to the relevant data. Finally, data are often incomplete and inhomogeneous; also, the required amount of data depends exponentially on the number of sectors (both economic and geographic) and the dynamics of scales one wishes to model. Compromises are needed at all stages, in order to make the data as homogeneous as possible. Such constraints on the database elaboration are essential for model calibration and validation.

Let us conclude this quick overview of potential bottlenecks by briefly mentioning two important technical issues. The first one is model integration. This issue has very generic aspects, such as designing module interfaces so that the output of one module is indeed the required input of another. This may need extensive restructuring of existing modules or even modelling logic. Also, very pragmatic problems, such as interfacing models developed on different platforms, may become quite challenging in themselves. The second problem is related to the visualization of the data and of the model output, for the modellers on the one hand and for exchanges with stakeholders and policy makers on the other hand. This visualization need covers two different aspects: an explicit visualization of model results in terms of, e.g., evolution of land-use and land-cover, which can be performed in a usual way through an appropriate use of GIS (geographical information systems) techniques; and, more critically perhaps, a manageable representation of policy options in terms of policy objectives and the various social/environmental compromises entailed by these policy options. This last aspect of the problem constitutes in itself a field of research in fast expansion.

The remainder of this section is focused on some issues that are more specific to the type of modelling of interest in our research group, i.e., decision help in a sustainability perspective at the local geographic levels (from the employment catchment area to the région).

Scales

The choice of modeled scales must result from compromises between scientific questions and decision-help objectives. On the scientific side, first, the scales one needs to model vary with the question one wants to address. For example, in urban planning issues, both in terms of housing tract planning or transportation infrastructure, the relevant modelling scales are defined by the most important (in numbers as well as traveled distance) commuting trips. This point has long been recognized by local planning agencies, which now consider urban planning at the level of a communauté de commune or more recently, Schémas de Cohérence Territoriaux (SCoT). This scale is adapted, but its administrative boundary, which results from discussions and negotiations, may not reflect the logic of transportation problems. Also, in practice, it usually includes many other considerations. For the analysis of impacts associated with material and energy flows, French régions are probably best adapted, in particular in a logic of relocalization of economic activities in a context of increasing energy prices and desired reduction of GHG emissions. On the other end of the spectrum, ecosystem services analysis often requires modelling at very fine scales, in order to analyze, e.g., species habitat fragmentation and connectivity. In practice, the approach that has been adopted in our project is to study some well-defined and limited areas at very fine scales, and characterize these services at larger scales in a coarser way.

On the public policy side, two questions arise: identifying correctly what elected representatives and agencies may do, and what they actually can do; the difference between the two arises from the fact that on the one hand they may not realize that they actually possess some leverages on various problems, and on the other because some of their actual official domains of action may be impeded by various extraneous considerations (some of them briefly mentioned in the next paragraph). Finally, the relevant political leverage may not exist at the scale where the problem arises, as the "subsidiary principle" is still far from being efficiently applied at all decision levels in Europe and in France.

Model complexity and modularity, and decision-help

In all such modelling efforts, one must bear in mind that political decisions must often, if not always, be reached in the absence of complete scientific, social, and economic information on the problems at hand. On the one hand, the political time scale, like it or not, is not the time scale of research; on the other hand, asking for more scientific information is more often than not a way to maintain the existing status quo and gain time.

In this context, a balance between strictly scientific objectives and the final aim of public policy decision help must be found: a too elaborate model will be unusable in practice by stakeholders and policy-makers, especially that their dashboards are often very limited and qualitative. Furthermore, stakeholder interests and sometimes conflicting lobbying (even at the most local levels) often weighs more than providing correct and relevant scientific information. In this context, even perfect knowledge of the scientific determinants of the problems to be addressed at the political level is no guarantee that problems are correctly anticipated and possible win-win lines of actions identified and implemented.

In this respect, the elaboration of multi-criteria and multi-stakeholders decision procedures is of paramount importance, and must be developed in parallel with more strictly scientific lines of questioning. An expert in these issues is involved in our group for these reasons, and this aspect of the question requires fostering interactions with local stakeholders and decision-help agencies right from the start of the intended research project. More generally, implication of stakeholders, in particular of decision-makers and institutional actors, is required for a correct upstream focus of some of the project's objectives and downstream use of its results. This makes model modularity a critical feature in order to address different and possibly conflicting stakeholder preoccupations. In all cases, the model inputs and outputs must be largely simplified in discussions with stakeholders and policy makers. It is the role of the multi-criteria decision-help experts to establish the right level of simplification in coordination with stakeholders on the one hand, and the scientific experts on the other, and to "fill in" the gaps if necessary. The question of the visualization of the model and of the various policy options is particularly critical as well.

A challenging framework for modelling science

Before describing some key challenges more specific to modelling aspects, we provide a brief overview of the types of models already developed in those fields.

As for LUTI (Land Use and Transportation Integrated) modelling, we can cite the TRANUS model (one of the most widely used LUTI models), which has been developed since 1982 by the company Modelistica5 , and is distributed via Open Source software. TRANUS proceeds by solving a system of deterministic nonlinear equations and inequalities containing a number of economic parameters (e.g. demand elasticity parameters, location dispersion parameters, etc.). The solution of such a system represents an economic equilibrium between supply and demand. A second popular LUTI model is UrbanSim6 . Whereas TRANUS aggregates over e.g. entire population or housing categories, UrbanSim takes a micro-simulation approach, modelling and simulating choices made at the level of individual households, businesses, and jobs, for instance, and it operates on a finer geographic scale than TRANUS.

The scientific domains related to eco-system services and ecological accounting, are much less mature than the one of urban economy and LUTI modelling. Nowadays, the community working on ecological accounting and material flow analysis only proposes statistical models based on more or less simple data correlations. The ecosystem services community has been using statistical models too, but is also developing more sophisticated models based for example on system dynamics, multiagent type simulations or cellular models. Here, we can cite for example the widely used land cover model CLUE-S7 which belongs to the last category. Now, let us focus on three key challenges more directly related to modelling issues.

Model calibration and validation

The overall calibration of the parameters that drive the equations implemented in the above models is a vital step. Theoretically, as the implemented equations describe e.g. socio-economic phenomena, some of these parameters should in principle be accurately estimated from past data using econometrics and statistical methods like regressions or maximum likelihood estimates, e.g. for the parameters of logit models describing the residential choices of households. However, this theoretical consideration is often not efficient in practice for at least two main reasons. First, the above models consist of several interacting modules. Currently, these modules are typically calibrated independently; this is clearly sub-optimal as results will differ from those obtained after a global calibration of the interaction system, which is the actual final objective of a calibration procedure. Second, the lack of data is an inherent problem.

As a consequence, models are usually calibrated by hand. The calibration can typically take up to 6 months for a medium size LUTI model (about 100 geographic zones, about 10 sectors including economic sectors, population and employment categories). This clearly emphasizes the need to further investigate and at least semiautomate the calibration process. Yet, in all domains mentioned above, very few studies have addressed this central issue, not to mention calibration under uncertainty which has largely been ignored (with the exception of a few uncertainty propagation analyses reported in the literature).

Here the challenges are related to two major issues connected with calibration and validation of models: (a) defining a calibration methodology and developing relevant and efficient algorithms to facilitate the parameter estimation of considered models [Nocedal'99,Conn'09]; (b) defining a validation methodology and developing the related algorithms (this is complemented by sensitivity analysis, see the following paragraph). In both cases, analyzing the uncertainty that may arise either from the data or the underlying equations, and quantifying how these uncertainties propagate in the model, are of major importance.

Sensitivity analysis

A sensitivity analysis (SA) consists, in a nutshell, in studying how the uncertainty in the output of a model can be apportioned to different sources of uncertainty in the model inputs [Saltelli'08]. It is complementary to an uncertainty analysis, which focuses on quantifying uncertainty in model output. SA's can be useful for several purposes, such as guiding model development and identifying the most influential model parameters and critical data items. Identifying influential model parameters may help in devising meta-models (or, surrogate models) that approximate an original model and may be simulated, calibrated, or analyzed more efficiently. As for detecting critical data items, this may indicate for which type of data more effort must be spent in the data collection process in order to eventually improve the model's reliability. Finally, SA can be used as one means for validating models, together with validation based on historical data (or, put simply, using training and test data) and validation of model parameters and outputs by experts in the respective application area.

The first two applications of SA are linked to model calibration, discussed in the previous section. Indeed, prior to the development of the calibration tools, one important step is to select the significant or sensitive parameters and to evaluate the robustness of the calibration results with respect to data noise (stability studies). This may be performed through a global sensitivity analysis, e.g. by computation of Sobol's indices. Many problems will have to be circumvented e.g. difficulties arising from dependencies of input variables, variables that obey a spatial organization, or switch inputs.

As for the third application of SA, model validation, a preliminary task bears on the propagation of uncertainties. Identifying the sources of uncertainties and their nature is crucial to propagate them via Monte Carlo techniques. To make a Monte Carlo approach computationally feasible, it is necessary to develop specific meta-models. Both the identification of the uncertainties and their propagation require a detailed knowledge of the data collection process; these are mandatory steps before a validation procedure based on SA can be implemented.

Modelling of socio-economic and environmental interactions

Considering the assessment of socio-economic impacts on the environment and ecosystem service analysis, the problems encountered here are intrinsically interdisciplinary: they draw on social sciences, ecology or Earth sciences. The modelling of the considered phenomena must take into account many factors of different nature which interact via various functional relationships. These heterogeneous dynamics are a priori nonlinear and complex: they may have saturation mechanisms, threshold effects, and may be density dependent. The difficulties are compounded by the strong interconnections of the system (presence of important feedback loops) and multi-scale spatial interactions. The spatial processes involve proximity relationships and neighborhoods, like for example, between two adjacent parcels of land. The multi-scale issues are due to the simultaneous consideration in the modelling, of actors of different types and that operate at specific scales (spatial and temporal). For example, to properly address biodiversity issues, the scale at which we must consider the evolution of rurality is probably very different from the one at which we model the biological phenomena. Multi-scale approaches can also be justified by the lack of data at the relevant scales. This is for example the case for the material flow analysis at local scales for which complex data disaggregations are required.

At this stage, it is crucial to understand that the scientific fields considered here are far from being mature. For example, the very notions of ecosystem services or local ecological accounting are quite recent and at best partially documented, but advances in those fields are essential, and will be required to identify transition paths to sustainability. Nowadays, the analyses are only qualitative or statistic. The phenomena are little understood. It is then crucial here to do upstream research. It is to anticipate and to help the development of modelling tools that will be used tomorrow in these fields.

Developing flexible integrated systemic models (upgradable, modular…) which are efficient, realistic and easy to use (for developers, modelers and end users) is a challenge in itself. What mathematical representations and what computational tools to use; cellular automata, multi-agent models, system dynamics, or large systems of equations describing equilibrium models? Is it necessary to invent other representations? What is the relevant level of modularity? How to get very modular models while keeping them very coherent and easy to calibrate? Is it preferable to use the same modelling tools for the whole system, or can we freely change the representation for each considered subsystem? How to easily and effectively manage different scales? How to get models which automatically adapt to the granularity of the data and which are always numerically stable? How to develop models that can be calibrated with reasonable efforts, consistent with the (human and material) resources of the agencies and consulting firms that use them?

Conclusion

In this article we have shared a certain number of our motivations and outlooks about integrated modelling for decision-making support to sustainability policies at local scales. We have identified three scientific domains that play a key role in local scale sustainability and for which improvement in available knowledge is crucial and urgent: urban economy (and related transportation and land use issues), material flow analysis and ecosystem services modelling. Then, we have discussed challenges and difficulties one is confronted with when tackling these problems. The difficulties are multiple and of various types. Some of them are related to the very nature of the problem (interdisciplinary, scale delimitation) and require carrying out this exercise with a very specific state of mind (integration of knowledge being by certain aspects more problematic than expertise; interactions with stakeholders and decision-makers). Some of the difficulties are technical and even pragmatic (data, visualization, model interfacing). Finally, this problem also offers a very challenging framework for the modelling sciences, including applied mathematics and computer science. Model calibration and validation, as well as sensitivity analysis have largely been ignored until now, when they are really critical in this context. They are also extremely arduous and complex. In other respects, developing flexible integrated systemic models which are efficient, realistic and easy to use is a challenge in itself.

http://steep.inrialpes.fr/

http://socle3.obs.ujf-grenoble.fr/

http://projet-aetic.upmf-grenoble.fr/

http://www-leca.ujf-grenoble.fr/

http://www.modelistica.com/english

http://www.urbansim.org

http://www.ivm.vu.nl/en/Organisation/departments/spatial-analysis-decision-support/Clue

Acknowledgments

The authors would like to thanks all the members and partners of STEEP and the SOCLE3 group, in particular Patrick Criqui, Denis Dupré, Sandra Lavorel, Clémentine Prieur, Arthur Vidard, Benoit Lefèvre, Tomás de la Barra, Mathieu Saujot, Antoine Rolland, Patrick Bonnel and François Mancebo. This work is supported by the FRB (Fondation pour la Recherche sur la Biodiversité) and ONEMA via the ESNET project and by ANR ("Numerical Model" program, 2012) via the CITiES project.