Constraint Programming for Mining Borders of Frequent Itemsets

Mohamed-Bachir Belaid, Christian Bessiere, Nadjib LazaarIJCAI 2019 · DOI

TL;DR

This paper introduces a novel constraint programming (CP) framework for mining both maximal frequent itemsets (MFIs) and minimal infrequent itemsets (MIIs) using a single, parameterized model. By defining two new global constraints, FREQUENTSUBS and INFREQUENTSUPERS, the authors provide a flexible way to specify user queries for itemset mining and demonstrate that mining constrained borders is coNP-hard, justifying their "multi-shot" approach.

What Problem Does This Paper Address?

Discovering frequent itemsets is a cornerstone of data mining. However, the sheer volume of frequent itemsets can be overwhelming. Researchers often focus on "borders" of frequent itemsets: Maximal Frequent Itemsets (MFIs), which are frequent itemsets whose supersets are infrequent, and Minimal Infrequent Itemsets (MIIs), which are infrequent itemsets whose subsets are frequent. While MFIs and MIIs represent complementary concepts (the positive and negative borders of frequent itemsets), existing methods often treat them separately. This paper addresses the challenge of developing a unified framework that can efficiently mine either MFIs or MIIs, and importantly, can incorporate additional user-defined constraints on these itemsets.

Methods

The core contribution is a generic constraint programming model, MODEL_{D,s,b}, designed to mine either MFIs or MIIs. This model utilizes a vector of Boolean variables where each variable represents the presence of an item in an itemset. The key innovations are two new global constraints:

  • FREQUENTSUBS: This constraint ensures that all proper subsets of a potential itemset are frequent. It is implemented with a polynomial-time propagator that prunes the search space by enforcing domain consistency.
  • INFREQUENTSUPERS: This constraint ensures that all proper supersets of a potential itemset are infrequent. It also comes with a polynomial-time propagator for domain consistency.

The choice between mining MFIs or MIIs is controlled by a single Boolean parameter b. The paper also proves that mining borders with additional constraints is coNP-hard, which implies that a single, efficient CP model for all possible constrained border mining problems is unlikely. This justifies their approach of using a flexible CP model that can handle various constraints through propagation.

Datasets

The paper uses standard benchmark datasets for evaluation, including:

  • Zoo
  • Chess
  • Anneal
  • Connect
  • Mushroom
  • Pumsb

These datasets are characterized by their name, number of items (|I|), number of transactions (|T|), and density (ρ). No new datasets were introduced.

Key Insights and Ideas

  • Unified Framework: The ability to mine both MFIs and MIIs with a single parameterized CP model is a significant simplification and offers flexibility to users.
  • Global Constraints for Borders: The introduction of FREQUENTSUBS and INFREQUENTSUPERS provides a principled way to model the border properties within a CP framework.
  • CoNP-Hardness of Constrained Borders: The proof that mining constrained borders is coNP-hard is crucial. It explains why specialized, "one-shot" algorithms might fail when additional constraints are present and validates the "multi-shot" or iterative approach enabled by CP.
  • Duality in Propagators: While not perfectly symmetrical, the propagators for FREQUENTSUBS and INFREQUENTSUPERS exhibit a duality in how they prune variable domains, reflecting the complementary nature of MFIs and MIIs.

Key Results

  • The proposed CP model (CP4MFI for MFIs and CP4MII for MIIs) is shown to be competitive with state-of-the-art specialized algorithms like FPGROWTH and WALKY-G.
  • CP4MII outperforms WALKY-G on a majority of instances, particularly on dense datasets where WALKY-G struggles with memory usage.
  • The CP approach excels when mining constrained borders (e.g., MFIs of a minimum size or MIIs of a maximum size). The constraint propagation effectively prunes the search space, leading to significant speedups compared to specialized algorithms that treat constraints as a post-processing step. For example, on Pumsb_17000, tightening the minimum size constraint for MFIs drastically reduced the computation time for the CP model, while FPGROWTH's time remained relatively constant.

Limitations and Future Work

  • Performance on Very Large Datasets: While competitive, the CP approach's performance can still be limited by the inherent complexity of constraint satisfaction problems, especially on extremely large datasets where specialized algorithms might still have an edge.
  • CoNP-Hardness Implication: The coNP-hardness result for constrained borders implies that for arbitrary constraints, a single CP model might not be the most efficient solution. Future work could explore more sophisticated "multi-shot" strategies or hybrid approaches.
  • Propagator Efficiency: While polynomial, the time complexity of the propagators is O(n² × m). Further optimizations or more advanced propagation techniques could be explored.
  • Exploration of Other Constraints: The paper focuses on cardinality constraints. Exploring the effectiveness of the framework with other types of user-defined constraints would be a valuable future direction.

Summary updated

BibTeX
@inproceedings{belaid2019constraint,
  author = {Mohamed-Bachir Belaid and Christian Bessiere and Nadjib Lazaar},
  title = {{Constraint Programming for Mining Borders of Frequent Itemsets}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/149},
}
Figure