Đề xuất bài toán khai thác tập phổ biến tuyệt đối trên dữ liệu giao dịch có trọng số của items

Trong bài viết này, nhóm tác giả đề xuất bài toán khai thác tập phổ biến tuyệt đối trên dữ liệu giao dịch có trọng số của items và tiếp cận theo hướng không thỏa tính chất bao đóng giảm. Đây là tập itemset phổ biến có tất cả các itemset con đều phổ biến - giúp giai đoạn khai thác luật kết hợp nhanh và hiệu quả trên dữ liệu giao dịch có trọng số của items.
Nội dung trích xuất từ tài liệu:
Đề xuất bài toán khai thác tập phổ biến tuyệt đối trên dữ liệu giao dịch có trọng số của items 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.0070 ĐỀ XUẤT BÀI TOÁN KHAI THÁC TẬP PHỔ BIẾN TUYỆT ĐỐI TRÊN DỮ LIỆU GIAO DỊCH CÓ TRỌNG SỐ CỦA ITEMS Phan Thành Huấn1,3, Lê Hoài Bắc2,3 Khoa Toán - Tin học, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia TP. Hồ Chí Minh 1 2 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 3 Đại học Quốc gia TP. Hồ Chí Minh huanphan@hcmussh.edu.vn, lhbac@fithcmus.edu.vn TÓM TẮT: Trong bài viết này, nhóm tác giả đề xuất bài toán khai thác tập phổ biến tuyệt đối trên dữ liệu giao dịch có trọng số của items và tiếp cận theo hướng không thỏa tính chất bao đóng giảm. Đây là tập itemset phổ biến có tất cả các itemset con đều phổ biến - giúp giai đoạn khai thác luật kết hợp nhanh và hiệu quả trên dữ liệu giao dịch có trọng số của items. Để giải quyết bài toán trên, nhóm tác giả sử dụng cách tiếp cận đơn giản dựa theo thuật toán AprioriTID và kết hợp biểu diễn dạng bit - cải tiến thành thuật toán có tên gọi là AprioriTID-PFWI. Nhóm tác giả tiến hành thực nghiệm thuật toán trên bộ dữ liệu thực của UCI và bộ dữ liệu giả lập của trung tâm nghiên cứu IBM Almaden, cho thấy bài toán đề xuất là khả thi cùng thuật toán cải tiến hiệu quả. Từ khóa: Khai thác luật kết hợp, tập phổ biến tuyệt đối có trọng số, thuật toán AprioriTID-PFWI. I. GIỚI THIỆU Năm 1993, R. Agrawal cùng đồng sự đề xuất mô hình cơ bản khai thác luật kết hợp từ dữ liệu giao dịch (DLGD) truyền thống (mức độ quan trọng hay mức ý nghĩa của các thuộc tính là như nhau - thuộc tính không có trọng số) theo hai pha [1]: Pha 1: Tìm tất cả các kết hợp thỏa ngưỡng phổ biến tối thiểu minsup (sinh tập phổ biến FI - Frequent Itemset); Pha 2: Sinh luật kết hợp lần lượt từ các kết hợp thỏa minsup ở pha 1 và các luật kết hợp này phải thỏa ngưỡng tin cậy tối thiểu minconf. Lúc này, luật kết hợp chỉ có một thuộc tính ở vế phải (X → ik: X là tập gồm nhiều thuộc tính, ik là một thuộc tính đơn). Trong năm tiếp theo, R. Agrawal cùng đồng sự tiếp tục mở rộng mô hình khai thác luật kết hợp tổng quát (X→ Y với X, Y là kết hợp phổ biến gồm nhiều thuộc tính) và đề xuất thuật toán Apriori, AprioriTID [2] khai thác tập phổ biến trên dữ liệu giao dịch không trọng số. Sau đó, nhiều nhà nghiên cứu tập trung đề xuất các cấu trúc dữ liệu lưu trữ phù hợp cùng với chiến lược rút gọn không gian sinh dựa vào tính chất bao đóng giảm (DCP - Downward Closure Property) của các kết hợp. Phần lớn các đề xuất khai thác luật kết hợp tập trung nâng cao hiệu năng khai thác tập phổ biến ở Pha 1. Vào những năm cuối của thế kỷ XX, cùng với sự phát triển đa dạng các dữ liệu giao dịch và kế thừa từ bài toán khai thác tập phổ biến truyền thống của R. Agrawal; G. D. Ramkumar cùng đồng sự đã đề xuất thuật toán WIS [3] khai thác tập phổ biến có trọng số của các thuộc tính (mức độ quan trọng/mức ý nghĩa của các thuộc tính là khác nhau) chứa nhiều tri thức hơn so với khai thác tập phổ biến truyền thống. Từ đấy, có rất nhiều nhà nghiên cứu tập trung đề xuất các thuật toán khai thác tập phổ biến trên DLGD có trọng số của các thuộc tính. Theo công trình [12], nhóm tác giả khảo sát các nghiên cứu liên quan đến bài toán khai thác tập phổ biến trên DLGD có trọng số của của các thuộc tính, gồm hai hướng tiếp cận chính: - Hướng tiếp cận thỏa tính chất bao đóng giảm hay còn gọi là tính chất Apriori (chiếm tỷ lệ 90% nghiên cứu): một số thuật toán điển hình như WIS [3] của nhóm G. D. Ramkumar, WARM [5] của nhóm F. Tao, MINWAL [4] của nhóm C. H. Cai, WFIM [6] của nhóm U. Yun, FWI [10] của nhóm G. Lee, SWFP [11] của nhóm X. Zhao,... - Hướng tiếp cận không thỏa tính chất bao đóng giảm (chiếm tỷ lệ 10% nghiên cứu): không gian sinh gia tăng đáng kể, đây là hướng nghiên cứu đầy thách thức; có ba nhóm nghiên cứu - năm 2011, nhóm Z. Huai đề xuất thuật toán WHIUA [7]; năm 2013, nhóm G. C. Lan đề xuất thuật toán PWA [8] và sau đó có nhiều cải tiến; năm 2015, nhóm X.Wei đề xuất thuật toán IWFPM [9]. Tuy nhiên, các thuật toán này đều tiếp cận dựa trên thuật toán Apriori [2] do R. Agrawal cùng đồng sự đề xuất vào năm 1994, đây là thuật toán có nhiều trích dẫn và cải tiến cũng như ứng dụng trên nhiều loại dữ liệu khác nhau trong gần suốt 30 năm qua. Nhóm tác giả nhận thấy rằng: Đối với hướng tiếp cận không thỏa tính chất bao đóng giảm thì khi sinh luật kết hợp từ tập phổ biến ở Pha 1 sẽ xuất hiện các luật kết hợp X → Y với X là kết hợp không phổ biến và Y là kết hợp phổ biến hoặc ngược lại, điều này sẽ làm tốn nhiều thời gian loại bỏ các luật ở dạng trên. Vì lẽ đó, nhóm tác giả đã đề xuất bài toán khai thác tập phổ biến tuyệt đối trên DLGD có trọng số của các thuộc tính - tất cả tập con đều phổ biến. Phan Thành Huấn, Lê Hoài Bắc 283 Để minh họa cho bài toán đề xuất là khả thi, nhóm tác giả chọn thuật toán AprioriTID cho việc cải tiến và kết hợp biểu diễn DLGD dạng bit thành thuật toán AprioriTID-PFWI khai thác nhanh tập phổ biến tuyệt đối trên dữ liệu giao dịch có trọng số của các thuộc tính và theo hướng tiếp cận không thỏa tính chất bao đóng giảm. Trong Phần II, bài báo trình bày các khái niệm cơ bản về khai thác tập phổ biến không trọng số, tập phổ biến và tập phổ biến tuyệt đối ...