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
9 trang |
Chia sẻ: Thục Anh | Ngày: 11/05/2022 | Lượt xem: 354 | Lượt tải: 0
Nội dung tài liệu DYN-MRI: Thuật toán khai thác nhanh tập hiếm tối thiểu với ngưỡng phổ biến động, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Phan Thành Huấn
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.
191
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.
k-itemset
Tập RI
#RI = 26
Tập mRI
#mRI = 5
1 H H, B, D
2 HE, DF, DG, BG FG, FE
3 BGE, BGA, BGC, DFG, DFA, DFC, DGA, DGC, GGE
4
BGAC, BGEA, BGEC, DFAC, DGAC, DGEA, DGEC,
FGEA, FGEC
5 BGEAC, DFGAC, FGEAC
192
Phan Thành Huấn
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 5 26 100 19mRI RI % % (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| ( ikxlexlooc) |< | ( 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
193
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:
194
Phan Thành Huấ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 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á (ikik+1iℓ).
- 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
195
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
nhân
Tập hiếm tối thiểu mRI (minsup = 3)
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.
196
Phan Thành Huấn
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
[].
- 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 [].
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.
197
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.
198
Phan Thành Huấn
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).
199
Các file đính kèm theo tài liệu này:
- dyn_mri_thuat_toan_khai_thac_nhanh_tap_hiem_toi_thieu_voi_ng.pdf