Sweeping the disjunctive search space towards mining new exact concise representations of frequent itemsets

摘要

Concise (or condensed) representations of frequent patterns follow the minimum description length (MDL) principle, by providing the shortest description of the whole set of frequent patterns. In this work, we introduce a new exact concise representation of frequent itemsets. This representation is based on an exploration of the disjunctive search space. The disjunctive itemsets convey information about the complementary occurrence of items in a dataset. A novel closure operator is then devised to suit the characteristics of the explored search space. The proposed operator aims at mapping many disjunctive itemsets to a unique one, called a disjunctive closed itemset. Hence, it permits to drastically reduce the number of handled itemsets within the targeted re-presentation. Interestingly, the proposed representation offers direct access to the disjunctive and negative supports of frequent itemsets while ensuring the derivation of their exact conjunctive supports. We conclude from the experimental results reported and discussed here that our representation is effective and sound in comparison with different other concise representations.