FGenHUSM: Một thuật toán hiệu quả khai thác các chuỗi sinh phổ biến lợi ích cao
Abstract
Khai thác các chuỗi phổ biến và các chuỗi lợi ích cao có mức độ quan trọng khác nhau trong các ứng dụng thực tế. Gần đây, các nghiên cứu tập trung giải quyết bài toán tổng quát hơn, là khai thác tập FHUS chuỗi phổ biến lợi ích cao. Tuy nhiên, thời gian và bộ nhớ dùng để khai thác FHUS vẫn còn quá lớn. Bài báo đề xuất khái niệm tập FGHUS các chuỗi sinh phổ biến lợi ích cao, là một biểu diễn súc tích của FHUS, và một thuật toán mới hiệu quả để khai thác nó. Dựa vào hai chặn trên của độ đo lợi ích, hai chiến lược tỉa theo chiều rộng và sâu được thiết kế để loại bỏ nhanh các chuỗi ít phổ biến hoặc lợi ích thấp. Sử dụng một chặn dưới mới của lợi ích, một chiến lược tỉa địa phương mới được đề xuất để loại bỏ sớm các chuỗi không là chuỗi sinh phổ biến lợi ích cao. Dựa vào các chiến lược này, một thuật toán mới FGenHUSM được thiết kế để khai thác FGHUS mà tính hiệu quả của nó được thể hiện qua các thử nghiệm trên các cơ sở dữ liệu lớn.
References
C. F. Ahmed, S. K. Tanbeer, and B.-S. Jeong, “Mining high utility web access sequences in dynamic web log data,” in 11th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, 2010, pp. 76–81.
B.-E. Shie, H.-F. Hsiao, V. S. Tseng, and S. Y. Philip, “Mining high utility mobile sequential patterns in mobile commerce environments,” in International Conf. Database Systems for Advanced Applications, 2011, pp. 224–238.
M. Zihayat, H. Davoudi, and A. An, “Top-k utility-based gene regulation sequential pattern discovery,” in IEEE International Conference on Bioinformatics and Biomedicine, 2016, pp. 266–273.
C. F. Ahmed, S. K. Tanbeer, and B.-S. Jeong, “A novel approach for mining high-utility sequential patterns in sequence databases,” ETRI Journal, vol. 32, no. 5, pp. 676–686, 2010.
J.Yin,Z.Zheng,andL.Cao,“USpan: An efficient algorithm for mining high utility sequential patterns,”in ACM/SIGKDD Int’l Conf. Knowl. Disc. Data Mining, 2012, pp. 660–668.
J. C.-W. Lin, J. Zhang, and P. Fournier-Viger, “High-utility sequential pattern mining with multiple minimum utility thresholds,” in Asia-Pacific Web and Web-Age Infor. Management Joint Conf. Web and Big Data, 2017, pp. 215–229.
T. Truong, A. Tran, H. Duong, B. Le, and P. Fournier-Viger, “EHUSM: Mining high utility sequences with a pessimistic utility model,” 1st Int’l Work. Utility-Driven Mining, 2018.
T. C. Tin, T. N. Anh, D. Van Hai, and L. H. Bac, “HUPSMT: An efficient algorithm for mining high utility-probability sequences in uncertain databases with multiple minimum utility thresholds,” Journal of Computer Science and Cybernetics, vol. 35, no. 1, pp. 1–20, 2019.
T. Truong-Chi and P. Fournier-Viger, “A survey of high utility sequential pattern mining,” in High-Utility Pattern Mining, P. Fournier-Viger, J. Lin, R. Nkambou, B. Vo, and V. Tseng, Eds. Springer, 2019, pp. 97–129.
W. Gan, J. C.-W. Lin, J. Zhang, H.-C. Chao, H. Fujita, and S. Y. Philip, “ProUM: Projection-based utility mining on sequence data,” Info. Sciences, vol. 513, pp. 222–240, 2020.
X. Yan, J. Han, and R. Afshar, “CloSpan: Mining closed sequential patterns in large datasets,” in SIAM International Conference on Data Mining, 2003, pp. 166–177.
B. Le, H. Duong, T. Truong, and P. Fournier-Viger, “FCloSM, FGenSM: Two efficient algorithms for mining frequent closed and generator sequences using the local pruning strategy,” Knowledge and Information Systems, vol. 53, no. 1, pp. 71–107, 2017.
T. Truong, H. Duong, B. Le, and P. Fournier-Viger, “FMaxCloHUSM: An efficient algorithm for mining frequent closed and maximal high utility sequences,” Eng. Applications of Artificial Intelligence, vol. 85, pp. 1–20, 2019.
L. Szathmary, P. Valtchev, A. Napoli, and R. Godin, “Efficient vertical mining of frequent closures and generators,” in Int’l Symp. Intelligent Data Analysis, 2009, pp. 393–404.
A. Tran, T. Truong, and B. Le, “Simultaneous mining of frequent closed itemsets and their generators: Foundation and algorithm,” Engineering Applications of Artificial Intelligence, vol. 36, pp. 64–80, 2014.
P. Fournier-Viger, C.-W. Wu, and V. S. Tseng, “Novel concise representations of high utility itemsets using generator patterns,” in International Conference on Advanced Data Mining and Applications, 2014, pp. 30–43.
P. Fournier-Viger, A. Gomariz, M. ˇSebek, and M. Hlosta, “VGEN: Fast vertical mining of sequential generator patterns,” in International Conference on Data Warehousing and Knowledge Discovery, 2014, pp. 476–488.
H. Duong, T. Truong, and B. Le, “Efficient algorithms for simultaneously mining concise representations of sequential patterns based on extended pruning conditions,” Eng. Applications of Artificial Intelligence, vol. 67, pp. 197–210, 2018.
P. D. Gr¨unwald, I. J. Myung, and M. A. Pitt, Advances in minimum description length: Theory and applications. MIT press, 2005.
M.-T. Tran, B. Le, B. Vo, and T.-P. Hong, “Mining non-redundant sequential rules with dynamic bit vectors and pruning techniques,” Applied Intelligence, vol. 45, no. 2, pp. 333–342, 2016.
P. Fournier-Viger, A. Gomariz, T. Gueniche, A. Soltani, C.W. Wu, and V. S. Tseng, “SPMF: A Java open-source pattern mining library,” The Journal of Machine Learning Research, vol. 15, no. 1, pp. 3389–3393, 2014.