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

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

Yacine Izza, Said Jabbour, Badran Raddaoui, Abdelahmid Boudane

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 1265-1271. https://doi.org/10.24963/ijcai.2020/176

While traditional data mining techniques have been used extensively for finding patterns in databases, they are not always suitable for incorporating user-specified constraints. To overcome this issue, CP and SAT based frameworks for modeling and solving pattern mining tasks have gained a considerable audience in recent years. However, a bottleneck for all these CP and SAT-based approaches is the encoding size which makes these algorithms inefficient for large databases. This paper introduces a practical SAT-based approach to discover efficiently (minimal non-redundant) association rules. First, we present a decomposition-based paradigm that splits the original transaction database into smaller and independent subsets. Then, we show that without producing too large formulas, our decomposition method allows independent mining evaluation on a multi-core machine, improving performance. Finally, an experimental evaluation shows that our method is fast and scale well compared with the existing CP approach even in the sequential case, while significantly reducing the gap with the best state-of-the-art specialized algorithm.
Keywords:
Data Mining: Frequent Pattern Mining
Constraints and SAT: Constraints and Data Mining ; Constraints and Machine Learning
Constraints and SAT: Constraints: Modeling, Solvers, Applications