A Symbolic Approach to Computing Disjunctive Association Rules from Data

Saïd Jabbour, Badran Raddaoui, Lakhdar SaisIJCAI 2023 · DOI

TL;DR

This paper introduces a novel generalization of association rules called "disjunctive association rules" that can capture more complex relationships between items in transactional data. They propose a symbolic approach using propositional logic and SAT solvers to efficiently mine these rules, demonstrating its effectiveness on real-world datasets.

What Problem Does This Paper Address?

Traditional association rule mining (ARM) focuses on rules where both the antecedent (X) and consequent (Y) are conjunctions of items (e.g., "if a customer buys bread and butter, they will also buy milk"). While useful, this approach can miss valuable insights when items can be substituted or when relationships are more complex. For instance, a rule like "if a customer buys bread, they might buy milk or butter" is not directly captured. This paper addresses this limitation by introducing "disjunctive association rules" that allow for disjunctions (ORs) within the antecedent and consequent, making them more expressive. The challenge then becomes efficiently mining these more complex rules from large datasets.

Methods

The core of this paper lies in its symbolic approach to mining these generalized disjunctive association rules.

  • k-Disjunctive Support: They introduce a new concept called "k-disjunctive support." This relaxes the traditional itemset matching by allowing a transaction to match an itemset even if up to k items from the itemset are missing in the transaction, as long as at least one item is present. This leads to "k-disjunctive support based itemsets."
  • (k, k')-Disjunctive Association Rules: Building on this, they define "(k, k')-disjunctive support based association rules" where the antecedent is a k-disjunctive itemset and the consequent is a k'-disjunctive itemset. This allows for flexible matching of both parts of the rule.
  • Symbolic Encoding and SAT Solving: The key innovation is a polynomial-time reduction of the mining problem to the propositional satisfiability (SAT) problem. They encode the problem of finding these rules into a Conjunctive Normal Form (CNF) formula. The models of this CNF formula then correspond directly to the desired disjunctive association rules. This approach leverages the power of modern SAT solvers for efficient rule discovery.
  • Closure Constraint: They also incorporate a "closure constraint" to ensure that the mined rules are "closed," meaning they cannot be extended further while maintaining the same support.

Datasets

The authors evaluated their approach on several publicly available datasets from the FIMI repository, including:

  • chess
  • mushroom
  • pumsb
  • connect
  • retail
  • T1014D100K
  • T40110D100K

These datasets represent a variety of sizes and characteristics, commonly used for benchmarking association rule mining algorithms.

Key Insights and Ideas

  • Beyond Conjunctions: The most significant insight is the realization that disjunctions are crucial for capturing richer patterns in real-world data, moving beyond the limitations of purely conjunctive rules.
  • Flexibility through k: The introduction of the k-disjunctive support parameter provides a tunable knob to control the expressiveness and matching flexibility of itemsets and rules, allowing for a spectrum from classical rules (k=0) to highly generalized ones.
  • SAT as a Unifying Framework: The paper demonstrates the power of SAT solvers not just for classical problems but also for complex data mining tasks like generalized association rule mining. This highlights the potential of symbolic AI approaches to tackle diverse computational challenges.
  • Separation of Modeling and Solving: The symbolic encoding allows for a clear separation between defining the problem (modeling) and finding the solutions (solving). This makes the approach adaptable to new constraints without modifying the core mining algorithm.

Key Results

  • Efficiency: The proposed symbolic approach, when encoded into CNF and solved using SAT solvers, proved efficient on various real-world datasets.
  • Scalability: Experiments showed that the approach can handle large datasets, although the time complexity generally increases with the parameter k' (the flexibility of the consequent).
  • Parallelization Benefits: The paper demonstrates that parallelizing the SAT solving process significantly reduces computation time, especially for larger k' values and datasets. For example, mining closed 6-DSVARs on the mushroom dataset with a = 35% took over 1000 seconds with a single core but was reduced to under 60 seconds with 4 cores.
  • Increased Rule Count: As k' increases, the number of discovered rules also increases substantially. For instance, for the chess dataset with a = 75%, the number of classical rules (k'=0) was around 287k, while for 4-DSVARs (k'=4), it jumped to approximately 85 million.

Limitations and Future Work

  • Computational Cost with High k: The paper acknowledges that increasing the k parameter (allowing more missing items) leads to a significant increase in computation time and the number of rules.
  • Minimal Non-Redundant Rules: The authors suggest extending their framework to mine "minimal non-redundant (k, k')-DSVARs," which would further refine the output and reduce redundancy.
  • Pre-processing Techniques: To improve efficiency, especially for larger k values, they propose exploring pre-processing techniques.
  • Load Balancing in Parallelization: In the parallel evaluation, they noted that the decomposition method might not always achieve perfect load balancing, leading to suboptimal speedups in some cases. Future work could address this with dynamic load balancing strategies.

Summary updated

BibTeX
@inproceedings{jabbour2023symbolic,
  author = {Saïd Jabbour and Badran Raddaoui and Lakhdar Sais},
  title = {{A Symbolic Approach to Computing Disjunctive Association Rules from Data}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/237},
}
Figure