Constraint Programming for Mining Borders of Frequent Itemsets

Belaid, Mohamed-Bachir; Bessiere, Christian; Lazaar, Nadjib

doi:10.24963/ijcai.2019/149

Constraint Programming for Mining Borders of Frequent Itemsets

Mohamed-Bachir Belaid, Christian Bessiere, Nadjib Lazaar

Download BibTeX Cite

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. Main track. Pages 1064-1070.

https://doi.org/10.24963/ijcai.2019/149

Keywords

Constraints and SAT: Global Constraints

Abstract

Frequent itemset mining is one of the most studied tasks in knowledge discovery. It is often reduced to mining the positive border of frequent itemsets, i.e. maximal frequent itemsets. Infrequent itemset mining, on the other hand, can be reduced to mining the negative border, i.e. minimal infrequent itemsets. We propose a generic framework based on constraint programming to mine both borders of frequent itemsets.One can easily decide which border to mine by setting a simple parameter. For this, we introduce two new global constraints, FREQUENTSUBS and INFREQUENTSUPERS, with complete polynomial propagators. We then consider the problem of mining borders with additional constraints. We prove that this problem is coNP-hard, ruling out the hope for the existence of a single CSP solving this problem (unless coNP ⊆ NP).

Mohamed-Bachir Belaid, Christian Bessiere, and Nadjib Lazaar. 2019. Constraint Programming for Mining Borders of Frequent Itemsets. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19. IJCAI, 1064–1070. https://doi.org/10.24963/ijcai.2019/149

@inproceedings{ijcai2019p149,
  title     = {Constraint Programming for Mining Borders of Frequent Itemsets},
  author    = {Belaid, Mohamed-Bachir and Bessiere, Christian and Lazaar, Nadjib},
  booktitle = {Proceedings of the Twenty-Eighth International Joint Conference on
               Artificial Intelligence, {IJCAI-19}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Sarit Kraus},
  pages     = {1064--1070},
  year      = {2019},
  month     = {8},
  note      = {Main track},
  doi       = {10.24963/ijcai.2019/149},
  url       = {https://doi.org/10.24963/ijcai.2019/149},
}

TY  - CPAPER
TI  - Constraint Programming for Mining Borders of Frequent Itemsets
AU  - Belaid, Mohamed-Bachir
AU  - Bessiere, Christian
AU  - Lazaar, Nadjib
T2  - Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2019
SP  - 1064
EP  - 1070
DO  - 10.24963/ijcai.2019/149
UR  - https://doi.org/10.24963/ijcai.2019/149
ER  -