Constraint Programming for Mining Borders of Frequent Itemsets

Mohamed-Bachir Belaid 1 Christian Bessière 1 Nadjib Lazaar 1
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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).
Keywords : Global Constraints
Document type :
Conference papers
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02310629
Contributor : Isabelle Gouat <>
Submitted on : Thursday, October 10, 2019 - 12:32:14 PM
Last modification on : Saturday, October 12, 2019 - 1:22:44 AM

File

ijcai19.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Mohamed-Bachir Belaid, Christian Bessière, Nadjib Lazaar. Constraint Programming for Mining Borders of Frequent Itemsets. IJCAI: International Joint Conference on Artificial Intelligence, Aug 2019, Macao, China. pp.1064-1070, ⟨10.24963/ijcai.2019/149⟩. ⟨lirmm-02310629⟩

Share

Metrics

Record views

28

Files downloads

38