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 coNPhard, ruling out the hope for the existence of a single CSP solving this problem (unless coNP ? NP).