DYN-mRI: Thuật toán khai thác nhanh tập hiếm tối thiểu với ngưỡng phổ biến động

Bài viết này đề xuất thuật toán nhanh khai thác tập hiếm tối thiểu với ngưỡng phổ biến tối thiểu động. Kết quả thực nghiệm trên bộ dữ liệu thực và giả lập, cho thấy thuật toán đề xuất nhanh hơn so với thuật toán hiện hành.
Nội dung trích xuất từ tài liệu:
DYN-mRI: Thuật toán khai thác nhanh tập hiếm tối thiểu với ngưỡng phổ biến động Phan Thành Huấn 191 DYN-mRI: Thuật toán khai thác nhanh tập hiếm tối thiểu với ngưỡng phổ biến động Phan Thành Huấn1,2 1 Bộ môn Tin học, Đại học Khoa học Xã hội và Nhân văn, Đại học Quốc gia, Tp. Hồ Chí Minh 2 Khoa Toán -Tin học, Đại học Khoa học Tự nhiên, Đại học Quốc gia, Tp. Hồ Chí Minh huanphan@hcmussh.edu.vn Tóm tắt. Trong khai thác dữ liệu, khai thác tập hiếm là một kỹ thuật khai thác rất quan trọng với các ứng dụng tiềm năng như phát hiện các cuộc tấn công máy tính, giao dịch gian lận trong các tổ chức tài chính, tin sinh học, y tế. Trong bài viết này, chúng tôi đề xuất thuật toán nhanh khai thác tập hiếm tối thiểu với ngưỡng phổ biến tối thiểu động. Kết quả thực nghiệm trên bộ dữ liệu thực và giả lập, cho thấy thuật toán đề xuất nhanh hơn so với thuật toán hiện hành. Từ khóa: Luật Kết Hợp, Tập Hiếm Tối Thiểu, Ngưỡng Phổ Biến Động. 1 Giới thiệu Thuật toán khai thác luật kết hợp truyền thống [1-3] chỉ dùng một giá trị ngưỡng phổ biến tối thiểu minsup với ngầm định là các mặt hàng có cùng tính chất và tần số trong dữ liệu, điều này không thực tế. Trong kinh doanh bán lẻ, thường các mặt hàng thiết yếu, hàng tiêu dùng và các sản phẩm giá rẻ được mua nhiều hơn, trong khi các mặt hàng xa xỉ và các sản phẩm giá trị cao lại ít được mua (tập hiếm). Nếu chọn minsup quá cao thì các mặt hàng được khai thác thông thường có giá thành thấp và mang lại lợi nhuận không cao cho doanh nghiệp. Ngược lại, nếu chọn minsup quá thấp thì các mặt hàng được khai thác quá lớn, điều này làm cho doanh nghiệp khó khăn khi ra quyết định kinh doanh. Từ đó, có nhiều thuật toán khai thác tập hiếm được đề xuất như Apriori-Inverse, ARIMA, Rarity, Walky-G. Các thuật toán này dựa trên Apriori [4- 6], Eclat [7] và có nhiều hạn chế như quét dữ liệu nhiều lần, sử dụng nhiều bộ nhớ, các chiến lược cắt tỉa (không tái sử dụng cho lần khai thác tiếp theo). Thuật toán NOV-mRI [8] được nhóm tác giả đề xuất hiệu quả hơn các thuật toán [5-7]. Tuy nhiên, thuật toán này vẫn chưa đáp ứng thực tế - khi cần khai thác tập hiếm thì người dùng có thể yêu cầu thực hiện khai thác tập hiếm thỏa ngưỡng minsup trong nhiều chuỗi thao tác liên tiếp khác nhau. Để đáp ứng thực tế, tác giả cải tiến thuật toán NOV-mRI khai thác nhanh tập hiếm tối thiểu khi thay đổi minsup được gọi là thuật toán DYN-mRI và không đọc lại dữ liệu cho nhiều lần khai thác kế tiếp. Trong phần 2, trình bày các khái niệm cơ bản về khai thác tập phổ biến, tập hiếm và tập hiếm tối thiểu. Phần 3, xây dựng thuật toán liên quan và thuật toán DYN-mRI khai thác tập hiếm tối thiểu với ngưỡng minsup động. Kết quả thực nghiệm được trình bày trong phần 4 và kết luận ở phần 5. 192 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA 2018 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC 2 Các vấn đề liên quan 2.1 Khai thác tập phổ biến Cho ???? = {????1 , ????2 , … ???????? } là tập gồm m mục hàng riêng biệt, mỗi mục hàng gọi là item. Tập các mục ???? = {????1 , ????2 , … ???????? }, ∀???????? ∈ ????(1 ≤ ???? ≤ ????) gọi là itemset, tập mục có k mục gọi là k-itemset. Ɗ là dữ liệu giao dịch, gồm n bản ghi phân biệt gọi là tập các giao dịch ???? = {????1 , ????2 , … ???????? }, mỗi giao dịch ???????? = {????????1 , ????????2 , … ???????????? }, ∀???????????? ∈ ????(1 ≤ ???????? ≤ ????). Định nghĩa 1: Độ phổ biến (support) của itemset ???? ⊆ ????, ký hiệu ????????????(????) là số giao dịch trong Ɗ có chứa X. Định nghĩa 2: Cho ???? ⊆ ????, X gọi là itemset phổ biến nếu ????????????(????) ≥ ????????????????????????, trong đó minsup là ngưỡng phổ biến tối thiểu. Cho dữ liệu giao dịch Ɗ trong Bảng 1. Bảng 1. Dữ liệu giao dịch ???? cho Ví dụ. Mã Tập mục hàng t1 A C E F t6 E t2 A C G t7 A B C E t3 E H t8 A C D t4 A C D F G t9 A B C E G t5 A C E G 10 A C E F G Dữ liệu giao dịch Ɗ trong Bảng 1, có 8 item riêng biệt I = {A, B, C, D, E, F, G, H} và 10 giao dịch T = {t1, t2, t3, t4, t5, t6, t7, t8, t9, t10}. 2.2 Khai thác tập hiếm và tập hiếm tối thiểu Trong thực tế, nhiều ứng dụng tiềm năng cần khai thác các tập hiếm như ứng dụng phát hiện các cuộc tấn công máy tính, giao dịch gian lận trong các tổ chức tài chính, tin sinh học, y tế,…. Dưới đây là các khái niệm liên quan đến tập hiếm: Định nghĩa 3: Cho X  I, X gọi là itemset hiếm – nếu sup(X) < minsup. Ký hiệu RI là tập hợp chứa các itemset hiếm. Định nghĩa 4: Cho X  I, X gọi là itemset hiếm tối thiểu – nếu X  RI và tất cả tập con thực sự của X là phổ biến. Ký hiệu mRI là tập chứa các itemset hiếm tối thiểu. Tính chất 1: ik  I, nếu sup(ik) < minsup thì ik  mRI. Bảng 2. Tập RI và mRI trên dữ liệu giao dịch ???? với minsup = 2. Tập RI Tập mRI k-itemset #RI = 26 #mRI = 5 1 H H, B, D 2 HE, DF, DG, BG FG, FE 3 BGE, BGA, BGC, DFG, DFA, DFC, DGA, DGC, GGE BGAC, BGEA, BGEC, DFAC, DGAC, DGEA, DGEC, 4 FGEA, FGEC 5 BGEAC, DFGAC, FGEAC Phan Thành Huấn 193 Bảng 2, cho thấy tập RI và mRI chứa k-itemset với minsup = 2. Số lượng |RI ...