Đề 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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

19
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề 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 trên DLGD có trọng số của các thuộc tính. Phần III, trình bày thuật toán AprioriTID khai thác tập phổ biến và thuật toán cải tiến AprioriTID-PFWI cho khai thác tập phổ biến tuyệt đối có trọng số. Kết quả thực nghiệm được trình bày trong Phần IV và kết luận ở Phần V. II. CÁC VẤN ĐỀ LIÊN QUAN A. Khai thác luật kết hợp không trọng số Cho I = {i1, i2,..., im} là tập gồm m thuộc tính, mỗi thuộc tính gọi là item. Tập các item X ={i1, i2,..., ik}, ∀ij ∈ I (1≤ j ≤ k) gọi là itemset, itemset có k item 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 T = {t1, t2,..., tn}, mỗi giao dịch tk ={ik1, ik2,..., ikm}, ikj ∈ I (1≤ kj ≤ m). Định nghĩa 1: Cho X, Y ⊆ I với X ∩ Y = ∅, luật kết hợp là một mệnh đề kéo theo có dạng X → Y, thỏa hai ngưỡng độ đo cho trước (minsup - độ phổ biến tối thiểu; minconf - độ tin cậy tối thiểu), trong đó X gọi là tiền đề và Y là kết luận. Định nghĩa 2: Độ phổ biến (support) của itemset X ⊆ I, ký hiệu sup(X) - tỷ lệ giữa số giao dịch trong Ɗ có chứa X và n giao dịch. sup( X ) = {t ∈ D | X ⊆ t} n (1) Định nghĩa 3: Độ phổ biến của luật kết hợp X → Y, ký hiệu sup(X → Y) - tỷ lệ giữa số giao dịch trong Ɗ chứa {X ∪ Y} và n giao dịch. sup( X → Y ) = sup( X ∪ Y ) (2) Định nghĩa 4: Độ tin cậy (confidence) của luật kết hợp X → Y, ký hiệu conf(X → Y) - tỷ lệ giữa số giao dịch chứa {X ∪ Y} và số giao dịch chứa X trong Ɗ. conf ( X → Y ) = sup( X ∪ Y ) sup( X ) (3) Định nghĩa 5: Cho X ⊆ I, X gọi là itemset phổ biến nếu sup(X) ≥ minsup, trong đó minsup là ngưỡng phổ biến tối thiểu. Ký hiệu FI là tập hợp các itemset phổ biến. Các tính chất bao đóng giảm trong khai thác tập phổ biến trên DLGD: Tính chất 1: ∀ X ⊆ Y: sup(X) ≥ sup(Y); Tính chất 2: ∀ X ⊂ Y, sup(Y) ≥ minsup: sup(X) ≥ minsup; Tính chất 3: ∀ X ⊂ Y, sup(X) < minsup: sup(Y) < minsup. Cho dữ liệu giao dịch Ɗ trong Bảng 1. Bảng 1. Dữ liệu giao dịch Ɗ cho các ví dụ b) Dữ liệu giao dịch dạng bit và có thứ tự theo a) Dữ liệu giao dịch ban đầu; số lượng item trên mỗi giao dịch TID Items TID Items |t| t1 A C E F t6 0 0 0 0 1 0 0 0 1 t2 A C t2 1 0 1 0 0 0 0 0 2 t3 E H t3 0 0 0 0 1 0 0 1 2 t4 A C D F G t5 1 0 1 0 1 0 0 0 3 t5 A C E t8 1 0 1 1 0 0 0 0 3 t6 E t9 1 0 1 0 1 0 0 0 3 t7 A B C E t1 1 0 1 0 1 1 0 0 4 t8 A C D t7 1 1 1 0 1 0 0 0 4 t9 A C E t4 1 0 1 1 0 1 1 0 5 t10 A C E F G t10 1 0 1 0 1 1 1 0 5 (|t|: số lượng item có trong giao dịch t)
284 ĐỀ 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 ITEMS Ví dụ 1: 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} với giá trị ngưỡng minsup = 0,20, ta có: Xét itemset X ={A, C, E}, sup({A,C,E}) = 0,50 ≥ minsup, ta nói: ”X ={A, C, E} phổ biến với minsup = 0,20”; Theo tính chất 1 thì các tập con của X ={A, C, E} có độ phổ biến lớn hơn hoặc bằng 0,50 - độ phổ biến lần lượt của các tập con của X: sup({A}) = 0,80; sup({C}) = 0,80; sup({E}) = 0,70; sup({A, C}); sup({A, E}) = 0,50; sup({C, E}) = 0,50. Theo tính chất 2 thì các tập con của X ={A, C, E} cũng phổ biến; ta thấy độ phổ biến của các tập con của X đều lớn hơn hoặc bằng ngưỡng minsup. Theo tính chất 3, Y = {H} thì sup({H}) = 0,10 < minsup, ta nói: ”Y = {H} itemset không phổ biến ngưỡng minsup = 0,20”. Khi đó, các tập cha của Y cũng không phổ biến, nghĩa là Z = {E, H} cũng itemset không phổ biến, với sup({E, H}) = 0,10 < minsup = 0,20. Mã giả thuật toán. Khai thác luật kết hợp Đầu vào: Dữ liệu giao dịch Ɗ, minsup, minconf Đầu ra: Tập luật kết hợp thỏa minsup, minconf 1: FI = {∅}//tập chứa các kết hợp - Pha 1 2: Forall Z ∈ Ƥ≥1(I) do 3: If (sup(Z) ≥ minsup) then 4: FI = FI ∪ Z 5: AR = {∅}//tập chứa luật kết hợp - Pha 2 6: Forall fi ∈ FI do 7: Forall X ∈ Ƥ1≤k
Phan Thành Huấn, Lê Hoài Bắc 285 Định nghĩa 6: Cho X ⊆ I, trọng số của itemset X được tính w(X)=Max(wi1, wi2,..., wik), ∀ ij ∈X (1≤ j≤ k). Định nghĩa 7: Cho X ⊆ I, trọng số phổ biến của itemset X được tính ws(X)= w(X)×sup(X). Định nghĩa 8: Cho X ⊆ I, X gọi là itemset phổ biến nếu ws(X) ≥ minwsup, trong đó minwsup là ngưỡng trọng số phổ biến tối thiểu (do người dùng chỉ định). Tập hợp chứa các itemset phổ biến có trọng số gọi là tập phổ biến có trọng số, ký hiệu là FWI. Bảng 3. Trọng số của từng item trong Ɗ Items A B C D E F G H Trọng số (wi) 0,60 0,50 0,65 0,55 0,70 0,60 0,80 0,30 Ví dụ 3: Cho Ɗ trong Bảng 1, và mỗi item có trọng số được cho trong Bảng 2 và minwsup = 0,12 Xét itemset X ={A, C, D}, ta có: sup({A, C, D}) = 0,20; w({A, C, D}) = max(wA, wC, wD) = max(0,60; 0,65; 0,55) = 0,65 và ws = 0,65×0,20=0,13 ≥ minwsup=0,12 - ta nói: ”X ={A, C, D} là itemset phổ biến có trọng số”; Theo tính chất 2 (mở rộng cho trường hợp có trọng số) thì các tập con của itemset X ={A, C, D} cũng phổ biến, nghĩa là tất cả tập con của X đều phổ biến - Các con của X là Ƥ≥1(X)= {({A}; 0,48), ({C}; 0,52), ({D}; 0,11), ({A, C}; 0,52), ({A, D}; 0,12), ({C, D}; 0,13)}, tuy nhiên chỉ có các itemset {{A}, {C}, {A, C}, {A, D}, {C, D}}} là phổ biến; còn itemset {D}, ta có: sup({D}) = 0,20; w({D}) = 0,55 và ws({D}) = 0,11 < minwsup = 0,12 là không phổ biến. Điều này cho chúng ta thấy: Khai thác tập phổ biến có trọng số thì tính chất 2 là không thỏa và kéo theo tính chất 3 cũng không thỏa hay nói khác đi là khai thác tập phổ biến trên DLGD có trọng số items thì không thỏa tính chất bao đóng giảm (tính chất Apriori). Như vậy, khi sinh luật kết hợp từ itemset {A, C, D} thì không thể sinh luật {D}→{A, C} (có tiền đề là itemset {D} không phổ biến, kết luận là itemset {A, C} phổ biến). Để sinh nhanh luật kết hợp từ DLGD có trọng số của items, nhóm tác giả đề xuất bài toán khai thác tập phổ biến tuyệt đối và luật kết hợp được sinh từ tập này. Bài toán này được định nghĩa như sau: Định nghĩa 9: Cho X ∈ FWI, X gọi là k - itemset phổ biến tuyệt đối nếu tất cả tập con khác rỗng của itemset X là itemset phổ biến. Tập hợp chứa các itemset phổ biến tuyệt đối có trọng số gọi là tập phổ biến tuyệt đối có trọng số, ký hiệu là PFWI. Tính chất 4: (rút gọn không gian sinh) ∀ik ∈ I, ws(ik) < minwsup: {ik ∪ X} ∉ PFWI, ∀ X ⊆ I. Bảng 4. Tập FWI, PFWI trên dữ liệu giao dịch Ɗ với minwsup = 0,12 Tập FWI Tập PFWI k-itemset #FWI = 26 #PFWI = 23 1 {{F},{A},{C},{E},{G}} {{F},{A},{C},{E},{G}} {{D, A}, {D, C}, {F, A}, {F, C}, {F, E}, {F, G}, {{F, A}, {F, C}, {F, E}, {F, G}, {A, C}, 2 {A, C},{ A, E}, {A, G}, {C, E}, {C, G}} {A, E}, {A, G}, {C, E}, {C, G}} {{D, A, C}, {F, A, C}, {F, A, E}, {F, A, G}, {F, C, E}, {{F, A, C}, {F, A, E}, {F, A, G}, {F, C, E}, 3 {F, C, G}, {A, C, E}, {A, C, G}} {F, C, G}, {A, C, E}, {A, C, G}} 4 {{F, A, C, E}, {F, A, C, G}} {{F, A, C, E}, {F, A, C, G}} Trong Bảng 4, cho thấy tập phổ biến có trọng số FWI và tập phổ biến tuyệt đối PFWI chứa k-itemset với minwsup = 0,12. Số lượng tập phổ biến |FWI| = 26, số lượng tập phổ biến tuyệt đối |PFWI| = 23. Tỷ suất PFWI FWI = 23 26 × 100% ≈ 88,50% (tỷ lệ rút gọn 11,50%). Qua đó, ta dễ dàng thấy mối quan hệ giữa tập phổ biến và tập phổ biến tuyệt đối như sau: PFWI ⊆ FWI. III. CÁC THUẬT TOÁN Trong nghiên cứu này, ngoài việc đề xuất bài toán mới thì nhóm tác giả còn khảo sát và tìm thuật toán phù hợp đã có để cải tiến nhằm minh họa tính khả thi của bài toán đề xuất. Qua quá trình khảo sát, nhóm tác giả nhận thấy thuật toán tiếp cận tựa Apriori (sử dụng chiến lược tìm kiếm theo chiều rộng - Breadth First Search) là phù hợp cho việc giải bài toán trên. Nhóm tác giả đã chọn thuật toán AprioriTID để cải tiến và minh họa cho bài toán khai thác tập phổ biến tuyệt đối trên DLGD có trọng số của items. A. Thuật toán AprioriTID khai thác tập phổ biến trên DLGD không có trọng số Thuật toán AprioriTID [2] được Agrawal cải tiến từ thuật toán Apriori nhằm rút ngắn quá trình tính toán độ phổ biến của các ứng viên k-itemset. Đây là thuật toán có nhiều trích dẫn và cải tiến, cũng như áp dụng trên nhiều định dạng dữ liệu khác nhau. Một số ký hiệu trong thuật toán AprioriTID:
286 ĐỀ 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 ITEMS - Lk : tập thành viên k-itemset thỏa minsup, mỗi thành viên có 2 trường thông tin là itemset và độ phổ biến; - Ck : tập ứng viên chứa k-itemset tiềm năng, mỗi ứng viên có 2 trường thông tin là itemset và độ phổ biến; - C k : tập các ứng viên k-itemset được chứa trong từng giao dịch t của dữ liệu giao dịch Ɗ; Mã giả thuật toán AprioriTID. Đầu vào: Dữ liệu giao dịch Ɗ, minsup Đầu ra: Tập chứa các itemset phổ biến FI 1: L1 = {1-itemset};// tập các item 2: C1 = tập dữ liệu giao dịch Ɗ; 3: For (k=2; Lk-1 ≠ ∅; k++) do 4: Ck = Apriori-gen(Lk-1); //phát sinh các kết hợp k-itemset theo thứ tự từ điển 5: C k = ∅; 6: Forall t ∈ C k −1 do 7: Ct = {c ∈ Ck| (c - c[k]) ∈ t.set-of-itemset ∧ (c - c[k-1]) ∈ t.set-of-itemset} 8: Forall c ∈ Ct do //Ct tập các ứng viên được chứa trong giao dịch t 9: c.sup += 1/n 10: If (Ct ≠ ∅) then //các ứng viên xuất hiện trong giao dịch t 11: C k += 12: Lk = {c ∈ Ck| c.sup ≥ minsup} //lọc các itemset thỏa minsup 13: Return FI =∪k Lk Với mỗi giao dịch t, xác định các ứng viên tiềm năng từ Ck được chứa trên giao dịch này và lưu vào Ct. Độ phổ biến của từng ứng viên tiềm năng Ck được tính toán theo Ct. Lần lượt các Ct được lưu vào C k . Thủ tục phát sinh các ứng viên k-itemset tiềm năng Ck từ tập (k-1)-itemset phổ biến Lk-1 Mã giả thủ tục Apriori-gen. Đầu vào: Tập chứa các (k-1)-itemset phổ biến Lk-1 Đầu ra: Tập ứng viên k-itemset Ck 1: Ck = {X ∪ X’| X, X’ ∈ Lk-1, |X ∩ X’| = k - 2} 2: Forall itemset c ∈ Ck do //loại bỏ các kết hợp không có trong DLGD 3: Forall (k-1)-subset s of c do //có k phần tử con (k-1)-itemset của c 4: If (s ∉ Lk-1) then //các item được sắp theo thứ tự từ điển 5: Ck = Ck - c 6: Return Ck Tập ứng viên tiềm năng k-itemset Ck: Mỗi c ∈ Ck được tạo thành từ kết hợp của k thành viên (k-1)-itemset phổ biến từ tập chứa (k-1)-itemset phổ biến Lk-1. Điều này cho thấy các ứng viên tiềm năng thuộc Ck đều thỏa định nghĩa 9. B. Thuật toán AprioriTID-PFWI Nhóm tác giả trình bày thuật toán AprioriTID-PFWI khai thác tập phổ biến tuyệt đối, cải tiến từ thuật toán AprioriTID và kết hợp biểu diễn dạng bit cho DLGD được rút gọn ở mỗi bước sinh k-itemset. Một số ký hiệu trong thuật toán AprioriTID-PFWI: - Lk : tập thành viên chứa k-itemset thỏa minwsup, mỗi thành viên có 4 trường thông tin là itemset và độ phổ biến, bổ sung thêm thứ tự nhỏ nhất (min) và lớn nhất (max) của item trong mỗi itemset thuộc Lk; - Ck : tập ứng viên chứa k-itemset tiềm năng, mỗi ứng viên có 4 trường thông tin là itemset biểu diễn dạng bit, độ phổ biến, thứ tự nhỏ nhất (min) và lớn nhất (max) của item trong mỗi itemset thuộc Ck ; - Ɗk : dữ liệu giao dịch được biểu diễn dạng bit, mỗi giao dịch dạng bit có thêm 3 trường thông tin là |t| số lượng items trong giao dịch, thứ tự nhỏ nhất (min) và lớn nhất (max) là thứ tự item đầu, cuối trong giao dịch. Thuật toán sử dụng trường thông tin |t| cho việc rút gọn DLGD ở mỗi bước; dựa vào trường min, max xác định nhanh giao dịch t có chứa ứng viên k-itemset tiềm năng - biểu diễn DLGD dạng bit là lựa chọn hiệu quả.
Phan Thành Huấn, Lê Hoài Bắc 287 Mã giả thuật toán AprioriTID-PFWI. Đầu vào: Dữ liệu giao dịch Ɗ, minwsup Đầu ra: Tập chứa các itemset phổ biến tuyệt đối PFWI 1: L1 = {1-itemset}; // tập các item thỏa ngưỡng minwsup - theo tính chất 4 2: Ɗ1 = tập DLGD Ɗ chỉ chứa các item có trong L1 và có |t| > 1; //sắp tăng dần theo |t| 3: For (k=2; |Lk-1 | < k; k++) do 4: Ck = Apriori-gen*(Lk-1); //sinh các kết hợp k-itemset theo thứ tự giảm dần của wi 5: Forall t ∈ Ɗk-1 do 6: Forall c ∈ Ck do 7: If (t.min ≤ c.min ∧ t.max ≤ c.max) then //kiểm tra nhanh c ∈ t 8: If (c == c AND t) then //đếm tần số 9: c.sup += 1/n 10: Lk = {c ∈ Ck| (ws(c) ≥ minwsup} //lọc các itemset thỏa minwsup 11: Ɗk = Ɗk-1 - {t ∈ Ɗk-1| |t| < k} //rút gọn tập dữ liệu 12: Return PFWI =∪k Lk Trong thuật toán AprioriTID-PFWI, nhóm tác giả đã sử dụng tập Ɗ được biểu diễn dạng bit và tập Ɗk được rút gọn ở mỗi bước sinh ứng viên tiềm năng k-itemset. Dòng 1, áp dụng tính chất 4 để rút gọn không gian sinh L1 (so với khai thác tập phổ biến có trọng số) theo thứ tự giảm dần của trọng số item; Ở dòng 2, DLGD Ɗ1 được rút gọn - chỉ chứa các item có trong L1 và có số lượng item trong giao dịch lớn hơn 1; Dòng 3, thuật toán dừng khi số lượng (k-1)- itemset nhỏ hơn k (dựa theo quy tắc sinh ứng viên tiềm năng - ứng viên k-itemset được sinh từ k thành viên (k-1)- itemset). Từ dòng 5-9, tính độ phổ biến của các ứng viên tiềm năng k-itemset (rút gọn bước sinh các kết hợp trên mỗi giao dịch so với thuật toán gốc) trên Ɗk đã được rút gọn. Thủ tục Apriori-gen* được cải tiến bằng cách xếp giảm dần theo trọng số của các item và có thứ tự từ điển (được minh họa trong phần sau). C. Minh họa thuật toán khai thác tập phổ biến tuyệt đối có trọng số AprioriTID-PFWI Trong phần này, nhóm tác giả minh họa thuật toán AprioriTID-PFWI khai thác các itemset phổ biến tuyệt đối có trọng số, cho thấy tính khả thi của bài toán đề xuất cùng với DLGD được rút gọn thông qua cải tiến. Ví dụ 4: Cho dữ liệu giao dịch Ɗ trong Bảng 1 và Bảng 3, minwsup = 0,15. Dòng 1, xét các item thỏa minwsup = 0,15: có 5 items {G}, {E}, {C}, {A}, {F} được sắp giảm dần theo trọng số và gán lần lượt thứ tự từ 1 đến 5 (dễ dàng quan sát trong minh họa - dãy bit lấy thứ tự từ trái sang). Phần minh họa có bổ sung cột itemset và w là trọng số của itemset; Dòng 2, rút gọn dữ liệu Ɗ1 = {t2, t8, t5, t7, t9, t1, t4, t10} đã loại bỏ {t3, t6} vì có | t | < 2; Từ dòng 3-11, lần lượt phát sinh các C2, L2, Ɗ2, C3, L3, Ɗ3, C4 và L4. ⇒ ⇒ Các 2-itemset tiềm năng {G, E} và {E, F} không thỏa ngưỡng minwsup = 0,15: ws({G, E}) = 0,10×0,80 = 0,08; ws({E, F}) = 0,20×0,70 = 0,14. Rút gọn dữ liệu Ɗ2 = {t5, t7, t9, t1, t4, t10};
288 ĐỀ 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 ITEMS ⇒ ⇒ Tất cả 3-itemset tiềm năng đều thỏa ngưỡng minwsup = 0,15. Rút gọn dữ liệu Ɗ3 = {t1, t4, t10}; ⇒ ⇒ Tập ứng viên C4 chỉ có duy nhất một 4-itemset tiềm năng và thỏa ngưỡng minwsup = 0,15. Tập L4 chỉ có 1 thành viên (≤ 5) 4-itemset phổ biến, kết thúc thuật toán. Tập phổ biến tuyệt đối có trọng số PFWI trên Ɗ ở Bảng 1 và Bảng 2 với minwsup = 0,15: L1 ∪L2 ∪ L3 ∪ L4 k-itemset Tập phổ biến tuyệt đối có trọng số PFWI (#PFWI = 19) - (itemset; sup; w) 1 ({G}; 0,20; 0,80), ({E}; 0,70; 0,70), ({C}; 0,80; 0,65), ({A}; 0,80; 0,60), ({F}; 0,30 ; 0,60) ({G, C}; 0,20 ; 0,80), ({G, A}; 0,20 ; 0,80), ({G, F}; 0,20 ; 0,80), ({E, C}; 0,50 ; 0,70), 2 ({E, A}; 0,50 ; 0,70), ({C, A}; 0,80 ; 0,65), ({C, F}; 0,30 ; 0,65), ({A, F}; 0,30 ; 0,60) ({G, C, A}; 0,20 ; 0,80), ({G, C, F}; 0,20 ; 0,80), ({G, A, F}; 0,20 ; 0,80), ({E, C, A}; 0,50 ; 0,70), 3 ({C, A, F}; 0,30 ; 0,65) 4 ({G, C, A, F}; 0,20 ; 0,80) IV. KẾT QUẢ THỰC NGHIỆM Thực nghiệm trên máy tính Core Duo 2.0 GHz, 4Gb, thuật toán cài đặt trên C#, MVS 2010. Nghiên cứu thực nghiệm trên hai nhóm dữ liệu: Nhóm dữ liệu thực có mật độ dày: Sử dụng dữ liệu thực từ kho dữ liệu về học máy của Trường Đại học California (Lichman, M. (2013). UCI Machine Learning Repository [http://archive.ics.uci.edu/ml]. Irvine, CA: University of California, School of Information and Computer Science) gồm 2 tập Chess và Mushroom. Nhóm dữ liệu giả lập có mật độ thưa: Sử dụng phần mềm phát sinh dữ liệu giả lập của trung tâm nghiên cứu IBM Almaden (IBM Almaden Research Center, San Joe, California 95120, U.S.A [http://www.almaden.ibm.com]) gồm 2 tập T10I4D100K và T40I10D100K. Bảng 5. Dữ liệu thực nghiệm Số Số mục nhỏ nhất/ Số mục lớn nhất/ Số mục trung bình/ Mật độ Tên dữ liệu Số mục giao dịch giao dịch giao dịch giao dịch (%) Chess 75 3.196 37 37 37 49,3 Mushroom 119 8.142 23 23 23 19,3 T10I4D100K 870 100.000 1 29 10 1,1 T40I10D100K 942 100.000 4 77 40 4,2 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 có trọng số của items và dựa trên thuật toán AprioriTID kết hợp biểu diễn DLGD dạng bit để cải tiến thành thuật toán có tên gọi là AprioriTID- PFWI. Đây là thuật toán đầu tiên giải bài toán trên, nên chưa có thuật toán cùng hướng tiếp cận để so sánh hiệu năng thuật toán. Để so sánh hiệu năng thuật toán AprioriTID-PFWI, nhóm tác giả chọn thuật toán WHIUA [7] khai thác tập phổ biến có cùng phương pháp tính độ đo về trọng số phổ biến; thuật toán được hiệu chỉnh thành thuật toán khai thác tập phổ biến tuyệt đối có trọng số của items gọi là WHIUA-PFWI (loại bỏ các itemset không phổ biến tuyệt đối). Trên cơ sở này, nhóm tác giả so sánh hiệu năng giữa hai thuật toán WHIUA-PFWI và AprioriTID-PFWI.
Phan Thành Huấn, Lê Hoài Bắc 289 Trọng số của từng item được phát sinh ngẫu nhiên trong [0, 1]. Hình 1. Thời gian thực hiện ApriotiTID-PFWI và WHIUA-PFWI trên Chess, Mushroom Hình 1a và 1b là kết quả thực nghiệm trên nhóm dữ liệu có mật độ cao, ta thấy thuật toán AprioriTID-PFWI nhanh hơn thuật toán WHIUA-PFWI. Hình 2. Thời gian thực hiện ApriotiTID-PFWI và WHIUA-PFWI trên T10I4D100K, T40I10D100K Hình 2a và 2b là kết quả thực nghiệm trên nhóm dữ liệu giả lập có mật độ thấp, ta thấy thuật toán AprioriTID- PFWI nhanh hơn thuật toán WHIUA-PFWI. Hiệu suất của thuật toán AprioriTID-PFWI rất cao so với WHIUA-PFWI trên dữ liệu thưa. Kết quả trên cho thấy thuật toán khai thác tập phổ biến tuyệt đối có trọng số AprioriTID-PFWI tốt hơn thuật toán WHIUA-PFWI - đây chỉ là thực nghiệm so sánh hiệu năng mang tính tương đối. Thuật toán cũng cần thực nghiệm thêm trên nhiều tập dữ liệu có mật độ khác nhau, cũng như trên nhiều tập dữ liệu cỡ lớn. V. KẾT LUẬN 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, đồng thời sử dụng thuật toán AprioriTID và kết hợp biểu diễn DLGD dạng bit để cải tiến thành thuật toán AprioriTID- PFWI cho thấy bài toán là khả thi (ngoài cách tiếp cận đơn giản - khai thác tập phổ biến và kết hợp hậu xử lý để loại bỏ các itemset không phổ biến tuyệt đối). Qua đó, cho thấy còn nhiều bài toán cần khai thác trên dữ liệu giao dịch có trọng số của items chưa được quan tâm nghiên cứu. Nghiên cứu tiếp theo của nhóm tác giả là lựa chọn hoặc xây dựng cấu trúc dữ liệu lưu trữ hiệu quả tập giao dịch và đồng thời đề xuất thuật toán khai thác nhanh tập phổ biến tuyệt đối; điều này giúp đẩy nhanh giai đoạn sinh luật kết hợp trên dữ liệu giao dịch có trọng số của items. Đây là một trong những bài toán tiềm năng đang bị bỏ ngỏ, cùng với nhiều ứng dụng trong các lĩnh vực như kinh tế, y học,… TÀI LIỆU THAM KHẢO [1] R. Agrawal, T. Imilienski, A. Swami, “Mining association rules between sets of large databases”. Proc. of the ACM SIGMOD International Conference on Management of Data, Washington, DC, pp. 207-216, 1993. [2] R. Agrawal, R. Srikant, “Fast Algorithms for Mining Association Rules in Large Databases”. VLDB, Chile, pp.487-499, 1994. [3] G. D. Ramkumar, S. Ranka, S. Tsur, “Weighted Association Rules: Model and Algorithm”. Proc. ACM SIGKDD, pp. 1-13, 1998.
290 ĐỀ 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 ITEMS [4] C. H. Cai, A. W. C. Fu, C. H. Cheng, W. W. Kwong, “Mining association rules with weighted items”. Proceedings. IDEAS'98. International Database Engineering and Applications Symposium (Cat. No.98EX156), Cardiff, UK, pp. 68-77, 1998. [5] F. Tao, F. Murtagh, M. M. Farid, “Weighted association rule mining using weighted support and significance framework”. SIGKDD’03, pp. 661-666, 2003. [6] U. Yun, J. J. Leggett, “WFIM: Weighted frequent itemset mining with a weight range and a minimum weight”. SDM 2005: pp. 636-640, 2005. [7] Z. G. Huai, M. H. Huang, “A weighted frequent itemsets Incremental Updating Algorithm base on hash table”. IEEE 3rd International Conference on Communication Software and Networks, Xi'an, pp. 201-204, 2011. [8] G. C. Lan, T. P. Hong, H. Y. Lee, and C. W. Lin, “Mining Weighted Frequent Itemsets”. Proceedings of the 30th workshop on Combinatorial Mathematics and Computation Theory (Alg’30), pp. 85-89, 2013. [9] X. Wei, Z. Li, T. Zhou, H. Zhang, G. Yang, “IWFPM: Interested Weighted Frequent Pattern Mining with Multiple Supports”. Journal of Software, vol. 10, pp. 9-19, 2015. [10] G. Lee, U. Yun, K. H. Ryu, “Mining frequent weighted itemsets without storing transaction IDs and generating candidates”, Inter Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 25(1), pp. 111-144, 2017. [11] X. Zhao, X. Zhang, P. Wang, S. Chen, Z. Sun, “A weighted frequent itemset mining algorithm for intelligent decision in smart systems”, IEEE Access, vol. 6, pp. 29271-29282, 2018. [12] Phan Thanh Huan, Le Hoai Bac, “A comprehensive survey of frequent itemsets mining on transactional database with weighted items”. Journal of Research and Development on Information and Communication Technology, (1), pp. 18-27, 2021. PROPOSED PERFECTLY FREQUENT ITEMSETS MINING PROBLEM ON TRANSACTIONAL DATABASE WITH WEIGHTED ITEMS Phan Thanh Huan, Le Hoai Bac ABSTRACT: In this paper, the authors propose an perfectly frequent itemsets mining problem on transactional database with weighted items and the approach that does NOT satisfy the downward closure property. This is a frequent itemsets that has all sub-itemsets that are frequent itemsets - making the association rules mining phase fast and efficient on transactional database with weighted items. The authors solve the above problem using the simple approach of the AprioriTID algorithm and combined bit representation - the improved into an algorithm called AprioriTID-PFWI. The authors conducts algorithm experiments on both real-life datasets of UCI and synthetic datasets generated by IBM Almaden, showing that the proposed problem is feasible and the algorithm improves efficiency.