Willy Ugarte

Patrice Boizumault

Samir Loudni

Bruno Crémilleux

Alban Lepailleur

Mining (Soft-) Skypatterns using Constraint Programming

Within the pattern mining area, skypatterns enable to express a userpreference point of view according to a dominance relation. In this paper, we deal with the introduction of softness in the skypattern mining problem. First, we show how softness can provide convenient patterns that would be missed otherwise. Then, thanks to Constraint Programming, we propose a generic and efficient method to mine skypatterns as well as soft ones. Finally, we show the relevance and the effectiveness of our approach through experiments on UCI benchmarks and a case study in chemoinformatics for discovering toxicophores.

Introduction

Discovering useful patterns from data is an important field in data mining for data analysis and is used in a wide range of applications. Many approaches have promoted the use of constraints to focus on the most promising knowledge according to a potential interest given by the final user. As the process usually produces a large number of patterns, a determined effort has been made towards a better understanding of the fragmented information conveyed by the patterns and to produce pattern sets i.e. sets of patterns satisfying properties on the whole set of patterns [De Raedt and Zimmermann, 2007]. Using the dominance re-lation is a recent trend in constraint-based data mining to produce useful pattern sets [START_REF] Soulet | Mining dominant patterns in the sky[END_REF].

Skyline queries [START_REF] Börzsönyi | The skyline operator[END_REF] enable to express a user-preference point of view according to a dominance relation. Such queries have attracted considerable attention due to their importance in multi-criteria decision and are usually called "Pareto efficiency or optimality queries" In a multidimensional space where a preference is defined for each dimension, a point p i dominates another point p j if p i is better (i.e., more preferred) than p j in at least one dimension, and p i is not worse than p j on every other dimension. However, while this notion of skylines has been extensively developed and researched for database applications, it has remained unused until recently for data mining purposes. Computing skylines of patterns from a database is clearly much harder than computing skylines in database applications due to the huge difference between the size of search spaces (we explain this issue in Section 5). The inherent complexity on computing skylines of patterns may explain the very few attempts in this direction.

A pioneering work [START_REF] Papadopoulos | Skygraph: an algorithm for important subgraph discovery in relational graphs[END_REF] proposed a technique to extract skyline graphs maximizing two measures. Recently, the notion of skyline queries has been integrated into the constraint-based pattern discovery paradigm to mine skyline patterns (henceforth called skypatterns) [START_REF] Soulet | Mining dominant patterns in the sky[END_REF]. Briefly, given a set of measures, skypatterns are patterns based on a Pareto-dominance relation for which no measure can be improved without degrading the others. As an example, a user may prefer a pattern with a high frequency, large length and a high confidence. In this case, we say that a pattern x i dominates another pattern x j if f req(x i ) ≥ f req(x j ), size(x i ) ≥ size(x j ), con f idence(x i ) ≥ con f idence(x j ) where at least one strict inequality holds. Given a set of patterns, the skypattern set contains the patterns that are not dominated by any other pattern (we formally introduce the notions in the following sections). Skypatterns are interesting for a twofold reason: they do not require any threshold on the measures and the notion of dominance provides a global interest with semantics easily understood by the user.

Nevertheless, skypatterns queries, like other kinds of queries, suffer from the stringent aspect of the constraint-based framework. Indeed, a pattern satisfies or does not satisfy the constraints. But, what about patterns that slightly miss a constraint? A pattern, close to the frontier of the dominance area, could be interesting although it is not a skypattern. In the paper, we formally introduce soft skypatterns. Note that there are very few works such as [Bistarelli andBonchi, 2007, Ugarte et al., 2012] dealing with softness into the mining process.

The contributions of this paper are the following. First, we introduce the notion of soft skypattern. Second, we propose a flexible and efficient approach to mine skypatterns as well as soft ones thanks to the Dynamic CSP (Constraint Satisfaction Problems) framework [START_REF] Verfaillie | Constraint solving in uncertain and dynamic environments: A survey[END_REF]. Our proposition benefits from the recent progress on cross-fertilization between data mining and Constraint Programming (CP) [De Raedt et al., 2008, Khiari et al., 2010[START_REF] Guns | Itemset mining: A constraint programming perspective[END_REF]. The common point of all these methods is to model in a declarative way pattern mining as CSP, whose resolution provides the complete set of solutions satisfying all the constraints. We show how the (soft-) skypatterns mining problem can be modeled and solved using Dynamic CSP. A major advantage of the method is to improve the mining step during the process thanks to constraints dynamically posted and stemming from the current set of candidate skypatterns. Moreover, the declarative side of the CP framework leads to a unified framework handling softness in the skypattern problem. Finally, the relevance and the effectiveness of our approach is highlighted through a case study in chemoinformatics for discovering toxicophores and experiments on UCI benchmarks.

This paper is organized as follows. Section 2 presents the context and defines skypatterns. Section 3 introduces soft skypatterns. Section 4 presents our flexible and efficient CP approach to mine skypatterns as well as soft ones. We review some related work in Section 5. Finally, Section 6 describes experiments on UCI benchmarks and reports in depth a case study in chemoinformatics by performing both a performance and a qualitative analysis.

The skypattern mining problem

Context and definitions

Let I be a set of distinct literals called items. An itemset (or pattern) is a non-empty subset of I . The language of itemsets corresponds to L I = 2 I \ / 0. A transactional dataset T is a multiset of patterns of L I . Each pattern (or transaction) is a database entry. Table 1 (left side) presents a transactional dataset T where each transaction t i gathers articles described by items denoted A,. . . ,F. The traditional example is a supermarket database in which each transaction corresponds to a customer and every item in the transaction to a product bought by the customer. An attribute (price) is associated to each product (see Table 1, right side).

Constraint-based pattern mining aims at extracting all patterns x of L I satisfying a query q(x) (conjunction of constraints) which is usually called theory [START_REF] Mannila | Levelwise search and borders of theories in knowledge discovery[END_REF]: T h(q) = {x ∈ L I | q(x) is true}. A common example is the frequency measure leading to the minimal frequency constraint. The latter provides patterns x having a number of occurrences in the dataset exceeding a given minimal threshold min f r : freq(x) ≥ min f r . There are other usual measures for a pattern x:

• size(x) is the number of items that x contains.

• area(x) = f req(x) × size(x).

• min(x.val) is the smallest value of the item values of x for attribute val.

• max(x.val) is the highest value of the item values of x for attribute val.

• average(x.val) is the average value of the item values of x for attribute val.

• mean(x) = (min(x.val) + max(x.val))/2.

Considering the dataset described in Table 1, we have: freq(BC)=5, size(BC)=2 and area(BC)=10. Moreover, average(BCD.price)=30 and mean(BCD.price)=25.

In many applications, it is highly appropriated to look for contrasts between subsets of transactions, such as toxic and non toxic molecules in chemoinformatics (see Section 6). We will use the growth rate, a well-known contrast measure [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF]:

Definition 1 (Growth rate). Let T be a database partitioned into two subsets D 1 and D 2 . The growth rate of a pattern x from D 2 to D 1 is:

m gr (x) = |D 2 | × f req(x, D 1 ) |D 1 | × f req(x, D 2 )
The collection of patterns contains redundancy w.r.t. measures. Given a measure m, two patterns x i and x j are said to be equivalent if m(x i ) = m(x j ). A set of equivalent patterns forms an equivalent class w.r.t. m. The largest element w.r.t. the set inclusion of an equivalence class is called a closed pattern.

Definition 2 (Closed pattern). A pattern

x i ∈ L I is closed w.r.t. a measure m iff ∀ x j ∈ L I , x j x i , ⇒ m(x j ) = m(x i ).
The set of closed patterns is a compact representation of the patterns (i.e we can derive all the patterns with their exact value for m from the closed ones).

This definition is straightforwardly extended to a set of measures M, thus we define the constraint closed M (x) stating that x must be a closed pattern w.r.t all the measures of M.

Skypatterns

Skypatterns have been recently introduced by [START_REF] Soulet | Mining dominant patterns in the sky[END_REF]. Such patterns enable to express a user-preference point of view according to a dominance relation. As an example, a user may prefer a pattern with a high frequency, large length and a high confidence. In this case, we say that a pattern x i dominates another pattern x j if f req(x j ) ≥ f req(x i ), size(x j ) ≥ size(x i ), con f idence(x j ) ≥ con f idence(x i ) where at least one strict inequality holds. Given a set of patterns, the skypattern set contains the patterns that are not dominated by any other pattern. Fig. 1: Skypatterns extracted from the dataset shown in Table 1.

Given a set of measures M, if a pattern x j is dominated by another pattern x i according to all measures of M, x j is considered as irrelevant. This idea is at the core of the notion of skypattern.

Definition 3 (Pareto Dominance). Given a set of measures M, a pattern x i dominates another pattern x j with respect to M (denoted by x i M x j ), iff ∀m ∈ M, m(x i ) ≥ m(x j ) and ∃m ∈ M, m(x i ) > m(x j ).

Consider the example in Table 1. For M={ f req, area}, pattern BCD dominates pattern BC since f req(BCD)= f req(BC)=5 and area(BCD)>area(BC). For M={ f req, size, average}, pattern BDE dominates pattern BCE since f req(BDE) = f req(BCE)=4, size(BDE)=size(BCE)=3 and average(BDE.price)>average(BCE.price).

Definition 4 (Skypattern operator). Given a pattern set P ⊆ L I and a set of measures M, a skypattern of P with respect to M is a pattern of P not dominated in P with respect to M. The skypattern operator Sky(P,M) returns all the skypatterns of P with respect to M: Sky(P,M) = {x i ∈ P | ∃x j ∈ P, x j M x i }.

The skypattern mining problem is thus to evaluate the query Sky(L I , M). For instance, from the data set in Table 1 and with M={ f req, size}, Sky(L I , M) = {ABCDEF, BCDEF, ABCDE, BCDE, BCD, B, E} (see Figure 1).

The shaded area is called the forbidden area, as it cannot contain any skypattern. The other part is called the dominance area. The edge of the dominance area (bold line) marks the boundary between these two areas. [START_REF] Soulet | Mining dominant patterns in the sky[END_REF] have proposed an efficient approach taking benefit of theoretical relationships between pattern condensed representations and skypatterns and making the process feasible when the pattern condensed representation can be extracted. Nevertheless, this method can only use a crisp dominance relation.

The soft skypattern mining problem

This section introduces the softness within the skypattern mining problem. The skypatterns suffer from the stringent aspect of the constraint-based framework. In order to introduce softness in this context, we propose two kinds of soft skypatterns: the edge-skypatterns that belongs to the edge of the dominance area (see Section 3.1) and the δ -skypatterns that are close to this edge (see Section 3.2).

The key idea is to strengthen the dominance relation in order to soften the notion of non dominated patterns. The goal is to capture valuable skypatterns occurring in the forbidden area.

Edge-skypatterns

Similarly to skypatterns, edge-skypatterns are defined according to a dominance relation and a Sky operator. These two notions are reformulated as follows:

Definition 5 (Strict Dominance). Given a set of measures M, a pattern x i strictly dominates a pattern x j with respect to M (denoted by x i M x j ), iff ∀m ∈ M, m(x i ) > m(x j ).

Definition 6 (Edge-skypattern operator). Given a pattern set P ⊆ L I and a set of measures M, an edge-skypattern of P, with respect to M, is a pattern of P not strictly dominated in P, with respect to M. The edge-skypattern operator Edge-Sky(P, M) returns all the edge-skypatterns of P with respect to M: Edge-Sky(P, M) = {x i ∈ P | ∃x j ∈ P, x j M x i } Fig. 2: Edge-skypatterns extracted from the dataset shown in Table 1. Fig. 3: δ -skypatterns (that are not edge ones) extracted from the dataset (Table 1).

Given a set of measures M, the edge-skypattern mining problem is thus to evaluate the query Edge-Sky(P, M). Figure 2 depicts the 28=7+(4+8+3+4+2) edgeskypatterns extracted from the example in Table 1 for M={ f req, size}. Obviously, all edge-skypatterns belong to the edge of the dominance area, and seven of them are (hard) skypatterns (see Figure 1).

Proposition 1. For two patterns x i and x j , x i M x j =⇒ x i M x j .

Proposition 2. For a pattern set P and a set of measures M, Sky(P, M) ⊆ Edge-Sky(P, M).

Proofs are obvious and thus omitted.

δ -skypatterns

In many cases the user may be interested in skypatterns expressing a trade-off between the measures. The δ -skypatterns address this issue. Let 0 < δ ≤ 1.

Definition 7 (δ -Dominance). Given a set of measures M, a pattern x i δ -dominates another pattern x j with respect to M (denoted by

x i δ M x j ), iff ∀m ∈ M, (1 -δ ) × m(x i ) > m(x j ).
Definition 8 (δ -Skypattern operator). Given a pattern set P ⊆ L I and a set of measures M, a δ -skypattern of P with respect to M is a pattern of P not δ -dominated in P with respect to M. The δ -skypattern operator δ -Sky(P, M) returns all the δskypatterns of P with respect to M: δ -Sky(P, M) = {x i ∈ P | ∃x j ∈ P :

x j δ M x i }.
The δ -skypattern mining problem is thus to evaluate the query δ -Sky(P, M). There are 38 (28+10) δ -skypatterns extracted from the example in Table 1 for M={ f req, size} and δ =0.25. Figure 3 only depicts the 10 δ -skypatterns that are not edge-skypatterns.

Intuitively, the δ -skypatterns are close to the edge of the dominance relation, the value of δ expressing the maximal relative distance between a skypattern and this border.

Proposition 3. For two patterns x i and x j , x i δ M x j =⇒ x i M x j . Proposition 4. For a pattern set P and a set of measures M, Edge-Sky(P, M) ⊆ δ -Sky(P, M).

Proofs are obvious and thus omitted.

To conclude, given a pattern set P ⊆ L I and a set of measures M, the following inclusions hold: Sky(P, M) ⊆ Edge-Sky(P, M) ⊆ δ -Sky(P, M).

Mining (soft-) skypatterns using CP

This section describes how the skypattern and the soft skypattern mining problems can be modeled and solved using Dynamic CSP [START_REF] Verfaillie | Constraint solving in uncertain and dynamic environments: A survey[END_REF]. A major advantage of this approach is to improve the mining step during the process thanks to constraints dynamically posted and stemming from the current set of the candidate skypatterns. The purpose of adding constraints dynamically is to enlarge the forbidden area until it could not be expanded (Section 4.4 provides a detailed example).

Each time a solution is found, we dynamically post a new constraint leading to reduce the search space. This process stops when we cannot enlarge the forbidden area. Moreover, the declarative side of the CP framework easily enables us to manage constraints providing several kinds of softness and leads to a unified framework handling softness in the skypattern mining problem.

Our proposition benefits from the recent progress on cross-fertilization between data mining and CP [De Raedt et al., 2008, Khiari et al., 2010[START_REF] Guns | Itemset mining: A constraint programming perspective[END_REF]. The common point of all these methods is to model in a declarative way pattern mining as CSP, whose resolution provides the complete set of solutions satisfying all the constraints. The implementation of our approach has been carried out in Gecode1 .

Sections 4.1 and 4.2 briefly recall the notions of CSP and Dynamic CSP in Constraint Programming. Section 4.3 describes how mining skypatterns can can be performed using Dynamic CSP. Section 4.4 provides an example. Section 4.5 shows that soft skypatterns can be mined in the same way as skypatterns. Section 4.6 presents the boolean pattern encoding. Finally, Section 4.7 is devoted to closedness constraints.

CSP

A CSP P=(X , D, C ) is defined by:

• a finite set of variables X = {x 1 , x 2 , . . . , x k }, • a domain D, which maps every variable x i ∈ X to a finite set of values D(x i ), • a finite set of constraints C .
The problem is to find a mapping from variables to values such that each variable x i is mapped to a value in its domain D(x i ) and such that all constraints of C are satisfied.

Algorithm 1 shows how a CSP can be solved using a depth-first search. D and C denote respectively the current domains and the current set of constraints. In each node of the search tree, the algorithm branches by assigning values to a variable that is unfixed (line 7). It backtracks when a violation of constraints is found, i.e. at least one domain is empty (line 2). The search is further optimized by carefully choosing the variable that is fixed next (line 6); for instance, heuristics dom/deg selects the variable x i having the smallest ratio between the size of its current domain and the number of constraints it occurs.

Algorithm 1 Depth-First(D) 1: D ← Filter(D,C) 2: if there exists x i ∈ X s.t. D(x i ) is empty then 3: return failure 4: end if 5: if there exists x i ∈ X s.t. |D(x i )| > 1 then 6: Select x i ∈ X s.t. |D(x i )| > 1 7: for all v ∈ D(x i ) do 8: Depth-First(D ∪ {x i -> {v}}) 9:
end for 10: else 11:

Manage-Solution(D,C) 12: end if

The main concept used to speed-up the search is filtering (procedure Filter(D,C) at line 1). Filtering reduces the domains of variables such that the domain remains locally consistent. A solution is obtained (line 11) when each domain D(x i ) is reduced to a singleton and all constraints are satisfied. For CSP, Manage-Solution(D,C) simply consists in outputting the obtained solution D.

Dynamic CSP

A Dynamic CSP [START_REF] Verfaillie | Constraint solving in uncertain and dynamic environments: A survey[END_REF]] is a sequence P 1 , P 2 , ..., P n of CSP, each one resulting from some changes in the definition of the previous one. These changes may affect every component in the problem definition: variables (addings or removals), domains (value addings or removals), constraints (addings or removals).

For our approach, variables and domains remain the same and the changes are only performed by adding new constraints. Solving such Dynamic CSP can be considered as a backtracking algorithm that, each time a new solution is found, imposes new constraints φ (X ) that survive backtracking, stating that next solutions should verify both the current set of constraints and φ (X ). Dynamic constraints φ (X ) are added to the constraint store (see Algorithm 2) in order to hold in all the branches of the search tree, surviving backtracking. (Note that C is a global variable to all calls to the Depth-First procedure).

Algorithm 2 Manage-Solution(D,C) 1: Output solution D 2: C ← C ∪ {φ (X )}

Mining skypatterns using Dynamic CSP

This subsection describes our CP approach for mining both skypatterns and soft skypatterns. Constraints on the dominance relation are dynamically posted during the mining process and softness is easily introduced using such constraints. The purpose of adding constraints dynamically is to enlarge the forbidden area until it could not be expanded.

Variable x will denote the (unknown) skypattern we are looking for. Changes are only performed by adding new constraints (see Section 4.2). So, we consider the sequence P 1 , P 2 , ..., P n of CSP where each P i = ({x}, L , q i (x)) and:

q 1 (x) = closed M (x) q i+1 (x) = q i (x) ∧ φ (s i , x)
where s i is the first solution to query q i (x) First, the constraint closed M (x) states that x must be a closed pattern w.r.t all the measures of M (see Definition 2). It allows to reduce the number of redundant patterns2 .

Then, the constraint φ (s i , x) ≡ ¬(s i M x) states that the next solution (which is searched) will not be dominated by s i . Using a short induction proof, we can easily argue that query q i+1 (x) looks for a pattern x that will not be dominated by any of the patterns s 1 , s 2 , . . ., s i .

Each time the first solution s i to query q i (x) is found, we dynamically post a new constraint φ (s i , x), based on the values of the measures for s i , leading to reduce the Trans.

Items search space. This process stops when we cannot enlarge the forbidden area (i.e. there exits n s.t. query q n+1 (x) has no solution).

t 1 A B C D E F t 2 A B C D E F t 3 A B t 4 D t 5 A C t 6 E Item A B C D E F
For skypatterns, φ (s i , x) states that ¬(s i M x) (see Definition 3):

φ (s i , x) ≡ m∈M m(s i ) < m(x) ∨ m∈M m(s i ) = m(x)
However, the n extracted patterns s 1 , s 2 , . . ., s n are not necessarily all skypatterns. Some of them can only be "intermediate" patterns simply used to enlarge the forbidden area. A post processing step must be performed to filter all candidate patterns s i that are not skypatterns, i.e. for which there exists s j (1 ≤ i < j ≤ n) s.t. s j dominates s i . So mining skypatterns is achieved in a two-steps approach:

1. Compute the set S = {s 1 , s 2 , . . . , s n } of candidates using Dynamic CSP. 2. Filter all patterns s i ∈ S that are not skypatterns.

While the number of candidates (n) could be very large, it remains reasonablysized in practice for the experiments we conducted (see Table 3 and Table 4 for UCI benchmarks, and Table 5 for the case study in chemoinformatics for discovering toxicophores).

Example

This subsection gives an example of computing skypatterns using a Dynamic CSP and shows how the forbidden area is successively enlarged. We consider the dataset depicted in Table 2 and the set of measures M ={freq, area}.

Let P 1 be the associated Dynamic CSP (see Section 4.3). P 1 = ({x}, L , q 1 (x)) where query q 1 (x) = closed M (x). Its first solution is pattern s 1 = ABCDEF (with freq(s 1 ) = 2 and area(s 1 ) = 12), see Figure 4a.

So, we consider query q 2 (x) =closed M (x) ∧ ¬(s 1 M x) stating that we are looking for a closed pattern x not dominated by s 1 = ABCDEF. Its first solution is pattern s 2 = AB (with freq(s 2 ) = 3 and freq(s 2 ) = 6), see Figure 4b. Then, the next query is q 3 (x) = closed M (x) ∧ ¬(s 1 M x) ∧ ¬(s 2 M x) stating that we are looking for a closed pattern x neither dominated by s 1 nor s 2 . Its first solution is pattern s 3 = AC (with freq(s 3 ) = 3 and area(s 3 ) = 6), see Figure 4c.

The next query is q 4 (x) = q 3 (x) ∧ ¬(s 3 M x) whose first solution is s 4 = A (see Figure 4d) and then query q 5 (x) = q 4 (x) ∧ ¬(s 4 M x). q 5 (x) has no solution since the dominated area cannot be enlarged. So, the process ends for n = 5.

In this example, note that all extracted patterns are skypatterns (i.e., there is no intermediate patterns). The CSP system did not generate solution that does not satisfy the dominance relation. Experiments in the next section provide examples with intermediate patterns.

Mining soft skypatterns using Dynamic CSP

Soft skypatterns are processed exactly the same way as skypatterns (see Section 4.3). Each kind of soft skypatterns has its own constraint φ (s i , x) according to its relation of dominance.

For edge-skypatterns, φ (s i , x) states that ¬(s i M x) (see Definition 5):

φ (s i , x) ≡ m∈M m(s i ) ≤ m(x) For δ -skypatterns, φ (s i , x) states that ¬(s i δ M x) (see Definition 7): φ (s i , x) ≡ m∈M (1 -δ ) × m(s i ) ≤ m(x)
However, the n extracted patterns s 1 , s 2 , . . ., s n are not necessarily all soft skypatterns. Some of them can only be "intermediate" patterns simply used to enlarge the forbidden area. So, a post processing is required as for skypatterns (see Section 4.3). Mining soft skypatterns is also achieved in a two-steps approach:

1. Compute the set S = {s 1 , s 2 , . . . , s n } of candidates using Dynamic CSP. 2. Filter all patterns s i ∈ S that are not soft skypatterns.

Once again, the number of candidates (n) remains reasonably-sized in practice for the experiments we conducted (see Table 4 for UCI benchmarks, and Table 5 for toxicophores).

Pattern encoding

We now introduce the model of a pattern that can be provided to the constraint programming system. Let d be the 0/1 matrix where, for each transaction t and each item i, (d t,i = 1) iff (i ∈ t) Pattern variables are set variables represented by their characteristic function with boolean variables. [De Raedt et al., 2008[START_REF] Guns | Itemset mining: A constraint programming perspective[END_REF]] model an unknown pattern x and its associated dataset T by introducing two sets of boolean variables:

• {X i | i ∈ I } where (X i = 1) iff (i ∈ x), • {T t | t ∈ T } where (T t = 1) iff (x ⊆ t).
Each set of boolean variables aims at representing the characteristic function of the unknown pattern. The relationship between x and T is modeled by posting reified constraints stating that, for each transaction t, (T t = 1) iff x is a subset of t:

∀t ∈ T , (T t = 1) ⇔ ∑ i∈I X i × (1 -d t,i ) = 0 (1)
A reified constraint associates a 0/1 variable to a constraint reflecting whether the constraint is satisfied (value 1) or not (value 0). Such constraints are useful for expressing propositional formulas over constraints and for expressing that a certain number of constraints hold.

Reified constraints do not enjoy the same level of propagation as simple constraints, but if the solver deduces T t = 1 (resp. T t = 0), then the sum must be equal to 0 (resp. must be different from 0). The propagation is also performed, in a same way, from the sum constraint toward the equality constraint. Using these reified constraints, some measures are easy to encode: f req(x) = ∑ t∈T T t and size(x) = ∑ i∈I X i . The minimal frequency constraint f req(x) ≥ θ (where θ is a threshold) is encoded by the constraint ∑ t∈T T t ≥ θ .

Closedness constraints

This subsection provides the encoding of closedness constraints (see Definition 2).

Let M={freq}, the closedness constraint ensures that a pattern x has no superset with the same frequency. So, x is a closed pattern w.r.t. the measure freq iff:

∀i ∈ I , (X i = 1) ⇔ ∑ t∈T T t × (1 -d t,i ) = 0 (2)
Let M={min}, and val be an attribute (e.g. see Table 1 where val=price). Let min(x.val) be the smallest value of the item values of x for attribute val (see Section 2.1). If item i belongs to x, then its value for attribute val (i.val) must be greater than or equal to the minimal value min(x.val). Conversely, if i.val is greater than or equal to min(x.val), i must belong to x (if not, x would not be maximal for inclusion). So, x is a closed pattern w.r.t. the measure min iff: ∀i ∈ I , (X i = 1) ⇔ i.val ≥ min(x.val)

(3)

There are equivalences between closed patterns according to measures: the closed patterns w.r.t mean and min are the same and the closed patterns w.r.t area, growth-rate and frequency are the same [START_REF] Soulet | Mining dominant patterns in the sky[END_REF]. The constraint closed M (x) states that x must be a closed pattern w.r.t M (the closed patterns w.r.t M gather the closed patterns w.r.t each measure of M i.e. x is closed w.r.t M iff x is closed for at least one measure m ∈ M).

Related Work

The notion of dominance that we introduced in Section 2.2 is at the core of the skyline processing and the recent notion of skypattern that integrates into the pattern discovery process the idea of skylines.

Computing skylines is a derivation from the maximal vector problem in computational geometry [Matousek, 1991], the Pareto frontier [START_REF] Kung | On finding the maxima of a set of vectors[END_REF] and multiobjective optimization [Steuer, 1992].

Since its rediscovery within the database community by [START_REF] Börzsönyi | The skyline operator[END_REF]], several methods have been developed for answering skyline queries [START_REF] Börzsönyi | The skyline operator[END_REF], Papadias et al., 2005, Papadias et al., 2008, Tan et al., 2001]. These methods assume that tuples are stored in efficient tree data structures, such as B-Tree (allowing search and sequential access in logarithmic time) or R-Tree (for indexing multi-dimensional information). Alternative approaches have also been proposed towards helping the user in selecting most significant skylines. For example, [START_REF] Lin | Selecting stars: The k most representative skyline operator[END_REF] measure this significance by means of the number of points dominated by a skyline.

Introducing softness for skylines. [START_REF] Jin | Mining thick skylines over large databases[END_REF] have proposed thick skylines to extend the concept of skyline. A thick skyline is either a skyline point p i , or a point p j dominated by a skyline point p i and such that p j is close to p i . In this work, the idea of softness is limited to metric semi-balls of radius ε>0 centered at points p i , where p i are skylines.

Computing skypatterns is different from computing skylines. Skyline queries focus on the extraction of tuples of the dataset and assume that all the elements are in the dataset, while the skypattern mining task consists in extracting patterns which are elements of the frontier defined by the given measures. The skypattern problem is clearly harder because the search space for skypatterns is much larger than the search space for skylines:

O(2 |I | ) instead of O(|T |) for skylines.
There are only very few works dealing with skypatterns. As already said, [START_REF] Soulet | Mining dominant patterns in the sky[END_REF] have proposed an approach taking benefit of theoretical relationships between pattern condensed representations and skypatterns and making the process feasible when the pattern condensed representation can be extracted. To the best of our knowledge, it is the single work addressing a large set of measures. Nevertheless, this method only uses a crisp dominance relation. Other works address specific measures. A trade-off between quality and diversity measures is introduced in [van Leeuwen and Ukkonen, 2013] for subgroup discovery. [START_REF] Papadopoulos | Skygraph: an algorithm for important subgraph discovery in relational graphs[END_REF] and [START_REF] Shelokar | Mosubdue: a pareto dominance-based multiobjective subdue algorithm for frequent subgraph mining[END_REF] are interested in graph analysis. [START_REF] Papadopoulos | Skygraph: an algorithm for important subgraph discovery in relational graphs[END_REF] discover subgraphs maximizing the number of vertices and the edge connectivity whereas [START_REF] Shelokar | Mosubdue: a pareto dominance-based multiobjective subdue algorithm for frequent subgraph mining[END_REF] adapt the framework of the subdue method to the extraction of graph patterns satisfying the Pareto dominance on two to three measures.

CP for computing the Pareto frontier. [Gavanelli, 2002] has proposed an algorithm that provides the Pareto frontier in a CSP. This algorithm is based on the concept of nogoods and uses spatial data structures (quadtrees) to arrange the set of nogoods. This approach deals for computing skylines and cannot be directly applied to skypatterns. The application is not immediate since several different patterns may correspond to a same point (they all have the same values for the considered measures). As experiments show the practical efficiency of our approach, we have considered that adding [Gavanelli, 2002] to a constraint solver would require an important development time compared to the expected benefits.

Experimental study

In this section, we report an experimental study on several benchmarks and a case study from chemoinformatics.

Experiments on UCI benchmarks

This section compares our approach (noted CP+SKY) with Aetheris, which is the only other method able to mine skypatterns [START_REF] Soulet | Mining dominant patterns in the sky[END_REF]. As our proposal, Aetheris proceeds in two steps. First, condensed representations of the whole set of patterns (i.e. closed patterns according to the considered set of measures) are extracted. Then, the sky operator (see Definition 4) is applied.

Experiments we performed on UCI datasets show that:

1. CP+SKY and Aetheris obtain similar CPU-times for mining skypatterns (see Section 6.1.2). 2. As the number of extracted skypatterns is very low, mining soft skypatterns enables to emphasize interesting knowledge that could be missed by skypatterns (see Section 6.1.3).

Experimental protocol

We carried out experiments on several datasets from the UCI repository3 . We considered two sets of measures: M 1 ={ f requency, growth-rate, area} and M 2 = { f requency, max, area, mean}. Measures using numeric values, like mean, were applied on attribute values that were randomly generated within the range [0..1]. For each method, reported CPU-times include both steps. All experiments were conducted on a computer running Linux operating system with a core i3 processor at 2.13 GHz and a RAM of 4 GB. Aetheris CPU-times are obtained by the programs kindly provided by A. Soulet and used in [START_REF] Soulet | Mining dominant patterns in the sky[END_REF]. The implementation of CP+SKY was carried out in Gecode by extending the CP-based patterns extractor developed by [START_REF] Khiari | Constraint programming for mining n-ary patterns[END_REF].

Mining skypatterns

Table 3 compares CP+SKY with Aetheris on several datasets for the two sets of measures M 1 and M 2 . For each dataset, and each set of measures, we report:

• the number4 of skypatterns, First, the number of skypatterns is always very low. There are less than 40 skypatterns for M 1 except for vehicle (57) and hypo (209). It is the same for M 2 , for which the number of skypatterns does not exceed 106, thus highlighting the interest of extracting soft skypatterns. Second, on most of the datasets (except for german and hypo for M 1 , and german, hypo and mushroom for M 2 ), required CPU-times for mining all the skypatterns are very low (less than one minute). Third, CP+SKY and Aetheris perform quite similarly on most of the datasets. For the dataset german (resp. vehicle), with M 1 , CP+SKY is 4.5 (resp. 2.5) faster than Aetheris, while on the three datasets abalone, hypo and mushroom, Aetheris is clearly better (with a factor of 3).

Dataset M 1 = { f req,
Figure 5a and Figure 5b provide two scatter plots of CPU-times for CP+SKY and Aetheris (see Table 3). Each point represents a dataset: its x-value (log-scale) is the CPU-time for CP+SKY to mine it, its y-value (log scale) is the CPU-time for Aetheris to mine it. A point at the beginning of an axis means that the considered approach requires 1 second or less to mine it.

Figure 5a and Figure 5b show that CP+SKY and Aetheris obtain similar CPUtimes. For M 1 , CP+SKY is faster than Aetheris on three datasets (e.g., points above the red line, i.e. y=x). On the other hand, Aetheris clearly dominates CP+SKY on three datasets (e.g. points near the right border of the figure). For the other datasets, the two approaches are quite similar (e.g., points near the red line and points in the bottom of the figure). For M 2 , most of the points tend to concentrate in the vicinity of the red line: CP+SKY and Aetheris solve many datasets within similar CPU-times. Moreover, the gap between the two methods on datasets hypo and mushroom for M 2 is greatly reduced with respect to M 1 .

These results show that our approach, though integrating softness, obtains similar performances as Aetheris for mining skypatterns.

Mining soft skypatterns

This section shows the feasibility of mining soft skypatterns on UCI Benchmarks (for these experiments, parameter δ was set to 5%). As our proposal is the only approach able to mine soft skypatterns, it is no longer compared with Aetheris. Table 4 reports, for each dataset, and each set of measures:

• for edge-skypatterns: their number5 , the number of candidates and the required CPU-time, • for δ -skypatterns: their number6 , the number of candidates and the required CPU-time.

Finally, our CP-based approach enables to mine both skypatterns and soft ones in a same way. This cannot be performed by [START_REF] Soulet | Mining dominant patterns in the sky[END_REF] that can only handle a crisp dominance relation.

Case study: discovering toxicophores

Toxicology is a scientific discipline involving the study of the toxic effects of chemicals on living organisms. A major issue in chemoinformatics is to establish re- lationships between chemicals and a given activity (e.g., CL507 in ecotoxicity). Chemical fragments8 which cause toxicity are called toxicophores and their discovery is at the core of prediction models in (eco)toxicity [Auer andBajorath, 2006, Poezevara et al., 2011]. The aim of this present study, which is part of a larger research collaboration with the CERMN Lab, a laboratory of medicinal chemistry, is to investigate the use of softness for discovering toxicophores.

Dataset M 1 = { f req,

Experimental protocol

The dataset is collected from the ECB web site9 . For each chemical, the chemists associate it with hazard statement codes (HSC) in 3 categories: H400 (very toxic, CL50 ≤ 1 mg/L), H401 (toxic, 1 mg/L < CL50 ≤ 10 mg/L), and H402 (harmful, 10 mg/L < CL50 ≤ 100 mg/L). We focus on the H400 and H402 classes. The dataset T consists of 567 chemicals, 372 from the H400 class and 195 from the H402 class. The chemicals are encoded using 1,450 frequent closed subgraphs previously extracted from T10 with a 1% relative frequency threshold.

In order to discover patterns as candidate toxicophores, we use both measures typically used in contrast mining [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF] such as the growth rate since toxicophores are linked to a classification problem with respect to the HSC and measures expressing the background knowledge such as the aromaticity or rigidity because chemists consider that this information may yield promising candidate toxicophores. Our method offers a natural way to simultaneously combine in a same framework these measures coming from various origins. We briefly sketch these measures and the associated threshold constraints. Growth rate. When a pattern has a frequency which significantly increases from the H402 class to the H400 class, then it stands a potential structural alert related to the toxicity: if a chemical has, in its structure, fragments that are related to a toxic effect, then it is more likely to be toxic. Emerging patterns embody this natural idea by using the growth-rate measure (see Definition 1). Frequency. Real-world datasets are often noisy and patterns with low frequency may be artefacts. The minimal frequency constraint ensures that a pattern is representative enough (i.e., the higher the frequency, the better is). Aromaticity. Chemists know that the aromaticity is a chemical property that favors toxicity since their metabolites can lead to very reactive species which can interact with biomacromolecules in a harmful way. We compute the aromaticity of a pattern as the mean of the aromaticity of its chemical fragments. We denote by m a the aromaticity measure of a pattern.

Redundancy is reduced by using closed skypatterns which are an exact condensed representation of the whole set of skypatterns (see Footnote 2). We consider four sets of measures: M 1 , M 2 , M 3 and M 4 (see Table 5). For δ -skypatterns, we consider two values: δ =10% and δ =20%. The extracted skypatterns and soft skypatterns are made of molecular fragments. To evaluate the presence of toxicophores in their description, an expert analysis leads to the identification of well-known environmental toxicophores. A few examples are depicted in Table 6. Table 5: Analysis of (soft-) skypattern mining on ECB dataset.

Mining the (soft-) skypatterns

This section evaluates the interest of using (soft-) skypatterns for discovering toxicophores. • for edge-skypatterns: their extra-number (see footnote #7), the number of candidates and the required CPU-time, • for δ -skypatterns: their extra-number (see footnote #8), the number of candidates and the required CPU-time.

CP+SKY outperforms Aetheris in terms of CPU-times (see Table 5a). Moreover, the number of candidates generated by our approach remains small compared to the number of closed patterns computed by Aetheris. Thanks to constraints added dynamically, our CP approach enables to drastically reduce the number of candidates.

Moreover, increasing the number of measures leads to a higher number of (soft-) skypatterns, particularly for high values of δ . In fact, a pattern rarely dominates all other patterns on the whole set of measures. Nevertheless, in our experiments, the number of soft skypatterns remains reasonably small. For edge-skypatterns, there is a maximum of 144 patterns, while for δ -skypatterns, there is a maximum of 1, 724 patterns (for δ = 20%). Moreover, regarding the CPU-times, our approach is very effective: the soft skypatterns computation requires less than 30 minutes.

Qualitative Analysis

In this section, we analyse qualitatively the (soft-) skypatterns by evaluating the presence of toxicophores in their description, according to well-known environmental toxicophores.

For M 1 ={growth-rate, f requency}, soft skypatterns enable to efficiently detect well-known toxicophores emphasized by skypatterns, while for M 2 ={growthrate, aromaticity} and M 4 ={growth-rate, f requency, aromaticity}, soft skypatterns enable to discover (new) interesting toxicophores that would not be detected by skypatterns. (a) Growth rate and frequency measures (M 1 ). Figure 6a shows the distribution of (soft-) skypatterns for M 1 .

• Skypatterns. Only 8 skypatterns are found, and 3 well-known toxicophores are emphasized. Two of them are aromatic compounds, namely the chlorobenzene (pattern p 1 : {Clc}) and the phenol rings (pattern p 2 : {c1(ccccc1)O}). The contamination of water and soil by organic aromatic chemicals is widespread as a result of industrial applications ranging from their use as pesticides, solvents to explosives and dyestuffs. Many of them may bioaccumulate in the food chain and have the potential to be harmful to living systems including humans, animals, and plants. The third one, the organophosphorus moiety (pattern p 3 : {OP, OP=S}) is a component occurring in numerous pesticides. • Soft skypatterns confirm the trends given by skypatterns. However, the chlorosubstituted aromatic rings (e.g. pattern p 4 : {Clc(ccc)c, Clcccc}), and the organophosphorus moiety (e.g. pattern p 5 : {OP(=S)O), COP(=S)O}) are detected by the edge-skypatterns and by the δ -skypatterns. Indeed, several patterns containing these toxicophores are extracted. In order to partition the (soft-) skypatterns, we used the k-means clustering method with the euclidean metric. The computed solution consists in k=3 distinct clusters. (b) Growth rate and aromaticity measures (M 2 ). As results for M 2 and M 3 are similar, Figure 7a only reports the distribution of the (soft-) skypatterns for M 2 .

• Skypatterns for M 2 are less informative than the ones mined for M 1 .

• Soft skypatterns lead to the discovery of several different aromatic rings. In fact, the nature of these chemicals can vary in function of i) the presence/absence of heteroatoms (e.g. N, S), ii) the number of rings, and iii) the presence/absence of substituents. Regarding the two kinds of soft skypatterns:

-edge-skypatterns lead to the extraction of (i) nitrogen aromatic compounds: indole (pattern p 1 : {ncc, c1cccccc1}) and benzoimidazole (pattern p 2 : {ncnc, c1ccccc1}), (ii) S-containing aromatic compounds: benzothiophene (pattern p 3 : {ccs, c1ccccc1}), (iii) aromatic oxygen compounds: benzofurane (pattern p 4 : {coc, c1ccccc1}), and (iv) polycyclic aromatic hydrocarbons: naphthalene (pattern p 5 : {c1ccc2ccccc2cc1}).

δ -skypatterns complete the list of the aromatic rings which were not enumerated during the extraction of the skypatterns, namely biphenyl (pattern p 6 : {c1ccccc1c2ccccc2}).

In order to partition the (soft-) skypatterns, we used once again the k-means clustering method with the euclidean metric. The computed solution consists in k=3 distinct clusters. Figure 7b highlights these clusters:

1. Cluster #1 is made of 3 skypatterns and 6 edge ones, with very high growth rate and aromaticity equal to zero. They correspond to organophosphorus moieties. 2. Cluster #2 contains only δ -skypatterns. From a chemical point of view, it emphasizes several different aromatic rings. 3. Cluster #3 comprises 2 skypatterns and several edges ones which correspond to nitrogen aromatic compounds.

(c) Growth rate, frequency and aromaticity measures (M 4 ). The most interesting results are provided using M 4 (see Figure 8). Table 6 gives a classification of all the (soft-) skypatterns extracted according to well-known toxicophores. The introduction of the softness (via soft skypatterns) enables to discover interesting toxicophores previously discussed that would not be detected by skypatterns.

Conclusion

We have introduced the notion of soft skypattern and proposed a flexible and efficient approach to mine skypatterns as well as soft ones thanks to Dynamic CSP. Moreover, the declarative side of the CP framework easily enables us to manage constraints providing several kinds of softness and leads to a unified framework handling softness in the skypattern problem. Finally, the relevance and the effectiveness of our approach has been highlighted through experiments on UCI benchmarks and a case study in chemoinformatics for discovering toxicophores.

In the future, we would like to study the introduction of softness on other tasks such as clustering, study the contribution of soft skypatterns for recommendation and extend our approach to skycubes. Another direction is to improve the solving stage by designing a one-step method: each time a new solution s i is found, all candidates that are dominated by s i can be removed (see Section 4.3). Another idea is to hybridize our CP approach with local search methods [START_REF] Drugan | Stochastic pareto local search: Pareto neighbourhood exploration and perturbation strategies[END_REF] to improve the efficiency of the method.

  (a) 1st solution: s 1 = ABCDEF. (b) 2nd solution: s 2 = AB. (c) 3rd solution: s 3 = AC. (d) Last solution: s 4 = A.

Fig. 4 :

 4 Fig. 4: Solving the toy example using Dynamic CSP.

  (a) M 1 = { f requency, growth-rate, area} (b) M 2 = { f requency, max, area, mean}

Fig. 5 :

 5 Fig. 5: Scatter plots comparing CPU-times on UCI datasets.

  (a) Distribution of the (soft-) skypatterns. (b) Clustering using k-means (k=3).

Fig. 6 :

 6 Fig. 6: Analysing the (soft-) skypatterns for M 1 .

  Figure 6b highlights these clusters: (a) Distribution of the (soft-) skypatterns. (b) Clustering using k-means (k=3).

Fig. 7 :

 7 Fig. 7: Analysing the (soft-) skypatterns for M 2 .

Fig. 8 :

 8 Fig. 8: Analysing the (soft-) skypatterns for M 4 .

Table 1 :

 1 Transactional dataset T .

	Trans.	Items
	t 1	B	E F
	t 2	B C D
	t 3 A		E F	Item A B C D E F
	t 4 A B C D E	Price 30 40 10 40 70 55
	t 5	B C D E
	t 6	B C D E F
	t 7 A B C D E F

Table 2 :

 2 Example of a toy dataset.

  Density of a dataset:The ratio of the number of present items in the dataset (i.e. ∑

							growth rate, area}	M 2 = { f req, max, area, mean}
						CP+SKY	Aetheris		CP+SKY	Aetheris
		# items	# transactions	density	# of Skypatterns	# of Candidates	Time (sec)	# of Closed Patterns	Time (sec)	# of Skypatterns	# of Candidates	Time (sec)	# of Closed Patterns	Time (sec)
	abalone	28 4,178 0.321 29 2,669 11	38,996 1 44 5,094 16	30,800	1
	anneal	68 798 0.195 38	555 1	9,601 1 76 14,098 12	66,974	2
	austral	55 690 0.272 22 9,015 6 136,010 4 38 16,231 18 785,005	19
	breast	43 286 0.231 13	801 1	6,210 1 17 1,471 1	25,702	1
	cleve	43 303 0.325 22 5,896 3	64,016 2 27 8,387 6 242,228	6
	cmc	28 1,474 0.357 38 4,209 2	48,923 1	6 8,749 10	69,306	1
	crx	59 690 0.269 27 10,035 6 130,768 5 15 35,931 31 1,035,271	29
	german	76 1,000 0.276 35 111,099 26 3,215,841 118 40 56,973 120 6,198,069 182
	glass	34 216 0.295 24 1,332 1	44,605 1 18 1,112 1	17,660	1
	heart	38 270 0.368 26 6,018 2	58,706 1 20 8,662 4 237,586	5
	hepatic	45 155 0.421 34 8,209 1 100,105 4 84 40,450 11 643,543	14
	horse	75 300 0.235 14 3,968 6 124,368 6 16 15,446 20 1,244,224	35
	hypo	47 3,163 0.389 209 273,430 244 673,102 65 37 198,459 435 2,316,785 323
	iris	15 151 0.333	3	63 1	287 1 10	111 1	231	1
	lymph	59 142 0.322 18 4,359 1	38,888 1 83 18,477 6 408,507	11
	mushroom 119 8,124 0.193 25 1,130 550 227,699 24 102 9,380 594 2,736,405 230
	new-thyroid 21 216 0.287	7	99 1	593 1 14	161 1	1,218	1
	page	35 941 0.314 14 1,197 2	32,904 1 26 2,251 3	94,512	1
	pima	26 768 0.346 14	786 1	14,798 1 15	217 1	42,554	1
	tic-tac-toe	29 259 0.344 26 4,906 3	42,711 1	9 4,499 6	95,798	2
	vehicle	58 846 0.327 57 29,088 6 358,357 16 106 65,400 73 2,291,888	71
	wine	45 179 0.311 13 2,129 1	24,010 1 35 6,438 3 113,886	2
	zoo	43 102 0.394 33 1,199 1	4,567 1 54 4,290 1	34,588	1

i∈I ∑ t∈T d i,t ) w.r.t. the size of the dataset (i.e. |I | × |T |)

Table 3 :

 3 Comparing CP+SKY with Aetheris on UCI Benchmarks.• for CP+SKY, the number of candidates (i.e. intermediate patterns required to determine the forbidden area (see Section 4.3)) and the associated CPU-time, • for Aetheris, the number of closed patterns of the condensed representation and the associated CPU-time.

Table 4 :

 4 growth rate, area} M 2 = { f req, max, area, mean} Analysis of soft skypattern mining on UCI benchmarks.

		# items	# transactions	Density	CP+Edge-Sky CP+δ -Sky (δ = 5%) # of Edge-skypatterns # of Candidates Time (sec) # of δ -skypatterns # of Candidates Time (sec)	CP+Edge-Sky # of Edge-skypatterns # of Candidates	Time (sec)	CP+δ -Sky (δ = 5%) # of δ -skypatterns # of Candidates	Time (sec)
	abalone	28 4,178 0.321 834 15,896 38	39 18,031	38	3,447 8,718	24 2,422	11,730	29
	anneal	68 798 0.195	38 4,843 3	3 5,769	3	1,495 25,275	20 6,952	33,909	26
	austral	55 690 0.272	14 30,402 27	17 47,288	34 10,847 59,980	43 67,904 124,531	74
	breast	43 286 0.231	49 2,496 1	3 3,211	1	2,184 4,044	1 2,585	7,131	1
	cleve	43 303 0.325	15 22,407 8	6 31,393	10 15,613 27,102	10 9,324	45,301	14
	cmc	28 1,474 0.357	87 18,802 15	16 28,970	21 19,737 28,049	29 4,685	32,330	30
	crx	59 690 0.269	10 30,851 26	27 49,081	34 51,912 159,831 116 134,398 279,219 150
	german	76 1,000 0.276 164 400,028 650	54 945,432 1647 96,743 377,821 477 176,616 835,909 782
	glass	34 216 0.295	29 5,160 1	16 5,737	1	706 4,103	1 2,091	4,974	1
	heart	38 270 0.368	11 16,472 6	8 27,841	8 20,958 36,740	11	31	63,097	16
	hepatic	45 155 0.421 1179 35,111 7	21 43,155	8 20,846 119,983	35 17,105 157,261	33
	horse	75 300 0.235	12 17,606 15	3 26,412	18 13,938 69,042	39 50,151	98,491	45
	hypo	47 3,163 0.389 9147 472,434 823 2,918 672,019 875 215,789 764,023 8,256 765,715 1,956,947 22789
	iris	15 151 0.333	27	128 1	2	128	1	46	129	1	32	151	1
	lymph	59 142 0.322	31 8,399 2	7 13,522	3	6,886 74,370	19 66,930	97,640	20
	mushroom 119 8,124 0.193	28 11,314 609 114 12,761 614 209,695 600,450 7,021 378,536 719,762 18360
	new-thyroid 21 216 0.287	5	247 1	1	277	1	98	371	1	61	418	1
	page	35 941 0.314	10 3,775 5	3 5,634	7	3,483 8,207	8 8,397	15,154	13
	pima	26 768 0.346	7 8,120 5	13 12,320	6	2,438 2,566	2	80	5,143	3
	tic-tac-toe	29 259 0.344	95 27,478 19	26 37,182	22 11,473 17,087	13 6,730	39,053	24
	vehicle	58 846 0.327 366 226,070 162 111 296,149 211 73,583 194,280 195	531 460,716 372
	wine	45 179 0.311 130 17,831 3	9 18,970	3	2,825 18,883	5 4,879	25,119	5
	zoo	43 102 0.394	55 3,779 1	41 3,951	1	2,301 13,286	2 4,096	14,263	2

  Table 5a compares CP+SKY with Aetheris for different combinations of measures. For each set of measures, we report: • the number of skypatterns, • for CP+SKY, the number of candidates (i.e. the number of intermediate patterns, see Section 4.3) and the associated CPU-time, • for Aetheris, the number of closed patterns of the condensed representation and the associated CPU-time.

Table 5b

 5b

	reports, for each set of measures:

  1. Cluster #1 is made of patterns with a high growth rate and a low frequency. It contains 2 skypatterns and 23 soft ones: 8 of them are edge-skypatterns and 15 are δ -skypatterns. From a chemical point of view, most of these patterns contain the organophosphorus moiety and few sub-fragments of alkyl-substituted benzene (e.g. {ccC, cccC}).

	2. Cluster #2 contains 4 skypatterns and 21 soft ones: 11 of them are edge-
	skypatterns and 10 are δ -skypatterns. From a chemical point of view, it empha-
	sizes two well-known toxicophores, namely the chlorobenzene and the phenol
	rings.
	3. Cluster #3 comprises 2 skypatterns and 5 edge-skypatterns. Most of them are
	aromatic compounds, namely the benzene ring (i.e. with high frequency and low
	growth rate).

Table 6 :

 6 Repartition of soft skypatterns for M 4 .

http://www.gecode.org/

The closed constraint is used to reduce pattern redundancy. Indeed, closed skypatterns make up an exact condensed representation of the whole set of skypatterns[START_REF] Soulet | Mining dominant patterns in the sky[END_REF].

http://www.ics.uci.edu/ mlearn/MLRepository.html

Obviously, it is the same for both methods.

They correspond to edge-skypatterns that are not hard skypatterns.

They correspond to δ -skypatterns that are neither hard skypatterns neither edge-skypatterns.

Lethal concentration of a substance required to kill half the members of a tested population after a specified test duration.

A fragment denominates a connected part of a chemical structure containing at least one chemical bond.

European Chemicals Bureau: http://echa.europa.eu/

A chemical Ch contains an item A if Ch supports A, and A is a frequent subgraph of T .

Acknowledgements This work is partly supported by the ANR (French Research National Agency) funded project FiCOLOFO ANR-10-BLA-0214. The authors would like to thank Arnaud Soulet (University Franois Rabelais of Tours, France), for providing the Aetheris program and his highly valuable comments.


Bamba Kane
email: bamba.kane@unicaen.fr

Bertrand Cuissart
email: bertrand.cuissart@unicaen.fr

Bruno Crémilleux
email: bruno.cremilleux@unicaen.fr

Minimal Jumping Emerging Patterns: Computation and Practical Assessment

Keywords: pattern mining, emerging patterns, minimal jumping emerging patterns, ruled-based classification

Jumping Emerging Patterns (JEP) are patterns that only occur in objects of a single class, a minimal JEP is a JEP where none of its proper subsets is a JEP. In this paper, an efficient method to mine the whole set of the minimal JEPs is detailed and fully proven. Moreover, our method has a larger scope since it is able to compute the essential JEPs and the top-k minimal JEPs. We also extract minimal JEPs where the absence of attributes is stated, and we show that this leads to the discovery of new valuable pieces of information. A performance study is reported to evaluate our approach and the practical efficiency of minimal JEPs in the design of rules to express correlations is shown.

Introduction

Contrast set mining is a well established data mining area [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF] which aims at discovering conjunctions of attributes and values that differ meaningfully in their distributions across groups. This area gathers many techniques such as subgroup discovery [START_REF] Wrobel | An algorithm for multi-relational discovery of subgroups[END_REF] and emerging patterns [START_REF] Dong | Efficient mining of emerging patterns: Discovering trends and differences[END_REF]. Because of their discriminative power, contrast sets are highly useful in supervised tasks to solve real world problems in many domains [START_REF] Chen | Emerging patterns and classification algorithms for dna sequence[END_REF][START_REF] Kobylinski | Spatial emerging patterns for scene classification[END_REF][START_REF] Lozano | Introduction of Jumping Fragments in Combination with QSARs for the Assessment of Classification in Ecotoxicology[END_REF].

Let us consider a dataset of objects partitioned into several classes, each object being described by binary attributes. Initially introduced in [START_REF] Dong | Efficient mining of emerging patterns: Discovering trends and differences[END_REF], emerging patterns (EPs) are patterns whose frequency strongly varies between two datasets. A Jumping Emerging Pattern (JEP) is an EP which has the notable property to occur only in a single class. JEPs are greatly valuable to obtain highly accurate rule-based classifiers [START_REF] Kobylinski | Efficient mining of jumping emerging patterns with occurrence counts for classification[END_REF][START_REF] Li | Making use of the most expressive jumping emerging patterns for classification[END_REF]. They are used in many domains like chemistry [START_REF] Lozano | Introduction of Jumping Fragments in Combination with QSARs for the Assessment of Classification in Ecotoxicology[END_REF], knowledge discovery from a database of images [START_REF] Kobylinski | Spatial emerging patterns for scene classification[END_REF], predicting or understanding diseases [START_REF] Dong | Mining border descriptions of emerging patterns from dataset pairs[END_REF], or DNA sequences [START_REF] Chen | Emerging patterns and classification algorithms for dna sequence[END_REF]. A minimal JEP designates a JEP where none of its proper subsets is a JEP. Minimal JEPs are of great interest because they capture the vital information that cannot be skipped to characterize a class. Using more attributes may not help and even add noise in a classification purpose. Mining minimal JEPs is a challenging task because it is a time consuming process. Current methods require either a frequency threshold [START_REF] Fan | An efficient single-scan algorithm for mining essential jumping emerging patterns for classification[END_REF] or a given number of expected patterns [START_REF] Terlecki | Efficient discovery of top-k minimal jumping emerging patterns[END_REF]. On the contrary, one of the results of this paper is to be able to compute the whole set of minimal JEPs.

The contribution of this paper can be summarized as follows. First, we introduce an efficient method to obtain all minimal JEPs. A key idea of our method is to introduce an alternative definition of a minimal JEP which stems from the differences between pairs of objects, each of a different class. A backtrack algorithm for computing all minimal JEPs is detailed and the related proofs are provided. Our method does not require either a frequency threshold or a number of patterns to extract. It provides a general approach and its scope encompasses the essential JEPs [START_REF] Fan | An efficient single-scan algorithm for mining essential jumping emerging patterns for classification[END_REF] (i.e., JEPs satisfying a given minimal frequency threshold) and the k most supported minimal JEPs [START_REF] Terlecki | Efficient discovery of top-k minimal jumping emerging patterns[END_REF] which constitute the state of the art in this field. Second, taking into account the absence of attributes may provide interesting pieces of knowledge to build more accurate classifiers as experimentally shown by Terlecki and Walczak [START_REF] Terlecki | Jumping emerging patterns with negation in transaction databases classification and discovery[END_REF]. We address this issue. Our method integrates the absence of attributes in the process by adding their negation. It produces the whole set of minimal JEPs both with the present and absent attributes. Practical results advocate in favor of this addition of negated attributes in the description of the objects. Third, the results of an experimental study are given. We analyze the computation of the minimal JEPs, including the absence of attributes and comparisons with essential JEPs and top-k minimal JEPs. Finally, we experimentally assess the quality of minimal JEPs, essential JEPs and top-k minimal JEPs as correlations between a pattern and a class.

Section 2 gives the preliminaries. The description of our method is provided in Section 3. Section 4 presents the experiments. We review related work in Section 5 and we round up with conclusions and perspectives in Section 6.

Preliminaries

Let G be a dataset, a multiset consisting of n elements, an element of G is named an object. The description of an object is given by a set of attributes, an attribute being an atomic proposition which may hold or not for an object. The finite set of all the attributes occurring in G is denoted by M. In the remainder of this text, for the sake of simplicity, the word "object" is also used to designate the description of an object.

A pattern denominates a set of attributes, an element of the power set M, denoted P(M). A pattern is included in the object g if p is a subset of the description of g: p ⊆ g. The extent of a pattern p in G, denoted p G , corresponds to the set of the objects that include p: p G = {g ∈ G : p ⊆ g}. A pattern is supported if it is included in at least one object of the dataset. Moreover, we define a relation, I, on G × P(M) as follows: for any object g and any pattern p, gIp ⇐⇒ p ⊆ g.

Usual data mining methods only consider the presence of attributes. With binary descriptions, the absence of an attribute can be explicitly denoted by adding the negation of this attribute in order to build patterns conveying this information. We integrate this idea in this paper by adding the negation of absent attributes and thus the description of an object always mentions every attribute either positively or negatively. In other words, M explicitly contains the negation of any of its attributes, the symbol ¬ is used to denote the negation of an attribute (cf. Table 1 as an example).

Minimal Jumping Emerging Pattern. We now suppose that the dataset G is partitioned into two subsets G + and G -, every subset of such a partition is usually named a class of the dataset. We call an object of G + a positive object and an object of G -a negative object. We say that a supported pattern p is a JEP if it is never included in any negative object: p G = ∅ and p G ⊆ G + .

A JEP is minimal if it does not contain another JEP as a proper subset. The set of the minimal JEPs is a subset of the set of the JEPs which groups all the most general JEPs. As a JEP contains at least one minimal JEP, when an object includes a JEP then it includes a minimal JEP.

Table 1 displays a dataset of 6 objects partitioned in two datasets: G + = {g 1 , g 2 } and G -= {g 3 , g 4 , g 5 , g 6 }. The pattern p = {1, ¬2} is a JEP as p G+ = {g 1 } and p G-= ∅ and {1} and {¬2} are not JEPs, p is thus a minimal JEP.

Contribution

Section 3.1 introduces the key notion of a difference between two objects, it provides a new definition of a minimal JEP. The latter is the support of our algorithm for extracting minimal JEPs which is detailed and proven in Section 3.2.

A relation between the minimal JEPs and the differences between objects

Let G be a dataset partitioned into two subsets G + and G -. The difference between an object i and an object j groups the attributes of i that are not satisfied by j: D i,j = i \ j = {m ∈ M : i I m and ¬j I m}. When one focuses on a negative object j, the gathering of the differences for a negative object j corresponds to the union of the differences between i and j, for any positive object i: D •j = ∪ i∈G+ D i,j . In Table 2, the gathering of the differences for the negative object 4 is

D •4 = D 1,4 ∪ D 2,4 = {1,¬2} ∪ {¬4} = {1,¬2,¬4}.
The following lemma is a direct consequence of the definition of the gathering of the differences for a negative object. Lemma 1. Let j be a negative object and p be a pattern. If D •j ∩ p = ∅ then p is not included in j : ¬(j I p).

It follows that, if a supported pattern p intersects with every gathering of the differences for a negative object and, thanks to Lemma 1, p cannot be included in any negative object, thus p is a JEP. We now reason by contraposition and we suppose that a supported pattern p does not intersect with the gathering of the differences for one negative object j 0 :

D •j0 ∩ p = ∅ . If p is supported by a positive object i 0 , as D •j0 ∩ p = ∅ implies D i0,j0 ∩ p = ∅,
then p is supported by j 0 . Thus p cannot be a JEP.

A JEP corresponds to a supported pattern which has at least one attribute in every D •j , for j a negative object. Proposition 1 follows:

Proposition 1. A supported pattern p is a JEP if D •j ∩ p = ∅, ∀j ∈ G -
On the example, the JEP p = {1, ¬2} intersects with every D •j (see Table 2):

D •g3 ∩ p = {1, ¬2}, D •g4 ∩ p = {1, ¬2} , D •g5 ∩ p = {1} and D •g6 ∩ p = {¬2}.
We now establish a relation between the gathering of the differences and the minimal JEPs.

Proposition 2. A JEP p is a minimal JEP if, for every attribute a of p, ∃j ∈ G -such that p ∩ D •j = {a}.
On the example, the JEP p = {3, 1, ¬2} is not a minimal JEP since it contains the JEP {1, ¬2}. Proposition 2 gives another point of view: since no intersection between p and a D •j (for j a negative object) corresponds to {3}, the attribute {3} does not play a necessary part in the discriminative power of p, thus p is not a minimal JEP.

Proof (of Proposition 2). Let p be a JEP.

Suppose p is not minimal: there exists a JEP q, different from p, such that q p. Consider an attribute a such that a ∈ p \ q. As q is a JEP, Prop. 1 imposes that ∀j ∈ G -, q ∩ D •j = ∅, it ensues that ∀j ∈ G -, p ∩ D •j = {a}. One now can state that, if p is not minimal, then p contains one attribute a such that ∀j ∈ G -, p ∩ D •j = {a}.

Conversely, suppose there exists an attribute a in p such that ∀j ∈ G -, p ∩ D

•j = {a}. As p is a JEP, Prop. 1 ensures that D •j ∩ p = ∅, ∀j ∈ G -. It follows that, ∀j ∈ G -, D •j ∩ p \ {a} = ∅. By applying Prop. 1, p \ {a} is a JEP and p cannot be minimal.
Prop. 2 states that a minimal JEP is a supported pattern that excludes all the negative objects and where every attribute is necessary to exclude (at least one) object. It follows:

Consequence of Prop. 2. Let p be a minimal JEP for the dataset G + ∪ G -and g -∈ G -. If p is not a minimal JEP for the dataset G + ∪ G -\ {g -} then there exists a unique attribute a, a ∈ p, such that p\{a} is a minimal JEP for the dataset G + ∪ G -\{g -}.

Calculation of the minimal JEPs

We now introduce a structure designed to generate all the minimal JEPs for a dataset: a rooted tree whose "valid" leaves are in a one-to-one correspondence with the minimal JEPs. We suppose here that for ∀j ∈ G -, D •j = ∅, as it follows from Prop. 1 that this condition is a necessity for the existence of at least one minimal JEP. We also assume that an arbitrary order is given on the negative objects: for two negative objects j and j , j ≺ j if j is accounted before j .

Rooted tree. A rooted tree (T, r) is a tree in which one node, the root r, is distinguished. In a rooted tree, any node of degree one, unless it is the root, is called a leaf. If {u, v} is an edge of a rooted tree such that u lies on the path from the root to v, then v is a child of u. An ancestor of u is any node of the path from the root to u. If u is an ancestor of v, then v is a descendant of u, and we write u v; if u = v, we write u < v.

A tree of the minimal JEPs. We create the tree (T, r) as a rooted tree in which each node x, except the root r, holds two labels: an attribute, l attr (x) ∈ M, and a negative object l obj (x) ∈ G -. For a node x of (T, r), Br(x) gathers the attributes that occur along the path from the root to x: Br(x) = {l attr (y), y x}; Br(x) indicates the pattern considered at x. For any node x of T and any attribute a, a ∈ Br(x), crit(a, x) gathers the negative objects already considered at the level of x and whose exclusion is due to the sole presence of a in Br(x): crit(a, x) = {j l obj (x) :

D •j ∩ Br(x) = {a}}.
Definition 1 (A tree of the minimal JEPs (ToMJEPs)). A rooted tree (T, r) is a tree of the minimal JEPs for G if: i) any node x, except the root r, holds two labels: an attribute label, l attr (x) ∈ M, and a negative object label, l obj (x) ∈ G -. ii) if x is an internal node then: a) the children of x hold the same negative object label: l obj (y) = min{j ∈ G -: D •j ∩ Br(x) = ∅}, ∀y a child of x, b) every child of x holds a different attribute label, c) the union of the attribute labels of the children y of x corresponds to

D •l obj (y) . iii) x is a leaf if it satisfies one of the following conditions: a) ∃z x such that crit(l attr (z), x) = ∅, b) ∀j ∈ G -, D •j ∩ Br(x) = ∅.
A leaf which satisfies the criteria iii)a) is named dead-end leaf, otherwise it is named a candidate leaf.

Figure 1 depicts a ToMJEPs for the dataset of Tables 1 and2. The nodes with a dashed line are the dead-end leaves, the nodes surrounded by a solid line the candidate leaves. A candidate leaf surrounded by a bold plain line is associated to a supported pattern: it represents a minimal JEP. For example, the node x such that Br(x) = {1, ¬2} is associated to a minimal JEP while the node We will now demonstrate that there is a one-to-one mapping between the "supported" candidate leaves of a ToMJEPs and the minimal JEPs. The following lemma is an immediate consequence of the definition of a ToMJEPs, together with the application of Prop. 1 and 2.

Lemma 2. Let (T, r) be a ToMJEPs and x be a node of T , different from a deadend leaf. If there exists i ∈ G + such that i I Br(x) then Br(x) is a minimal JEP for the dataset G = G + ∪ {j ≤ l obj (x)}.

Proof. By definition of a ToMJEPs, for a node x, we have Br(x) ∩ D •j = ∅, ∀j ≤ l ≤ l obj (x). Thanks to Prop. 1, it follows that Br(x) is a JEP for G + ∪ {j ≤ l obj (x)}.

If x is not a dead-end leaf, by definition of a ToMJEPs, we have ∀z ≤ x, crit(l attr (z), x) = ∅, thus ∀a ∈ Br(x), ∃j ∈ ∪{j ≤ l obj (x)} such that Br(x) ∩ D •j = {a}. Prop. 2 ensures that Br(x) is a minimal JEP for the dataset G + ∪ {j ≤ l obj (x)}. Lemma 3. Let (T, r) be a ToMJEPs. Let p be pattern. If p is a minimal JEP for the dataset G + ∪ G -then there exists a unique candidate leaf x such that Br(x) = p.

Proof. The proof reasons inductively on G -. For a sake of simplicity, we denote here the set of the negative objects as {1, . . . , k}

with k = |G -| and ∀1 ≤ j ≤ k -1, j ≺ j + 1.
Definition 1 implies that the children of the root r deal with 1 (the first negative object), we have D •1 = {l attr (x) : x is a child of r}. Moreover, as by definition of a ToMJEPs, crit(l attr (x), x) = ∅, no child of r is a dead-end leaf. Thus, associated to any pattern p which is a minimal JEP for the dataset G + ∪ {1}, there is a unique node x, different from a dead-end leaf such that Br(x) = p.

Let us now suppose that, considering any minimal JEP p for G + ∪ {1, . . . , l} with l < k, there exists a unique node x, different from a dead-end leaf, such that Br(x) = p. When we consider a pattern q, minimal JEP for the dataset G + ∪ {1, . . . , l, l + 1}, two cases arise:

-If q is a minimal JEP for G + ∪ {1, . . . , l}, then, thanks to the induction hypothesis, there exists a unique node x q such that Br(x q ) = q. -Otherwise, thanks to the consequence of Prop. 2, there exists one attribute a such that D •l+1 ∩ q = {a} and D •j ∩ a = {a}, ∀j l. Prop 2 ensures that q \ {a} is minimal JEP for G + ∪ {1, . . . , l}. Thanks to the induction hypothesis, there exists a unique node x, different from a dead-end leaf, such that Br(x) = q \{a}. By definition of a ToMJEPs, there exists a unique child of x, such that Br(q) = x. As q is a minimal JEP, x is not a dead-end leaf.

Prop. 3 is a consequence of Lemmas 2 and 3: Proposition 3 (One-To-One correspondence). Let (T, r) be a ToMJEPs. There is a one-to-one correspondence between the set of the candidate leaves x such that Br(x) is a supported pattern and the set of the minimal JEPs.

Prop. 3 ensures that we can generate the minimal JEPs by simply performing a depth first traversal of a ToMJEPs and output the candidate leaves such that Br(x) is a supported pattern. Note that it is not necessary to compute and store the entire ToMJEPs. A depth first traversal only requires to store the path from the root to the node currently visited.

The sketch of implemention provided in Section 4.1 gives information about the calculation of the extent, the calculation of the essential JEPs and the top-k minimal JEPs that are inferred from a ToMJEPs.

Experimental evaluation

This section provides and comments results from a study conducted on 13 benchmark datasets. We investigate the computation of the JEPs according to running time, setting a minimum frequency threshold. It also indicates the reliability of correlation between a JEP and a class. In the following, a JEP denominates a supported pattern with respect to any class.

Material and methods

The datasets. The study is conducted on 13 usual datasets described in Table 3. All the datasets are available from the UCI Machine Learning repository [START_REF] Lichman | UCI machine learning repository[END_REF]. We selected these datasets because they have been used, at least once, in an experimental assessment of JEPs [START_REF] Dong | Mining border descriptions of emerging patterns from dataset pairs[END_REF][START_REF] Fan | An efficient single-scan algorithm for mining essential jumping emerging patterns for classification[END_REF][START_REF] Terlecki | Efficient discovery of top-k minimal jumping emerging patterns[END_REF]. Non binary attributes were converted into a binary valued format by applying a sanctioned method [START_REF] Kerber | Chimerge: Discretization of numeric attributes[END_REF][START_REF] Liu | Feature selection via discretization[END_REF] which is available at Frans Coenen's website1 . Implementation. Our algorithm partially explores a ToMJEPs in a depth first manner, it outputs every candidate leaf whose associated pattern is a supported one. We implemented two solutions to ensure to only output supported patterns. The first one, called post-filtering solution, generates all the candidate leaves and then checks whether their extent is empty or not. The second one, named maintaining extent solution, integrates the computation of the extents with the calculation of the child of an internal node of a ToMPJEPs. It enables to backtrack as soon as the extent is empty. Moreover, when a minimum frequency threshold is provided, the maintaining extent solution is straightforwardly adapted to improve the computing of the essential JEPs. Indeed, the frequency of candidate essential JEPs [START_REF] Fan | An efficient single-scan algorithm for mining essential jumping emerging patterns for classification[END_REF] is directly derived from the cardinality of the extent. For the same reason, this solution also enables to compute the top-k minimal JEPs [START_REF] Terlecki | Efficient discovery of top-k minimal jumping emerging patterns[END_REF] when a value for k is provided. Moreover, the pruning strategy becomes more and more efficient during the mining step because the minimal frequency threshold to belong to the top-k minimal JEP only increases during the mining.

Protocol. In order to compute all the minimal JEPs whatever the positive class is, we successively consider each class (of the dataset) as the positive class while the union of the others classes constitutes the negative class. Computations were performed on a server using Ubuntu 12.04 with 2 processors Intel Xeon 2.80 GHz and 512 gigabytes of RAM.

Results and discussions

Computation of the minimal JEPs. We computed all the minimal JEPs on the 13 selected datasets, by using the post-filtering and maintaining extent solutions. Moreover, essential JEPs are computed with two minimum frequency thresholds (1% and 5%), and the top-k JEPs with k = 10 and k = 20. Table 4 gives the cardinalities of the sets of the minimal JEPs and the running times. For computing all the minimal JEPs, the maintaining extent solution always operates faster than the post-filtering solution, by a factor varying from 1.6 to 3. By observing the results for the essential JEPs and top-k minimal JEPs, one notes that the running time decreases significantly when a minimal threshold is set for the cardinality of the extent. The use of a frequency constraint related to the cardinality of the extent is efficient, obviously there is the risk to miss interesting patterns.

Minimal JEPs as rules to express correlations. A JEP expresses a correlation between the occurrence of a pattern and one class of objects. This part provides experimental results to assess the interest of such rules: do these rules cover a large part of the objects? Are they confident enough? We have also performed experiments to evaluate the usefulness of the explicit description of the absent attributes by adding their negations.

The study has been conducted by using a leave-one-out framework: every object has been successively discarded from the dataset. For every object g, the minimal JEPs have been extracted by considering G \ {g} as the dataset and the resulting rules have been applied on g.

Table 5 provides results obtained by applying minimal JEPs, essential JEPs, or top-k minimal JEPs as association rules. No Negated attributes designates the descriptions which do not explicitly take into account the absence of attributes whereas With Negated attributes points the descriptions that explicitly consider the absence of attributes. The column Cov denotes the coverage of the set of association rules (the part of the objects for which at least one association rule has applied). The column Con refers to the average confidence (i.e., the ratio between the number of correct applications of the rules over the whole number of applications of the rules). For example, if we consider the dataset named breast, whith the No Negated attributes description, 47.78% of the objects contain at least one minimal JEP, this coverage raises to 49.33% of the objects when the descriptions With Negated attributes are accounted. With the same dataset, by using the No Negated attributes description, 98.19% of the rules resulting from a minimal JEP apply on an object of the proper class ; this average confidence slightly decreases to 96.13% when the No Negated attributes description is used.

First of all, the JEPs often apply on a large portion of the objects: for 7 datasets among the 13 datasets, more than 80% of the objects contain at least one JEP. Note that this coverage increases when the description turns from No Negated attributes to With Negated attributes, up to 8% for the hepatitis dataset.

The average confidences indicate that minimal JEPs often point a reliable association between a pattern and a class, even when no frequency constraint is set. By paying the price of a lower coverage, setting a minimum frequency threshold -as it is done for the essential JEPs or, indirectly, for the top-k minimal JEPs -causes an increase of the average confidence, depending on the dataset. The average confidence levels reached by the two descriptions, No Negated attributes and With Negated attributes, are very comparable.

As a conclusion, both description families, With Negated attributes and No Negated attributes, lead to minimal JEPs reaching a similar level of confidence. However, the minimal JEPs extracted with the With Negated attributes descriptions cover a wider range of objects than the minimal JEPs extracted with the No Negated attributes descriptions, but with a longer running time.

Related work

Since the key paper of Dong and Li [START_REF] Dong | Efficient mining of emerging patterns: Discovering trends and differences[END_REF], subsequent research has focused on mining emerging patterns and contrast sets. However, there are very few attempts to tackle the discovery of minimal JEPs. Fan and Ramamohanarao have proposed an algorithm extracting the minimal JEPs whose frequency of occurrence is greater than a given threshold, such JEPs are called essential JEPs [START_REF] Fan | An efficient single-scan algorithm for mining essential jumping emerging patterns for classification[END_REF]. Terlecki and Walczak have designed a computational method based on a CP-Tree to get the k most supported minimal JEPs, named top-k minimal JEPs [START_REF] Terlecki | Efficient discovery of top-k minimal jumping emerging patterns[END_REF]. These methods require either a frequency threshold or a given number of expected patterns. On the contrary, our method is free from these parameters and computes the whole set of minimal JEPs. Terlecki and Walczak [START_REF] Terlecki | Jumping emerging patterns with negation in transaction databases classification and discovery[END_REF] have experimentally shown that taking into account the absence of attributes may provide interesting pieces of knowledge to build more accurate classifiers. We have dealt with this issue since our method extracts minimal JEPs including the negation of the attributes which are absent.

In addition, JEPs can be associated to version space [START_REF] Mitchell | Generalization as search[END_REF]. A version space gathers the descriptions that match all objects of one class and no object of the other class. Therefore a version space corresponds to the JEPs that match all objects of one class. JEPs are also related to the concept of disjunctive version space since a JEP corresponds to all descriptions of objects that match at least one object of one class and no object for the other classes. In Formal Concept Analysis, a JEP is also named "hypothesis" [START_REF] Ganter | Hypotheses and version spaces[END_REF] (a hypothesis brings together the descriptions of objects that match at least one object in one class and no object in others).

Conclusion

We have introduced an efficient method to extract the whole set of minimal JEPs. To the best of our knowledge, it is the first method which does not require either a frequency threshold or a given number of expected patterns. Our method is also able to straightforwardly extract the essential JEPs and the k most supported minimal JEPs. Moreover it enables the integration of negated attributes that can be precious for a classification purpose. We have experimentally analyzed the computation of these JEPs, together with the reliability of the correlations between a JEP and a class.

The structure of tree of the minimal JEPs constitutes a framework for designing and expressing algorithms to compute the minimal JEPs from a dataset. In order to speed up the calculation, this framework will be used to seek for efficient orderings on the attributes or on the objects. Another direction is to produce patterns correlated to one class to a lesser extent and mine emerging patterns with high growth-rate values. Beyond this work, we plan to use minimal JEPs in the design of an advanced rule-based classifier.

Fig. 1 .

 1 Fig. 1. Example of a tree for minimal JEPs

Table 1 .

 1 A dataset of 6 objects

	Objects	Attributes 1 ¬1 2 ¬2 3 ¬3 4 ¬4
	G+	g1 g2	x	x x	x x x	x	x
	G-	g3 g4 g5 g6	x	x x x x x x	x x x x	x x x x	x

Table 2 .

 2 Differences from the dataset in Table1

		g3	g4	g5	g6
	g1 1,3,¬2	1,¬2	1	¬2,4
	g2	3,¬4	¬4	2,¬4	¬1
	D•j 1,3,¬2,¬4 1,¬2,¬4 1,2,¬4 ¬1,¬2,4

Table 3 .

 3 The datasets and their characteristics

	Datasets Objects Attributes Classes Datasets Objects Attributes Classes
	breast	699	20	2	mushroom 8124	90	2
	congres	435	34	2	pima	768	38	2
	ecoli	336	34	8	tic-tac-toe	958	29	2
	glass	214	48	7	waveform	5000	101	3
	heart	303	52	5	wine	178	68	3
	hepatitis	155	56	2	zoo	101	42	7
	iris	150	19	3

Table 4 .

 4 Computation of minimal JEP including negation of attributes

			All minimal JEPs	Essential JEPs	Top-K minimal JEPs
			post-filtering maintaining extent	1%	5%	10	20
	Datasets Min.JEPs	Time	Time	Time	Time	Time	Time
	iris	40	70.564 ms	24.348 ms	14.316 ms 9.783 ms 13.043 ms 17.303 ms
	breast	38	924.998 ms	347.572 ms	190.432 ms 79.198 ms 95.212 ms 119.213 ms
	ecoli	200	842.345 ms	353.734 ms	173.658 ms 98.982 ms 134.314 ms 136.712 ms
	zoo	3323	1339.008 ms	579.208 ms	232.023 ms 101.032 ms 67.178 ms 79.032 ms
	pima	1443	7.323 s	3.093 s	895.053 ms 532.123 ms 1.009 s	1.694 s
	glass	59747	27.172 s	12.418 s	6.927 s	3.241 s	1.439 s	2.081 s
	congres	55449	89.396 s	38.077 s	19.145 s	8.380 s	3.107 s	4.929 s
	hepatitis	410404	123.520 s	53.706 s	25.576 s	14.419 s	2.978 s	3.097 s
	heart	122865	3.351 mn	1.194 mn	29.560 s	15.201 s	9.432 s	8.921 s
	tic-tac-toe 109949	5.664 mn	2.797 mn	55.860 s	13.182 s	4.541 s	6.325 s
	wine	1353996 200.321 mn	99.366 mn	58.053 mn 36.324 mn 8.342 mn 11.821 mn
	mushroom 17345228 673.563 mn	423.116 mn	192.743 mn 101.765 mn 27.545 mn 50.325 mn
	waveform 23895434 1845.431 mn	954.190 mn	421.813 mn 238.425 mn 47.342 mn 59.175 mn

Table 5 .

 5 Evaluation of minimal JEPs as rules to express correlations Datasets Cov Con Cov Con Cov Con Cov Con Cov Con Cov Con Cov Con Cov Con Cov Con Cov Con breast 47.78 98.19 45.2 98.32 44.81 99.10 39.16 98.5 43.29 97.01 49.33 96.13 47.42 97.49 45.25 98.51 38.21 97.92 40.21 95.85 congres 99.08 89.7 91.29 91.98 80.37 92.31 71.32 93.72 78.53 91.67 99.00 88.10 92.28 90.31 85.42 92.13 60.43 95.23 70.14 94.23 ecoli 34.52 63.79 30.71 66.38 25.74 71.63 20.32 75.73 25.92 68.97 37.32 71.23 32.12 73.98 26.43 74.21 25.92 75.43 27.13 74.01 glass 90.18 62.17 80.32 70.38 77.90 78.12 70.45 70.32 75.27 68.43 94.13 64.15 87.12 66.53 80.23 68.43 75.43 70.29 78.58 65.23 heart 97.02 58.5 83.32 61.90 80.32 64.87 70.32 71.43 74.23 69.25 98.02 56.42 86.32 57.82 82.55 60.43 61.21 80.32 67.01 78.43 hepatitis 82.42 78.39 72.63 81.30 69.32 84.01 69.91 85.90 72.72 83.94 91.03 75.38 73.23 79.17 70.31 81.83 62.62 80.72 70.39 77.38 iris 88.67 90.98 79.64 92.23 75.43 94.61 71.60 96.10 74.38 94.67 91.33 89.40 85.32 95.39 83.21 96.37 78.62 97.23 82.76 96.37 mushroom 70.15 77.12 52.20 79.44 47.53 88.43 58.18 81.38 60.06 79.92 74.76 78.43 57.92 80.01 53.91 82.54 63.74 80.32 66.34 77.98 pima 17.05 54.2 14.47 58.12 13.54 60.01 13.01 62.43 14.43 58.91 18.54 61.20 16.03 63.01 14.92 65.53 10.74 62.91 13.59 59.54 tic-tac-toe 81.62 86.57 65.32 88.10 61.93 89.21 60.43 80.21 62.32 78.32 82.12 82.34 70.64 83.21 65.47 84.24 72.31 69.43 75.32 67.30 waveform 45.28 72.19 32.93 74.91 29.99 75.10 33.19 73.10 35.92 72.01 48.09 76.98 40.67 78.01 39.52 82.94 37.91 79.63 40.47 74.78 wine 72.91 67.43 56.72 71.93 41.73 83.01 51.84 70.84 53.42 62.81 73.54 65.89 61.92 67.81 59.02 69.67 55.81 69.51 61.90 67.39 zoo 89.11 92.22 72.19 94.44 60.91 95.10 68.92 93.78 73.24 87.32 93.24 91.43 79.32 92.47 77.19 93.93 60.33 92.48 67.39 90.03

		All Min. JEPs
	1% 5%	eJEP	No negated attributes
	10
		top-k
	20
		All Min. JEPs
	1% 5% 10	eJEP	With Negated attributes
		top-k
	20

http://cgi.csc.liv.ac.uk/ ~frans/KDD/Software/LUCS-KDD-DN/exmpleDNnotes. html