Symmetry Breaking in Itemset Mining

Belaïd Benhamou, Saïd Jabbour, Lakhdar Sais, Yakoub Salhi

2014

Abstract

The concept of symmetry has been extensively studied in the field of constraint programming and in propositional satisfiability. Several methods for detection and removal of these symmetries have been developed, and their integration in known solvers of these domain improved dramatically their effectiveness on a large variety of problems considered difficult to solve. The concept of symmetry may be exported to other domains where some structures can be exploited effectively. Particularly in data mining where some tasks can be expressed as constraints. In this paper, we are interested in the detection and elimination of symmetries in the problem of finding frequent itemsets of a transaction database and its variants. Recent works have provided effective encodings as Boolean constraints for these data mining tasks and some recent works on symmetry detection and elimination in itemset mining problems have been proposed. In this work we propose a generic framework that could be used to eliminate symmetries for data mining task expressed in a declarative constraint language. We show how symmetries between the items of the transactions are detected and eliminated by adding symmetry-breaking predicate (SBP) to the Boolean encoding of the data mining task.

Paper Citation

in Harvard Style

Benhamou B., Jabbour S., Sais L. and Salhi Y. (2014). Symmetry Breaking in Itemset Mining . In Proceedings of the International Conference on Knowledge Discovery and Information Retrieval - Volume 1: KDIR, (IC3K 2014) ISBN 978-989-758-048-2, pages 86-96. DOI: 10.5220/0005078200860096

in Bibtex Style

@conference{kdir14,
author={Belaïd Benhamou and Saïd Jabbour and Lakhdar Sais and Yakoub Salhi},
title={Symmetry Breaking in Itemset Mining},
booktitle={Proceedings of the International Conference on Knowledge Discovery and Information Retrieval - Volume 1: KDIR, (IC3K 2014)},
year={2014},
pages={86-96},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005078200860096},
isbn={978-989-758-048-2},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Knowledge Discovery and Information Retrieval - Volume 1: KDIR, (IC3K 2014)
TI - Symmetry Breaking in Itemset Mining
SN - 978-989-758-048-2
AU - Benhamou B.
AU - Jabbour S.
AU - Sais L.
AU - Salhi Y.
PY - 2014
SP - 86
EP - 96
DO - 10.5220/0005078200860096