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

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

Thêm vào BST

Báo xấu

17
lượt xem 2
download

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

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.

Chủ đề:

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

Lưu

Nội dung Text: 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| = 26 và |mRI| = 5. Tỷ suất mRI RI  5 26  100% 19% (mRI  RI). 3 Thuật toán đề xuất 3.1 Tập chiếu và item xuất hiện ít nhất trên cùng một giao dịch Tập chiếu của mục hàng 𝑖𝑘 trên dữ liệu giao dịch Ɗ: 𝜋(𝑖𝑘 ) = {𝑡 ∈ 𝒟|𝑖𝑘 ∈ 𝑡} là tập các giao dịch có chứa mục hàng 𝑖𝑘 ( - đơn điệu giảm) . 𝑠𝑢𝑝(𝑖𝑘 ) = |𝜋(𝑖𝑘 )| (1) Tập chiếu của tập 𝑋 = {𝑖1 , 𝑖2 , … 𝑖𝑘 }, ∀𝑖𝑗=1,𝑘 ̅̅̅̅ ∈ 𝐼, 𝜋(𝑋) = 𝜋(𝑖1 ) ∩ 𝜋(𝑖2 ) … ∩ 𝜋(𝑖𝑘 ). 𝑠𝑢𝑝(𝑋) = |𝜋(𝑋)| (2) Để tránh trùng lặp không gian sinh, chúng tôi đưa ra Định nghĩa 5: Định nghĩa 5: Cho ik  I (i1  i2  …  im) thứ tự theo độ phổ biến, ta gọi ik là item hạt nhân. Tập Xlexlooc  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| ( ikxlexlooc) | < | ( ik)| ,  xlexlooc Ƥ 1(Xlexlooc),  i j  Xlexlooc, i k  ij. Ký hiệu, lexlooc(ik) = Xlexlooc. 3.2 Thuật toán sinh item xuất hiện ít nhất trên cùng một giao dịch có thứ tự Trong phần này, chúng tôi trình bày thuật toán sinh các item 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_LOOC. Mỗi phần tử trong Index_LOOC gồm có 3 thành phần thông tin sau: - Index_LOOC[k].item: item hạt nhân thứ k; - Index_LOOC[k].sup: độ phổ biến của item hạt nhân thứ k; - Index_LOOC[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; Mã giả thuật toán 1. Xây dựng bảng Index_LOOC Đầu vào: Dữ liệu giao dịch Ɗ Đầu ra: Mảng Index_LOOC, ma trận dataset BiM//ma trận bit 1. Với mỗi phần tử k của mảng Index_LOOC thực hiện: 2. Index_LOOC[k].item = ik 3. Index_LOOC[k].sup = 0 4. Index_LOOC[k].looc= 0 5. Với mỗi giao dịch ti thực hiện: 6. Lưu giao dịch ti vào ma trận BiM 7. Với mỗi item k có trong giao dịch ti thực hiện: 8. Index_LOOC[k].looc = Index_LOOC[k].looc OR vectorbit(ti) 9. Index_LOOC[k].sup = Index_LOOC[k].sup + 1 10. Sắp xếp mảng Index_LOOC tăng dần theo sup 11. Với mỗi phần tử j của mảng Index_COOC: // định nghĩa 5
194 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 12. Index_COOC[k].looc= lexlooc(ik) 13. Trả về mảng Index_LOOC, ma trận dataset BiM Minh họa thuật toán 1: thực hiện từ dòng 1 đến 9 Khởi tạo mảng Index_LOOC: (looc 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 looc 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 Đọc giao dịch t1: {A, C, E, F} có biểu diễn dạng bit là 10101100 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 Tương tự, đọc giao dịch t10: {A, C, E, F, G} có biểu diễn dạng bit là 10101110 item A B C D E F G H sup 8 2 8 2 7 3 5 1 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_LOOC như sau: Item H B D F G E A C sup 1 2 2 3 5 7 8 8 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 11 và 12, ta có bảng sau: Bảng 3. Mảng Index_LOOC có thứ tự tăng theo độ phổ biến của item và looc có thứ tự. Item H B D F G E A C sup 1 2 2 3 5 7 8 8 looc  G F, G G, E E A, C   Các bổ đề dùng loại bỏ các item không sinh itemset hiếm tối thiểu: Bổ đề 1:  ik  ij, nếu ij  lexlooc(ik) thì sup(ik  ij) < sup(ik). Chứng minh: sup(ik ij) < sup(ik), theo (1) và (2) (ik ij) = (ik)  (ij)  (ik) ■. Bổ đề 2:  ik  I, sup(ik)  minsup, nếu lexlooc(ik) = Xlexlooc và sup(ik xsub) < minsup thì {ik  xsub } RI,  xsub  Ƥ 1(Xlexlooc). Chứng minh: theo bổ đề 1, ta có sup(ik xsub) < sup(ik)  minsup, nên {ik  xsub } RI,  xsub  Ƥ1(Xlexlooc) ■. Bổ đề 3:  ik  I, sup(ik)  minsup, nếu lexlooc(ik) = Xlexlooc và sup(ik  xsub) < minsup thì {ik  xsub } mRI,  xsub  Ƥ 2(Xlexlooc). Chứng minh: theo bổ đề 2, ta có {ik  xsub } RI và theo bổ đề 1, ij  xsub mà sup(ik  ij) < minsup nên {ik  xsub } mRI,  xsub  Ƥ 2(Xlexlooc) ■. 3.3 Thuật toán sinh cây nLOOC-Tree Từ Index_LOOC 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ó 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:
Phan Thành Huấn 195 - 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 danh sách cây nLOOC-Tree Đầu vào: Ma trận BiM, Mảng Index_LOOC Đầu ra: Danh sách cây nLOOC-Tree 1. Với mỗi phần tử k của mảng Index_LOOC: 2. nLOOC_Tree[k].item = Index_LOOC[k].item 3. nLOOC_Tree[k].sup = Index_LOOC[k].sup 4. Với mỗi item ik  giao dịch tℓ : 5. Với mỗi item ij  Index_LOOC[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 mảng Index_LOOC ở 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ụ 1: 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. Thuật toán khai thác tập hiếm tối thiểu mRI từ cây nLOOC-Tree: Mã giả thuật toán 3. Khai thác tập hiếm tối thiểu mRI Đầu vào: Mảng Dataset, Index_LOOC và minsup Đầu ra: Tập hiếm tối thiểu mRI 1. Với mỗi Index_LOOC[k].sup < minsup
196 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. mRI[k] = mRI[k]  Index_LOOC[k].item//theo tính chất 3 3. Với mỗi (Index_LOOC[k].sup ≥ minsup) và (Index_LOOC[k].looc {})//bổ đề 3 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ụ 2: Cho dữ liệu giao dịch Ɗ trong Bảng 1 và minsup = 3. Dòng 1 và 2: các item hiếm tối thiểu theo tính chất 1 – có item H, B và D (sup(H) = 1, sup(B) = 2 và sup(D) = 2 < minsup); Dòng 3: loại bỏ item A và C khỏi danh sách các item khai thác; (Bổ đề 3) Xây dựng các cây nLOOC-Tree cho các item cần khai thác: F, G và E; Xét item F, xem cây nLOOC-Tree(F): có 2 đường đi đơn {F  G  E}, {F  E} lần lượt sup(FE) = 2 < minsup, khi đó mRI[F] = {(FE, 2)} và sup(FGE) = 1 < minsup có phân đoạn đường đi đơn là {F  G} và sup(FG) = 2 < minsup , nên {FGE}  mRI[F]. Vì vậy, mRI[F] = {(FG, 2), (FE, 2)}. 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] = {}. Xét item E, xem cây nLOOC-Tree(E): có một đường đi đơn {E  A  C} và sup(EAC) = 5  minsup. Ta có, mRI[E] = {}. Tập hiếm tối thiểu mRI trên dữ liệu giao dịch Ɗ ở Bảng 1 với minsup = 3: Item hạt Tập hiếm tối thiểu mRI (minsup = 3) nhân H (H, 1) B (B, 2) D (D, 2) F (FG, 2) (FE, 2) 3.4 Thuật toán khai thác nhanh tập hiếm tối thiểu với ngưỡng minsup động Thực tế, khi cần khai thác luật kết hợp thì người dùng có thể yêu cầu thực hiện khai thác luật kết hợp thỏa ngưỡng minsup và minconf trong nhiều chuỗi thao tác liên tiếp nhau. Vì vậy, tác giả đề xuất thuật toán DYN-mRI khai thác hiệu quả cập nhật nhanh tập hiếm tối thiểu khi thay đổi ngưỡng minsup, có 2 trường hợp như sau: Trường hợp 1: minsupNext < minsupPrev – yêu cầu trước đó là khai thác tập mRI với ngưỡng minsupPrev lớn hơn ngưỡng minsupNext của yêu cầu khai thác tập mRI tiếp theo. Cập nhật mRI[item] với sup(item) ≥ minsupNext. Ví dụ 3: minsupNext = 2 < minsupPrev = 3. Cập nhật khai thác tập hiếm tối thiểu từ item có sup(item) ≥ minsupNext = 2, nghĩa là cập nhật từ item B trở về sau.
Phan Thành Huấn 197 Item hạt nhân Tập hiếm tối thiểu mRI (minsup = 2) H (H, 1) B (BG, 1) D (DF, 1) (DG, 1) F (FGE, 1) Trường hợp 2: minsupNext > minsupPrev – yêu cầu trước đó là khai thác tập mRI với ngưỡng minsupPrev nhỏ hơn ngưỡng minsupNext của yêu cầu khai thác tập mRI tiếp theo. Cập nhật mRI[item] với sup(item) ≥ minsupPrev. Ví dụ 4: minsupNext = 5 > minsupPrev = 3. Cập nhật khai thác tập hiếm tối thiểu từ item có sup(item) ≥ minsupPrev = 3, nghĩa là cập nhật từ item F trở về sau. Item hạt nhân Tập hiếm tối thiểu mRI (minsup = 5) H (H, 1) B (B, 2) D (D, 2) F (F, 3) G (GE, 3) 4 Kết quả thực nghiệm Thực nghiệm trên máy tính CF-74, Core Duo 2.0 GHz, 4GB RAM, thuật toán cài đặt trên C#, Microsoft Visual Studio 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: 2 tập dữ liệu Chess và Mushroom [http://archive.ics.uci.edu/ml]. - Nhóm dữ liệu giả lập có mật độ thưa: 2 tập dữ liệu giả lập T10I4D100K và T40I10D100K [http://www.almaden.ibm.com]. Bảng 4. Dữ liệu thực nghiệm. Dữ liệu Số giao dịch Số item Số item trung bình/giao dịch Mật độ (%) Chess 3.196 75 37 49,3 Mushroom 8.142 119 23 19,3 T10I4D100K 100.000 870 10 1,1 T40I10D100K 100.000 942 40 4,2 Trong phần thực nghiệm, sử dụng 4 tập dữ liệu được mô tả ở Bảng 4 và so sánh thuật toán đề xuất DYN-mRI với thuật toán AprioriRare [5], thuật toán Walky-G [7] và thuật toán NOV-mRI [8]. Để so sánh thời gian thực hiện giữa thuật toán đề xuất với thuật toán AprioriRare, Walky-G và NOV-mRI, chúng tôi chỉ tiến hành so sánh theo từng ngưỡng minsup. Riêng đối với thuật toán DYN-mRI, chúng tối tính thời gian trung bình cho cả 2 trường hợp được nêu ở trên.
198 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 Hình 2. Thời gian thực hiện của 4 thuật toán trên Chess, Mushroom. Hình 3. Thời gian thực hiện của 4 thuật toán trên T10I4D100K, T40I10D100K. Hình 2a và 2b: kết quả thực nghiệm trên nhóm dữ liệu có mật độ dày, ta thấy thuật toán DYN-mRI nhanh hơn thuật toán NOV-mRI, Walky-G và AprioriRare. Hiệu suất của thuật toán DYN-mRI trung bình cao hơn so với NOV-mRI lần lượt là 2a=47%, độ lệch chuẩn 2a=2,1% và 2b=38,6%, độ lệch chuẩn 2b=3,3%. Hình 3a và 3b: kết quả thực nghiệm trên nhóm dữ liệu giả lập có mật độ thưa, ta thấy thuật toán DYN-mRI nhanh hơn thuật toán NOV-mRI, Walky-G và AprioriRare. Hiệu suất của thuật toán DYN-mRI, NOV-mRI rất cao so với Walky-G và AprioriRare trên dữ liệu thưa. Hiệu suất trung bình của DYN-mRI cao hơn so với NOV-mRI lần lượt là 3a=55,7%, độ lệch chuẩn 3a=1,3% và 3b=52,8%, 3b=3,6%. Kết quả trên cho thấy thuật toán khai thác tập hiếm tối thiểu DYN-mRI tốt hơn thuật toán NOV-mRI, Walky-G và AprioriRare khi ngưỡng minsup thay đổi. 5 Kết luận 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 với ngưỡng minsup động được gọi là thuật toán DYN-mRI. Thuật toán hiệu quả hơn khi người dùng khai thác tập hiếm tối thiểu với ngưỡng minsup động thì thuật toán DYN-mRI chỉ thực hiện khai thác tập hiếm tối thiểu trên cây nLOOC-Tree và tập hiếm tối thiểu theo từng item hạt nhân đã được tính ở lần khai thác trước làm giảm thời gian xử lý đáng kể. Từ những kết quả đạt được, tác giả mở rộng thuật toán để có thể khai thác tập hiếm tối thiểu trên dữ liệu giao dịch có trọng số của item, đây là hướng nghiên cứu đang được quan tâm trong nhiều lĩnh vực, đặc biệt là trong kinh doanh, y khoa.
Phan Thành Huấn 199 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 Tự nhiên, Đại học Quốc gia Tp.HCM, Việt Nam. Tài liệu tham khảo 1. Agrawal R., Imilienski T., Swami A.: Mining association rules between sets of large databases. Proc. of the ACM SIGMOD Int Conf on Management of Data, 207-216 (1993). 2. Zaki M. J., Parthasarathy S., Ogihara M., Li W.: New Algorithms for Fast Discovery of Association Rules. In: Proc. of the 3rd International Conference on Knowledge Discovery in Databases, 283-286 (1997). 3. Han J., Pei J., Yin Y., Mao R.: Mining frequent patterns without candidate generation: A frequent pattern tree approach. Data Mining and K. Discovery, 8(1), 53–87 (2004). 4. Koh Y. S., Rountree N.: Finding sporadic rules using apriori-inverse. In PAKDD’05, 3518, Springer, 97–106 (2005). 5. Szathmary L., Napoli A., Valtchev P.: Towards rare itemset mining. Proc. of the 19th IEEE Int. Conf. on Tools with AI, IEEE Computer Society, 305–312 (2007). 6. Troiano L., Birtolo C.: A fast algorithm for mining rare itemsets. IEEE 19th International Conference on Intelligent Systems Design and Applications, 1149-1155 (2009). 7. Szathmary L., Valtchev P., Napoli A., Godin R.: Efficient vertical mining of mRI. Proc. of the 19th Int Conf on Concept Lattices and Their Applications, 269–280 (2012). 8. Phan Thành Huấn, Lê Hoài Bắc: Thuật toán hiệu quả khai thác tập hiếm tối thiểu. Hội nghị Khoa học Quốc gia FAIR lần thứ XI (2018).