Thuật toán song song khai thác nhanh các mẫu trọng số hữu ích phổ biến từ cơ sở dữ liệu định lượng động
A Parallel Algorithm for Fast Mining Frequent Weighted Ultility Patterns from Dynamic Quantitative Databases
Abstract
Trong những năm gần đây, bài toán khai thác các mẫu trọng số hữu ích phổ biến (FWUP) đang được quan tâm nghiên cứu. Đây là một là một biến thể của bài toán khai thác mẫu. Một số phương pháp giải quyết khá hiệu quả bài toán này đã được đề xuất. Tuy nhiên, trong thực tế, khi dữ liệu có kích thước lớn và trọng số các mục thường xuyên thay đổi dẫn đến các thuật toán xử lý tốn nhiều thời gian trong quá trình khai thác mẫu. Nếu tận dụng khả năng tính toán song song của các hệ thống tính toán, hoặc của các bộ vi xử lý đa lõi (multi-core) thì có thể cải thiện được thời gian tính toán của các thuật toán. Trong bài báo này chúng tôi giới thiệu một giải pháp song song hoạt động trên bộ xử lý đa lõi, đặt tên là pdFWUNL, để khai thác các mẫu trọng số hữu ích phổ biến từ cơ sở dữ liệu định lượng động có trọng số các mục thay đổi. Kết quả thực nghiệm cho thấy thời gian khai thác mẫu của thuật toán song song pdFWUNL của chúng tôi hiệu quả hơn phương pháp tuần tự tốt nhất hiện có.
References
R. Agrawal, T. Imielinski, and A. Swami, “Mining association rules between sets of items in large databases,” vol. 22. ACM, 1993, pp. 207–216.
M. S. Khan, M. Muyeba, and F. Coenen, “A weighted utility framework for mining association rules.” IEEE, 2008, pp. 87–92.
B. Vo, B. Le, and J. J. Jung, “A tree-based approach for mining frequent weighted utility itemsets.” Springer, 2012, pp. 114–123.
N. D. Ham, V. D. Bay, N. T. H. Minh, and T.-P. Hong, “Mbis: an efficient method for mining frequent weighted utility itemsets from quantitative databases,” Journal of Computer Science and Cybernetics, vol. 31, no. 1, pp. 17–30, 2015.
H. Bui, B. Vo, and H. Nguyen, “Wun-miner: A new method for mining frequent weighted utility itemsets.” IEEE, 2016, pp. 001 365–001 370.
H. Nguyen, N. Le, H. Bui, and T. Le, “A new approach for efficiently mining frequent weighted utility patterns,” Applied Intelligence, vol. 53, no. 1, pp. 121–140, 1/2023.
H. Nguyen, N. Le, H. Bui, and T. Le, “Mining frequent weighted utility patterns with dynamic weighted
items from quantitative databases,” Applied Intelligence, 3/2023, [Online; accessed 2023-06-15]. [Online]. Available: https://link.springer.com/10.1007/s10489-023-04554-z
H. Yao, H. J. Hamilton, and C. J. Butz, “A foundational approach to mining itemset utilities from databases.” SIAM, 2004, pp. 482–486.
Y. Liu, W.-k. Liao, and A. Choudhary, “A two-phase algorithm for fast discovery of high utility itemsets.” Springer, 2005, pp. 689–695.
V. S. Tseng, B.-E. Shie, C.-W. Wu, and S. Y. Philip, “Efficient algorithms for mining high utility itemsets from transactional databases,” IEEE transactions on knowledge and data engineering, vol. 25, no. 8, pp. 1772–1786, 2012.
M. Liu and J. Qu, “Mining high utility itemsets without candidate generation,” 2012, pp. 55–64.
S. Zida, P. Fournier-Viger, J. C.-W. Lin, C.-W. Wu, and V. S. Tseng, “Efim: a highly efficient algorithm for high-utility itemset mining.” Springer, 2015, pp. 530–546.
L. T. Nguyen, V. V. Vu, M. T. Lam, T. T. Duong, L. T. Manh, T. T. Nguyen, B. Vo, and H. Fujita, “An efficient method for mining high utility closed itemsets,” Information Sciences, vol. 495, pp. 78–99, 8 2019.
S. Krishnamoorthy, “Mining top-k high utility itemsets with effective threshold raising strategies,” Expert Systems with Applications, vol. 117, pp. 148–165, 3 2019.
H. Kim, U. Yun, Y. Baek, J. Kim, B. Vo, E. Yoon, and H. Fujita, “Efficient list based mining of high average utility patterns with maximum average pruning strategies,” Information Sciences, vol. 543, pp. 85–105, 1 2021.
U. Huynh, B. Le, D.-T. Dinh, and H. Fujita, “Multi-core parallel algorithms for hiding high-utility sequential patterns,” Knowledge-Based Systems, vol. 237, p. 107793, 2 2022.
H. M. Huynh, L. T. Nguyen, B. Vo, Z. K. Oplatková, P. Fournier-Viger, and U. Yun, “An efficient parallel algorithm for mining weighted clickstream patterns,” Information Sciences, vol. 582, pp. 349–368, 1 2022.
S. Kumar and K. K. Mohbey, “A review on big data based parallel and distributed approaches of pattern mining,” Journal of King Saud University - Computer and Information Sciences, vol. 34, no. 5, pp. 1639–1662, 5 2022.
Z. Deng, Z. Wang, and J. Jiang, “A new algorithm for fast mining frequent itemsets using n-lists,” Science China Information Sciences, vol. 55, pp. 2008–2030, 2012.
R. Rymon, “Search through systematic set enumeration,” in Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning, 1992, pp. 539–550.
“Spmf: A java open-source data mining library, retrieved from http://www.philippe-fournierviger.com/spmf/index.php?link=datasets.php (accessed: 20 august 2020).”
