Willy Ugarte

Patrice Boizumault

Bruno Crémilleux

Alban Lepailleur

Samir Loudni

Marc Plantevit

Chedy Raïssi

Arnaud Soulet

Skypattern Mining: from Pattern Condensed Representations to Dynamic Constraint Satisfaction Problems

Keywords: Skypatterns, pattern mining, constraint programming, dynamic CSP, user preferences

come

Introduction

The process of extracting useful patterns from data, called pattern mining, is an important subfield of data mining, and has been used in a wide range of applications and domains such as bioinformatics [START_REF] Zaki | Data mining in computational biology[END_REF], chemoinformatics [START_REF] Gasteiger | Chemoinformatics: A Textbook[END_REF], social network analysis [START_REF] Backstrom | Group formation in large social networks: membership, growth, and evolution[END_REF], web mining [START_REF] Backstrom | Optimizing web traffic via the media scheduling problem[END_REF] and network intrusion detection [START_REF] Fan | Using artificial anomalies to detect unknown and known network intrusions[END_REF]. Since the key papers of Agrawal et al. [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF], Mannila et al. [START_REF] Mannila | Levelwise search and borders of theories in knowledge discovery[END_REF], a considerable number of patterns, such as itemsets, strings, sequences, trees and graphs, have been studied and used in real-world applications. Nowadays, many pattern extraction problems like subgroup discovery [START_REF] Wrobel | An algorithm for multi-relational discovery of subgroups[END_REF], discriminative pattern mining [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF], and tiling [START_REF] Geerts | Tiling databases[END_REF] are understood from both theoretical and computational perspectives.

Most existing pattern mining approaches enumerate patterns with respect to a given set of constraints that range from simple to complex. For instance, given a transaction database, a well-known pattern mining task is to enumerate all itemsets (i.e. sets of items) that appear in at least s transactions. However, the output of pattern mining operations can be extremely large even for moderately sized datasets. For instance, in the worst case, the number of frequent itemsets is exponential in the number of the items in the dataset.

So far, the community has expended much effort on developing sophisticated algorithms which push the constraints deep into the mining process [START_REF] Bonchi | A constraint-based querying system for exploratory pattern discovery[END_REF]. But also in on compression (i.e. reduction) techniques to limit the number of output patterns depending on the application contexts [START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF][START_REF] Calders | Non-derivable itemset mining[END_REF][START_REF] Boulicaut | Free-sets: A condensed representation of boolean data for the approximation of frequency queries[END_REF]. The pattern mining community, however, has paid less attention to combining mining constraints. In practice, many constraints entail choosing threshold values such as the well-used minimal frequency. This notion of "thresholding" has serious drawbacks. Unless specific domain knowledge is available, the choice is often arbitrary and may lead to a very large number of extracted patterns which can reduce the success of any subsequent data analysis. This drawback is even more pronounced when several thresholds have to be combined. A second drawback is the stringent enumeration aspect: a pattern is either above or below a threshold. But what about patterns that respect only some thresholds? Should they be discarded? It is often very difficult to apply subtle selection mechanisms. There are very few works such as [START_REF] Bistarelli | Soft constraint based pattern mining[END_REF][START_REF] Ugarte | Extracting and summarizing the frequent emerging graph patterns from a dataset of graphs[END_REF] which propose to introduce a softness criterion into the mining process. Other studies attempt to integrate user preferences into the mining task in order to limit the number of extracted patterns such as the top-k pattern mining approaches [START_REF] Ke | Top-k correlative graph mining[END_REF][START_REF] Wang | TFP: an efficient algorithm for mining top-k frequent closed itemsets[END_REF]. By associating each pattern with a rank score, this approach returns an ordered list of the k patterns with the highest score to the user. However, combining several measures in a single scoring function is difficult and the performance of top-k approaches is often sensitive to the size of the datasets and to the threshold value, k.

We present a unified methodology of two approaches that aim to make the results of pattern mining useful from a user-preference point of view. To this end, we integrate into the pattern discovery process the idea of skyline queries [START_REF] Börzsönyi | The skyline operator[END_REF] in order to mine skyline patterns in a threshold-free manner. Such queries have attracted considerable attention due to their importance in multi-criteria decision making and economics where they are usually called "Pareto efficiency or optimality queries". Briefly, in a multidimensional space where a preference is defined for each dimension, a point a dominates another point b if a is better (i.e. more preferred) than b in at least one dimension, and a is not worse than b on every other dimension. For example, a user selecting a set of patterns may prefer a pattern with a high frequency, a large length and a high confidence. In this case, we say that pattern a dominates another pattern b if a.f requency ≥ b.f requency, a.length ≥ b.length, a.conf idence ≥ b.conf idence, where at least one strict inequality holds. Given a set of patterns, the skyline set contains the patterns that are not dominated by any other pattern.

Skyline pattern mining is interesting for several reasons. First, skyline processing does not require any threshold selection. In addition, for many pattern mining applications it is often difficult (or impossible) to find a reasonable global ranking function. Thus the idea of finding all optimal solutions in the pattern space with respect to multiple preferences is appealing. Second, the formal property of dominance satisfied by the skyline pattern defines a global interestingness measure with semantics easily understood by the user. These semantics are discussed at length in the economics literature, where the Pareto efficiency is applied to the selection of alternatives in resource distributions. However, while this notion of skylines has been extensively developed in engineering and database applications, it has remained unused for data mining purposes until recently [START_REF] Soulet | Mining dominant patterns in the sky[END_REF]. Thirdly, skyline pattern mining is appealing from an efficiency and usability point of view. The authors of [START_REF] Bentley | On the average number of maxima in a set of vectors and applications[END_REF] established a loose upper-bound on the the average number of skyline tuples O((ln n) d-1 ) (with n tuples and d dimensions) which contrasts with the usual worst-case number of possible itemsets O(2 |I| ) (where |I| represents the cardinality of the set of items).

Contributions and roadmap

We present significant extensions of our recent papers [START_REF] Soulet | Mining dominant patterns in the sky[END_REF][START_REF] Ugarte | Mining (soft-) skypatterns using dynamic CSP[END_REF] on the discovery of skyline patterns, or "skypatterns". First, we detail a static method (called Aetheris) based on the theoretical relationships with condensed representations of patterns (representations which return a subset of the patterns having the same expressiveness as the whole set of patterns [START_REF] Calders | A survey on condensed representations for frequent sets[END_REF]). Second, we describe a dynamic method (called CP+Sky) which involves a continuous refinement of the skyline constraints based on the extracted patterns. This is achieved through a dynamic CSP (Constraint Satisfaction Problems) framework (denoted by DynCSP). Third, the key notion of "skylineability" which constitutes the cornerstone of our two methods is explained in more detail. Finally, we present an extensive empirical study which includes a wide range of datasets and comparisons of our techniques. This enables us to draw some lessons about the strengths and weaknesses of each method and to better understand the advantages/weaknesses of the CSP machinery (see Sections 7.1.2 and 7. 1.3).

The rest of this paper is organized as follows. Section 2 surveys the works related to skyline pattern analysis. Section 3 introduces some basic definitions, the formal problem statement and an overview of our work. The key notion of skylineability is then studied in Section 4. Section 5 discusses the computation of condensed representation of patterns for skypattern queries. Section 6 discusses skylineability but within a DynCSP framework. We report an empirical study on several datasets and a case study from the chemoinformatics domain in Section 7. Finally, Section 8 discusses the learnt lessons.

Related work

Pattern mining

Frequent itemset mining was first described in [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF]. The problem can be defined as follows: a transaction is a subset of a given set of items I, and a transaction database, denoted T , is a set of such transactions. A subset X of I is a frequent itemset in T if the number of transactions containing X exceeds a given threshold, denoted by σ. One of the earliest findings in the data mining literature was that a mining process usually produces large collections of patterns. Many researchers have proposed methods to reduce the size of the output. These include the constraint-based pattern mining framework [START_REF] Ng | Exploratory mining and pruning optimizations of constrained association rules[END_REF], the condensed representations [START_REF] Calders | A survey on condensed representations for frequent sets[END_REF] and the compression of the dataset by exploiting Minimum Description Length Principle [START_REF] Siebes | Item sets that compress[END_REF], to name a few. A general observation is that patterns represent "fragmented knowledge", and often there is no clear view of how these knowledge fragments interact and combine to produce a global model. Recent approaches have therefore used schemes such as pattern teams [START_REF] Knobbe | Pattern teams[END_REF], constraint-based pattern set mining [START_REF] Raedt | Constraint-based pattern set mining[END_REF] and pattern selection strategies [START_REF] Bringmann | The chosen few: On identifying valuable patterns[END_REF] that aim to minimize the redundancy and the number of patterns. A common theme in these studies is to select patterns from the initial large set of patterns on the basis of their usefulness in a given context. This approach falls into the general trend to produce pattern sets i.e. sets of patterns satisfying properties on the whole set of patterns [START_REF] Raedt | Constraint-based pattern set mining[END_REF]. Other approaches take advantage of closed patterns to maximize a specific measure such as the growth rate for emerging patterns [START_REF] Garriga | Closed sets for labeled data[END_REF] and the area for tiling [START_REF] Kontonasios | An information-theoretic approach to finding informative noisy tiles in binary databases[END_REF][START_REF] Geerts | Tiling databases[END_REF]. Often, these methods focus on optimizing a global measure on the discovered pattern set and neglect the relationships between patterns. Moreover, these approaches suffer from a lack of flexibility to express the queries requested by the analyst. For each method, the user has to understand its semantics and express queries satisfying its algorithmic properties and constraints.

Another class of techniques considers statistical significance of patterns. The objective is to extract patterns for which a given characteristic (usually the frequency) deviates so much from its expected value under a null model that it is unlikely to have been generated by it. The frequency of a pattern is then considered as a random variable, whose distribution under the null hypothesis has to be calculated or approximated, and the significance of the pattern is assessed through a statistical test that compares the expected frequency under the null model to the observed frequency. A number of works have explored various notions of statistical significance for itemsets and have proposed novel and efficient methods for their extraction [START_REF] Hämäläinen | Efficient discovery of statistically significant association rules[END_REF][START_REF] Gallo | MINI: mining informative non-redundant itemsets[END_REF][START_REF] Gionis | Assessing data mining results via swap randomization[END_REF][START_REF] Mampaey | Tell me what i need to know: succinctly summarizing data with itemsets[END_REF] Pattern mining and Constraint programming. Pattern mining benefits from the recent cross-fertilization between data mining and Constraint Programming [START_REF] Guns | Itemset mining: A constraint programming perspective[END_REF][START_REF] Raedt | Constraint programming for itemset mining[END_REF][START_REF] Khiari | Constraint programming for mining n-ary patterns[END_REF][START_REF] Ugarte | Extracting and summarizing the frequent emerging graph patterns from a dataset of graphs[END_REF]. Constraint Programming is a general declarative methodology for solving constraint satisfaction problems. Within this framework, the user specifies in a declarative way what the problem is by using constraints rather than a method dedicated to solve the problem. Then a general solver provides the complete set of solutions satisfying all the constraints. The approach is very expressive and allows to combine a wide range of mining constraints [START_REF] Raedt | Constraint programming for itemset mining[END_REF].

Skyline

The skyline points can be viewed as compromise points with respect to a given set of criteria. Skyline computation is strongly related to mathematical and microeconomics problems such as maximum vectors [START_REF] Kung | On finding the maxima of a set of vectors[END_REF], Pareto set [START_REF] Matousek | Computing dominances in eˆn[END_REF], and multiobjective optimization [START_REF] Steuer | Multiple Criteria Optimization: Theory, Computation and Application[END_REF]. Since its rediscovery within the database community by Börzsönyi et al. [START_REF] Börzsönyi | The skyline operator[END_REF], many methods have been developed for answering skyline queries that can handle various constraints in different computational environments [START_REF] Papadias | Progressive skyline computation in database systems[END_REF][START_REF] Tan | Efficient progressive skyline computation[END_REF]. Skyline queries focus on the extraction of tuples from a given dataset and assume that all the elements are in the dataset, while the skypattern mining task consists of 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 (cf. Section 3.2). Few studies focus on skypattern mining for several pattern domains (e.g., graphs and subgroups). The published approaches are designed for particular types of patterns and consider a very limited number of measures to compute the skyline of patterns. Among them, two proposals address graph analysis. In [START_REF] Papadopoulos | Skygraph: an algorithm for important subgraph discovery in relational graphs[END_REF], the authors compute the skyline of subgraphs according to the number of vertices and the edge connectivity. Similarly, in [START_REF] Shelokar | Mosubdue: a pareto dominance-based multiobjective subdue algorithm for frequent subgraph mining[END_REF], the authors adapt the framework of the "Subdue" method [START_REF] Cook | Graph-based data mining[END_REF] to compute the patterns that are dominant according to three measures (e.g., frequency, number of nodes and density). In [START_REF] Van Leeuwen | Discovering skylines of subgroup sets[END_REF], the authors introduce the skypattern mining problem in the context of subgroups. Their approach aims at discovering subgroups that maximize a quality measure and a diversity measure. The notion of dominance is at the core of the skyline processing. In [START_REF] Négrevergne | Dominance programming for itemset mining[END_REF], the notion of dominance is used to propose a novel algebra extending relational algebras towards pattern mining. It leads to a generic method for mining several kinds of patterns (including the skypatterns) according to a preorder associated to the dominance relation. The solving part in [START_REF] Négrevergne | Dominance programming for itemset mining[END_REF] is performed by using Constraint Programming with a principle similar as the technique used in our CP+Sky method (cf. Section 6.2). The key idea is to use constraints on the dominance relation, which are dynamically added during the mining process. These constraints avoid producing solutions dominated by the solutions already extracted. In [START_REF] Négrevergne | Dominance programming for itemset mining[END_REF], the dynamically added constraints ensure that a candidate solution (i) is not dominated according to the preorder corresponding to the algebra or (ii) is equivalent to a solution already found. This last condition is required since the Pareto dominance is a strict and partial order whereas a preorder is a reflexive relation. In CP+Sky, the dynamically added constraints stem from the dominance relation (i.e. a candidate solution is not dominated by the previous solutions). Finally, [START_REF] Négrevergne | Dominance programming for itemset mining[END_REF] does not deal with the skylineability notion which is introduced in our work. As we will see, the skylineability allows to reduce the number of measures that have to be considered in the mining process and thus decreasing the runtime. Skylineability is associated to the theoretical relationships that we establish between the skymining problem and condensed representations of patterns. Another option for preference-based processing is the top-k procedure [START_REF] Ke | Top-k correlative graph mining[END_REF][START_REF] Wang | TFP: an efficient algorithm for mining top-k frequent closed itemsets[END_REF]. A ranking function f r is applied to patterns, and the k best patterns with the highest score with respect to f r are returned. As previously mentioned, this approach suffers from some limitations. The choice of k is not trivial (i.e. the horizon problem). A low value may miss useful patterns and too high a value introduces redundancy within the produced patterns (i.e. highly similar patterns). This limitation is the main motivation for the notion of the "most informative patterns" (MIP) that were proposed in [START_REF] Pennerath | The model of most informative patterns and its application to knowledge extraction from graph databases[END_REF]. MIPs can be seen as patterns that locally dominate other patterns according to a scoring function. This approach shares a similar spirit to ours as it also limits the number of enumerated patterns to a more manageable level. However, in contrast to our approach, work on MIPs includes a notion of dominance that is local and specific only to subsets of patterns.

Problem Statement and overview of the unified methodology

We introduce in this section some basic definitions and the formal problem statement. We also give an overview of the two methods Aetheris and CP+Sky we propose. These methods fully exploit an adequate representation of patterns dedicated to user preferences [START_REF] Soulet | Adequate condensed representations of patterns[END_REF]. Our study is interesting for several reasons. By carefully selecting patterns that are "the best available" for a given set of preferences, we greatly reduce the output and we limit the curse of "pattern explosion". The user is guaranteed that only the best patterns w.r.t. his criteria are present in the final result. Last but not least, our approach is threshold-free1 . Only the preferences and the dataset are required as an input.

Preliminary definitions

Although the problem can be formulated for any kind of pattern, for the sake of simplicity, we will illustrate our definitions using the itemset pattern domain. Section 8 discusses the computational and theoretical aspects associated with the problem when extracting more sophisticated kinds of patterns.

Let I be a set of distinct literals called items, an itemset (or pattern) corresponds to a non-empty subset of I. These patterns are gathered together in the language L: L = 2 I \∅. A transactional dataset T is a multi-set of patterns of L. Each element of T , named transaction, is a database entry.

X → freq(X) × length(X) mean X → min(X.val)+max(X.val)) 2 bond X → freq(X) freq∨(X) aconf X → freq(X) max(X.freq) gr 1 X → |T2| |T1| × freq(X,T1) freq(X,T2)
p-value X → -binomial(prod(X.supp), freq(X))

(b) Some measures of M

Table 1: Example of a toy dataset and measures

All the measures discussed in this study are based on the set of primitivebased measures M that were defined in the context of constraint-based pattern mining [START_REF] Soulet | Mining constraint-based patterns using automatic relaxation[END_REF]. Table 2 presents some general definitions of measures and Table 1b gives some specific examples (gr denotes the growth rate [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF], f req ∨ the disjunctive support, measures such as bond and aconf are detailed in [START_REF] Omiecinski | Alternative interest measures for mining associations in databases[END_REF]). Interestingly, our methodology is suitable for recent mining techniques utilizing statistical significance of patterns as discussed in related work. For instance, the p-value under the null model which considers all items to be independent random variables is rewritable as a primitive-based measure (see the definition of the p-value in Table 1a). As claimed in [START_REF] Soulet | Mining constraint-based patterns using automatic relaxation[END_REF], M encompasses a very large set of interesting measures.

In addition to the classical operators of + (i.e. +, -, ×, /) and L (i.e. ∪, ∩, \), the function freq denotes the frequency of a pattern (i.e. freq(X, T ) = |{t ∈ T | X ⊆ t}|), and length its cardinality. The disjunctive support is freq ∨ (X) = |{t ∈ T | ∃i ∈ X : i ∈ t}|. More atypical primitives also fit the primitive-based framework like binomial(p, i) = n k=i n k p k (1 -p) n-k . Given a function val : I → R + , we extend it to a pattern X and denote by X.val the multi-set {val(i) | i ∈ X}. This kind of function is used with the usual SQL-like primitives sum, min and max. For instance, sum(X.val) is the sum of val for each item of X. Note that prod is a slightly different aggregate function

Measure m ∈ M Primitive(s) Operand(s) m 1 θm 2 θ ∈ {+, -, ×, /, binomial} (m 1 , m 2 ) ∈ M 2 θ(s) θ ∈ {f req, f req ∨ , length} s ∈ S θ(s.val) θ ∈ {sum, max, min, prod} s ∈ S constant r ∈ + - - Syntactic expression s ∈ S Primitive(s) Operand(s) s 1 θs 2 θ ∈ {∪, ∩, \} (s 1 , s 2 ) ∈ S 2 θ(s) θ ∈ {f, g} s ∈ S variable X ∈ L - - constant l ∈ L - -
i.e. g(X) = {t ∈ T id | X ⊆ t}.
This large variety of measures allows for more flexibility to formulate new or well-known interestingness measures that match the data analyst's objectives. Rather than using a ranking function for combining these measures and then maximizing it, we propose to use the Pareto composition: Definition 1 ((Pareto-)Dominance). Given a set of measures M ⊆ M, a pattern X dominates another pattern Y with respect to M , denoted by X M Y , iff for any measure m ∈ M , m(X) ≥ m(Y ) and there exists m ∈ M such that m(X) > m(Y ). Two patterns X and Y are said to be indistinct with respect to M , denoted by

X = M Y , iff m(X) equals m(Y ) for any measure m ∈ M (if M = ∅, then X = ∅ Y ). Finally, X M Y denotes that (X M Y ) ∨ (X = M Y ).
Note that we define the Pareto dominance only with the greater than symbol (i.e. >) assuming that the end-user wants to maximize a set of measures. The case of a minimization of a measure m is equivalent to maximizing the measure m = -m (this case is illustrated with the definition of p-value which contains a minus).

Consider our running example using the data set T in Table 1a and suppose that M = {freq, area}, then the pattern ABCDEF dominates ABC because freq(ABC) = freq(ABCDEF ) = 2 and area(ABCDEF ) > area(ABC). Note in this case that ABCDEF is indistinct to ABC with respect to {freq}. Similarly, suppose that M = {freq, mean, length}, the pattern AC dominates AB because freq(AC) = freq(AB) = 3, |AB| = |AC| = 2 and mean(AC) > mean(AB).

The skypattern mining problem

Given a set of measures M , if a pattern is dominated by another according to all measures of M , it is irrelevant and should be discarded in the output. The notion of skyline pattern, skypattern for short, formalizes this intuition.

Definition 2 (Skypattern operator). Given a pattern set P ⊆ L and a set of measures M ⊆ M, a skypattern of P with respect to M is a pattern not dominated by any pattern 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 ∈ P | ∃Y ∈ P : Y M X}
Then, the skypattern problem can be stated: Problem 1. Given a set of measures M ⊆ M, the skypattern mining problem is to evaluate the query Sky(L, M ).

For instance, from the running data set (cf. Table 1a), Sky(L, {freq, length}) = {ABCDEF, AB, AC, A}, as illustrated in Figure 1. In the general case, the skypattern mining problem is challenging because of the very high number of candidate patterns (i.e |L|). Indeed, a naive enumeration of L is not feasible. For example, with 1000 items a naive approach will need to compute (2 1000 -1) × |M | measures and then compare them. A less naive approach based on heuristics (such as the anti-monotonicity of some measures) may give some results. However, the performance will be closely tied to the underlying properties of the data sets. For instance, in the case of the frequency measure, the density of the data set plays a major role in the performance and some algorithms are not able to extract frequent patterns at very low thresholds. Nevertheless, considering the following property provides new insights into an efficient computation of skypattern queries.

Property 1. Given a set of measures M ⊆ M, Sky(L, M ) = Sky(P, M ) for any pattern set P such that Sky(L, M ) ⊆ P ,

(∀P ⊆ L)(Sky(L, M ) ⊆ P ⇒ Sky(L, M ) = Sky(P, M ))
Proof Let P be a set of patterns such that Sky(L, M ) ⊆ P ⊆ L. First, let X be a pattern in Sky(L, M ). Then there is no Y = X in L such that Y M X. In particular, there is no Y = X in P such that Y M X. Note that X belongs to P which is a superset of Sky(L, M ). Thus, X is a pattern in Sky(P, M ). Suppose now that X is not in Sky(L, M ): then there exists Y = X in L \ P such that Y M X and ∀Y ∈ P , there is Y M X. By induction, any Y or another pattern dominating Y not in P would have to be in Sky(L, M ).

As Sky(L, M ) ⊆ P ⊆ L and |P | ≤ |L|, we argue that evaluating Sky(P, M ) is generally much less costly than evaluating Sky(L, M ) since the cost of Sky(x, M ) generally decreases with the cardinality of x. Consequently, we aim to reduce the cost of evaluating Sky(P, M ) by finding a small but relevant set P (i.e. that includes Sky(L, M )) by means of 1) condensed representations of patterns or 2) dynamic pruning.

Condensed representations of patterns. In many pattern mining tasks (e.g., association rule mining or clustering), condensed representations of patterns significantly reduce the mining effort without loss of precision. Could we use this principle in the case of skypattern mining? A direct approach would be to compute a concise representation for each measure m ∈ M , but this is generally not possible because some measures, such as area or length, are not condensable (i.e., the condensed representation is equal to |L|). Therefore, our problem can be reformulated as follows: given a set of measures M , how to identify a smaller set of measures M which allows the computation of a concise representation on the patterns (i.e. the pattern set P ) without loss of skypatterns? In addition, how can one use this set of measures to extract efficiently the skypatterns without redundancies? We address this problem in the next sections.

Dynamic pruning. Instead of extracting the whole condensed representation of patterns and then applying the Sky operator. One may consider the use of the Sky operator locally during the extraction. Indeed, as soon as a pattern is a candidate skypattern, the search space dominated by this pattern can be directly eliminated. In other words, each new candidate skypattern adds a constraint allowing to safely prune the remaining search space. These new constraints prevent the enumeration of unnecessary patterns. Section 6 describes how CSP can be used to update constraints during the extraction and thus reduce the search space.

Unified methodology for the two methods

Aetheris CP+Sky

Representative patterns according to M based on M' To clarify our methodology, we illustrate in Figure 2 the different processes of the two methods Aetheris and CP+Sky we propose. These two methods share the same overall methodology and mainly differ in the specific step of the computation of representative patterns of the skypatterns.

After the user's preferences selection, in a common first step, Aetheris and CP+Sky automatically identify a smaller set of measures M which allows for the computation of a concise representation on the patterns thanks to the use of converters (cf. Section 4). The second step (respectively 2 and 2' for Aetheris and CP+Sky) aims at computing an as small as possible superset that enables the retrieval of all skypatterns. For that purpose, Aetheris builds a static set of representative patterns according to the set M , which is based on the notion of converting the initial set of preference M (cf. Section 5). CP+Sky builds dynamically a more concise set by pruning unpromising patterns (the set of representative patterns of CP+Sky is included in the set of representative patterns of Aetheris) (cf. Section 6). The third step filters the set of representative patterns with the Sky operator. This step remains efficient because the number of representative patterns is much smaller than the number of possible skypatterns. Finally, this step provides a concise representation of the skypatterns. The end-user can either output this concise representation or the entire list of skypatterns as a final step depending on the application needs. Our methodology revolves around the simple idea that to be able to efficiently extract and analyze skypatterns, one needs to be able to (statically or dynamically) exhibit a concise representation of the skypatterns that will be used as an input to the skyline operator.

Skylineability

The set of skypatterns has no good property like downward closure or convexity. Conventional techniques used to prune the pattern search space like antimonotone properties are thus ineffective. However, using Property 1, an efficient computation of the set of representative patterns of skypatterns becomes possible. To do so, we introduce the notion of skylineability which aims at computing a reduced collection of representative patterns of the skypatterns (cf. the end of the previous section). This efficient computation is carried out using either free [START_REF] Boulicaut | Free-sets: A condensed representation of boolean data for the approximation of frequency queries[END_REF] or closed patterns [START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF].

Skylineability of a set of measures

Intuitively, skylineability refers to the notion of local extrema in the search space. The local extrema in this case are the maximal values for each preference selected by the end-user. By definition, only these extrema may therefore be skypatterns. Thus there is no need, while mining, to take into account the other patterns which are necessarily dominated by these extrema. Assume any two patterns X and Y , such that X ⊂ Y , have the same value for each measure of M : X = M Y . If Y always dominates X for a given set of measures M ⊆ M, then M is said to be maximally M -skylineable. This information is extremely important as it allows the discarding of non-maximal patterns (here, X) which are dominated by maximal patterns (here, Y ). This notion of skylineability can be seen as a way of mapping domination between two different sets of measures M and M .

Figure 3 (top) depicts the benefit of skylineability in the general case where it becomes possible to focus only on a subset of patterns and measures (i.e. M ) and have a formal guarantee that these patterns will not be dominated in the full set of measures (i.e. M ). We illustrate now this notion of skylineability on our running example. Let us consider patterns from T that maximize the frequency and area measures: M = {freq, area}. In our example (cf. Table 1a), the patterns B and AB have the same frequency (see Figure 3 (bottom)). Thus, if we define M = {f req}, B = M AB and AB M B because the area of AB is greater than that of B. In fact, for any two patterns X ⊂ Y such that X = freq Y , we have Y M X and M = {freq, area} is thus said maximally {freq}-skylineable. The mining process can focus on only extracting patterns based on the frequency measure (i.e. M ) without having to take into account the area measure that is present in M .

In practice, local extrema are not necessarily the longest patterns (i.e. the closed patterns which are the maximal patterns of equivalence classes) but can also be the shortest patterns (i.e. the free patterns which are the minimal patterns of equivalence classes). Thus, the concept of skylineability is defined in a dual manner: Definition 3 (Minimal skylineability). Given a set of measures M ⊆ M, a set of measures M ⊆ M is said to be (strictly) minimally M -skylineable iff for any patterns X and Y such that X ⊂ Y and X = M Y , one has X M Y (respectively X M Y ). Definition 4 (Maximal skylineability). Given a set of measures M ⊆ M, a set of measures M ⊆ M is said to be (strictly) maximally M -skylineable iff for any patterns X and Y such that X ⊂ Y and

X = M Y , one has Y M X (respectively Y M X).
From the previous definitions, given a set of measures M which is maximally M -skylineable, if X = M Y and X ⊃ Y , it is clear that X cannot be dominated by Y on M . For instance, M = {freq, area} is strictly maximally {freq}skylineable because area(X) strictly increases with the cardinality of X (when the frequency remains constant). Hence, in Figure 3 (bottom), we can deduce that ABCDEF dominates the patterns ABCDE, ABCD, . . . , DEF without considering the full set of measures M but only M . Notice that {freq} is (weakly) maximally (or minimally) {freq}-skylineable and that {length(X)} is strictly maximally ∅-skylineable.

Property 2. Given a set of measures M ⊆ M, there is at least one set M ⊆ M such that M is minimally and maximally M -skylineable.

Proof Let M ⊆ M be a set of measures. Let M ⊆ M be the set of all unary primitives defined on L. Let X and Y be two patterns such that X = M Y . Let m ∈ M . As X = m Y for any primitive m ∈ M and m is composed of such primitives, thus X = m Y . We conclude that X = M Y and then, X M Y and Y M X.

Property 2 is a very important result as it means that a set of measures is always skylineable (due to the fact that M is at least M -skylineable). Obviously, for a set of measures M , the smaller 2 M , the stronger its M -skylineability. For instance, {freq}-skylineability is more interesting than {freq, area}-skylineability because area is not a condensable function [START_REF] Soulet | Adequate condensed representations of patterns[END_REF]: there is no pair of distinct patterns X and Y such that X = {freq,area} Y . How to choose automatically a subset M is discussed next.

Minimal and maximal skylineable converters

One of the disadvantages of skylineability is that it depends on a set of measures M whose choice is essential to effectively reduce the search space. We propose two operators to automatically build M given the initial set of measures M . Basically, the construction of M consists in identifying primitives that must remain constant in order that minimal or maximal patterns are always dominant patterns. Intuitively, any primitive p that is part of the measure m ∈ M that hinders the M -skylineability of m, has to be added to M . For instance, it is easy to see that the frequency decreases the area because the frequency decreases with the specialization. In order that the closed patterns maximize the area, the frequency has to belong to M . More generally, it is essential to take into account the monotone behavior of primitives: decreasing or increasing. For instance, the length increases with X while the frequency decreases. It is also necessary to consider the operations that combine these primitives. The result of a multiplication increases when one of its operands increases. However, the result of a division decreases with its second operand. For this purpose, we define two operators denoted c and c (see Table 3).

∅ ∅ d(X) d ∈ {f req, min, g, prod} ∅ {d(X)} i(X) i ∈ {length, max, sum, f req ∨ , f } {i(X)} ∅ d(e 1 ) d ∈ {f req, min, g, prod} c(e 1 ) c(e 1 ) i(e 1 ) i ∈ {length, max, sum, f req ∨ , f } c(e 1 ) c(e 1 )
Table 3: Definition of the minimal and maximal skylineable converters c and c

2 In the sense of cardinality.

Given a primitive-based measure m ∈ M, the minimal skylineable converter returns a set of measures M = c(m) guaranteeing that for any pattern X ⊂ Y , if X = M Y then m(X) ≥ m(Y ). In other words, X dominates Y with respect to m. Dually, the maximal converter c guarantees that m(X) ≤ m(Y ) for any pattern X ⊂ Y such that X = c(m) Y .

Let us illustrate c and c on the area measure. The area is defined as a product of the frequency and length. Thus, we use the first definition in Table 3.

c(area) = c(freq(X))∪c(length(X)) = ∅∪{length(X)} = {length(X)}. Symmetrically, c(area) = c(freq(X)) ∪ c(length(X)) = {freq(X)} ∪ ∅ = {freq(X)}.
The skylineable converters enable us to automatically find optimization techniques already known for specific measures such as area [START_REF] Kontonasios | An information-theoretic approach to finding informative noisy tiles in binary databases[END_REF][START_REF] Geerts | Tiling databases[END_REF], p-value [START_REF] Gallo | MINI: mining informative non-redundant itemsets[END_REF] or growthrate [START_REF] Garriga | Closed sets for labeled data[END_REF] (see Table 4a). We can observe that many measures are maximized by the closed itemsets according to frequency which may explain the success of closed pattern mining. But, in this work, we generalize this principle to optimize any primitive-based measures. Note that when the converter c returns no measure (e.g., bond or aconf ), it means that the measure decreases with respect to the specialization. Dually, c(m) = ∅ means that m increases with respect to the specialization. For instance, c({freq(X), area(X)}) = c(freq(X)) ∪ c(area(X)) = {freq(X)} and c({freq(X), area(X)}) = c(freq(X)) ∪ c(area(X)) = {length(X)}. c({freq(X), area(X)}) = {freq(X)} means that the most specific patterns (when the frequency remains unchanged) maximize the measures {freq(X), area(X)}. The following property formalizes this observation: Property 3. A set of primitive-based measures M ⊆ M is minimally c(M )skylineable and maximally c(M )-skylineable.

Meas. m c(m) c(m) area {length(X)} {freq(X)} mean {max(X.val)} {min(X.val)} bond ∅ {freq(X), freq ∨ (X)} aconf ∅ {freq(X), max(X.val)} gr 1 {freq(X, T 2 )} {freq(X, T 1 )} p-value {prod(X.supp)} {freq(X)} (a) Individual measures c({freq(X), area(X)}) c(freq(X)) c(freq(X) × length(X)) c(freq(X)) c(length(X)) (b) A set of measures M = {freq(X), area(X)}

Proof

The key idea relies on the monotonous property according to each variable of a primitive. The operators c( ) and c( ) are recursively applied to return the set of primitives which must be constant in order to respectively minimize or maximize the measure. Two cases arise to be sure that an expression p(h 1 , . . . , h k ) is minimized with X. For each i ∈ {1, . . . , k}, if the primitive p increases according to the i th variable (while the other ones remain unchanged), it is necessary to return the primitives such that h i is also minimized according to X. For this purpose, the minimal skylineable converter is applied again. Otherwise, the primitive p decreases with the i th variable and we return the primitives such that h i is maximized by applying the maximal skylineable converter. The dual approach is used to maximize a measure.

In our implementation, the set of measures M is parsed through a syntax tree. Following this step, the minimal and maximal skylineable converters are recursively applied to automatically compute c(M ) and c(M ) (an example is provided in Table 4b for M = {freq(X), area(X)}). This process is illustrated in Figure 2 with the edge labelled 1. From now on, the set of measures M refers to c(M ) or c(M ).

Condensed representations of patterns for static mining of skypatterns

This section presents our static method called Aetheris based on the theoretical relationships between condensed representations of patterns and skypatterns.

Aetheris follows a two-step process (cf. Section 3.3) : first, a set of representative patterns is extracted and then the Sky operator is applied on these patterns. The technique is said to be static because the extraction of a representative pattern does not depend on the patterns already extracted, contrary to the CP+Sky method presented in the next section.

A major issue is how to extract representative patterns for a group of skypatterns. In the previous section, we remarked that some skypatterns share exactly the same values on the whole set of measures M (e.g. B = {f req} AB). This observation enables us to properly answer the question: instead of directly evaluating the skypattern query on L, we can compute the skypatterns on a condensed representation of L and then generate the entire set of skypatterns. To this end, we introduce the distinct operator which is at the core of the construction of a condensed representation adequate to M : Definition 6 (Distinct operator). Given a set of measures M ⊆ M, the distinct operator for P ⊆ L with respect to M and θ ∈ {⊂, ⊃} returns all the patterns X of P such that their generalizations (or specializations) are distinct from X with respect to M :

Dis θ (P, M ) = {X ∈ P | ∀Y θX : X = M Y } where θ ∈ {⊂, ⊃}.
Given a set of measures M , the set of free (respectively closed) patterns adequate to M corresponds exactly to Dis ⊂ (L, M ) (respectively Dis ⊃ (L, M )).

For instance, from our running example, Dis ⊂ (L, {freq}) = {A, B, C, D, E, F, AD, AE, BC, BD, BE, CD, CE, DE} and Dis ⊃ (L, {freq}) = {A, D, E, AB, AC, ABCDEF }.

We now introduce the indistinct operator that enables the retrieval of all the indistinct patterns from their representatives: Definition 7 (Indistinct operator). Given a set of measures M ⊆ M, the indistinct operator returns all the patterns of L being indistinct with respect to M with at least one pattern in P .

Ind(L, M , P ) = {X ∈ L | ∃Y ∈ P : X = M Y }
For instance, from Table 1a, the set of patterns that have exactly the same frequency as patterns B or C is Ind(L, {freq}, {AB, AC}) = {B, C, AB, AC}.

Preserving functions express a property of compression and are at the core of Property 4. A preserving function is a condensable primitive (many functions are preserving: freq, f req ∨ , count, min, max, sum, etc., see more details in [START_REF] Soulet | Adequate condensed representations of patterns[END_REF]). The skypatterns of Sky(Dis θ (L, M ), M ) form a condensed representation of Sky(L, M ). It is well-known that the size of adequate condensed representations (i.e. Dis ⊂ (L, M ) or Dis ⊃ (L, M )) is smaller than the whole collection of patterns [START_REF] Calders | A survey on condensed representations for frequent sets[END_REF]. Thus, we have achieved our objective as mentioned in Section 3.2.

The technique is even more efficient if the set of measures is strictly Mskylineable. In this case, the Ind operator can be skipped and Theorem 1 is reduced to the following relation: Sky(L, M ) = Sky(Dis θ (L, M ), M ) (with θ ∈ {⊂, ⊃}).

Figure 4 illustrates the computation of the skypatterns with our method Aetheris. Suppose that M = {f req, area}, the first step applies the maximal skylineable converter on M . Then, the distinct operator preserves the closed itemsets (Step 2). The skyline operator selects the dominant patterns at Step 3 by removing D and E which are dominated by AB (i.e. area(D) = area(E) = 3 < area(AB) = 6). Finally, the last step computes the indistinct patterns of skypatterns. Note that this step in this example is unnecessary because the area is strictly {freq}-skylineable.

Mining skypatterns using dynamic CSP

This section describes how the skypattern mining problem can be modeled and solved by using DynCSP [START_REF] Dechter | Belief maintenance in dynamic constraint networks[END_REF][START_REF] Verfaillie | Constraint solving in uncertain and dynamic environments: A survey[END_REF]. A major advantage of this method is that it improves the mining step during the process thanks to constraints dynamically arising from the current set of candidate skypatterns. These constraints avoid producing new solutions dominated by the current skypatterns and thus reduce the search space. More precisely, each time a solution is found, a new constraint is dynamically posted. The process stops when we cannot enlarge the dominated area further (cf. Figure 1). The set of obtained representative patterns is a subset of the set of representative patterns extracted with Aetheris (cf. Section 3.3). The completeness of our CP+Sky method is insured by the completeness of the CSP solver. The implementation has been carried out in Gecode3 .

The rest of this section is organized as follows. Subsection 6.1 recalls some general background on CSP and DynCSP. Subsection 6.2 describes how skypattern mining can be modeled using DynCSP. Subsection 6.3 presents the pattern encoding as well as the filtering that is achieved. Subsections 6.4 and 6.5 are devoted to closedness constraints and freeness constraints. Finally, Subsection 6.6 provides an example.

CSP and DynCSP

Constraint Satisfaction Problem. A CSP [54, 55] P =(X , D, C) is defined by a finite set of variables X = {x 1 , x 2 , . . . , x k }, a set of domains D which maps every variable x i ∈ X to a finite set of values D(x i ) and a finite set of constraints C.

Algorithm 1 provides a general overview of a CSP solver. Dom and Store denote respectively the current domains and the current set of constraints. Essentially, a CSP solver consists of a depth-first search algorithm. At each node of the search tree, procedure Constraint-Search selects an unassigned variable (line 5) according to user-defined heuristics 4 and assigns it a value (line 6). After that assignment, procedure Constraint-Search is called recursively (line 7). It backtracks when a constraint cannot be satisfied, i.e. when at least one domain is empty (line 2). A solution is obtained (line 9) when each domain Dom(x i ) is reduced to a singleton and all constraints are satisfied. The main concept used to speed-up the search is the constraint propagation by Filtering method. This method reduces the domains of variables such that they remain locally consistent. Constraint propagation operates on an individual constraint. To maintain local consistency for individual constraints, propagation rules are used. Given a constraint and the current domains of the variables in its scope, a propagator removes domain values that do not satisfy the constraint. Since variables usually participate in several constraints, the updated domains are propagated to the other constraints, whose propagators are in turn activated. This process of constraint propagation is repeated for all constraints until no more domain values can be removed or a domain becomes empty. Dynamic CSP. A DynCSP [START_REF] Dechter | Belief maintenance in dynamic constraint networks[END_REF][START_REF] Verfaillie | Constraint solving in uncertain and dynamic environments: A survey[END_REF] is a sequence P 1 , P 2 , ..., P n of CSPs, each one resulting from some changes in the definition of the previous one. These changes may affect every component in the problem definition: variables (additions or removals), domains (value additions or removals), constraints (additions or removals).

DynCSP-based method for mining skypatterns

This section provides our CSP-based method CP+Sky for mining skypatterns. As before, the representative patterns are searched according to M using the skylineability principle. The key idea is to use constraints on the dominance relation, which are dynamically added during the mining process. These constraints avoid producing solutions dominated by the solutions already extracted and thus reduce the search space. We start by highlighting the way we handle DynCSP and then we provide our encoding.

For our approach, changes between CSP P i and CSP P i+1 are only performed by adding new constraints without any removal of constraints. Additions are handled in a straightforward way with the help of filtering. Solving such a DynCSP involves solving a single CSP with additional constraints posted during search. These constraints will survive backtracking and state that next solutions should verify both the current set of constraints as well as the added ones. Each time a new solution is found, new constraints φ(X ) are imposed. Such constraints state that next solutions should verify both the current set of constraints Store and φ(X ) (cf line 10 of Algorithm 1).

Variable x will denote the (unknown) skypattern we are looking for. 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) = dis θ (x)
where dis θ (x) denotes the representative pattern x. q i+1 (x) = q i (x) ∧ φ i (x) where s i is the first solution to query q i (x).

First, the constraint dis θ (x) states that x must be either a closed pattern w.r.t. M (i.e. dis θ (x) = closed M (x)) or a free pattern w.r.t. M (i.e. dis θ (x) = f ree M (x)). Then, the constraint φ i (x) ≡ ¬(s i M x) states that the next solution (which is searched for) 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 output by Algorithm 1, we dynamically post a new constraint φ i (x) (see line 10) leading to a reduction of the search space. For skypatterns, φ i (x) states that ¬(s i M x):

φ i (x) ≡ m∈M m(s i ) < m(x) ∨ m∈M m(s i ) = m(x)
This process stops when we cannot enlarge the dominated area further, i.e. there exists n s.t. query q n+1 (x) has no solution. The dominated area cannot be extended and is fully established.

But, the n extracted patterns s 1 , s 2 , . . ., s n are not necessarily all skypatterns. Some of them could only be "intermediate" patterns simply used to enlarge the dominated 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-step approach:

1. Compute the set S = {s 1 , s 2 , . . . , s n } of candidates using DynCSP.

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 Section 7).

However, the order in which candidates are produced in the first step influences the way the dominated area is enlarged, and therefore the effectiveness of CP+Sky. One way to enhance the efficiency would be to select the most beneficial order in which candidates are generated. In the case of a single measure m, we can always derive an optimal order that guarantees that any solution produced in step 1 is a skypattern, thus avoiding the need for post-processing. It suffices to generate the patterns from the largest values of m to the lowest values of m (cf Definition 1). But in the general case where several measures are involved, finding such an optimal order is often impossible and post-processing is required.

Pattern encoding and filtering

We now introduce the modeling 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. [START_REF] Guns | Itemset mining: A constraint programming perspective[END_REF] and [START_REF] Raedt | Constraint programming for itemset mining[END_REF] model an unknown pattern x and its associated dataset T by introducing two sets of Boolean variables:

• item variables {X i | i ∈ I} where (X i = 1) iff (i ∈ x),
• transaction variables {T t | t ∈ T } where (T t = 1) iff (x ⊆ t).

Each set of Boolean variables aims to represent 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 the same way from the sum constraint towards the equality constraint. For example, when an item variable X i is set, the following propagation is applied to the reified constraints described by equation 1 (see [START_REF] Guns | Itemset mining: A constraint programming perspective[END_REF] for more details):

• if for some t, i∈I (min D(X i ))×(1-d t,i ) > 0 then remove 1 from D(T t ),
• if for some t, i∈I (min D(X i ))×(1-d t,i ) = 0 then remove 0 from D(T t ).

Finally, using the Boolean encoding, it is worth noting that some measures are easy to encode: freq(x) = t∈T T t and length(x) = i∈I X i . So, the minimal frequency constraint freq(x) ≥ θ (where θ is a threshold) is encoded by the constraint t∈T T t ≥ θ. In the same way, the maximal size constraint length(x) ≤ α (where α is a threshold) is encoded by the constraint i∈I X i ≤ α.

Closedness constraints

This section describes how to encode closed M (x). As an illustration, we provide the examples of M ={min} and M ={f req}. Recalling that thanks to skylineability, these measures also allow to handle measures such as mean, area, growth-rate, etc. In practice, these two examples are enough for running the experiments given in Section 7.

Let M ={min} and val(j) a function that associates an attribute value to each item j. If item i belongs to x, then its value must be greater than or equal to the min. Conversely, if this value is greater than or equal to the min, then i must belong to x (if not, x would not be maximal for inclusion). Item i belongs to x is encoded as (X i = 1). So, x is a closed pattern for the measure min iff:

∀i ∈ I, (X i = 1) ⇔ val(i) ≥ min{val(j) | j ∈ x} (2)
Let M ={f req}, the closedness constraint ensures that a pattern has no superset with the same frequency. If item i belongs to x, it is obvious that f req(x ∪ {i}) = f req(x). Conversely, if f req(x ∪ {i}) = f req(x), then i must belong to x (if not, x would not be maximal for inclusion). f req(x) is encoded as t∈T T t and f req(x∪{i}) is encoded as t∈T T t ×d t,i . Finally, the constraint closed M (x) is encoded using Equation (1) and Equation (3).

∀i ∈ I, (X

i = 1) ⇔ t∈T T t × (1 -d t,i ) = 0 (3)

Freeness constraints

Similar to the closedness constraint, we now give two examples of encoding of the freeness constraint. Following our principle of dealing with measures used in the experiments, we give the examples of M ={f req} and M ={max} because applying the minimal converter c on mean gives max (cf. Table 4).

Let M ={max} and val(j) a function that associates an attribute value to each item j. If item i does not belong to x, then its value must be greater than or equal to the min. Conversely, if this value is greater than or equal to the min, then i cannot belong to x (if i belongs to x, x would not be minimal for inclusion). Item i does not belong to x is encoded as (X i = 0). So, x is a free pattern for the measure max iff:

∀i ∈ I, (X i = 0) ⇔ val(i) ≤ max{val(j) | j ∈ x} (4)
Let M ={f req}, the freeness constraint ensures that a pattern has no subset with the same frequency. If item i does not belong to x, it is obvious that f req(x \ {i}) = f req(x). Conversely, if f req(x \ {i}) = f req(x), then i must not belong to x (if i belongs to x, x would not be minimal for inclusion).

In order to encode f req(x\{i}), we introduce Boolean variables T t,i such that the relationship between x \ {i} and T is modeled by posting reified constraints stating that, for each transaction t, (T t,i = 1) iff x \ {i} is a subset of t:

∀t ∈ T , (T t,i = 1) ⇔ j∈I\{i} X j × (1 -d t,j ) = 0 (5)
f req(x) is encoded as t∈T T t and f req(x \ {i}) is encoded as t∈T T t,i . So f ree M (x) is modeled using Equation (1) and Equation [START_REF] Backstrom | Optimizing web traffic via the media scheduling problem[END_REF].

∀i ∈ I, (X

i = 0) ⇔ t∈T (T t -T t,i ) = 0 (6)
6.6. Solving the running example using DynCSP We now illustrate CP+Sky on the running example in Table 1a with M ={freq, area}. We use the maximal converter c and thus the closedness constraint. As c(area) = f req, we get M ={freq}. Figure 5 depicts the various steps of the resolution.

Let P 1 be the associated DynCSP (see Section 6.2). 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), cf. Figure 5a. 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 area(s 2 ) = 6), cf. Figure 5b. 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), cf. Figure 5c. The next query is q 4 (x) = q 3 (x) ∧ ¬(s 3 M x) whose first solution is s 4 = A (cf. Figure 5d) 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 further and the process ends at n = 5.

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

Experiments

We first report an experimental study on several UCI benchmarks (see Section 7.1). We then discuss the practical use of skypatterns in a chemoinformatics case study (see Section 7.2). All experiments were conducted on a personal computer running a Linux operating system with an i3 core processor with a clock speed of 2.13 GHz and 4GB of RAM. The implementation of Aetheris refers to [START_REF] Soulet | Mining dominant patterns in the sky[END_REF]. The implementation of CP+Sky was carried out in Gecode. All source codes and data sets are publicly available at https://forge.greyc.fr/ projects/skymining/files Note that it was shown in [START_REF] Soulet | Mining dominant patterns in the sky[END_REF] that Aetheris always outperforms a baseline approach by at least a factor of 10. In addition, the collection of skypatterns is always much smaller than the collection of patterns returned by an optimal constraintased approach (i.e. assuming that an ideal end-user is able to perfectly set the thresholds and then run a usual constraint-based mining method). Therefore, this empirical study focuses on the comparison between Aetheris and CP+Sky.

Experiments on UCI benchmarks 7.1.1. Experimental protocol

We focused on 23 different (in terms of dimensions and density 5 ) datasets (see the left column in Table 5) from the UCI6 repository. We considered the set of measures M ={f req, max, area, mean, growth-rate} and selected 6 subsets: M 1 ={f req,area, mean, growth-rate}, M 2 ={f req, max, area, growth-rate}, M 3 ={f req, max, area, mean}, M 4 ={f req, max, mean, growth-rate}, M 5 ={max, area, mean, growth-rate} and M 6 =M . Measures using numeric values, like mean or max, were applied to randomly generated attribute values (within the range [0, 1]).

For each method, we report the CPU-time and the number of skypatterns for every query on the selected set of measures. Note that Aetheris first computes the set of closed patterns 7 w.r.t. M and then applies the Sky operator on the extracted collection. On the other hand, CP+Sky does not mine closed patterns as a first step but instead computes a small set of candidates using DynCSP and then applies the Sky operator. For each method, the reported CPU-times include the different processing steps. We also report for each dataset the size of the Dataset M 6 = {f req, max, area, mean, growth rate}

Averages over {M 1 , M 2 , M 3 , M 4 , M

Performance analysis

A general overview. Table 5 provides the results of CPU-times for CP+Sky and Aetheris for 138 skypattern queries (23 × 6). We report for each dataset and for every collection of measures8 :

• the number of skypatterns (the largest output is 478),

• with CP+Sky: the number of candidates and the associated CPU-time,

• with Aetheris: the number of closed patterns and the associated CPU-time.

Table 5 indicates that CP+Sky and Aetheris run within the same order of magnitude. On 16 datasets out of 23, CPU times for both CP+Sky and Aetheris are very small (less than 30 seconds). The results of the 7 remaining data sets are analyzed in more detail to highlight the differences and limitations of our proposed methods. A more detailed analysis. Figure 6 depicts a scatter plot of CPU-times for CP+Sky and Aetheris. Each point represents a skypattern query for one of the 7 selected datasets: its x-value (log-scale) is the CPU-time obtained with CP+Sky, its yvalue (log scale) the CPU-time with Aetheris. A specific color is associated to each dataset. The line y = x draws the case where Aetheris and CP+Sky have the same CPU-times. Most of the points are above this line, which means a longer runtime for Aetheris. With all the measures (i.e. M 6 ), the speed-up is 1.9 (resp. 1.53) on hypo (resp. german). The only exception is the mushroom dataset.

Another interesting result provided by Table 5 is the number of closed patterns extracted by Aetheris in comparison with the number of candidates generated by CP+Sky. The number of candidates remains small (in the thousands) compared to the number of closed patterns (in millions). Figure 7 illustrates this particular result for the selected datasets. It reports for each set of measures M i (i ∈ [START_REF] Soulet | Mining dominant patterns in the sky[END_REF][START_REF] Backstrom | Optimizing web traffic via the media scheduling problem[END_REF]) and the 7 datasets investigated in Figure 6, the number of closed patterns, the number of candidate patterns and the number of skypatterns (both methods). This figure highlights the discrepancy between the methods with the distinct lower number of representative patterns required by CP+Sky in comparison to the Aetheris method. Table 6: Comparing the CPU times for the two steps on the 7 selected datasets for M 6 .

Table 6 shows an in-depth comparison of the CPU-times for the two steps performed by CP+Sky and Aetheris for the set of measures M 6 . The second (i.e. the post-processing) step is the same for both methods and is performed using the same classical algorithm: the BNL approach [START_REF] Börzsönyi | The skyline operator[END_REF]. The time complexity of this approach is O(n 2 ) where n is the number of representative patterns generated in the first step. These results clearly show that CP+Sky takes less time than Aetheris to generate the representative patterns. This is in part explained by the huge number of closed patterns that Aetheris needs to post-process. This drawback does not exist for CP+Sky because the number of candidates remains small and thus, the post-processing step is negligible. The only exception is for the mushroom dataset, where Aetheris is very efficient

Summary

No method is constantly better on all datasets. CP+Sky usually generates a low number of candidates compared to Aetheris. The number of candidates and closed patterns seems to provide an appropriate explanation of the performances of the two methods. However, they only constitute simple indicators and do not take into account other evidence. For instance the results on the mushroom dataset may seem surprising and counter-intuitive. Even if the number of candidates (14, 599) is low compared to the number of closed patterns extracted from this dataset [START_REF] Soulet | Mining dominant patterns in the sky[END_REF]153,229), Aetheris is more performant than CP+Sky.

The mushroom dataset (which is the largest UCI dataset both in terms of transactions and items) has the lowest density (around 18%), which implies that its number of closed patterns is small w.r.t its size. The same reasoning also applies for the number of candidates. In this case, the size of the set of constraints is important, as there are as many reified constraints as transactions (cf Section 6.3). So, filtering takes much more time to generate the candidates. For this dataset, it is more efficient to compute the closed patterns and filter them, even if they are more numerous.

Following the mushroom dataset analysis, we investigated the notion of density and its impact on the performances of our two methods by generating several datasets and varying their density from 0.15 to 0.65 (we kept the numbers of items and transactions similar to the mushroom dataset). Figure 8 shows the evolution of CPU-times according to the density for both methods. As the items in the data are randomly generated to provide the density value, the number of closed patterns increases according to the density. Thus, the running time of Aetheris also increases according to this parameter. The behavior of CP+Sky is more complex due to the dynamic pruning. Having more candidate skypatterns is a benefit if these patterns are able to prune significantly the search space. The experimental study shows a good trade-off with a density close to 0.5 (note that in practice there are very few real-world datasets with a density higher than 0.5).

We also performed experiments on other data sets from the UCI repository, such as the chess (75 items, 3196 transactions, density 0.49) and the connect data sets (129 items, 67557 transactions, density 0.33). However, we were not able to complete the skypattern mining process. Aetheris was not able to complete the closed pattern mining step on either data set. For CP+Sky, the first step of candidates generation took approximatively 20 hours and generated more than 40 million candidates for the chess dataset. The application of the sky operator failed because of the quadratic complexity (i.e. O(n 2 ) ) of the BNL method. The experiments on the connect dataset with CP+Sky were aborted after more than 24 hours of computation.

Case study: discovering toxicophores

A major issue in chemoinformatics is to establish relationships between chemicals and their activity in (eco)toxicity. Chemical fragments 9 which cause toxicity are called toxicophores and their discovery is at the core of prediction models in (eco)toxicity [START_REF] Lepailleur | Automated detection of structural alerts (chemical fragments) in (eco)toxicology[END_REF]. The aim of this study, which is part of a larger research collaboration with the CERMN Lab, is to investigate the use of skypatterns for discovering toxicophores.

Experimental protocol

The dataset was collected from the ECB web site 10 . For each chemical, the chemists have associated 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 (transactions), 372 from the H400 class and 195 from the H402 class. The chemicals are encoded using 1450 frequent closed subgraphs (items) previously extracted 11 with a 1% relative frequency threshold. Therefore, the extracted skypatterns correspond to sets of chemical fragments, which are represented by frequent closed subgraphs [START_REF] Cuissart | Emerging patterns as structural alerts for computational toxicology[END_REF].

Discovering candidate toxicophores is similar to supervised descriptive rule discovery [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF], and or learning classification rules, and we therefore use growth rate as a contrast measure. Indeed, when a pattern's frequency strongly increases from class H402 to class H400, it can be considered a potential structural alert related to toxicity. If a compound includes several such fragments in its graph structure, it is more likely to be toxic. Emerging patterns model this idea using the growth rate measure. On the other hand, real-world datasets are often noisy and patterns with low frequency may be artefacts. We also use the frequency measure to ensure the representativeness of the patterns (i.e. the higher the frequency, the better).

The skypattern framework makes it possible to integrate measures coming from the background domain. In ecotoxicity, chemists know that the aromaticity measure 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 (the higher the aromaticity, the higher the toxicity hypothesis). The chemical knowledge provides the aromaticity of the chemical fragments and we compute the aromaticity of pattern as the mean of the aromaticity of its chemical fragments.

We organophosphorus moiety skypattern is a generalization of around 90 JEFs and can be seen as a kind of maximum common structure (i.e. consensus structure) of these fragments.

The main result of the study concerns the chemical interpretation of the outputs. Indeed, the generalization capability of the skypatterns leads to a reduced list of potential toxicophores easily interpretable by the chemists (cf. Figure 10). Even if the skypattern process is complete with respect to the user preferences and the dataset, the proposed list of toxicophores depends on the composition of the used dataset and the measures. We cannot hope to discover all the ecotoxicological structural alerts in one pass, because we cannot expect that all the structural alerts are present in a single dataset. But any progress in the discovery of potential toxicophores is a valuable step. The method can suggest new compounds as toxicophores, i.e. toxicophores which were previously unknown. Further in vitro experiments are required to validate such candidate toxicophores.

Note that adding the p-value as a measure in order to provide a statistical significance in the skypatterns does not change the results in this experiment. Indeed, p-value is maximized by the closed patterns adequate to frequency and with the set of measures M 5 ={growth-rate, f req, aromaticity, p-value} only the aromaticity leads to another closed patterns. Out of curiosity, we ran the experiment with M 5 and we get 28 skypatterns instead of 21 with M 4 (the 21 skypatterns extracted with M 4 are still skypatterns with M 5 ). There are no significant new insights from a chemical point of view.

Conclusion and Perspectives

In this paper, we investigate in detail the skyline pattern mining problem by studying the theoretical relationships between condensed representations of patterns and skypatterns. Based on the concept of skylineability, we have devised the static method Aetheris and the dynamic method CP+Sky. Aetheris exploits the condensed representations of patterns to provide a proper superset of skypatterns on which to apply the Sky operator. CP+Sky iteratively refines the skyline constraints using the extracted patterns. This leads to better pruning of the search space. Our approach generates the complete set of skypatterns in a generic manner (i.e. with a large set of measures that includes statistical assessments such as the p-value). The practical goal is to make the result of pattern mining useful from a user-preference point of view. One strength of the approach lies in the fact that no threshold has to be set, the end-user only needs to specify as input the dataset and the set of measures she is interested in.

An extensive empirical study as well as a case study from chemoinformatics show the efficiency and effectiveness of our two algorithms according to both quantitative and qualitative aspects. Despite the gain in generality brought by the CSP framework and the fact that Aetheris benefits from the pruning strategies based on the anti-monotonicity to extract patterns, CP+Sky competes with Aetheris and even outperforms it in some cases. However, with CP+Sky, the search order of the patterns may significantly impact the efficiency of the CSP solver. Investigating the most beneficial order in which patterns are enumerated is a promising research direction to maximize the effectiveness of the strategy of dynamically posting constraints.

Skypattern mining can generally be applied to a wide range of problems by adapting either the language or the dominance relation. For instance, the language of sequences or graphs can also produce skypatterns. The dominance relation can be changed or extended to take into account different other criteria for userpreferences. We sketch now these two issues. Language. Our formalization, and especially the skylineability notion, is general enough to be applied to a large set of languages (sequences, trees and graph for instance). However, a change in the language can impact the efficiency of the extraction methods. Regarding Aetheris, the efficiency of the approach is based on Theorem 1 involving the distinct and indistinct operators. As aforementioned, with itemset patterns and the frequency measure, the distinct operator corresponds to the well-known closed or free condensed representations of frequent patterns. Consequently, the efficient extraction of skypatterns for more complex languages (i.e. skyline sequential patterns or skyline graph patterns) is strongly tied to the advances and progress on complex condensed representations of patterns.

Evaluating the distinct operator on more complex patterns efficiently such as sequences, trees and graphs implies additional challenges. To cite one, in the case of sequences, convenient properties such as the free patterns apriori property [START_REF] Lo | Mining and ranking generators of sequential patterns[END_REF], which implies effective search space pruning, cannot be used. However, there are already many methods of extraction dedicated to closed sequential patterns, closed graphs and so on. Extending CP+Sky to other languages is a challenging task due to the difficulty of modeling complex patterns. To the best of our knowledge, only certain types of pattern in sequence mining have been successfully studied [START_REF] Coquery | A SAT-based approach for discovering frequent, closed and maximal patterns in a sequence[END_REF][START_REF] Kemmar | Mining relevant sequence patterns with CP-based framework[END_REF]. Dominance relation. The dominance relation contains two components: the measures for which basic preferences are expressed (e.g., frequency, area) and the combination of these basic preferences (here, the Pareto composition). Primitivebased measures are flexible enough to allow the user to express a wide variety of criteria. Indeed, classical interestingness measures for pattern mining (such as frequency, growth rate), utility functions and measures of statistical significance (like the p-value) fall within this framework. Of course, Aetheris, as mentioned above, depends again on condensed representations that are well-adapted for the desired measures. Conversely, all interestingness measures are easily expressible with CP+Sky. Through its declarative nature, CP+Sky offers via CSP a very flexible way to change the dominance relationship. For instance the strict dominance (i.e. a pattern is dominated by another pattern when the latter has a better value for all measures in M ), is easily configurable with CSP and this relaxation of the dominance relation leads to the mining of soft-skypatterns [START_REF] Ugarte | Mining (soft-) skypatterns using dynamic CSP[END_REF].

Exploratory skypattern mining. We think that the skypattern mining is particularly well suited to exploratory research. Indeed, a strength of our approach is to propose a reduced collection of patterns to the data expert who can quickly analyze it. It would be interesting to integrate the user feedbacks to make skypattern mining more iterative and more exploratory. An interesting avenue is to offer an interactive way to refine the preference criteria by computing the skypattern cube according to all possible subsets of measures [START_REF] Ugarte | Computing skypattern cubes[END_REF] and then assist the user with an intuitive navigation. We claim that the skypattern cube exploration will provide a better understanding of the impact of the measures on the problem at hand. Other kinds of interactions are also possible, such as discarding a skypattern to reveal patterns that were previously dominated and could become interesting.

Figure 1 :

 1 Figure 1: Example of skypatterns for the set of measures M = {f req, length} (all the other patterns are in the dominated area).

3 ⊇Figure 2 :

 32 Figure 2: Unified view of skypattern mining with Aetheris and CP+Sky.

Figure 3 :

 3 Figure 3: Use of skylineability in the general case (cf. Figure 3a, top) and in our running example (cf. Figure 3b, bottom) in which AB = f req B: we directly knows that AB M B without considering area (length(AB) > length(B)).

  Expr. e Primitive(s) c(e) c(e) e 1 θe 2 θ ∈ {+, ×, ∪} c(e 1 ) ∪ c(e 2 ) c(e 1 ) ∪ c(e 2 ) e 1 θe 2 θ ∈ {-, /, binomial, ∩} c(e 1 ) ∪ c(e 2 ) c(e 1 ) ∪ c(e 2 ) constant -

Table 4 :Definition 5 (

 45 Applying the minimal and maximal convertersIn practice, as the skypatterns are computed for a set of measures, we extend the minimal and maximal converters: Minimal and maximal skylineable converters). The minimal and maximal skylineable converters defined by Table3 forany primitive-based measure are naturally extended to a set of primitive-based measures M ⊆ M: c(M ) = m∈M c(m) and c(M ) = m∈M c(m).

Property 4 .Figure 4 :

 44 Figure 4: Computing the skypatterns with respect to {freq; area} from the running example

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

Figure 5 :

 5 Figure 5: Solving the running example using DynCSP.

(a) M 1 (

 1

Figure 6 :

 6 Figure 6: Comparing CPU times on the 7 selected datasets for M i , i ∈ [1..6].

Figure 7 :

 7 Figure 7: Comparing # of patterns on the 7 selected datasets for M 1 , . . . , M 6 .

Figure 8 :

 8 Figure 8: Measuring the impact of the density for the two methods.

Figure 10 :

 10 Figure 10: Examples of environmentally hazardous compounds related to skypatterns S4, S3, S2, P1, and S1.

Table 1a

 1a

	Tid	Items	Items val
	t 1 A B C D E F	A	10
	t 2 A B C D E F	B	55
	t 3 A B		C	70
	t 4	D	D	30
	t 5 A	C	E	15
	t 6	E	F	25
	(a) A toy data set T
	N ame	Definition
	area
				presents a
	transactional dataset T where 6 transactions denoted by t 1 , . . . , t 6 are described
	by 6 items denoted by A, . . . , F .

Table 2

 2

	: A subset of the primitive-based measures
	due to val : I → [0, 1] (e.g., the support of each item in p-value definition).
	Finally, f is the intension i.e. f (T ) = {i ∈ I | ∀t ∈ T, i ∈ t}, and g is the
	extension

Table 5 :

 5 Comparing the two methods on 23 UCI datasets (a detailed summary). condensed representation w.r.t M and the number of candidates to respectively analyse the behaviors of Aetheris and CP+Sky.

	1
	9,808.80
	6
	3,393.20

  tested several combinations of measures: M 1 ={growth-rate, f req}, M 2 ={growth-rate, aromaticity}, M 3 ={f req, aromaticity} and M 4 ={growth-rate, f req, aromaticity}.

				Skypatterns
	# of Sky-	patterns	# of Candidates	CP+Sky CPU-Time	# of closed patterns	Aetheris	CPU-Time
	M 1 ={growth-rate, f req}	8 613 18m:34s	41, 887 19m:20s
	M 2 ={growth-rate, aromaticity}	5 140 15m:32s	53, 201 21m:33s
	M 3 ={f req, aromaticity}	2 456 16m:45s 157, 911 21m:16s
	M 4 ={growth-rate, f req, aromaticity}	21 869 17m:49s	69, 827 21m:40s

Table 7 :

 7 Skypattern mining on ECB dataset.7.2.2. Performance analysisTable7reports, for each set of measures M i ∈ [1..4]: (i) the number of skypatterns, (ii) for CP+Sky, the number of candidates and the associated CPU-time and (iii) for Aetheris, the number of closed patterns and the associated CPU-time. CP+Sky outperforms Aetheris in term of CPU-times. Moreover, the number of candidates for CP+Sky is drastically smaller than the number of closed patterns computed by Aetheris. It clearly shows the usefulness of filtering via the dynamically posted constraints.

Thresholds are entirely optional, depending on the analyst's needs and do not depend on the algorithm.

http://www.gecode.org/

For our implementation, we used the most constrained variable order heuristics, which branches over the variable contained in most constraints; this order is dynamic (updated during the search).

The density of a dataset is t∈T |t|/(|T | × |I|).

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

We use an absolute minimal frequency threshold of 1.

Reported values in columns[START_REF] Backstrom | Optimizing web traffic via the media scheduling problem[END_REF][START_REF] Fan | Using artificial anomalies to detect unknown and known network intrusions[END_REF][START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF][START_REF] Mannila | Levelwise search and borders of theories in knowledge discovery[END_REF] are associated to M 6 . But, reported values in columns[START_REF] Wrobel | An algorithm for multi-relational discovery of subgroups[END_REF][START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF][START_REF] Geerts | Tiling databases[END_REF][START_REF] Bonchi | A constraint-based querying system for exploratory pattern discovery[END_REF][START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF] represent average values over M 1 , M 2 , M 3 , M 4 and M 5 .

A fragment denotes a connected part of a chemical structure having 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 .

Acknowledgments. This work is partly supported by the ANR (French Research National Agency) funded projects FiCoLoFo ANR-10-BLA-0214 and Hybride ANR-11-BS002-002.

Qualitative analysis

We now analyse the skypatterns qualitatively by comparing them with wellknown environmental toxicophores [START_REF] Sushko | Toxalerts: A web server of structural alerts for toxic chemicals and compounds with potential adverse reactions[END_REF]. With the growth rate and frequency measures (i.e. M 1 ), only 8 skypatterns are found, among those we have emphasized 3 well-known toxicophores. Figure 9a depicts these skypatterns denoted P i , one of them is on the y-axis. Two of them are components of widespread pesticides, namely the chloro-substituted aromatic ring (P 1 : {Clc}) and organophosphorus moiety (P 3 : {OP, OP=S}). The third one, the phenol ring (P 2 : {c1(ccccc1)O}) is related to hydrophobocity and formation of free radicals [START_REF] Hansch | Comparative QSAR evidence for a free-radical mechanism of phenol-induced toxicity[END_REF].

The most interesting results follow from the addition of the background knowledge. Indeed, adding the aromaticity measure leads to skypatterns with novel chemical characteristics. We discuss the results obtained with the growth rate, frequency and aromaticity measures (i.e. M 4 ). Once again, the whole set of skypatterns remains small and can lends itself to straight-forward analysis. 21 skypatterns are mined (see Figure 9b). To simplify the picture, the S i denote sets of skypatterns sharing a common chemical feature. The figure emphasizes several environmentally hazardous chemical fragments: the phenol ring (S 4 ), the chloro-substituted aromatic ring (S 3 ), the alkyl-substituted benzene (S 2 ), and the organophosphorus moiety (P 1 ). Besides, information dealing with nitrogen aromatic compounds is also extracted (S 1 ). The comparison of this list of patterns with jumping emerging fragments (JEF) extracted from previous experiments [START_REF] Lozano | Introduction of jumping fragments in combination with QSARs for the assessment of classification in ecotoxicology[END_REF] highlights the generalization potency of the skypatterns. As an example, the