On maximal frequent itemsets mining with constraints

Said Jabbour (1) , Fatima Ezzahra (1, 2) , Imen Ouled Dlala (1, 3) , Badran Raddaoui (4, 5, 6) , Lakhdar Sais (1)

1 CRIL - Centre de Recherche en Informatique de Lens
2 INPT - Institut National des Postes et Télécommunications [Rabat]
3 LARODEC - Laboratoire de Recherche Opérationnelle de Décision et de Contrôle de Processus
4 TSP - INF - Département Informatique
5 ACMES-SAMOVAR - Algorithmes, Composants, Modèles Et Services pour l'informatique répartie
6 CNRS - Centre National de la Recherche Scientifique

Recently, a new declarative mining framework based on constraint programming (CP) and propositional satisfiability (SAT) has been designed to deal with several pattern mining tasks. The itemset mining problem has been modeled using constraints whose models correspond to the patterns to be mined. In this paper, we propose a new propositional satisfiability based approach for mining maximal frequent itemsets that extends the one proposed in [20]. We show that instead of adding constraints to the initial SAT based itemset mining encoding, the maximal itemsets can be obtained by performing clause learning during search. A major strength of our approach rises in the compactness of the proposed encoding and the efficiency of the SAT-based maximal itemsets enumeration derived using blocked clauses. Experimental results on several datasets, show the feasibility and the efficiency of our approach.

Domains: Information Retrieval [cs.IR]; Artificial Intelligence [cs.AI]; Software Engineering [cs.SE]

Said Jabbour, Fatima Ezzahra, Imen Ouled Dlala, Badran Raddaoui, Lakhdar Sais. On maximal frequent itemsets mining with constraints. CP 2018 : 24th International Conference on Principles and Practice of Constraint Programming, Aug 2018, Lille, France. pp.554-569, ⟨10.1007/978-3-319-98334-9_36⟩. ⟨hal-03700069⟩