A SAT-Based Approach for Mining Association Rules

Abdelhamid Boudane, Saïd Jabbour, Lakhdar Sais, Yakoub SalhiIJCAI 2016 · OpenReview

Introduction

Association rule mining is a fundamental task in data science, typically used to uncover relationships between variables in large datasets. Traditional algorithms like Apriori and FP-Growth rely on a two-step procedural approach: first identifying frequent itemsets and then generating rules from those sets. While effective for standard tasks, these methods are often difficult to adapt when new constraints—such as finding only "closed" or "indirect" rules—are introduced.

This paper proposes a shift toward a declarative framework using Propositional Satisfiability (SAT). By modeling the entire association rule mining problem as a single Boolean formula, the authors introduce SFAR (SAT-based Association Rules), a method that offers significant flexibility and competitive performance for complex mining tasks.

The SFAR Framework

The core of the SFAR approach is the translation of data mining requirements into Boolean logic. The framework uses variables to represent:

  • Item Membership: Whether an item belongs to the antecedent ($X$) or the consequent ($Y$).
  • Transaction Coverage: Whether a specific transaction in the database supports the rule.

Constraints such as disjointness (ensuring an item isn't in both $X$ and $Y$), support (minimum frequency), and confidence (reliability of the implication) are encoded as cardinality and pseudo-Boolean constraints. Unlike traditional methods, SFAR finds valid rules in a single step by solving the resulting SAT formula.

Performance on Pure vs. Closed Rules

The authors evaluated SFAR against specialized procedural tools like ZART across 16 benchmark datasets. The results highlight a clear trade-off between simplicity and complexity.

For "pure" association rules—the simplest form of the problem—specialized procedural algorithms remain faster. As shown in the evaluation on the Australian-credit dataset, ZART maintains a significant speed advantage over SFAR across varying confidence levels.

Performance comparison for pure rules on the Australian-credit dataset (frequency=50%).

However, the advantage shifts dramatically when mining Closed Association Rules. These rules are more informative because they eliminate redundancy. Because the "closed" constraint can be added to the SAT formula as a simple additional clause, SFAR handles the increased complexity much more efficiently than procedural methods that must be redesigned from scratch.

Performance comparison for closed rules on the Australian-credit dataset (confidence=100%).

As seen in the figure above, as the frequency threshold decreases—making the search space exponentially larger—SFAR's execution time remains manageable while ZART's time spikes significantly. This trend was consistent across dense datasets where traditional methods struggle with redundancy.

Conclusion

The SAT-based approach demonstrates that declarative modeling is a powerful alternative to specialized algorithms. While procedural tools are optimized for basic tasks, SFAR excels in complex scenarios like closed and indirect rule mining. This framework paves the way for future research into even more specialized constraints, such as top-k or weighted association rules, where the flexibility of SAT solvers can be fully leveraged.

Summary updated

Abstract

Discovering association rules from transaction databases is one of the most studied data mining task. Many effective techniques have been proposed over the years. All these algorithms share the same two steps methodology: frequent itemsets enumeration followed by effective association rules generation step. 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 Boolean formula whose models correspond to the rules to be mined. To highlight the flexibility of our proposed framework, we also address two other variants, namely the closed and indirect association rules mining tasks. Experiments on many datasets show that on both closed and indirect association rules mining tasks, our declarative approach achieves better performance than the state-of-the-art specialized techniques.
BibTeX
@inproceedings{boudane2016sat,
  author = {Abdelhamid Boudane and Saïd Jabbour and Lakhdar Sais and Yakoub Salhi},
  title = {{A SAT-Based Approach for Mining Association Rules}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=BybqXBzO-S},
}
Figure