On the Enumeration of Association Rules: A Decomposition-based Approach

1 Introduction

In the recent years, there is an increasing need to discover relations among large transactional databases, which may be tackled by association rules mining. The outputs generated from the association rule mining are some rules, which pass the user-specified minimum support and confidence measures. Each association rule consists of a couple of itemsets representing the antecedent and consequent of the rule. As the set of association rules (ARs, for short) in large databases can rapidly grow to be unwieldy, many other kinds of ARs have been studied essentially to reduce the redundancy inherent in a collection of rules. The most common ones are minimal non-redundant association rules (MNRs, for short).

Mining ARs is beneficial to the correct and appropriate decision made by decision makers. Since the first well known application usually referred to as market basket data analysis [Agrawal and Srikant, 1994], today, research work on ARs is motivated by a range of application areas, such as banking, manufacturing, medical diagnosis, and telecommunications.

Over the last decade, there have been a lot of proposals of ARs mining (see [Ceglar and Roddick, 2006] for a survey). These work can be generally partitioned into two main categories: specialized and declarative approaches. Specialized algorithms, such as Apriori [Agrawal and Srikant, 1994] and FP-Growth [Han et al., 2004], are generally a two-step process: (1) finding all frequent itemsets with adequate supports, and (2) generating ARs with high confidence by combining these frequent or large itemsets. Nevertheless, the main bottleneck of this line of research is that additional user-specified constraints, i.e., rules with an antecedent and/or consequent of a given size or rules with or without some specific items, often require new implementations to filter out the ARs violating or satisfying the user's constraints, which can be computationally infeasible for large databases.

Since there are usually various constraints over patterns to mine (i.e., support, confidence, etc.), new research have began connecting data mining to symbolic Artificial Intelligence (AI). Such fertilization leads to a number of algorithms that have been proposed within Constraints Programming (CP), Satisfiability (SAT), and Answer Set Programming (ASP) for mining sequences [Jabbour et al., 2013; N´egrevergne and Guns, 2015; Gebser et al., 2016], frequent itemsets [Henriques et al., 2012; Lazaar et al., 2016; Schaus et al., 2017], association rules [Boudane et al., 2016; Belaid et al., 2019], clustering [Dao et al., 2017; Boudane et al., 2017a], and overlapping communities in networks [Jabbour et al., 2017; Ganji et al., 2017; Jabbour et al., 2020], etc. The main advantage of symbolic AI approaches for pattern mining is their declarativity and flexibility, which include the ability to incorporate new user-specified constraints without the need to modify the underlying system. To the best of our knowledge, earlier work that deal with ARs mining are that of [Boudane et al., 2016] and [Belaid et al., 2019]. In the first one, the authors developed a SAT-based approach to discover closed and indirect ARs. More specifically, they used propositional satisfiability with different linear inequalities to ensure the minimum frequency and the confidence of rules. Encoding ARs mining into SAT enables to take advantage of the recent and impressive progress achieved in SAT solving. Unfortunately, the counterpart of this method is the big encoding making such approach far from to be scaling. The proposed approach of [Belaid et al., 2019] presents a CP model to mine ARs and MNRs from transactional databases. The authors extended the global constraint coversize [Schaus et al., 2017] by adding a new one called confidence to ensure the confidence of the rules. However, these two constraints cannot been expressed within existing global constraints. Hence, such extension generally borrowed techniques from specialized algorithms (to define propagators over the coversize and confidence constraints) which is far from the hoped-for declarativity.

In this paper, in order to break through these barriers and to scale the symbolic AI based approaches to larger databases, a declarative method for mining ARs and MNRs is first proposed using a SAT representation. At the core of our approach is a novel decomposition method that allows to split the original database into subsets that can be mined independently. Hopefully, without causing too large formulas and the associated memory problems, the advantage of our SAT encoding scheme is to allow independent evaluation on a multicore machine, improving performance. We stress the fact that the introduced partitioning scheme in this paper is independent of any particular solver and widely applicable. Finally, a last contribution of this work consists of an empirical evaluation of the decomposition-based method, showing significant computational benefits. Specifically, our approach outperforms the CP-based algorithm CP4AR while significantly reducing the performance gap with the specialized system ECLAT-Z.

2 Formal Preliminaries

2.1 Propositional Logic and SAT problem

We consider a propositional language L defined from a finite set of propositional variables V ar = {p, q, r, . . .}, the logical constants ⊥, ⊤, and the usual logical connectives (namely, ¬, ∧, ∨, →, and ↔). Propositional formulas will be denoted by Greek letters Σ, ∆, etc. V ar(Σ) denotes the set of propositional variables appearing in the formula Σ. It is common for logical reasoning algorithms to operate on normal form representations instead of arbitrary sentences. A formula in conjunctive normal form (CNF) is a conjunction (∧) of clauses, where a clause is a disjunction (∨) of literals. A literal is a propositional variable (p) or its negation (¬p). In addition, a Boolean interpretation (or world) µ of a formula Σ ∈ L is a total function from V ar(Σ) to {0, 1} (0 corresponds to false and 1 to true). We denote by Σ|x the formula Σ where x assigned true, i.e., Σ ∧ x. µ is a model of Σ iff it makes it true in the usual truth functional way. Then, Σ is satisfiable if there exists a model of Σ. models(Σ) denotes the set of models of a formula Σ. Lastly, SAT is the NP-complete problem that consists in deciding whether a given CNF formula is satisfiable or not.

2.2 AGlimpse at ARs Mining

Let Ω denote a universe of items (or symbols), called alphabet. We use the letters a, b, c, etc. to range over the elements of Ω. An itemset I over Ω is defined as a subset of Ω, i.e., I ⊆ Ω. We denote by 2Ω the set of all itemsets over Ω and we use the capital letters I, J,K, etc. to range over the elements of 2Ω. Typically, a transaction is an ordered pair (i, I) where 1 ≤ i ≤ m, called the transaction identifier, and I an itemset, i.e., (i, I) ∈ N × 2Ω. A transaction database D is defined as a finite non empty set of transactions (D ⊆ N × 2Ω) where each transaction identifier refers to a unique itemset. Given a transaction database D and an itemset I, the cover of I in D, denoted C(I,D), is defined as follows: {i ∈ N | (i, J) ∈ D and I ⊆ J}. The support of I in the database D, denoted as Supp(I,D), is defined as the cardinality of C(I,D), i.e., Supp(I,D) = |C(I,D)|. An itemset I ⊆ Ω such that Supp(I, D) ≥ 1 is closed iff, for all itemsets J with I ⊂ J, Supp(J, D) < Supp(I, D).

An association rule is a pattern of the form X → Y where X and Y are two disjoint itemsets. X and Y are called the antecedent and the consequent of the rule, respectively. In addition, the interestingness of ARs is defined through the notions of support and confidence. The support of an AR X → Y in a transaction database D, defined as Supp(X → Y, D) = Supp(X∪Y,D) |D| , determines how often a rule is applicable to a given dataset, i.e., the occurrence frequency of the rule. The confidence of X → Y in D, defined as Conf(X → Y,D) = Supp(X∪Y,D) Supp(X,D) , provides an estimate of the conditional probability of Y given X. Then, a valid AR is an AR with support and confidence greater than or equal to the minimum support α and minimum confidence β thresholds, respectively. More specifically, given a transaction database D, a minimum user-specified support α and confidence β thresholds, the problem of mining association rules consists in computing the following set: {X → Y | X, Y ⊆ Ω ∧ Supp(X → Y, D) ≥ α ∧ Conf(X → Y, D) ≥ β}.

It is well-recognized that the main factor that hinders the applications of ARs is the huge number of ARs returned by the mining process. Typically, for reasonable thresholds α and β, the number of ARs can reach impractical amounts, such that analyzing the rules themselves becomes a challenging task. Moreover, many of these rules have no value to the user since they can be considered redundant. In this work, we are also interested in the well-known minimal non-redundant association rules variant, namely MNRs [Kryszkiewicz, 1998; Bastide et al., 2000].

Definition 1. Let D be a transaction database. Then, an AR X → Y is a MNR iff there is no AR X′ → Y ′ in D different from X → Y s.t. (i) Supp(X → Y,D) = Supp(X′ → Y ′ ,D), (ii) Conf(X → Y,D) = Conf(X′ → Y ′ ,D), and (iii) X′ ⊆ X and Y ⊆ Y ′ .

3 SAT Encoding Scheme for ARs Mining

Here, we review the SAT encoding scheme for the problem of mining ARs proposed in [Boudane et al., 2016]. Basically, to encode the ARs mining problem into SAT one must define a set of variables and a set of constraints on the variables. Then, the idea was to build a one-to-one mapping between the set of ARs and the models of the corresponding CNF formula. More precisely, different variables are used to represent the covers of the two parts of the rule X → Y , namely, X and X ∪ Y . These variables are used in 0/1 linear inequalities to ensure the support and the confidence of the rules.

Given a transaction database D = {(1, I1), . . . , (m, Im)}, a minimum support α and confidence β thresholds. To represent the itemsets X and Y of each candidate rule X → Y , two propositional variables xa and ya are associated to each item a in order to guarantee if a belongs to X (i.e., xa = true) or Y (i.e., ya = true). For the covers of X and X ∪Y , new variables pi and qi are also introduced to each transaction identifier i ∈ {1 . . .m}. In addition, the following constraints (see Figure 1) are introduced on the variables to build a oneto-one mapping between the models of the obtained CNF formula, denoted as ΣAR D,α,β , and the ARs. More precisely, Constraint (1) ensures the non-overlapping between X and Y . The formulas (2) and (3) capture the cover of X and X ∪ Y , respectively. Moreover, the inequality constraints (4) and (5) express the support and the confidence constraints w.r.t. the user-specified thresholds α and β. Then, the ARs mining problem from D corresponds to the enumeration of the models of the CNF formula: ΣAR D,α,β = (1)∧(2)∧(3)∧(4)∧(5). Under a Boolean interpretation µ, the candidate rule is X = {a ∈ Ω | µ(xa) = 1} → Y = {b ∈ Ω | µ(yb) = 1} where C(X,D) = {i ∈ N | µ(pi) = 1} and C(X ∪ Y,D) = {i ∈ N | µ(qi) = 1}. Now, Constraint (6) ensures the closure of the itemset X∪Y , i.e., if C(X∪Y,D) = C(X∪Y ∪{a},D), then the item a has to belong to X ∪ Y (a is either in X or Y ). We note here that Constraint (6) allows to add n clauses to the SAT encoding where n is the number of items.

To simplify the notation, in the sequel we use Σ instead of ΣAR D,α,β whenever it is clear from the context.

4 Our Approach

Encoding problems in CNF format and solving them with SAT solvers is indeed a competitive approach. SAT has the advantage of being very easy in its formulation. Nonetheless, the simplicity of the CNF format makes its use very restrictive. For instance, a constraint problem with a few dozen of variables may result in a SAT problem with thousands of variables and millions of clauses. Also, one may argue that a cause of inefficiency is the huge number of models of the CNF formula. Clearly, this is also the bottleneck for the SAT encoding scheme [Boudane et al., 2016] for ARs mining problem. Indeed, in this encoding, the number of clauses is, in the worst case, |D| × |Ω|.

In order to prune the search space, one can add more constraints to the previous model. For instance, Constraint (7) allows us to propagate the literal ya when the number of transactions supporting such literal is less than α. Similarly, Constraint (8) allows us to propagate the literal qi when the associated transaction has all items assigned false.

Unfortunately, these two cardinality constraints can outgrow the available memory and can consequently make SAT solving inefficient. To break through this barrier, in the sequel we propose to use a decomposition method that allows to split the search space into numerous but smaller sub-problems and easier to solve. Such decomposition based method allows us to avoid encoding the whole transaction database. Our main idea is as follows. First, given a CNF formula Σ and a variable xa ∈ V ar(Σ), the models of Σ can be partitioned into those of Σ∧xa and Σ∧¬xa. By generalizing such principle, one can split a CNF formula into subformulas such that each subformula can be evaluated in an independent way.

Definition 2. Let Σ ∈ L be a CNF formula. P = {Σ ∧ Γ1, . . . , Σ ∧ Γn} is a partition of Σ if Γ = {Γ1, . . . , Γn} is a set of formulas defined over V ar(Σ) such that ∨ni=1 Γi ≡ ⊤, and Γi ∧ Γj |= ⊥, for all 1 ≤ i ̸= j ≤ n. Γ = {Γ1, . . . , Γn} is called the Σ-partition.

That is, by Definition 2, the set of models of Σ is equal to ⊎ models(Σ ∧ Γi) (1 ≤ i ≤ n). The above definition is a general definition that allows for a range of possible splitting techniques to be defined. In what follows, we consider an instantiation that consists in splitting Σ into its literal conjuncts w.r.t. a given ordering on the variables of Σ.

4.1 ADecomposition-based Encoding for ARs

Here, we present our decomposition method to extract ARs. Given an AR X → Y , we select the variables encoding the antecedent X = {a1, . . . , an} to define the partition P. Let 〈xa1 , . . . , xan 〉 be an ordering on the set of variables encoding X. Then, the Σ-partition Γ = {Γ1, . . . , Γn} over {xa1 , . . . , xan } is defined as: Γi = xai ∧ ∧1≤k<i ¬xak (1 ≤ i ≤ n). Now, the main idea is to split recursively the formula Σ w.r.t. its positive and negative literals. Then, the formula Σ ∧ Γi ≡ Σ|...¬xai-1 ,xai enforces xai to be true, that is the item ai belongs to X. Consequently, the encoding can be restricted to transactions containing the item ai. Also, the literal xak for all 1 ≤ k < i assigned false allows to exclude the item ak to be in X. Clearly, this allows to avoid encoding the entire database and without causing too large formulas and the associated memory problems.

Clearly, the splitting of Σ leads to many independent subformulas encoding subsets of a specific list of transactions of the original database. However, some of such sub-problems might remain large, hence there is again a firm barrier to the scalability of the approach to larger databases. To illustrate, let us suppose that an item ai appears in each transaction of the database D. Then, the encoding of the cover of X ∪ Y requires considering all the transactions but excluding ai.

To limit such blow up in terms of encoding size, we therefore opt to develop a different encoding based on a double splitting over X. More formally, the Σ-partition Γ in Definition 2 can be redefined as follows:

Clearly, Γi,j extends Γi by performing a second call to Γi at each branch. In other words, after the selection of an item ai, we iterate the same reasoning over transactions involving ai.

Our algorithm for ARs mining is illustrated in Algorithm 1, that we refer to as SATAR (SAT approach for ARs mining). Given a transaction database D and following an ordering over items of D at each iteration an item a is fixed to be

Figure 1: SAT Encoding Scheme for ARs.

Algorithm 1: Decomposition-based ARs Mining

Data: A transaction database D, α, β Result: The set of all ARs R 1 R ← ∅, Γ ← ∅, V = 〈a1 . . . an〉 ← items(D); 2 for a ∈ V do 3 D′ ← {T ∈ D | a ∈ T}; 4 V ′ ← items(D′ ) \ {a}; 5 Γ←Γ∪ {a}; 6 for a′ ∈ V ′ do 7 D′′ ← {T ∈ D′ | a′ ∈ T}; 8 Γ ← Γ ∪ {a′ }; 9 F = encode cnf(Γ,D′′ ); // F = Σ∧Γi,j 10 R = R ∪ enumerate models(F ) ; 11 Γ ← (Γ \ {a′ }) ∪ {¬a′ }; 12 end 13 F = encode cnf(Γ,D′ ) ; // F = Σ∧Γi,i 14 R = R∪ enumerate models(F) ; 15 Γ← (Γ \ {a}) ∪ {¬a}; 16 end 17 return R;

in X restricting the encoding to transactions containing a denoted D′ over a subset of items V ′ ⊆ V . A second iteration is performed by fixing a second item a′ to be in X leading to more restricted subset of transactions D′′ . Then, the function encode cnf is called over D′′ to encode the problem into a CNF formula. Finally, the enumeration of the models of the CNF formula is performed using the function enumerate models incarnating a SAT-based enumeration solver.

4.2 ADecomposition-based Encoding for MNRs

Now, we extend our decomposition-based approach to enumerate MNRs. To do so, new constraints have to be added to the previous encoding. Then, we perform the same splitting technique to limit the overhead in terms of the huge number of clauses. First, let us recall that MNRs have been characterized through the closure [Taouil et al., 2000] and the notion of minimal generator. In fact, a rule X → Y is nonredundant iff X ∪ Y is closed and X is a minimal generator. In other words, the MNRs are the closed rules in which the antecedents are minimal w.r.t. set inclusion. Using such property, in [Boudane et al., 2017b] the authors provided a characterization of the antecedents of the MNRs, called minimal generators. Let us first introduce some useful notions.

Definition 3. Let D be a transaction database and X a closed itemset in D. Then, an itemset X′ ⊆ X is a minimal generator of X iff Supp(X′ ,D) = Supp(X,D), and there is no X′′ ⊆ X s.t. X′′ ⊂ X′ and Supp(X′′ ,D) = Supp(X, D).

Proposition 1. [Boudane et al., 2017b] Given a transaction database D, the rule X → Y is a MNR in D iff X → Y is a closed AR, and |X| = 1 or, for all items a ∈ X, Supp(X, D) < Supp(X \ {a}, D).

Proposition 1 characterizes minimal generators by providing constraints over its items. A direct translation of such characterization into constraints can be done as follows:

That is, Constraint (9) enforces that if a belongs to X then there exists a transaction T such that X ̸⊂ T and X \ {a} ⊂ T. Hence, the MNRs correspond to the models of the CNF formula Σ ∧ ∆ ∧ Θ where Θ is the closure constraint (6).

Unfortunately, Constraint (9) leads to too large formulas. In particular, the inequality constraint ∑b̸∈T xb ≤ 1 has to be encoded for each transaction in the database. In the worst case, minimal generator constraints require a large number of clauses making the encoding of MNRs ever, large.

To tackle this problem, we consider the same splitting principle that leads to independent sub-problems of the form Σ ∧ ∆ ∧ Θ ∧ Γi,j . The main difference with the enumeration of ARs lies in the fact that the minimal generator constraint depends on the whole transaction database. In fact, a minimal generator of the database D restricted to transactions with ai and aj is not necessarily a minimal generator of D.

Next, let us show how the formula ∆ is simplified by Γi,j when i < j. The transaction database D can be partitioned into D1, D2, D3, and D4 such that D1 contains ai and not aj , D2 contains aj and not ai, D3 contains both ai and aj, and D4 does not contain neither ai nor aj. Under Γi,j, ∆ can be rewritten as the conjunction of ∆ over the items of D3 as:

More importantly, D4 is not used in ∆ under Γi,j assumption where i < j thanks to the double splitting over X, i.e., none of ai and aj are present in the transactions of D4. Consequently, for all T ∈ D4, ∑b̸∈T xb ≤ 1 is already falsified by two items. Moreover, ∆ ∧ Γi,i ≡ ⊤ since X is singleton and thus is a minimal generator.

For the closure constraint Θ, we proceed by simplifying the constraint (6) under Γi,j leading to:

5 Empirical Investigation

We now present the experiments carried out to evaluate the performance of our approach. In particular, we study the running time for discovering ARs and MNRs in sequential and parallel setting. For baseline comparison, we retain the CPbased algorithm CP4AR [Belaid et al., 2019] and the specialized method ECLAT-Z [Szathmary et al., 2008], which in turn is shown more competitive than all existing approaches.

Algorithm 1 is implemented in C++ top-on the SAT solver MiniSAT [E´en and S¨orensson, 2002], which is changed to enumerate all models by performing a DPLL procedure [Davis et al., 1962] without restart. We use the API OpenMP that supports multi-platform shared memory multiprocessing programming in C/C++. The partition is performed by considering the items frequencies in increasing order.

Our experiments were performed on a machine with Intel Xeon quad-core processors with 32GB of RAM running at 2.66 GHz on Linux CentOS. Time-out was set to 1800 seconds and memory-out to 10 GB in all runs. We consider the datasets used in [Belaid et al., 2019] coming from FIMI 1 and CP4IM 2 repositories. The minimum confidence threshold β is fixed to 75%3 and different minimum support values are chosen w.r.t. the size of each dataset. All experiments are available at: https://github.com/crillab/satar-xp.

We perform two kinds of experiments. In the first evaluation, we carry out a comparison to enumerate both ARs and MNRs. In the second, we perform a parallel evaluation to mining ARs and MNRs by varying the number of cores.

Sequential Evaluation. Table 1 reports comparative results of SATAR against CP4AR and ECLAT-Z, using different values of α (in percent). Table 1 contains both results for ARs and MNRs. It reports the number of models (i.e., patterns) and the total CPU time (in seconds) for each dataset with different values of α. "TO" (resp. "MO") is shown when time limit is exceeded (resp. when the memory limit is reached). We also use the symbol "-" to indicate that the method is not able to scale on the number of patterns under the time limit. As one can observe, for ARs mining, SATAR outperforms CP4AR on almost all tested datasets. Moreover, for some datasets e.g., connect and pumsb, the gain is impressive. Interestingly enough, our approach overpasses the specialized algorithm ECLAT-Z, e.g., anneal, chess and mushroom datasets. Remarkably, for the largest dataset kosarak, our approach is able to enumerate all ARs while ECLAT-Z and CP4AR fail for all the considered values of α. In total, on 19/33 SATAR provides the best time when ECLAT-Z ranked first on 13/33. CP4AR is not able to provide the best time on any test.

For MNRs mining, we have similar observations as for ARs. SATAR and ECLAT-Z show better results than CP4AR. Indeed, SATAR wins on 20 from 33 datasets, followed by ECLAT-Z with a score of 10, whereas CP4AR has only 2 datasets. Furthermore, on some large datasets SATAR outperforms ECLATZ on MNRs, e.g., pumsb and T10I4D100K with α = 75% and 0.02%, respectively.

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

2 http://dtai.cs.kuleuven.be/CP4IM/datasets/

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

Parallel Evaluation. The decomposition technique defined in this work allows to generate independent problems that can be handled on a multi-core machine. Hence, we extended SATAR algorithm for multi-core solving. The different subformulas Σ ∧ Γi,j are then distributed over the used cores to be solved. The sub-problems are fairly assigned to cores. We perform similar experiments by considering 1,2 and 4 cores and varying the minimum support threshold values. Figure 2 shows the solving time on a representative sample of datasets. As expected, our parallel approach allows us to considerably reduce the computing time. For instance, with a single core, the T10I4D100K dataset is not solved for α = 0.01% for MNRs, while this task is achieved when the number of cores is greater than 1. Moreover, the time needed to extract all MNRs from pumsb dataset with α = 75% is reduced from 950 seconds with a single core to less than 400 seconds with 4 cores. Clearly, the runtime gain increases with the number of cores. As one can observe in Figure 2, this gain is more important when the number of cores passes from 1 to 2 cores rather than from 2 to 4.

Let us stress that our decomposition is performed before the solving process rather than in a dynamic way during the search. Consequently, the time required by cores to solve their assigned sub-problems is different in general. In the sequel, we analyze the load unbalancing of our approach.

Load Balancing. To assess the suitability of our load balancing strategy, we provide an empirical analysis of the CPU time with different number of cores on a sample of datasets. We limit our analysis to ARs mining. Similar observations are made on MNRs. We fix the number of cores to 4. In Figure 3, for each value of α we report the average time over cores, the minimum and maximum time to quantify the idleness of some cores. The tighter the difference between minimum and maximum time is, the better the load balancing is.

As we can observe, our approach allows to limit the relative load unbalancing, i.e., all the cores spent almost the same time to solve their assigned sub-problems. This is more impressive for the dataset T10I4D100K. Overall, our decomposition strategy allows to balance correctly the search between the different cores. Last, it allows to tackle large datasets e.g., kosarak and T10I4D100K, proving the efficiency and scalability of our SATAR approach.

6 Conclusion

In this paper, we have proposed a novel SAT based approach to mine (minimal non-redundant) ARs from large transaction databases. Our approach relies on a decomposition strategy that allows us to achieve efficiency by suitably lowering the size of the sub-problems without jeopardizing completeness. An extensive campaign of experiments conducted over different real-world datasets has shown that our approach scales well and outperforms the CP based approach CP4AR while competed with the specialized approach ECLAT-Z.

Different research directions can improve this work. First, our decomposition approach can be performed dynamically in order to limit the load unbalancing. We are also interested in studying better ordering among variables to improve our decomposition technique.