Abstract
The concept of symmetry has been extensively studied in the field of constraint programming and in the propositional satisfiability. Several methods for detection and removal of these symmetries have been developed, and their use in known solvers of these domains improved dramatically their effectiveness on a big variety of problems considered difficult to solve. The concept of symmetry may be exported to other areas where some structures can be exploited effectively. Particularly, in the area of data mining where some tasks can be expressed as constraints or logical formulas. We are interested here, by the detection and elimination of local and global symmetries in the item-set mining problem. Recent works have provided effective encodings as Boolean constraints for these data mining tasks and some idea on symmetry elimination in this area begin to appear, but still few and the techniques presented are often on global symmetry that is detected and eliminated statically in a preprocessing phase. In this work we study the notion of local symmetry and compare it to global symmetry for the itemset mining problem. We show how local symmetries of the boolean encoding can be detected dynamically and give some properties that allow to eliminate theses symmetries in SAT-based itemset mining solvers in order to enhance their efficiency.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Agrawal, R., Imieliński, T., Swami, A.: Mining association rules between sets of items in large databases. In: Proceedings of the 1993 ACM SIGMOD International Conference n Management of Data, SIGMOD ’93, pp. 207–216. ACM, New York (1993)
Agrawal, R., Srikant, R.: Fast algorithms for mining association rules in large databases. In: Proceedings of the 20th International Conference on Very Large Data Bases, VLDB ’94, pp. 487–499. Morgan Kaufmann Publishers Inc., San Francisco (1994)
Aloul, F.A., Ramani, A., Markov, I.L., Sakallah, K.A.: Solving difficult SAT instances in the presence of symmetry. In: Proceedings of the 39th Design Automation Conference (DAC 2002), pp. 731–736. ACM Press (2002)
Aloul, F.A., Markov, I.L., Sakallah, K.A.: Shatter: efficient symmetry-breaking for boolean satisfiability. In: DAC, pp. 836–839. ACM (2003)
Aloul, F.A., Ramani, A., Markov, I.L., Sakallak, K.A.: Solving difficult sat instances in the presence of symmetry. In: IEEE Transaction on CAD, vol. 22(9), pp. 1117–1137 (2003)
Aloul, F.A., Ramani, A., Markov, I.L., Sakallah, K.A.: Solving difficult instances of boolean satisfiability in the presence of symmetry. IEEE Trans. CAD Integr. Circ. Syst. 22(9), 1117–1137 (2003)
Aloul, F.A., Ramani, A., Markov, I.L., Sakallak, K.A.: Symmetry breaking for pseudo-boolean satisfiabilty. In: ASPDAC’04, pp. 884–887 (2004)
Audemard, G., Benhamou, B., Siegel, P.: Aval: an enumerative method for sat. In: Proceedings of the International Conference on Compitational Logic, CL’2000, pp. 373–383. Springer, London (2000)
Benhamou, B.: Study of symmetry in constraint satisfaction problems. In: PPCP’94, pp. 246–254 (1994)
Benhamou, B., Saïdi, M.R.: Local symmetry breaking during search in csps. In: Springer (ed.) The 13th International Conference on Principles and Practice of Constraint Programming (CP 2007), LNCS, vol. 4741, pp. 195–209. Providence (2007)
Benhamou, B., Sais, L.: Theoretical study of symmetries in propositional calculus and application. In: CADE’11, pp. 281–294 (1992)
Benhamou, B., Sais, L.: Tractability through symmetries in propositional calculus. J. Autom. Reasoning 12(1), 89–102 (1994)
Benhamou, B., Jabbour, S., Sais, L., Salhi, Y.: Symmetry breaking in itemset mining. In: Proceedings of the International Conference on Knowledge Discovery and Information Retrieval, pp. 86–96 (2014), doi:10.5220/0005078200860096
Benhamou, B., Nabhani, T., Ostrowski, R., Saïdi, M.R.: Dynamic symmetry breaking in the satisfiability problem. In: Proceedings of the 16th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR-16. Dakar (2010)
Besson, J., Boulicaut, J.F., Guns, T., Nijssen, S.: Generalizing itemset mining in a constraint programming setting. In: Inductive Databases and Constraint-Based Data Mining, pp. 107–126. Springer (2010)
Bonchi, F., Lucchese, C.: Extending the state-of-the-art of constraint-based pattern discovery. Data Knowl. Eng. 60(2), 377–399 (2007)
Bucila, C., Gehrke, J., Kifer, D., White, W.: Dualminer: a dual-pruning algorithm for itemsets with constraints. Data Min. Knowl. Disc. 7(3), 241–272 (2003)
Burdick, D., Calimlim, M., Gehrke, J.: Mafia: a maximal frequent itemset algorithm for transactional databases. In: ICDE, pp. 443–452 (2001)
Crawford, J., Ginsberg, M., Luks, E., Roy, A.: Symmetry-breaking predicates for search problems. In: Knowledge Representation (KR), pp. 148–159. Morgan Kaufmann (1996)
Desrosiers, C., Galinier, P., Hansen, P., Hertz, A.: Improving frequent subgraph mining in the presence of symmetry. In: MLG (2007)
Freuder, E.: Eliminating interchangeable values in constraints satisfaction problems. In: AAAI-91, pp. 227–233 (1991)
Gély, A., Medina, R., Nourine, L., Renaud, Y.: Uncovering and reducing hidden combinatorics in Guigues-Duquenne bases. In: Ganter, B., Godin, R. (eds.) ICFCA, Lecture Notes in Computer Science, pp. 235–248. Springer (2005)
Grahne, G., Zhu, J.: Fast algorithms for frequent itemset mining using fp-trees. IEEE Trans. Knowl. Data Eng. 17(10), 1347–1362 (2005)
Guns, T., Nijssen, S., De Raedt, L.: Itemset mining: a constraint programming perspective. Artif. Intell. 175(12–13), 1951–1983 (2011)
Guns, T., Dries, A., Tack, G., Nijssen, S., Raedt, L.D.: Miningzinc: a modeling language for constraint-based mining. In: International Joint Conference on Artificial Intelligence, pp. 1365-1372, Beijing (2013)
Han, J., Pei, J., Yin, Y.: Mining frequent patterns without candidate generation. In: Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, SIGMOD ’00, pp. 1–12. ACM, New York (2000)
Henriques, R., Lynce, I., Manquinho, V.M.: On when and how to use sat to mine frequent itemsets. CoRR arXiv:1207.6253 (2012)
Jabbour, S., Sais, L., Salhi, Y., Tabia, K.: Symmetries in itemset mining. In: 20th European Conference on Artificial Intelligence (ECAI ’12), pp. 432–437. IOS Press (2012)
Jabbour, S., Khiari, M., Sais, L., Salhi, Y., Tabia, K.: Symmetry-based pruning in itemset mining. In: 25th International Conference on Tools with Artificial Intelligence (ICTAI’13). IEEE Computer Society, Washington DC (2013)
Jabbour, S., Sais, L., Salhi, Y.: Boolean satisfiability for sequence mining. In: CIKM, pp. 649–658 (2013)
Jabbour, S., Sais, L., Salhi, Y.: Top-k frequent closed itemset mining using top-k sat problem. In: European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD’13), vol. 146, pp. 131–140. Springer (2013)
Khiari, M., Boizumault, P., Crémilleux, B.: Constraint programming for mining n-ary patterns. In: Cohen, D. (ed.) CP, Lecture Notes in Computer Science, vol. 6308, pp. 552–567. Springer (2010)
Krishnamurthy, B.: Short proofs for tricky formulas. Acta Inf. 22(3), 253–275 (1985)
Métivier, J. P., Boizumault, P., Crémilleux, B., Khiari, M., Loudni, S.: A constraint language for declarative pattern discovery. In: Proceedings of the 27th Annual ACM Symposium on Applied Computing, SAC ’12, pp. 119–125. ACM, New York (2012)
Minato, S.I.: Symmetric item set mining based on zero-suppressed Bdds. In: Todorovski, L., Lavrac, N., Jantke, K.P. (eds.) Discovery Science, Lecture Notes in Computer Science, vol. 4265, pp. 321–326. Springer (2006)
Minato, S.I., Uno, T., Arimura, H.: Fast generation of very large-scale frequent itemsets using a compact graph-based representation (2007)
Murtagh, F., Contreras, P.: Hierarchical clustering for finding symmetries and other patterns in massive, high dimensional datasets (2010). CoRR arXiv:1005.2638
Pei, J., Han, J., Lakshmanan, L.V.S.: Pushing convertible constraints in frequent itemset mining. Data Min. Knowl. Disc. 8(3), 227–252 (2004)
Puget, J.F.: On the satisfiability of symmetrical constrained satisfaction problems. In: Kamorowski, J., Ras, Z.W. (eds.) Proceedings of ISMIS’93, LNAI 689, pp. 350–361 (1993)
Raedt, L.D., Guns, T., Nijssen, S.: Constraintprogrammingfor itemsetmining. In: KDD, pp. 204–212 (2008)
Raedt, L.D., Guns, T., Nijssen, S.: Constraint programming for data mining and machine learning. In: AAAI (2010)
Tiwari, A., Gupta, R., Agrawal, D.: A survey on frequent pattern mining: current status and challenging issues. Inform. Technol. J. 9, 1278–1293 (2010)
Tseitin, G.S.: On the complexity of derivation in propositional calculus. In: Structures in the Constructive Mathematics and Mathematical Logic, pp. 115–125. H.A.O Shsenko (1968)
Uno, T., Asai, T., Uchida, Y., Arimura, H.: Lcm: an efficient algorithm for enumerating frequent closed item sets. In: Proceedings of Workshop on Frequent Itemset Mining Implementations (FIMI 03) (2003)
Uno, T., Kiyomi, M., Arimura, H.: Lcm Ver. 2: efficient mining algorithms for frequent/closed/maximal itemsets. In: FIMI (2004)
Vanetik, N.: Mining graphs with constraints on symmetry and diameter. In: Shen, H.T., Pei, J., Zsu, M.T., Zou, L., Lu, J., Ling, T.W., Yu, G., Zhuang, Y., Shao, J. (eds.) WAIM Workshops, Lecture Notes in Computer Science, vol. 6185, pp. 1–12. Springer (2010)
Zaki, M.J., Hsiao, C.J.: Efficient algorithms for mining closed itemsets and their lattice structure. IEEE Trans. Knowl. Data Eng. 17(4), 462–478 (2005)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Benhamou, B. Local and global symmetry breaking in itemset mining. Ann Math Artif Intell 80, 91–112 (2017). https://doi.org/10.1007/s10472-016-9528-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-016-9528-4