Khai thác tập hữu ích cao tương quan với ràng buộc chiều dài

Vấn đề khai thác tập hữu ích cao tương quan (Correlated Hight Utility Itemset - CoHUI) trong cơ sở dữ liệu giao dịch đã có nhiều nghiên cứu được đề xuất nhằm trích xuất tri thức từ hành vi mua hàng của người dùng. Bài viết đề xuất thuật toán CHL (Correlated High Utility Itemset with Length constraint) để khai thác tập hữu ích cao tương quan trên cơ sở dữ liệu giao dịch với ràng buộc chiều dài.
Nội dung trích xuất từ tài liệu:
Khai thác tập hữu ích cao tương quan với ràng buộc chiều dài Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIV về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), TP. HCM, ngày 23-24/12/2021 DOI: 10.15625/vap.2021.0079 KHAI THÁC TẬP HỮU ÍCH CAO TƯƠNG QUAN VỚI RÀNG BUỘC CHIỀU DÀI Nguyễn Văn Lễ1, Trần Văn Thọ1, Phạm Tuấn Khiêm1, Nguyễn Văn Hoàng2 1 Trường Đại học Công nghiệp thực phẩm TP. Hồ Chí Minh 2 Trường Đại học Văn Lang lenv@hufi.edu.vn, thotv@hufi.edu.vn, khiempt@hufi.edu.vn, hoang.nv@vlu.edu.vn TÓM TẮT: Vấn đề khai thác tập hữu ích cao tương quan (Correlated Hight Utility Itemset - CoHUI) trong cơ sở dữ liệu giao dịch đã có nhiều nghiên cứu được đề xuất nhằm trích xuất tri thức từ hành vi mua hàng của người dùng. Tuy nhiên, kết quả khai thác được có nhiều tập với số lượng mặt hàng lớn sẽ gây khó khăn cho việc phân tích và quyết định trong kinh doanh thay vì xem xét trên các tập kết quả với số lượng mặt hàng ít hơn. Do đó ràng buộc chiều dài được bổ sung trong quá trình khai thác, nhưng mới chỉ dừng lại trong việc khai thác tập hữu ích cao mà chưa xem xét cho việc khai thác tập hữu ích cao có tương quan. Trong bài báo này, chúng tôi đề xuất thuật toán CHL (Correlated High Utility Itemset with Length constraint) để khai thác tập hữu ích cao tương quan trên cơ sở dữ liệu giao dịch với ràng buộc chiều dài. Kết quả thử nghiệm trên các cơ sở dữ liệu Chess, Mushroom, Accident, Kosarak, Retail, Chainstore cho thấy thuật toán CHL có hiệu suất thực thi hiệu quả hơn so với thuật toán so sánh CoUPM về thời gian thực thi và bộ nhớ sử dụng, đặc biệt là các cơ sở dữ liệu thưa. Từ khóa: Tập hữu ích cao, tính tương quan, ràng buộc chiều dài, tập hữu ích cao có tương quan, khai thác dữ liệu. I. GIỚI THIỆU Khai thác các tập hữu ích cao (High Utility Itemsets - HUI) trên cơ sở dữ liệu giao dịch là bài toán phổ biến và có nhiều ứng dụng trong thực tế. Các thuật toán khai thác tập hữu ích cao đề cập đến việc khám phá các tập mặt hàng có độ hữu ích cao so với ngưỡng độ hữu ích cho trước. Một số thuật toán điển hình về khai thác tập hữu ích cao như: UP-Grown [1], Two-Phase [2], HUI-Miner [3], FHM [4], EFIM [5], HMiner [6]. Năm 2016, Fournier-Viger và cộng sự [7] đề xuất thuật toán FHM+ bổ sung thêm ràng buộc chiều dài để tối ưu tập kết quả. Một hạn chế quan trọng của các thuật toán khai thác tập hữu ích cao là chỉ sử dụng độ đo lợi nhuận để đánh giá mức độ hữu ích của các tập mặt hàng. Điều này dẫn đến kết quả khai thác có nhiều tập mặt hàng mang lại lợi nhuận cao nhưng giữa các mặt hàng trong tập lại có mối tương quan yếu. Những tập mặt hàng này kém ý nghĩa trong vấn đề phân tích kinh doanh. Từ đó, bài toán mới đặt ra là cần tìm ra các tập mặt hàng vừa có độ hữu ích cao và vừa có tính tương quan giữa các phần tử trong tập. Có nhiều nghiên cứu được đề xuất để giải quyết vấn đề này như thuật toán FCHM được đề xuất bởi Fournier-Viger và cộng sự [8]. Cùng giải quyết vấn đề này, J. C. W. Lin và cộng sự đã đề xuất thuật toán FDHUP [9] để khai thác HUI có ràng buộc tần suất cao. Sau đó, vào năm 2017, W. Gan và cộng sự đề xuất thuật toán CoHUIM [10] xem xét cả tính tương quan và lợi nhuận giữa các mặt hàng trong giao dịch. Tuy nhiên, thuật toán này sinh ra số lượng lớn các ứng viên và việc quét lại cơ sở dữ liệu gốc nhiều lần làm tăng đáng kể thời gian thực thi và bộ nhớ sử dụng. Tiếp sau đó, vào năm 2019, W. Gan và cộng sự đề xuất thuật toán CoUPM [11] có hiệu suất thực thi tốt hơn thuật toán CoHUIM. Trong bài báo này, chúng tôi đề xuất thuật toán CHL để khai thác tập hữu ích cao tương quan với ràng buộc chiều dài của tập mục. Việc bổ sung thêm ngưỡng chiều dài tập mục vào khai thác giúp cho thuật toán CHL đạt hiệu quả cao. Những đóng góp chính của bài báo: 1) Đề xuất thuật toán CHL sử dụng ràng buộc chiều dài tập mục trong việc khai thác tập hữu ích cao tương quan trên cơ sở dữ liệu giao dịch. 2) Áp dụng các chiến lược tỉa hiệu quả như U-Prune, LA-Prune, EUCS-Prune và Kulc-Prune làm tăng hiệu suất thực thi của thuật toán. 3) Thực nghiệm trên các nhóm cơ sở dữ liệu dày và thưa cho thấy thuật toán CHL có hiệu suất thực thi cao hơn thuật toán CoUPM ở thời gian thực thi và bộ nhớ sử dụng. Cấu trúc bài báo được chia làm 6 phần: Phần I trình bày giới thiệu; Phần II trình bày các công trình liên quan; Phần III trình bày các định nghĩa và ký hiệu; Phần IV trình bày thuật toán đề xuất CHL; Phần V trình bày kết quả thực nghiệm và đánh giá; Phần VI trình bày kết luận và hướng phát triển. II. CÁC CÔNG TRÌNH LIÊN QUAN Gần đây, bài toán khai thác tập hữu ích cao (High Utility Itemset - HUI) đã được nghiên cứu và ứng dụng rộng rãi, đặc biệt là trong lĩnh vực kinh doanh. Vào năm 2005, Liu và cộng sự đề xuất thuật toán Two-phase [2] nhằm khai thác tập hữu ích cao trên cơ sở dữ liệu giao dịch. Thuật toán thực hiện trên 2 pha, pha đầu tìm kiếm các ứng viên tiềm năng, pha 2 thực hiện quét lại cơ sở dữ liệu nhiều lần để xác định ứng viên nào thực sự là tập hữu ích cao. Dựa trên cách tiếp cận này, một số thuật toán khác được đề xuất để nâng cao hiệu quả khai thác HUI như: CTU-Mine [12], UP- Grown [1],UP-Grown+ [13]. Phương pháp 2 pha tuy giải quyết được bài toán khai thác tập hữu ích cao nhưng tỏ ra kém hiệu quả khi thực hiện trên 2 giai đoạn độc lập dẫn đến tốn nhiều thời gian và bộ nhớ. Để giải quyết vấn đề này, 374 KHAI THÁC TẬP HỮU ÍCH CAO TƯƠNG QUAN VỚI RÀNG BUỘC CHIỀU DÀI năm 2012, Liu và cộng sự đề xuất cấu trúc dữ liệu mới là danh sách Utility-List với thuật toán HUI-Miner [3]. Thuật toán được thiết kế để thực hiện trên 1 pha thực thi nên đã tăng hiệu suất ...