Marc Plantevit
email: plantevi@lirmm.fr

Anne Laurent
email: laurent@lirmm.fr

Maguelonne Teisseire
email: teisseire@lirmm.fr

OLAP-Sequential Mining: Summarizing Trends from Historical Multidimensional Data using Closed Multidimensional Sequential Patterns

Keywords: data mining, datawarehouses, closed multidimensional sequential patterns

published or not. The documents may come

Introduction

Data warehouses are now well spread over companies. They contain valuable information that can easily be queried and visualized with the OLAP tools, provided the fact that the user is able to design on-line his own queries. However, it is still challenging to provide the user with tools that can automatically extract relevant knowledge from such huge amounts of data. Data warehouses are indeed different from usually mined databases as they contain aggregated data, described by means of several dimensions that can possibly be organized through hierarchies. In this paper, we thus try and extend existing methods that are now recognized for mining classical databases to this framework. As data are historized, we argue that sequential patterns are well-suited to this task. Sequential patterns have been studied for more than ten years [START_REF] Agrawal | Mining sequential patterns[END_REF], with a lot of research and industrial applications (e.g. user behavior, web log analysis, discovery of patterns from proteins' sequences, security and music). Algorithms have been proposed, based on the APriori-based framework [START_REF] Javeed | Spade: An efficient algorithm for mining frequent sequences[END_REF], [START_REF] Masseglia | The PSP Approach for Mining Sequential Patterns[END_REF] , [START_REF] Ayres | Sequential pattern mining using a bitmap representation[END_REF], or on other approaches [START_REF] Pei | Mining sequential patterns by pattern-growth: The prefixspan approach[END_REF], [START_REF] Han | Mining frequent patterns without candidate generation[END_REF]. Sequential patterns have recently been extended to multidimensional sequential patterns by [START_REF] Pinto | Multidimensional sequential pattern mining[END_REF], [START_REF] Plantevit | M 2 sp: Mining sequential patterns among several dimensions[END_REF], and [START_REF] Yu | Mining sequential patterns from multidimensional sequence data[END_REF]. They aim at discovering patterns that take time into account and that involve several dimensions. For instance in [START_REF] Plantevit | M 2 sp: Mining sequential patterns among several dimensions[END_REF], rules like A customer who bought a surfboard together with a bag in NY later bought a wetsuit in SF are discovered. Note that such sequences can also contain a wild-card item * instead of a dimension value. For instance, considering the previous example, if there is no frequent pattern in the database describing the fact that wetsuits were later bought in SF, or NY etc, but there are numerous wetsuits bought whatever the city, then the rule A customer who bought a surfboard together with a bag in NY later bought a wetsuit will be mined, represented as (surfboard , NY )(wetsuit , * ) .

Sequential patterns are usually extracted from the simple schema: (e.g. products, customer id and date) but the number of mined patterns can be very huge. This is why condensed representations were proposed for the itemset framework ( [START_REF] Pasquier | Discovering frequent closed itemsets for association rules[END_REF], [START_REF] Pei | Closet: An efficient algorithm for mining frequent closed itemsets[END_REF], [START_REF] Javeed | Charm: An efficient algorithm for closed itemset mining[END_REF], [START_REF] El | Finding all frequent patterns starting from the closure[END_REF]) and for sequential patterns ( [START_REF] Yan | Clospan: Mining closed sequential patterns in large databases[END_REF], [START_REF] Wang | Frequent closed sequence mining without candidate maintenance[END_REF]). In both cases, the approaches allow a condensed representation and a pruning strategy in the search space.

However, these works are not suitable for multidimensional sequential patterns because they only consider a particular case for candidate generation. In our context, a super-sequence may indeed result from several cases (1) a longer sequence (more items) or (2) a more general sequence based on the relation between dimension values and the wild-card value * (more general items).

The main contributions of this paper are a theoretical framework for mining closed multidimensional sequential patterns and some algorithms called CMSP (Closed Multidimensional Sequential Pattern mining) to mine such patterns. When considering multidimensional data, the number of possible patterns is combinatorially explosive and the generate-and-prune methods are no more scalable for long sequences, as highlighted in [START_REF] Pei | Pattern-growth Methods for Frequent Pattern Mining[END_REF], [START_REF] Rassi | Deducing bounds on the support of sequential patterns[END_REF]. This is why we adopt the pattern growth paradigm ( [START_REF] Pei | Mining sequential patterns by pattern-growth: The prefixspan approach[END_REF]) to propose a greedy approach for mining frequent sequences without candidate generation.

The paper is organized as follows. First we recall the related work in Section 2 and we detail why existing works are not suitable for mining data warehouse. Then we present the core of our proposition: the definitions are introduced in Section 3 while the CM SP algorithms are detailed in Section 4. Experiments on synthetic and real data, reported in Section 5, show that our method performs well both on runtime and number of extracted closed sequences. Finally, we provide some concluding remarks and suggestions for future work in Section 6.

Related Work

In this Section, we first recall from [START_REF] Plantevit | M 2 sp: Mining sequential patterns among several dimensions[END_REF] the seminal definitions of multidimensional sequential patterns. Then we present existing works from the literature on closed patterns.

Multidimensional Sequential Patterns

To the best of our knowledge, three proposals exist for mining sequential patterns when considering several dimensions.

The approach proposed by [START_REF] Pinto | Multidimensional sequential pattern mining[END_REF] mines sequences over one single dimension (e.g. product) labeled by multidimensional patterns. However, no combination of dimensions is possible through time (within the sequence).

[22] is very particular since the dimensions are embedded one within the other one (web pages are visited within one session during one day).

In [START_REF] Plantevit | M 2 sp: Mining sequential patterns among several dimensions[END_REF], rules not only combine several dimensions but they also combine these dimensions over time. For instance in the rule A customer who bought a surfboard together with a bag in NY later bought a wetsuit in SF, N Y appears before SF , and surf board appears before wetsuit.

As the last approach is more general than the other two ones, we focus here on the concepts of multidimensional sequential patterns introduced in [START_REF] Plantevit | M 2 sp: Mining sequential patterns among several dimensions[END_REF].

More formally, let us consider a database DB where data are described with respect to n dimensions. We consider a 3-bin partitioning of the dimensions:

-the set of those dimensions that will be contained within the rules (analysis dimensions) is denoted by D A ; -the set of those dimensions on which the counting will be based (reference dimensions) is denoted by D R ; -the set of those dimensions that are meant to introduce an order between events (e.g. time) is denoted by D T .

The database can then be partitioned into blocks defined by their positions on the reference dimensions.

A multidimensional item e is a m-tuple defined over the set of the m D A dimensions. We consider e = (d 1 , d 2 , . . . , dm) where d i ∈ Dom(D i ) ∪ { * }, ∀D i ∈ D A and where * stands for the wild-card value. For instance, (1, 2) is a multidimensional item defined with respect to two dimensions. A multidimensional itemset i = {e 1 , . . . , e k } is a non-empty set of multidimensional items. All items of the itemset have to be "incomparable" to preserve the notion of set. For instance, {(1, 1), (1, 2)} is a multidimensional itemset whereas {(1, 1)(1, * )} is not an itemset because (1, 1) ⊆ (1, * ). A multidimensional sequence ς = i 1 , . . . , i l is a non-empty ordered list of multidimensional itemsets. For instance, ς 1 = {(1, 1), (1, 2)}{(1, * ), ( * , 4)}{(1, 3)} is a multidimensional sequence. Sequences that contain k items and g itemsets are called g-k-sequences: Definition 1 (g-k-Sequence) A g-k-sequence S is a sequence that is composed of g itemsets and k items as following: S = {e 1 1 , e

(k i ) = k.
A multidimensional sequence can be included into another one:

Definition 2 (Sequence inclusion) A multidimensional sequence ς = a 1 , . . . , a l is said to be a subsequence of ς ′ = b 1 , . . . , b l ′ if there exist integers 1 ≤ j 1 ≤ j 2 ≤ . . . ≤ j l ≤ l ′ such that a 1 ⊆ b j1 , a 2 ⊆ b j2 , . . . , a l ⊆ b j l .
For instance, the sequence {(1, 2), ( * , 3)}{(2, 2)} is a subsequence of the sequence {(1, * ), ( * , 3)}{( * , 2)( * , 3)} .

We consider that each block defined over D R contains one multidimensional data sequence, which is thus identified by that block. A block supports a sequence ς if all items of ς can be matched (each value on each analysis dimension has to be matched except with wild-card value *) with an item of the data sequence with respect to time order. Thus, the support of a multidimensional sequence is the number of those blocks defined over D R which contain this sequence. When considering the classical case of sequential patterns, the sets of analysis, reference, and order dimensions consist of only one dimension (usually the product, customer id and time dimensions). Note that even in this classical case, the number of frequent sequential patterns discovered from a database can be huge. And this problem becomes worse in the case of multidimensional patterns since multidimensional framework produces more patterns than classical framework.

For this reason, it is necessary to study condensed representations. We aim at representing the sequential patterns and their support. Thus, we do not consider the solution of representing only maximal sequential patterns, since this would result in the loss of the information about the support of subsequences.

In this paper, we consider closed patterns. They indeed allow to represent the patterns in a compressed manner without any loss of information.

Closed Patterns

A major challenge in mining frequent patterns is the fact that such mining often generates a huge number of patterns satisfying the minimum support threshold. This is because if a pattern is frequent, each of its subpatterns is also frequent. A pattern will contain an exponential number of smaller subpatterns. To overcome this problem, closed frequent pattern mining were proposed by [START_REF] Pasquier | Discovering frequent closed itemsets for association rules[END_REF]. Frequent closed patterns algorithms, which heavily draw on Formal Concept Analysis (FCA) mathematical settings [START_REF] Ganter | Applied lattice theory: Formal concept analysis[END_REF][START_REF] Sadok Ben Yahia | Frequent closed itemset based algorithms: a thorough structural and analytical survey[END_REF], present a novel alternative with a clear promise to dramatically reduce, without information loss, the size of the frequent pattern set. From the frequent closed patterns, the support of frequent non-closed patterns can be inferred.

Based on the previous approaches [START_REF] El | Finding all frequent patterns starting from the closure[END_REF], [START_REF] Pasquier | Discovering frequent closed itemsets for association rules[END_REF], [START_REF] Pei | Closet: An efficient algorithm for mining frequent closed itemsets[END_REF], [START_REF] Javeed | Charm: An efficient algorithm for closed itemset mining[END_REF], a closed pattern is defined as follows:

Definition 3 (Closed Pattern) A (sequential) pattern α is closed if there does not exist any pattern β such that α ⊆ β and support(α) = support(β).

For instance, let us suppose that the sequences a 3 and a, b, c 2 are closed, where a 3 stands for the sequence a having support 3. Then it can be deduced that the sequences a, c and b, c , which are included in the previous ones, have support 2. If their support was 3 then the sequence a would not be closed. Thus, their frequency is directly correlated to the frequency of a, b, c . All the sequences are shown in Figure 1 where the closed sequences are circled.

It should be noticed that many works have been done on the extraction of closed itemsets [START_REF] El | Finding all frequent patterns starting from the closure[END_REF][START_REF] Pei | Closet: An efficient algorithm for mining frequent closed itemsets[END_REF][START_REF] Javeed | Charm: An efficient algorithm for closed itemset mining[END_REF][START_REF] Wang | Closet+: searching for the best strategies for mining frequent closed itemsets[END_REF] but only two approaches have been proposed for sequential closed patterns: BIDE and CloSpan.

CloSpan [START_REF] Yan | Clospan: Mining closed sequential patterns in large databases[END_REF] first extracts a set of closed sequence candidates, which contains the set of frequent sequences. In this first set, some sequences are not closed. Thus, CloSpan prunes the non-closed sequences in a second step. CloSpan uses the patterngrowth approach, which is different from the APriori-like candidate-generation-andtest approaches. CloSpan decomposes the database in order to discard non-needed computations [START_REF] Pei | Pattern-growth Methods for Frequent Pattern Mining[END_REF]. In order to reduce the space search, the database is projected by the current mined sequence also called prefix sequence. The projected database according to the sequence α is denoted DB|α. For instance, given the data sequence S = (abcd)ea(bc)(ac) and α = (ab)a , S|α = (bc)(ac) . As soon as a sub-pattern or a superpattern of the current sequence shares the same projected database as the current one, we do not need to explore this database in order to grow this sequence. Indeed, their subtrees can be merged into one without having to mine a subtree in the search space already mined.

BIDE [START_REF] Wang | Frequent closed sequence mining without candidate maintenance[END_REF] enhances the previous approach (CloSpan). The authors propose an approach without any candidate maintenance-and-test paradigm. This approach prunes the search space more deeply. It checks a pattern closure in a more efficient way while consuming less memory than CloSpan. Indeed, BIDE does not maintain the set of historic closed patterns.

It should be noted that these two approaches not only reduce the number of sequences to be considered, but also result in better performances (both in time and memory).

We can also cite the work of [START_REF] Songram | Closed multidimensional sequential pattern mining[END_REF] which considers closed sequential patterns in multidimensional framework. However, this approach uses a condensed representation of [START_REF] Pinto | Multidimensional sequential pattern mining[END_REF]. So this approach mines sequences over one single dimension (e.g. product) labeled by multidimensional patterns. Thus, no combination of dimensions is possible through time (within the sequence).

OLAP Mining has been studied since 1997 [START_REF] Han | OLAP mining: Integration of OLAP with data mining[END_REF], aiming at designing methods to automatically extract relevant knowledge from multidimensional databases. In this framework, the challenges are numerous, as this kind of data is different from classical databases that are usually mined. First, multidimensional databases contain aggregated data. Moreover, this data is described using dimensions, which can be organized through hierarchies. Finally, the data is historized so as to report the evolution through time. Discovering trends from such data can thus be seen as the task of extracting the relevant frequent sequences that occur. This is the reason why we choose here to study sequential patterns, as efficient methods have been designed to extract such trends, while remaining scalable (typically by using algorithms that do not have to manage sets of candidates) and concise (typically by using closed sequential patterns). However to the best of our knowledge, multidimensional sequential patterns have not been con-sidered in the existing work. So, we propose a theoretical framework for mining closed multidimensional sequential patterns.

Particularity of the Multidimensional Framework

In this section, we explain why it is quite difficult to apply existing work on sequential pattern to the multidimensional framework. These reasons are essentially due to the inclusion of wild-carded -sequences.

Unfortunately, the classical framework (one analysis dimension) is no longer suitable when considering wild-carded multidimensional sequential patterns. For instance, if we assume that {(a 1 , b 1 ), ( * , b 2 )} 2 is closed, then by calculating the other sequences, it could be calculated that the sequences {(a 1 , b 1 ), (a 1 , b 2 )} and {(a 1 , b 1 ), (a 2 , b 2 )} are in the same case as previously (support should be 2). However, it may happen that the sequences {(a 1 , b 1 ), (a 1 , b 2 )} and {(a 1 , b 1 ), (a 2 , b 2 )} have a support of 1. This may occur because a super-sequence may result from several cases: a longer sequence (more items) or a more general sequence based on the relation between dimension values and the wild-card (more general items). More precisely, it is due to the fact that all values of domain dimensions are contained in wild-card.

CMSP -Closed Multidimensional Sequential Patterns

In order to define Closed Multidimensional Sequential Patterns, we introduce a specialization relation between patterns to catch the specific context of the multidimensional data.

Definition 4 (Specialization/Generalization) A multidimensional sequential pattern α = a 1 , . . . , a l is more general than β = b 1 , . . . , b l ′ (l ≤ l ′ ) (and β is more specific than α) if there exist integers

1 ≤ j 1 ≤ j 2 ≤ . . . ≤ j l ≤ l ′ such that b j1 ⊆ a 1 , b j2 ⊆ a 2 , . . . , b j l ⊆ a l .
If β is more specific than α, we write α ⊂ S β where ⊂ S denotes a specialization relation.

Example 1

The sequence β = {(a 1 , b 1 ), (a 2 , b 2 )}{( * , b 1 )} is more specific than the sequence α = {(a 1 , * ), (a 2 , b 2 )} . We denote α ⊂ S β. We can note that this definition is different from the inclusion definition (definition 2). Here, the main idea is that a sequence is more specific than another one if it is at least longer than the other one and its items should be more specific. For instance, (1, * ) ⊂ S (1, 1), [START_REF] Agrawal | Mining sequential patterns[END_REF][START_REF] Agrawal | Mining sequential patterns[END_REF] and

(1, * ) (1, 1), (1, 1) .

We can now define closed multidimensional sequence and closed multidimensional sequential patterns as follows:

Definition 5 (Closed Multidimensional Sequence) A multidimensional sequence α is closed if there does not exist β such that α ⊂ S β and support(α) = support(β) Definition 6 (Closed Multidimensional Sequential Pattern) Let minsup be a minimal support threshold, a sequence s is a closed multidimensional sequential pattern if s is closed and support(s) ≥ minsup.

Example 2 (Closed Multidimensional Sequential Patterns and Inference)

With a minimal support threshold equal to 3 and the database shown in Table 1, the set of closed patterns is given by the first part of Table 2.

With a minimal support threshold equal to 2, the set of closed sequential patterns is given by Table 2. Unclosed sequences can be inferred from the closed ones. For instance, the support of the sequences ( * , b 2 ) and (a 2 , * ) can then be computed as being equal to 3. Thus, two levels of knowledge can be inferred from closed patterns:

1. for subsequences containing fewer items; 2. for subsequences containing more general items (more wildcards).

These two levels can be mixed in order to infer even more general knowledge.

1 {(a 1 , b 1 ), (a 1 , b 2 )}{(a 2 , b 2 )}{(a 1 , b 3 )}{(a 1 , b 2 )(a 2 , b 2 )} 2 {(a 1 , b 2 ), (a 2 , b 1 )}{(a 3 , b 2 )}{(a 2 , b 1 )}{(a 2 , b 1 )} 3 {(a 4 , b 4 )}{(a 2 , b 1 )}{(a 1 , b 1 )(a 2 , b 2 ))} Table 1 Running Example (a 1 , * ) 3 (a 2 , * ), (a 2 , * ) 3 (a 2 , * ), ( * , b 2 ) 3 ( * , b 1 ), (a 2 , * ) 3 ( * , b 2 ), ( * , b 2 ) 3 {(a 1 , b 1 ), ( * , b 2 )} 2 {(a 1 , b 2 ), ( * , b 1 )}, (a 2 , * ), (a 2 , * ) 2 {(a 1 , b 2 ), ( * , b 1 )}( * , b 2 ), (a 2 , * ) 2 (a 2 , b 1 ), (a 2 , * ) 2 (a 2 , b 1 ), ( * , b 1 ) 2 (a 2 , b 1 ), ( * , b 2 ) 2 (a 2 , * ), (2, 2) 2 (a 2 , * ), (1, * ) 2 ( * , b 1 ), (a 2 , b 2 ) 2 ( * , b 1 ), (a 1 , * ) 2
Table 2 Closed multidimensional sequences with support 2 and 3

CM SP : Mining Closed Multidimensional Sequential Patterns

As mentioned in the introduction, generate-and-prune methods cannot be scalable for long sequences. This non-scalability problem is worse in a multidimensional framework since the number of possible patterns is combinatorially explosive.Thus, we adopt the pattern-growth paradigm in order to define complete and scalable algorithms for mining multidimensional closed sequential patterns. The definitions we consider here are taken from the approaches that are recognized as being efficient for mining for sequential patterns. The first approach is described in Section 4.2. It considers the methods defined in CloSpan [START_REF] Yan | Clospan: Mining closed sequential patterns in large databases[END_REF]. The second approach we consider here is based on Bide [START_REF] Wang | Frequent closed sequence mining without candidate maintenance[END_REF] described in Section 4.3. In this approach, no candidate set is maintained.

We define below the definitions that are common to these two approaches, and we then detail on each of them the implementation we propose. Experimental results are reported in Section 5.

Order Within The Itemset of a Sequence

Ordering items within the itemsets is one of the main basis to improve the implementation and to discard already examined cases. The existing methods presented in [START_REF] Yan | Clospan: Mining closed sequential patterns in large databases[END_REF] and [START_REF] Wang | Frequent closed sequence mining without candidate maintenance[END_REF] for ordering sequences are not directly applicable to the multidimensional framework. Indeed wild-carded items are not explicitly present in databases. Such items are retrieved by inference since there is no associated tuple in the database.

1 {(a 1 , b 1 ), (a 1 , b 2 )} 2 {(a 1 , b 2 ), (a 2 , b 1 )} Table 3
Where is the sequence {(a 1 , b 2 ), ( * , b 1 )} ? Table 3 shows an example of a database that cannot be treated by these two methods, since wild-carded items are not explicitly present in the database. Thus, no total lexicographic order can be defined between the elements of the itemsets. So these methods cannot mine the sequence {(a 1 , b 2 ), ( * , b 1 )} . As an example, CloSpan finds the frequent item (a 1 , b 2 ) with a support of 2 and then, it constructs the projected database prefixed by the sequence {(a 1 , b 2 )} . This projected database contains the sequences {} and {(a 2 , b 1 )} . Thus the item ( * , b 1 ) does not appear to be frequent in this projected database whereas it is frequent in the initial database.

This trivial example highlights the need to introduce a lexical order taking wildcarded items into account.

It should be noted that it is not possible to extend the whole database with all the possible wild-carded items before the mining process. For example, if we consider a database containing m analysis dimensions and n i items in an itemset i, this transformation would produce (2 m -1) × n i items instead of n i leading to a database of size (2 m -1) P ti∈DB n ti . It is then necessary to take all wild-carded items into account during the process of closed multidimensional sequential patterns and not before as a pre-treatment.

We will then introduce an lexical order and functions to locally materialize the wild-carded items.

It is necessary to have a lexicographic order when mining frequent patterns since it is the basis foundation of the non-duplication of items during the computation. We now define the concept of extended itemset.

Definition 7 (Extended Itemset) A frequent itemset is said to be extended if it is equal to its downward closure according to the specialization relation (⊂ S ).

The extended itemsets enable to mine wild-carded items which can be deduced from data sequences.

In order to optimize the computation of closed multidimensional sequential patterns, we introduce a lexico-graphico-specific (LGS) order. This order results from an alpha-numerical order according to the precision of the items (number of * in the item). Thus the priority is given to the most specific items during the mining process. For instance, itemset i 1 = {(a 1 , b 1 ), (a 2 , b 1 ), (a 1 , * ), (a 2 , * ), ( * , b 1 )} is sorted w.r.t LGS order.

We define a function which transforms an itemset (transaction) into its extended itemset.

Definition 8 (Function LGS-Closure) LGS-Closure is an application from an itemset i to the closure of i w.r.t. the LGS order < lgs .

Example 3 (LGS-Closure) LGS-Closure({(a 1 , b 1 ), (a 2 , b 1 )}) = {(a 1 , b 1 ), (a 2 , b 1 ),- (a 1 , * ), (a 2 , * ), ( * , b 1 )}
This closure is illustrated in the Figure 5. Note that we do not return the most general item (*,*) of the lattice . This item does not need to be mined since it is a tautology.

Fig. 2 LGS-Closure

The extraction of frequent items is then performed on each extended itemset. In the pattern-growth approach, the sequences are greedily extracted by adding a frequent item to a frequent prefix sequence. The prefix sequence can be extended by adding a frequent item in a new itemset or by adding a frequent item in the last itemset of the prefix sequence. It is thus necessary to define an efficient way to extend a prefix sequence according to its last itemset. Furthermore, we have to preserve the notion of set of an itemset (two comparable items cannot appear together within an itemset). For that purpose, we define a restriction as follows.

Definition 9 (Function LGS-Closure X ) The function LGS-Closure X (i) in an application from an itemset i to the closure of i taking filtering of the itemset X = {x 1 ≤ lgs . . . ≤ lgs x k ′ } into account such that:

LGS-Closure X (i) = {e ∈ LGS-Closure(i) s.t. e ≥ lgs x k ′ and ∄x j ∈ X | x j ⊆ e} Example 4 (LGS-Closure X ) LGS-Closure {(a1,b1)} ({(a 1 , b 1 ), (a 1 , b 2 ), (a 1 , b 3 )}) = {( * , b 2 ), ( * , b 3 )} 4.

CM SP Cand

In this section, we define an algorithm adapted from CloSpan.

Closed sequential patterns are extracted using algorithms 1 (CM SP Cand) and 2 (SequenceGrowing) following a depth-first strategy.

Instead of scanning the whole database level by level in the same way as APriori-like methods, the database is projected according to the current examined prefix sequence. This projection is quite different from [START_REF] Pei | Mining sequential patterns by pattern-growth: The prefixspan approach[END_REF]. Since we should take into account wildcarded items, the database projection should take into account the transaction (itemset of the block data sequence) where item was found, and not only the item itself like in [START_REF] Pei | Mining sequential patterns by pattern-growth: The prefixspan approach[END_REF]. To take into account this transaction, we use the LGS-Closure function by filtering the already found items.

For instance, if we consider the following data sequence S = (1, 1), {(1, 2), (1, 3)}, (2, 2) and the current prefix sequence α = (1, 2) . According to [START_REF] Pei | Mining sequential patterns by pattern-growth: The prefixspan approach[END_REF], the projected database S|α = { (1, 3)}, [START_REF] Ayres | Sequential pattern mining using a bitmap representation[END_REF][START_REF] Ayres | Sequential pattern mining using a bitmap representation[END_REF] where [START_REF] Agrawal | Mining sequential patterns[END_REF][START_REF] Boulicaut | Free-sets: A condensed representation of boolean data for the approximation of frequency queries[END_REF] indicates that the item (1, 3) and the last itemset of α shares the same itemset in the data sequence. With our algorithm, the projected database is quite different since we take into account wild-card values. The projected database is built as follows:

S|α = LGS-Closure {(1,2)} ({(1, 2)(1, 3)}), {(2, 2)}, thus we have: S|α = { (1, 3) (1, * ) ( * , 3)}, {(2, 2)}.
The use of projected database prevents from scanning already seen data. Indeed, if we consider a frequent sequence α and the current examined prefix sequence β such that β ⊆ S α or α ⊆ S β and such that the projected database is the same for β and α, then it is not necessary to expand this last sequence. We just need to copy the subtree (already mined) of the sequence α to the sequence β.

We can note that:

-if α ⊆ S β then α cannot be closed; -if β ⊆ S α then the sequences prefixed by β are already known, thus allowing us to discard the frequent suffixes of β.

In the latter case, it should be noted that β cannot be closed. However, it is necessary to keep this sequence as it can be included in some other ones, thus avoiding database scans.

Algorithm 3 considers locally frequent items from projected fragments of the database. It is based on the LGS-Closure function (definition 9). The projected database is scanned only once in order to extract all frequent items. Two types of items can be mined:

1. The items which cannot be included in the last itemset of the prefix sequence ς.

These items should be included in a new itemset of ς. In order to mine such items and to take into account wild-carded item, we need to extend all transactions of the projected database (step by step) thanks to the function LGS-Closure. 2. The items which can be included in the last itemset of the prefix sequence ς. In that case, we use the function LGS-Closure parametrized with the last itemset of ς.

The last task of Algorithm 1 is to eliminate non-closed multidimensional sequences from the set of closed sequence candidates. The problem is to check out for each multidimensional sequence ς, whether there exists a multidimensional sequence ς ′ such that ς ⊂ S ς ′ and support(ς) = support(ς ′ ). A naive algorithm, which compares each multidimensional sequence with other ones in the set, cannot work because of its quadratic complexity in the number of closed sequence candidates. We adopt the fast subsumption checking algorithm introduced by Zaki [START_REF] Javeed | Charm: An efficient algorithm for closed itemset mining[END_REF]. The value of support is very dense. Thus support cannot be a relevant hash key which enables a sparse distribution of keys. [START_REF] Javeed | Charm: An efficient algorithm for closed itemset mining[END_REF] proposes using the sum of sequences' identifiers (denoted τ (D S ))as its hash key instead of using support. However, in sequence framework, the equivalence of τ (D S ) does not imply the equivalence of support. Thus, for the multidimensional sequences that share the same τ (D S ), we need to check their support in order to eliminate the invalid candidates. This hash key, also used in CloSpan, is easy to compute. Furthermore, it enhances the space search reduction. Thus, the complexity of this operation is Θ( P n 2 τi ) where nτ i is the number of closed sequence candidates that share the same τ i . The nτ i are significantly less than the total number of closed sequence candidates ( P nτ i ).

CM SP F ree: Mining CLosed Multidimensional Sequential Patterns Without Candidate Set Maintenance

The previous algorithm, CM SP Cand Algorithm 1, needs to maintain a set of potentially closed sequences (set L). In post-processing, it has to compute closed sequences among candidate sequences of this set. This maintenance is expensive (quadratic in the size of the set) even if optimization techniques allow to reduce this cost. In this section, we propose an algorithm without candidate-set-maintenance. This approach is based on Bide [START_REF] Wang | Frequent closed sequence mining without candidate maintenance[END_REF]. We first detail some preliminar definitions (Sequence extensions) then we present the associated algorithm.

Sequence Extensions

According to the definition of closed multidimensional sequential pattern, if a g-ksequence S = s 1 , . . . , sg is not closed then there exists a sequence S ′ with the same support of S such that S ⊂ S S ′ . Definition 10 enumerates the five possible ways to have a more specific sequence from a g-k-sequence.

Definition 10 A more specific sequence can be built in five different ways from a g-ksequence s 1 , s 2 , . . . , sg :

-inter itemset forward extension S ′ = s 1 , s 2 , . . . , sg, {e ′ } ; -intra itemset forward extension S ′ = s 1 , s 2 , . . . sg ∪ {e ′ } ; -inter itemset backward extension S ′ = s 1 , s 2 , . . . , s i , {e ′ }, s i+1 , . . . , sg ; -intra itemset backward extension S ′ = s 1 , s 2 , . . . s i ∪ {e ′ }, s i+1 , . . . , sg ; -specialization of an item ∃i ∈ {1, . . . , g}, ∃e, ∃e ′ s.t. e ⊂ S e ′ : S ′ = s 1 , s 2 , . . . , s i-1 ,s i [e ′ /e], s i+1 , . . . , sg where s i [e ′ /e] is the substitution of e by e ′ in s i .

We will notice that the last point can easily be detected thanks to the order of sequence we consider as soon as the four ones (extensions) are detected.

Theorem 1 (Bi-Directional Extension) A sequence S is closed if and only if there does not exist neither any backward or forward extension nor any specialization that preserves the support of S. The proof trivially comes from the definition of closed multidimensional sequential patterns.

In order to check if a sequence is closed, we have to check if there exists some backward or forward extension or specialization of an item, thanks to theorem 1.

It is easy to find the forward extensions of a sequence:

Lemma 1 (Forward Extension) Let S be a sequence, the complete set of forward extensions of S is equivalent to the set of locally frequent items on the projected database according to S such that their support is equal to support(S).

Proof Locally frequent items are discovered by scanning the projected database according to prefix sequence Sp. Since each event occurs during or after the prefix sequence Sp, if an item e occurs in all data sequence from the projected database, then e is a forward extension. All events (items) that occur after the first instance of the sequence Sp is included in the projected database DB| Sp , which means that the complete set of forward extensions can be extracted by scanning the projected database DB Sp .

It is harder to detect the backward extensions of a sequence than forward extensions. There are two types of backward extension:

-S ′ = s 1 , s 2 , . . . , s i , {e ′ }, s i+1 , . . . , sg -S ′ = s 1 , s 2 , . . . s i ∪ {e ′ }, s i+1 , . . . , sg
An item can be inserted in a new itemset between two itemsets s i and s i+1 (inter itemset backward extension). An item can also be inserted in an already defined itemset.

As a sequence can appear several times within a block data sequence, we can identify g intervals to localize the potential backward extension of a g-k sequence.

Figure Fig. 3 describes the g intervals of a multidimensional prefix sequence in a multidimensional data sequence.

Data S1 S2 S3 Sg-1 Sg ... I1 I2 I3 Ig ...

Sequence

Fig. 3 The g intervals that may contained backward extensions of prefix g-k-sequence Sp = s 1 , s 2 , . . . , sg in a block data sequence

We have to maximize these intervals in order to detect all backward extension items.

Definition 11 (i th Maximal Interval) Let Sp = s 1 , s 2 , . . . , sg be a g-k prefix sequence and S be a block data sequence, the i th maximal interval of S according to Sp is defined as follow:

-if i = 1: the subsequence from the beginning of S to la(s 1 ) excluded where la(s 1 ) is the last appearance of the itemset s 1 in S such that la(s 1 ) < la(s 2 ) < . . . < la(g). -if 1 < i ≤ g: the subsequence between the first appearance of the sequence s 1 , s 2 ,-. . . , s i-1 (denoted by f a( s 1 , s 2 , . . . , s i-1 )) and la(s i ) excluded such that la(s i ) < la(s i+1 ) < . . . < la(g).

As an example, the first maximal interval of the sequence s = {(1, 1)}{(1, 2)} in the data sequence S = {(1, 1)}{(1, 2)}{(1, 1)}{(1, 2)}{(1, 1)}{(1, 2)} is the subsequence {(1, 1)}{(1, 2)}{(1, 1)}{(1, 2)} . The second maximal interval of s in S is {(1, 2)}{(1, 1)}{(1, 2)}{(1, 1)} .

Lemma 2 (Backward Extension Checking) Let Sp = s 1 , s 2 , . . . , sg be a g-k prefix sequence, if there exists an item e that appears in each i th maximal intervals of Sp in DB, then e is a backward extension.

Otherwise, if there is no item e that appears in each i th maximal interval of Sp in DB, then Sp cannot have a backward extension.

Proof Let Sp = s 1 , s 2 , . . . , sg be a g-k-prefix sequence, if there exists an item e that appears in each i th maximal interval of Sp in DB (each i th maximal interval of Sp in each data sequence of DB), then we can build the sequence S ′ p = s 1 , s 2 , . . . , s i-1 ∪ {e}, s i , . . . , sg or S ′ = s 1 , s 2 , . . . , s i-1 , {e}, s i , . . . , sg such that Sp ⊂ S S ′ p and support(S ′ p ) = support(Sp). Thus, e is a backward extension of Sp in DB. Suppose that there exists a sequence S ′ p = s 1 , s 2 , . . . , s i-1 ∪{e}, s i , . . . , sg or S ′ p = s 1 , s 2 , . . . , s i-1 , {e}, s i , . . . , sg such that Sp ⊂ S S ′ p and support(S ′ p ) = support(Sp). In each data sequence of DB that contain Sp, item e must appear after the first appearance of s 1 , . . . , s i-1 and before the last appearance of the subsequence s i , . . . , sg . That means that e must appear in each i th maximal interval of Sp in DB. Thus, if we cannot find an item that appears in each i th maximal interval of Sp then there is no backward extension of the sequence Sp in DB.

A prefix sequence cannot be closed if there exists a specialization of an item of the sequence; LGS order allows us to extract closed sequences by considering sequences that contain the most specific items (no or few * ). Thus, if there exists a specialization of an item of a sequence, then the specialized sequence" that contains at least one more specific items is already extracted and added in the set of closed multidimensional sequential patterns. As a consequence, if a sequence is potentially closed (no backward and forward extension), it is sufficient to check if there is no more specific sequence in the set of already mined closed sequence. It should be noted that this set is significantly smaller than the set of frequent sequences. In the worst case, it is necessary to consider all already mined closed sequences that have the same support of the current examined prefix sequence.

Pruning The Search Space

While seeking new sequences with frequent sequence enumeration algorithm , we can use the bidirectional closure property (theorem 1) to check if the current prefix sequence is closed in order to generate a set of non-redundant knowledge. Although this property allows to return a more compact set, it does not allow to retrieve sequences more efficiently. For instance, there is no closed sequence prefixed by a sequence s, therefore it is useless to continue to search such sequences in this case. We define a pruning method to reduce space search by not considering unpromising sequence.

As noticed previously, a sequence may appear several times in a data sequence. In Definition 11, we introduced the notion of maximal interval to detect all the backward extensions. Now, we want to minimize these intervals in order to detect the unpromising sequences. We thus define the notion of i th minimal interval.

Definition 12 (i th Minimal Interval) Let S be a data sequence that supports a gk-sequence prefix sequence Sp = s 1 , s 2 , . . . , sg , the i th minimal interval of Sp in S is defined as follow:

-if i = 1: it is the subsequence before the f a(s 1 ).

-if 1 < i ≤ g: it is the subsequence from f a( s 1 , . . . , s i-1 ) to f a(s i ) excluded such that f a(s i ) < f a(s i+1 ) ≤ . . . ≤ f a(sg).

Theorem 2 (Pruning) Let Sp = s 1 , s 2 , . . . , sg be a g-k prefix sequence, if there exists an integer i such that there is an item e that appears in each i th minimal interval of Sp in DB, then there does not exist closed sequence with prefix Sp.

Proof If an item e appears in each i th minimal interval of Sp, then we can use the new prefix sequence S ′ p that contains e. Indeed, Sp ⊂ S S ′ p and support(S ′ p ) = support(Sp). Thus, all locally frequent items on DB| Sp are also frequent on DB| S ′ p . Therefore, Sp is an unpromising sequence. There is no closed sequence with prefix Sp. The examination of Sp can thus be interrupted.

Let us consider the multidimensional sequence database from Tab. 4. We can stop the exploration of the prefix sequence (a 1 , b 1 , c 1 ) because item (a 1 , b 2 , c 3 ) appears in each first interval of (a 1 , b 1 , c 1 ) in DB. Thus, there is no hope to discover frequent closed sequence from prefix (a 1 , b 1 , c 1 ) .

Thanks to theorems and definitions, we can now define the algorithm for mining closed multidimensional sequential patterns without candidate set maintenance.

Algorithm CM SP F ree

Algorithms 4 and 5 describe the extraction of closed sequential patterns without candidate set maintenance. These algorithms follow the same structure for mining frequent multidimensional sequences in depth first. Indeed, in the worst case (each frequent sequence is closed), the search spaces are the same. However, we introduce a pruning condition to efficiently reduce the search space. Algorithm 5 describes the key part of the extraction. First, if the number of backward and forward extensions of the current prefix sequence Sp is 0, then Sp is potentially closed and we have to check if there is no more specific sequence in set F CS that contains the already discovered closed multidimensional sequential patterns. If there is no such sequence with same support, then Sp is added to F CS. Set F CS is partitioned into subsets according to the support of the closed sequences. Thus, the search of more specific closed sequence than Sp is carried out on a subset of F CS. In the worst case, the complexity of this verification is O(lσ) where lσ is the number of already mined closed sequences which support is equal to σ. Finally, each locally frequent item e on projected database is taking into account. The algorithm checks if it is possible to prune the search space according to the prefix sequence Sp.e (e is added in the last itemset of Sp or in a new one). If it is not possible, the algorithm computes the number of backward extensions of Sp.e and continue the discovery of closed sequences with this new prefix sequence Sp.e.

Experiments

In this section, we report experiments performed on synthetic data and real data.

Synthetic Data

We generated a database thanks to IBM Quest Market-Basket Synthetic Data Generator (100, 000 tuples). Items (1 dimension) were then transformed into multidimensional The runtime increases with the size of the database. Thus we can consider that CM SP is scalable according to this parameter.

Real Data Cube

We report experiments performed on real data. They aim at showing the representative power of closed multidimensional patterns. They were performed on data cube issued from EDF (Electricité De France, the main French energy supplier and electricity producer) marketing context. This data cube describes the marketing activity on a very large EDF customer database (about 30 million of residential customers). We consider five analysis dimensions. As soon as the number of frequent sequences becomes too important, an approach with candidate set maintenance is not adapted whereas CM SP allows the knowledge discovery with low support. We also notice the representative power of closed multidimensional sequential patterns. Indeed, a small number of closed sequences provides the representation of all frequent sequences without any loss of information on the support. As an example, 100, 000 sequences can be retrieved thanks to only about 100 closed sequences. In this paper, we propose a novel framework (definitions and algorithms) for mining closed multidimensional sequential patterns. Mining closed patterns leads to a condensed representation of the patterns without any loss of information. This advantage allows the computation of several measures (e.g. confidence for sequential rules) without any extra-scan of the database as all support values are known. Some works had been done on closed patterns and on closed sequential patterns. But we show in this paper that they cannot be directly applied to the multidimensional framework because of the wild-carded items we consider, leading to a non-easy lexical order. This paper introduces a new challenge with the inference of wild-carded items which are not directly materialized in the data sequences. Two approaches have been investigated, extending the pattern growth framework, with or without candidate maintenance and they are compared. Experiments on synthetic data and real data show the interest of our proposition.

In future work, we plan to consider time constraints and hierarchies which could be easily considered according to the definitions in this framework. It would be interesting to compare CM SP algorithms against an adaptation of work on closed itemset generation using FCA. However, it is necessary to provide an closure operator on multidimensional sequence. The use of more condensed representations could allow a more efficient multidimensional sequential pattern mining. These representations (non-derivable [START_REF] Calders | Mining all non-derivable frequent itemsets[END_REF], k-free [START_REF] Boulicaut | Free-sets: A condensed representation of boolean data for the approximation of frequency queries[END_REF]) exist in itemset framework but they do not exist yet for sequential or multidimensional patterns. This work presents thus a great challenge for future work.

Fig. 1

 1 Fig. 1 Searching all the frequent sequences from the closed ones

Algorithm 1 :

 1 CM SP Cand Data: Database DB, minimal support minsup Result: The set of closed C begin /* Initialization */ Set L ← {} Set C ← {} Sequence α ← /*Frequent sequence mining (depthfirst)*/ SequenceGrowing(α, DB, L, minsup) /*Pruning of non-closed in L*/ foreach s 1 ∈ L do foreach s 2 ∈ L do if s 1 ⊆ S s 2 et support(s 1 ) = support(s 2 ) then delete(s 1 , L) C ← L return C endAlgorithm 2: SequenceGrowing: Mining algorithm Data: Sequence α,projected database DB|α, closed sequence candidate set L , minimal support minsup Result: The set of sequences prefixed by α begin /*α may be closed*/ insert(α, L); /*Check if the sequence was already checked out */ if ∃β | (α ⊆ S β or β ⊆ α) and they both share the same projected database then Copy the descendants of β in α; return Set F l ← getF requentItems(DB|α, minsup); foreach α ′ ← α.b do Build DB|α ′ ; SequenceGrowing(α ′ , DB|α ′ , L, minsup); end can be stopped. Indeed, sequences {(a 1 , b 2 , c 3 )}, {(a 1 , b 1 , c 1 ), (a 1 , b 3 , * )} and {(a 1 , b 2 , c 3 )}-{(a 1 , b 1 , c 1 ), ( * , b 3 , * )} are discovered without scanning the projected database DB (a 1 ,b 1 ,c 1 ) . The discovery of frequent sequences goes on with the examination of the prefix sequence (a 1 , b 1 , * ) . The process is iterated untill the extraction of all the sequences with prefix equal to ( * , * , c 3 ) . Finally, closed sequences are retrieved from the closed candidates set. Only sequences {(a 1 , b 2 , c 3 )}{(a 1 , b 1 , c 1 ), (a 1 , b 3 , * )} and {(a 1 , * , b 2 )} are closed.

Fig. 4

 4 Fig. 4 Experiments carried out on synthetic data

Fig. 5

 5 Fig. 5 Experiments carried out on real data

Acknowledgements This work was partially funded by the EDF R&D Corporation in the framework of a collaboration aiming at studying OLAP Mining for discovering atypical temporal evolutions in data cubes. Thus the authors would like to thank Françoise Guisnel, Sabine Goutier and Marie-Luce Picard, for providing real data to assess our approach.

Example

Let us consider the multidimensional sequence database from Tab. 4 . We want to discover all closed multidimensional sequential patterns with minsup equal to 2. The main algorithm CMSP Cand calls routine SequenceGrowing with the empty sequence , DB and minsup = 2 as parameters.

The first step aims at discovering all the frequent items on DB thanks to routine getFrequentItems:

The sequences are mined with a depth-first strategy according to the order LGS.

The prefix sequence (a

There is no frequent item on the projected database according to

The discovery of frequent sequences continue with the examination of the prefix sequence (a 1 , b 2 , c 3 ) .

When prefix sequence end items (5 dimensions). Since approach without candidate maintenance has to compute backward and forward extension to determine if a sequence is closed, we suppose that an approach with candidate set maintenance is more efficient in sparse data (number of frequent sequences similar to number of closed ones). Experiments reported here confirm it. As soon as the minimal support threshold is low, the approach with candidate set maintenance is adapted. Indeed, the runtime of such approach is very sensitive to the number of frequent sequences since frequent sequences are potentially closed and retrieving all closed sequences is quadratic in the size of the set of candidate sequences. An approach without candidate set maintenance is more robust since it does not consider any set of candidates. Furthermore, an approach without candidate set maintenance provides efficient search space pruning properties. Figure 4(c) reports the behavior of CM SP according to the size of de database (number of data sequences).


domain: spi phys

text:
Rémi Baqué
email: remi.baque@onera.fr

Olivier Ruault

Du Plessis

Nicolas Castet

Patrick Fromage

Joseph Martinot-Lagarde

Jean-François Nouvel

Hélène Oriot

Sébastien Angelliaume

Frédéric Brigui

Hubert Cantalloube

Nicolas Plessis

Patrick Castet

Joseph Fromage

Jean-François Martinot-Lagarde

Hélène Nouvel

Sébastien Oriot

Frédéric Angelliaume

Hubert Brigui

Martine Cantalloube

Pascale Chanteclerc

Xavier Dubois-Fernandez

Philippe Dupuis

Martineau

SETHI / RAMSES-NG: New performances of the flexible multi-spectral airborne remote sensing research platform

Keywords: Remote sensing, SAR, Very High Resolution, Moving target detection and tracking, Optronic

come   L'archive ouverte pluridisciplinaire

I. INTRODUCTION

With the objective of maintaining and updating its airborne remote sensing acquisition capabilities, ONERA has been developing and up-grading its airborne remote sensing system SETHI.

SETHI is a very flexible and multi-function system used for civilian applications as forest measurements and vegetation characterization, chemical products detection and maritime survey, and defense applications as target recognition and tracking. It combines two Pods under wings which are able to carry heavy and cumbersome payloads of different kinds ranging from VHF-UHF to X band and/or optical sensors with a wide range of acquisition geometries. The Pod-based concept allows the easy integration and testing of new systems under the single certification of the Pods by authorities.

II. PLATFORM DESCRIPTION

A. The Aircraft

SETHI is onboard a Falcon 20 (Fig. 1) that is an aircraft designed by Dassault Aviation forty years ago. This aircraft (with payload onboard) can fly all over the world up-to 30000 feet, with 2.5 hours of autonomy. The ground speed can be from 200 to 400 kt.

B. Pods under wings and cabin layout

The Pod design (Fig. 2) includes an outside envelope engineered to provide transparency for electromagnetism waves in a large range of frequencies and a main beam which guarantees the necessary mechanical resistance required by the aeronautical regulations. The useful length of the Pod is 2.3 meters, its diameter is 0.535 meter and payload weight can reach 120 kg. Optical windows on the Pod nose are designed to accommodate optronic sensors. Overall the cabin has a total capacity of 88 U and 480 kg.

The cabin and Pod capacities allow payload boarding flexibility that justifies SETHI interest as airborne remote sensing research platforms.

III. SENSOR PERFORMANCES

SETHI flexibility is also demonstrated regarding the sensor geometry and configuration possibilities.

A. Digital core flexibility and performances

To be able to adapt the radar waveform to the scientist needs, the microwave synoptic uses an Arbitrary Waveform Generator (AWG) that generates all waveform needed (Frequential chirp, OFDM, arbitrary signal, …) and a very high bandwidth and data-rate sampling system that is used for received signal direct sampling. This digital core is full configurable with a high level of flexibility that allows many waveform and applications.

The generation is performed by a 10 bits 2 channels 12 GS/s AWG that transmits a s(t) signal pre-calculated in laboratory. We can use any arbitrary signal as Chirps, OFDM, Modulated signals, etc. and introduce notches (to avoid forbidden frequencies). The VHF/UHF, P and L Band are directly generated (no frequency up-conversion needed) with up to 240 MHz instantaneous bandwidth. The X Band waveform is generated with an instantaneous 720 MHz bandwidth that fed an up-conversion module. The full bandwidth (4 GHz) is obtained by step frequency waveform (6 radar recurrences). AWG Multi Channel capacity is used for simultaneous multi-frequency acquisition on a same area.

The sampling system is a 12 bits 4 channels 2 GHz analog bandwidth one. Each channel is sampled at 1 GS/s I/Q data rate and the storage total capacity is 7 TB at 3.2 GB/s. These high dynamic and high data rate performances are useful for large area observation (large swath) and simultaneous multi-band area imaging. As for generation, VHF/UHF, P and L Band signals are directly sampled (no down-conversion needed), X Band signals are down-converted before sampling. Each sampling system channel is able to record several sampling windows. Multi-sampling windows is useful for system calibration, transmit signal noise characterization.

First sampling window is used to record a copy of the transmitted signal taken just before antenna and injected in receiver input. This signal has traveled all the radar channels (Tx and Rx) and is used to calibrate the radar (expected antenna). Second sampling window is placed between transmitted signal and first received echoes. It is composed of received and radar noises and is used to measure the sensor noise (Noise Equivalent Sigma Zero estimation). The third window is the useful swath to be imaged. The sampling system is equipped with a 10 Gb/s optic fiber data link that fed sampled data to a powerful hybrid CPU/GPU processor. This processor is used onboard SETHI to produce images and products of any SETHI sensor, waveform, geometry. Fig. 4 is an example of high resolution X-Band change detection obtained onboard SETHI a few minutes after second acquisition.

B. Sensor flexibility and performances

SETHI Pods carry microwave and optronic sensors covering from VHF to X Band (Fig. 4) and from 0.4 to 2.5 µm wavelength (Fig. 5).

Radar

C. Geometry and trajectography possibilities

The Pod conception allows many sensor configurations as Along Track Interferometry (ATI), or Pod to Pod Cross Track Interferometry (XTI), and various sensors integration (optronic, radar, AIS receiver, GPS receiver, datalink …). All these possibilities offer a large configuration panel (Fig. 7) that covers many remote sensing applications. The radar antennas can be oriented and moved during operation. This flexibility is provided by "motorized antenna" that can be horn, patches array, dipoles and parabolic antennas. The incidence angle of each antenna can be modified during the flight with a high accuracy (0.1 degree). This is a significant point to explore the incidence angle effect on clutter or target SER. This motorization is also used to point different radars on same area for simultaneous multi-band applications (Fig. 8). Specifically for very high resolution and long range X-UHR Band sensor, antennas are motorized on two axes, so incidence and azimuth angles can be modified during the flight with very high speed (45°/s). This is very interesting for real time aircraft motion compensation and target tracking. Many applications need various trajectory types (linear, circular, octagonal, etc.) to obtain target/clutter signatures on every azimuth angle for example. Other applications need very high precision trajectories for multi-pass interferometry (time coherence analysis, PolInSAR studies, etc.) or repetitive trajectory for time coherence analysis or satellite simulation. To achieve these objectives, SETHI missions are planned by an ONERA made mission planning software that allows all trajectory types, and a very high precision onboard trajectory system is used as high precision piloting assistance. This trajectory system is composed by a very high precision FOG (Fiber Optic Gyroscope) inertial sensor with 0.0025° pitch and roll measurement precision (0.005° yaw precision) and 0.6 m RMS real time position measurement (0.1 cm RMS after post processing). Pilots and sensor operators have in real time information of airborne position and difference between it and the theoretical one on compact touch-screens (Fig. 9). This view can be used for linear and circular trajectory types. Previous chapters demonstrated the SETHI flexibility concerning payload types, integration, configuration, geometry and trajectory. This flexibility has been used in many experimental campaigns to reach various civilian and defense objectives.

A. Forest measurement and ground characterization

Fig. 10 is an example of multi-sensors observation application, dedicated to ground characterization. It is Porquerolles island (France, Mediterranean Sea) observation with full polarization X-and VHF/UHF-Band and dual polarization L-Band SAR images, associated to very high resolution optical and hyperspectral imagery.

B. Maritime surveillance

With objective of maritime opportunity target imagery, AIS receiver has been added with antenna in Pod and receiver in cabin. This system gives GPS point of targets and the trajectory system flexibility is used to create in real time the associated trajectory (Fig. 11). With this principle have been acquired Optical, SAR and vertical profile [START_REF] Cantalloube | SAR retrieval of a ship vertical profile from her roll and pitch motion[END_REF]. Second one, called NOFO, took place off the coast of Norway in June 2015. The released products were hydrocarbons, detected with Hyperspectral VNIR imagery (Fig. 13) and simultaneous X and L Band imagery.

D. Very High Resolution SAR imagery

The X-UHR sensor high performances are very interesting for target recognition. With 4 GHz bandwidth, the imagery resolution attends 5 cm. Fig. 14 is a zoom on a centimeter resolution (< 10 cm) circular SAR imagery on which is a lying man holding a sledgehammer, and hand tools placed on ground to write "ONERA". Target recognition can also be obtained by using circle trajectory around the target (Fig. 16) as realized in the MULTIGIS campaign in 2013.

Fig. 1 .

 1 Fig. 1. SETHI aircraft

Fig. 2 .

 2 Fig. 2. SETHI Pod (with representation of inside payload) and cabin layout SETHI new configuration cabin is composed by four 22U standard electronic cabinets and three (or four) operator seats (Fig. 2).

Fig. 3 .

 3 Fig. 3. Multi-sampling window principle

Fig. 4 .

 4 Fig. 4. On-board High Resolution X-Band change detection application

Fig. 7 .

 7 Fig. 7. In-Pod payload configuration examples Each Pod configuration can be plugged under any wing (Left or Right) and associated with any other Pod configuration. So we can associate VHF/UHF + VNIR + SWIR in one Pod with L + X + Optical in the other Pod for simultaneous multiband area observation; or X XTI (Tx/Rx) + Optical and X XTI+ATI for simultaneous elevation and speed measurement for example.

Fig. 8 .

 8 Fig. 8. Available sensors geometries

Fig. 9 .

 9 Fig. 9. Operator (a) and Pilot (b) real time trajectory display IV. APPLICATIONS

Fig. 10 .

 10 Fig. 10. Multi-sensor (X, L, VHF/UHF, VNIR and Optical) results

Fig. 11 .

 11 Fig. 11. Very high resolution Optical and SAR boat imagery (up) and real time onboard AIS informations and ISAR elevation profile (down)C. Chemical product detection and characterizationTwo campaigns have been realized with SETHI system with offshore pollutant detection and characterization objective. First one, called POLLUPROOF, took place in Mediterranean Sea in May 2015. The pollutants released were non-hydrocarbon one. Example presented below (Fig.12) is SAR imagery of FAME (Fatty Acid Methyl Esters) pollutant (left part of the slick) and rapeseed oil after (right part of the slick). This example demonstrates the interest of multi-band radar for pollutant detection and characterization (various informations from different sensors).

Fig. 12

 12 Fig. 12. L (left) and X (right) Band full polarization SAR image of non-hydrocarbon pollutants

Fig. 13 .

 13 Fig. 13. Oil slick Hyperspectral VNIR imagery That experimental campaign has been successful thanks to the mutli-sensor SETHI capacities.

Fig. 14 .

 14 Fig. 14. Zoom on Ultra High Resolution circular imagery (< 10 cm) with Human and tool detectionThis Very High Resolution sensor has 2 axis real time motorized antenna that allow Spot Light mode and aircraft motion compensation. It also has a long range capacity with 8 kW transmit peak power. With long range and real time motion compensation, long range imagery can be obtained as presented on this long range (60 km) wide swath (18 km), 20 cm resolution image (Fig.15)[START_REF] Cantalloube | Very High Resolution Airborne Synthetic Aperture Radar Imaging at Long Range[END_REF].

Fig. 15 .

 15 Fig. 15. Long range (60 km) wide swath (18 km) 20 cm resolution X Band imagery

Fig. 16 .

 16 Fig. 16. X band Very High Resolution circular imagery of trihedrals and Abeille aircraft (one color per azimuth direction)E. Ground Mobile Target DetectionThe X-UHR reception antenna has many configurations: it can be a polarimetric one, a bi-source one or a 4 channels array antenna. Bi-source configuration has already been used for ground mobile target detection during DELOCCIMOSSAR campaign in 2014[START_REF] Oriot | High resolution airborne SAR/GMTI using a 2 channel antenna[END_REF] and ground mobile targets tracking is presented Fig.17. Data of first airborne tests with the 4 channels array antenna are under processing.

Fig. 17 .

 17 Fig. 17. X band ground target detection and tracking

Acknowledgment

Authors wish to acknowledge DGA (French MoD) for its financial support to MULTIGIS and DELOCCIMOSSAR campaigns. Financial support for the AFRISAR campaign was provided by CNES and ESA. The POLLUPROOF research program (ANR-13-ECOT-007) has been funded by the French National Research Agency (ANR). Authors wish to acknowledge TOTAL for the NOFO (Norwegian Clean Seas Association for Operating Companies) exercises funding.