Marc Plantevit
email: plantevi@lirmm.fr

Anne Laurent
email: laurent@lirmm.fr

Maguelonne Teisseire
email: teisseire@lirmm.fr

Up and Down: Mining Multidimensional Sequential Patterns Using Hierarchies

published or not. The documents may come

Introduction

Data warehouses collect large volume of data through time for decision making purpose. As soon as data are described through time, sequential pattern mining is well adapted [START_REF] Agrawal | Mining sequential patterns[END_REF]. Indeed, sequential patterns aim at describing the main trends from a database based on correlations between events through time. However, sequential patterns are mined among only one dimension whereas databases can contain several dimensions. Therefore, they have recently been extended to multidimensional sequential patterns in order to handle this multidimensionality [START_REF] Pinto | Multi-dimensional sequential pattern mining[END_REF][START_REF] Plantevit | M 2 SP: Mining Sequential Patterns Among Several Dimensions[END_REF][START_REF] Yu | Mining sequential patterns from multidimensional sequence data[END_REF]. Even if multidimensional sequential pattern mining provides a better view of source data for decision support, these methods cannot totally take advantage of the framework of multidimensional databases. In particular, they do not consider hierarchies. Note that mining rules at very high levels of granularity leads to trivial rules whereas mining rules at very low levels of granularity is not always possible because the support value would be too low. The algorithm HYPE [START_REF] Plantevit | Hype: mining hierarchical sequential patterns[END_REF] defined to take hierarchies into account in the extraction of multidimensional sequential patterns has some drawbacks. This approach does not allow to discover patterns such as "When coke sales increase in U.K, soft drink sales increase one month later in E.U". Indeed, the two multidimensional items of the sequence (U.K, Coke) and (Europe, Sof t drink) are comparable (i.e. (U.K, Coke) is more specific than (Europe, Sof t drink)). Note that mining all possible combinations of items is impracticable because of the size of the search space. To the best of our knowledge, there is no sequence mining approach that proposes to take hierarchy into account in a multidimensional framework such that comparable items can appear in the discovered sequences.

In this paper, we propose the concepts of convergent and divergent multidimensional sequences. They provide a more complete knowledge extraction that is better adapted to the main specificity of multidimensional frameworks. Thus, the generation of patterns is either from general items to specific items or from specific items to general ones in order to limit the number of candidate patterns. These new kinds of multidimensional sequences allow to mine longer sequences by modulating the degree of precision/generalization among them. A convergent sequence goes from general knowledge to precise knowledge. As an example, "when soft drink sales increase in USA, coke sales increase on the west coast whereas lemonade sales increase on the east cost" is a convergent sequence. A divergent sequence goes from precise knowledge to general knowledge. For instance, "many sales of beer in London and of wine in France are followed by many sales of alcoholic drinks in Europe" is a divergent sequence.

The rest of this paper is organized as follows. Preliminary concepts and related work are described in Section 2. We define the convergent and divergent multidimensional sequences and algorithms that allow their discovery in Section 3. Some experiments carried out on synthetic and real data are reported in Section 4. In the last Section, we give some conclusions and perspectives for future researches.

Related Work: Multidimensional Sequential Patterns and Hierarchies

Combining several analysis dimensions allows to extract knowledge that well describe the data. [START_REF] Pinto | Multi-dimensional sequential pattern mining[END_REF] was the first work dealing with multidimensional sequential pattern mining. The purchased products are not only described by date id and customer id as in classic sequential pattern mining, but according to a set of dimensions such as Cust-Grp, City, Cust-Age, etc.. This approach mines sequences that are defined among only one dimension (product ). These sequences are described by a multidimensional pattern. Thus, it is impossible to mine combinations of multidimensional pattern through time. [START_REF] Plantevit | M 2 SP: Mining Sequential Patterns Among Several Dimensions[END_REF] proposes to mine such inter pattern multidimensional sequences. Discovered patterns do not only combine several analysis dimensions. These dimensions are combined through temporal dimensions (e.g. time). As an example, in the pattern "lemonade sales increase in N.Y. then coke sales increase in L.A.", N Y appears before LA and lemonade before coke.

In [START_REF] Yu | Mining sequential patterns from multidimensional sequence data[END_REF], the authors mine for sequential patterns in the specific framework of Web Usage Mining. Even though they consider three dimensions (pages, sessions, days), these dimensions are very particular since they belong to a single hierarchized dimension.

This approach provides a better time management but does not fit to multidimensional framework.

Few approaches handle both hierarchy and multidimensionality in sequential pattern mining. In [START_REF] Yu | Mining sequential patterns from multidimensional sequence data[END_REF] , dimensions are just used to represent time, so multidimensionality is not really handled. HYPE ( [START_REF] Plantevit | Hype: mining hierarchical sequential patterns[END_REF]) allows the mining of sequences that are defined among different levels of hierarchy. HYPE provides the discovery of rules as "when drink sales increase in Europe, carbonated water exports increase in France whereas soft drink exports increase in USA" where different levels of hierarchy are present in the multidimensional sequence. However, this proposal cannot extract sequences with items that are defined on the same dimensions but with different granularities such as (London, Coke) and (Europe, Sof t drink). Indeed, this approach mines multidimensional sequential patterns from the most specific items in order to preserve its scalability.

CD M2S Convergent or Divergent Multidimensional Sequential Patterns

In this section, we introduce an original concept. Indeed, human mind often thinks in two different and symmetrical ways. Thinking runs from general to specific or from specific to general. We try to replicate these types of reasoning in the knowledge that we want to extract. We introduce the concept of convergent and divergent sequences. First, we present the preliminary definitions associated to multidimensional sequential patterns and hierarchies. We then describe the convergent and divergent patterns and the associated algorithms.

Preliminary Definitions

Let SDB be a set of multidimensional data sequences. Each element of data sequences is defined on a set of m analysis dimensions denoted by D A . Each dimension D i ∈ D A is associated with a domain of values, denoted by Dom(D i ).

For every dimension D i , we assume that Dom(D i ) contains a specific value denoted by ALL i . We assume that each dimension D i ∈ D A is associated with a hierarchy H i . Every hierarchy H i is a direct acyclic graph (DAG) whose nodes are elements of Dom(D i ) and whose root is ALL i . As usual, the edges of such a DAG can be seen as is-a relationships. The specialization relation corresponds to a top-down path in T i , i.e. a path connecting two nodes when scanning T i from the root to the leaves. We note that when no hierarchy is defined for a dimension D i , we consider H i as being a tree whose root is ALL i and whose leaves are all the elements of Dom(D i ) \ {ALL i }.

Every element (item) e i of a multidimensional data sequence is a tuple t = (d 1 , . . . , d m ) such that for every i = 1, . . . , m, d i ∈ Dom(D i ) and d i is a leaf in H i . In other words, data sequences are defined at the finest levels of the hierarchies associated to D A .

The multidimensional sequence database in Table 1 is used to illustrate the different concepts and definitions. It describes the purchases of products carried out in various cities of the world for three different companies identified by an S ID . Items of data sequences are defined on two dimensions: Place and Product. Dimension Place is associated to hierarchy H P lace whose root is ALL P lace . Element of dimension Place are defined through several levels of hierarchy:

ALL P lace > Continent > Country > City.
A multidimensional item a = (d 1 , . . . , d m ) is a tuple defined on D A such that ∃d i = ALL i .
It is important to note that a multidimensional item can be defined with any value at any level of the hierarchies associated to the analysis dimensions. For instance, (Europe, Coke) and (N.Y, W ine) are two multidimensional items.

Since multidimensional items are defined at different levels of hierarchies, it is possible to compare them using a specificity relation.

Let a = (d 1 , . . . , d m ) and a ′ = (d ′ 1 , . . . , d ′ m ) be two multidimensional: (i) e is said to be more general than a ′ (a ′ ⊆ a) if ∀d i , d i is an ancestor of d i ′ in H i or d i = d ′ i ; (ii) a is said to be more specific than a ′ (a ⊆ a ′ ) if ∀d i , d i is a descendant of d ′ i in H i or d i = d ′ i ;
(iii) a and a ′ are said to be incomparable if there is no relation between them (a a ′ and a ′ a).

A multidimensional itemset i = {a 1 , . . . , a k } is a non-empty set of multidimensional items such that for all distinct i, j in {1 . . . k}, a i and a j are incomparable. For instance, {(F rance, W ine), (U.K, W ine)} is a multidimensional itemset. {(Europe, ALL P roduct ), (London, W ine)} is not a multidimensional itemset because (London, W ine) ⊆ (Europe, ALL P roduct ).

A multidimensional sequence s = i 1 , . . . , i l is an ordered list of multidimensional itemsets. {(U SA, W ine)}{(F rance, W ine)(U.K, W ine)} is a multidimensional sequence associated to the database SDB Table 1.

A multidimensional data sequence S supports a multidimensional sequence s = i 1 , . . . , i l if for every item a i of every itemset i j , there exists an item a ′ i in S such that a ′ i ⊆ a i with respect to the ordered relation (itemset i 1 must be discovered before itemset i 2 , etc.). According to Table 1, data sequence S 2 supports the sequence s = {(F rance, Coke)}{(Europe, W ine)}{(U SA, Coke)} .

The support of a sequence s is the number of data sequences of SDB that support s. Given a user-defined minimum support threshold minsup, a sequence is said to be frequent if its support is greater than or equal to minsup.

Given a set of multidimensional data sequences SDB that are defined on a set of dimension D A , the problem of mining multidimensional sequential patterns is to discover all multidimensional sequences that have a support greater than or equal to the user specified minimum support threshold minsup.

Convergent and Divergent Multidimensional Sequences

So far, we have defined the problem of mining multidimensional sequential patterns. We have also noticed that taking hierarchies into account provides relations between multidimensional items. Now, we can introduce the concept of convergent and divergent sequences.

Definition 1 (Divergent Sequence ) A sequence s = i 1 , . . . , i k is said to be a divergent sequences if for every item e j ∈ i k , ∄e ′ j ′ ∈ i k ′ such that k ′ < k and e j ⊂ e ′ j ′ .

In other words, for each item e of the sequence, there does not exist more general item contained before e in the sequence. The sequence {(P aris, Coke)},-{(F rance, Coke)(U.K, Coke)}, {(Europe, Coke)}{(ALL P lace , Coke)} is a divergent sequence.

Definition 2 (Convergent Sequence) A sequence s = i 1 , . . . , i k is said to be a convergent sequence if for every item

e j ∈ i k , ∄e ′ j ′ ∈ i k ′ such that k ′ < k and e ′ j ′ ⊂ e j .
For each item e of the sequence, there does not exist more specific item contained before e in the sequence. The sequence {(ALL P lace , W ine)}, {(Europe, W ine)}, {(Italy, W ine)(F rance, W ine)} is a convergent sequence.

Algorithm

Ordering the items in the itemsets of the sequences is a fundamental step to avoid the already examined cases. Existing methods that are based on different paradigms (pattern growth ([6]), Apriori([1, 5, 11, 2])), are not directly applicable in a multidimensional framework. Indeed, items, that are not defined with the finest level of hierarchy, are not explicitly present in the database. Such items are retrieved by inference since there is no associated tuple in the database.

We then introduce functions to locally handle all items and not only items that are present in data sequences. An itemset is said to be extended if it is equal to its closure according to the relation of specialization (⊆). This notion allows to take all items into account. In order to enhance the management of items, we introduce a lexicographicospecific order (lgs) that is an alpha-numeric order according to the precision degree of the item. Thus, the most specific items are the first to be handled. We have to define a function LGS-Closure that transforms an itemset of a data sequence into its extended itemset that contain all the items that can be inferred. As an example, LGS-Closure({(P aris, Coke)}) = {(P aris, Coke),(P aris, ALL P roduct , (F rance, Coke), (F rance, ALL P roduct ), (Europe, Coke),(Europe, ALL P roduct ), (ALL P lace , Coke)}. We note that the tuple (ALL P lace , ALL P roduct ) is not considered by definition of multidimensional item.

The extraction of frequent items can be done on each extended itemset. In pattern growth approaches, sequences are extracted by greedily adding a frequent item to a frequent sequence. It is thus necessary to define an efficient way for extending sequences from the last itemset of the sequences. For this purpose, we define the function LGS-ClosureX where X is an itemset that contains "forbidden items" (i.e. every items e i of the last itemset of the prefix sequence and all items comparable to e i ). As an example, {(ALL P lace , W ine)} =

LGS-Closure {(Europe,ALL P roduct )} ({(P aris, W ine), (London, W ine)}).

Divergent sequences are discovered thanks to algorithm CD M 2S. To mine all divergent sequences on SDB, routineCD M 2S( , SDB, ∅, minsup) is called.

This algorithm is pattern growth based [START_REF] Pei | Mining sequential patterns by pattern-growth: The prefixspan approach[END_REF]. Instead of scanning the whole database, level by level as Apriori based methods, the database is projected according to the prefix sequence. This data projection projection is quite different from [START_REF] Pei | Mining sequential patterns by pattern-growth: The prefixspan approach[END_REF]. Indeed, we have to handle all possible items, so the projection has to take the itemsets of the data sequences that contain the discovered item, and not only the item as in [START_REF] Pei | Mining sequential patterns by pattern-growth: The prefixspan approach[END_REF].

Two kinds of items can be extracted from the projected database: 1. Items that are added in a new itemset of the prefix sequence α. These items are mined thanks to LGS-Closure. 2. Items (denoted by e) that are added in the last itemset of the prefix sequence α. In this case, we use the function LGS-Closure X where X is the last itemset of the sequence α.

This algorithm allows the extraction of divergent sequences. To mine convergent sequences, it is necessary to use the same algorithms but on an inverted database. Indeed, beginning by the end (invert the ordered relation) of the data Algorithm 1: CD M2S

Experiments

In this Section, we report experiments on both synthetic and real data.

Synthetic Data:

Experiments were carried out on a synthetic database. This database contains 10, 000 data sequences (with an average of 47 itemsets) over 5 analysis dimensions. Some hierarchical relations are defined between elements of each analysis dimension. In this paper, we report the behavior of our approach (number of patterns, runtime) according to several parameters (support threshold, |D A |, degree and depth of hierarchies).

Figures Fig. 2(a) and Fig. 2(b) respectively report the runtime and the number of frequent sequences according to the minimum support threshold. The number of sequences tends to increase when the support decreases. The runtime follows the same behavior. However, it is possible that the number of frequent sequences decreases when the support decreases. Indeed, some more specific items can appear. Furthermore, a more general item is faster inferred in a data sequence than a more specific one. Therefore, we can obtain a smaller number of frequent sequences.

Figures Fig. 2(c) and Fig. 2(d) report the runtime and the number of frequent sequences according to the depth of the hierarchies on the analysis dimension. Adding one level in the hierarchies provides more precise data (soda becomes pepsi or coca). There is thus more different values in the database. CD M 2S is robust front of the specialization phenomena. Indeed, even if the data become very specific (5 different levels in the hierarchy), our approach allows to extract some sequences that are described among several level of hierarchy. We can notice that the runtime increases when the number of levels of the hierarchies increases. This is due to the number of potentially frequent items that increases. Figures Fig. 2(e) and Fig. 2(f) report the behavior (runtime and number of sequences) of our approach according to the degree of the hierarchies. Increasing the degree of a hierarchy provides more specific data (adding a son or an instance). Our approach allows to discovery knowledge while hierarchies become more specific. However, the cost of the extraction (runtime) is more expensive. These experiments on synthetic data show the robustness of our approach according to the diversity of the data (D A , degree and depth of the hierarchies, etc.). Considering a more diverse source data leads to a more important extraction cost that stays acceptable.

Real Data:

We report experiments on logs of toy game [START_REF] Dartnell | Assisting scientific discovery with an adaptive problem solver[END_REF] which is an Eleusis based card game. This game was created in order to simulate the activity of the scientific discovering (publications, refutations, experiments). The problem in Robert Abbot's Eleusis card game [START_REF] Gardner | Mathematical games[END_REF] is to find a secret law hidden from the players and determining the valid sequences of cards that can be played during the game. [START_REF] Dartnell | Assisting scientific discovery with an adaptive problem solver[END_REF] proposes a new version in which humans are helped by machines to produce a theory. Players have to discover a rule (for instance a rule is "two successive cards must have two different colors" and a positive example according to this rule is "ace of hearts followed by king of spades"). A player wins points if he produces a positive example or he publishes his theory. He also earns points if he refutes a theory published by another player. He loses points if his theory is disproved by another player.

The hidden rules are card sequences. Each sequence contains a left part and a right part. Each part can contain several cards. We have described this problem according to several analysis dimensions: one dimension for the card values ( king, queen, . . ., ace); one dimension for the card colors (heart, diamond, spade and clubs); one dimension for the position of the card in the sequence(right or left) and one dimension for the oracle answer (true, wrong).

We can obtain convergent and divergent rules. A divergent sequence is: "For the secret rule water lily, players frequently propose the following cards: three of spade, ace of spade, a odd card of spade and finally a black odd card.". A convergent sequence is: "For the secret rule lily, players frequently propose a red card, a card of heart, a numbered card of heart.". We notice that these rules are relevant for the expert and they cannot be extracted with classical algorithm.

Conclusion

We proposed an original method multidimensional sequences that are defined on several levels of hierarchy according to different points of view: from general to particular (convergent) or from particular to general (divergent). We thus defined the concepts of convergent and divergent multidimensional sequences. We also introduced the algorithm CD M 2S that is pattern growth based. Some experiments on synthetic and real data show the interest of our approach. Note that this proposal is totally different from [START_REF] Plantevit | Hype: mining hierarchical sequential patterns[END_REF]. Indeed, in this paper, we focus on mining for special sequences: divergent or convergent sequences. Such sequences mean that comparable items can appear together within a convergent or divergent sequence whereas they cannot in HY P E. Furthermore, HY P E algorithm is APriori based whereas algorithm CD M 2S is pattern-growth based. This work offers several perspectives. First, divergent sequence can model special behaviours like buzz or the appearance of a seminal paper that leads to lot of publications and applications. Convergent sequences can model behaviors that become specialized through time like the appearance of new scientific topics or marketing products. Therefore, It would be very interesting to focus on the discovery and the prediction of such behaviors. Second, the efficiency of the extraction can be enhanced thanks to condensed representations (closed patterns, etc.) that provide some properties to efficiently prune the search space. Furthermore, other propositions can be done on the management of the hierarchies. We can imagine a modular management of hierarchies where some levels of the hierarchies would be more important (minimal and maximal levels on some hierarchies in order to be not too general or too specific) to fit user needs and to preserve the scalability of the extraction.

Fig. 2 .

 2 Fig. 2. Experiments carried out on synthetic data

Figures Fig. 2

 2 Figures Fig. 2(g) and Fig. 2(h) report the runtime and the number of sequences according to the number of analysis dimensions (|D A |). Adding some

  Figures Fig. 2(g) and Fig. 2(h) report the runtime and the number of sequences according to the number of analysis dimensions (|D A |). Adding some

Table 1 .

 1 Dimension Product is associated to hierarchy H P roduct whose root is ALL P roduct and Coke and W ine are leaves. Part of the hierarchies is illustrated Fig. 3.1. Set of multidimensional data sequences SDB Part of Hierarchies ALL P lace and H P roduct

	SID		Multidimensional data sequences
	S1	{(P aris, Coke)}{(P aris, Coke)}{(London, Coke)}{(T okyo, Coke)}
	S2 {(P aris, Coke)}{(Lyon, W ine)(P aris, Coke)}{(T urin, Coke)}{(N.Y, Coke)}
	S3	{(N.(a) Cities	(b) Drinks
		Fig. 1.

Y, W ine)}{(L.A, Coke)}{(P aris, W ine), (London, W ine)}

  Prefix sequence α, projected database SDB|α, set of current frequent sequences F S , minimum support threshold minsup Result: Set of divergent frequent sequences with prefix α ′ , SDB|α) ≥ minsup and e ′ ⊂ e}; foreach items e ∈ LF do α ′ ← α.e; Call CD M 2S(α ′ , SDB| α ′ , F S, minsup);

	begin
	if α = then
		F S ← F S ∪ {α};
	LF	←	{e	s.t.	support(e, SDB|α)	≥	minsup	and
	∄e ′ s.t. support(e

Data: end sequences and re-invert the discovered patterns allows a discovery from general to particular case.


Sandra Bringay

Anne Laurent

Béatrice Orsetti

Paola Salle

Maguelonne Teisseire

Handling Fuzzy Gaps in Sequential Patterns: Application to Health

Dealing with numerical data for mining novel knowledge is a non trivial task that has received much attention in the last years. However, it is still not easy to handle such data, especially when large volumes of values must be analyzed. In our work, we focus on biological data from DNA chips that biologists study in order to try and discover new gene correlations that could help understanding diseases like breast cancer. In this framework, we consider the values from the DNA microarrays, which convey the behavior of some genes, and we want to discover how these behaviors are correlated. This data are considered as being ordered as numerical values can be sorted. In previous work, rules like (1 5)(2) have been discovered, meaning that genes 1 and 5 have the same expression level followed by gene 2 that has a higher expression value. However, such data are very noisy and considering close values as ordered is often false. We thus consider here fuzzy rankings based on a fuzzy partition provided by the experts. Rules can then better characterize how genes are correlated.

I. INTRODUCTION

Health is a major concern for the modern society. Cancer is a leading cause of death and in particular breast cancer, which is the second most common type of cancer and the fifth most common cause of cancer death [Org09]. As deaths from breast cancer worldwide are projected to continue rising, the problem of discovering the genes involved in their development have been intensively addressed by the biomedical community. In this framework, researchers aim at discovering how genes behave in terms of their implication in biological processes and how their expression is regulated and co-regulated.

Formerly impossible because of the costs, collecting large amounts of data is now possible, especially by means of the microarrays. Such microarrays [BCS + 05], [START_REF] Hoerndli | Functional genomics meets neurodegenerative disorders. part ii: Application and data integration[END_REF] allow researchers to compare the expression of genes in different tissues, cells or conditions. However, the way to process those data for making a biomedical sense is a big challenge. For such purposes, data mining plays a key role as it allows for discovering previously unknown knowledge from large amounts of data.

In the framework of our study, we have studied test datasets available online 1 [WKZ + 05]. The number of microarrays depend on the number of people whose tumor was taken (286 samples). Each microarray reports the expression of 17,816 genes put under several conditions, leading to Sandra Bringay, Anne Laurent, Paola Salle and Maguelonne Teisseire are with the LIRMM laboratory -CNRS UMR 5506, Univ. Montpellier 2 (contact email: laurent@lirmm.fr).

Maguelonne Teisseire is with the CEMAGREF Montpellier. Béatrice Orsetti is with the INSERM. 1 http://www.ihes.fr/ zinovyev/princmanif2006/ In this paper, we focus on such data and we aim at discovering rules to help biologists and medical doctors to analyze how genes interact. In previous work, we have proposed an algorithm DEMON [START_REF] Salle | DEMON: DEcouverte de MOtifs squentiels pour les puces ADN[END_REF] to extract sequential patterns from microarray data. An example of such pattern is gene 'Gene 1' has an expression lower than genes 'Gene 2' and 'Gene 3' which expressions are close. In this paper, we focus on how fuzzy logic can help defining rules that are more understandable and actionable for the experts. For instance, the experts are eager to be provided with rules that they can easily interpret in a linguist manner without being obliged to define a crisp partition of the values from the microarrays. For this purpose, we propose to extent classical sequential patterns to obtain rules like (G1 G5) (very overexpressed,0.8) (G3) , meaning that in the experiment led, the gene 3 is far much expressed compared to genes 1 and 5, which are expressed in a similar way. The level to which genes are under or over expressed is defined using a fuzzy partition, leading to the so called fuzzy gaps.

We provide below the definitions introduced in order to handle fuzzy gaps, together with the associated algorithms. Experiments reported here show some examples of patterns found by this approach, and could not have been discovered using classical crisp approaches.

II. BASIC DEFINITIONS

In this section, we present the seminal information related to the data we want to mine, and sequential patterns [START_REF] Agrawal | Mining sequential patterns[END_REF], that are the basis of our approach.

A. Biological Data of Breast Cancers

Cancer arises from a change in a single cell, which spreads to one or more organs. This change may be caused by external agents such as tobacco or ionizing radiation and/or inherited genetic factors. Cancers result from mutations, or abnormal changes, in the genes responsible for the regulation of the growth of cells. While the cells of healthy people are normally regenerated by this process, mutations can occur in sick people cells, which will inhibit some genes and increase the action of other ones, resulting in abnormal behaviors. The cells divide without control, producing more cells and forming a tumour. A tumour can be benign (not dangerous) or malignant (potentially dangerous). Breast cancer refers to a malignant tumour that has developed from cells in the breast. Discovering new information about groups of genes implied in breast cancers is challenging. We thus propose to mine for rules describing how the levels of gene expressions are correlated and ordered. This method is based on sequential patterns as they allow us to discover correlations among ordered items. For this purpose, we mine databases that report the level of expressions of genes taken from cells of several patients, as described by the example below.

Example 1: DNA chips report the gene expression levels for some genes taken from the cells of breast tumors. We consider here 4 chips and 5 genes. Table I displays this database, genes having been ordered by expression level.

B. Sequential Patterns

Sequential patterns are often introduced as an extension of association rules in [START_REF] Agrawal | Mining sequential patterns[END_REF]. They highlight correlations between database records as well as their temporal relationships. Some generalization were proposed to use fuzzy set

Chip ID Expression Level Genes 1 -6.2 G2 -1.8 G1 -1.3 G5 2.3 G3 4.8 G4 2 -5.4 G2 -2 G1,G5 2.3 G3 4.8 G4 3 -5.8 G2 -3.6 G1 -3 G5 2.3 G3 7.5 G4 4 -4.7 G2 0 G4 2.3 G5 8.57 G3,G1 TABLE I EXAMPLE OF DATABASE FOR GENES 1, 2, 3, 4, 5
theory to handle numeric attributes. In this paper we use sequential patterns with fuzzy gaps to provide the biologists with more precise sequences.

Sequential patterns describe frequent sequences of itemsets. By itemset, we consider a set of items that occur simultaneously in a timestamped database. For instance, when considering a database from a supermarket, the database will describe the items purchased by customers at different dates. Frequent patterns extracted from such database are like (butter chips)(chocolate) > sup meaning that sup% of the customers purchased butter together with chips and then chocolate.

Definition 1 (Itemset): Let I = {i 1 , i 2 , ..., i m } be the set of items being considered. An itemset is a non-empty set of items (i 1 i 2 . . . i k ) ⊆ I.

It should be noted that as an itemset is a set, it is a nonordered representation.

Definition 2 (Sequence): A sequence s is a non-empty ordered list of itemsets, denoted by it 1 it 2 ...it p . A sequence is said to be an n-sequence (or a sequence of size n) if is consists of n items.

Definition 3 (Database): Let R be a set of object records where each record consists of three pieces of information: an object-id, a record timestamp and a set of items appearing in the record. R is said to be the database.

In our context, the object-id is an experiment (Chip ID). Records correspond to the genes, and timestamps correspond to the expression levels, as detailed below.

Example 2: Referring back to Table I, G1, G2, G3, G4 and G5 are items. (G1 G5) is a itemset, and s = (G1 G5) (G3) is a sequence. The database is given by the whole table.

Definition 4 (Subsequence

): A sequence it 1 it 2 ...it p is a subsequence of another one it 1 it 2 ...it m if there exist integers l 1 < l 2 < ... < l p such that it 1 ⊆ it l1 , it 2 ⊆ it l2 , ..., it p ⊆ it lp . Chip ID Gene Expression Sequence 1 (G2)(G1)(G5)(G3)(G4) 2 (G2)(G1 G5)(G3)(G4) 3 (G2)(G1)(G5)(G3)(G4) 4 (G2)(G4)(G5)(G3 G1)
= (G1) (G3) is a subsequence of s =< (G1 G5) (G3) because (G1) ⊆ (G1 G5) and (G3) ⊆ (G3). However, (G1) (G5) is not a subsequence of s.
It should be noted that databases can be displayed as a set of sequences, as shown by Table II. All records from the same object are then grouped together and sorted in increasing order of their timestamp. They are called a data sequence.

Definition 5 (Sequence Support): An object supports a sequence s if s is included within the data sequence of this object (s is a subsequence of the data sequence).

The frequency of a sequence (f req(s)) is defined as the percentage of objects supporting s.

A sequence is said to be frequent according to a minimum frequency value (minF req) specified by the user if the condition f req(s) ≥ minF req holds. The problem of discovering frequent sequential patterns is then described as the discovery of all sequences that occur for most than minsup customers, where minsup is said to be the minimal support and is provided by the user. The set of sequential patterns contains all maximal 2 frequent sequences.

In classical approaches, the sequences are discovered whatever the time gap that may occur between two itemsets (e.g., purchases). More recently, time constraints have been introduced in order to manage the inter-relations in a more precise way [START_REF] Srikant | Mining sequential patterns: Generalizations and performance improvements[END_REF]. For instance, such constraints allow for discarding sequences if the gap between two itemsets is greater than a given number of days or, in the opposite, two itemsets are considered as being simultaneous if they occur at close dates. Fuzzy constraints have been introduced by [FLT07], [START_REF] Fiot | Softening the blow of frequent sequence analysis: Soft constraints and temporal accuracy[END_REF]. However these constraints do not allow to consider several gaps between two itemsets.

In this paper, we consider fuzzy intervals to describe these gaps, thus providing an approach to mine fuzzy ordered patterns.

III. FUZZY ORDERED PATTERNS

In this section, we detail our contribution, aiming at providing efficient and relevant methods for mining patterns including fuzzy gaps. For this purpose, we consider a fuzzy partition provided by the expert [START_REF] Jones | Fuzzy Sets: Theory and Applications[END_REF]. This partition is given as a set of n fuzzy sets A = {A 1 , . . . , A n } defined 2 in terms of their size over the universe U of the values that can characterize the difference between two gene expression values. This fuzzy partition is defined such as ∀u ∈ U , n i=1 µ i (u) = 1 where µ i is the membership function of the fuzzy set A i . Figure 3 describes an example of such a partition. It should be noted that, as asked by the biologists, two genes showing an expression difference lower than ln(2) will be considered as having a similarly expression. ln(2) plays a crucial role in the definition of the fuzzy partition as the normalization of microarrays relies on this particular value.

Based on this partition, it is possible to describe when two values must be considered as being lightly, averagely or very different, and to which extent. These descriptions are used to defined the fuzzy gaps, which will appear in the patterns we introduce in this paper.

A. Mining Sequential Patterns with Fuzzy Gaps

In this section, we detail how we handle fuzzy gaps when mining microarray data. We recall here that rules like (G1 G5) (very dif f erent,0.8) (G3) are to be extracted, meaning that genes 1 and 5 have similar expression values, followed by gene 3 that has a very different value.

Example 4: From Table I, it is clear that, for 3 chips out of 4, the expression of gene G1 is lower than the expression of G3 and that the expression of gene G5 is lower than the expression of G3, two frequent sequences would then be discovered: (G1)(G3) and (G5)(G3) . However, it is impossible to see that G1 and G5 have similar expressions and to describe how the expressions are separated. In our approach, we thus soften this and, as said above, we mine rules like Gene 3 is far much expressed compared to genes 1 and 5, which are expressed in a similar way reported as (G1 G5)very over expressed(G3) .

Each rule is associated to its support and to the degrees to which the fuzzy relations (e.g., very close, close, very different) hold.

We provide below the formal approach we propose and the associated definitions.

We recall here that our approach aims at mining databases defined as in Definition 3. Such a database contains objects, each object consisting of a sequence of itemsets. We first define how the crisp gap between two itemsets can be computed.

Definition 6 (Itemset Difference): Let R be a database, o be a record from R, and it 1 and it 2 be two itemsets from the sequence associated to o. The difference δ(it 2 , it 1 ) between it 1 and it 2 is defined as the absolute value of absolute value of the difference between the timestamp of the first item of it 2 and the last item of it 1 .

Example 5: In Table I, the difference δ(it 2 , it 1 ) between itemsets it1 = (G2) and it2 = (G1 G5) equals | -2 -(-5.4)| = 3.4 for object 2 and | -1.8 -(-6.2)| = 4.4 for object 1 as -1.8 is the lower expression value for itemset it 2 . In our context, calculating the difference amounts to compute the difference between the two expression levels.

Definition 7 (Fuzzy Gap Sequence): Let A be a set of fuzzy sets building a fuzzy partition, a fuzzy gap sequence s F G is defined as an ordered list of itemsets and fuzzy sets such as

s F G = it 1 (A i1 )it 2 (A i2 )...(A ip-1 )it p where ∀i ∈ [1, p -1], A i ∈ A.
Definition 8 (Fuzzy Gap Degree): Let s o be the data sequence associated to an objet o, let it 1 and it 2 be two itemsets and A be a fuzzy subset associated to its membership function µ. A fuzzy gap degree between it 1 and it 2 is a pair (A, d) and we have it 1 (A, d)it 2 where d = µ(δ(it 2 , it 1 ))

Example 6: We consider the object 1 from Table I, and the fuzzy set averagely over expressed (hereafter avg).

We have δ(it 2 , it 1 ) = 4.4 as shown in the previous example. We have the fuzzy gap degree (G1 G5)(avg; 1)(G3) as µ avg (4.4) = 1.

Considering object 2, we have G5)(avg; 0)(G3) as δ(it 2 , it 1 ) = 0.3 and µ avg (0.3) = 0.

Considering object 3, we have (G1 G5)(avg; 0.66)(G3) as δ(it 2 , it 1 ) = 5.3 and µ avg (5.3) = 0.66.

Considering object 4, the sequence (G1 G5)(G3) does not hold as G1 occurs at a higher level compared to G5.

The degree of a data sequence is computed using a t-norm to merge the fuzzy gap degrees. Note that the t-norm botn used is generalized to an n-ary function.

Definition 9 (Fuzzy Gap Sequence Degree): Let s o be the data sequence associated to an objet o, a fuzzy gap degree-sequence s F GD is defined as

s F GD = it 1 (A i1 , d 1 )it 2 (A i2 , d 2 )...(A ip-1 , d p-1 )it p where (A i , d i )
are fuzzy gap degrees. The degree of s o denoted by

F s F G (s o ) is then computed as: F s F G (s o ) = ⊥(d 1 , ..., d p-1 )
Remark. In our approach, the min is considered as the tnorm we use as we do not want to penalize long sequences by over decreasing their degree. Note that every t-norm is associative, and can thus be computed on-the-fly when building the fuzzy gap sequence, thus leading to more performant algorithms.

Finally, the support of a fuzzy gap sequence is computed by summing the membership degrees over the whole database.

Definition 10 (Fuzzy Gap Sequence Support): Let s F G be a fuzzy gap sequence, let O be the set of objects of the database records, the support of s F G is computed as:

F req(s F G ) = o∈O F s F G (s o )

|O|

Example 7: In our running example, the sequence (G1 G5)(averagely over expressed)(G3) has a support of 1+0+0.66+0 4 = 1.66 4 = 0.415 = 41.5%.

Given a database of object records and the associated sequential patterns, the problem of fuzzy gap sequence mining is to find all maximal fuzzy gap sequences which support is greater than a user-defined threshold (M inF GF req).

B. Algorithms

In this section, we detail the algorithms we propose for tackling the problem of mining fuzzy gap sequences.

Sequential patterns are computed using a levelwise approach, meaning that sequences of size k are computed from frequent sequences of size k -1. This approach allows us to remain scalable as the databases to be mined can be very large. In the context of fuzzy gap sequences, we aim at describing the gaps between itemsets in frequent sequences in order to display a more valuable information to the experts. For this purpose, each sequential pattern is examined in order to define the best linguistic labels to be associated with the gaps between the itemsets, as reported by Algorithm 1.

Algorithm 1: Fuzzy Gap Sequence Extraction

Data: R, a database of records MS, the set of sequential patterns from R M inF GF req, the threshold defined by the user A the set of fuzzy sets building a fuzzy partition Result: S F G , the set of maximal fuzzy gap sequences begin S F G ← ∅ F uzzyGapSeq ←FuzzyGapGen(MS, A) /* Generation of all possible fuzzy gap sequences associated to the fuzzy subsets*/ foreach s F G ∈ F uzzyGapSeq do

F req s F G ← ∅ foreach o ∈ R do foreach s F G ∈ F uzzyGapSeq do F req s F G ← F req s F G + F s F G (s o ) /*
The frequency is computed by summing the degree of each object data sequence */

foreach s F G ∈ F uzzyGapSeq do if (Freq s F G /|R|) ≥ M inF GF req then S F G ← S F G ∪ {s F G } end
The F uzzyGapGen function (Algorithm 2) generates all combinations of sequences with the possible fuzzy sets for describing the gaps between itemsets.

IV. EXPERIMENTAL RESULTS

A. DataSet

As said above, we consider the dataset provided online [WKZ + 05]. The number of microarrays amounts to 286 and 17,816 genes are considered, which intensity ranges from -7.54 to 8.57 (meaning that the maximum difference between two gene expressions is 16.11).

The dataset aims at discovering classification tools for dicrimating between two types of cancer: agressive and non agressive). We thus took the genes for which the difference of expression is significative between these two classes by using the SAM (Significant Analysis MicroArray) method,

← loc s ∪ { s • a • it i+1 } S F G ← S F G ∪ {loc s }
end usually used by biologists, which uses the FDR and q-value method presented in [START_REF] Storey | A direct approach to false discovery rates[END_REF]. 555 genes were extracted by this process.

On top of this data, we consider the following trapezoidal fuzzy sets that were provided by the biologist:

• almost equal (genes belong then to the same itemset) when the difference ranges from 0 to ln(2)

B. Some Extracted Rules

We report here some rules that have been extracted by our approach and were described as interesting by the expert. For confidential reasons, we do not provide the gene name hidden behind the number we provide.

Without any management of gaps between itemsets, the following sequence was discovered: (546)(411)(51) . However, this sequence was not relevant as genes 546 and 411 have similar expression levels for many experiments.

By considering gaps using crisp intervals, the following pattern was discovered: (546 411) lightly (51) showing the interest of considering intervals as:

• it was then possible to consider 546 and 411 as similar,

• it was possible to describe how 51 was expressed compared to these two first items.

However, it is very difficult for biologists to define crisp partitions as the cutting is too strict and does not represent the reality. Biologists thus defined a fuzzy partition, which allowed us to discover to which extent the pattern (546 411) lightly (51) was true. This support was 3.63 instead of 5 in the crisp case. This information is of great importance to the expert.

Finally, one of the more actionable results from the experiments we led comes from the fact that the experts would like to find out patterns to discriminate between the benign and malignant cases. For this purpose, we compare the patterns found from the two subsets. In our former experiments, many patterns (e.g. (5)(41)(51) ) were the same in both experimental conditions and were thus considered as non discriminant. However, by using our approach, we found out that this pattern occurs in both conditions, but with very different fuzzy gaps. Indeed, for benign tumors, the pattern (5)avg(41)lightly(51) can occur, whereas the pattern (5)avg(41)very(51) occurs for malignant tumors. Our approach can thus help discriminating between the two forms of tumors.

V. CONCLUSION

In this paper, we study the problem of mining biological data for discovering relevant gene interactions in the framework of breast cancer. For this purpose, we show how Fuzzy Logic is of great interest in order to better take into account. The experimental results reported here highlight these promising results.

Further work will include the study of the properties of the fuzzy constraints introduced by the fuzzy partition in order to enhance the performances of our algorithm in terms of memory and time consumption, and further experiments on other databases, including other microarray data and clinical data from a psychological study both related to the Alzheimer disease. Moreover, we aim at studying how the computation of the support impacts the sequences found by our approach. In particular, we will compare the results obtained in this paper using a sigma-count to the results obtained by a thresholded count or a thresholded sigmacount. This comparison will be led both on the performance side (time and memory consumption) and on the semantic side by an evaluation provided by the experts.

Fig. 1 .

 1 Fig. 1. Gene Expression Values from a DNA Microarray

Fig. 3 .

 3 Fig. 3. Fuzzy Partition for Expression the Difference Between Two Gene Expression Values

TABLE II EXAMPLE

 II OF SEQUENCE DATABASE FOR GENES 1, 2, 3, 4, 5 Example 3: Referring back to our previous examples and Table I, the sequence s


Cécile Low-Kam
email: clowkam@math.univ-montp2.fr

Anne Laurent
email: laurent@lirmm.fr

Maguelonne Teisseire
email: teisseire@lirmm.fr

Detection of Sequential Outliers using a Variable Length Markov Model

The problem of mining for outliers in sequential datasets is crucial to forward appropriate analysis of data. Therefore, many approaches for the discovery of such anomalies have been proposed. However, most of them use a sample of known typical sequences to build the model. Besides, they remain greedy in terms of memory usage. In this paper we propose an extension of one such approach, based on a Probabilistic Suffix Tree and on a measure of similarity. We add a pruning criterion which reduces the size of the tree while improving the model, and a sharp inequality for the concentration of the measure of similarity, to better sort the outliers. We prove the feasability of our approach through a set of experiments over a protein database.

Introduction

Lately, mining for outliers in large sequential databases has risen as an active domain of research. By outlier, we mean "an observation that deviates so much from others as to arouse suspicion that it was generated by a different mechanism" [START_REF] Hawkins | Identification of Outliers[END_REF]. Indeed, the potential applications of anomaly detection are numerous and diverse, as this is a matter of interest for areas such as knowledge discovery (Web Usage Mining) and biostatistics (DNA mutations detection). Even so, it remains a challenging problem as outliers are rare by definition [START_REF] Sun | Mining for outliers in sequential databases[END_REF]. Furthermore, they have to be separated from noise which arises unavoidably in a dataset: considering noise as an anomaly wrongly raises suspicion. Within the last few years, detection of outliers has been investigated for all kind of datasets. Among those approaches, some were based on discordance tests under assumptions of one probabilistic distribution of the observations, in the cases of univariate or multivariate data [START_REF] Barnett | Outliers in Statistical Data[END_REF]. Others were based on a distance, allowing the detection of anomaly when confronted to multidimensional data [START_REF] Knorr | Algorithms for mining distancebased outliers in large datasets[END_REF].

Meanwhile, bases of DNA or protein sequences have been studied to understand biological mechanisms, for example through the extraction of motifs in [START_REF] Ferreira | Chapter vi: Deterministic motif mining in protein databases[END_REF]. Those datasets are challenging because of their structure and their size, demanding appropriate model selection. Therefore, a very efficient approach for mining for outliers in such bases is proposed in [START_REF] Sun | Mining for outliers in sequential databases[END_REF]. However, some issues are problematic: first, this method remains very memory-demanding, and second, it involves some previous knowledge of typical sequences to build a model. Consequently, we propose here to extend this approach to overcome both of those challenges: we use an information criterion to reduce the size of the model, while making it more accurate. We also add refined bounds for the similarities of the sequences. This leads to a better detection of anomalies among the database.

The rest of the paper is organised as follows: in Section 2 is presented an accurate method for the detection of anomalies. Our improvements are proposed in Section 3, resulting in an adequate and parsimonious method for mining for outliers in sequential databases. The pertinence of our approach is showed through experiments in Section 4, followed by a detailed analysis of all our propositions. We summarise our work and evocate potential further research in Section 5.

The Basic Method

In this Section we recall an existing approach for the extraction of outliers in sequential databases [START_REF] Sun | Mining for outliers in sequential databases[END_REF]. This work of Sun et al. is based on a natural assumption for sequences such as DNA or proteins: they have a property of "short memory" [START_REF] Ron | The power of amnesia: Learning probabilistic automata with variable memory length[END_REF], that is, a variable length Markov condition: for a sequence s = s 1 ...s , if for 2 ≤ i ≤ , P T (s i |s 1 ...s i-1 ) is the probability that s i follows s 1 ...s i-1 , then there is an integer 1 ≤ K ≤ i -1 such that P T (s i |s 1 ...s i-1 ) = P T (s i |s i-K ...s i-1 ).

(1)

Figure 1. An example of PST on the binary alphabet.

It is a Markov property of order K. It is said to be variable as K is not fixed. An usual representation of such a model is a suffix tree,where each node has its greater suffix as a parent. Each leaf represents a memory of the associated Markov chain. This model is for example used for the classification of protein sequences in families [START_REF] Bejerano | Modeling protein families using probabilistic suffix trees[END_REF]. Indeed, it allows to estimate the probability of each sequence in the set.

Probabilistic Suffix Tree (PST)

Let us consider a set S of sequences over a finite alphabet Σ. The probability of a sequence s is denoted by P T (s). A PST is a classic suffix tree, provided with conditional probabilities for each node. More precisely each node contains the count of its associated sequence s in the database and a vector of length |Σ| of the conditional probabilities P T (σ|s) for each σ ∈ Σ. As the size of the tree grows exponentially with the length of the memory, it is pruned. To this end, a maximum length L for the tree is fixed. And nodes with low frequency, considered as negligible, are removed.

Example 2.1 Figure 1 shows a PST on the alphabet {a, b}. A maximum length L = 3 is fixed. 4 is the minimal frequency for the sequences. The nodes aa, aab and bab have been pruned because they are too rare.

Once the PST has been constructed, the conditional probabilities associated to its nodes are used to estimate the distribution of each sequence, as for any sequence s = s 1 ...s :

P T (s 1 ...s ) = P T (s |s 1 ...s -1 )...P T (s 2 |s 1 )×P T (s 1 ) (2)
Example 2.2 Using the former PST, P T (aabb) = P T (b|aab)×P T (b|aa)× P T (a|a)×P T (a) = P T (b|ab)×P T (b|a)×P T (a|a)×P T (a) = 0.5×0.8×0.2×0.35.

Thus, the probability of each sequence is computed according to the PST. Afterwards, a measure of similarity is introduced, in order to discreminate between typical and non-typical observations.

Measure of Similarity and Information Theory

In [START_REF] Sun | Mining for outliers in sequential databases[END_REF], for each sequence s = s 1 ...s , the measure of similarity is defined as:

SIM N (s) = 1 log P T (s 1 ...s ). (4)
To allow the computation of any new sequence's similarity, the conditional probabilities of the PST are smoothed, thus, infinity is avoided. The measure SIM N is normalised, and therefore it is not biased by the length of the sequence. Moreover, when under appropriate assumptions, it has an interesting aymptotic property. First, the sequences are supposed to be generated by an information source. This implies that they take their values in a finite alphabet, and that their distribution is stationary, i.e. it does not change over time. Second, let us remind that the entropy of a random variable is a measure of regularity [START_REF] Ash | Information Theory[END_REF]. This notion can easily be extended to two or more variables, through the concept of joint and conditional distribution, leading to joint and conditional entropies. The uncertainty of an information source is then defined as the limit of the conditional entropy.

Let us suppose that the sequences of the base S have been generated by an unique ergodic information source, then Shannon-McMillan theorem [START_REF] Shannon | A mathematical theory of communication[END_REF] states that -SIM N is consistent towards the uncertainty of the source. A proof of this result can be found in [START_REF] Ash | Information Theory[END_REF]. Therefore, when is large, SIM N (s) should be close to minus the uncertainty of the source, if s has indeed been generated by it. Otherwise, SIM N (s) will lay far from the similarity of other sequences. Consequently, a concentration inequality such as Chebyshev's is used to determine bounds outside which sequences are likely to be anomalies. However, this inequality is known to be ill-fitted for points far from the mean, which actually are the potential outliers.

In [START_REF] Sun | Mining for outliers in sequential databases[END_REF], experiments on a protein database are led with success. But they lay on the prior knowledge of which sequences are typical, as only those are used to build the PST. Indeed, first, a model is built over the typical sequences, and second, the authors determine whether new sequences are anomalies with respect to the given model. But we wish to directly extract the outliers from the set of sequences. For all that, however well-fitted the method presented in this section may be to point out structural differences between families of proteins, it fails when one wishes to truly mine for outliers. Moreover, though partially pruned, the tree remains space-consuming. Therefore, the aim of the present paper is the improvement of the approach proposed in [START_REF] Sun | Mining for outliers in sequential databases[END_REF]. We determine whether a sequence s is an outlier given a base S and a threshold t. (Our approach may be easily extended to find the top-n outliers in S.)

Our Extension

In this section, we detail our approach. Namely, we introduce:

• A further pruning of the tree, with an information criterion, inducing systematic discovery of anomaly, thanks to an adequate and reduced model.

• An exponential concentration inequality for the measure of similarity, leading to sharper bounds and therefore better discrimination of outliers.

We adopt the same hypotheses of short memory property and stationarity, and also consider the case of a finite alphabet Σ.

Pruning the PST with Akaike's Information Criterion

We have seen in Section 2 that a PST is pruned in two steps: a maximal length L is fixed. Any node deeper than L is pruned. Any node with a lower frequency in the dataset than a given threshold is pruned. In addition to the two pruning procedures we have seen so far, in [START_REF] Ron | The power of amnesia: Learning probabilistic automata with variable memory length[END_REF] a PST is built as follows: a node is added only if it differs statistically from its parent. To this end, a criterion based on the Kullback-Leibler information is used. The Kullback-Leibler information or distance is sometimes called relative entropy, and denotes the information lost when a distribution is used to approximate another [START_REF] Burnham | Model Selection and Inference: A Practical Information-Theoretic Approach[END_REF]. The statistic of error for a letter σ and a sequence s, denoted by Err(σs, s), is defined in [START_REF] Ron | The power of amnesia: Learning probabilistic automata with variable memory length[END_REF] by the Kullback-Leibler distance between the distributions P T (.|σs) and P T (.|s), pondered by the probability of σs. If Err(σs, s) is less than a given threshold, the node σs is pruned. Nodes corresponding to strings which observation probabilities are weak are also pruned, no matter how they differ from their parent: being rare, they are considerated as negligible. In [START_REF] Sun | Mining for outliers in sequential databases[END_REF], only this last criterion is applied. But there could be cases where the compared distributions differ at a deeper level. Therefore, in [START_REF] Ron | The power of amnesia: Learning probabilistic automata with variable memory length[END_REF], all the potential descendants of each pruned node are also tested.

Example 3.1 Let us consider again the binary suffix tree of Figure 1. Suppose the threshold is 0.1. Err(abb, bb) = 0.001, and Err(bbb, bb) = 0. Nodes abb and bbb are thus pruned, because their vector of conditional probabilities is similar to their parent's: therefore no additional knowledge is gained using a memory of order 3 instead of one of order 2.

This last pruning method is not used in [START_REF] Sun | Mining for outliers in sequential databases[END_REF]. For this purpose, we recall a well-known criterion Akaike called An Information Criterion (AIC) and introduced in [START_REF] Akaike | Information theory as an extension of the maximum likelihood principle[END_REF]. It allows to balance between the fit of a model and its complexity. Let L be the likelihood function of a model, and k its number of parameters. Then the AIC is:

AIC = 2k -2 log L. ( 5
)
The AIC is related to the Kullback-Leibler information. It is based on the maximum likelihood estimate of the model. The correcting term asymptotically unbiases the estimate. This criterion allows to compare the distance of two possible models from the "true" unknown one, then choose the closest (see [START_REF] Burnham | Model Selection and Inference: A Practical Information-Theoretic Approach[END_REF] for details). Therefore, over a set of candidate models, we should select the one with the lowest AIC. In practice, the AIC may perform poorly when the number of parameters is important with respect to the size of the dataset. This problem was lifted in [START_REF] Sugiura | Further analysis of the data by akaike's information criterion and the finite corrections[END_REF]. Therefore, the Second-Order Information criterion was defined in [START_REF] Hurvich | Regression and time series model selection in small samples[END_REF] by:

AIC c = AIC + 2k(k + 1) n -k -1 , (6)
where n is the length of the data. The AIC c performs well, no matter how many parameters are in the model. For all that, we always use this corrected version in our experiments.

We apply this criterion in two steps. First, let us denote by M L the markovian model of fixed order L. We select the "best" global model among the set {M L , L ≥ 0}, according to the criterion. Therefore, a maximal length for the tree is fixed. In the second step, the same criterion is applied locally at the parent-son level: let M p be the model based on a parent and M s the model based on its sons, then,

∆AIC c = AIC c (M p ) -AIC c (M s ) (7)
expresses the difference between the two models. We add all its sons to a parent if ∆AIC c is greater than 0. Otherwise, we do not add any of the parent's descendants.

Here the AIC differs from the Kullback-Leibler criterion, as nodes are added one by one for the latter.

Thus, we obtain a variable order Markov model. We introduce the corrected Akaike's Criterion in the algorithm proposed in [START_REF] Sun | Mining for outliers in sequential databases[END_REF]. Our experiments show that the size of the tree reduces drastically with this new criterion, and that the quality of the prediction is improved. In summary, besides getting a statistical-based choice of model, we are able to lower the number of nodes of the PST, in order to gain on its size. Once the model has been selected, the conditional probabilities of the PST are used to calculate SIM N (s) for each sequence s in S.

Sharper Bounds for the Concentration of SIM N

In the previous subsection, we have seen how similarity measures are computed. Then, in order to find the outliers among the base, an inequality of concentration is used in [START_REF] Sun | Mining for outliers in sequential databases[END_REF]. Let E(SIM N ) and V(SIM N ) be the expectation and the variance of the random variable SIM N . Then Chebyshev's inequality states that

P {|SIM N -E(SIM N )| ≥ t} ≤ V(SIM N ) t 2 . (8)
The outliers should be those which similarity lay far from the mean, out of the bounds defined in [START_REF] Burnham | Model Selection and Inference: A Practical Information-Theoretic Approach[END_REF]. But, although satisfying for points close to the mean, this inequality performs poorly for observations far from it, i.e. potential outliers. For these points, exponential concentration inequalities are known to be more accurate. Among them is Bennett's inequality [START_REF] Bennett | Probability inequalities for the sum of independent random variables[END_REF]:

Theorem 3.1 Let X 1 , ..., X be independant real-valued random variables with zero mean, and assume that |X i | ≤ c with probability one. Let S = i=1 X i and σ 2 = 1 i=1 V(X i ). Then for any t > 0,

P {S > t} ≤ exp - σ 2 c 2 h ct σ 2 , ( 9
)
where the function h is defined by

h(u) = (1 + u) log(1 + u) -u for u ≥ 0.
A proof of this result can be found in [START_REF] Devroye | Combinatorial method in density estimation[END_REF]. We consider the random variables

X i = log P T (s i |s 1 ...s i-1 ), 1 ≤ i ≤ .
They are bounded as the conditional probabilities of the tree are smoothed. The exponential type of Bennett's inequality assure that sharper concentration results are thus obtained. Indeed, our experiments show that as far as outlier detection is concerned, bounds obtained with Bennett's perform better than those induced by Chebyshev's inequality.

Experiments and Analysis

In order to prove the efficiency of our approach, we have led some experiments on the Pfam database [START_REF] Bateman | The pfam protein families database[END_REF], which contains about 9300 families of proteins, on the alphabet of amino acids of size 20. Pfam is known to cover many protein families [START_REF] Ferreira | Chapter vi: Deterministic motif mining in protein databases[END_REF]. We use the R software [START_REF] Team | R: A Language and Environment for Statistical Computing[END_REF], and its Bio3D package [START_REF] Grant | Bio3d: An r package for the comparative analysis of protein structures[END_REF] to read data in the FASTA format. In [START_REF] Sun | Mining for outliers in sequential databases[END_REF], it has been observed that a good similarity measure should be able to detect the difference of structure between two families. Therefore, it has been proposed to build a PST over one family, then compute the similarities of each sequence to obtain bounds. This tree has then be used to calculate similarity measures of members of others families, in order to know how many of them fall out of bounds. We have led similar experiments, comparing results obtained when pruning or not with the corrected Akaike's Criterion, and when using Bennett's or Chebyshev's inequality. All methods have given similar satisfying results, suggesting that all Markov models of reasonable order work well for this purpose. However, our aim here is to detect what are the outliers among a set of sequences, without knowledge about which members are typical, and should thus be used to build the tree. Therefore, we consider the HCV_core family of the Pfam database, containing over 3000 members, to which we add a few sequences belonging to the NADHdh family. In this paper, we present the results obtained for two such datasets. The first one, denoted by D 1 , contains 30 sequences from the NADHdh family, that is, about 1% of outliers. The second set D 2 contains 300 sequences from the NADHdh family, representing 10% of the total. We build a PST over those datasets, and check how well the similarity measure picks out the members of the NADHdh family).

First, we select the global model (the maximal order of the Markov chain) using the AIC c . We consider four Markov models of increasing order {M L , 0 ≤ L ≤ 3}. Table 1 summarises the results obtained for D 1 . The criterion select the model of a Markov chain of order 2 corresponding to the lowest score. Let us consider the histograms of similarities obtained with M 0 , M 1 , M 2 and M 3 : Figure 2 shows an estimation of the distribution of the similarities of both typical sequences and outliers, given one model. M 2 discriminates best between the two groups of similarities, as they are clearly separated, therefore an adequate inequality of concentration should be able to pick up well the outliers within the data, as it will be seen later. On the contrary, the other models allow similarities for both groups to overlap on each other, making the distinction hard to figure out. We see that the most complex model of the list is not ade- Let us now proceed with the second step of our pruning strategy. We have seen in Section 3 that once the maximal depth for the tree has been found, one can also use the criterion locally, for each node. We prune the PST according to the AIC c at the local father and child level, and obtain a similar histogram. The tree has now 312 nodes instead of 368. The first histogram of Figure 3 shows a clear separation between the two groups. As the anomalies are detected all the same, and the cost of calculation for the local criterion is important (it is a sum on all the alphabet), we may wonder if it is worth it. But when dealing with large alphabets, one might wish to select a variable length Markov model level by level, without first having to fix a maximal length, then build all the tree, and eventually prune nodes that should be removed. Therefore, we build the PST on the same base of sequences only using the local ∆AIC c criterion, that is, we do not fix a maximal depth for the tree. The PST thus obtained has only 515 nodes for a maximal depth of 3 and leads to comparable accurate results, as shown by the second histogram of Figure 3. However, it is usually advised to first select a global model [START_REF] Burnham | Model Selection and Inference: A Practical Information-Theoretic Approach[END_REF], so this last approach must be employed with caution.

Once the model has been selected, we determine whether an observation is an outlier with respect to a given threshold. To this end, under the model M 2 , we compute the bounds obtained with Bennett's inequality with a threshold correponding to the ratio of outliers introduced in the datasets. Then we compare our results to those obtained us-

L = 2
L is not fixed [START_REF] Sun | Mining for outliers in sequential databases[END_REF]. This is the same as setting the bound at 3 standard-deviations from the mean. We get the results presented in Table 2: it shows what percentages of true or false outliers are extracted. For the first dataset, both inequalities lead to comparable accurate bounds. However, the threshold for Bennett's inequality seems to make more sense, regarding the number of outliers introduced. Generally, one can not know in advance how many outliers are in the dataset. But checking the similarities on a histogram such as those presented in Figure 2 gives an intuition. For the second dataset, Chebyshev's inequality is clearly outperformed by Bennett's.

Eventually, pruning the PST using the AIC c leads to satisfying results. But in [START_REF] Sun | Mining for outliers in sequential databases[END_REF], a pruning criterion solely based on frequency was proposed. One may thus wonder whether it would lead to similar detection. Table 3 summarises the results of a such pruning for D 1 and L = 4, using Bennett's inequality with a threshold of 1%. For thresholds lower than 15, all outliers are not detected. For a threshold greater than 15, all anomalies are out of bounds, but the tree may be larger than our optimal result. Thus, this method has comparable and sometimes even better results than our, regarding the size of the tree. However, no indication about the threshold is given, while it depends on the size of the dataset, on the number of outliers, and on the very structure of the sequences of the base. Indeed, for D 2 , when fixing the minimal frequency at 15 and using Bennett's inequality Datasets with 1%, 10% of outliers at 10%, 66% of the outliers are not outlined. The quality of the detection may thus vary whereas pruning with an information criterion allows to systematically identify the outliers.

In this section, we have presented the results of our approach on bases of proteins. We also have led similar experiments on other families in the Pfam database, leading to the same accurate detection of outliers.

Conclusion and Further Work

In this paper, we have provided an approach for mining for outliers in sets of sequences of data. It is an extension of the one proposed in [START_REF] Sun | Mining for outliers in sequential databases[END_REF]: namely, the building of a PST from the dataset and the use of a measure of similarity. However, both the important size of the tree and the exact mining of outliers remained problematic issues. Therefore, we have improved this method through a further pruning of the PST, based on Akaike's Information Criterion, in order to reduce its size and to have an appropriate model, and through the use of the exponential inequality of Bennett to get more accurate bounds. Those additions have resulted in a more efficient mining of outliers, as the quality of prediction was improved while the size of the tree remained small. We have confirmed our conjectures through a whole set of experiments on a base of protein sequences. Future work will consist in extending our method to more complex structures of data, such as sequential patterns in sequences of sets [START_REF] Agrawal | Mining sequential patterns[END_REF].

Figure 2 .

 2 Figure 2. Comparaison of Markov models of order 0 to 3.

Figure 3 .

 3 Figure 3. Histograms obtained when applying the criterion locally.

Table 1 .

 1 AIC c for Markov Models of order 0 to 3.

	Model	AIC c
	M 0	10.2 × 10 5
	M 1	6.4 × 10 5
	M 2	1.6 × 10 5
	M 3	3.2 × 10 5

Table 2 . Percentages of true and false outliers out of bounds.

 2

	Dataset Inequality Threshold	True False
	D 1	Chebyshev	0.11	100.0	0.3
	D 1	Bennett	0.01	100.0	0.5
	D 2	Chebyshev	0.11	5.0	0.7
	D 2	Bennett	0.10	100.0	4.0
	ing Chebyshev's inequality with a threshold of 11% as it is
	recommended in

Table 3 . Results with a frequency-based cri- terion for

 3 D 1 .

	Thresholds Number of nodes Non-detected outliers
	5	1318	0.37
	10	782	0.03
	15	603	0.0

Table 4 .

 4 Table of Notations PST Probabilistic Suffix Tree SIM N Measure of similarity Σ, σ Alphabet, letter of the alphabet S, s = s 1 ...s Set of sequences, one sequence P T (s)

		Probability of s
	M L	Markov Model of order L
	H	Entropy or Uncertainty
	AIC	Akaike's Information Criterion
	L	Likelihood
	k	Number of parameters of the model
	D 1 , D 2