Marc Plantevit
email: plantevi@lirmm.fr

Sabine Goutier
email: sabine.goutier@edf.fr

Françoise Guisnel
email: francoise.guisnel@edf.fr

Anne Laurent
email: laurent@lirmm.fr

Maguelonne Teisseire
email: teisseire@lirmm.fr

Mining Unexpected Multidimensional Rules

Keywords: H.2.8 [Database Management]: Database applications, data mining Algorithms, Design, Theory Unexpected Patterns, Sequential Patterns, Multidimensional Framework

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

The extraction of patterns and rules is an active domain of data mining. These patterns have been extensively applied in various areas such as customer market basket analysis, web-log analysis, discovery of patterns from protein sequences network security and music analysis. These practical applications have been made possible by the development of robust algorithms [START_REF] Ayres | Sequential pattern mining using a bitmap representation[END_REF][START_REF] Zaki | Spade: An efficient algorithm for mining frequent sequences[END_REF][START_REF] Pei | Mining sequential patterns by pattern-growth: The prefixspan approach[END_REF]. However, the extraction of rules presents some non negligible limits, thus putting restrictions to its effective use. The main disadvantage stems from the huge set of extracted rules which may imply a second data-mining problem. The existence of a large number of rules makes them unmanageable for any human user in a decision making framework. This disadvantage directly comes from the type of knowledge the rules try to extract: frequent and confident rules. Although it may be useful when users want to discover frequent unobserved relations, it may be not when they want to discover unexpected relations.

It has been noticed that, in fact, 10% of the rules cause 90% of labor. The occurrence of a frequent event carries less information than the occurrence a rare or hidden event [START_REF] Cohen | Finding interesting associations without support pruning[END_REF][START_REF] Yang | Mining surprising periodic patterns[END_REF][START_REF] Suzuki | Unified algorithm for undirected discovery of exception rules[END_REF]. Therefore, it is more interesting to mine unexpected unfrequent events than frequent events which are all normally already known. Some works allow to discover unexpected knowledge from association rules like exceptions, surprising rules [START_REF] Suzuki | Scheduled discovery of exception rules[END_REF][START_REF] Berzal | Anomalous association rules[END_REF]. For instance, "seat belt and child → danger" is an exception rule according to the strong rule "seat belt → safe". But these rules cannot take time into account whereas the data stored in data warehouses are historical data. For instance, purchases are reported every day or every hour. Furthermore, data are often aggregated according to several dimensions in a data cube. For instance, sales are aggregated according to the shop, city, customer group, customer age, etc.

Even if various approaches have been proposed for discovering unexpected rules thanks to association rules, there is no approach that combines unexpected rules and time in a multidimensional framework. This paper thus aims at introducing unexpected multidimensional sequential rules. This new kind of rules highlights, in a multidimensional framework, correlations between events through time. Unexpected multidimensional sequential rules are unfrequent and confident rules. They represent deviations from common and well-known behaviors. These common behaviors can be modeled by multidimensional sequential rules (frequent and confident). Indeed, a common behavior corresponds to rules which often occur in the data set, and so are frequent. These rules should be highly confident to be considered. Unexpected multidimensional sequential rules are hidden by a a dominant rule. They represent potential future common rules and surprising behaviors that have to be handled.

In this paper, we present the approaches to discover unexpected knowledge and we present the concepts related to multidimensional sequential patterns. We introduce the fundamental concepts related to our approach as well as algorithms allowing its implementation. Experiments carried out on real data are reported and highlight the interest of our approach.

MOTIVATING EXAMPLE

In order to illustrate our approach, we consider the following running example that will be used throughout the paper.

Let us consider a data cube DC in which transactions issued from customers are aggregated. We assume that DC contains the number of sales reported over the following dimensions: D is the date of sale (ranging from 1 . . . 12), C is the city where transactions have been issued (considering several cities: N.Y., L.A., etc. ), A is the age of customers (considering three discretized values, denoted by Y (young), M (middle) and O (old)), CH is the hobby of the customers (walking, surf, golf, etc.), P is the product sold (car, bike, etc.), and M is the aggregated number of sales (measure).

For instance, the first cell of DC (see the first tuple Fig. 1) means that, at date 1, 12 little cars were bought in N.Y by young customers who like golf. Let us now assume that we want to extract all unexpected multidimensional sequential rules that deal with the age of customers, the hobby of the customers, the products they bought and that are enough frequent and confident with respect to the cities where transactions have been issued. We considered unexpected rules compared to common rules who are highly frequent and confident.

As an illustration, we suppose the following common rule: If young customer has recently received his car license then he will buy a little car. An unexpected rule according to this common rule may be: If a young customer who loves surfing has received his car license then he will buy a van. This rule has a low support but it is highly confident. In this case, extra information specified in the if-part (love surfing) changes the conclusion (little car to van).

RELATED WORK

In this section, we report works on mining unexpected rules and we introduce the multidimensional sequential pattern mining problem formulation.

Unexpected Knowledge

In the literature, it has been noted that a frequent event carries less information than a rare or hidden event [START_REF] Cohen | Finding interesting associations without support pruning[END_REF][START_REF] Yang | Mining surprising periodic patterns[END_REF][START_REF] Suzuki | Unified algorithm for undirected discovery of exception rules[END_REF]. Therefore, it is often more interesting to discover unexpected and non-frequent events than frequent ones. The main problem is to determine what is an interesting event (low support is not enough) and how to extract it. Among works on discovering unexpected rules , there are two types of approaches. On the one hand, user-driven methods require the intervention of a human expert. On the other hand, data-driven methods try to autonomously discover more restrictive rules. In the literature, the terms subjective and objective can also be found to characterize the user-driven and the data-driven approaches [START_REF] Silberschatz | What makes patterns interesting in knowledge discovery systems[END_REF].

In user-driven methods, a human expert has to intervene at least on one of the following points, in order to:

• Determinate some restrictions over the attributes which can potentially occur in the relations [START_REF] Srikant | Mining association rules with item constraints[END_REF].

• Describe data with a hierarchy [START_REF] Han | Discovery of multiple-level association rules from large databases[END_REF].

• Indicate the potentially useful rules according to prior beliefs [START_REF] Liu | Analyzing the subjective interestingness of association rules[END_REF].

• Eliminate all the uninteresting rules in a first step so that other rules can automatically appear in subsequent steps [START_REF] Sahar | Interestingness via what is not interesting[END_REF].

Thus, user-driven approaches are quite constraining since they also require an expert intervention as soon as data are updated. That is the reason why we focus on data-driven approaches.

Data-driven approaches are divided into two sub-fields. Some works use interestingness measures that are different from usual confidence and support measures [START_REF] Tan | Selecting the right objective measure for association analysis[END_REF][START_REF] Geng | Interestingness measures for data mining: A survey[END_REF]. Other approaches try to discover unexpected knowledge which are not extracted by classical algorithms.

Meaningful rules are not necessary frequent. [START_REF] Cohen | Finding interesting associations without support pruning[END_REF] and [START_REF] Ma | Mining mutually dependent patterns[END_REF] try to discover unfrequent itemsets which are highly correlated.

In [START_REF] Zhong | Peculiarity oriented multidatabase mining[END_REF], the authors try to obtain peculiarities which are defined as highly confident unfrequent rules according to a nearness measure. These peculiarities are significantly different from the rest of the individuals. [START_REF] Yang | Mining surprising periodic patterns[END_REF] extracts unusual sequences where items with low appearance probability appear together. In this case, the sequences are quite surprising. This approach does not use the support to determine the frequency of a sequence but the authors use entropy measures to detect surprising sequences.

Suzuki's approach is very interesting and consists in looking for exceptions that occur in a database [START_REF] Suzuki | Scheduled discovery of exception rules[END_REF][START_REF] Hussain | Exception rule mining with a relative interestingness measure[END_REF][START_REF] Suzuki | In pursuit of interesting patterns with undirected discovery of exception rules[END_REF][START_REF] Suzuki | Undirected discovery of interesting exception rules[END_REF][START_REF] Suzuki | Unified algorithm for undirected discovery of exception rules[END_REF]. The presence of an attribute interacting with another may change the consequent of a strong rule. For instance, "seat belt and child → danger" is an exception rule according to the strong rule "seat belt → safe". The general form of an exception rule is as follows:

X ⇒ Y, XZ ⇒ ¬Y, X Z
X ⇒ Y is a common sense rule, XZ ⇒ ¬Y is an exception rule where ¬Y can be a concrete value E. X Z is the reference rule. In [START_REF] Hussain | Exception rule mining with a relative interestingness measure[END_REF] and [START_REF] Suzuki | Unified algorithm for undirected discovery of exception rules[END_REF], the authors use 5 user-defined parameters to describe this rules. In general terms, they try to discover interaction between attributes: in [START_REF] Suzuki | In pursuit of interesting patterns with undirected discovery of exception rules[END_REF], X represents antibiotics, Y recovery, Z staphylococci and E death.

The following rule can be discovered: with the help of antibiotic, the patient usually recovered, unless staphylococci appears; in this case, antibiotic combined with staphylococci may result to death". This type of rules is very interesting and cannot be detected by association rule algorithms. In [START_REF] Suzuki | Undirected discovery of interesting exception rules[END_REF], the authors define 5 thresholds in order to extract the pairs. However, a strict specification of the different thresholds for a data set can lead to no discovery. In [START_REF] Suzuki | Scheduled discovery of exception rules[END_REF], the authors propose a solution to this problem with an avl tree for each threshold to easily and efficiently update the values.

In [START_REF] Berzal | Anomalous association rules[END_REF], the authors define the anomalous rules. Anomalous rules are association rules which are verified when the common rules fail. More formally, let X, Y and A be three itemsets, X A is an " anomalous rule " according to the rule X ⇒ Y where A is the anomaly, if the following conditions hold:

• X ⇒ Y is a strong rule (support and confidence)

• X¬Y ⇒ A is a confident rule • XY ⇒ ¬A is a confident rule.
This approach is based on support (M inSupp) and confidence (M inConf ) thresholds since the rules are a case of association rules.

According to the definition of Suzuki, these rules are semantically different. Moreover, this approach do not require the existence of the "conflictual" itemset (Z). The authors define the confidence of an anomalous rule as follows: conf R (X

A) = supp R (X∪A) supp R (X)
where R corresponds to the subset of the database which contains X and which does not verify the rule X ⇒ Y . In other words, R is the data set which does not verify the rule and which may contain an anomaly. Since suppR(X) is equal to supp(X ∪ ¬Y ) on the whole database, the support can easily be computed as supp(X)supp(X ∪ Y ).

The confidence of an anomalous rule X

A can then be defined as follows: confR(X A) = supp(X∪A)-supp(X∪Y ∪A) supp(X)-supp(X∪Y )

. The authors estimate that in practical case, A is an item and no an itemset. Their approach is based on the fact that even if X ∪ A and X ∪ Y ∪ A may be unfrequent, they are the extensions of frequent itemsets X and X ∪ Y . Therefore, their problem is reduced to the support computation of L ∪ i for each frequent itemset L and item i which is potentially an anomaly. The extraction of such anomalous rules is Apriori-based.

There are several objective approaches which try to mine particular types of rules. Each type of rules has a particular semantic. All these approaches are managed in a database framework without taking time into account. Moreover, they only consider one dimension in the association rule mining.

Multidimensional Sequential Patterns

In this section, we describe the problem of mining multidimensional sequential rules. Three works try to combine several analysis dimensions [START_REF] Pinto | Multi-dimensional sequential pattern mining[END_REF], [START_REF] Yu | Mining sequential patterns from multidimensional sequence data[END_REF] and [START_REF] Plantevit | M 2 SP: Mining sequential patterns among several dimensions[END_REF]. We present the formal definition from [START_REF] Plantevit | M 2 SP: Mining sequential patterns among several dimensions[END_REF] because it is the most general framework.

Rules combine several dimensions but they also combine these dimensions over time. 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.

Let us consider a data cube DC defined on the set of dimensions Dn, and a partition of Dn into four sets:

• DT for the temporal dimensions, the set of dimensions that are meant to introduce an order between events (e.g. time);

• DA for the analysis dimensions, the set of dimensions on which the rules will be built;

• DR for the reference dimensions, the set of dimensions on which the counting will be based (customer ID);

• DI for the ignored dimensions, the set of dimensions which are not taken into account in the mining process.

Each tuple c = (d1, . . . , dn) can thus be written as c = (i, r, a, t) with i being the restriction on DI of c, r its restriction on DR, a the restriction on DA, and t the restriction on DT .

Given a cube DC, the set of all tuples in DC having the same value r on DR is called a block and we denote the set of blocks from cube DC by BDC,D R . Thus, each block Br in BDC,D R is identified by the tuple r that defines it.

During the mining of multidimensional sequential patterns, the set DR identifies the blocks of the data cube to be considered when computing the support. For this reason, this set is called reference. The support of a sequence is the proportion of blocks embedding it. Note that with usual sequential patterns, and sequential patterns from [START_REF] Pinto | Multi-dimensional sequential pattern mining[END_REF], this set is reduced to one dimension (cid in [START_REF] Pinto | Multi-dimensional sequential pattern mining[END_REF]). Besides, the set DA describes the analysis dimensions, so patterns defined by these dimensions will be found in the multidimensional sequential pattern mining. Note that with usual sequential patterns mining, we only consider a unique analysis dimension corresponding for instance to the products purchased or the web pages visited. Finally, set DI describes the ignored dimensions, which are used neither to define the date, nor the blocks, and which are not present within the patterns mined.

In our running example, we consider DI = ∅, DR = {C}, DT = {D} and DA = {A, CH, P }.

According to the dimension set partition, a multidimensional item e is a m-tuple defined over the set of the m DA dimensions. We consider e = (d1, d2, . . . , dm) where di ∈ Dom(Di) ∪ { * }, ∀Di ∈ DA and where * stands for the wild-card value. For instance, (Y oung, Golf, Bike) and ( * , W alking, * ) are two multidimensional items defined with respect to three analysis dimensions.

A multidimensional itemset i = {e1, . . . , e k } is a non-empty set of multidimensional items. According to the notion of itemset, two comparable items cannot appear in the same itemset. For instance, {(Y oung, T ennis, car)(Old, * , bike)} is a multidimensional itemset whereas {(M, T ennis, * ), (M, * , * )} cannot be an itemset since (M, T ennis, * ) ⊂ (M, * , * ).

A multidimensional sequence ς = i1, . . . , i l is a non-empty ordered list of multidimensional itemsets. For instance, ς 1 = {(Y oung, * , car), ( * , golf, * )}{(Y oung, M usic, guitar)} is a multidimensional sequence. A multidimensional sequence can be included into another one.

Definition 1 (Sequence inclusion).

A multidimensional sequence ς = a1, . . . , a l is said to be a subsequence of

ς ′ = b1, . . . , b l ′ if there are integers 1 ≤ j1 ≤ j2 ≤ . . . ≤ j l ≤ l ′ such that a1 ⊆ bj 1 , a2 ⊆ bj 2 , . . . , a l ⊆ bj l .
For instance, the sequence ς 1 = {(Y oung, * , car), ( * , golf, * )} {(Y oung, M usic, guitar)} is a subsequence of the sequence We consider that each block defined over DR contains one multidimensional data sequence, which is identified by that block. A block supports a sequence ς if ς is a subsequence of the data sequence identified by that block.

Let us define the support of a multidimensional sequence as the number of blocks defined over DR containing this sequence. Given a user-defined minimal support threshold, denoted σ (0 ≤ σ ≤ 1), the goal of multidimensional sequential pattern mining is to extract all the sequences S in DC such that support(S) ≥ σ.

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). We note that even in this classical case, the number of frequent sequential patterns discovered from a database can be huge. The problem is worse in the case of multidimensional patterns since the multidimensional framework produces more patterns than the classical framework.

UNEXPECTED MULTIDIMENSIONAL SE-QUENTIAL RULES 4.1 Overview

Our goal is to extract unexpected rules which are often hidden by common rules with high support. The main idea, in this paper, is to use wild-card values in the if-part of a common rule. We want to instantiate at least one wild card value in the antecedent of a common rule in order to detect a different and unexpected conclusion.

Let CR be a common rule (frequent and confident):

CR : P → Q
where P and Q are two multidimensional sequences.

According to common rule CR, an unexpected rule U R is an unfrequent and confident rule as follow: U R : P specialized → Q ′ P specialized is an instantiation of P . At least one wild-card value from P has been instantiated with an analysis dimension domain value.

Q ′ is different from Q. U R is unfrequent but confident.
Before introducing the formal definition of unexpected multidimensional sequential rules, it is necessary to formalize multidimensional sequential rule concept, the instantiation of wild-card values in the if-part and the difference of conclusions.

Multidimensional Sequential Rules

Let α = i1, i2, . . . i k , i k+1 , . . . , in be a multidimensional sequence where each ij represents a multidimensional itemset. A multidimensional sequential rule R is an implication: R : i1, i2, . . . i k → i k+1 , . . . , in As for association rules, the relevance of a multidimensional rule is indicated by its support and its confidence. The support of R is equal to:

support(R) = support( i1, i2, . . . i k , i k+1 , . . . , in )
The confidence of R is equal to:

Conf (R) = support( i1, i2, . . . i k , i k+1 , . . . , in ) support( i1, i2, . . . i k )

Specification of wild-carded premises

In order to discover unexpected multidimensional sequential rules, we have to instantiate wild-carded premises of common rules.

We define the following functions :

• * λ (x) such that * λ (x) = x • ai λ such that ai λ (x) =  ai if x = ai ∅ otherwise
These functions are associated with the dimension values of a multidimensional item. Thus, for a multidimensional item C = (t1, t2, . . . , tm), we can construct the function C λ :

X = (x1, . . . , xm) → C λ (X) = (t1 λ (x1), t2 λ (x2), . . . , tm λ (xm))
As an example, we can construct from an item C = (a, * , c) the function C λ = (a λ , * λ , c λ ).

Definition 2 (Instance). Let C and X be two multidimensional items, X is said to be an instance of C if C λ (X) = X.

For instance, X = (a, b, c) is an instance of C = (a, * , c) since C λ (X) = X. We can denote that X is an instance of itself (X λ (X) = X).

Definition 3 (Pseudo-instance of an itemset).

Let i = {e1, e2, . . . , em} and i ′ = {e ′ 1 , e ′ 2 , . . . , e ′ m ′ } be two itemsets such that m ≤ m ′ , i is said to be a pseudo-instance of i ′ if there exist some integers

1 ≤ k1 ≤ k2 ≤ . . . ≤ km ≤ m ′ such that ∀ej ∈ i, e ′ k j λ (ej) = ej.
We use the term pseudo because itemset i can be smaller than i ′ . Besides, if they have the same size, we can use the term instance.

= i ′ 1 , i ′ 2 , . . . i ′ m ′
be two sequences such that m ≤ m ′ , s is said to be a pseudo-instance of s ′ if there exist some integers

1 ≤ k1 ≤ k2 ≤ . . . ≤ km ≤ m ′ such that ∀ij ∈ s, ij is a pseudo instance of i ′ k j .
As Discovering an unexpected rule amounts to the discovery of a sequential rule where adding some information in the premise modifies the consequent. So we have to define an instanciation operation in order to substitute some wild-card values (*) by some dimension domain values. This operation is a specification of at least one wild-carded item in a sequence s ′ according to its instance in a sequence s. This operation is defined as follows:

Definition 5 (Instantiation). Let s ′ and s be two sequences such that s is a pseudo-instance of s ′ , the function ι(s ′ , s) is the substitution of at least one item e ′ i in s ′ with an instance of e ′ i in s. ι : sequence × sequence → set of sequences ι(s ′ , s) → {s ′′ such that the following conditions hold} Instantiation operation does not return only one sequence but a set of sequences. This set can make its management non-trivial because of non-deterministic solution. However, we can produce a deterministic solution by greedily instantiating item by item.

• s ′′ is an instance of s ′ . • ∃ items e ′′ i ∈ s ′′ , e ′ i ∈

Difference in the conclusion

In order to discover unexpected rules, we have to find a different conclusion from the instantiated premise. The conclusion of a multidimensional sequential rule is also a sequence, so we have to define the difference between two sequences.

Definition 6 (Difference). Let s = i1, i2, . . . , i l and s ′ = i ′ 1 , i ′ 2 , . . . , i ′ l ′ be two sequences, s and s ′ are said to be different (s = s ′ ) if s s ′ and s ′ s.

Two sequences s and s ′ are not comparable if s is more specific or general than s ′ . If we consider that two comparable sequences are different, we may discover many unexpected rules where the conclusion of an unexpected rule is just a more specific sequence than the conclusion of the common rule. So we consider two sequences as being different if they have at least one different item and if they are not comparable. As an example, the sequences s1 = {(a1, b1)}{(a2, * )} and s2 = {(a1, b1)} are not different since s2 ⊂ s1. Sequences s1 and s3 = {(a2, b2)}{(a1, b2)(a2, b1)} are different since there is no relation between s1 and s3.

Unexpected Multidimensional Sequential Rules

We consider the following user-defined thresholds :

• minCR: the minimal support threshold for common rules,

• maxU R: the maximal support threshold for unexpected rules,

• minU R: the minimal support threshold for unexpected rules,

• minConf : the minimal confidence threshold (the same for all rules).

The threshold minCR represents the minimal support value above which a rule can be considered as frequent. The threshold minConf represents the minimal confidence value above which a rule can be considered as confident. We consider that a rule which is not frequent automatically cannot be a potential unexpected rules. In this way, we consider two thresholds, if the support of a rule is greater than maxU R, this rule is too "frequent" to be an unexpected rule. Indeed, we argue that unexpectedness is related to non frequent event. So we propose this threshold to highlight this difference. We can denote that maxU R can be equal to minCR.

In order to differentiate unexpectedness from noise, we introduce the threshold minU R. All patterns with support smaller than minU R are considered as noise.

Figure 2 illustrates the use of different support thresholds.

We consider that unexpected rules may occur enough in the data cube so that not to be considered as noise. Furthermore, the support of unexpected rules is weak enough not to be considered as a common rule.

A common rule CR is a frequent and confident rule as following : We consider only the instance CR's premise having a support greater than minCR:

CR : sα → s β s.t. supp(CR) > minCR and conf (RC) > minConf (1)
s ′ s.t. supp(s ′ ) > minCR and s ′ is an instance of sα (2)
An unexpected rule is a confident rule which premise is an instantiation of sα with s ′ and verifies support conditions:

U R : ι(sα, s ′ ) → sc s.t. minU R ≤ supp(U R) ≤ maxU R and sc = s β (3)
We have to verify if there is no common rule with premise sα. If there is such rule, U R is not considered as an unexpected rule.

V R : sα → sc s.t. conf (V R) < minConf and/or supp(RV ) < maxU R

We have defined unexpected multidimensional sequential rules.

In order to discover all of them, for each common rule RC (1), we have to discover the set of sequences S verifying (2), (3) and (4).

ALGORITHM

In this section, we define the algorithm for mining unexpected multidimensional sequential rules.

Algorithm 1 describes our approach. This algorithm is divided into three steps. First, multidimensional sequences are mined and stored in a prefix tree. Then, common rules are discovered in the prefix tree. Finally, the last step is about searching for unexpected rules.

Multidimensional sequences are mined according to support threshold minU R. These sequences are stored in a prefix tree. Subroutine getF reqSet() performs this extraction. We use a pattern growth based method to mine multidimensional sequences. Subroutine getF reqSet() is the most expensive operation of this algorithm. Indeed, it need several scans over the data cube DC to mine multidimensional sequences having a support greater than minU R. However, this subroutine can be called once with a lower support threshold. Then, from the returned prefix tree of multidimensional sequences, we can discover common rules and unexpected rules according to several parameter settings (minU R, maxU R, minConf and minCR). As an example, the sequence extraction can be performed during the night; the decision maker performs then several unexpected rule mining during the day.

Common rules are obtained by one scan on the tree. Subroutine getCR() only has to consider each node of tree f reqT ree once (one tree traversal). This subroutine returns the set of common rules with respect to confidence threshold minConf and support threshold minCR.

In the same way, f reqT ree is traversed to discover the set of unexpected rules. Nevertheless, mining unexpected multidimensional sequential rule set has also to consider the set of common rules (denoted CRS). Indeed, f reqT ree is traversed to find rules r : p → q where support and confidence conditions hold (minU R ≤ support(r) ≤ maxU R and conf (r) ≥ minConf ). To be considered as a potential unexpected rule, it is necessary to find a premise p ′ in common rule set CRS such that p is an instance of p ′ . In this case, rule r is potentially an unexpected multidimensional sequential rule. To check it, it is necessary to verify the nonexistence of a common rule p ′ → q. If this condition holds, r is added to the set of unexpected multidimensional sequential rules U RS. Otherwise, r is not an unexpected rule at all since r has the same consequent as a common rule (frequent and confident). The different operations on set CRS can be enhanced by using a more elaborated structure like hash tables with single or double hashing. • to customers characterized by their heating energy (Heating),

• by customers' relationship entities (Geography),

• on different supports (Support Of Offer) such as mailing or phoning,

• and at different dates (Time).

On this detailed table, we build a datacube structured by these 6 dimensions and the aggregated number of offers as a measure.

According to the dimension set partition, we consider one reference dimension (DR = {Geography}), one temporal dimension (DT = {Time}) and five analysis dimensions.

The measure is transformed and put in the analysis dimensions.

As an example, according to the common rule CR = {( * , In order to highlight the relevance of our approach, we report the behavior (runtime, number of mined unexpected rules, ratio of unexpected rules over rules) of our approach when a threshold (minU R, minConf ) changes.

Figure 5 shows the runtime of our approach for mining the data cube when the confidence changes for four different minU R values. This behavior is quite similar as observed on Fig. 8 where runtime is related to minUR changes according to four different confidence values. Indeed, when a threshold become lower, the number of unexpected rules (Figure 4 and 7) or potential unexpected rules increases. Indeed, the less thresholds are, the more space search is large.

Figure 6 shows the percentage of unexpected rules when the confidence changes. An an example, according to minU R = 0.375, only about 1% of rules such that their support is between minU R and maxU R are unexpected. When the confidence threshold becomes too low, this confidence does not represent a sufficient constraint and the percentage of unexpected rules become important. If Data Mining is about finding gems in a database, our approach is quite closed to this metaphor when the confidence threshold is enough constraining.

CONCLUSION AND FUTURE WORKS

In this paper, we define unexpected multidimensional sequential rules, by proposing to combine unexpectedness and time in order to mine such rules. The different concepts and the algorithm used to implement our approach are presented. Moreover, experiments on real data cube are reported and highlight the interest of our approach.

This work offers several perspectives. The efficiency of the extraction can be enhanced by discovering unexpected rules during pattern extraction and by directly using measure in the support counting. We should also take hierarchies into account in order to discover unexpected multidimensional sequential rules defined over several hierarchies level. We can also return the top k unexpected multidimensional sequential rules in order to focus on the most relevant ones. In order to generalize Suzuki's approach, we should duplicate the dimensions on DT in DA. Indeed, thanks to date, we can construct union between two sequences and then check if the conclusion becomes different.

Figure 1 :

 1 Figure 1: Cube DC

ς 2 =

 2 {(Y oung, * , car), ( * , golf, * )}{(Old, Surf ing, * )} {(Y oung, M usic, * )} , denoted by ς1 ⊆ ς2.

  For instance, {(a, b, c)} is a pseudo-instance of {(a, * , c), ( * , b, b)} and {(a, b, c), ( * , b, b)} is an instance of {(a, * , c), ( * , b, b)} since they have the same size. Definition 4 (Pseudo-instance of a sequence). Let s = i1, i2, . . . im and s ′

  an example, {(a, b, c)(a, * , d)}{(a, b, * )(b, * , * )} is a pseudo-instance of {(a, b, c)(a, * , d), (d, e, f )}{(a, * , * )(b, * , * )} .

For

  instance, ι( {(a, * , c), (e, f, * )}{( * , c, d)} , {(a, b, c)} ) is equal to the sequence {(a, b, c), (e, f, * )}{( * , c, d)} . The wild-card value of the item (a, * , c) has been instantiated by the value b according to its instance (a, b, c).

Figure 2 :

 2 Figure 2: Different Support Thresholds

F

  LU X, * , * , * )}{( * , F LU X, * , Electrical, * )} → {( * , * , * , Electrical, * )} , the rule U R = {(BIEN, F LU X, * , * , * )}{( * , F LU X, * , Elec trical, * )} → {(BIEN,FLUX, * , Electrical, * )} is an unexpected rule.

Figure 4 :

 4 Figure 4: #Unexpected Rules over minConf (maxU R = 0.8)

Figure 5 :

 5 Figure 5: Runtime over Confidence (maxU R = 0.8)

Figure 6 :

 6 Figure 6: Percentage of Unexpected Rules over minConf (maxU R = 0.8)

  Figure 7: #Unexpected Rules over minU R Threshold (maxU R = 0.8)

Figure 8 :

 8 Figure 8: Runtime over minU R Threshold (maxU R = 0.8)

  s ′ and ei ∈ s such that ei is an instance of e ′

	i and e ′′ i = [ei/e ′ i ] where [ei/e ′ i ] is the
	substitution of e ′ i by ei.

  Algorithm 1: Mining Unexpected Multidimensional Sequential Rules Data: DC, DA, DT , DR, minCR, maxU R, minU R, minConf Result: The set U RS of unexpected multidimensional sequential rules begin F reqT ree ← getF reqSeq(DC, D A , D R , D T , minU R) CRS ← getCR(F reqT ree, minCR, minConf ) U RS ← ∅ foreach rule r : p → q ∈ f reqT ree s.t. minU R ≤ supp(r) ≤ maxU R and conf (r) ≤ minConf do if ∃ premise p ′ ∈ CRS s.t. p is an instance of p ′ then if ∃seq x s.t. ι(p

	Figure 3: Example of customers detailed table
	#OFFER OFFER STATE_OF_	HEATING GEOGRAPHY SUPPORT_OF_	TIME
			OFFER			OFFER
	1	BIEN	Flux	Electrical	Bordeaux	Phoning	Jan 2003
	2	BIEN	Flux	Gas	Montpellier	Mailing	Mar 2005
	3	RENO	Stock	Electrical	Lyon	Phoning	Nov 2004
	4	DCS	Flux	Gas	Lyon	Phoning	Feb 2003
	5	RENO	Stock	Fuel	Paris	Mailing	Jan 2004
	…	…	…	…	…	…	…
	One tuple of Tab. 3 is related to one EDF marketing of-
	fer (Offer), at different states (State Of Offer) such as
	current (FLUX ) or closed (STOCK ), proposed:
							In this section, we report experiments performed on real
							data. They aim at showing the relevance of our approach.
							They have been performed on data issued from EDF (Elec-
							tricité de France) marketing context and are in the scope
							of a research collaboration between EDF Research and De-
							velopment and LIRMM laboratory. Indeed, EDF, the main
							French energy supplier and electricity producer, has resort
							to On-Line Analytical Processing (OLAP) applications to
							analyze internal and external data. In this context, EDF
							and LIRMM are developing efficient tools to discover unex-
							pected temporal evolution within OLAP data.
							We consider the simplified detailed table (Fig. 3), describing
							marketing activity on a very large EDF customer database
							(about 30 millions of residential customers).
							The simplified database scheme is:
							Marketing Offer (#Offer, Offer, State Of Offer,
							Heating, Geography, Support Of Offer, Time)

′ , x) → p and supp(x) ≥ minCR then if ∄p ′ → q ∈ CRS then U RS ← U RS ∪ {r} end

6. EXPERIMENTS


Sarra Ayouni
email: sarra.ayouni@fst.rnu.tn

Sadok Ben Yahia

Anne Laurent
email: laurent@lirmm.fr

Pascal Poncelet
email: poncelet@lirmm.fr

Fuzzy Gradual Patterns: What Fuzzy Modality For What Result?

Gradual Patterns allow to express frequent patterns like "the older an employee, the higher his/her income". After having been extensively used for fuzzy command (e.g., "the closer the wall, the harder the break"), they are currently grasping the attention of the data mining community, where the focus is put on the scalability of the methods when addressing very large databases (e.g. biology). However, it is often the case that the information is not contained at the upper and lower boundaries (min/max), but rather hidden in-between. For instance, the most interesting rule could be "the closer the age of an employee to 46, the higher his/her income". In this paper, we introduce several methods for automatically defining fuzzy modalities and we compare the results obtained when considering the various solutions.

Introduction

Gradual patterns are of the form "the more/less A 1 , . . ., the more/less A k " [START_REF] Dubois | Gradual inference rules in approximate reasoning[END_REF], [START_REF] Galichet | Imprecise specification of ill-known functions using gradual rules[END_REF]. For instance, "the older an employee, the higher his/her income" refers to such a pattern. They have been recently reintroduced in the literature as one of the types of patterns that data mining techniques can be of help to discover [START_REF] Berzal | An alternative approach to discover gradual dependencies[END_REF], [START_REF] Jorio | Fast extraction of gradual association rules: A heuristic based method[END_REF], [START_REF] Jorio | Mining frequent gradual itemsets from large databases[END_REF], [START_REF] Laurent | Graank: Exploiting rank correlations for extracting gradual dependencies[END_REF].

Standing within fuzzy settings, fuzzy gradual patterns are of the form "the more/less A 1 is F 1 . . ., the more/less A k is F k " [START_REF] Dubois | Gradual inference rules in approximate reasoning[END_REF], [START_REF] Galichet | Imprecise specification of ill-known functions using gradual rules[END_REF], as for instance in "the more an employee is almost 46 years old, the more his/her income is almost 37,000 euros per year", where almost 46 years old and almost 37,000 euros are fuzzy sets described by their respective membership functions. The fuzzy set theory, introduced by Zadeh [START_REF] Zadeh | Fuzzy sets[END_REF], allows to deal with natural language and to imprecise concepts like young or almost X years old. A membership function µ of a fuzzy set A is an application from the domain D of the attribute being considered (e.g., ages from 0 to 125) to [0, 1]. Considering a value x ∈ D, µ(x) ranges in [0, 1] and indicates to which extent x belongs to the fuzzy set A.

Discovering fuzzy gradual patterns can be of benefit to many application areas. For instance, in biology, it is of paramount interest to retrieve the information that "the closer the expression of gene i to .32, the closer the expression of gene j to -.12".

In this paper, we aim at building fuzzy modalities that seems to be the most relevant. Instead of building a complete partition, we rather focus on a fuzzy modality that is meant to gather the identity of the numerical attribute being considered. For doing this, our idea is to define fuzzy modalities that describe to which extent the value of an attribute is close to this attribute's median.

For instance, Table 1 displays sample data that describes people regarding their identifier, their age, their annual income, and the number of their cars. Unfortunately, it is not possible to retrieve gradual patterns from this table. However, if considering the fuzzy modalities almost 46 years old and almost 37,000 euros as sketched by Figure 1, the table can be transformed as showed by Table 2. Thus, the pattern "the more an employee is almost 46 years old, the more his/her income is almost 37,000 euros per year" appears to be true: the lines can be ordered considering the list of id < 1, 5, 2, 3, 4 > and it can be seen that the pairs of values (degree of age almost 46, degree of income almost 37,000) appears to be ordered by a precedence order. Indeed, if we consider that a tuple t precedes another tuple t (denoted as t t ) whenever all the components can be ranked in this order, then we have that tuples defined by projecting the database on (degree of age almost 46, degree of income almost 37,000) are ordered: (0, 0) (0, .25) (.25, .25) (.5, .5) (1, 1). modalities that allow to discover relevant fuzzy gradual patterns. We thus begin by recalling below some preliminaries about gradual patterns and automatic fuzzy partition building, before introducing our contribution for building fuzzy modalities in the framework of fuzzy gradual patterns.

Our objective is then to automatically retrieve fuzzy

Experiments have been carried on real datasets and are reported in the penultimate section. The last section concludes this paper and sketches some issues for future work.

Related Work

In this section, we present an overview of approaches dealing with gradual patterns. We also present an overview of different strategies for building fuzzy membership functions.

Gradual Patterns

Gradual patterns are extracted from datasets described over m attributes (X 1 , . . ., X m ) defined on numerical domains dom(X i ). A dataset D is a set of rows (m-tuples) in dom(X 1 )×, . . ., × dom(X m ). In the case of fuzzy data, the X i attributes are fuzzy linguistic variables associated to linguistic values defined through fuzzy sets. Let us consider an attribute corresponding to the speed of vehicles. In the crisp case, it contains the numerical values of the measured speeds. Whereas, in the fuzzy case, it will be associated to linguistic variables, e.g., "slow", "normal", and "fast". These linguistic variables or modalities are defined by their membership degrees (according to a membership function) indicating the extent to which their speeds belong to each modality. Extracting gradual patterns grasped the interest of many researchers [START_REF] Jorio | Fast extraction of gradual association rules: A heuristic based method[END_REF], [START_REF] Jorio | Mining frequent gradual itemsets from large databases[END_REF], [START_REF] Hüllermeier | Implication-based fuzzy association rules[END_REF], [START_REF] Hüllermeier | Association rules for expressing gradual dependencies[END_REF], [START_REF] Laurent | Graank: Exploiting rank correlations for extracting gradual dependencies[END_REF] and various definitions were proposed to assess the support value of a gradual pattern.

A gradual pattern or gradual itemset is defined as a nonempty set of several gradual items. A gradual item is defined as a pair of an attribute and a variation * ∈ {≤, ≥}. Let A be an attribute, then the gradual item (A, ≥) means that the attribute A is increasing. It can be interpreted by "the more A". Here, the attribute A can be crisp or fuzzy. For instance (Speed, ≥) is a crisp gradual item, as well as (Fast Speed, ≥) which is a fuzzy gradual item.

A gradual rule, denoted by M ⇒ M , is defined as a pair of gradual itemsets on which a causality relationship is imposed. Different measures and semantics have been proposed to extract and assess such kind of rules. Nevertheless, many semantics have been formalized to define the cases where such a rule can be said to hold or not. The authors in [START_REF] Hüllermeier | Association rules for expressing gradual dependencies[END_REF] propose a method to extract so called gradual dependencies denoted by A t B. A linear regression analysis is performed on the contingency diagram depicted from the data set. The validity of the rule is assessed on the basis of the regression coefficients α, β of the line that approximates the points in the contingency diagram and the quality of the regression as given by the R 2 coefficient. A tendency rule contains one or more attributes in the condition part and only one in the conclusion part. When it contains many attributes in the condition part, the authors propose to use a logical conjunction modeled by means of a socalled t-norm. The gradual tendency is then understood as a covariance constraint between the aggregated membership degrees.

Another definition has been proposed in [START_REF] Berzal | An alternative approach to discover gradual dependencies[END_REF]. The semantics of a gradual dependence is quite different, since the authors only consider the fulfilment variation. The authors define a gradual dependence as being similar to a functional dependence. However, in a functional dependency, the equalities between the values are considered while in a gradual dependency the variations of degrees between two objects are of interest. According to [START_REF] Berzal | An alternative approach to discover gradual dependencies[END_REF], the gradual dependence A ⇒ B holds in a database D if ∀ o=(x, y) and o =(x , y ) ∈ D, A(x) < A(x ) implies B(y) < B(y ). It should be noted that this definition does not take into account any comparison between data rows. A new definition of gradual dependencies was proposed in [START_REF] Molina | Measuring variation strength in gradual dependencies[END_REF] using fuzzy association rules. The authors take into account the variation strength in the degree of fulfilment of an imprecise property by different objects. Hence, a gradual dependency holds in a database D if ∀ o=(x, y) and o =(x , y ) ∈ D, v * 1 (A(x), A(x )) implies v * 2 (B(y), B(y )), where v * is a variation degree of an attribute between two different rows. In both propositions [START_REF] Berzal | An alternative approach to discover gradual dependencies[END_REF] and [START_REF] Molina | Measuring variation strength in gradual dependencies[END_REF], the authors propose to build a modified data set D that contains as many rows as there are pairs of distinct objects in the initial data set D in order to identify such gradual dependencies.

Another definition was proposed in [START_REF] Jorio | Fast extraction of gradual association rules: A heuristic based method[END_REF]. As pointed out in the introduction, the support of a gradual itemset A * 1 1 , . . . , A * p p is defined as the maximal number of rows {r 1 , . . . , r l } for which there exists a permutation π such that

∀ j ∈ [1, l -1], ∀ k ∈ [1, p], it holds A k (r πj ) * k A k (r πj+1
). More formally, denoting L the set of all such sets of rows the support of a gradual itemset is defined as follows. Let s=A * 1 1 , . . . , A * p p be a gradual itemset, we have:

supp(s) = max L i ∈L |Li| |D|
The authors propose a heuristic to compute this support for gradual itemsets, in a levelwise process that considers itemsets of increasing lengths. The authors in [START_REF] Jorio | Mining frequent gradual itemsets from large databases[END_REF] propose the GRITE method 1 which is an efficient method based on the precedence graph and binary matrices for data representation.

In [START_REF] Laurent | Graank: Exploiting rank correlations for extracting gradual dependencies[END_REF], the authors proposed a novel definition of the support of gradual patterns based on rank correlation (concordant and discordant pairs of rows from the data). The authors use the same algorithm and data binary representation as cited above.

Another type of fuzzy gradual rules was proposed in [START_REF] Bouchon-Meunier | Strengthening fuzzy gradual rules through "all the more" clauses[END_REF]. The authors propose to mine gradual rules enriched with a clause introduced by the expression "all the more": such rules of the form "the more X is A, the more Y is B, all the more Z is C" offer additional precisions on the relation between the attributes. For instance the pattern "the closer the wall, the harder the brakes are applied, all the more the higher the speed" means that the pattern "the closer the wall, the harder the brakes are applied" is more true when the speed is high than when the speed is not high. It should be noted that many interpretations and computations could be proposed in this framework.

We focus below on the methods that have been proposed for building membership functions.

Building Fuzzy Modalities

In this respect, most of the methods build either a triangular, trapezoidal or gaussian function. If considering the problem of building a triangular membership function, then the problem will be to delimit the support and kernel of the fuzzy set. Let us consider that the support is defined 1. GRITE stands for GRadual ITemset Extraction.

0 1 U Membership degree µ Α X 1 X 2 X 3 Figure 2.

An example of a Triangular Membership Function

in the interval [x 1 x 3 ] and the kernel is {x 2 } (see Figure 2). The function is defined by:

µ A (x) =    x-x1 x2-x1 if x 1 ≤ x < x 2 x-x3 x2-x3 if x 2 ≤ x < x 3 0 otherwise
The values have to satisfy the following condition:

x 1 < x 2 < x 3
If considering the problem of building a trapezoidal membership function, then the support is defined in the interval [x 1 , x 4 ] and the kernel is [x 2 , x 3 ] (see Figure 3). The function is defined by:

µ A (x) =        x-x1 x2-x1 if x 1 ≤ x < x 2 1 if x 2 ≤ x < x 3 x-x4 x3-x4 if x 3 ≤ x < x 4 0 otherwise
The values have to satisfy the following condition:

x 1 < x 2 < x 3 < x 4
If considering the problem of building a gaussian membership function, then we consider a center x 2 and parameters x 2 and x 3 (see Figure 4). The function is defined by: Many methods were proposed in the literature to build fuzzy membership functions. These methods have been classified into four categories in [START_REF] Aladenise | Acquisition de connaissances imparfaites : mise en évidence d'une fonction d'appartenance[END_REF]: automatic methods, statistical and probabilistic methods, psychometric methods and geometric methods, as reviewed below.

µ A (x) = e ( x-x 2 w ) 0 1 U Membership degree µ Α X 1 X 2 X 3 X 4
2.2.1. Automatic Methods. Automatic methods to construct membership functions are based on a two-step process that first defines a primary membership function (e.g., by random) that is then adjusted in the second step.

The second step relies on an optimization performed by methods such as neural networks or evolutionary algorithms. Evolutionary algorithms are inspired by biological evolution (reproduction, selection, mutation) [START_REF] Goldberg | Genetic algorithms in search, optimization, and machine learning[END_REF], [START_REF] Holland | Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[END_REF]. They rely on a population that is enhanced step by step by combining the elements and by selecting the best ones. A fitness function must be defined in order to rank the elements regarding their performance. For instance, in the context of data mining, the aim may be to increase the number of large itemsets and/or rules discovered or their confidence [START_REF] Kaya | Utilizing genetic algorithms to optimize membership functions for fuzzy weighted association rules mining[END_REF], [START_REF] Alcalá-Fdez | Learning the membership function contexts for mining fuzzy association rules by using genetic algorithms[END_REF].

Regarding the problem of building membership functions, the elements of the population (i.e., the chromosomes) are randomly generated and each chromosome represents the parameters describing a membership function.

After the encoding step, these chromosomes undergo through a selection (individual solutions are selected through a fitness-based process) and reproduction steps. In this later step, a second population is generated from those selected through genetic operators (crossover, and mutation). This generational process is repeated until a termination condition has been reached (e.g., a number of runs, or a indicator that the membership function is satisfactory).

2.2.2. Clustering Methods. When using clustering, the membership functions are generated either during the process of the clustering [START_REF] Bezdek | Pattern Recognition with Fuzzy Objective Function Algorithms[END_REF], or on the basis of certain parameters diverted from the obtained clusters [START_REF] Fu | Finding fuzzy sets for the mining of fuzzy association rules for numerical attributes[END_REF]. In these methods, membership functions can represent the adequacy rate of each element to the cluster to which it is attached. It can also be the distance between every element and the center of gravity of its cluster.

Statistical and Psychometric Methods.

Statistic methods rely on the study of the distribution of the values to build the membership function. For instance, histograms are used and a smooth function is designed on them. "Yes-No" methods consist in asking every member of the population a question having yes or no answer. The membership degree of an element to a fuzzy set is built as being equal to the number of the "yes" answers [START_REF] Gaines | Fuzzy and probability uncertainty logics[END_REF], [START_REF] Giles | The concept of grade of membership[END_REF], [START_REF]Are grades of membership probabilities? Fuzzy Sets Syst[END_REF]. In a statistical method based on set estimation, the degrees of membership functions are directly given by individuals. The question "what is the degree of membership of an element x in the fuzzy set A?" is repeated several times in different moments to one or several person(s). A variable is used to register the obtained answers. The membership function is then defined by a conditional distribution function f (y/x) where y is a variable registering the answers [START_REF] Wang | From the fuzzy statistics to the falling random subsets[END_REF].

Discovering Fuzzy Gradual Patterns

We recall that our goal is to compare the gradual patterns obtained on numerical databases when applying the existing approaches on fuzzified data. We aim at discovering patterns including linguistic terms that describe values that are inbetween the two extremes of the minimum and maximum values of the attributes, e.g., patterns like "the closer the age of an employee to 46, the closer his/her income to 37,000 euros per year".

Building the Fuzzy Modalities

We study here some means to define the fuzzy set. Several possibilities are explored.

It is important to note that it would be hardly possible to ask an expert to design a fuzzy partition or fuzzy modality on all the attributes of a database, for instance a genomic database containing the expression of thousands of genes. The expert would then been asked to define a single fuzzy description that will be applied on the whole dataset, which we argue to be non relevant.

Here the aim is rather to obtain automatically the best fuzzy modality. However, it is very difficult to define what would be this best fuzzy modality. We argue here that this modality must allow to discover some interesting patterns that would not have been retrieved by existing methods, either because no partition was defined, as in the crisp approaches [START_REF] Jorio | Fast extraction of gradual association rules: A heuristic based method[END_REF], or because the fuzzy partition being considered is pre-defined and not automatically built [START_REF] Berzal | An alternative approach to discover gradual dependencies[END_REF].

Moreover, this fuzzy description must cover the whole universe and must be interpretable as "almost v" in order to simplify the reading of the fuzzy gradual patterns to be extracted.

Finally, our method must remain scalable, as this is one of the main challenges of fuzzy data mining.

We thus focus on a method which is based on the definition of a function describing a smooth transition between all the values. As the values are split around the median, we consider the median as the central point of our fuzzy description and we then describe all the values depending on the extent to which they are similar to the median. For this purpose, several possibilities are explored. We may consider then several ways to build membership functions, for instance gaussian membership function or triangular membership function where the center is the median and the width is the whole universe in cover all the values. However, there is no difference in the ranking of the values when we consider triangular or gaussian functions if considering the same value to the center as they are piecewise monotonic.

It should be noted that we aim at retrieving the most interesting fuzzy modality for every attribute. It can thus be the case that two attributes describe the same type of data (e.g., expression of gene), but that the fuzzy modality is not the same one for both of them. This allows to distinguish our method to classical ones and to be as close as possible to the dataset. Some other methods could be considered to build the membership functions, as for instance genetic programming. However, these methods are very time consuming and could not scale on databases containing thousands of attributes.

The median may be replaced by the average of the variable or by the most frequent value (although this is usually hardly reasonable on quantitative attributes), and we may consider the standard deviation for defining the width of the support, instead of covering all the universe. However, this would not change much the algorithms described below.

Algorithms

Our method stands within a pre-treatment step, that can be applied before all existing algorithms for gradual pattern discovery. The runtimes are thus not an indicator of the quality of the method building the fuzzy modalities but they must remain as short as possible. This pre-treatment has been implemented using the R software 2 , which makes it possible to efficiently manage large databases within reasonable runtimes.

The algorithm 1 proceeds in two steps as described below. The first one (i.e.; Algorithm 2) corresponds to fuzzy modalities building and Algorithm 3 refers to classical algorithm to extract gradual patterns, as that given in [START_REF] Jorio | Mining frequent gradual itemsets from large databases[END_REF]. The BuildF uzzM od function as described in Algorithm 2 computes the key parameters of the fuzzy modality of each attributes of the original dataset. After that it returns the membership degree of each value of the attribute to the corresponding fuzzy modality that has been found.

Experimental Results

Our approach has been tested on several databases. One of them contains data on NBA players 3 containing 17 dimensions (player regular season). A second one describes the behavior of 500 genes for a biological study on breast cancer, while a third one describes data about wine [START_REF] Frank | UCI machine learning repository[END_REF] (13 columns) where the class attribute has been removed.

All these three datasets are pre-treated in order to replace every attribute by a fuzzy set describing to which extent the initial value is close to the median. For instance, Table 3 displays the new attributes for database wine. The value being considered is the median. Table 4 displays the number of patterns discovered with and without considering a fuzzy modality for two different values of minimum support. In fact, crisp gradual patterns are of the form "the more/less A 1 , . . ., the more/less A k ", while fuzzy gradual patterns are of the form "the more/less A 1 is almost X, . . ., the more/less A k is almost Y ". In order to discover crisp patterns, the GRITE method [START_REF] Jorio | Mining frequent gradual itemsets from large databases[END_REF] has been used. It can be seen that our method allows to retrieve some patterns that could not be extracted before.

Table 3 reports some of the patterns discovered using Return F our method. For the wine database, attributes Total phenols and Flavanoids are not linked with the crisp approach, while building a fuzzy modality allows to discover that they are correlated when considering The more/less the Total phenols is almost 98 and The more/less the Flavanoids is almost 2.355. Based on this correlation, patterns containing 9 attributes have been built.

For the NBA database, no pattern was built for a minimum support of 100% while 275 patterns were built considering the fuzzy modalities. For instance, attributes 1 and 12 have been retrieved to be correlated: the more Games Played is almost 122, the less Field Goals Attempted is almost 626. To sum up, we can conclude that our approach allows to discover potentially useful hidden knowledge in large datasets that crisp approach can not discover.

Conclusion

In this paper, we propose a method for automatically building fuzzy modalities from numerical datasets in order to build fuzzy gradual patterns. Many perspectives are linked to this work. Other methods and statistics may be used. The goal may also be changed in order, for instance, to build the fuzzy membership function that allows to retrieve the highest number of rules, or the most discriminant rules for classifying data (e.g., wine). Moreover, each attribute may be divided into several fuzzy subsets, for building a complete fuzzy partition and exploiting it. Genetic programming may also be used to automatically build the partition, as done for fuzzy association rules. Finally, user preferences may be taken into account, together with closed patterns, so as retrieving as few patterns as possible, in order to avoid drowning the user in the resulting patterns while retrieving the most relevant ones.

Figure 1 .

 1 Figure 1. Fuzzy Modalities over Age and Income attributes

Figure 3 .Figure 4 .

 34 Figure 3. An example of a Trapezoidal Membership Function

Algorithme 1 3 D 4 F

 134 Mining Fuzzy Gradual Patterns 1 INPUT:D Input Database, ς MinSup 2 OUTPUT: F Set of frequent gradual patterns ← BuildF uzzM od(D) ← MineGradualPatterns(D',ς) 5 Return F

2 OUTPUT: D Transformed Database 3 foreach 7 / 10 foreach 11 foreach 12 D

 237101112 Attribute A in D do 4 TmpMin ← Min(D.A) 5 TmpMax ← Max(D.A) 6 TmpCenter ← Median(D.A) Row r in D do Attribute A in D do [A, r] ← MFunc(D[A,r])

Algorithme 3 1 INPUT: D Input Database, ς MinSup 2 OUTPUT : F 3 F 4 foreach 6 F

 312:346 MineGradualPatterns -Mining Gradual Patterns Set of frequent gradual patterns ← Pairs of Attributes Such that Support ≥ ς Size k in [3, ...] do 5 Build candidates from Frequent of Size k -1 ← F {Gradual Patterns containing k attributes such that Support ≥ ς} 7 endforeach 8

Table 1 .

 1 Sample Data

	Id Age Income (keuros) Nb of Cars
	1	32	30	1
	2	43	40	2
	3	48	37	2
	4	46	39	3
	5	57	34	3

Table 2 .

 2 Transforming the Sample Data

	Id	Age	Income (keuros) Nb of Cars
		Almost 46	Almost 37	Almost 2
	1	0	0	0.5
	2	.25	.25	1
	3	.5	.5	1
	4	1	1	0.5
	5	0	.25	0.5

Table 3 .

 3 Wine Gradual Items Before and After Pretreatment Less the Malic Acid The more/less the Malic Acid is almost 13.05 Ash The More/Less the Ash The more/less the Ash is almost 1.865 Alcalinity of ash The More/Less the Alcalinity of ash The more/less the Alcalinity of ash is almost 2.36 Magnesium The More/Less the Magnesium The more/less the Magnesium is almost 19.5

	Attribute	Classical Description	Fuzzy Description
	Malic Acid The More/Total phenols The More/Less the Total phenols	The more/less the Total phenols is almost 98
	Flavanoids	The More/Less the Flavanoids	The more/less the Flavanoids is almost 2.355
	Nonflavanoid phenols	The More/Less the Nonflavanoid phenols	The more/less the Nonflavanoid phenols is almost 0.34
	Proanthocyanins	The More/Less the Proanthocyanins	The more/less the Proanthocyanins is almost 1.555
	Color intensity	The More/Less the Color intensity	The more/less the Color intensity is almost 4.69
	Hue	The More/Less the Hue	The more/less the Hue is almost 0.965
	OD280/OD315 of diluted wines The More/Less the OD280/OD315 of diluted wines The more/less the OD280/OD315 of diluted wines is almost 2.78
	Proline	The More/Less the Proline	The more/less the Proline is almost 673.5
	Algorithme 2 BuildFuzzMod -Building Fuzzy Modalities

1 INPUT: D Input Database

Table 4 .

 4 Number of Patterns Extracted w.r.t. the M inSup Value

		wine crisp wine fuzzy	nba crisp nba fuzzy
	1	23	38,259	0	275
	0.8	149	797,148	0	19,040

Acknowledgment. The authors would like to thank Lisa DI JORIO for providing the source code to compute the gradual patterns.