A SAT-Based Approach for Mining Association Rules

1 Introduction

Association analysis is one of the fundamental data mining task. It aims to discover interesting relationships hidden in large data sets. Such relationships between sets of items are presented in the form of implications, called association rules, along with metrics to quantify the rule's relevance. Since the first well known application [Agrawal and Srikant, 1994], usually referred to as market basket data analysis, several new application domains have been identified, including among others, bioinformatics, medical diagnosis, networks intrusion detection, web mining, and scientific data analysis. This broad spectrum of applications enabled association analysis to be applied to a variety of data sets, including sequential, spatial, and graph-based data.

There has been considerable work developing a nice theory and fast algorithms for mining association rules. Among the existing techniques, Apriori [Agrawal and Srikant, 1994] and FP-Growth [Han et al., 2004] are some of the most known algorithms. All these algorithms share the same two steps methodology. The first step is to find all itemsets with adequate supports and the second step is to generate association rules with high confidence by combining these frequent or large itemsets. Support and confidence are two important statistical measures. For a given rule r : X ! Y , the support is defined as the percentage of transactions containing X [ Y , while the confidence provides an estimate of the conditional probability p(X◁Y ) of Y given X usually defined as the ratio between the supports of X [ Y and X. Association rules mining aims to identify all rules meeting user specified constraints such as minimum support and minimum confidence. Supports is used to eliminate uninteresting rules, while confidence measures the reliability of the inference made by the rule. The higher the confidence, the more likely it is for Y to be present in transactions that contain X.

From this brief overview, two observations can be made. First, one can easily guess why association rules mining techniques follow a two steps based approach. Secondly, we can also observe that the relevance of the rules to be mined are expressed using constraints. As pointed out in [Raedt et al., 2011], on many data mining tasks, constraints are often part of the problem specification. This observation led to a new active and multidisciplinary research field, initiated by Luc De Reardt et al. [Raedt et al., 2008], focussing on cross fertilization between data mining and artificial intelligence (AI). Two well-known AI representation and solving models, namely constraint programming (CP) and propositional satisfiability (SAT) have been used to model and solve several data mining tasks, including pattern mining [Guns et al., 2011; N´egrevergne and Guns, 2015; Jabbour et al., 2015a; 2015b] and clustering [Davidson et al., 2010; M´etivier et al., 2012; Dao et al., 2013]. This new framework offers a declarative and flexible representation model. Indeed, in data mining, new constraints often require new implementations, while they can be easily integrated in such declarative models.

Following this research trend, in this paper, we propose a new propositional satisfiability based approach to mine association rules in a single step. The task is modeled as a propositional formula whose models correspond to the rules to be mined. As the number of association rules can grow rapidly, especially as we lower the frequency requirements, limiting the number of rules produced without information loss has be recognized as an important issue. It has also been noted that some of the infrequent patterns, such as indirect associations, provide useful insight into the data. In our second contribution, we consider two well-known variants designed to overcome these two main limitations, namely closed [Taouil et al., 2000] and indirect [Tan et al., 2000] association rules mining tasks. Our goal is to highlight the flexibility and the nice declarative features of our proposed framework.

The paper is organized as follows. After some preliminaries about propositional satisfiability and association rules mining, we present in Section 3 our SAT-based encoding of the association rules mining task. Section 4 presents the two variants mentioned above, namely closed and indirect associations rules. In Section 5, our proposed approches are extensively evaluated on many data sets, demonstrating that declarative approaches can achieve better performances with respect to specialized techniques particularly on closed and indirect association rules.

2 Preliminaries

2.1 Propositional Logic and SAT Problem

In this section, we define the syntax and the semantics of propositional logic. Let Prop be a countable set of propositional variables. We use the letters p, q, r, etc to range over Prop. The set of propositional formulas, is defined inductively started from Prop, the constant ? denoting false, the constant > denoting true, and using the usual logical connectives ≻, ^, _, !, and $. We use P(A) to denote the set of propositional variables appearing in the formula A. A Boolean interpretation I of a formula A is defined as a function from P(A) to ¶0↪ 1♦ (0 corresponds to false and 1 to true). A model of a formula A is a Boolean interpretation I that satisfies A, i.e. I(A) = 1. A formula A is satisfiable if there exists a model of A. 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 a negated propositional variable (≻p). The two literals p and ≻p are called complementary. Let us mention that any propositional formula can be translated to a CNF formula equivalent w.r.t. satisfiability, using linear Tseitin's encoding [Tseitin, 1968]. The SAT problem consists in deciding wether a given CNF formula admits a model or not.

2.2 Association Rules

Let ⌦ be a finite non empty set of symbols, called items. From now on, we assume that this set is fixed. 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 use 2⌦ to denote the set of itemsets over ⌦ and we use the capital letters I, J, K, etc to range over the elements of 2⌦.

A transaction is an ordered pair (i↪ I) where i is a natural number, called transaction identifier, and I an itemset, i.e., (i↪ I) 2 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 2 N ♣ (i↪ J) 2 D and I ✓ J♦. The support of I in D, denoted S(I↪D), corresponds to the cardinality of C(I↪D), i.e., S(I↪D) = ♣C(I↪D)♣. An itemset I ✓ ⌦ such that S(I↪D) ≥ 1 is a closed itemset if, for all itemsets J with I ⇢ J, S(J↪ D) < S(I↪ D).

For instance, consider the transaction database D in Table 1. In this case, we have C(¶a↪ b♦↪D) = ¶1↪ 2↪ 3♦ and S(¶a↪ b♦↪D) = 3 while S(¶f♦↪D) = 2. The itemset ¶a↪ b♦ is closed, while ¶f♦ is not closed.

In this work, we are interested in the problem of mining association rules. An association rule is a pattern of the form X ! Y where X (called the antecedent) and Y (called the consequent) are two disjoint itemsets. In association rules mining, the interestingness predicate is defined using the notions of support and confidence. The support of an association rule X ! Y in a transaction database D, defined as S(X ! Y↪D) = S(X[Y↪D) ♣D♣ , determines how often a rule is applicable to a given data set, i.e., the occurrence frequency of the rule. The confidence of X ! Y in D, defined as Conf(X ! Y↪D) = S(X[Y↪D) S(X↪D) , provides an estimate of the conditional probability of Y given X. A valid association rule is an association rule with support and confidence greater or equal to the minimum support (↵) and minimum confidence (β) thresholds. More precisely, given a transaction database D, a minimum support threshold ↵ and a minimum confidence threshold β, the problem of mining association rules consists in computing the following set:

3 SAT-Based Association Rules Mining

In this section, we describe a SAT encoding for the problem of mining association rules. The basic idea consists in the use of propositional variables to represent the covers of the itemsets X and X [ Y for each candidate rule X ! Y . These variables are used in 0/1 linear inequalities to determine wether the support and the confidence of the candidate rule are greater than the specified minimum thresholds for the support and the confidence.

Let D = ¶(1↪ I1)↪ ▷ ▷ ▷ ↪ (m↪ Im)♦ be a transaction database, ↵ a minimum support threshold and β a minimum confidence threshold. To represent the two itemsets of each candidate rule X ! Y , we associate two propositional variables xa and ya to each item a. The variables of the form xa (resp. ya) are used to represent the antecedent (resp. consequent) of each candidate rule. Then, to represent the cover of X and X [ Y , we associate to each transaction identifier i 2 ¶1 ▷ ▷ ▷m♦ two propositional variables pi and qi. The variables of the form pi (resp. qi) are used to represent the cover of X (resp. X [ Y ). More precisely, given a Boolean interpretation I, the candidate rule is X = ¶a 2 ⌦ ♣ I(xa) = 1♦ ! Y = ¶b 2 ⌦ ♣ I(yb) = 1♦, the cover of X is ¶i 2 N ♣ I(pi) = 1♦, and the cover of X [ Y is ¶i 2 N ♣ I(qi) = 1♦.

We now describe our SAT-based encoding using the propositional variables described previously. The first propositional formula allows us to express the constraint X \ Y = ;:

To obtain the cover of the itemset X, we use the following propositional formula:

In this formula, pi is false if and only if X contains an item that does not belong to the transaction i. As a consequence, the cover of X is ¶i 2 N ♣ I(pi) = 1♦.

In the same way as the previous formula, we use the following formula to capture the cover of X [ Y :

It is worth noticing that we use the propositional variables pi to prevent the reuse of the variables xa. This allows us to obtain a more compact formula.

Let us now introduce the formula expressing that the support of the candidate rule has to be greater than or equal to the specified threshold m ⇥ ↵ (in percentage):

This formula means that the number of variables qi (i 2 ¶1 ▷ ▷ ▷m♦) assigned to 1 has to be greater than or equal to ↵, which is equivalent to the fact that the support of X[Y is greater than or equal to m⇥↵.

Finally, we describe the formula expressing the fact that β is a minimum confidence threshold:

We here consider that β is given in percentage format β% where β is a positive integer. Thus, the previous formula can be rewritten as follows:

The two propositional formulas (4), (5) corresponds to 0/1 linear inequalities, usually called cardinality (resp. Pseudo Boolean) constraints. The first linear encoding of general 0/1 linear inequalities to CNF has been proposed by J. P. Warners in [Warners, 1998]. Several authors have addressed the issue of finding an efficient encoding of cardinality (e.g. [Asin et al., 2011; Jabbour et al., 2013a; Warners, 1998]) or Pseudo Boolean (e.g. [Ab´ıo et al., 2012; E´en and S¨orensson, 2006; Warners, 1998]) constraints as a CNF formula. Efficiency refers to both the compactness of the representation (size of the CNF formula) and to the ability to achieve the same level of constraint propagation (generalized arc consistency) on the CNF formula.

We use EAR(D↪ ↵↪ β) to denote the encoding corresponding to the conjunction of formulas (1), (2), (3), (4), and (5).

4 Closed and Indirect Association Rules

In this section, we highlight the nice declarative and flexible aspects of the proposed SAT framework for mining association rules. To this end, we consider two well-known association rules variants, namely closed [Taouil et al., 2000] and indirect association rules [Tan et al., 2000]. The first has been proposed to avoid redundant rules using condensed representation, while the second aims to find indirect relations in data. Indirect association, extensively used to build web recommandation systems [Kazienko, 2009], refers to a pair of items that rarely occur together but highly depend on the presence of a mediator itemset.

Definition 1 (Closed Association Rule) An association rule r : X ! Y is a Closed association rule iff r : X ! Y is a valid association rule and X [ Y is closed.

Intuitively, we obtain a closed association rule by maximizing either its antecedent or its consequent while decreasing neither the support nor the confidence.

A SAT encoding of the problem of mining closed association rules, noted ECAR(D↪ ↵↪ β), can be simply obtained by extending the encoding described previously (EAR(D↪ ↵↪ β)) with the following formula:

This formula means that if we have C(X [Y↪ D) = C(X [ Y [ ¶a♦↪D) then the item a has to belong to Y , i.e., a 2 Y . As a consequence, if X ! Y and X ! Y ] ¶a♦ are two valid association rules (] stands for disjoint union), then the Boolean interpretation that corresponds to the rule X ! Y is a counter-model of (6). Moreover, if there is no item a such that X ! Y ] ¶a♦ is a valid association rule, then the Boolean interpretation corresponding to X ! Y is a model of (6). Furthermore, it is worth noticing that the formula (6) encodes that X [ Y is closed. Indeed, we do not need to add a formula to maximize the antecedent of the rule as it is implicitly encoded in the formula (6). More precisely, the formula remains the same if we substitute ≻xa (resp. ya) by ≻ya (resp. xa). Thus, the formula (6) describes a necessary and sufficient requirement for mining the closed association rules. We can also note that the number of clauses added by the formula (6) is equal to the number of items.

We now consider a second mining task related to the problem of mining association rules. It consists in mining indirect rules, which allow to discover items that rarely occur together but frequently occur with other items [Tan et al., 2000].

Definition 2 Let D be a transaction database. Two items a0 and b0 are indirectly associated via an itemset M, called mediator, w.r.t. a maximum support threshold λ, a minimum support threshold ↵ and a mediator dependence threshold β iff the following conditions hold:

• ÷ S(¶a0♦ ! ¶b0♦↪D)  λ (Itempair Support Condition) 1 .
• ÷ There exists a non empty itemset M such that:
• S(¶a0♦ !M↪D) ≥ ↵ and S(¶b0♦ !M↪D) ≥ ↵ (Mediator Support Condition)
• Dep(¶a0♦↪M↪ D) ≥ β and Dep(¶b0♦↪M↪ D) ≥ β where Dep(p↪Q↪D) is a dependence measure between p and Q w.r.t. D (Dependence Condition)

In other words, in the problem of mining indirect rules, we look for pairs of items that are infrequent (or rare) but separately involved in interesting association rules with the same consequent.

Over the year, several measures of dependence between two itemsets X and Y have been proposed, including IS measure [Tan et al., 2002] and classical confidence. The relevance of such measures depends on the target application. In this paper, as a dependency measure, we simply use the confidence of X ! Y . This last dependence measure is for example employed in [Kazienko, 2005] for a web recommendation application. Using confidence as a dependency measure and minimum confidence threshold instead of mediator dependance threshold the two conditions (mediator support and dependence) in Definition 2 can be simply stated as: ¶a0♦ ! M and ¶b0♦ !M are two valid association rules w.r.t. the minimum support ↵ and minimum confidence β thresholds.

In order to define a SAT encoding for the problem of mining indirect association rules, we have to use propositional variables that allow us to capture the cover of the association rule ¶a0♦ ! ¶b0♦ and we adapt the encoding EAR(D↪ ↵↪ β) to constrain the antecedent of the two association rules ¶a0♦ ! M and ¶b0♦ ! M to contain only a single item. We use the propositional variables xa0 c and xb0 c for each item c to represent a0 and b0 respectively. Similarly, we use the same set of variables ya for each item a as in EAR(D↪ ↵↪ β) to capture the elements of the mediator. Moreover, we introduce variables of the form pa0 i (resp. pb0 i ) to express the cover of the item a0 (resp. b0) in the same way as in EAR(D↪ ↵↪ β) and variables of the form qa0 i and qb0 i to express the covers of M [ ¶a0♦ and M [ ¶b0♦ respectively. Finally, we also introduce variables of the form ri to capture the cover of ¶a0↪ b0♦.

The following formula allows us to capture the association rule ¶a0♦ ! M:

where the variables of the form xa, pi and qi are replaced in EAR(D↪ ↵↪ β) with xa0 a , pa0 i and qa0 i respectively. The cardinality constraint Pa2⌦ xa0 a = 1 is used to require that antecedent of the rules contains a single item.

1 We can equivalently write S(¶a0↪b0♦↪D) ♣D♣  λ

In the same way as (7), we use the following formula to capture the association rule ¶b0♦ !M:

where the variables of the form xa, pi and qi are replaced in EAR(D↪ ↵↪ β) with xb0 a , pb0 i and qb0 i respectively.

We now describe the formula that allows us to capture the cover of ¶a0↪ b0♦:

Finally, we introduce the formula expressing that ¶a0♦ ! ¶b0♦ is infrequent w.r.t. the maximum support threshold λ:

In Definition 2, the items a0 and b0 are interchangeable leading to symmetrical indirect association rules. To avoid enumerating such redundant indirect association rules, we break symmetries between a0 and b0 by adding the constraints a0 < b0 over the set of items ⌦ expressed as:

We use EIR(D↪ λ↪ ↵↪ β) to denote the encoding of the problem of mining indirect rules (7) ^ (8) ^ (9) ^ (10) ^ (11).

5 Experiments

In this section, we present a comparative experimental evaluation of our proposed approaches with specialized association rules mining algorithms. We consider, three mining tasks, namely classical (pure), closed, and indirect association rules.

For our SAT based association rules mining, to enumerate all the models of a given propositional CNF formula, we use an adaptation of modern SAT solvers proposed in [Jabbour et al., 2014]. For cardinality and pseudo Boolean constraints, similarly to constraint programming, a propagator is associated to each constraint, obtained by maintaining the sum of its assigned variables. Managing such constraints on the fly outperforms our previous implementation based on the stateof-the-art SAT encodings [Jabbour et al., 2013b].

Another advantage, is that for each association rules mining instance, as the constraints (1), (2) and (3) does not depend on the specified thresholds, the propositional formula is generated only once. On all the considered data, the encoding phase does not exceed 5 seconds CPU time.

Let us note that our approach can be easily encoded using MiningZinc, a general framework for constraint-based pattern mining [Guns et al., 2013]. MiningZinc is a nice declarative framework, it offers a high level modeling language with a toolchain component for finding solutions.

In the experiments, we indicates by SFAR R with R 2 ¶pure↪ closed↪ indirect♦, our SAT based approach for mining the corresponding (R) association rules. We compare our approaches to two specialized association rules mining algorithms Coron 2 and SPMF 3 [Fournier-Viger et al., 2014]. Coron and SPMF are two multi-purpose data mining toolkits, implemented in Java, which incorporate a rich collection of data mining algorithms. For pure and closed association rules, we compare our approach to the ZART algorithm implemented in the Coron toolkit, which is one of the recent state-of-the-art algorithms for enumerating closed association rules [Szathmary et al., 2007]. For indirect association rules, we compare our solver to the SPMF implementation.

To give an idea on the size of our encodings, for classical association rule mining, the smallest (resp. the biggest) formula corresponds to the encoding of zoo-1 (resp. mushroom) data and contains 274 variables and 4379 clauses (resp. 16486 variables and 1616795 clauses).

To compare the performances of the different mining approaches, for each data we proceed as follows:

• ÷ For pure and closed association rules, the support is varied from 5% to 100% with an interval of size 5%. The confidence is varied in the same way. Then, for each data, a set of 400 configurations is generated.
• ÷ For indirect association rules, there are an additional parameter λ. The frequency and confidence are varied from 20% to 100% with an interval of size 20%. λ is varied from 10% to 100% with an interval of size 10%. This leads to 250 configurations for each data.

All the experiments were done on Intel Xeon quad-core machines with 32GB of RAM running at 2.66 Ghz. For each instance, we fix the timeout to 15 minutes of CPU time.

Table 2 describes our comparative results. We report in column 1 the name of the data and its characteristics in parenthesis: number of items (#items), number of transactions (#trans) and density. For each algorithm, we report the number of solved configurations (#S), and the average solving time (avg▷time in seconds). For each unsolved configuration, the time is set to 900 seconds (time out). In the last row of Table 2, we provide the total number of solved configurations and the global average CPU time in seconds.

2 Coron: http://coron.loria.fr/site/system.php

3 SPMF: http://www.philippe-fournier-viger.com/spmf/

Pure rules: The performances of ZART algorithm are better than SFAR. It solves 181 configurations more and it is better on all the considered data. ZART performs the enumeration of pure association rules in two steps. We observed that ZART performs the first step efficiently. Its CPU time does not exceed few seconds on the majority of the considered configurations. For the pure rules, the second step remains easy enough to perform. On classical association rules, the specialized algorithm ZART is better than SFAR.

Closed association rules: On this category, our SAT based approach outperform ZART. It solves 368 configurations more than ZART. Except for Splice-1 data, SFAR is the best on all the data in terms of the number of solved configurations and average CPU time. Let us remark that for Splice-1 data, the number of closed association rules is very limited (less than 4000). This explains why SFAR is worse than ZART on this data.

Let us recall that ZART finds the closed association rules in two steps. In the first step, the set of all frequent closed itemsets are efficiently enumerated (in few seconds), while in the second step, the extraction of association rules from the closed itemsets already generated is more time consuming. For instance, on Lymph data, SFAR is remarkably efficient. It solves about 100 configurations more than ZART. More generally, the higher the density of the data, the better are the performances of SFAR.

Indirect association rules: The performances of SFAR are very impressive. SFAR approach solves 572 instances more than SPMF. Here again, the approach is better on all the considered data. As we can remark the time needed by SFAR to obtain all indirect association rules is relatively stable and very low compared to SPMF. The number of indirect associations is very small compared to classical or closed association rules. However, SPMF takes a lot of time to find them. For example, if we take the Hepatitis data with frequency = 40%, confidence = 40% and λ = 20%, SPMF takes 122▷56 seconds to find just 359 indirect association rules, while SFAR does not exceed 1 second. We also noticed that for some configurations, SPMF takes excessive CPU time without finding any indirect association rule under the time limit. As a summary on indirect association rules, SFAR outperforms SPMF.

In Figure 1, the behavior of the considered approaches are highlighted on two representative data, Australian-credit and Kr-vs-kp. We varied one parameter, while maintaining the others fixed. For pure association rules, ZART and SFAR present similar behavior. When the frequency decreases, the time needed to find all rules increases. Let us remark that for some particular parameters values, our approach can outperforms the one of ZART on pure rules as is the case for Kr-vs-kp. Similar behavior is also observed for frequent closed association rules. However, we can note that when the confidence goes from 100% to 80%, the CPU time dramatically increases. Such a gap is more visible with SFAR on classical association rules and with ZART on closed association rules. Indeed, for Kr-vs-kp instance, using SFAR, we vary between 0 to 70 seconds while with ZART approach, the variation range is from 40 to 240 seconds.

Throughout this experimental study, we noticed that the specialized algorithms like ZART performs the first frequent (resp. closed) itemsets enumeration step efficiently. However, they take excessive CPU time in the second rules extraction step. Additionally, the extraction step is more time consuming for closed rules than classical rules even if the number of closed rules is lower in general. In Table 3, we provide the variation of the ratio between the number of classical (pure) rules and the number of closed rules. As we can observe, as the frequency decreases, the number of classical rules increases rapidly compared to the number of the closed rules. This last observation explains why SFAR is more efficient on the enumeration of closed rules than on the enumeration of classical ones. Overall, ZART solves more configurations for pure rules than for closed ones, while SFAR is more efficient in mining closed rules and indirect rules than classical ones.

As a summary of our experiments, we can say that for mining tasks combining several constraints, our declarative and flexible approach is better than specialized mining tools.

6 Acknowledgments

This work has been supported by the CNRS project QuDoSSI - D´efi Mastodons 2016.

7 Conclusion and perspectives

In this paper we developed a novel association rules mining approach that accurately discovers association rules efficiently. Our declarative approach contrasts with all the previous techniques as the mining of association rules is performed in a single step, thanks to our SAT based encoding. As a second contribution, we have shown that our proposed framework is flexible and declarative, as one can easily model other important variants, such as closed and indirect association rules mining. The experiments particularly show that on closed and indirect association rules mining, our proposed approaches achieves better performance with respect to specialized mining techniques.

Our work opens several perspectives. First, our results on closed and indirect association rules provide new research directions for association rules mining. Indeed, several other variants can be addressed more efficiently by extending our proposed framework. Such rules include among others top-k association rules, weighted association rules [Tao et al., 2003] and disjunctive association rules [Nanavati et al., 2001].