×

zbMATH — the first resource for mathematics

Symmetries in itemset mining. (English) Zbl 1327.68194
De Raedt, Luc (ed.) et al., ECAI 2012. 20th European conference on artificial intelligence, Montpellier, France, August 27–31, 2012. Proceedings. Including proceedings of the 7th conference on prestigious applications of artificial intelligence (PAIS-2012) and the system demonstrations track. Amsterdam: IOS Press (ISBN 978-1-61499-097-0/pbk; 978-1-61499-098-7/ebook). Frontiers in Artificial Intelligence and Applications 242, 432-437 (2012).
Summary: In this paper, we describe a new framework for breaking symmetries in itemset mining problems. Symmetries are permutations between items that leave invariant the transaction database. Such kind of structural knowledge induces a partition of the search space into equivalent classes of symmetrical itemsets. Our proposed framework aims to reduce the search space of possible interesting itemsets by detecting and breaking symmetries between items. Firstly, we address symmetry discovery in transaction databases. Secondly, we propose two different approaches to break symmetries in a preprocessing step by rewriting the transaction database. This approach can be seen as an original extension of the symmetry breaking framework widely used in propositional satisfiability and constraint satisfaction problems. Finally, we show that Apriori-like algorithms can be enhanced by dynamic symmetry reasoning. Our experiments clearly show that several itemset mining instances taken from the available datasets contain such symmetries. We also provide experimental evidence that breaking such symmetries reduces the size of the output on some families of instances.
For the entire collection see [Zbl 1272.68015].

MSC:
68T05 Learning and adaptive systems in artificial intelligence
PDF BibTeX XML Cite
Full Text: Link