Fhurim: Thuật toán khai phá tập mục hữu ích cao hiếm

dựng các utility-list của các tập mở rộng của Px (tập mở rộng là tập ). Gọi đệ quy thuật toán FHURIM_Miner để xác định tập mục hữu ích cao cho các tập mở rộng của Px Sau đây là thuật toán FHURI được viết dưới dạng mã giả: Thuật toán FHURIM Vào: D: CSDL Giao tác; ngưỡng hữu ích tối thiểu; ngưỡng hỗ trợ cực đại. Ra: HURIs: Tập gồm các tập mục hữu ích cao hiếm. 1. ; 2. ; Thuật toán FHURIM_Initial Vào: D: CSDL Giao tác; ngưỡng hữu ích tối thiểu; Ra: : Tập gồm các mục có trọng số hữu ích lớn hơn hoặc bằng và được sắp xếp theo thứ tự tăng dần của trọng số hữu ích của các mục; ULs: tập các utility_list của các mục đơn trong ; EUCS: Chứa dữ liệu theo cấu trúc EUCS; 1. ) 2. Tính ; 3. Xác định tập { }; 4. Sắp xếp lại thứ tự của các mục trong { } ( ) ; 5. ){ Huỳnh Triệu Vỹ, Lê Quốc Hải, Trương Ngọc Châu 165 6. Xây dựng tập ULs gồm các utility-list của các mục ; 7. Xây dựng cấu trúc EUCS 8. } Thuật toán FHURIM_Miner Vào: P.UL: Utility-list của tập mục P; ULs: tập các utility-list của các tập mục mở rộng của P; ngưỡng hữu ích tối thiểu; ngưỡng hỗ trợ cực đại; : cấu trúc EUCS; Ra: HURIs: Tập gồm các tập mục hữu ích cao hiếm; 1. { 2. { } 3. { 4. { };//tập các utility-list của các tập mở rộng của Px 5. 6. 7. 8. ; 9. } 10. } B. Kết quả thực nghiệm Mô tả CSDL: Các cơ sở dữ liệu liệu chạy thực nghiệm chúng tôi sử dụng CSDL được công bố tại [15], chi tiết về các CSDL này được mô tả trong Bảng 5. Bảng 5. Mô tả tập CSDL thực nghiệm Databases #|D| #|I| #AvgLen #MaxLen Foodmart 4.141 1.559 4,0 11 Mushroom 8.124 119 23 23 Chú thích: #|D|: Tổng số giao tác; #|I|: Tổng số mục trong CSDL; #AvgLen: Độ dài trung bình của giao tác trong CSDL; #MaxLen: Độ dài cực đại của giao tác trong CSDL. Mô tả hệ thống máy tính: CPU Core I5 2.4GHz, RAM 8GB, Windows 10. Kết quả thực nghiệm: Chúng tôi so sánh thời gian thực thi giữa thuật toán FHURIM với thuật toán Up-Rare Growth trên CSDL được mô tả trong Bảng 5. Kết quả thực nghiệm cho thấy thuật toán FHURIM có thời gian thực thi nhanh hơn nhiều lần so với thuật toán Up-Rare Growth. Bởi vì thuật toán UP-Rare Growth dựa trên cấu trúc UP-Tree để tính toán độ phổ biến và giá trị hữu ích của tập mục cùng nhau và áp dụng chiến lược tỉa không gian tìm kiếm tương tự như thuật toán UP-Growth. Tuy nhiên, nhược điểm của UP-Tree là tốn nhiều thời gian và bộ nhớ để xây dựng cấu trúc UP-Tree, đặc biệt khi ngưỡng hữu ích tối thiểu thấp và CSDL chứa mẫu dài và dày vì thuật toán chỉ tỉa các mục đơn có TWU nhỏ hơn ngưỡng hữu ích tối thiểu và độ hỗ trợ của tập mục chỉ được tính khi toàn bộ dữ liệu được thêm vào cây UP-Tree. Còn đối với thuật toán FHURIM sử dụng cấu trúc utility-list và EUCS để tính toán giá trị hữu ích và độ phổ biến của các tập mục (từ utility-list của mục đơn được khởi tạo ban đầu) mà không cần quét lại CSDL, đồng thời trên 2 cấu trúc này cũng chứa thông tin heuristic để tỉa không gian tìm kiếm hiệu quả. Hình 5 biểu diễn thời gian thực thi giữa hai thuật toán Up-Rare Growth và FHURIM trên CSDL Foodmart và Mushroom với các ngưỡng hỗ trợ cực đại và ngưỡng hữu ích tối thiểu khác nhau. 0 300 600 900 1200 1500 0.024 0.048 0.072 0.096 R u n t im e s( m s) Max Support Foodmart (Min Utility=560) UP-Rare Growth FHURIM 0 300 600 900 1200 1500 0.024 0.048 0.072 0.096 R u n t im e s( m s) Max Support Foodmart (Min Utility=600) UP-Rare Growth FHURIM 166 FHURIM: THUẬT TOÁN KHAI PHÁ TẬP MỤC HỮU ÍCH CAO HIẾM Hình 5. Kết quả so sánh thời gian thực thi của thuật toán Up-Rare Growth so với FHURIM trên CSDL Foodmart và Mushroom IV. KẾT LUẬN Khai phá tập mục hữu ích cao hiếm là một mở rộng của bài toán khai phá tập mục hữu ích cao nhằm mục đích tìm ra trong CSDL liệu giao tác tất cả tập mục hữu ích cao nhưng không phổ biến trong CSDL. Trong bài báo này chúng tôi đề xuất thuật toán có tên gọi là FHURIM để khai phá nhanh tập mục hữu ích cao hiếm mà không cần trải qua pha sinh tập ứng viên dựa trên cấu trúc utility-list và chiến lược tỉa EUCS. Chúng tôi chạy thực nghiệm trên 2 CSDL thực với các trường hợp khác nhau về ngưỡng hữu ích tối thiểu và ngưỡng hỗ trợ cực đại, kết quả cho thấy thuật toán của chúng tôi nhanh hơn thuật toán hiện tại. TÀI LIỆU THAM KHẢO [1] R. Agrawal, T. Imieliński, and A. Swami, "Mining association rules between sets of items in large databases," in Acm sigmod record, 1993, pp. 207-216. [2] N. Bloom, R. Sadun, and J. V. Reenen, "The organization of firms across countries," The Quarterly Journal of Economics, vol. 7, pp. 1663-1705, 2012. [3] H. Yao, H. J. Hamilton, and C. J. Butz, "A foundational approach to mining itemset utilities from databases," in Proceedings of the 2004 SIAM International Conference on Data Mining, 2004, pp. 482-486. [4] Q. H. Duong, P. Fournier-Viger, H. Ramampiaro, K. Nørvåg, and T. L. Dam, "Efficient high utility itemset mining using buffered utility-lists," Applied Intelligence, vol. 48, pp. 1859-1877, 2018. [5] A. Erwin, R. P. Gopalan, and N. Achuthan, "Efficient mining of high utility itemsets from large datasets," in Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2008, pp. 554-561. [6] P. Fournier-Viger, C. W. Wu, S. Zida, and V. S. Tseng, "FHM: Faster high-utility itemset mining using estimated utility co-occurrence pruning," in International symposium on methodologies for intelligent systems, 2014, pp. 83- 92. [7] M. Liu and J. Qu, "Mining high utility itemsets without candidate generation," in Proceedings of the 21st ACM international conference on Information and knowledge management, 2012, pp. 55-64. [8] Y. Liu, W. K. Liao, and A. Choudhary, "A fast high utility itemsets mining algorithm," in Proceedings of the 1st international workshop on Utility-based data mining, 2005, pp. 90-99. [9] V. S. Tseng, C. W. Wu, B. E. Shie, and P. S. Yu, "UP-Growth: an efficient algorithm for high utility itemset mining," in Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, 2010, pp. 253-262. [10] H. Yao and H. J. Hamilton, "Mining itemset utilities from transaction databases," Data & Knowledge Engineering, vol. 59, pp. 603-626, 2006. [11] S. Zida, P. Fournier-Viger, J. C. W. Lin, C. W. Wu, and V. S. Tseng, "EFIM: a fast and memory efficient algorithm for high-utility itemset mining," Knowledge and Information Systems, vol. 51, pp. 595-625, 2017. [12] J. Pillai, O. Vyas, and M. Muyeba, "Huri–a novel algorithm for mining high utility rare itemsets," in Advances in Computing and Information Technology, ed: Springer, 2013, pp. 531-540. [13] V. Goyal, S. Dawar, and A. Sureka, "High utility rare itemset mining over transaction databases," in International Workshop on Databases in Networked Information Systems, 2015, pp. 27-40. [14] J. Pillai, O. Vyas, and M. K. Muyeba, "A Fuzzy Algorithm for Mining High Utility Rare Itemsets-FHURI," International Journal on Recent Trends in Engineering & Technology, vol. 10, p. 1, 2014. [15] P. Fournier-Viger. (2019). An Open-Source Data Mining Library. Available: viger.com/spmf/index.php?link=datasets.php 3500 18500 33500 48500 63500 78500 93500 25 30 35 40 R u n t im e s( m s) Max Support Mushroom (Min Utility=8050000) UP-Rare Growth FHURIM 3500 18500 33500 48500 63500 78500 93500 25 30 35 40 R u n t im e s( m s) Max Support Mushroom (Min Utility=8080000) UP-Rare Growth FHURIM Huỳnh Triệu Vỹ, Lê Quốc Hải, Trương Ngọc Châu 167 FHURIM: HIGH UTILITY RARE ITEMSETS MINING ALGORITHM Huynh Trieu Vy, Le Quoc Hai, Truong Ngoc Chau ABSTRACT: Mining rare high utility itemsets aims at discovering the itemsets such that their support are under maximal support threshold and no less than minimal utility threshold given by users. The Two-phase rare high utility itemset mining algorithms require high running time. Especially, at the high maximal support threshold, the set of candidate itemsets is very large. In order to overcome this drawback, this paper proposes the rare high utility itemset mining algorithm without generating candidate itemsets. The utility-list structure is applied to store utility and support value of itemsets and for effectively pruning searching space. The experiment results indicate that the proposed algorithm is better than the state-of-the-art.