A Symbolic Approach to Computing Disjunctive Association Rules from Data

1 Introduction

Association rule mining task aims at generating within a given transaction dataset a set of rules of the form X → Y , where X (called the antecedent) and Y (called the consequent) are sets of items [Rakesh et al., 1993]. Intuitively, these rules express that transactions in the database containing the items in X tend to also contain the items in Y . Such rules are of interests in many real-world application domains, including recommendation systems [Sandvig et al., 2007], medical diagnosis [Ordonez et al., 2006], health insurance [Viveros et al., 1996], and more recently for supervised learning [Rijnbeek and Kors, 2010; Aglin et al., 2020; Ali et al., 1997]. Several proposals for discovering different kinds of association rule based on itemset mining have been introduced (readers are referred to [Fournier-Viger et al., 2017] for a comprehensive survey). However, most of existing works mainly focused on rules with a conjunction among items for the antecedent and the consequent. Such detected rules can be seen as Horn rules [Balc´azar and Garriga, 2007], a particular fragment of propositional logic formulas.

Recently, some researchers get attention for mining generalized association rules, among them disjunctive association rules extending the expressive power of classical association rules. Indeed, when association rules of the form a ∧ b → c and a ∧ b → d cannot be found from a given database, it does not mean that a ∧ b → c ∨ d will not be an association rule from that database, which shall be a very useful information in some cases. For instance, the rules expressing that when customers buy bread they also buy butter or milk or customers who buy either Sneakers or shoes also buy socks, would be relevant for the sales managers as usually some products cannot be marketed at the same time. Computing such rules can also help sales managers understand customer behavior and what she needs, as well as provide appropriate product combinations, and to make decisions to promote products.

In previous work, the authors of [Nanavati et al., 2001] defined generalized disjunctive association rules by integrating in the consequent different logical operators except the negation. In [Sampaio et al., 2008], the authors presented an algorithm to enumerate disjunctive association rules where the itemsets for the antecedent and the consequent can be a conjunction or a disjunction of items. The main issue of this approach is the high computational complexity since it is based on Apriori-like algorithm [Agrawal and Srikant, 1994] to generate frequent itemsets of the disjunctive association rules. Furthermore, Hamrouni et al. [Hamrouni et al., 2010b] introduced a novel approach, called GARM, to mine disjunctive closed patterns. Such structures are then used to derive generalized association rules employing conjunction, disjunction and negation connectives between items. Later, the authors in [Alharbi et al., 2014] presented an algorithm to deal with disjunctive association rules on uncertain databases using two minimum support thresholds. The first one is used to generate pairs of itemsets that respect an expected minimum support, while inducing the disjunctive itemsets that reach the second minimum support threshold to produce k-disjunctive rules of the form x → Y where x is an item and Y is a disjunction of k - 1 items. Finally, the authors in [Hilali et al., 2013; Hilali-Jaghdam et al., 2011] proposed an approach to discover association rules of the form X → Y such that X and Y are frequent itemsets, disjoint and involving infrequent items. The aforementioned rules are not sufficiently expressive to capture interesting disjunctive relationships among items, since they restrict the candidate pattern to be fully contained in the transactions of the database, However, in many real data with missing items in the transactions, such requirement cannot be fulfilled. Moreover, discovering the aforementioned kind of generalized association rules is clearly more complex than that of classical association rules.

Recently, observing that most data mining tasks often involve constraints, declarative approaches that connect data mining with symbolic Artificial Intelligence (AI) models, including Constraints Programming (CP), Propositional Satisfiability (SAT) and Answer Set Programming (ASP), have emerged. In these frameworks, the problem is formulated as a logical formula or a constraint network, whose solutions represent the output of the mining task. In this context, a number of symbolic AI approaches have been designed to address a variety of mining problems, including among others sequences mining [Jabbour et al., 2013; N´egrevergne and Guns, 2015; Gebser et al., 2016], frequent itemsets mining [Lazaar et al., 2016; Schaus et al., 2017; Dlala et al., 2018; Jabbour et al., 2018a; Belaid et al., 2019b; Hidouri et al., 2021; Hidouri et al., 2022], classical [Belaid et al., 2019a] and minimal non-redundant [Belaid et al., 2019a; Izza et al., 2020] association rules mining, and more recently overlapping communities detection [Jabbour et al., 2016; Jabbour et al., 2017; Jabbour et al., 2018b; Jabbour et al., 2020; Jabbour et al., 2022]. The application of symbolic AI to data mining is supported by its theoretical and algorithmic foundations and the flexibility it affords, i.e., the ability to incorporate new user-specified constraints without the need to modify the underlying algorithms.

In this paper, we propose a symbolic AI framework particularly suitable for modelling and mining a new kind of disjunctive patterns from transaction databases. More precisely, we make the following major contributions:

• We present k-disjunctive support based itemsets, a generalized form of traditional itemsets by allowing the absence of up to k items in each transaction matching the itemset. Such definition is extended to disjunctive association rules, named (k, k′ )-disjunctive support based association rules X → Y , where X (resp. Y ) is a kdisjunctive (resp. k′ -disjunctive) support based itemset. To find these relevant patterns, we also introduce their associated measures (i.e., support and confidence) to quantify their interestingness. Interestingly, the output and the structure of the patterns can be managed though an incremental setting of the parameters.
• We define a polynomial-time reduction from mining k-disjunctive support based itemsets and (k, k′ )- disjunctive support association rules to the propositional satisfiability model enumeration problem. The main strength of our symbolic AI framework lies its ability to separate the modeling phase from the solving stage.
• We conduct extensive experiments on different popular real-world datasets to evaluate the efficiency of our approach to discover (k, k′ )-disjunctive support based association rules in sequential and parallel setting.

2 Technical Background

2.1 Propositional Logic and Satisfiability Problem

We assume a propositional language L built up inductively from a countable set PS of propositional letters, the Boolean constants ⊤ (true or 1) and ⊥ (false or 0), and the standard logical connectives {¬, ∧, ∨,→,↔} in the usual way. We use the letters x, y, z, etc. to range over the elements of PS. Propositional formulas of L are denoted by Φ,Ψ, Γ, etc. A literal is a propositional variable (x) of PS or its negation (¬x). A clause is a (finite) disjunction of literals, while a term is a (finite) conjunction of literals. A clause containing only one literal is called a unit clause. For any formula Φ from L, P(Φ) denotes the symbols of PS occurring in Φ. A conjunctive normal form (CNF) formula is a (finite) conjunction of clauses. Also, a formula in disjunctive normal form (DNF) is a (finite) disjunction of terms.

A Boolean interpretation I of a propositional formula Φ is a mapping from P(Φ) to {0, 1}. If I(Φ) = 1, then I is called a model of Φ, and we write I |= Φ. Let M(Φ) denote the set of all models of Φ. We write |=UP to denote the logical consequence restricted to unit propagation 1 .

The propositional satisfiability problem (SAT) is the problem of determining whether a CNF formula admits a model or not. At present, this widely studied NP-Complete problem has been successfully applied in various practical settings, including data mining [Raedt et al., 2008; Guns et al., 2017], overlapping community detection [Jabbour et al., 2018b; Jabbour et al., 2020], and more recently queries answering over databases [Dixit, 2019; Bienvenu and Bourgaux, 2022].

2.2 Association Rules Mining

Let Ω denotes a universe of items (or symbols). The letters a, b, c, etc. will be used to range over the elements of the universe Ω. A classical itemset X over Ω is defined as a subset of Ω, i.e., X ⊆ Ω. X can be seen as a conjunction of items. We denote by 2Ω the set of all itemsets over Ω and we use the capital letters X, Y,Z, etc. to range over the elements of 2Ω. A transaction database D is a finite set of pairs denoted by {(1, T1), . . . , (m, Tm)} s.t. Ti ∈ 2Ω \ {∅} for 1 ≤ i ≤ m. Given an itemset X and a transaction database D, the cover of X in D is defined as C(X, D) = {(i, Ti) ∈ D and X ⊆ Ti}. The support of X in D is then defined as Supp(X,D) = |C(X,D)|. A generalized disjunctive itemset, in short GDI, is a disjunctive collection of itemsets, which will be denoted by [X1, . . . ,Xp]. Note that this square bracket notation is used to distinguish it from a classical itemset [Nanavati et al., 2001]. Obviously, a GDI [X] = [X1, . . . ,Xp] can be seen as a DNF formula ∨1≤i≤p (∧a∈Xi a). The support of a GDI in the transaction database D is defined by the following equation:

Given a transaction database D, an association rule (in short AR) is an implication of the form X → Y where X

1 Unit propagation is a kind of inference based on resolution with unit clauses, i.e., Φ∧x∧(¬x∨y1 ∨. . .∨yn) |=UP (y1 ∨. . .∨yn).

and Y are two disjoint itemsets called the antecedent and the consequent of the rule, respectively [Rakesh et al., 1993]. The interestingness of an AR is computed through two statistical measures, called the support and the confidence. The support of X → Y in the database D, written as:

determines the occurrence frequency of the rule in D, and the confidence of X → Y in D is then defined as:

Technically, the confidence is the conditional probability of the occurrence of the consequent of the association rule given its antecedent. Hereafter, a generalized disjunctive association rule (GDAR, for short) is an AR of the form [X1, . . . ,Xp] → [Y1, . . . , Yq]. When there is no ambiguity, a GDAR [X1, . . . ,Xp] → [Y1, . . . , Yq] will be simply denoted by [X] → [Y ]. GDARs extend the expressive power of ARs by capturing disjunctive relationships among items [Nanavati et al., 2001]. The support and confidence constraints of a GDAR are expressed as follows:

3 Formal Approach

Although traditional itemsets are useful patterns, they are not sufficiently expressive to catch disjunctive relationships among items. To discover more valuable information from transaction databases, GDIs extend traditional itemsets by allowing the disjunction among conjunctive items [Nanavati et al., 2001]. Clearly, these two previous models share the same requirement: they restrict the candidate pattern to be fully contained in the transactions of the database. Due to such over-restriction, useful knowledge may not always be detected from data, since some relevant patterns can partially match the transactions of the database. To alleviate such limitation, we revisit the basic model of patterns to extend its expressive power and thus enhance the relevance of knowledge that can be recovered from transaction databases. For this purpose, let us define the notions of k-disjunctive cover and k-disjunctive support.

Definition 1. Let D be a transaction database and k a positive integer. The k-disjunctive cover of an itemset X is C k (X,D) = {(i, T) ∈ D | T ∩X ̸= ∅ and |X \ T| ≤ k}. Then, the k-disjunctive support of X is defined as usual as: Suppk (X, D) = |C k (X, D)|.

Technically speaking, unlike the cover in the traditional model of itemsets that constrains an itemset to be entirely contained in the transaction, the k-disjunctive cover relaxes such constraint so that a transaction can miss up to k of the items in the itemset X (but should at least contain one of the items). The k-disjunctive support of X determines thereby the number of matched transactions in the database according to the k-disjunctive cover. Obviously, if k = 0, then Supp0 (X,D) = Supp(X,D). Interestingly, for a given itemset X one can deduce a GDI parameterized by k, in short k-GDI, as [X1,X2, . . . ,Xp] where Xi = [X ∩ Ti | (i, Ti) ∈ C k (X, D)].

Proposition 1. Let D be a transaction database, and k, l two positive integers. Deciding whether there exists an itemset X s.t. |X| ≥ l and Suppk (X,D) = |D| is NP-complete.

Based on the k-disjunctive support, we can determine how interesting an itemset is, as we show next.

Definition 2. Let D be a transaction database and α > 0 a support threshold. Then, an itemset X is called a kdisjunctive support based frequent itemset (k-DSFI, for short) if and only if Suppk (X, D) ≥ α.

Intuitively, Definition 2 states that an itemset is frequent w.r.t. the k-disjunctive support if it meets a minimum support threshold. We say also that an itemset X is closed w.r.t. the k-disjunctive support if and only if for all X ⊂ Y , Suppk (Y, D) < Suppk (X, D).

Proposition 2 shows that finding a k-disjunctive support based frequent itemset of size at least l is NP-complete.

Proposition 2. Let D be a transaction database, k, l two positive integers, and α > 0 a minimum support threshold. Deciding whether there exists a k-DSFI X in D s.t. |X| ≥ l is NP-complete.

Now, we are able to extend the generalized form of itemset cover introduced previously to the association rule setting.

Definition 3. Let D be a transaction database, and k, k′ two positive integers. We define the (k, k′ )-disjunctive support and (k, k′ )-disjunctive confidence of an AR X → Y as:

Similarly to itemsets, for a given association rule X → Y one can deduce a GDAR w.r.t. the parameters k and k′ , written as follows:

Next, an association rule X → Y is closed w.r.t. the (k, k′ )-disjunctive support constraint iff there is no association rule X′ → Y ′ such that the following conditions hold:

It is important to note the following result.

Property 1. Let D be a transaction database, X → Y an AR, and [X′ ] → [Y ′ ] the GDAR associated to X → Y . Then, Suppk,k′ (X → Y,D) = Supp([X′ ] → [Y ′ ],D) and Confk,k′ (X → Y, D) = Conf([X′ ] → [Y ′ ], D).

Definition 4. Let D be a transaction database, α > 0 a minimum support threshold, and β > 0 a minimum confidence threshold. Then, an AR X → Y is a (k, k′ )-disjunctive support based valid AR ((k, k′ )-DSVAR, for short) if and only if Suppk,k′ (X → Y, D) ≥ α and Confk,k′ (X → Y, D) ≥ β.

A (k, k′ )-DSVAR requires two input parameters k and k′ to control the number of missing items in transactions. Notably, by varying these two parameters, one can increase or decrease the number of items forming the antecedent or the consequent of a (k, k′ )-DSVAR. Obviously, if k and k′ are both set to 0, then a (k, k′ )-DSVAR simply corresponds to a classical association rule.

Once again, we stress that our more fine-grained approach is general enough to encompass traditional models of pattern as a particular instance, by properly setting the parameters k and k′ . The next corollary follows from Proposition 2.

Corollary 1. Let D be a transaction database, k, k′ , l, l′ positive integers, and α > 0 (resp. β > 0) a minimum support (resp. confidence) threshold. Deciding whether there exists a (k, k′ )-DSVAR X → Y in D s.t. |X| ≥ l and |Y | ≥ l′ is NP-complete.

Example 1. Consider the transaction database D depicted in Table 1. For α = 4 and k = 1, X1 = {a, b, c, d}, X2 = {a, c, e}, and X3 = {f, g, h, i} are 1-DSFIs. The GDIs representations of X1, X2, and X3 are respectively:

Also, we have the following (1, 1)-DSVARs: r1 = {d, e} → {a, b, c} and r2 = {f, h} → {g, i}. The corresponding

[{a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}], [{a, c}, {a, c, e}, {a, e}], and [{g, h, i}, {f, g, h, i}, {f, g, i}, {f, g, h}]. GDARs of r1 and r2 are respectively:

Problem Definition. Given a transaction database D, and two positive integers k and k′ , in the forthcoming subsections our main objective is to mine the set of all (closed) k-DSFIs and (closed) (k, k′ )-DSVARs that meet the minimum support and confidence constraints. We shall refer to these two problems as CDSFIMk, and CDSVARMk,k′ , respectively.

3.1 Symbolic Encoding of the CDSFIMk Problem

Given a transaction database D, a minimum support threshold α (expressed in percentage), and a positive integer k, our focus is to find the set of all closed k-DSFIs supported by at least α transactions in D. In this subsection, we describe a new symbolic encoding for the CDSFIMk problem. Our key idea is to encode the task of CDSFIMk into a CNF propositional formula whose models correspond exactly to the set of closed k-DSFIs in D. That is, the CDSFIMk problemwill be reduced to the problem of computing all models of an underlying CNF formula. Notice that the distinction between the modeling and the solving step offers a straightforward way to evolve the specification of the problem, by simply adding new constraints to the symbolic encoding. Besides, the solving step can be constantly optimized through further improvements performed by the symbolic AI community. In fact, recent breakthrough in the efficiency of propositional satisfiability solving technology opens an avenue for encoding various realistic applications to SAT. However, keep in mind that the problem encoding might have a great impact on the efficiency of the solving phase. The challenge is thus to provide the most appropriate encoding combining efficiency and succinctness, while ensuring correctness and completeness. This requires clearly a judicious choice of propositional variables and logical constraints as well as their reformulation in CNF.

Next, we present our symbolic encoding for CDSFIMk as follows. First, to establish a one-to-one mapping between the models of the symbolic encoding and the set of (closed) kDSFIs, each item a ∈ Ω (resp. each transaction (i, Ti) ∈ D) is associated with a propositional variable xa (resp. qi). Second, we introduce the constraints allowing us to obtain the propositional formula for the CDSFIMk problem.

Cover constraint. The first constraint is the cover constraint expressed as follows:

Constraint (1) ensures that a transaction Ti supports the kDSFI X when up to k items of X are not in Ti. This constraint is a conjunction of the so-called conditional car-

eralizes the well-known cardinality constraints that naturally arise in different propositional encoding of real-world problems. Several encodings have been designed to translate (conditional) cardinality constraints into CNF (e.g. [Sinz, 2005; E´en and S¨orensson, 2006; Bailleux et al., 2006; Boudane et al., 2018]).

Frequency constraint. Now, to constrain the candidate itemset to be a k-DSFI, i.e., to cover at least m × α transactions, we add the following cardinality constraint:

Closure constraint. Moreover, we introduce the closure constraint allowing us to complete our symbolic encoding of the CDSFIMk problem. This constraint provides the condition under which a k-DSFI is closed.

Intuitively, Constraint (3) simply asserts that an item a cannot be included in the candidate k-DSFI if its addition violates the cover constraint in at least one transaction. We illustrate the closure constraint with the following example.

Example 2. In Table 1 and for k = 2, the closure constraint over the item e is as follows:

Recall that the k-DSFI relaxes the core property of classical itemsets that requires the full matching of the itemset with a transaction to be in its cover. Then, to find more useful kDSFIs one can require that each item appears at least γ times in the itemset. Such constraint can be simply expressed as:

Proposition 3. The propositional formula Φα,γ CDSFIMk = (1) ∧ (2)∧(3)∧(4) encodes the problem of mining closed k-DSFIs in D where each item appears γ times.

Interestingly, Proposition 3 shows that there exists a oneto-one mapping between the models of the propositional formula Φα,γ CDSFIMk and the closed k-DSFIs induced from D where each item appears γ times.

3.2 Symbolic Encoding of the CDSVARMk,k′ Problem

This subsection presents a polynomial-time reduction from mining closed (k, k′ )-DSVARs to the problem of enumerating the models of a CNF formula. First, we use two disjoint sets of propositional variables, namely xa and ya, ∀a ∈ Ω, to model the antecedent X and the consequent Y of the (k, k′ )- DSVAR X → Y . Similarly, the sets {p1, . . . , pm} and {q1, . . . , qm} are introduced to capture the disjunctive support of X and X → Y , respectively.

Our approach relies also on numerous logical constraints, depicted in Figure 1, to model the problem of computing (k, k′ )- DSVARs. Specifically, the first Constraint (5) excludes the same item to belong to both X and Y . Constraints (6) and (7) simply encode the supports of X and Y . In addition, formulas (8) and (9) express the support and the confidence of the (k, k′ )-DSVAR. Constraint (10) enforces that each item appears in at least γ transactions. Last, the closure constraint can be expressed through Constraint (11).

Proposition 4. Let D be a transaction database, α (resp. β) a minimum support (resp. confidence) threshold, and k, k′ two positive integers. The formula Φα,β,γ CDSVARMk,k′ = (5)∧(6)∧ (7)∧(8)∧(9)∧(10)∧(11) encodes the computation of closed (k, k′ )-DSVARs in D s.t. each item appears at least γ times.

The propositional formula Φα,β,γ CDSVARMk,k′ involves (conditional) cardinality constraints (see Figure 1). As mentioned above, these constraints can be translated into CNF. The previous symbolic encoding is polynomial, making our approach of closed (k, k′ )-DSVAR mining problem polynomial in the size of the transaction database D. Fortunately, although the encoding of the conditional cardinality constraints (e.g., Constraints 7, 10, 11), the number of variables and clauses of our encoding is polynomial w.r.t. the number of items (n) and the number of transactions (m) in the database.

Next, we will consider the computation of a special kind of (k, k′ )-DSVAR when k = 0. Specifically, the aim is to find the set of (closed) (k, k′ )-DSVARs that give rise to GDARs of the form X → [Y1, . . . , Yp]. This kind of rules is always considered in the literature (e.g. [Hamrouni et al., 2010a; Alharbi et al., 2014]), and it allows to discover more interesting relations between variables in transaction databases. In what follows, when there is no ambiguity, a (0, k′ )-DSVAR will be simply denoted by k′ -DSVAR.

4 Experimental Evaluation

We now present the experiments carried out to assess the efficiency of the approach described in the paper. For this, we study the running time for computing the set of closed k′ - DSVARs in sequential and parallel setting. Our approach is implemented in the C++ language top-on the well-known satisfiability solver MiniSAT [E´en and S¨orensson, 2002], which is adapted as a non-blocking clause model enumeration procedure. The pigeon-hole encoding [Jabbour et al., 2014; Boudane et al., 2018] is applied to translate the different (cardinality) constraints into CNF. We also employ the application programming interface OpenMP that supports multiplatform shared memory multiprocessing programming in C and C++ languages. To increase efficiency, we adopt a decomposition technique similar to the the one defined in [Izza et al., 2020]. The encoding is partitioned by considering different sub-problems Φ1, . . . , Φn, where Φi = Φα,β,γ CDSVARMk,k′ ∧ xai ∧ ∧j<i ¬xaj where Ω = {a1, . . . , an}.

4.1 Experimental Setup

Our experiments were performed on a Linux machine with Intel Xeon quad-core processors and 32GB of RAM running at 2.66 GHz. For all runs, time-out and memory-out were set to 2 hours and 10 GB, respectively. We use a set of datasets coming from the FIMI 2 repository. We also fix the minimum confidence threshold β to 95%3 while the value of γ is identical to α. Note that numerous minimum support values are tested w.r.t. the size of datasets. We did not perform any comparative evaluation since the baselines [Hamrouni et al., 2010a; Alharbi et al., 2014] are limited to specific rules involving only a disjunction of items in the consequent of rules.

For the empirical evaluation, we perform two types of experiments. In the first experimental study, we perform a sequential comparison to compute the set of all closed k′ - DSVARs. In the second experimental evaluation, we carry out a parallel evaluation to find all closed k′ -DSVARs while changing the number of cores used for the computation.

4.2 Sequential Evaluation

Table 2 contains closed k′ -DSVARs mining results. It reports the number of closed k′ -DSVARs (#k′ -CDSVARs) and the total CPU time (in seconds) for each dataset with different values of k′ (between 0 and 4), and by varying α. We also use the symbol "-" to mention that the approach is not able to scale on the set of all closed k′ -DSVARs under the time

2 http://fimi.ua.ac.be/data/

3 Similar results were observed when β is set to 85% and 90%.

Table 2: Experimental results for mining closed k′ -DSVARs (0 ≤ k′ ≤ 4) for representative sample of datasets

limit. As one can observe from Table 2, the time needed to compute the set of closed k′ -DSVARs increases continuously with the parameter k′ . This can be explained by the fact that relaxing the cover constraint increases the number of closed k′ -DSVARs. Such relaxation can also lead to more conflicts when finding all models of the underlying CNF formula. Another observation that can be made is that for k′ > 0 more variables are needed to encode Constraints (5), (6), etc. For instance, for chess data and α = 75%, the number of classical association rules (i.e., k′ = 0) is equal to 287183, while this number is close to 85 millions for 4-CDSVARs (k′ = 4). For the chess solving time, it passes from 8.43 seconds for k′ = 0 to about 5000 seconds for k′ = 4. Similar behavior is observed across all datasets with different α values.

4.3 Parallel Solving

In the second part of our empirical evaluation, we extended our approach for computing closed k′ -DSVARs in parallel. In fact, as shown in [Izza et al., 2020], the decomposition technique generates independent sub-problems that can be handled on a multi-core shared memory machine. We perform similar experiments by using 1, 2 and 4 cores and varying k′ from 1 to 10 to see how the performance of our approach varies. We also consider different threshold values in our parallel implementation. Figure 2 shows the empirical results for a representative sample of datasets. As expected, the parallelbased approach allows to reduce significantly the running time needed to discover all closed k′ -DSVARs. For instance, with a single core, the running time exceeds 1000 seconds to mine the closed 6-DSVARs in the mushroom dataset with α = 35%. When the number of cores is more than one, this task is achieved while reducing the running time (800 seconds and 540 seconds for 2 and 4 cores, respectively). Moreover, the time needed to extract all closed k′ -DSVARs for the large dataset T40I10D100K, with α = 6%, is reduced from 31.50 seconds with a single core to less than 9 seconds with 4 cores. This observation remains valid for the different values of k′ . In addition, it is worth noticing from Figure 2 that the percentage of gain is more remarkable by varying the number of cores from 1 to 2 rather than from 2 to 4. The unique exception is the dataset T40I10D100K with α = 5%. This is due to the fact that the decomposition is applied before the solving process and no dynamic method is employed to control the load balancing. Consequently, the time needed by the cores to handle their assigned sub-tasks is generally different.

5 Conclusions and FutureWork

In this paper, we have presented disjunctive support based patterns, a generalization of traditional patterns by allowing the absence of up to k items in each transaction supporting the pattern. We also designed a new symbolic encoding for closed k-DSFIs and (k, k′ )-DSVARs mining problems using propositional logic. We proved that our polynomial encoding allows to control the rules by varying the two parameters k and k′ . An extensive campaign of experiments carried out over different real-world datasets has shown the efficiency of our approach to compute (k, k′ )-DSVARs.

Different research directions can improve the present work. First, our framework can be extended for mining minimal non-redundant (k, k′ )-DSVARs. Furthermore, as shown in the paper, relaxing the cover constraint leads to more difficult problems. Our goal is then to improve the efficiency of our approach by considering some pre-processing techniques.

Acknowledgments

This work was funded, in part, by the Agence Nationale de la Recherche ANR under grant EXPIDA: ANR-22-CE23-0017.