Threshold-free Pattern Mining Meets Multi-Objective Optimization: Application to Association Rules

1 Introduction

Constraint-based pattern mining is a fundamental data mining task, extracting locally interesting patterns to be either interpreted directly by domain experts, or to be used as descriptors in downstream tasks, such as classification or clustering. Since the publication of the seminal paper [Agrawal and Srikant, 1994], two problems have limited the usability of this approach: 1) how to fix thresholds which are involved in many of these constraints, and 2) how to deal with the large result sets that often number in the thousands or even millions of patterns. Translating user preferences into top-k constraints [Wang et al., 2005] w.r.t. to some quality measures presents a serious drawback as the choice of k is not obvious. Moreover, combining several measures into a single function is difficult. Post-processing results via condensed representations [Pasquier et al., 1999] still typically leaves many patterns, while pattern set mining [De Raedt and Zimmermann, 2007] just pushes the problem further down the line.

A decade ago, several approaches have promoted the discovery of more complex interactions between patterns. An example of such interactions can be found in multi-objective optimization (MOO) [Figueira et al., 2005] where several

(often conflicting) objectives need to be simultaneously optimized. Without preferences, it is common to assess solutions of best compromise according to Pareto dominance. A solution is said to be non-dominated (or Pareto optimal) if we cannot improve an objective without degrading another.

Regarding the association of pattern discovery and MOO, a few approaches have been proposed. In [Ghosh and Nath, 2004], a multi-objective rule mining using genetic algorithms was proposed. [van Leeuwen and Ukkonen, 2013] proposes an algorithm to mine skyline subgroups. The notion of skyline patterns is exploited in [Ugarte et al., 2017] to mine high quality patterns according to multiple measures.

This paper continues a line of work that aims at connecting Constraint Programming (CP) to pattern mining to solve some data mining tasks [Guns et al., 2011; Kemmar et al., 2017]. We propose a new compact and flexible MOO CP model to efficiently discover Pareto optimal patterns (a.k.a skypatterns) according to a set of measures. Our model exploits condensed pattern representations to reduce the mining effort. To that end, we design a new global constraint, ADEQUATECLOSURE, for ensuring the closeness constraint over multiple measures. We show how skypatterns can be used to find high-quality non-redundant association rules without the use of thresholds. Finally, we show the relevance of our approach on both UCI datasets and a case study related to the analysis of genes expression data integrating multiple external genes annotations to discover associations between them.

2 Preliminaries

2.1 Itemset and Association Rules Mining

Let I = {1, ..., n} be a set of n items, an itemset (or pattern) P is a non-empty subset of I. The language of itemsets corresponds to LI = 2I \∅. A transactional dataset D is a multiset of transactions over I, where each transaction t ⊆ I; T = {1, ...,m} a set of m transaction indices. An itemset P occurs in a transaction t, iff P ⊆ t. The cover of P in D is the set of transactions in which it occurs: t(P) = {t ∈ D | P ⊆ t}. The support of P in a dataset D is the size of its cover: sup(P) = |t(P)|. An itemset P is said to be frequent in D if sup(P) ≥ θ, where θ is a userspecified minimal support threshold. Given T ⊆ D, i(T) is the set of items that are common to all transactions in T: i(T) = {i ∈ I | ∀t ∈ T, i ∈ t}. We define by clos a closure operator, given as clos(P) = i ◦ t(P) = i(t(P)). The closure of an itemset P is the set of common items that belong to all transactions in t(P): clos(P) = {i ∈ I | ∀t ∈ t(P), i ∈ t}. An itemset P is said to be closed iff clos(P) = P. The closure operator is at the root of the definition of the equivalence classes, and thus the condensed representation of the itemsets [Pasquier et al., 1999]. Interestingly, [Soulet and Cr´emilleux, 2008] proposed an adequate closure operator to measures other than the support.

Definition 1 (Adequate closure operator) Let M be a set of measures. The closure of an itemset P w.r.t. M (called adequate closure), denoted by closM(P), is the set of items s.t. closM(P ) = {i ∈ I | ∀m ∈ M, m(P ∪ {i}) = m(P )}.

An item i belongs to closM(P) iff each measure m ∈ M remains constant with the addition of i. Proposition 1 extends the closure operator clos to the set M: two itemsets P and Q are in the same equivalence class iff closM(P) = closM(Q). Thus, all the itemsets belonging to the same equivalence class have the same value for each m ∈ M.

Proposition 1 Let M be a set of measures, closM is a closure operator. P is closed w.r.t. M iff closM(P) = P .

Many well-known interestingness measures based on support are used to evaluate the relevance of itemsets (see Table 1). All-confidence (aconf) is a measure of interestingness of a pattern that indicates the dependency between all of the items in the pattern [Omiecinski, 2003]. The aconf of an itemset P can be defined as the ratio between its support and the maximum support of its items. This simply states that allconfidence is the smallest confidence of any rule for the set of items of P. Note that the maximum value for the denominator will occur when the subset of P consists of a single item. Hence, it is only needed to compute the support of each item. Additional information (such as numerical values associated to items) can also be used. Given a function val : I → R+, we extend it to an itemset P and denote by P.val the multi-set {val(i) | i ∈ P}. Note that val may also be the support. This kind of function is used with the usual primitive-based measures like sum, min and max. For instance, sum(P.val) is the sum of val for each item of P .

Association rules mining. An association rule is an implication r : X ⇒ Y where X and Y are itemsets such that X ∩ Y = ∅ and Y ̸= ∅. X is called antecedent of the rule and Y its consequent. The support of the rule is given by sup(r) = sup(X ∪ Y ). The confidence of the rule indicates how often the rule has been found to be true, i.e. conf(r) = sup(r) sup(X) . Given a minimum confidence c and a minimum support θ, the goal is to find all the rules r such that conf(r) ≥ c and sup(r) ≥ θ. The lift of a rule r is defined as lift(r) = conf(r)×|D| sup(Y ) . One common use of lift is to measure the correlation between X and Y : a value greater (resp. smaller) than 1 means that X and Y are positively (resp. negatively) correlated while a value close to 1 means that X and Y are independent. To reduce the number of rules, Bastide et al. [Bastide et al., 2000] proposed the notion of minimal non-redundant rules (MNR). An association rule r : X ⇒ Y is an MNR iff: (1) sup(r) ≥ θ and conf(r) ≥ c; (2) X∪Y is

.

closed w.r.t. the support; and (3) X is a generator. An itemset X is said to be a generator if it has no frequent subset with the same support. In the sequel, we will show how our approach avoids the hard task of setting these thresholds to get interesting patterns, thanks to multi-objective optimization.

2.2 Multi-Objective Optimization (MOO)

A MOO problem P [Figueira et al., 2005] consists of a set of m objective functions fi : Rn → R for i = 1..m and a discrete set X of feasible solutions (a.k.a. decision space). For simplicity, we assume (w.l.o.g.) that the objective functions are to be maximized simultaneously. We note F as the vector-function F : Rn → Rm, which maps each feasible solution x ∈ X into the corresponding objective vector F (x) = (f1(x), . . . , fm(x)). We denote by Y the image of X in the objective space, s.t. Y = {y|y = F(x), x ∈ X}. Now, comparing solutions in X amounts to comparing solutions of the objective space Y. In the absence of the decision maker's preferences, the objective vectors are commonly compared using the Pareto dominance. Let's consider y, y′ ∈ Y be two solutions of P. We say that y dominates y′ , denoted y ≻ y′ , iff : ∀i ∈ [1..m] : yi ≥ y′i and ∃j ∈ [1..m] : yj > y′j . A solution y∗ ∈ Y is Pareto optimal (a.k.a. efficient) iff there is no solution y ∈ Y that dominates y∗ , i.e. ∄y ∈ Y : y ≻ y∗ . The set of all efficient solutions is called the Pareto front.

Definition 2 (Archive) An archive A ⊆ Y is a set of solutions s.t. there is no solution in A that dominates another solution in A: ∄y, y′ ∈ A : y ≻ y′ .

Our mining task is the discovery of the Pareto optimal patterns w.r.t. a set of measures (objectives) M. For a given pattern P , each variable of the objective vector (obj1, ..., obj|M|) represents the value m(P) of the measure m ∈ M. A pattern associated to a Pareto optimal solution is called a skypattern. The skypattern mining problem consists of finding the set Sky of all skypatterns w.r.t. M. The main drawback is that the number of candidate skypatterns is exponential in the worst case (i.e. equals to all patterns, |Sky| = 2|I| - 1). Fortunately, Soulet et al. [Soulet et al., 2011] proposed maximal skylineability to reduce the mining effort. It consists to find a set of measures M ′ such that each skypattern w.r.t. M is either closed w.r.t. M ′ or is a subset of a skypattern closed to M ′ . In other words, the set of skypatterns w.r.t. M and closed w.r.t. M ′ forms a condensed representation of the full set of skypatterns. Thus, we only focus our search to the set of closed patterns w.r.t. M ′ . For instance, M = {sup(X), area(X), aconf(X)} is maximally M ′ = {sup(X),max(X.sup)}-skylineable because area strictly increases with the size (when sup remains constant), while aconf remains constant (when sup(X) and max(X.sup) remain constant). In other words, if a pattern X is a subset of pattern Y , sup(X) = sup(Y ), max(X.sup) = max(Y.sup), then we have the guarantee that Y ≻ X w.r.t. the set of measures M. In this paper, we will not cover how to get M ′ from M, since it would be beyond its scope. For further details, we refer the reader to [Soulet et al., 2011].

3 ACPModel for Mining Skypatterns

The CP paradigm [Hoeve and Katriel, 2006] is at the core of generic approaches for pattern mining. With the recent development of global constraints with efficient filtering algorithms, CP became competitive for solving some data-mining tasks [Belaid et al., 2019; Schaus et al., 2017; Kemmar et al., 2017]. In this section, we present our CP model, called CLOSEDSKY, taking benefit of global constraints in order to get an efficient and compact model for mining skypatterns. To build this model, we need a transactional dataset D, a set of measures M and an archive A (see definition 2), which is dynamically updated each time we find a new solution, since A should remain domination-free. The CLOSEDSKYD,M,A(x, obj) model is given as follows:

• (a) Variables. Our model has: (i) n Boolean variables x, where xi represents the presence of the item i ∈ I in the pattern. (ii) objective variables: obj is a vector of integer variables, s.t. obji represents the value of a measure m ∈ M. (b) Constraints. Our model exploits a set of constraints for which efficient pruning algorithms exist.

- Pareto. Constraint (1) is a global optimization constraint, that is used to extract skypatterns without any additional dynamic constraints (see [Ugarte et al., 2017]). Formally, PARETOA(obj) ≡ ∧ y∈A ∨ i=1..|M| obji > yi. It enforces that

the next objective vector obj = (obj1, ..., obj|M|) is not dominated w.r.t. the archive A, i.e. ∄y ∈ A : y ≻ obj. This constraint is fully detailed in [Schaus and Hartert, 2013].

• Closedness. We introduce Constraint (2) as a new global constraint to ensure that x is closed w.r.t. a set of measures M ′ . It is proposed to genuinely discover condensed representations of patterns (without reified constraints). M ′ is automatically computed s.t. M is maximally M ′ -skylineable.

The filtering rules of this constraint are given in Section 3.1.

• Measures. Constraint (3) is used to link each objective variable obji to a measure m ∈ M such that obji = m(x). This constraint also involves the definition of each measure m ∈ M. For instance, if M = {sup, area}, then MEASURESD,M can be defined as follows:

where the COVERSIZE global constraint [Schaus et al., 2017] models the sup(x) measure, i.e. obj1 = |t(x)|, while the Constraint (5) models the area of x as the product of its support (saved in obj1) by its size.

̸

3.1 The Global Constraint ADEQUATECLOSURE

In the following, we introduce our global constraint ADEQUATECLOSURE for mining condensed representations of patterns w.r.t. M ′ . This is achieved thanks to the closure operator closM′ which is adequate for a set of measures. Contrary to [Ugarte et al., 2017], our global constraint requires neither reified constraints nor auxiliary variables. All the proofs are given in the supplementary material [Vernerey et al., 2022]. We will use the notations : x+ = {i ∈ I|dom(xi) = {1}}, x- = {i ∈ I|dom(xi) = {0}}, x∗ = I \ {x+ ∪ x-}, where dom(xi) denotes the set of allowed values of the variable xi.

Definition 3 (ADEQUATECLOSURE) Let x be a vector of Boolean variables, D a transactional dataset and M ′ a set of measures. The constraint ADEQUATECLOSURE D,M′(x) holds iff closM′ (x+) = x+.

Now, we define the closure inclusion operator clinc exploited by our global constraint filtering rules, for mining adequate condensed representations w.r.t. a set of measures M ′ .

Definition 4 (Closure inclusion) Let x be a partial assignment of variables in {x1, . . ., x|I|}, M ′ a set of measures and i an item. clinc(x+, i,M ′ ) holds iff ∀m ∈ M ′ ,m(x+ ∪ {i}) = m(x+).

Definition 4 provides a necessary and sufficient condition for the property of pattern condensation with respect to a set of measures M ′ , when extending the current itemset x+ with a free item (from x∗ ). In other words, clinc(x+, i,M ′ ) ⇔ i ∈ closM′(x+). Lemma 1 characterizes a consistent partial assignment w.r.t. ADEQUATECLOSURE constraint, that is a partial assignment that can be extended to a solution which satisfies this constraint.

Lemma 1 (Consistent partial assignment) Let x+ be a partial assignment of variables in {x1, . . ., x|I|} and M ′ a set of measures. x+ is a consistent partial assignment iff ∃j ∈ x- s.t. clinc(x+, j,M ′ ) holds.

The propagator we propose for ADEQUATECLOSURE is based on two filtering rules given through Proposition 2.

Proposition 2 (Filtering rules) Given a consistent partial assignment x, a set M ′ of measures, for any i ∈ x∗ : (R1) if clinc(x+, i,M ′ ) ⇒ 0 /∈ dom(xi). (R2) if ∃j ∈ x- s.t. clinc(x+ ∪ {i}, j, M ′ ) ⇒ 1 /∈ dom(xi).

The first rule filters 0 from dom(xi) if {i} is a closure inclusion of x+ (see Def. 4). It allows to add all items i ∈ x∗ that are required to extend x+ to a closed pattern w.r.t. M ′ . The second rule filters 1 from dom(xi) if clinc(x+ ∪ {i}, j, M ′ ) holds where j ∈ x-. Roughly speaking, this rule checks whether x+ ∪ {i} cannot be extended to a closed itemset w.r.t. M ′ without adding j (see Lemma 1).

4 MiningMNRs using Skypatterns

In association rules mining, finding appropriate values for c and θ (which are involved in confidence and support constraints) without prior knowledge is very difficult, unless the end-user is able to perfectly manage thresholds selections in this paradigm. In this section, we show how skypatterns can be used to mine high-quality MNRs without any threshold. The whole process consists of two solving steps:

• Generating skypatterns: compute skypatterns with CLOSEDSKY model detailed in Section 3, using the set of measures Mr = {sup, area, aconf }.
• Generating MNRs: generate all MNRs from the collection of representative skypatterns computed in the first step using a dedicated CP model.

(a) Generating skypatterns. The main idea is to take advantage on a condensed representation of LI to compute a reduced but relevant collection of representative skypatterns w.r.t. Mr for mining MNRs. Indeed, the maximal skylineability principle allows us to reduce Mr to M ′r = {sup(X),max(X.sup)}. Moreover, the set of patterns maximizing both support and All-confidence measures (a.k.a. skypatterns) might be the more interesting ones for generating relevant rules. However, as these measures are antimonotone (i.e. they decrease with specialization), small patterns are more likely to be selected. To increase the average length of the extracted skypatterns and thus the size of the MNRs generated, we add the area measure to Mr.

Pareto optimal patterns w.r.t. Mr are interesting since they lead to rules with a high support and/or high confidence. Let P = X ∪ Y be a skypattern and r : X ⇒ Y be a rule. We have conf(r) ≥ aconf(P) and sup(r) = sup(P). This can be seen directly from the definition. As we are maximizing both the aconf and sup measures when computing skypatterns, all rules that can be produced from P have a confidence (resp. support) greater than or equal to our minimum aconf(P) (resp. sup(P)) value. Thus, all the extracted rules are valid since they satisfy the implicit thresholds c = aconf(P) and θ = sup(P). Moreover, our approach allows to discover rules with a low support but a high confidence (i.e. rare rules). This kind of rules is hard to extract with a classic rule miner since (1) the user should tune the thresholds accordingly, (2) the number of rules extracted with low thresholds may be prohibitive.

(b) Generating MNRs. Let clossup(P) be the closure of P w.r.t. {sup} and clos-sup (P ) = clossup(P ) \ P .

First, it is interesting to stress that the first MNR condition (i.e. sup(r) ≥ θ and conf(r) ≥ c) is satisfied since c = aconf(P) and θ = sup(P). Thus, our MNRs generation step is threshold-free. Second, to be an MNR (2nd condition), we need to ensure that, for any rule r : X ⇒ Y , P = X ∪ Y must be closed w.r.t. {sup}. However, P can be closed w.r.t. M ′r without being closed w.r.t. sup ∈ M ′r . To satisfy the second MNR condition, we impose that X ∪ Y = clossup(P). However, we have aconf(P) ≥ aconf(clossup(P)) which means that the confidence of the generated rules might be smaller than aconf(P). That is why we add the constraint clos-sup (P) ⊆ Y . Finally (3rd condition), we enforce that X must be a generator using the global constraint GENERATOR introduced by [Belaid et al., 2019]. As a summary, given the set Sky of skypatterns w.r.t. Mr, we generate all the MNRs r : X ⇒ Y s.t. ∃P ∈ Sky : X∪Y = clossup(P) ∧ clos-(P) ⊆ Y ∧ GENERATOR(X). We note that all the rules generated from the closure of the skypatterns have the same support and confidence as those that could be generated using skypatterns directly. More interestingly, these rules are MNRs. Proposition 3 summarises this important result.

Proposition 3 Let P be a skypattern, r : X ⇒ Y a rule s.t. X ∪ Y = P, and X a generator. Let r′ : X ⇒ Y ′ be a rule s.t. X ∪ Y ′ = clossup(P) ∧ Y ′ = Y ∪ clos-(P). r′ is an MNR with sup(r) = sup(r′ ) ∧ conf(r′ ) = conf(r) ≥ aconf (P ).

Hence, extracting all MNRs from Sky can be modeled using three vectors x, y and z of n Boolean variables, where xi, yi and zi respectively represent the presence of item i ∈ I in the antecedent of the rule, in the consequence of the rule, and in the rule as a whole z. A forth vector sky of |Sky| Boolean variables is also introduced. Our model involves different types of constraints : a channeling constraint ensuring that z = (x ∪ y); one channeling constraint per s ∈ Sky ensuring that z = clossup(s) and clos-(s) ⊆ y and GENERATOR(x). Other constraints ensure that both the antecedent and the consequence of the rule are not empty and that an item cannot simultaneously appear in both of them.

5 RelatedWork

Computing skypatterns. [Soulet et al., 2011] have proposed AETHERIS, which proceeds in two steps. First, condensed representations of patterns w.r.t. the set M ′ are extracted. Then, a post-processing step is applied to remove all patterns that are not skypatterns. [Ugarte et al., 2017] also proposed a two-step approach (called CP+SKY), but contrary to AETHERIS, CP+SKY dynamically builds a more concise representation thanks to constraints on the dominance relation, which are dynamically added during the mining. In [N´egrevergne et al., 2013], the concept of dominance programming is used to propose a generic method extending relational algebras towards pattern mining. The solving step is similar to the technique used in CP+SKY, but does not exploit the skylineability principle. Our approach also benefits from theoretical relationships between pattern condensed representations and skypatterns but requires no post processing step and exploits global constraints to efficiently extract condensed representations of patterns and their Pareto fronts.

Computing MNRs. Several algorithms have been proposed to extract ARs and MNRs. ECLAT-Z [Szathmary et al., 2008] is the most efficient one. Omiecinski [Omiecinski, 2003] proposed an algorithm for mining ARs with a minimum All-confidence. Belaid et al. [Belaid et al., 2019] proposed a CP model for mining ARs and MNRs. SAT-based approaches have also been proposed [Izza et al., 2020]. Unlike our proposition, all these methods require thresholds.

6 Experimental Evaluation

We report an experimental study on UCI datasets and on a case study from gene expression analysis. Experiments were conducted on Intel(R) Xeon(R) CPU E7-8870, 2.10GHz with a RAM of 1.48 TB and a time limit of one hour. Our approach is implemented in Java top-on the Choco solver [Prud'homme et al., 2016] version 4.10.8, a Java library for constraint programming, and is publicly available [Vernerey et al., 2022]. We implemented a variant of CLOSEDSKY (denoted CLOSEDSKY-WC) ensuring a weaker consistency by disabling the filtering rule (R2). First, we carry out a comparison to enumerate skypatterns. For baseline comparison, we retain the CP-based method CP+SKY implemented using Choco library and the C++ implementation of the specialized method AETHERIS. Second, we perform an evaluation to mining MNRs, where we retain the CPbased method CP4MNR [Belaid et al., 2019] and the specialized method ECLAT-Z [Szathmary et al., 2008]. For all the skypattern mining experiments, we use the following heuristic: we select the free item i such that sup(x+ ∪ {i}) is minimal and we first instantiate it to 0.

6.1 UCI Datasets

We evaluate our approach on six datasets of the FIMI repository 1 . We consider two sets of measures Ms = {sup, area, gr,mean,max} and Mr = {sup, aconf, area}. Measures using numeric values, like mean or max, were applied to randomly generated attribute values (within the range [0, 1]) because the used repositories have no variables with numeric values. We stress that all measures having continuous values are encoded as integer decision variables.

Mining skypatterns. Table 2a reports comparative results of CLOSEDSKY against CP+SKY and AETHERIS. We report the number of skypatterns |Sky|, which is the same for all methods, and the total CPU times (in seconds) for each dataset. Since AETHERIS does not implement the aconf measure, we do not include it for the set Mr. As one can observe, the number of skypatterns generated is very low. Regarding the runtime, CLOSEDSKY outperforms CP+SKY on almost all tested datasets. Moreover, for some datasets e.g., Chess, Heart-cleveland and Mushroom, the gain is impressive. This is due to the huge number of reified constraints required by CP+SKY to model the closeness constraint. Interestingly enough, our approach overpasses the specialized algorithm AETHERIS. The huge number of closed patterns w.r.t. M ′ computed by AETHERIS in the first step makes the whole extraction process intractable for large datasets. Finally, we can notice that CLOSEDSKY-WC greatly improves the performance of CLOSEDSKY, e.g., Connect dataset.

Mining MNRs. We apply our two-step approach SKY4MNR (see Sect. 4) to extract relevant MNRs. We use CLOSEDSKY-WC to perform the skypatterns generating step. CP4MNR and ECLAT-Z require to fix the values for thresholds c and θ which are involved in confidence and support constraints. We set c to mins∈Skyaconf(s) and θ to mins∈Skysup(s). This allows to generate a superset of all the MNRs extracted by SKY4MNR. Table 2b reports comparative results of SKY4MNR against CP4MNR and ECLAT-Z. It reports the number of MNRs (obviously, the same for both CP4MNR and ECLAT-Z) and the total CPU time (in seconds) for each dataset. The table shows that the reduction in the number of generated MNRs is huge. Remarkably, for the dataset Mushroom, this reduction is still drastic (from 105 to 24). It is noteworthy that SKY4MNR finds these MNR sets in less than 2 seconds on almost all tested datasets. For the Pumsb dataset, SKY4MNR takes 141 seconds while CP4MNR and ECLAT-Z reaches TO.

1 fimi.ua.ac.be/data

Qualitative analysis of MNRs. To analyse the set of all MNRs R generated by each approach (ECLAT-Z and CP4MNR result in the same set of MNRs), we apply to the result of each approach a postprocessing step to discard all MNRs that are not on the Pareto front w.r.t. three rule assessment measures sup, conf and lift as follows: Let f be a mapping from R to IR3 that associates, to each rule r ∈ R, a data point f(r) ∈ IR3 with coordinates (sup(r), conf(r), lift(r)). Let F = {f(r) | r ∈ R}. Applying a skyline extractor method on F ensures to provide the Pareto front points. Figs. 1a-1c plot their values according to measures sup and conf. We can observe that most of the rules given by SKY4MNR are highly confident; the vast majority of the rules have confidences between 90 and 100 %. Moreover, their relative support ranges from 50 to 100 %, suggesting a trade-off between support and confidence. Interestingly, for the Mushroom dataset, SKY4MNR is able to identify rules with the lowest relative support and with the highest confidence and then lift (see suppl. material) without having to set any thresholds. This is a particularly distressing result for the traditional rule generation framework, unless the end-user is able to perfectly manage thresholds selection, which may seem unrealistic. Fig.1 (in suppl. material) plots the values of sup and lif t for all skyline points. We have similar observations as for support vs. confidence: SKY4MNR is able to find rules that are close to the skyline points.

6.2 Genes Expression Data

The aim of this study is to investigate the use of skypatterns to discover relationships between gene expression profiles and biological knowledge describing known gene properties represented as annotations in biological databases. Experiments were carried out on Eisen et al. genomic dataset 2 containing expression measures of 2465 Yeast genes for 79 biological conditions. Each yeast gene was annotated with the GO IDs of its associated terms in Yeast Gene Ontology, the PubMed IDs representing its associations with research papers, the IDs of the KEGG pathways in which it is involved, its phenotypes annotations and the names of the transcriptional regulator genes. All annotations were transformed into Boolean data, indicating if an annotation pertains or not to a given gene. The resulting datset is a matrix of 2465 transactions representing yeast genes and 9634 items representing discretized gene expression measures and gene annotations.

Mining skypatterns. CLOSEDSKY-WC again obtains the best performance: it takes 372 seconds to complete the extraction, which results in a total of 13 skypatterns, while the two approaches CP+SKY and AETHERIS run into Time Out. Interestingly enough, CLOSEDSKY also runs into Time Out.

Mining MNRs. We report comparative results of SKY4MNR against CP4MNR and ECLAT-Z. We also

2 i3s.unice.fr/∼pasquier/web/

(b) Heart-cleveland

Table 3: Examples of MNRs generated by SKY4MNR. heat3 and ndt80 refer to time points of the heat shock and sporulation experiments, respectively. ↓ denotes an under-expression. The prefixes go, path, pmid, pr allow to identify GO terms, KEGG pathways, PubMed ids and names of transcriptional regulators, respectively.

compared to GENMINER [Martinez et al., 2008], a specialized tool for mining MNRs from gene expression data. It uses the NORDI algorithm for discretizing continuous values and the CLOSE algorithm [Pasquier et al., 1999] for MNRs extraction. Recall that SKY4MNR is threshold-free. For other approaches, we consider the same thresholds θ and c used in GENMINER, i.e. θ = 0.3% ( at least 7 genes) and c = 50%. GENMINER found more than 1.33 × 106 MNRs within the time limit of 2 hours, while CP4MNR extracted 364119 MNRs in 364 seconds. Applying SKY4MNR results in a total of 63 MNRs in 375 seconds. Finally, ECLAT-Z runs into MO.

Rules analysis. Table 3 shows three forms of rules extracted by SKY4MNR. Rules with the form annotations ⇒ expressions (see rules 5-7) mean that a group of gene associated with a specific set of annotations is likely to be overexpressed or under-expressed. Rules with the form expressions ⇒ annotations mean that when a group of genes is overexpressed or under-expressed in a set of biological conditions, these genes are likely to have the corresponding gene annotations (see rules 8-10). For instance, rule 8 highlights a group of genes involved in ribosomal organization (path:03010) that are under-expressed after both a heat shock and a sporulation experiments [Carmona-Saez et al., 2006]. Finally, rules 1-4 reveal possible links between annotations from different sources like the relationship between KEGG pathways and Gene Ontology terms. Almost all the rules of Table 3 have been highlighted in [Martinez et al., 2007].

The expressiveness of our CP approach allows to ask for rules with some specific items in the antecedent and/or consequent or for rules not involving a particular set of items. For rules of the form 1 and 2, we imposed the presence of at least one expression item in the skypattern extraction step. We also forbidden the presence of the pimd items from the patterns because too many of them contain only pimd items. However, their closure may contain such items. Such constraints are not directly handled by GENMINER, a post-processing step to filter out the undesirable patterns is required.

7 Conclusions

We have proposed a new compact and flexible MOO CP model to efficiently mine Pareto optimal patterns according to a set of measures. Our model exploits condensed pattern representations that allows us to reduce the mining effort. We designed a new global constraint for ensuring the closeness constraint over multiple measures. We showed how skypatterns can be used to find a small but interesting set of MNRs without the use of thresholds. An extensive campaign of experiments conducted over UCI datasets and gene expression data has shown the effectiveness of our approach for both skypattern and association rules mining compared to CP based and specialized approaches.

(a) Anneal

(c) Mushroom