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.
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.
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