You are here

CoverSize: {A} Global Constraint for Frequency-Based Itemset Mining

TitleCoverSize: {A} Global Constraint for Frequency-Based Itemset Mining
Publication TypeConference Paper
Year of Publication2017
AuthorsSchaus, Pierre, Aoga John O. R., and Guns Tias
Conference NamePrinciples and Practice of Constraint Programming: 23rd International Conference, {CP 2017}
PublisherSpringer International Publishing
Conference LocationMelbourne, VIC, Australia
ISBN Number978-3-319-66158-2

Constraint Programming is becoming competitive for solving certain data-mining problems largely due to the development of global constraints. We introduce the CoverSize constraint for itemset mining problems, a global constraint for counting and constraining the number of transactions covered by the itemset decision variables. We show the relation of this constraint to the well-known table constraint, and our filtering algorithm internally uses the reversible sparse bitset data structure recently proposed for filtering table. Furthermore, we expose the size of the cover as a variable, which opens up new modelling perspectives compared to an existing global constraint for (closed) frequent itemset mining. For example, one can constrain minimum frequency or compare the frequency of an itemset in different datasets as is done in discriminative itemset mining. We demonstrate experimentally on the frequent, closed and discriminative itemset mining problems that the CoverSize constraint with reversible sparse bitsets allows to outperform other CP approaches.

Full text: