Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phá vỡ đối xứng địa phương và toàn cục trong khai thác tập mục
Tóm tắt
Khái niệm đối xứng đã được nghiên cứu rộng rãi trong lĩnh vực lập trình ràng buộc và trong khả năng thỏa mãn mệnh đề. Nhiều phương pháp để phát hiện và loại bỏ những đối xứng này đã được phát triển, và việc sử dụng chúng trong các trình giải đã biết trong các lĩnh vực này đã cải thiện đáng kể khả năng hiệu quả trên một loạt các vấn đề được coi là khó giải quyết. Khái niệm đối xứng có thể được xuất khẩu sang các lĩnh vực khác mà một số cấu trúc có thể được khai thác một cách hiệu quả. Đặc biệt, trong lĩnh vực khai thác dữ liệu mà một số nhiệm vụ có thể được diễn tả dưới dạng các ràng buộc hoặc công thức logic. Chúng tôi quan tâm đến việc phát hiện và loại bỏ các đối xứng địa phương và toàn cục trong vấn đề khai thác tập mục. Các công trình gần đây đã cung cấp các mã hóa hiệu quả dưới dạng các ràng buộc Boolean cho các nhiệm vụ khai thác dữ liệu này và một số ý tưởng về loại bỏ đối xứng trong lĩnh vực này đã bắt đầu xuất hiện, nhưng vẫn còn ít và các kỹ thuật được trình bày thường tập trung vào đối xứng toàn cục, được phát hiện và loại bỏ tĩnh trong giai đoạn tiền xử lý. Trong công việc này, chúng tôi nghiên cứu khái niệm đối xứng địa phương và so sánh nó với đối xứng toàn cục cho vấn đề khai thác tập mục. Chúng tôi chỉ ra cách phát hiện các đối xứng địa phương của mã hóa Boolean một cách động và đưa ra một số thuộc tính cho phép loại bỏ những đối xứng này trong các trình giải khai thác tập mục dựa trên SAT nhằm tăng cường hiệu suất của chúng.
Từ khóa
#đối xứng địa phương #đối xứng toàn cục #khai thác tập mục #lập trình ràng buộc #khả năng thỏa mãn mệnh đềTài liệu tham khảo
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)