Modified efficient high-utility itemset mining with multiple minimum utility

96 MODIFIED EFFICIENT HIGH-UTILITY ITEMSET MINING WITH MULTIPLE MINIMUM UTILITY Hoàng Ngọc Cương, Nguyễn Ngọc Thạch, Lê Thị Dung, Lê Quốc Đạt* Khoa Công nghệ Thông tin, Trường Đại học Công nghệ TP. Hồ Chí Minh GVHD: KS. Nguyễn Thanh Tùng TÓM TẮT Khai thác tập hạng mục có độ hữu ích cao (High Utility itemsets Mining- HUIM) là phương pháp phân tích hành vi của khách hàng. Các thuật toán HUIM có thể khai thác các tập mẫu có lợi nhất trong cơ sở dữ liệu giao dịch, cụ thể là các tập hạng mục có độ hữu ích cao (High Utility itemsets - HUI). Các thuật toán HUIM truyền thống đều bỏ qua việc mỗi vật phẩm sẽ có yêu cầu về mức độ hữu ích khác nhau. Trong nhiều cơ sở dữ liệu giao dịch trong thực tế, thông tin này được đưa ra tùy vào loại vật phẩm. Do đó áp dụng một ngưỡng cho tất cả vật phẩm là không hợp lý. Để tìm chính xác các hui từ cơ sở dữ liệu định lượng với đa ngưỡng, một thuật toán mới được gọi là MEHUI (Multiple Thresholds Efficient High-Utility Itemset Mining) được đề xuất, tích hợp tất cả các ưu điểm của thuật toán iMEFIM. Qua thực nghiệm có thể thấy rằng phương pháp bài nghiên cứu đưa ra có thể khai thác các HUI từ các giao dịch tại cửa hàng bán lẻ với hiệu quả cao. Từ khóa: cơ sở dữ liệu đa ngưỡng, cơ sở dữ liệu định lượng, khai thác dữ liệu, tập hạng mục có độ hữu ích cao, thuật toán MEHUI. 1 GIỚI THIỆU Bài toán khai thác tập hạng mục có độ hữu ích cao (High Utility itemsets - HUI) lần đầu tiên được đề xuất bởi H. Yao và cộng sự vào năm 2004 (Yao et al, 2004). Khai thác HUI nhằm mục đích khám phá các tập hạng mục có độ hữu ích cao trong cơ sở dữ liệu giao dịch. HUI sử dụng ngưỡng do người dùng chỉ định để lọc các tập hạng mục không thỏa mãn yêu cầu. Ngưỡng này được gọi là ngưỡng hữu ích tối thiểu và đại diện cho độ hữu ích thấp nhất mà mỗi tập hạng mục phải có để được xem là tập hạng mục có độ hữu ích cao. Bài toán khai thác tập hạng mục có độ hữu ích cao với nhiều ngưỡng độ hữu ích (Multiple threshold High Utility itemsets) lần đầu tiên được đề xuất vào năm 2008 (Lin, 2008). Các thuật toán HUIM truyền thống đều dùng một ngưỡng độ hữu ích cho tất cả các hạng mục. Tuy nhiên, trên thực tế thì mỗi mặt hàng đều có một ngưỡng độ hữu ích khác nhau do đó Multilple Thresholds HUI được sử dụng để khai thác các HUI bằng cách xem xét các ngưỡng hữu ích cho từng mặt hàng thay vì nhập một ngưỡng độ hữu ích duy nhất. Thuật toán MHUI (Multiple threshold High Utility itemsets) (Krishnamoorthy, 2018) được đề xuất bởi S. Krishnamoorthy đã giới thiệu phương pháp hiệu quả để khai thác các tập hạng mục có độ hữu ích cao với nhiều ngưỡng độ hữu ích tối thiểu. Thuật toán giới thiệu khái niệm về 97 hữu ích tối thiểu hậu tố và trình bày các chiến lược cắt tỉa để khai thác các tập hạng mục có độ hữu ích cao một cách hiệu quả dựa trên cấu trúc Utility-List. Thuật toán MHUI dựa trên thuật toán FHM (Faster High-Utility Itemset Mining) (Fournier- Viger et al, 2014) do đó thuật toán vẫn tiêu tốn nhiều thời gian và bộ nhớ để lưu trữ thông tin về Utility-List của mỗi tập hạng mục. Để giải quyết vấn đề này, bài nghiên cứu đề xuất thuật toán mới có tên MEHUI (Multiple thresholds Efficient High-Utility Itemset Mining) cho việc khai thác HUI với nhiều ngưỡng hữu ích tối thiểu. 2 THUẬT TOÁN Đầu vào của thuật toán MEHUI bao gồm một cơ sở dữ liệu giao dịch , một cơ sở dữ liệu giao dịch bao gồm một tập các giao dịch . Trong mỗi giao dịch có thông tin các hạng mục có trong giao dịch cũng như các giá trị về số lượng của hạng mục đó trong giao dịch được ký hiệu là ( ). Mỗi hạng mục sẽ mang lại một độ hữu ích tương ứng được ký hiệu là ( ). Độ hữu ích của một hạng mục trong một giao dịch được ký hiệu là ( ) và được tính bằng công thức ( ) ( ) ( ) . Độ hữu ích của một tập hạng mục trong giao dịch được tính bằng ( ) ∑ ( ) Độ hữu ích của một tập hạng mục trong cơ sở dữ liệu được tính bằng công thức ( ) ∑ ( ) . Trong bài toán khai thác tập hạng mục có độ hữu ích cao đa ngưỡng thì mỗi hạng mục được đặt một giá trị ngưỡng yêu cầu khác nhau được ký hiệu là ( ), và được tập hợp trong một danh sách được ký hiệu là . Một tập hạng mục có một giá trị ngưỡng được ký hiệu là ( ) và được xác định bằng công thức ( ) ( ) (Krishnamoorthy, 2018). Một tập hạng mục được gọi là tập hạng mục có độ hữu ích cao là tập hạng mục có độ hữu ích ( ) ( ). Thuật toán MEHUI sử dụng hai giới hạn dựa trên độ hữu ích, đó là độ hữu ích cục bộ (local utility - ) và độ hữu ích cây con (sub-tree utility - ) để cắt tỉa không gian tìm kiếm, cộng thêm hai kỹ thuật mới và hiệu quả để giảm chi phí quét cơ sở dữ liệu là phép chiếu cơ sở dữ liệu có độ hữu ích cao và hợp nhất giao dịch có độ hữu ích cao đã được trình bày ở thuật toán EFIM (A Fast and Memory Efficient algorithm for high-utility itemset Mining) (Zida et al, 2017). Song song với đó thuật toán sử dụng cấu trúc chiếu ngược P-set được đề xuất ở thuật toán iMEFIM (Nguyen et al, 2019). Tuy nhiên hai thuật toán EFIM và iMEFIM chưa giải quyết được vấn đề khai thác tập hạng mục độ hữu ích cao với đa ngưỡng độ hữu ích. Do đó, thuật toán MEHUI sẽ sử dụng giá trị ngưỡng độ hữu ích hậu tố như một giá trị ước lượng ngưỡng tối thiểu mà tập hạng mục có thể nhận bằng cách tính toán giá trị ngưỡng độ hữu ích nhỏ nhất của các giá trị có thể mở rộng từ tập hạng mục và đặt giá trị đó làm ngưỡng độ hữu ích hậu tố. Độ hữu ích hậu tố của tập hạng mục được ký hiệu là ( ) và được xác định ( ) ( ( ) ( ( ))) (Krishnamoorthy, 2018), trong đó ( ) là tập hạng mục có thể kết hợp với để tạo ra tập hạng mục là ứng viên có thể là HUI. Thuật toán MEHUI sẽ so sánh giá trị độ hữu ích cục bộ và độ hữu ích cây con với giá trị ( ) để cắt tỉa không gian tìm kiếm thay vì so sánh các giá trị này với giá trị ngưỡng cố định như các thuật toán truyền thống. Thuật toán sử dụng phép chiếu ngược P-set để tránh quét các giao dịch thừa không có chứa hạng mục cần tính toán, giúp giảm số lần tìm kiếm 98 hạng mục cần tìm trong mỗi giao dịch giúp thuật toán chạy tốt hơn trên các cơ sở dữ liệu thưa thớt. Mã giả thuật toán MEHUI Input: Database , set of items , MMU Output: High utility itemsets 1. 2. Scan to calculate ( ) for all item 3. ( ) ( ) ( ) 4. Sort ( ) in ascending order of ( ) values; 5. Scan to remove each item ( ) from all transactions. Then remove empty transactions; 6. Sort each transaction in ascending order according of ( )values when read backward; 7. Scan to calculate ( ) and ( ) for each item ( ); 8. ( ) ( ) ( ) ( ) 9. ( ( ) ( ) ( )) Procedure: Search Input: Itemset , database , primary items ( ) secondary items ( ) minimum utility threshold , the extensions of the projection ( ) Output: High utility itemsets found by appending items to . 1. 2. Foreach item ( ) do 3. 4. Scan in ( ) to calculate ( ) and construct // using transaction merging 5. if ( ) ( ) then 6. Scan to calculate ( ) ( ) and ( for all ( ) after 7. ( ) ( ) ( ) ( ) 8. ( ) ( ) ( ) ( ) 9. ( ( ) ( ) ( )) 10. End 11. Return HUIList. 99 Mô tả thuật toán MEHUI Thuật toán 1 nhận đầu vào là một cơ sở dữ liệu , tập các hạng mục và dữ liệu MMU. Thuật toán cho ra các tập hữu ích cao thỏa ngưỡng . Đầu tiên, khởi tạo . Sau đó, quét cơ sở dữ liệu và sử dụng utilityBinArray (mảng chứa độ hữu ích) để tính ( ), cho mỗi hạng mục (dòng #2). Tiếp theo, xây dựng tập hạng mục phụ thuộc ( ) (dòng #3). Sắp xếp tăng dần các hạng mục có chứa trong tập phụ thuộc theo giá trị của ( ) (dòng #4). Sau đó, quét để loại bỏ các hạng mục không thuộc ( ) và các giao dịch rỗng (dòng #5). Dòng #6, sắp xếp các giao dịch từ dưới lên theo giá trị của ( ). Tiếp theo tại dòng #7, quét , sử dụng utilityBinArray để tính ( ) và sử dụng phép chiếu cơ sở dữ liệu để giữ lại các hạng mục thuộc ( ). Sau đó tại dòng #8, xây dựng hạng mục căn bản ( ). Tại dòng #9 là quy trình tìm kiếm theo chiều sâu để duyệt đệ quy mở rộng các hạng mục ban đầu để tìm tất cả HUI (thuật toán 2). Thuật toán 2 nhận đầu vào là , tập hạng mục , tập ( ), tập ( ), dữ liệu , và các tập mở rộng của các . Và cho đầu ra là tất cả các tập hữu ích cao được tìm thấy thì thêm các hạng mục vào sau . Đầu tiên, khởi tạo danh sách HUI rỗng (dòng #1). Từ dòng #2 đến dòng #10 là vòng lặp để kiểm tra tất cả các tập mở rộng bằng một hạng mục ( ) vào ngay sau (dòng #3) được tập mục mới . Tiếp theo, quét tính ( ) và sử dụng phép gom giao dịch đc cơ cở dữ liệu mới (dòng #4). Tại dòng #5, nếu ( ) ( ) thì . Dòng #6, quét cơ sở dữ liệu và sử dụng utilityBinArray để tính ( ) ( ). Sau đó, xây dựng tập ( ) (dòng #7) và ( ) (dòng #8). Sau đó tại dòng #10, thuật toán SEARCH sau đó được gọi đệ quy để tiếp tục khám phá không gian tìm kiếm để mở rộng . Để tìm ra các tập HUI. 3 THỰC NGHIỆM Hai thuật toán được chạy thực nghiệm trên PC có cấu hình Intel Core I3-9400F, 16GB RAM chạy trên hệ điều hành Windows 10 pro và sử dụng Java JDK 8. Cơ sở dữ liệu được lấy trên website mã nguồn mở spmf1. Bảng 1. Thông tin cơ sở dữ liệu Dataset Số Lượng giao dịch Số Lượng hạng mục Độ dài Trung Bình BMS 59601 497 4.8 Chess 3196 75 37 Thuật toán sử dụng chỉ số GLMU để so sánh tốc độ của hai thuật toán MEHUI và MHUI do MHUI là thuật toán mới nhất đã được công bố trên tạp chí quốc tế về khai thác tập hạng 1 https://www.philippe-fournier-viger.com/spmf/index.php?link=datasets.php 100 mục có độ hữu ích cao đa ngưỡng. Với GLMU là một giá trị truyền vào do người dùng như một ngưỡng chặn dưới của các giá trị MU, khi đó MU sẽ được tính bởi công thức ( ) ( ( ) ) với là giá trị hằng số do người dùng nhập vào với mỗi cơ sở dữ liệu. Hình 1. So sánh bộ nhớ và thời gian trên cơ sở dữ liệu BMS Hình 2. So sánh bộ nhớ và thời gian trên cơ sở dữ liệu Chess Kết quả được thể hiện từ Hình 1 đến 4. Từ kết quả có thể thấy rằng thuật toán MEHUI chiếm ưu thế hơn so với thuật toán MHUI về thời gian thực hiện trong tất cả các bài kiểm tra. Trong mọi tập dữ liệu, khi ngưỡng GLMU càng được tăng lên thì thời gian chạy của thuật toán cũng giảm đi rất nhiều. Thuật toán MEHUI nhanh hơn đáng kể so với thuật toán MHUI trên CSDL BMS (100 lần Hình 1) và CSDL Chess (6 lần Hình 3). Một lý do khác khiến MEHUI đạt được tốc độ tăng đáng kể là vì MEHUI mở rộng khuôn khổ của thuật toán iMEFIM, một thuật toán hiệu quả cho HUIM. Sử dụng các giới hạn trên hiệu quả cao để loại bỏ các ứng cử viên từ iMEFIM, MEHUI sử dụng các chiến lược gộp giao dịch giống nhau, phép chiếu ngược P- set giúp giảm quá trình quét cơ sở dữ liệu cũng như hai độ đo chặt chẽ hơn so với độ đo độ hữu ích còn lại của thuật toán MHUI. 4 KẾT LUẬN Khai thác các tập hạng mục hữu ích cao với nhiều ngưỡng tiện ích là một trong những các giải pháp hữu ích có ý nghĩa thiết thực. Phương pháp mới này hỗ trợ người ra quyết định loại bỏ các hạng mục hiếm. Tuy nhiên, việc khai thác hiệu quả các HUI trong giải pháp mới này là khá thách thức. Bài báo này nhằm giải quyết các thách thức đó và đã thiết kế, phát triển phương pháp khai thác HUI một cách vượt trội. Chúng tôi đã trình bày thuật toán 101 MEHUI và xem xét trên nhiều mức tối thiểu các giá trị tiện ích để cải thiện hơn nữa về hiệu suất cho quá trình khai thác HUI. Chúng tôi sử dụng cấu trúc P-set để giảm số lượng giao dịch được quét và giảm chi phí quét cơ sở dữ liệu. Ngoài ra, chúng tôi cũng đánh giá thực nghiệm rộng rãi trên các cơ sở dữ liệu khác nhau cho thấy rằng MEHUI hiệu quả hơn về mặt cả thời gian chạy và sử dụng bộ nhớ so với các thuật toán đã được thử nghiệm trước đó. Trong công việc tương lai, chúng tôi dự định áp dụng thuật toán trên các tập đóng, tập tối đại và triển khai thuật toán hoạt động trên môi trường song song để có thể tận dụng lợi thế của đa ngưỡng hoặc để hoạt động trên cơ sở dữ liệu rất lớn. TÀI LIỆU THAM KHẢO [1] Fournier-Viger P, Wu C-W, Zida S, Tseng VS (2014) FHM: Faster High-Utility Itemset Mining Using Estimated Utility Co-occurrence Pruning. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8502 LNAI: 83–92. [2] Krishnamoorthy S (2018) Efficient mining of high utility itemsets with multiple minimum utility thresholds. Eng. Appl. Artif. Intell. 69: 112–126. [3] Lin JC-W, Gan W, Fournier-Viger P, Hong TP (2008) Mining High-Utility Itemsets with Multiple Minimum Utility Thresholds. Proceedings of the Eighth International C* Conference on Computer Science & Software Engineering - C3S2E ’15: 9–17. [4] Nguyen LTT, Nguyen P, Nguyen TDD., Vo B, Fournier-Viger P, Tseng VS (2019) Mining high-utility itemsets in dynamic profit databases. Knowledge-Based Syst 175: 130–144. [5] Yao H, Hamilton HJ, Butz CJ (2004) A Foundational Approach to Mining Itemset Utilities from Databases. Proceedings of the 2004 SIAM International Conference on Data Mining 4: 482–486. [6] Zida S, Fournier-Viger P, Lin JC-W., Wu C-W, Tseng VS (2017) EFIM: a fast and memory efficient algorithm for high-utility itemset mining,” Knowl. Inf. Syst 51: 595–625.