Thuật toán song song khai thác tập sinh tối thiểu của tập phổ biến đóng

t khai thác luật kết hợp này từ tập sinh tối thiểu của tập phổ biến đóng. Trong bài viết này, chúng tôi đề xuất thuật toán song song MCP-mGCFI khai thác nhanh tập sinh tối thiểu của tập phổ biến đóng trên bộ xử lý đa nhân. Thuật toán đề xuất dễ dàng mở rộng trên nhiều hệ thống tính toán phân tán như Hadoop, Spark. Kết quả thực nghiệm 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 thuật toán đề xuất hiệu quả. Từ khóa - Bộ xử lý đa nhân, luật kết hợp, tập sinh tối thiểu, tập phổ biến đóng, thuật toán song song MCP-mGCFI. I. GIỚI THIỆU Năm 1993, R.Agrawal đã đề xuất mô hình cơ bản khai thác luật kết hợp từ dữ liệu giao dịch dạng nhị phân theo hai giai đoạn [1]: sinh tập phổ biến (Frequent Itemset - FI) và sinh luật tin cậy kết hợp từ tập phổ biến. Khi đó, số lượng tập mục phổ biến được sinh ra rất lớn và chiếm rất nhiều thời gian. Một số tác giả trên thế giới đã đề xuất thuật toán sinh tập phổ biến đóng (Closed Frequent Itemset - CFI) [2-3], đây là tập không dư thừa và có kích thước nhỏ hơn FI rất nhiều lần (CFI ⊆ FI). Tuy nhiên, để sinh các luật kết hợp chính xác cũng như không dư thừa, một số tác giả đã đề xuất khai thác tập sinh tối thiểu của tập phổ biến đóng (minimal Generators Closed Frequent Itemset – mGCFI) [4-9] như thuật toán SSMG[4], Zart[5], MG-CHARM[6], và DefMe[9]. Các thuật toán trên tựa Apriori, tìm kiếm theo chiều sâu và sử dụng cấu trúc SE- Tree, IT-Tree – các thuật toán này tốn nhiều bộ nhớ và đọc dữ liệu nhiều lần; cũng như không hiệu quả trên các loại dữ liệu có mật độ dày hoặc thưa. Trong bài viết này, chúng tôi đề xuất thuật toán khai thác song song tập sinh tối thiểu. Thuật toán đề xuất theo hướng tiếp cận song song dữ liệu và cả chức năng, dưới đây là các thuật toán liên quan trong bài viết: - Xây dựng mảng Index_COOC chứa itemset đồng xuất hiện và itemset xuất hiện ít nhất trong một giao dịch của từng item hạt nhân; - Dựa trên Index_COOC xây dựng cây nLOOC-Tree; - Thuật toán tuần tự SEQ-mGCFI khai thác tập sinh tối thiểu của tập phổ biến đóng dựa trên cây nLOOC-Tree; - Thuật toán song song MCP-mGCFI khai thác nhanh tập sinh tối thiểu của tập phổ biến đóng trên BXLĐN. Trong phần 2, bài báo trình bày các khái niệm cơ bản về tập phổ biến, tập phổ biến đóng và tập sinh tối thiểu. Phần 3, xây dựng thuật toán xác định mảng chứa itemset xuất hiện ít nhất trong một giao dịch của từng item hạt nhân, thuật toán sinh cây nLOOC-Tree và thuật toán tuần tự SEQ-mGCFI khai thác tập sinh tối thiểu. Phần 4, nhóm tác giả dựa trên thuật toán tuần tự ở Phần 3 để xây dựng thuật toán song song MCP-mGCFI khai thác hiệu năng của bộ xử lý đa nhân. Kết quả thực nghiệm được trình bày trong phần 5 và kết luận ở phần 6. II. CÁC KHÁI NIỆM CƠ BẢN A. Tập phổ biến Cho I = {i1, i2,..., im} là tập gồm m mục hàng, mỗi mục hàng 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 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: Độ phổ biến (support) của itemset X ⊆ I, ký hiệu sup(X), là số các giao dịch trong Ɗ có chứa X. Định nghĩa 2: Cho X ⊆ I, X gọi là itemset phổ biến nếu sup(X) ≥ minsup, với 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ã giao dịch Tập item t1 A C E F t2 A C G t3 E H t4 A C D F G t5 A C E G t6 E t7 A B C E t8 A C D t9 A B C E G t10 A C E F G Dữ liệu ở Bảng 1, có 8 items 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}. Định nghĩa 3: Cho X ⊆ I, X được gọi là itemset phổ biến đóng nếu X là itemset phổ biến và không có tập cha cùng độ phổ biến. Tập hợp chứa các itemset phổ biến đóng gọi là tập phổ biến đóng, ký hiệu là CFI. Định nghĩa 4: Cho X ⊆ I, X ∈CFI, tất cả các itemset con thực sự của X có cùng độ phổ biến với X được gọi là itemset sinh của itemset phổ biến đóng X. Tập hợp chứa các itemset sinh của các itemset phổ biến đóng gọi là tập sinh của tập phổ biến đóng, ký hiệu là GCFI. 176 Định nghĩa 5: Cho X ⊆ I, ∀ X ∈ mGCFI ⊆ GCFI, không tồn tại tập con của X có cùng độ phổ biến với X. Ta nói mGCFI là tập chứa các itemset sinh tối thiểu của các itemset phổ biến đóng. Bảng 2. Tập CFI, GCFI và mGCFI trên Ɗ với minsup = 3 k-itemset CFI #CFI=6 GCFI #GCFI=13 mGCFI #mGCFI=7 1 E F, G, A, C F, G, A,C 2 AC FA, FC, GE, GA, GC, EA, EC GE, EA, EC 3 FAC, GAC, EAC GEA, GEC 4 GEAC Trong Bảng 2, cho thấy tập phổ biến đóng CFI, tập sinh GCFI và tập sinh tối thiểu mGCFI của tập phổ biến đóng chứa k-itemset lần lượt có số lượng CFI = 6, GCFI =13, mGCFI = 7, tỷ suất 7 13 100 54mGCFI GCFI % %= × = . Qua đó, ta dễ dàng thấy mGCFI ⊆ GCFI. B. Tổ chức lưu trữ dữ liệu giao dịch Lưu trữ dữ liệu giao dịch dạng bit là cấu trúc dữ liệu hiệu quả trong [10]. Chuyển dữ liệu giao dịch thành một ma trận nhị phân BiM, trong đó mỗi dòng tương ứng với một giao dịch và mỗi cột tương ứng với một item. Nếu item thứ ik xuất hiện trong giao dịch tj thì bit thứ i của dòng tj trong BiM sẽ mang giá trị 1, ngược lại sẽ mang giá trị 0. III. CÁC THUẬT TOÁN ĐỀ XUẤT A. Tập chiếu và items xuất hiện ít nhất trên cùng một giao dịch với item hạt nhân có thứ tự Tập chiếu của item ik trên dữ liệu giao dịch Ɗ: pi (ik)={t∈ Ɗ│ik ∈t} là tập các giao dịch có chứa item ik. sup(ik) = |pi ( ik)| (1) Tập chiếu của itemset X={i1, i2,..., ik}, ∀ij ∈ I (1 ≤ j ≤ k): pi(X) = {pi(i1) ∩ pi(i2) pi(ik)}. sup(X) = |pi(X)| (2) ) Ví dụ 1: Theo Bảng 1, có pi (A) = {t1, t2, t4, t5, t7, t8, t9, t10} và pi (B) = {t7, t9}. Khi đó, pi (AB) = pi (A)∩pi (B)= {t1, t2, t4, t5, t7, t8, t9, 10}∩{t7, t9} = {t7, t9}, pi (B) ⊆ pi (A) và pi (AB) ⊆ pi (A). Để tránh trùng lặp không gian sinh, chúng tôi đưa ra Định nghĩa 6 và 7– các item có thứ tự theo độ phổ biến: Định nghĩa 6: (Rút gọn không gian tìm kiếm) Cho ik ∈ I (i1 ≺ i2 ≺ ≺ im) thứ tự theo độ phổ biến, ta gọi ik là item hạt nhân. Tập Xlexcooc ⊆ I gọi đồng xuất hiện có thứ tự với item ik: Xlexcooc là tập các item xuất hiện cùng ik và pi ( ik)≡ pi ( ik ∪xlexcooc) , ∀ Xlexcooc∈ Ƥ≥1(Xlexcooc). Ký hiệu, Xlexcooc = lexcooc(ik). Định nghĩa 7: Cho ik ∈ I (i1 ≺ i2 ≺ ≺ im) thứ tự theo độ phổ biến, ta gọi ik là item hạt nhân. Tập Ylexlooc ⊆ I chứa các item xuất hiện có thứ tự cùng với ik ít nhất trong một giao dịch, nhưng không đồng xuất hiện: 1≤|pi ( ik∪ylexlooc) |< |pi ( ik)| , ∀ ylexlooc∈Ƥ≥1(Ylexlooc). Ký hiệu, Ylexlooc = lexlooc(ik). Ví dụ 2: Xem item G là item hạt nhân, ta xác định được các item xuất hiện cùng với item B ít nhất trong một giao dịch là looc(G) = {B, D, E, F} có pi (G) = {t2, t4, t5, t9, t10} và pi (GB) = {t9}, pi (GE) = {t5, t9, t10}. Trong phần này, chúng tôi trình bày thuật toán sinh các item đồng xuất hiện và xuất hiện ít nhất trong một giao dịch với item hạt nhân, được lưu trữ vào mảng Index_COOC. Mỗi phần tử trong Index_COOC gồm có 4 thành phần thông tin: - Index_COOC[k].item: item hạt nhân thứ k; - Index_COOC[k].sup:độ phổ biến của item hạt nhân thứ k; - Index_COOC[k].cooc: các item đồng xuất hiện cùng item hạt nhân thứ k dạng bit; - Index_COOC[k].looc: các item xuất hiện cùng item hạt nhân thứ k ít nhất trong một giao dịch dạng bit; Mã giả thuật toán 1. Xây dựng Index_COOC Đầu vào: Dữ liệu giao dịch Ɗ Đầu ra: Ma trận BiM, mảng Index_COOC 1. Với mỗi phần tử k của mảng Index_COOC: 2. Index_COOC[k].item = ik 3. Index_COOC[k].sup = 0 4. Index_COOC[k].cooc= 2m - 1 5. Index_COOC[k].looc= 0 6. Với mỗi giao dịch ti thực hiện: 7. Lưu giao dịch ti vào ma trận BiM 8. Với mỗi item k có trong giao dịch ti thực hiện: 9. Index_COOC[k].cooc &= vectorbit(ti) 10. Index_COOC[k].looc |= vectorbit(ti) 11. Index_COOC[k].sup + + 12. Sắp xếp mảng Index_COOC tăng dần theo sup 13. Với mỗi phần tử k của mảng Index_COOC: 14. Index_COOC[k].cooc= lexcooc(ik) 15. Index_COOC[k].looc= lexlooc(ik) 16. Trả về mảng Index_COOC, ma trận BiM Minh họa thuật toán 1: thực hiện từ dòng 1 đến 11 Khởi tạo mảng Index_COOC: (thành phần cooc và looc được biểu diễn dạng bit) số item là m = 8. item A B C D E F G H sup 0 0 0 0 0 0 0 0 cooc 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 looc 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 Duyệt lần lượt từng giao dịch từ t1 đến t10: Đọc t1: {A, C, E, F} có dạng bit là 10101100 item A B C D E F G H sup 1 0 1 0 1 1 0 0 cooc 10101100 11111111 10101100 11111111 10101100 10101100 11111111 11111111 looc 10101100 00000000 10101100 00000000 10101100 10101100 00000000 00000000 Duyệt đến t10: {A, C, E, F, G} có dạng bit là 10101110 item A B C D E F G H sup 8 2 8 2 7 3 5 1 cooc 10100000 11101000 10100000 10110000 00001000 10100100 10100010 00001001 looc 11111110 11101010 11111110 10110110 11101111 10111110 11111110 00001001 Dòng 10, sắp xếp theo độ phổ biến của item, ta có Index_COOC như sau: item H B D F G E A C sup 1 2 2 3 5 7 8 8 cooc E A, C, E A, C A, C A, C Ø C A looc Ø G F, G D, E, G B, D, E, F A, B, C, F, G, H B, D, E, F, G B, D, E, F, G Thực hiện rút gọn ở dòng 13, 14 và 15, ta có Bảng sau: Bảng 3. Index_COOC có thứ tự theo độ phổ biến của item item H B D F G E A C sup 1 2 2 3 5 7 8 8 cooc E A, C, E A, C A, C A, C Ø C Ø looc Ø G F, G G, E E A, C Ø Ø Bảng 3, minh họa kết quả trả về mảng Index_COOC từ thuật toán 1. Mảng Index_COOC có các thành phần cooc và looc được biểu diễn theo item. B. Thuật toán sinh cây nLOOC-Tree Từ Index_COOC xây dựng các cây chứa các mẫu xuất hiện ít nhất trong một giao dịch với item hạt nhân. Mỗi cây có 177 nút gốc là item hạt nhân và các nút con là items xuất hiện ít nhất trong một giao dịch với item hạt nhân. Mỗi nút có 2 thành phần: - nLOOC_Tree[k].item: item xuất hiện ít nhất với item hạt nhân (nút gốc); - nLOOC_Tree[k].sup: độ phổ biến của item xuất hiện cùng với item hạt nhân; Mã giả thuật toán 2: Xây dựng cây nLOOC-Tree Đầu vào: Ma trận BiM, Mảng Index_COOC Đầu ra: Danh sách cây nLOOC-Tree 1. Với mỗi phần tử k của mảng Index_COOC: 2. nLOOC_Tree[k].item = Index_COOC[k].item 3. nLOOC_Tree[k].sup = Index_COOC[k].sup 4. Với mỗi item ik ∈ giao dịch tℓ : 5. Với mỗi item ij ∈ Index_COOC[k].looc: 6. Nếu ij ∉ nút con của nút gốc nLOOC-Tree[k] thì 7. Thêm nút con ij vào nút gốc nLOOC-Tree[k] 8. Ngược lại 9. Thêm nút con ij vào nút gốc nLOOC-Tree[k] 10. Cập nhật sup của nút con ij của nút gốc nLOOC-Tree[k] 11. Trả về danh sách cây nLOOC-Tree Hình 1. Cây nLOOC-Tree theo Index_COOC ở Bảng 3. Cây nLOOC-Tree có các đặc trưng như sau: - Chiều cao của cây nhỏ hơn hoặc bằng số lượng các item xuất hiện ít nhất trong một giao dịch với item hạt nhân (các item có thứ tự theo độ phổ biến). - Mỗi đường đi đơn (single-path) là một mẫu có thứ tự từ nút gốc (item hạt nhân) đến nút lá và độ phổ biến của một mẫu là độ phổ biến của nút lá (ik→ik+1→→iℓ). - Mỗi phân đoạn đường đi đơn (sub-single-path) từ nút gốc đến nút con bất kỳ trong đường đi đơn là một mẫu thứ tự và độ phổ biến của mẫu là độ phổ biến của nút con ở cuối của phân đoạn đường đi đơn. Ví dụ 3: Xét item hạt nhân F, có đường đi đơn {F → G → E} và sup(FGE) = 1; phân đoạn đường đi đơn {F → G} và sup(FG) = 2 là độ phổ biến của nút con G. C. Thuật toán tuần tự khai thác tập sinh tối thiểu Thuật toán SEQ-mGCFI (SEQuential-minimal Generators Closed Frequent Itemsets): khai thác tuần tự tập sinh tối thiểu dựa trên cây nLOOC-Tree chứa các item xuất hiện ít nhất trong một giao dịch với từng item hạt nhân. Trong phần này, chúng tôi trình bày các bổ đề dùng để loại bỏ các item hạt nhân không có itemset sinh tối thiểu của itemset phổ biến đóng. Bổ đề 1: Xlexcooc = lexcooc(ik) thì sup(ik ∪ xsub) = sup(ik), ∀ xsub ∈ Ƥ≥1(Xlexcooc). Chứng minh: lexcooc(ik) = Xlexcooc, ∀ xsub ∈ Ƥ≥1(Xlexcooc). Theo Định nghĩa 6, ta có pi(ik ∪ xsub) = pi(ik) ∩ pi(xsub) = pi(ik) và theo phương trình (1), (2) thì sup(ik ∪ xsub) = sup(ik), ∀ xsub ∈ Ƥ≥1(Xlexcooc) ■. Ví dụ 4: Xét item F, với sup(F) = 3. Ta có, lexcooc(F) = {A, C} thì 3 itemset kết hợp {A, C, AC} và sup(F) = sup(FA) = sup(FC) = sup(FAC) = 3. Bổ đề 2: ∀ik ∈ mGCFI, Xlexcooc = lexcooc(ik) thì {ik ∪ xsub} ∉ mGCFI, ∀ xsub ∈ Ƥ≥1(Xlexcooc). Chứng minh: lexcooc(ik) = Xlexcooc, ∀ xsub ∈ Ƥ≥1(Xlexcooc). Theo bổ đề 1, ta có thì sup(ik ∪ xsub) = sup(ik) mà ik ∈ mGCFI, nên {ik ∪ xsub} ∉ mGCFI (Định nghĩa 5)■. Ví dụ 5: Xét item F với minsup = 3. Ta có, {F}∈ mGCFI và lexcooc(F) = {A, C} thì sup(F) = sup(FA) = sup(FC) = sup(FAC) = 3, nên {FA, FC, FAC}∉ mGCFI. Hệ quả 1: (theo bổ đề 2) ∀ ik ∈ I, nếu sup(ik) ≥ minsup và lexcooc(ik) = {∅} thì ik ∉ mGCFI. Bổ đề 3: ∀ ik ∈ I, Ylexlooc = lexlooc(ik): sup(ik ∪ ylexlooc) < sup(ik), ∀ ylexlooc ∈ Ƥ≥1(Ylexlooc). Chứng minh: sup(ik∪ ylexlooc) < sup(ik), theo định nghĩa 7, hiển nhiên pi(ik∪ ylexlooc) = pi(ik) ∩ pi(i1) ∩ ∩ pi(ij) ⊂ pi(ik), ∀ i1,j∈ ylexlooc■. Ví dụ 6: Xét item G ≺ E, E∈lexlooc(G)={E}. Ta có, sup(GE) = 3 < sup(G)= 5. Hệ quả 2: (theo bổ đề 1, 3 và định nghĩa 5) ∀ sspj ∈ nLOOC-Tree(ik) ⊆ Ƥ≥1(lexlooc(ik)), nếu sup(sspj) ≥ minsup và sup(sspj+1) < minsup thì sspj ∈ mGCFI. Ví dụ 7: Xét item F, minsup = 2. Các đường đi con sup(F → G) = sup(F → E) = 2 ≥ minsup, nên {FG, FE}∈ mGCFI. Hệ quả 3: (tập sinh tối thiểu từ các item đồng xuất hiện hoàn toàn) ∀ ik-1 ≺ ik ∈ I, nếu sup(ik-1) = sup(ik) và ik ∈ lexcooc(ik-1) thì itemsets sinh tối thiểu từ item hạt nhân ik-1, ∀{ik-1∪X} ∈ mGCFI được sinh thêm bằng cách thay thế bởi item hạt nhân ik, ∀{ik∪X}∈ mGCFI. Mã giả thuật toán 3: SEQ-mGCFI Đầu vào: Index_COOC, minsup Đầu ra: Tập sinh tối thiểu mGCFI 1. Với mỗi Index_COOC[k].sup ≥ minsup 2. Nếu (Index_COOC[k].cooc ≠{∅}) thì //hệ quả 1 3. mGCFI[k]=mGCFI[k]∪Index_COOC[k].item 4. Nếu (Index_COOC[k].looc ≠{∅}) thì 5. nLOOC_Tree(Index_COOC[k].item) 6. SSP ← GenPath(Index_COOC[k].item) 7. Với mỗi sspj ∈ SSP 8. Nếu (sup(sspj)≥minsup)∧(sup(sspj+1)<minsup) thì//hệ quả 2 9. mGCFI[k] = mGCFI[k]∪{sspj} 10. Nếu Full(Index_COOC[k].item, Index_COOC[k-1].item)thì 11. Replace(mGCFI[k], mGCFI[k-1])//hệ quả 3 12. Trả về tập sinh tối thiểu mGCFI Ví dụ 8: Cho dữ liệu giao dịch Ɗ trong Bảng 1 và minsup = 3. Sau khi thực hiện thuật toán 1, ta có mảng INDEX_COOC chứa các item xuất hiện ít nhất trong một giao dịch với item hạt nhân, như trong Bảng 3. Dòng 1 và 2: các item F, G, A là item sinh tối thiểu theo bổ đề 1 và hệ quả 1; 178 Xét item F, có sup(F) = minsup = 3. Khi đó, các itemset tối thiểu sinh từ item F là mGCFI[F] = {(F, 3)}. Xét item G, nLOOC-Tree(G) có đường đi đơn {G → E}, sup(GE) = 3 ≥ minsup . Ta có, mGCFI[G] = {(G, 5), (GE, 3)}. Xét item E, nLOOC-Tree(E): có đường đi đơn {E → A → C}, sup(EAC) = 5 ≥ minsup. Ta có, mGCFI[E] = {(EA, 5), (EC, 5)} và theo hệ quả 1 thì {(E, 7)} ∉ mGCFI[E]. Xét item A, xem cây nLOOC-Tree(A) = {∅}: theo bổ đề 2 thì itemset tối thiểu sinh từ item A là mGFI[A] = {(A, 8)}. Xét item C, theo hệ quả 3 thì item C đồng xuất hiện hoàn toàn cùng với item A: mGFI[C] = {(C, 8)}. Bảng 4. Tập sinh tối thiểu mGCFI trên Ɗ với minsup = 3 Item hạt nhân Tập sinh tối thiểu mGCFI F (F, 3) G (G, 5) (GE, 3) E (EA, 5) (EC, 5) A (A, 8) C (C, 8) IV. THUẬT TOÁN SONG SONG MCP-MGCFI Ngày nay, nhiều máy tính cá nhân có trên hai nhân cho phép nhiều luồng xử lý được thực hiện đồng thời – điều này làm cho máy tính có được tốc độ xử lý nhanh và khả năng đa nhiệm tốt hơn. Để tận dụng hiệu năng của bộ xử lý đa nhân (BXLĐN), cần phân phối xử lý đồng thời trên nhiều nhân cho nhiều pha/ bài toán để tiết kiệm thời gian/ nâng cao hiệu năng. Chúng tôi xây dựng thuật toán song song MCP-mGCFI (Multi Core Processor - minimal Generators Closed Frequent Itemsets) khai thác tập sinh tối thiểu trên BXLĐN dựa trên thuật toán tuần tự SEQ-mGCFI. Thuật toán tuần tự SEQ-mGCFI, gồm 2 pha chính: - Pha 1: Xây dựng mảng Index_COOC; - Pha 2: Thuật toán SEQ-mGCFI khai thác tập sinh tối thiểu từ mảng Index_COOC. Bước thứ nhất, song song hóa Pha 1 theo sơ đồ dưới đây: Hình 2. Sơ đồ song song hóa cho Pha 1 Hình 2, phân chia dữ liệu Ɗ thành c tập dữ liệu con Ɗ1, Ɗ2,, Ɗc-1, Ɗc ứng với từng nhân Ci thực hiện thuật toán 1 với đầu vào là dữ liệu Ɗi và đầu ra là mảng Index_COOCi tương ứng. Để tính mảng Index_COOC cho Ɗ, thực hiện phép tính: Index_COOC = Index_COOC1 ⊕Index_COOC2⊕(3) Sau đó, sắp xếp mảng Index_COOC tăng dần theo sup và chuẩn hóa theo dòng 13, 14 và 15 của thuật toán 1. Ví dụ 9: Giả sử Ɗ được chia thành 2 tập - Ɗ1 có 5 giao dịch {t1, t2, t3, t4, t5} và Ɗ2 có 5 giao dịch {t6, t7, t8, t9, t10}. Ɗ1 chạy thuật toán 1 trên nhân C1 và trả về Index_COOC1: item A B C D E F G H sup 4 0 4 1 3 2 3 1 cooc 10100000 11111111 10100000 10110110 00001000 10100100 10100010 00001001 looc 10111110 00000000 10111110 10110110 10101111 10111110 10111110 00001001 Ɗ2 chạy thuật toán 1 trên nhân C2 và trả về Index_COOC2: item A B C D E F G H sup 4 2 4 1 4 1 2 0 cooc 10100000 11101000 10100000 10110000 00001000 10101110 10101010 11111111 looc 11111110 11101010 11111110 10110000 11101110 10101110 11101110 00000000 Tính mảng Index_COOC cho Ɗ: Index_COOC = Index_COOC1 ⊕ Index_COOC2 item A B C D E F G H sup 8 2 8 2 7 3 5 1 cooc 10100000 11101000 10100000 10110000 00001000 10100100 10100010 00001001 looc 11111110 11101010 11111110 10110110 11101111 10111110 11111110 00001001 Bước thứ hai, song song hóa Pha 2 theo sơ đồ sau: Hình 3. Sơ đồ song song hóa cho Pha 2 Hình 3, phân chia mảng Index_COOC từ i1 đến im thành c phần ứng với từng nhân Cj thực hiện thuật toán SEQ-mGCFI với đầu vào là mảng Index_COOC từ phần tử thứ [(j-1)*(m div c)+1] đến phần tử thứ [j*(m div c)] và đầu ra là tập sinh tối thiểu mGCFIj tương ứng. Tập sinh tối thiểu cho tập dữ liệu giao dịch Ɗ, ta thực hiện theo phương trình: mGCFIƊ = mGCFI1∪ mGCFI2∪ mGCFIc (4) Ví dụ 10: Cho dữ liệu Ɗ trong Bảng 1, minsup = 3. Sau khi thực hiện song song hóa Pha 1 trên 2 nhân, ta có như Bảng 3. Nhân C1 chạy thuật toán SEQ-mGCFI từ item F đến E khai thác itemset sinh tối thiểu mGCFI1 như sau: mGCFI[F] (F, 3) mGCFI [G] (G, 5) (GE, 3) mGCFI [E] (EA, 5) (EC, 5) Nhân C2 chạy thuật toán SEQ-mGCFI từ item A đến C khai thác itemset sinh tối thiểu mGCFI2 như sau: mGCFI [A] (A, 8) mGCFI [C] (C, 8) Tập sinh tối thiểu mGCFI trên dữ liệu giao dịch Ɗ với minsup = 3 được tính mGCFIƊ = mGCFI1∪mGCFI2, ta có kết quả như Bảng 4. V. KẾT QUẢ THỰC NGHIỆM Thực nghiệm trên máy Panasonic CF-74, Core Duo 2.0 GHz (2 core, 2 thread), 4GB RAM, cài đặt trên C#, VS 2010. Nghiên cứu thực nghiệm trên 2 nhóm dữ liệu: Nhóm dữ liệu thực mật độ dày đặc: 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 []. 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 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 []) gồm 2 tập T10I4D100K và T40I10D100K. Bảng 5. Dữ liệu thực nghiệm Ɗ Số item Số item nhỏ nhất/giao dịch Số item lớn nhất/ giao dịch Số item trung bình/ giao dịch Mật độ (%) Chess 75 37 37 37 49,3 Mushroom 119 23 23 23 19,3 T10I4D100K 870 1 29 10 1,1 T40I10D100K 942 4 77 40 4,2 Trong bài viết này, chúng tôi đề xuất thuật toán khai thác song song tập sinh tối thiểu. Đây là đề xuất đầu tiên theo 179 hướng tiếp cận song song, 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. Vì vậy, chúng tôi đề xuất so sánh hiệu năng thuật toán song song như sau: so sánh thuật toán tuần tự SEQ-mGCFI với thuật toán Zart [5] và thuật toán DefMe [9]. Sau đó, chúng tôi so sánh hiệu suất của thuật toán song song MCP-mGCFI với thuật toán tuần tự SEQ-mGCFI. Trong thực nghiệm, chúng tôi tiến hành so sánh theo từng ngưỡng minsup và cả 4 thuật toán đều cho cùng kết quả số lượng itemsets sinh tối thiểu. Hiệu suất thực hiện thuật toán song song trên BXLĐN:             −−= c T c TTHS SSM1 (5) Trong đó: - TS: thời gian thực hiện tuần tự - TM: thời gian thực hiện song song trên BXLĐN - c: số lượng nhân của CPU (số core) Phương trình (5) - đánh giá hiệu suất của thuật toán song song MCP-mGCFI so với thuật toán tuần tự SEQ-mGCFI. 100 1000 10000 100000 1000000 10000000 50 55 60 65 70 Th ời gi an (m ili gi ây ) Minsup (% ) Chess Zart DefMe SEQ-mGCFI MCP-mGCFI Hình 4. Thời gian thực hiện khai thác mGCFI trên Chess Hình 4 là kết quả thực nghiệm trên tập dữ liệu Chess có mật độ dày đặc (49,3%), ta thấy thuật toán tuần tự SEQ- mGCFI nhanh hơn thuật toán Zart, DefMe và thuật toán chạy trên BXLĐN là MCP-mGCFI có thời gian thực hiện nhanh hơn thuật toán tuần tự SEQ-mGCFI. Hiệu suất trung bình của thuật toán MCP-mGCFI là 75,7% và độ lệch chuẩn 1,5%. 10 100 1000 10000 100000 25 30 35 40 45 Th ời gi an (m ili gi ây ) Minsup (% ) Mushroom Zart DefMe SEQ-mGCFI MCP-mGCFI Hình 5. Thời gian thực hiện khai thác mGCFI trên Mushroom Hình 5 là kết quả thực nghiệm trên tập dữ liệu Mushroom có mật độ cao (19,3%), ta thấy thuật toán tuần tự SEQ- mGCFI nhanh hơn thuật toán Zart, DefMe và thuật toán chạy trên BXLĐN là MCP-mGCFI có thời gian thực hiện nhanh hơn thuật toán tuần tự SEQ-mGCFI. Hiệu suất trung bình của thuật toán MCP-mGCFI là 77,1% và độ lệch chuẩn 1,4%. 10 100 1000 10000 100000 0.1 0.15 0.2 0.25 0.3 Th ời gi an (m ili gi ây ) Minsup (% ) T10I4D100K Zart DefMe SEQ-mGCFI MCP-mGCFI Hình 6. Thời gian thực hiện khai thác mGCFI trên T10I4D100K Hình 6 là kết quả thực nghiệm trên tập dữ liệu giả lập T10I4D100K có mật độ thấp (1,1%), ta thấy thuật toán tuần tự SEQ-mGCFI nhanh hơn thuật toán Zart, DefMe và thuật toán chạy trên BXLĐN là MCP-mGCFI có thời gian thực hiện nhanh hơn thuật toán tuần tự SEQ-mGCFI. Hiệu suất trung bình của MCP-mGCFI là 79,5% và độ lệch 0,9%. 10 100 1000 10000 100000 1000000 10000000 0.5 0.6 0.7 0.8 0.9 Th ời gi an (m ili gi ây ) Minsup (% ) T40I10D100K Zart DefMe SEQ-mGCFI MCP-mGCFI Hình 7. Thời gian thực hiện khai thác mGCFI trên T40I10D100K Hình 7 là kết quả thực nghiệm trên tập dữ liệu giả lập T40I10D100K có mật độ thấp (4,2%), ta thấy thuật toán tuần tự SEQ-mGCFI nhanh hơn thuật toán Zart, DefMe và thuật toán chạy trên BXLĐN là MCP-mGCFI có thời gian thực hiện nhanh hơn thuật toán tuần tự SEQ-mGCFI. Hiệu suất trung bình của thuật toán MCP-mGCFI là 81,3% và độ lệch chuẩn 1,9%. Kết quả trên cho thấy thuật toán song song khai thác tập sinh tối thiểu MCP-mGCFI trên BXLĐN tốt hơn rất nhiều so với thuật toán Zart, DefMe. Thuật toán MCP-mGCFI cần được thực nghiệm thêm trên các dữ liệu giao dịch cỡ lớn và so sánh thêm với các thuật toán chạy trên hệ thống tính toán phân tán Hadoop, Spark. Ngoài ra, ta còn thấy rõ thuật toán MCP- mGCFI hoàn toàn là thuật toán song song. VI. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Bài viết đã đề xuất thuật toán tuần tự SEQ-mGCFI khai thác nhanh tập sinh tối thiểu trên mảng itemset xuất hiện ít nhất trong một giao dịch của từng item hạt nhân. Từ thuật toán tuần tự SEQ-mGCFI, chúng tôi mở rộng và song song hóa thực hiện trên BXLĐN gọi là thuật toán MCP-mGCFI. Hiệu suất trung bình khi song song hóa trên 4 tập dữ liệu thực nghiệm là 78,4% và độ lệch chuẩn 2,6%. 180 Trong các nghiên cứu tiếp theo, nhóm tác giả sẽ mở rộng thuật toán MCP-mGCFI để có thể khai thác nhanh tập sinh tối thiểu trên hệ thống điện thoại thông minh đa lõi có tài nguyên hạn chế, cũng như thực nghiệm mở rộng trên hệ thống phân tán phổ biến hiện nay như Hadoop, Spark. LỜI CẢM ƠN Tác giả cảm ơn sự hỗ trợ từ Trường Đại học Khoa học Xã hội và Nhân văn; Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Tp.HCM. TÀI LIỆU THAM KHẢO [1] R. Agrawal, T. Imilienski, A. Swami, “Mining association rules between sets of large databases,” Proceedings of the ACM SIGMOD International Conference on Management of Data, Washington, DC, (1993), 207-216. [2] Y. Bastide, N. Pasquier, R. Taouil, G. Stumme, L.Lakhal: Mining Minimal Non-Redundant Association Rules using Closed Frequent Itemssets. In: 1st International Conference on Computational Logic, (2000), 972 - 986. [3] M. J. Zaki, “Mining Non-Redundant Association Rules,” Data Mining and Knowledge Discovery, 9, (2004), 223–248. [4] G. Dong, C. Jiang, J. Pei, J. Li, L. Wong, “Mining Succinct Systems of Minimal Generators of Formal Concepts,” In: Zhou, L., Ooi, B.-C., Meng, X. (eds.) DASFAA 2005. LNCS, Springer, Heidelberg, 3453, (2005), 175–187. [5] L. Szathmary, A. Napoli, S. O. Kuznetsov, “ZART: AMultifunctional Itemset Mining Algorithm,” Proc. of the 6th Intl. Conf. on Concept Lattices and Their Applications (CLA ’08), (2008), 47–58. [6] V. Bay, L. Bac, “Fast Algorithm for Mining Minimal Generators of Frequent Closed Itemsets and TheirApplications,” In: The IEEE 39th International Conference on Computers & Industrial Engineering, Troyes, France, (2009), 1407 – 1411. [7] T. Hamrouni, “Key roles of closed sets and minimal generators in concise representations of frequent patterns,” Intell. Data Anal, 2012, 16(4), (2012), 581 – 631. [8] L. Szathmary, P. Valtchev, A. Napoli, R. Godin, A. Boc, and V. Makarenkov, “A fast compound algorithm for mining generators, closed itemsets, and computing links between equivalence classes,” Annals of Mathematics and Artifcial Intelligence, Springer Verlag, 70 (1-2), (2014), 81 - 105. [9] A. Soulet, F. Rioult, “Efficiently Depth-First Minimal Pattern Mining,” In: Tseng V.S., Ho T.B., Zhou ZH., Chen A.L.P., Kao HY. (eds) Advances in Knowledge Discovery and Data Mining. PAKDD 2014. Lecture Notes in Computer Science. Springer, Cham, 2014, 8443, (2014), 28 – 39. [10] Phan Thành Huấn, Lê Hoài Bắc, “Nâng cao hiệu năng cho thuật toán khai thác tập hiếm tối thiểu,” Hội nghị Quốc gia REV-ECIT lần thứ XXI, (2018), 207-211. 181