Maximum frequent pattern generation from a large database of transactions and items for association rule mining is an important research topic in data mining. Association rule mining aims to discover interesting correlations, frequent patterns, associations, or causal structures between items hidden in a large database. By exploiting quantum computing, we propose an efficient quantum search algorithm design to discover the maximum frequent patterns. We modified Grover’s search algorithm so that a subspace of arbitrary symmetric states is used instead of the whole search space. We presented a novel quantum oracle design that employs a quantum counter to count the maximum frequent items and a quantum comparator to check with a minimum support threshold. The proposed derived algorithm increases the rate of the correct solutions since the search is only in a subspace. Furthermore, our algorithm significantly scales and optimizes the required number of qubits in design, which directly reflected positively on the performance. Our proposed design can accommodate more transactions and items and still have a good performance with a small number of qubits.
References
[1]
Wittek, P. (2014) Quantum Machine Learning: What Quantum Computing Means to Data Mining. Academic Press, Cambridge.
[2]
Zhao, Q. and Bhowmick, S.S. (2003) Association Rule Mining: A Survey. Nanyang Technological University, Singapore, 135.
[3]
Kaur, M. and Kang, S. (2016) Market Basket Analysis: Identify the Changing Trends of Market Data Using Association Rule Mining. Procedia Computer Science, 85, 78-85. https://doi.org/10.1016/j.procs.2016.05.180
[4]
Ünvan, Y.A. (2021) Market Basket Analysis with Association Rules. Communications in Statistics-Theory and Methods, 50, 1615-1628. https://doi.org/10.1080/03610926.2020.1716255
[5]
Yi, K., Chen, T. and Cong, G. (2018) Library Personalized Recommendation Service Method Based on Improved Association Rules. Library Hi Tech, 36, 443-457. https://doi.org/10.1108/LHT-06-2017-0120
[6]
Lin, W., Alvarez, S.A. and Ruiz, C. (2002) Efficient Adaptive-Support Association Rule Mining for Recommender Systems. Data Mining and Knowledge Discovery, 6, 83-105. https://doi.org/10.1023/A:1013284820704
[7]
Jooa, J., Bangb, S. and Parka, G. (2016) Implementation of a Recommendation System Using Association Rules and Collaborative Filtering. Procedia Computer Science, 91, 944-952. https://doi.org/10.1016/j.procs.2016.07.115
[8]
Langhnoja, S.G., Barot, M.P. and Mehta, D.B. (2013) Web Usage Mining Using Association Rule Mining on Clustered Data for Pattern Discovery. International Journal of Data Mining Techniques and Applications, 2, 141-150.
[9]
Singh, A.K., Kumar, A. and Maurya, A.K. (2014) Association Rule Mining for Web Usage Data to Improve Websites. 2014 International Conference on Advances in Engineering & Technology Research (ICAETR-2014), Unnao, 1-2 August 2014, 1-6.
[10]
Naulaerts, S., Meysman, P., Bittremieux, W., Vu, T.N., Vanden Berghe, W., Goethals, B. and Laukens, K. (2015) A Primer to Frequent Itemset Mining for Bioinformatics. Briefings in Bioinformatics, 16, 216-231. https://doi.org/10.1093/bib/bbt074
[11]
Rajak, A. and Gupta, M.K. (2008) Association Rule Mining: Applications in Various Areas. Proceedings of International Conference on Data Management, Ghaziabad, India, 3-7.
[12]
Agrawal, R., Imieliński, T. and Swami, A. (1993) Mining Association Rules between Sets of Items in Large Databases. ACM SIGMOD Record, 22, 207-216. https://doi.org/10.1145/170036.170072
[13]
Han, J., Kamber, M. and Pei, J. (2011) Data Mining: Concepts and Techniques. 3rd Edition, University of Illinois at Urbana-Champaign Micheline Kamber Jian Pei Simon Fraser University.
[14]
Agrawal, R. and Srikant, R. (1994) Fast Algorithms for Mining Association Rules. Proceedings of the 20th International Conference on Very Large Data Bases, San Francisco, 12-15 September 1994, 487-499.
[15]
Xie, H. (2021) Research and Case Analysis of Apriori Algorithm Based on Mining Frequent Item-Sets. Open Journal of Social Sciences, 9, 458-468. https://doi.org/10.4236/jss.2021.94034
[16]
Liu, H. and Wang, B. (2007) An Association Rule Mining Algorithm Based on a Boolean Matrix. Data Science Journal, 6, S559-S565. https://doi.org/10.2481/dsj.6.S559
[17]
Park, J.S., Chen, M.S. and Yu, P.S. (1995) An Effective Hash-Based Algorithm for Mining Association Rules. ACM SIGMOD Record, 24, 175-186. https://doi.org/10.1145/568271.223813
[18]
Savasere, A., Omiecinski, E.R. and Navathe, S.B. (1995) An Efficient Algorithm for Mining Association Rules in Large Databases. Georgia Institute of Technology, Atlanta.
[19]
Akash, M.B., Mandal, I. and Al Mamun, M.S. (2023) Backward Support Computation Method for Positive and Negative Frequent Itemset Mining. Journal of Data Analysis and Information Processing, 11, 37-48. https://doi.org/10.4236/jdaip.2023.111003
[20]
Yu, C.-H., Gao, F., Wang, Q.-L. and Wen, Q.-Y. (2016) Quantum Algorithm for Association Rules Mining. Physical Review A, 94, Article ID: 042311. https://doi.org/10.1103/PhysRevA.94.042311
[21]
Yu, C.H. (2022) Experimental Implementation of Quantum Algorithm for Association Rules Mining. ArXiv Preprint ArXiv: 2204.13634
[22]
Nielsen, M.A. and Chuang, I.L. (2002) Quantum Computation and Quantum Information; Cambridge University Press, Cambridge.
[23]
Bärtschi, A. and Eidenbenz, S. (2019) Deterministic Preparation of Dicke States. In: Gąsieniec, L., Jansson, J. and Levcopoulos, C., Eds., Fundamentals of Computation Theory. FCT 2019. Lecture Notes in Computer Science, Vol. 11651, Springer, Cham, 126-139. https://doi.org/10.1007/978-3-030-25027-0_9
[24]
Alasow, A., Jin, P. and Perkowski, M. (2022) Quantum Algorithm for Variant Maximum Satisfiability. Entropy, 24, Article No. 1615. https://doi.org/10.3390/e24111615
[25]
Alasow, A. and Perkowski, M. (2022) Quantum Algorithm for Maximum Satisfiability. 2022 IEEE 52nd International Symposium on Multiple-Valued Logic (ISMVL), Dallas, 18-20 May 2022, 27-34. https://doi.org/10.1109/ISMVL52857.2022.00012
[26]
Aleksandrowicz, G., Alexander, T., Barkoutsos, P., Bello, L., Ben-Haim, Y., Bucher, D., Cabrera-Hernández, F.J., Carballo-Franquis, J., Chen, A., Chen, C.F., et al. (2019) Qiskit: An Open-Source Framework for Quantum Computing. Zenodo, Honolulu.
[27]
Canteaut, A. and Videau, M. (2005) Symmetric Boolean Functions. IEEE Transactions on Information Theory, 51, 2791-2811. https://doi.org/10.1109/TIT.2005.851743
[28]
Wong, T.G. (2016) Quantum Walk Search on Johnson Graphs. Journal of Physics A: Mathematical and Theoretical, 49, Article ID: 195303. https://doi.org/10.1088/1751-8113/49/19/195303
[29]
Peres, A. (1985) Reversible Logic and Quantum Computers. Physical Review A, 32, 3266-3276. https://doi.org/10.1103/PhysRevA.32.3266
[30]
Perkowski, M. (2020) Inverse Problems, Constraint Satisfaction, Reversible Logic, Invertible Logic and Grover Quantum Oracles for Practical Problems. In: Lanese, I. and Rawski, M., Eds., Reversible Computation. RC 2020. Lecture Notes in Computer Science, Vol. 12227, Springer, Cham, 3-32. https://doi.org/10.1007/978-3-030-52482-1_1
[31]
Collins, H. and Easterly, K. (2021) IBM Unveils Breakthrough 127-Qubit Quantum Processor. https://newsroom.ibm.com/2021-11-16-IBM-Unveils-Breakthrough-127-Qubit-Quantum-Processor
