On SAT Models Enumeration in Itemset Mining

Saïd Jabbour, Lakhdar Sais, Yakoub SalhiarXiv 2015 · OpenReview

TL;DR

This paper tackles the challenge of efficiently enumerating frequent itemsets by adapting SAT solvers. The authors demonstrate that for this specific problem, a simpler DPLL-like approach with a well-chosen branching heuristic significantly outperforms complex CDCL solvers, suggesting that SAT solver components need careful tuning for specialized enumeration tasks.

What Problem Does This Paper Address?

Frequent itemset mining (FIM) is a fundamental task in data mining, aiming to discover sets of items that frequently co-occur in transactional datasets. While traditional FIM algorithms exist, recent research has explored encoding FIM problems into the Boolean Satisfiability (SAT) domain. This allows leveraging powerful SAT solvers. However, a key challenge arises when the goal is not just to find one solution (satisfiability) but to enumerate all possible solutions (models) that represent frequent itemsets. This model enumeration problem is particularly difficult when the number of frequent itemsets can be exponentially large. Existing SAT-based model enumeration methods, often relying on adding "blocking clauses," can become computationally prohibitive due to the sheer number of such clauses required. This paper investigates how to adapt modern SAT solvers, specifically their core components like restarts, branching heuristics, and clause learning, to efficiently handle the enumeration of frequent itemsets encoded as SAT problems.

Methods

The core of the paper involves two main aspects:

  1. SAT Encoding for Frequent Itemset Mining: The authors build upon existing SAT encodings for FIM. They define propositional variables to represent items and transactions. The encoding ensures that models of the SAT formula correspond to frequent itemsets. They introduce two key formulas:
  2. Formula (1) links transaction support to item presence.
  3. Formula (2) enforces the minimum support threshold.
  4. Formula (3) (and its CNF reformulation (4)) is crucial for forcing the enumerated itemsets to be closed frequent itemsets, which helps reduce output redundancy. The combined encoding is denoted as ECFIM(D, n).
  5. Adapting SAT Solvers for Model Enumeration: The paper's primary contribution lies in experimentally evaluating the impact of different SAT solver components on model enumeration efficiency for the FIM encoding. They compare:
  6. CDCL-based solver (CDCL-Enum): A state-of-the-art solver with restarts, clause learning, and sophisticated heuristics. When a model is found, a "no-good" (blocking clause) is added, and a restart is performed.
  7. DPLL-like procedures (DPLL-Enum variants): These are simplified versions that essentially perform backtracking without clause learning. They are tested with different branching heuristics:
  8. VSIDS: A popular heuristic that prioritizes variables based on their activity.
  9. JW (Jeroslow-Wang): A heuristic based on the maximum number of occurrences of variables.
  10. RAND: Random variable selection.

The goal is to understand which components are beneficial or detrimental for enumerating a potentially vast number of models.

Datasets

The experiments were conducted using datasets from the FIMI (Frequent Itemset Mining Implementations) and CP4IM (Constraint Programming for Itemset Mining) repositories. Specific datasets mentioned include:

  • german-credit
  • australian-credit
  • hepatitis.pdf
  • mushroom
  • anneal
  • primary-tumor
  • heart-cleveland.pdf
  • splice-1
  • chess
  • kr-vs-kp

These datasets represent a variety of transactional data characteristics, allowing for a comprehensive evaluation.

Key Insights and Ideas

  • CDCL vs. DPLL for Enumeration: For the specific task of enumerating a large number of models (as is common in FIM), the complex machinery of CDCL solvers (especially clause learning and restarts) can be counterproductive. A simpler DPLL-like approach, which avoids the overhead of learning and managing blocking clauses, often performs better.
  • Branching Heuristics Matter: The choice of branching heuristic is critical for DPLL-like enumerators. VSIDS and JW heuristics significantly outperform random selection, indicating that intelligent variable selection is key to efficiently navigating the search space for models.
  • Blocking Clauses are Costly: The paper highlights the exponential space complexity issue with traditional blocking clause approaches when the number of models is huge, as is typical for FIM. This reinforces the need for alternative enumeration strategies or solver adaptations.
  • Problem-Specific Tuning: The findings suggest that general-purpose SAT solvers, optimized for decision or single-solution finding, may not be directly optimal for model enumeration tasks. Tailoring solver components to the specific structure of the SAT encoding is crucial.

Key Results

The experimental evaluation, visualized through cactus plots, reveals that:

  • DPLL-like procedures generally outperform CDCL-Enum on the majority of instances, especially when the number of models (quorum) increases.
  • DPLL-Enum+JW and DPLL-Enum+VSIDS are significantly better than DPLL-Enum+RAND, demonstrating the importance of effective branching heuristics.
  • In many cases, DPLL-Enum+JW outperforms DPLL-Enum+VSIDS, suggesting it might be a more suitable heuristic for this SAT encoding.
  • For some datasets and quorums, DPLL-Enum+RAND and CDCL-Enum fail to enumerate all models within the given time limit, underscoring the scalability issues of these approaches for this problem.

Limitations and Future Work

  • Limitations: The paper acknowledges that the CDCL-based approach with blocking clauses is "clearly impractical" for FIM due to the potential exponential number of blocking clauses. The study focuses on specific components of SAT solvers and might not cover all possible adaptations.
  • Future Work: The authors plan to continue investigating the best heuristics for enumerating models in data mining problems. A particularly interesting avenue is exploring how to efficiently integrate clause learning into model enumeration, potentially in a more targeted way than standard CDCL solvers. They also aim to find better ways to integrate clauses learning for model enumeration.

Summary updated

Abstract

Frequent itemset mining is an essential part of data analysis and data mining. Recent works propose interesting SAT-based encodings for the problem of discovering frequent itemsets. Our aim in this work is to define strategies for adapting SAT solvers to such encodings in order to improve models enumeration. In this context, we deeply study the effects of restart, branching heuristics and clauses learning. We then conduct an experimental evaluation on SAT-Based itemset mining instances to show how SAT solvers can be adapted to obtain an efficient SAT model enumerator.
BibTeX
@misc{jabbour2015sat,
  author = {Saïd Jabbour and Lakhdar Sais and Yakoub Salhi},
  title = {{On SAT Models Enumeration in Itemset Mining}},
  year = {2015},
  eprint = {1506.02561},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1506.02561},
}
Figure