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

  • Trương Tín Chí Trường Đại học Đà Lạt
  • Trần Ngọc Anh Trường Đại học Đà Lạt
  • Dương Văn Hải Trường Đại học Đà Lạt
  • Lê Hoài Bắc Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Tp. Hồ Chí Minh
Keywords: Chuỗi lợi ích cao, khai thác chuỗi sinh phổ biến lợi ích cao, chặn trên và chặn dưới của độ đo lợi ích

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.

Author Biographies

Trương Tín Chí, Trường Đại học Đà Lạt

Trương Chí Tín là giảng viên tại Khoa Toán – Tin học, Trường Đại học Đà Lạt. Tác giả tốt nghiệp Cử nhân Toán tại Trường Đại học Đà Lạt năm 1983 và nhận bằng Tiến sĩ về Điều khiển tối ưu ngẫu nhiên năm 1990 tại Đại học Quốc gia Hà Nội. Hướng nghiên cứu hiện nay của tác giả là trí tuệ nhân tạo và khai thác dữ liệu.

Trần Ngọc Anh, Trường Đại học Đà Lạt

Trần Ngọc Anh đang giảng dạy và nghiên cứu tại Khoa Toán – Tin học, Trường Đại học Đà Lạt. Tác giả tốt nghiệp Đại học ngành Toán – Tin học vào năm 1999 tại Đại học Đà Lạt, nhận bằng Thạc sĩ và Tiến sĩ về Khoa học máy tính vào các năm 2004 và 2016 tại Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Tp. Hồ Chí Minh. Tác giả đang nghiên cứu về khai thác dữ liệu và trí tuệ nhân tạo.

Dương Văn Hải, Trường Đại học Đà Lạt

Dương Văn Hải tốt nghiệp Trường Đại học Đà Lạt ngành Tin học năm 2004. Tác giả tốt nghiệp Cao học ngành Công nghệ thông tin năm 2009 và đang là Nghiên cứu sinh tại Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Tp. Hồ Chí Minh. Tác giả hiện đang giảng dạy và nghiên cứu về khai thác dữ liệu tại Khoa Toán – Tin học, Trường Đại học Đà Lạt.

Lê Hoài Bắc, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Tp. Hồ Chí Minh

Lê Hoài Bắc nhận bằng Cử nhân Toán năm 1984, Cao học Khoa học máy tính năm 1990 và hoàn thành Luận án Tiến sĩ về Đảm bảo Toán học cho máy tính năm 2000 tại Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Tp. Hồ Chí Minh. Tác giả hiện là giảng viên tại Khoa Công nghệ Thông tin, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Tp. Hồ Chí Minh và đang nghiên cứu về trí tuệ nhân tạo, tính toán mềm, khai thác dữ liệu và khoa học dữ liệu.

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.

Published
2019-12-31
Section
Bài báo