Breaking Symmetries in Association Rules

In this paper, we propose an extension of the framework proposed in [1] for breaking symmetries in association rules problems. Symmetries are defined as permutations between items that leave invariant the set of the transactions. Such kind of structural knowledge induces a partition of the search space into equivalent classes of symmetrical itemsets. Our proposed approach aims show that symmetries can be exploited to reduce the search space of associations rules by the use of symmetries detected before. Firstly, recall the symmetry discovery in transaction databases. Secondly, we propose how symmetries can be broken as a preprocessing step. Our experiments clearly show that several association rules 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.