Nâng cao hiệu năng cho thuật toán khai thác tập hiếm tối thiểu trên bộ xử lý đa nhân

Chia sẻ: Wang Ziyi | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

4
lượt xem 0
download

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

Bài viết đề xuất thuật toán song song MCP-mRI nhằm nâng cao hiệu năng cho khai thác tập hiếm tối thiểu 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, Apache 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ả. Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Nâng cao hiệu năng cho thuật toán khai thác tập hiếm tối thiểu trên bộ xử lý đa nhân

Nâng Cao Hiệu Năng Cho Thuật Toán Khai Thác Tập Hiếm Tối Thiểu Trên Bộ Xử Lý Đa Nhân Phan Thành Huấn1,2, Lê Hoài Bắc3 Khoa Toán – Tin học, Trường Đại học Khoa học Tự nhiên, ĐHQG-HCM 1 2 Bộ môn Tin học, Trường Đại học Khoa học Xã hội và Nhân văn, ĐHQG-HCM 3 Khoa Công nghệ Thông tin, Trường Đại học Khoa học Tự nhiên, ĐHQG-HCM Email: huanphan@hcmussh.edu.vn, lhbac@fithcmus.edu.vn Tóm tắt - Trong khai thác dữ liệu, khai thác tập hiếm là một kỹ mảng chứa itemset xuất hiện ít nhất trong một giao dịch của thuật khai thác rất quan trọng với các ứng dụng tiềm năng như từng item hạt nhân, thuật toán sinh cây nLOOC-Tree và thuật phát hiện các cuộc tấn công máy tính, giao dịch gian lận trong toán tuần tự SEQ-mRI khai thác tập hiếm tối thiểu. Phần 4, các tổ chức tài chính, tin sinh học, y tế. Trong bài viết này, chúng nhóm tác giả dựa trên thuật toán tuần tự ở Phần 3 để xây dựng tôi đề xuất thuật toán song song MCP-mRI nhằm nâng cao hiệu thuật toán song song MCP-mRI khai thác hiệu năng của bộ xử năng cho khai thác tập hiếm tối thiểu 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 lý đa nhân. Kết quả thực nghiệm được trình bày trong phần 5 toán phân tán như Hadoop, Apache Spark. Kết quả thực nghiệm và kết luận ở phần 6. 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ả. II. CÁC KHÁI NIỆM CƠ BẢN Từ khóa - Bộ xử lý đa nhân, khai thác dữ liệu, tập hiếm tối A. Tập phổ biến thiểu, thuật toán song song MCP-mRI. Cho I = {i1, i2,..., im} 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 I. GIỚI THIỆU X  { i1 ,i2 ,...,ik }, i j  I (1  j  k ) gọi là itemset, tập mục có Thuật toán khai thác luật kết hợp truyền thống [1-5] chỉ k mục gọi là k-itemset. Ɗ là dữ liệu giao dịch, gồm n bản ghi dùng một giá trị ngưỡng phổ biến tối thiểu minsup với ngầm phân biệt gọi là tập các giao dịch T = {t1, t2,..., tn}, mỗi giao định là các mặt hàng có cùng tính chất và tần số trong dữ liệu, dịch ti  { ik1 ,ik 2 ,..., ik j }, ik j  I ( 1  k j  m ) . đ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 Định nghĩa 1: Độ phổ biến (support) của itemset X  I, ký mua nhiều hơn, trong khi các mặt hàng xa xỉ và các sản phẩm hiệu sup(X), là số các giao dịch trong Ɗ có chứa X. giá trị cao lại ít được mua (tập hiếm). Nếu chọn minsup quá cao Định nghĩa 2: Cho X  I, X gọi là itemset phổ biến nếu thì các mặt hàng được khai thác thông thường có giá thành sup(X) ≥ minsup, với minsup là ngưỡng phổ biến tối thiểu. thấp và mang lại lợi nhuận không cao cho doanh nghiệp. Cho dữ liệu giao dịch Ɗ trong Bảng 1. Bảng 1. Dữ liệu giao dịch Ɗ cho Ví dụ 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 Mã giao dịch Tập item ra quyết định kinh doanh. Từ đó, có nhiều thuật toán khai thác t1 A C E F tập hiếm được đề xuất như Apriori-Inverse, ARIMA, Rarity, t2 A C G Walky-G. Các thuật toán này dựa trên Apriori [6-9], Eclat t3 E H [10] và có nhiều hạn chế như quét dữ liệu nhiều lần, sử dụng t4 A C D F G nhiều bộ nhớ, các chiến lược cắt tỉa và chưa sử dụng triệt để t5 A C E G hiệu năng tính toán của bộ xử lý đa nhân (BXLĐN). t6 E Trong bài viết này, chúng tôi đề xuất thuật toán khai thác t7 A B C E song song tập hiếm tối thiểu. Thuật toán đề xuất theo hướng t8 A C D tiếp cận song song dữ liệu và cả chức năng, dưới đây là các t9 A B C E G thuật toán liên quan trong bài viết: - Xây dựng mảng Index_LOOC chứa các item xuất hiện ít t10 A C E F G nhất trong một giao dịch của từng item hạt nhân; Dữ liệu ở Bảng 1, có 8 item riêng biệt I ={A, B, C, D, E, F, - Dựa trên Index_LOOC xây dựng cây nLOOC-Tree ; G, H} và 10 giao dịch T = {t1, t2, t3, t4, t5, t6, t7, t8, t9, t10}. - Thuật toán tuần tự SEQ-mRI khai thác tập hiếm tối thiểu B. Tập hiếm và tập hiếm tối thiểu dựa trên cây nLOOC-Tree ; - Thuật toán song song MCP-mRI khai thác nhanh tập hiếm Trong thực tế, nhiều ứng dụng tiềm năng cần khai thác các tối thiểu trên BXLĐN. tập hiếm như ứng dụng phát hiện các cuộc tấn công máy tính, Trong phần 2, bài báo trình bày các khái niệm cơ bản về tập giao dịch gian lận trong các tổ chức tài chính, tin sinh học, y hiếm, tập hiếm tối thiểu. Phần 3, xây dựng thuật toán xác định tế,…. Nhiều tác giả đã đề xuất thuật toán [6-10] khai thác tập 207
hiếm tối thiểu thỏa một hoặc hai ngưỡng. Sau đây là các khái Ví dụ 3: Xem item G là item hạt nhân, ta xác định được các niệm liên quan: item xuất hiện cùng với item B ít nhất trong một giao dịch là Định nghĩa 3: Cho X  I, X gọi là itemset hiếm – nếu looc(G) = {B, D, E, F} có  (G) = {t2, t4, t5, t9, t10} và  (GB) sup(X) < minsup. Ký hiệu RI là tập hợp chứa các itemset hiếm. = {t9},  (GE) = {t5, t9, t10}. Định nghĩa 4: Cho X  I, X gọi là itemset hiếm tối thiểu Trong phần này, chúng tôi trình bày thuật toán sinh các – nếu X là itemset hiếm và tất cả tập con thực sự của X là phổ item xuất hiện ít nhất trong một giao dịch với item hạt nhân, biến. Ký hiệu mRI là tập hợp chứa các itemset hiếm tối thiểu. được lưu trữ vào mảng Index_LOOC. Mỗi phần tử trong Tính chất 1: ik  I, nếu sup(ik) < minsup thì ik  mRI. Index_LOOC gồm có 3 thành phần thông tin sau: Ví dụ 1: Dữ liệu Ɗ trong Bảng 1 với minsup = 2, ta có: - Index_LOOC[k].item: item hạt nhân thứ k; Xét itemset X ={F, G, E}, sup(FGE) = 1 < minsup, ta nói: - Index_LOOC[k].sup:độ phổ biến của item hạt nhân thứ k; ”Itemset X ={F, G, E} là itemset hiếm”; - Index_LOOC[k].looc: các item xuất hiện cùng item hạt Xét itemset Y ={H, E}, sup(HE) = 1 < minsup, ta nói: nhân thứ k ít nhất trong một giao dịch dạng bit; ”Itemset Y ={H, E} là itemset hiếm”; Mã giả thuật toán 1. Xây dựng Index_LOOC Ngoài ra, itemset X ={F, G, E} còn là itemset hiếm tối thiểu, nghĩa là các tập con thực sự của itemset X là phổ biến: Đầu vào: Dữ liệu giao dịch Ɗ sup(F) = 3, sup(G) = 5, sup(E) = 7, sup(FG) = 2, sup(FE) = 2, Đầu ra: Ma trận BiM, mảng Index_LOOC 1. Với mỗi phần tử k của mảng Index_LOOC: sup(GE) = 3  minsup = 2. Trong khi đó, itemset Y = {H, E} 2. Index_LOOC[k].item = ik không là itemset hiếm tối thiểu, do sup(H) = 1 < minsup. 3. Index_LOOC[k].sup = 0 Theo tính chất 1 thì các item có độ phổ biến nhỏ hơn 4. Index_LOOC[k].looc= 0 minsup thì thuộc mRI, ta có : item H, sup(H) = 1 < minsup, 5. Với mỗi giao dịch ti thực hiện: suy ra item H là item hiếm tối thiểu. 6. Lưu giao dịch ti vào ma trận BiM Bảng 2. Tập RI và mRI trên Ɗ với minsup = 2 7. Với mỗi item k có trong giao dịch ti thực hiện: Tập hiếm RI Tập hiếm tối thiểu mRI 8. Index_LOOC[k].looc |= vectorbit(ti) k-itemset #RI = 26 #mRI = 5 9. Index_LOOC[k].sup + + 1 H H 10. Sắp xếp mảng Index_LOOC tăng dần theo sup 2 HE, DF, DG, BG BG, DF, DG 11. Với mỗi phần tử k của mảng Index_COOC: BGE, BGC, BGA, DFG, DFC, DFA, DGA, FGE 12. Index_COOC[k].looc= lexlooc(ik) 3 DGC, FGE 13. Trả về mảng Index_LOOC, ma trận BiM 4 BEFC, BGEA, BGAC, DFGC, DFGA, DFAC, DGAC, FGEA, FGEC Minh họa thuật toán 1: thực hiện từ dòng 1 đến 9 5 BGEAC, DFGAC, FGEAC Khởi tạo mảng Index_LOOC: (thành phần looc được biểu diễn dạng bit) số item là m = 8 [4, 5]. Trong Bảng 2, tập hiếm RI và tập hiếm tối thiểu mRI chứa item A B C D E F G H k-itemset với minsup = 2. Số lượng itemset hiếm |RI| = 26 và sup 0 0 0 0 0 0 0 0 số lượng itemset hiếm tối thiểu |mRI| = 5. Tỷ suất looc 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 Duyệt lần lượt từng giao dịch từ t1 đến t10: mRI RI  5 26 100% 19% . Mối quan hệ giữa tập Đọc t1: {A, C, E, F} có dạng bit là 10101100 itemset hiếm và tập itemset hiếm tối thiểu như sau: mRI  RI. item A B C D E F G H sup 1 0 1 0 1 1 0 0 looc 10101100 00000000 10101100 00000000 10101100 10101100 00000000 00000000 III. CÁC THUẬT TOÁN ĐỀ XUẤT Duyệt … đến t10: {A, C, E, F, G} có dạng bit là 10101110 item A B C D E F G H A. Tập chiếu và items xuất hiện ít nhất trên cùng một giao sup 8 2 8 2 7 3 5 1 dịch với item hạt nhân có thứ tự 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ó Tập chiếu của mục hàng ik trên dữ liệu giao dịch Ɗ: Index_LOOC như sau:  (ik)={t Ɗ│ikt} là tập các giao dịch có chứa mục hàng ik . item H B D F G E A C sup 1 2 2 3 5 7 8 8 sup(ik) = | ( ik)| (1) 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 Tập chiếu của tập mục X  { i1 ,i2 ,..., ik } , Thực hiện rút gọn ở dòng 11 và 12, ta có Bảng sau: i j  I (1  j  k )  (X) =  (i1) (i2)…  (ik). Bảng 3. Index_LOOC có thứ tự theo độ phổ biến của item sup(X) = |(X)| (2) item sup H 1 B 2 D 2 F 3 G 5 E 7 A 8 C 8 Ví dụ 2: Theo Bảng 1, có  (A) = {t1, t2, t4, t5, t7, t8, t9, looc Ø G F, G G, E E A, C Ø Ø t10} và  (B) = {t7, t9 }. Khi đó,  (AB) =  (A) (B)= {t1, Bảng 3, minh họa kết quả trả về mảng Index_LOOC từ t2, t4, t5, t7, t8, t9, 10}{t7, t9} = {t7, t9},  (B)   (A) và thuật toán 1. Mảng Index_LOOC có thành phần looc được  (AB)   (A). biểu diễn theo item. Để tránh trùng lặp không gian sinh, chúng tôi đưa ra Định B. Thuật toán sinh cây nLOOC-Tree nghĩa 5 – các item có thứ tự theo độ phổ biến: Định nghĩa 5: Cho ik  I (i1  i2  …  im) thứ tự theo độ Từ Index_LOOC xây dựng các cây chứa các mẫu xuất phổ biến, ta gọi ik là item hạt nhân. Tập Xlexlooc  I chứa các hiện ít nhất trong một giao dịch với item hạt nhân. Mỗi cây có item xuất hiện có thứ tự cùng với ik ít nhất trong một giao dịch, nút gốc là item hạt nhân và các nút con là items xuất hiện ít nhưng không đồng xuất hiện: 1| ( ikxlexlooc) | < | ( ik)| , 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:  xlexlooc Ƥ1(Xlexlooc). Ký hiệu, lexlooc(ik) = Xlexlooc. - nLOOC_Tree[k].item: item xuất hiện ít nhất với item hạt nhân (nút gốc); 208
- nLOOC_Tree[k].sup: độ phổ biến của item xuất hiện Chứng minh: theo bổ đề 1, ta có sup(ik xsub) < sup(ik)  cùng với item hạt nhân; minsup, nên {ik  xsub } RI,  xsub  Ƥ1(Xlexlooc) ■. Mã giả thuật toán 2: Xây dựng cây nLOOC-Tree Bổ đề 3:  ik  I, sup(ik) ≥ minsup, nếu lexlooc(ik) = Xlexlooc Đầu vào: Ma trận BiM, Mảng Index_LOOC và sup(ik  xsub) < minsup thì {ik  xsub } mRI,  xsub  Đầu ra: Danh sách cây nLOOC-Tree Ƥ2(Xlexlooc). 1. Với mỗi phần tử k của mảng Index_LOOC: Chứng minh: theo bổ đề 2, ta có {ik  xsub } RI và theo bổ 2. nLOOC_Tree[k].item = Index_LOOC[k].item đề 1, ij  xsub mà sup(ik  ij) < minsup nên {ik  xsub } mRI, 3. nLOOC_Tree[k].sup = Index_LOOC[k].sup  xsub  Ƥ2(Xlexlooc) ■. 4. Với mỗi item ik  giao dịch tℓ : 5. Với mỗi item ij  Index_LOOC[k].looc: Mã giả thuật toán 3: SEQ-mRI Đầu vào: Ma trận BiM, Index_LOOC, minsup 6. Nếu ij  nút con của nút gốc nLOOC-Tree[k] thì Thêm nút con ij vào nút gốc nLOOC-Tree[k] Đầu ra: Tập hiếm tối thiểu mRI 7. 1. Với mỗi Index_LOOC[k].sup < minsup 8. Ngược lại Thêm nút con ij vào nút gốc nLOOC-Tree[k] 2. mRI[k] = mRI[k]  Index_LOOC[k].item//theo tính chất 1 9. 10. Cập nhật sup của nút con ij của nút gốc nLOOC-Tree[k] 3. Với mỗi (Index_LOOC[k].sup ≥ minsup) và (Index_LOOC[k].looc {})//bổ đề 3 11.Trả về danh sách cây nLOOC-Tree 4. nLOOC_Tree(Index_LOOC[k].item) 5. SSP  GenPath(Index_LOOC[k].item)//sinh sub-single-path 6. Với mỗi sspj  SSP 7. Nếu (sup(sspj) < minsup) và (sup(sspj \{iℓ})  minsup) thì 8. mRI[k] = mRI[k]{(sspj \{iℓ})} 9. Trả về tập hiếm tối thiểu mRI Ví dụ 5: Cho dữ liệu Ɗ trong Bảng 1 và minsup = 5. Dòng 1 và 2: các item hiếm tối thiểu theo tính chất 1 – có item H, B, D và F (sup(H) = 1, sup(B) = sup(D) = 2 và sup(F) = 3 < minsup); Dòng 3: loại bỏ item A và C khỏi danh sách các item khai phá; (Bổ đề 3) Xét item G, xem cây nLOOC-Tree(G): có một đường đi đơn {G  E} và sup(GE) = 3 < minsup. Ta có, mRI[G] = Hình 1. Cây nLOOC-Tree theo Index_LOOC ở Bảng 3. {(GE; 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 Bảng 4. Tập hiếm tối thiểu mRI trên Ɗ với minsup = 5 xuất hiện ít nhất trong một giao dịch với item hạt nhân Item hạt nhân Tập hiếm tối thiểu mRI (các item có thứ tự theo độ phổ biến). H (H;1) - Mỗi đường đi đơn (single-path) là một mẫu có thứ tự từ B (B; 2) nút gốc (item hạt nhân) đến nút lá và độ phổ biến của một D (D; 2) mẫu là độ phổ biến của nút lá (ikik+1…iℓ). F (F; 3) - Mỗi phân đoạn đường đi đơn (sub-single-path) từ nút gốc G (GE; 3) đế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ụ 4: Xét item hạt nhân F, có đường đi đơn {F  G  IV. THUẬT TOÁN SONG SONG MCP-MRI E} và sup(FGE) = 1; phân đoạn đường đi đơn {F  G} và Ngày nay, nhiều máy tính cá nhân và máy trạm có trên hai sup(FG) = 2 là độ phổ biến của nút con G. nhân cho phép nhiều luồng xử lý (thread) được thực hiện đồng thời – điều này làm cho các máy tính có được tốc độ xử lý C. Thuật toán tuần tự khai thác tập hiếm tối thiểu nhanh hơn và khả năng đa nhiệm tốt hơn. Để tận dụng hết hiệu Thuật toán SEQ-mRI (SEQuential-minimal Rare năng của BXLĐN ta cần phân phối xử lý đồng thời trên nhiều Itemsets): khai thác tuần tự tập hiếm tối thiểu dựa trên cây nhân cho nhiều pha hay bài toán khác nhau để tiết kiệm thời nLOOC-Tree chứa các item xuất hiện ít nhất trong một giao gian và nâng cao hiệu năng. dịch với từng item hạt nhân (có thứ tự theo độ phổ biến). Chúng tôi xây dựng thuật toán song song MCP-mRI Các bổ đề dùng loại bỏ các item không sinh itemset hiếm (Multi Core Processors - minimal Rare Itemsets) khai thác tập tối thiểu trong quá trình khai thác: hiếm tối thiểu trên BXLĐN dựa trên thuật toán SEQ-mRI. Bổ đề 1:  ik  ij, nếu ij  lexlooc(ik) thì sup(ik  ij) < Thuật toán tuần tự SEQ-mRI, gồm 2 pha chính: sup(ik). - Pha 1: Xây dựng mảng Index_LOOC chứa itemset xuất Chứng minh: sup(ik ij) < sup(ik), theo (1) và (2) (ik ij) = hiện ít nhất trong một giao dịch của từng item hạt nhân; (ik)  (ij)  (ik) ■. - Pha 2: Thuật toán SEQ-mRI khai thác tập hiếm tối thiểu từ Bổ đề 2:  ik  I, sup(ik)  minsup, nếu lexlooc(ik) = Xlexlooc mảng Index_LOOC. và sup(ik xsub) < minsup thì {ik  xsub } RI,  xsub  Ƥ1(Xlexlooc). 209
Bước thứ nhất, song song hóa Pha 1 theo sơ đồ dưới đây: 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 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 Hình 2. Sơ đồ song song hóa cho Pha 1 [http://archive.ics.uci.edu/ml]. Irvine, CA: University of Hình 2, phân chia dữ liệu Ɗ thành c dữ liệu con Ɗ1, Ɗ2,…, California, School of Information and Computer Science) gồm Ɗc-1, Ɗc ứng với từng nhân Ci thực hiện thuật toán 1 với đầu 2 tập Chess và Mushroom. vào là dữ liệu Ɗi và đầu ra là mảng Index_LOOCi tương ứng. Nhóm dữ liệu giả lập thưa: sử dụng phần mềm phát sinh Để tính mảng Index_LOOC cho Ɗ, thực hiện phép tính sau: dữ liệu giả lập của trung tâm nghiên cứu IBM Almaden (IBM Index_LOOC = Index_LOOC1 Index_LOOC2… (3) Almaden Research Center, San Joe, California 95120, U.S.A Sau đó, sắp xếp mảng Index_LOOC tăng dần theo sup và [http://www.almaden.ibm.com]) gồm 2 tập T10I4D100K và chuẩn hóa theo dòng 14, 15 và 16 của thuật toán 1. T40I10D100K. Ví dụ 6: Giả sử Ɗ được chia thành 2 tập - Ɗ1 có 5 giao Bảng 5. Dữ liệu thực nghiệm Số Số item nhỏ Số item lớn nhất/ Số item trung Mật độ dịch {t1, t2, t3, t4, t5} và Ɗ2 có 5 giao dịch {t6, t7, t8, t9, t10}. Ɗ item nhất/giao dịch giao dịch bình/ giao dịch (%) Ɗ1 chạy thuật toán 1 trên nhân C1 và trả về Index_LOOC1: Chess 75 37 37 37 49,3 item A B C D E F G H Mushroom 119 23 23 23 19,3 sup 4 0 4 1 3 2 3 1 T10I4D100K 870 1 29 10 1,1 cooc 10100000 11111111 10100000 10110110 00001000 10100100 10100010 00001001 T40I10D100K 942 4 77 40 4,2 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_LOOC2: Trong bài viết này, chúng tôi đề xuất thuật toán khai thác item A B C D E F G H song song tập hiếm tối thiểu. Đây là đề xuất đầu tiên theo sup 4 2 4 1 4 1 2 0 hướng tiếp cận trên, nên chưa có thuật toán cùng hướng tiếp cooc 10100000 11101000 10100000 10110000 00001000 10101110 10101010 11111111 looc 11111110 11101010 11111110 10110000 11101110 10101110 11101110 00000000 cận để so sánh hiệu năng thuật toán. Vì vậy, chúng tôi đề xuất Tính mảng Index_LOOC cho Ɗ, :Index_LOOC = so sánh hiệu năng thuật toán song song như sau: so sánh thuật Index_LOOC1  Index_LOOC2 toán tuần tự SEQ-mRI với thuật toán AprioriRare [7] và item A B C D E F G H thuật toán Walky-G [10]. Sau đó, chúng tôi so sánh hiệu suất sup 8 2 8 2 7 3 5 1 của thuật toán song song MCP-mRI với thuật toán tuần tự cooc 10100000 11101000 10100000 10110000 00001000 10100100 10100010 00001001 looc 11111110 11101010 11111110 10110110 11101111 10111110 11111110 00001001 SEQ-mRI. Trong thực nghiệm, chúng tôi tiến hành so sánh Bước thứ hai, song song hóa Pha 2 theo sơ đồ sau: theo từng ngưỡng minsup và cả 4 thuật toán đều cho cùng kết quả số lượng itemsets hiếm. Hiệu suất thực hiện thuật toán song song trên BXLĐN:  T  T  HS  1   TM  S   S  (5)  c   c  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) Hình 3. Sơ đồ song song hóa cho Pha 2 Phương trình (5) dùng để đánh giá hiệu suất của thuật toán Hình 3, phân chia mảng Index_LOOC từ i1 đến im thành c song song MCP-mRI so với thuật toán tuần tự SEQ-mRI. phần ứng với từng nhân Cj thực hiện thuật toán SEQ-mRI với đầu vào là mảng Index_LOOC từ phần tử thứ [(j-1)*(m div Chess c)+1] đến phần tử thứ [j*(m div c)] và đầu ra là tập hiếm tối 262144 thiểu mRIj tương ứng. Tập hiếm tối thiểu cho Ɗ, ta thực hiện: 65536 Thời gian (mili giây) 16384 mRIƊ = mRI1mRI2…mRIc (4) 4096 Ví dụ 7: Cho dữ liệu Ɗ trong Bảng 1, minsup = 2. Sau khi 1024 AprioriRare thực hiện song song hóa Pha 1, ta có như Bảng 4. 256 Walky-G Nhân C1 chạy thuật toán SEQ-mRI từ item H đến F sinh 64 16 SEQ-mRI tập hiếm tối thiểu mRI1 như sau: 4 MCP-mRI mRI[H] (H;1) 1 mRI [B] (B; 2) 11 12 13 14 15 mRI [D] (D; 2) Minsup (% ) mRI [F] (F; 3) Nhân C2 chạy thuật toán SEQ-mRI từ item G đến C và Hình 4. Thời gian thực hiện khai thác mRI trên Chess sinh tập hiếm tối thiểu mRI2 như sau: Hình 4 là kết quả thực nghiệm trên tập dữ liệu Chess có mRI [G] (GE; 3) mật độ dày đặc, ta thấy thuật toán tuần tự SEQ-mRI nhanh Tập hiếm tối thiểu mRI trên dữ liệu giao dịch Ɗ với hơn thuật toán AprioriRare, Walky-G và thuật toán chạy trên minsup = 5 được tính mRIƊ = mRI1mRI2 như Bảng 4. BXLĐN là MCP-mRI có thời gian thực hiện nhanh hơn thuật 210
toán tuần tự SEQ-mRI. Hiệu suất trung bình của thuật toán Hình 7 là kết quả thực nghiệm trên nhóm dữ liệu giả lập có MCP-mRI là 76,9% và độ lệch chuẩn 2,2%. mật độ thấp T40I10D100K, ta thấy thuật toán tuần tự SEQ- mRI nhanh hơn thuật toán AprioriRare, Walky-G và thuật Mushroom toán chạy trên BXLĐN là MCP-mRI có thời gian thực hiện 512 nhanh hơn thuật toán tuần tự SEQ-mRI. Hiệu suất trung bình 256 của thuật toán MCP-mRI là 80,9% và độ lệch chuẩn 2,7%. Kết quả trên cho thấy thuật toán song song khai thác tập Thời gian (mili giây) 128 64 hiếm tối thiểu MCP-mRI trên BXLĐN tốt hơn rất nhiều so 32 AprioriRare với thuật toán AprioriRare, Walky-G. Thuật toán MCP-mRI 16 Walky-G cần được thực nghiệm thêm trên các dữ liệu giao dịch cỡ lớn 8 SEQ-mRI và so sánh thêm với các thuật toán chạy trên hệ thống tính 4 2 MCP-mRI toán phân tán Hadoop, Spark. Ngoài ra, ta còn thấy rõ thuật 1 toán MCP-mRI hoàn toàn là thuật toán song song. 0,1 0,2 0,3 0,4 0,5 Minsup (% ) 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-mRI khai thác Hình 5. Thời gian thực hiện khai thác mRI trên Mushroom nhanh tập hiếm tối thiểu dựa trên mảng itemset xuất hiện ít Hình 5 là kết quả thực nghiệm trên tập dữ liệu Mushroom nhất trong một giao dịch của từng item hạt nhân. Từ thuật toán có mật độ cao, ta thấy thuật toán tuần tự SEQ-mRI nhanh hơn tuần tự SEQ-mRI, chúng tôi mở rộng và song song hóa thực thuật toán AprioriRare, Walky-G và thuật toán chạy trên hiện trên BXLĐN gọi là thuật toán MCP-mRI. Hiệu suất trung BXLĐN là MCP-mRI có thời gian thực hiện nhanh hơn thuật bình khi song song hóa là 78,6% và độ lệch chuẩn 1,7% (trên toán tuần tự SEQ-mRI. Hiệu suất trung bình của thuật toán dữ liệu thực nghiệm). MCP-mRI là 78% và độ lệch chuẩn 2,6%. Trong các nghiên cứu tiếp theo, nhóm tác giả sẽ mở rộng thuật toán MCP-mRI để có thể khai thác nhanh tập hiếm tối T10I4D100K thiểu trên hệ thống điện thoại thông minh đa lõi có tài nguyên 1048576 hạn chế, cũng như thực nghiệm mở rộng trên hệ thống phân tán 262144 phổ biến hiện nay như Hadoop, Spark. 65536 Thời gian (mili giây) 16384 LỜI CẢM ƠN 4096 AprioriRare Nhóm tác giả cảm ơn sự hỗ trợ từ Trường Đại học Khoa 1024 Walky-G học Xã hội và Nhân văn; Trường Đại học Khoa học Tự nhiên, 256 SEQ-mRI Đại học Quốc gia Tp.HCM. 64 16 MCP-mRI 4 TÀI LIỆU THAM KHẢO 1 [1] R. Agrawal, T. Imilienski, A. Swami. Mining association rules between 0,01 0,015 0,02 0,025 0,03 sets of large databases. Proc. of the ACM SIGMOD International Minsup (% ) Conference on Management of Data, Washington, DC, (1993) 207-216. [2] M. J. Zaki, S. Parthasarathy, M. Ogihara, W. Li. New Algorithms for Hình 6. Thời gian thực hiện khai thác mRI trên T10I4D100K Fast Discovery of Association Rules. In: Proc. of the 3rd International Hình 6 là kết quả thực nghiệm trên nhóm dữ liệu giả lập có Conference on Knowledge Discovery in Databases, (1997) 283-286. mật độ thấp T10I4D100K, ta thấy thuật toán tuần tự SEQ- [3] J. Han, J. Pei, Y. Yin, R. Mao. Mining frequent patterns without candidate generation: A frequent pattern tree approach. Data Mining and mRI nhanh hơn thuật toán AprioriRare, Walky-G và thuật Knowledge Discovery, 8(1), (2004) 53–87. toán chạy trên BXLĐN là MCP-mRI có thời gian thực hiện [4] J. Dong, M. Han. BitTableFI: An efficient mining frequent itemsets nhanh hơn thuật toán tuần tự SEQ-mRI. Hiệu suất trung bình algorithm. Knowledge-Based Systems 20(4), (2007) 329–335. của thuật toán MCP-mRI là 78,5% và độ lệch chuẩn 1,9%. [5] W. Song, B. Yang. Index-BitTableFI: An improved algorithm for mining frequent itemsets. Knowedge-Based Systems 21, (2008) 507- T40I10D100K 513. [6] Y. S. Koh, N. Rountree. Finding sporadic rules using apriori-inverse. In PAKDD’05, 3518, Springer, (2005) 97–106. 262144 [7] L. Szathmary, A. Napoli, P. Valtchev. Towards rare itemset mining. 65536 Proc. of the 19th IEEE Int. Conf. on Tools with Artiﬁcial Intelligence. Thời gian (mili giây) 16384 Washington, DC, USA: IEEE Computer Society, (2007) 305–312. 4096 [8] L. Troiano, C. Birtolo. A fast algorithm for mining rare itemsets. IEEE AprioriRare 19th International Conference on Intelligent Systems Design and 1024 256 Walky-G Applications, (2009) 1149-1155. 64 SEQ-mRI [9] L. Szathmary, Finding minimal rare itemsets with an extended version 16 of the Apriori algorithm, Proceedings of the 9th International MCP-mRI Conference on Applied Informatics, 1, (2014), 85-92. 4 [10] L. Szathmary, P. Valtchev, A. Napoli, R. Godin. Efficient vertical 1 mining of minimal rare itemsets. Proc. of the 19th Int Conference on 0,075 0,08 0,085 0,09 0,095 Concept Lattices and Their Applications, (2012) 269–280. Minsup (% ) Hình 7. Thời gian thực hiện khai thác mRI trên T40I10D100K 211