DFS-Apriori: Khai thác nhanh tập phổ biến áp dụng chiến lược tìm kiếm theo chiều sâu

Chia sẻ: Liễu Yêu Yêu | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

18
lượt xem 3
download

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

Bài viết "DFS-Apriori: Khai thác nhanh tập phổ biến áp dụng chiến lược tìm kiếm theo chiều sâu" khảo sát một số thuật toán Apriori cải tiến và trình bày cách tiếp cận mới cải tiến hiệu quả thuật toán Apriori dựa theo chiến lược tìm kiếm theo chiều sâu (Depth First Search – DFS) – dễ dàng mở rộng trên môi trường tính toán phân tán. Đồng thời, thuật toán đề xuất kỹ thuật rút gọn các ứng viên, tính nhanh độ phổ biến của ứng viên và biểu diễn dữ liệu dạng bit - giúp đẩy nhanh tốc độ tính toán và giảm thiểu truy xuất dữ liệu. 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: DFS-Apriori: Khai thác nhanh tập phổ biến áp dụng chiến lược tìm kiếm theo chiều sâu

Hội nghị Quốc gia lần thứ 25 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2022) DFS-Apriori: Khai Thác Nhanh Tập Phổ Biến Áp Dụng Chiến Lƣợc Tìm Kiếm Theo Chiều Sâu Phan Thành Huấn1,2,4, Đặng Thanh Minh1,4, Nguyễn Nhƣ Đồng3 1 Khoa Toán – Tin học, Trƣờng Đại học Khoa học Tự nhiên, ĐHQG.HCM-VN 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-VN 3 Trung tâm Giáo dục Nghề nghiệp – Giáo dục Thƣờng xuyên, Tp. Thủ Đức 4 Đại học Quốc gia Tp. Hồ Chí Minh Email: huanphan@hcmussh.edu.vn; minhthanhdang1982@gmail.com; dongnhunguyen74@gmail.com Tóm tắt - Khai thác tập phổ biến là giai đoạn cốt lõi trong khai đƣợc nhiều nhà nghiên cứu cải tiến và áp dụng khai phá trên thác luật kết hợp từ dữ liệu giao dịch nhị phân. Agrawal cùng nhiều loại dữ liệu khác nhau: chuỗi [3], định lượng [4], đồ thị đồng sự đề xuất thuật toán Apriori . Đây là thuật toán cơ sở cho [5], thuộc tính có trọng số [6],… nhiều cải tiến, cũng như được sử dụng khai thác trên nhiều loại Qua khảo sát các nghiên cứu liên quan đến cải tiến thuật dữ liệu khác nhau. Ngoài ra, những năm gần đây thuật toán toán Apriori khai thác tập phổ biến trên DLGD nhị phân, gồm Apriori là thuật toán được nhiều nhà nghiên cứu lựa chọn để mở hai hướng tiếp cận chính: rộng cho khai thác tập phổ biến từ dữ liệu lớn trên môi trường  Định dạng dữ liệu theo chiều ngang: Đây là định dạng phân tán. Thuật toán Apriori dựa theo chiến lược tìm kiếm theo theo thuật toán Apriori gốc. Các thuật toán cải tiến Apriori chiều rộng (Breadth First Search – BFS) – điều này làm hạn chế trong thực hiện tính toán phân tán. Trong bài viết này, nhóm tác thƣờng sử dụng chiến lƣợc rút gọn giao dịch và rút gọn giả khảo sát một số thuật toán Apriori cải tiến và trình bày cách không gian sinh các ứng viên tiềm năng k-itemset. Tuy tiếp cận mới cải tiến hiệu quả thuật toán Apriori dựa theo chiến nhiên, vấn đề tính độ phổ biến của k-itemset vẫn chƣa thật lược tìm kiếm theo chiều sâu (Depth First Search – DFS) – dễ sự hiệu quả. dàng mở rộng trên môi trường tính toán phân tán. Đồng thời,  Định dạng dữ liệu theo chiều dọc: Năm 1995, Savasere thuật toán đề xuất kỹ thuật rút gọn các ứng viên, tính nhanh độ [7] cùng đồng sự đề xuất thuật toán Parition sử dụng định phổ biến của ứng viên và biểu diễn dữ liệu dạng bit - giúp đẩy dạng dữ liệu theo chiều dọc. Định dạng này, giúp tính độ nhanh tốc độ tính toán và giảm thiểu truy xuất dữ liệu. Thuật phổ biến dễ dàng và hạn chế đối với DLGD có mật độ cao. toán cải tiến được gọi là DFS-Apriori. Nhóm tác giả tiến hành Bảng 1. Một số công trình cải tiến thuật toán Apriori [7-16] thực nghiệm thuật toán trên bộ dữ liệu thực của UCI và dữ liệu Tác giả Định dạng Thuật toán Năm giả lập của trung tâm nghiên cứu IBM Almaden, cho thấy thuật đứng đầu dữ liệu toán cải tiến hiệu quả. A. Savasere Partition dọc 1995 J. Lei HDO-Apriori ngang 2006 Từ khóa – luật kết hợp, tập phổ biến, thuật toán DFS-Apriori. W.Yu RATT ngang 2008 Y. Guo IApriori dọc 2010 I. GIỚI THIỆU J. Singh SOT-Apriori ngang 2013 Năm 1993, Agrawal cùng đồng sự đề xuất mô hình đầu tiên H. Singh MBAT ngang 2013 của bài toán khai thác luật kết hợp – khai thác luật kết hợp trên M. A. Maolegi M-Apriori dọc 2014 dữ liệu giao dịch (DLGD) nhị phân [1]. Khai thác luật kết hợp V.Vijayalakshmi CBTRA ngang 2015 là khai phá các luật kết hợp có độ phổ biến (support) cũng nhƣ S. Aditya LOT-Apriori ngang 2017 độ tin cậy (confidence) lớn hơn hoặc bằng một ngƣỡng phổ L. Xu MD-Apriori dọc 2019 biến tối thiểu (minsup) và ngƣỡng tin cậy tối thiểu (minconf). Bảng 1, liệt kê một số thuật toán cải tiến Apriori. Các đặc Bài toán đƣợc chia thành hai pha: trƣng của thuật toán cải tiến: i) rút gọn giao dịch dựa vào số Pha 1: Tìm tất cả các kết hợp thỏa ngƣỡng phổ biến tối lƣợng items trên mỗi giao dịch – SOT-Aprioir [11], CBTRA thiểu minsup (sinh tập phổ biến FI - Frequent Itemset); [14], LOT-Apriori [15] ; ii) rút gọn tập ứng viên tiềm năng – Pha 2: Sinh luật kết hợp lần lƣợt từ các kết hợp thỏa Partition [7], HDO-Apriori [8], Iapriori [11], M-Apriori [13], minsup ở pha 1 và các luật kết hợp này phải thỏa ngƣỡng tin MD-Apriori [16]; iii) giảm bƣớc tính độ phổ biến – RAAT [9], cậy tối thiểu minconf. MBAT [12]; iv) phân chia dữ liệu thành nhiều phần – Parition Sau đó, Agrawal cùng đồng sự tập trung hƣớng giải quyết [7], MD-Apriori [16]. cho pha 1 và nhóm đã đề xuất thuật toán Apriori [2] cho khai Ngoài ra, thuật toán tựa Apriori cũng đƣợc nhiều nhà thác tập phổ biến. Đây là thuật toán then chốt, quan trọng trong nghiên cứu quan tâm mở rộng thực hiện khai thác dữ liệu lớn khai thác luật kết hợp. Thuật toán tiếp cận sinh các kết hợp phổ trên môi trƣờng phân tán. Gần đây, Shashi cùng đồng sự đề biến với chiến lƣợc tìm kiếm theo chiều rộng (Breadth First xuất thuật toán EAFIM [19] khai thác trên môi trƣờng phân Search – BFS) dễ dàng cài đặt và song song hóa nhằm nâng tán Spark và dựa trên thuật toán Apriori gốc, thuật toán cao hiệu năng; thuật toán tốn nhiều lần quét dữ liệu và có độ EAFIM cũng cho thấy hiệu quả hơn thuật toán R-Apriori [18], phức tạp dạng hàm mũ. Chính vì vậy, Apriori là thuật toán YAFIM [17]. ISBN 978-604-80-7468-5 135
Hội nghị Quốc gia lần thứ 25 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2022) Nhóm tác giả thấy rằng, các thuật toán cải tiến trên chƣa Ví dụ 1: Dữ liệu giao dịch trong Bảng 1, có 8 item riêng quan tâm đến thứ tự độ phổ biến của các items, rút gọn bƣớc biệt I = {A, B, C, D, E, F, G, H} và tập giao dịch Ƭ = {t1, t2, phát sinh ứng viên k-itemset từ tập phổ biến (k-1)-itemset. t3, t4, t5, t6, t7, t8, t9, t10} với giá trị ngƣỡng phổ biến tối Ngoài ra, chiến lƣợc tìm kiếm theo chiều rộng rất khó phân rã thiểu minsup = 0,50, ta có: khi mở rộng khai thác dữ liệu lớn trên các hệ thống tính toán Theo tính chất 1: X ={G, A, C}, sup(GAC) = 0,50 – độ phân tán. Vì vậy, nhóm tác giả đề xuất tiếp cận mới trong cải phổ biến lần lƣợt các tập con của X: sup(A) = sup(C) sup(AC) tiến hiệu quả thuật toán Apriori cho khai thác tập phổ biến trên = 0,80; sup(G) = sup(GA) = sup(GC) = 0,50. DLGD áp dụng chiến lƣợc tìm kiếm theo chiều sâu (Depth Theo tính chất 2: các tập con của X ={G, A, C} cũng phổ First Search – DFS) – thuật toán dễ dàng mở rộng trên môi biến; ta thấy độ phổ biến của các tập con của X đều lớn hơn trƣờng tính toán phân tán. hoặc bằng ngƣỡng minsup. Phần 2, bài báo trình bày các khái niệm cơ bản về khai thác Theo tính chất 3: Y = {F} thì sup(F) = 0,20 < minsup - ”Y tập phổ biến, thuật toán AprioriTID và phân tích ƣu, nhƣợc = {F} itemset không phổ biến ngƣỡng minsup”. Khi đó, các điểm. Phần 3, đề xuất thuật toán khai thác nhanh tập phổ biến tập cha của Y cũng không phổ biến, nghĩa là Z = {F, E} cũng theo hƣớng tiếp cận theo chiều sâu DFS-Apriori; kết quả thực không phổ biến, sup(FE) = 0,20 < minsup. Bảng 3. FIs trên dữ liệu giao dịch T, minsup = 0,50 nghiệm đƣợc trình bày trong phần 4; kết luận và hƣớng phát triển đƣợc trình bày trong phần 5. k-itemset Tập phổ biến FIs (#FIs = 11) 1 (G; 0,50), (E; 0,70), (A; 0,80), (C; 0,80) II. CÁC KHÁI NIỆM CƠ BẢN (GA; 0,50), (GC; 0,50), (EA; 0,50), (EC; 0,50), 2 A. Khai thác tập phổ biến (AC; 0,80) Cho I = {i1, i2,..., im} là tập gồm m thuộc tính, mỗi thuộc 3 (GAC; 0,50), (EAC; 0,50) tính gọi là item. Tập các item X ={i1, i2,..., ik}, ij  I (1 j  k) Ở Bảng 3, trình bày k-itemset phổ biến trên DLGD với gọi là itemset, itemset có k item gọi là k-itemset. Dữ liệu giao ngƣỡng minsup = 0,50; các k-itemset phổ biến đƣợc sắp xêp dịch T = {t1, t2,..., tn} gồm n giao dịch, mỗi giao dịch tk ={ik1, tăng dần theo độ phổ biến của các items ik2,..., ikm}, ikj I (1kj m). (H  B  D  F  G  E  A  C) và có 11 itemset phổ biến. Định nghĩa 1: Độ phổ biến (support) của itemset X  I, ký B. Thuật toán Apriori và AprioriTID hiệu sup(X) - tỷ lệ giữa số giao dịch trong T có chứa X và n giao dịch. Thuật toán Apriori do Agrawal cùng đồng sự đề xuất năm 1994 [2], đƣợc đánh giá mang tính chất lịch sử trong khai thác sup( X )  t  T | X  t n luật kết hợp. Apriori là thuật toán nền tảng để tìm các tập phổ Định nghĩa 2: Cho X  I, X gọi là itemset phổ biến – biến sử dụng phƣơng pháp sinh ứng viên. Thuật toán có đặc nếu sup(X) ≥ minsup, trong đó minsup là ngƣỡng phổ biến tối điểm là tìm kiếm theo chiều rộng sử dụng tính chất Apriori: thiểu (do người dùng chỉ định). Ký hiệu FI là tập hợp chứa các bất kỳ (k-1)-itemset không phổ biến thì nó không thể là tập itemset phổ biến. con của k-itemset phổ biến. Một số tính chất của itemset phổ biến: đây là các tính Một số ký hiệu trong thuật toán Apriori: chất nền tảng sử dụng cho việc rút gọn không gian tìm kiếm – Lk: tập chứa k-itemset phổ biến; các tính chất này đƣợc gọi là tính chất Apriori/ bao đóng giảm Ck: tâp ứng viên tiềm năng k-itemset; (Downward Closure Property - DCP). Mã giả thuật toán Apriori Tính chất 1: (độ phổ biến của tập con) Cho X, Y  I, nếu X Đầu vào: Tập giao dịch Ƭ, ngƣỡng minsup  Y thì sup(X)  sup(Y); Đầu ra: Tập kết hợp nối liền phổ biến FI Tính chất 2: Một itemset con khác rỗng của một itemset 1: L1 = {1-itemset} phổ biến cũng là itemset phổ biến - XY, sup(Y) ≥ minsup: 2: For (k = 2; Lk-1   ; k++) do sup(X) ≥ minsup; 3: Ck = AprioriGen(Lk-1) Tính chất 3: Một itemset chứa một itemset không phổ biến 4: For each t  Ƭ do cũng là itemset không phổ biến - X Y, sup(X) < minsup: 5: Ct = subset(Ck, t) sup(Y) < minsup. 6: For each c  Ct do Bảng 2. Dữ liệu giao dịch T dùng cho Ví dụ 7: c.count ++ TID Items 8: Lk = {c  Ck| c.count  minsup} t1 A C E F 9: FI = k Lk t2 A C G 10: Trả về FI Dòng 1, tập L1 chứa các item thỏa minsup; dòng 2 đến 8, t3 E H phát sinh k-itemset phổ biến; dòng 3 sinh tập Ck ứng viên chứa t4 A C D F G k-itemset từ tập Lk-1 chứa các (k-1)-itemset phổ biến; dòng 4 t5 A C E G đến 7, với mỗi giao dịch t, xác định các ứng viên tiềm năng từ t6 E Ck đƣợc chứa trên giao dịch này và lƣu vào Ct. Độ phổ biến t7 A B C E của từng ứng viên tiềm năng Ck đƣợc tính toán theo Ct; dòng t8 A C D 8, lọc ứng viên k-itemset thỏa ngƣỡng minsup đƣa vào Lk. t9 A B C E G Thủ tục AprioriGen - sinh các ứng viên k-itemset tiềm t10 A C E F G năng Ck từ tập (k-1)-itemset Lk-1. ISBN 978-604-80-7468-5 136
Hội nghị Quốc gia lần thứ 25 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2022) Mã giả thủ tục AprioriGen Dữ liệu giao dịch T, có 5 item thỏa minsup: L1 = {(F; 0,30), Đầu vào: Tập chứa các (k-1)-itemset phổ biến Lk-1 (G; 0,50), (E; 0,70), (A; 0,80), (C; 0,80)}; C1 = Đầu ra: Tập ứng viên k-itemset Ck {, , , , , , , 3: For each (k-1)-subset s of c do }; 4: If (s  Lk-1) then Bước lặp k = 2: sinh tập ứng viên 2-itemset C2 = {FG, FE, 5: Ck = Ck - c FA, FC, GE, GA, GC, EA, EC, AC}; C 2 ={, , , , , , Vì vậy, trong quá trình đi tìm tập ứng viên, thuật toán chỉ cần , ; tập phổ biến L2 = không cần dùng đến tất cả tập ứng viên (cho đến thời điểm {(FA; 0,30), (FC; 0,30), (GE; 0,30), (GA; 0,50), (GC; 0,50), đó). Nhờ vậy, bộ nhớ đƣợc giải phóng đáng kể. (EA; 0,50), (EC; 0,50), (AC; 0,80)}; Nhược điểm: Thuật toán phải quét dữ liệu (maxlen+1) lần, Bước lặp k = 3: sinh ứng viên 3-itemset C3 = {FAC, GEA, với maxlen là chiều dài của itemset phổ biến dài nhất. Thuật toán Apriori giảm không gian dựa vào tính chất Apriori. Tuy GEC, GAC, EAC}; C 3 ={, , , , , , }; tập phổ biến L3 = {(FAC; 0,30), (GEA; 0,30), Trong công trình [2], Agrawal cùng đồng sự đề xuất thêm (GEC; 0,30), (GAC; 0,50), (EAC; 0,50)}; thuật toán cải tiến AprioriTID – độ phổ biến của ứng viên tiềm Bước lặp k = 4: sinh ứng viên 4-itemset C4 = {GEAC}; năng đƣợc tính dựa trên tập C k (lƣu trữ từng dòng giao dịch C 4 ={, , }; có chứa các ứng viên k-itemset theo cấu trúc ). tập phổ biến L4 = {(GEAC; 0,30)}; Một số ký hiệu trong thuật toán AprioriTID: Kết quả khai thác tập phổ biến trên dữ liệu giao dịch T, với Lk: tập chứa k-itemset phổ biến; ngƣỡng minsup = 0,30 đƣợc trình bày ở Bảng 4. Bảng 4. FIs trên dữ liệu giao dịch T, minsup = 0,30 Ck: tâp ứng viên tiềm năng k-itemset; Items Tập phổ biến FIs (#FIs = 19) C k : tập các ứng viên k-itemset đƣợc chứa trong từng giao dịch t của DLGD; F (F; 0,30), (FA; 0,30), (FC; 0,30), (FAC; 0,30) Mã giả thuật toán AprioriTID (G; 0,50), (GE; 0,30), (GA; 0,50), (GC; 0,50), Đầu vào: Tập giao dịch Ƭ, ngƣỡng minsup G (GEA; 0,30),(GEC; 0,30), (GAC; 0,50), (GEAC; 0,30) Đầu ra: Tập kết hợp nối liền phổ biến FI E (E; 0,70), (EA; 0,50), (EC; 0,50), (EAC; 0,50) 1: L1 = {1-itemset} 2: C1 = tập giao dịch Ƭ// chứa các item trong L1 A (A; 0,80), (AC; 0,80) 3: For (k = 2; Lk-1   ; k++) do C (C; 0,80) 4: Ck = AprioriGen(Lk-1) 5: Ck =  III. THUẬT TOÁN DFS-APRIORI 6: For each t  C k 1 do A. Thuật toán DFS-Apriori 7: Ct = {c  Ck| (c – c[k])  t.set-of-itemset Phần này, nhóm tác giả trình bày thuật toán DFS-Apriori  (c – c[k-1])  t.set-of-itemset} hiệu quả khai thác tập phổ biến, cải tiến từ thuật toán Apriori 8: For each c  Ct do và dễ dàng mở rộng trên các hệ thống tính toán phân tán: 9: c.count ++ Thứ nhất, sắp xếp các item theo thứ tự tăng dần của độ phổ 10: If (Ct  ) then biến – sử dụng tính chất 3 cho việc rút gọn các kết hợp ở bƣớc 11: tiếp theo (item đầu tiên trong các kết hợp là item có độ phổ C k += biến nhỏ nhất). 12: Lk = {c  Ck| c.count  minsup} Thứ hai, cải tiến thủ tục AprioriGen sinh các ứng viên 13: Trả về FI= k Lk bằng cách sắp xếp các (k-1)-itemset phổ biến theo thứ tự và Để thuận tiên cho việc minh họa thuật toán AprioriTID, sinh các kết hợp mới giúp giảm dƣ thừa và trùng lặp. nhóm tác giả hiệu chỉnh ở dòng 2 so với phiên bản gốc Thứ ba, thực hiện tính độ phổ biến cho các ứng viên tiềm ( C1 chứa các item có trong L1 thỏa ngƣỡng minsup). năng C theo nhóm item đầu dựa trên ma trận bit Ƭ tƣơng ứng đƣợc rút gọn theo cột occ (vector giao dịch chứa item thứ i). C. Minh họa thuật toán AprioriTID Một số ký hiệu trong thuật toán DFS-Apriori: Trong phần này, nhóm tác giả minh họa thuật toán - L: tập thành viên chứa k-itemset thỏa minsup, mỗi thành AprioriTID khai thác các itemset phổ biến: viên có 4 trƣờng thông tin là itemset và độ phổ biến sup, Ví dụ 2: Cho dữ liệu giao dịch T trong Bảng 1 và giá trị bổ sung thêm thứ tự nhỏ nhất (min) và lớn nhất (max) của ngƣỡng minsup = 0,30. item trong mỗi itemset thuộc Lk; ISBN 978-604-80-7468-5 137
Hội nghị Quốc gia lần thứ 25 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2022) - C: tập ứng viên chứa k-itemset tiềm năng, mỗi ứng viên Theo Ví dụ 2, tập giao dịch Ƭ trong Bảng 2 và giá trị có 4 trƣờng thông tin là itemset biểu diễn dạng bit, độ phổ ngƣỡng minsup = 0,30. biến sup, thứ tự nhỏ nhất (min) và lớn nhất (max) của item Bảng 5. Tập giao dịch T đã rút gọn – loại bỏ t3 và t6 trong mỗi itemset thuộc C; TID F G E A C min max |t| occ - Ƭ: tập giao dịch đƣợc biểu diễn dạng bit, mỗi giao dịch t10 1 1 1 1 1 1 5 5 1 dạng bit có thêm 3 trƣờng thông tin là |t| số lƣợng items t1 1 0 1 1 1 1 5 4 1 trong giao dịch, thứ tự nhỏ nhất (min) và lớn nhất (max) là t4 1 1 0 1 1 1 5 4 1 thứ tự item đầu, cuối trong giao dịch. t5 0 1 1 1 1 2 5 4 0 Mã giả thuật toán DFS-Apriori t9 0 1 1 1 1 2 5 4 0 Đầu vào: Tập giao dịch Ƭ, ngƣỡng minsup t2 0 1 0 1 1 2 5 3 0 Đầu ra: Tập phổ biến FI 1: L1 = {1-itemset}; // các item thỏa minsup t7 0 0 1 1 1 3 5 3 0 2: Ƭ = tập Ƭ chỉ chứa các item có trong L1 và có |t| > 1 t8 0 0 0 1 1 4 5 2 0 //Ƭ biểu diễn dạng bit và có thứ tự theo |t|, min, max Dữ liệu Ƭ đƣợc sắp xếp theo |t|, min, max và cột occ đƣợc 3: L2 = {L1L1}//2-itemset thỏa minsup cập nhật theo vector của item F: {1, 1, 1, 0, 0, 0, 0, 0}. Dòng 1, xét các item thỏa minsup = 0,30: có 5 items {F, G, 4: FI = L1  L2 E, A, C} đƣợc sắp tăng dần theo độ phổ biến và gán lần lƣợt 5: For (i = 1; i < |L1|; i++) //xét item thỏa minsup thứ tự từ 1 đến 5; 6: L = {  L2| .min == i} //nhóm item thứ i Dòng 2, sinh tập phổ biến 1-itemset L1 = {(F; 0,30), (G; 7: Cập nhật vector occ tƣơng ứng với item thứ i 0,50), (E; 0,70), (A; 0,80), (C; 0,80)}; 8: k = 3// sinh 3-itemset Xét item F: sinh 4 ứng viên 2-itemset C2[F] = {FG, FE, FA, 9: While (|L| > 1) do //sinh itemset phổ biến FC}; tập chứa 2-itemset phổ biến L2[F] = {(FA; 0,30), (FC; 10: C = AprioriGenStar(L) 0,30)}; sinh 1 ứng viên 3-itemset C3[F] = {FAC}; tập chứa 3- 11: For each c  C do //tính sup theo nhóm giao dịch itemset phổ biến L3[F] = {(FAC; 0,30)}. 12: j=1 Xét item G: cập nhật vector cột occ = {1, 0, 1, 1, 1, 1, 0, 0}; 13: While (k  t[j].|t|  t[j].min  c.min)//t  Ƭ sinh 3 ứng viên 2-itemset C2[G] = {GE, GA, GC}; tập chứa 2- 14: If (occ[j]==1  c.max t[j].max) then itemset phổ biến L2[G] = {(GE; 0,30), (GA; 0,30), (GC; 0,30)}; 15: If (c.itemset==c.itemset AND t[j].itemset) then sinh 2 ứng viên 3-itemset C3[G] = {GEA, GEC, GAC}; tập chứa 16: c.sup += 1/n 3-itemset phổ biến L3[G] = {(GEA; 0,30), (GEC; 0,30), (GAC; 17: j++ 0,50)}; sinh 1 ứng viên 4-itemset C4[G] = {GEAC}; tập chứa 4- itemset phổ biến L4[G] = {(GEAC; 0,30)}. 18: Lnext = {c  C| c.sup  minsup}//lọc ứng viên thỏa Xét item E: cập nhật vector cột occ = {1, 1, 0, 1, 1, 0, 1, 0}; 19: FI = FI  Lnext sinh 2 ứng viên 2-itemset C2[E] = {EA, EC}; tập chứa 2-itemset 20: L = Lnext phổ biến L2[E] = {(EA; 0,50), (EC; 0,50)}; sinh 1 ứng viên 3- 21: k++ itemset C3[E] = {EAC}; tập chứa 3-itemset phổ biến L3[E] = 22: Return FI {(EAC; 0,50)}. Mô tả thuật toán DFS-Apriori: Xét item A: cập nhật vector cột occ = {1, 1, 1, 1, 1, 1, 1, 1}; Dòng 1 và 2, sinh tập L1 chứa các item thỏa ngƣỡng minsup sinh 1 ứng viên 2-itemset C2[A] = {AC}; tập chứa 2-itemset phổ và rút gọn tập giao dịch biểu diễn dạng bit (loại bỏ các giao biến L2[A] = {(AC; 0,80)}. dịch chỉ có 1 item). Dòng 3, sinh tập phổ biến L2. Dòng 6, lọc Kết quả khai thác tập phổ biến đƣợc trình bày ở Bảng 4 các 2-itemset phổ biến theo nhóm item thứ i; dòng 7 – cập (19 itemset phổ biến: 4 itemset đƣợc khai thác theo chiều sâu nhật vector occ theo item thứ i, đây là dạng chỉ mục trong từ item F; 8 itemset từ item G; 4 itemset từ item E; 2 itemset từ phép đếm độ phổ biến. Từ dòng 9 đến dòng 21, khai thác theo item A và 1 itemset từ item C). chiều sâu theo item thứ i. Lặp lại dòng 5, sinh itemset phổ biến tiếp theo item thứ i kế tiếp. C. So sánh ứng viên tiềm năng và số giao dịch duyệt của 2 Mã giả thủ tục AprioriGenStar thuật toán Apriori và DFS-Apriori Đầu vào: Tập chứa các k-itemset phổ biến Lk Bảng 6. Số ứng viên và duyệt giao dịch theo Ví dụ 2 Đầu ra: Tập ứng viên Ck+1 AprioriTID DFS-Apriori 1: Ck+1 =  Lần lặp k Số Số giao Items Số Số giao 2: For (i = 1; i < |Lk| ; i++) do ứng viên dịch duyệt ứng viên dịch duyệt 3: For (j = i+1; j  |Lk| ; j++) do 2 10 340 F 5 15 3 28 90 G 7 34 4: Ck+1 = Ck+1  {Xi  Xj|{Xi  Xj}  Ck+1} 4 10 3 E 3 15 5: Trả về Ck+1 A 1 8 Thủ tục AprioriGenNew chỉ sinh các ứng viên từ tập phổ 5 0 0 C 0 0 biến k-itemset riêng biệt nhóm theo item (chiến lƣợc tìm kiếm Tổng: 48 433 Tổng: 16 72 theo chiều sâu) – độ phức tạp giảm đáng kể. Bảng 6, cho thấy tổng số ứng viên tiềm năng của thuật B. Minh họa thuật toán DFS-Apriori toán DFS-Apriori thấp hơn 66,67% so với AprioriTID và tổng Trong phần này, nhóm tác giả minh họa thuật toán DFS- số dòng giao dịch đƣợc duyệt thấp hơn 83,37%. Qua đó, cho Apriori khai thác tập phổ biến trên DLGD, cho thấy thuật toán thấy thuật toán DFS-Apriori khả thi và hiệu quả hơn so với cải tiến hiệu quả. thuật toán AprioriTID. ISBN 978-604-80-7468-5 138
Hội nghị Quốc gia lần thứ 25 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2022) IV. KẾT QUẢ THỰC NGHIỆM Thực nghiệm trên máy tính Core Duo 2.0 GHz, 4GB RAM, thuật toán cài đặt trên MSVC# 2010. A. Mô tả dữ liệu thực nghiệm Nghiên cứu thực nghiệm trên 2 nhóm dữ liệu:  Nhóm dữ liệu thực có mật độ dày: 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 Chess và Mushroom.  Nhóm dữ liệu giả lập có mật độ thưa: sử dụng phần Hình 2. Thời gian thực hiện khai thác FI trên Mushroom 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 T10I4D100K và T40I10D100K. Bảng 7. Dữ liệu thực nghiệm Số Số Số item trung Mật Dữ liệu item giao dịch bình/giao dịch độ (%) Chess 75 3.196 37 49,3 Mushroom 119 8.142 23 19,3 T10I4D100K 870 100.000 10 1,1 T40I10D100K 942 100.000 40 4,2 Bảng 7, mô tả 4 tập dữ liệu sử dụng trong thực nghiệm, Hình 3. Thời gian thực hiện khai thác FI trên T10I4D100K gồm các thông số nhƣ số lƣợng các item, số lƣợng giao dịch, số item trung bình trên mỗi giao dịch và mật độ của từng tập dữ liệu. B. Thực nghiệm Để đánh giá mức độ hiệu quả của thuật toán DFS-Apriori, chúng tôi so sánh thuật toán DFS-Apriori khai thác tập phổ biến trên DLGD với thuật toán AprioriTID [2] đƣợc cải tiến theo dạng bit. Cả hai thuật toán đều cho cùng kết quả trên các ngƣỡng minsup khác nhau. Hình 4. Thời gian thực hiện khai thác FI trên T40I10D100K Hình 3 và 4 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 DFS-Apriori nhanh hơn thuật toán AprioriTID-bit. Hiệu suất của thuật toán DFS- Apriori rất cao so với AprioriTID-bit trên dữ liệu thƣa. Kết quả thực nghiệm, cho thấy thuật toán cải tiến DFS- Apriori hiệu quả hơn thuật toán AprioriTID-bit. Ngoài ra, thuật toán cũng cần thực nghiệm so sánh thêm với các thuật toán theo hƣớng tiếp cận theo chiều sâu (Depth First Search - DFS), cùng với nhiều tập dữ liệu khác và mở rộng trên môi trƣờng Hình 1. Thời gian thực hiện khai thác FI trên Chess tính toán phân tán. Hình 1 và 2 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 DFS-Apriori nhanh hơn thuật V. KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN toán AprioriTID-bit. Trong bài viết này, nhóm tác giả đề xuất tiếp cận mới trong cải tiến hiệu quả thuật toán Apriori áp dụng chiến lƣợc tìm kiếm theo chiều sâu: Thứ nhất, rút gọn hiệu quả không gian sinh các ứng viên k-itemset từ tập (k-1)-itemset phổ biến; Thứ hai, ở mỗi bƣớc tính độ phổ biến của ứng viên k-itemset chỉ ISBN 978-604-80-7468-5 139
Hội nghị Quốc gia lần thứ 25 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2022) xem xét các giao dịch dạng bit có chứa item đầu tiên (item có [9] W. Yu, X. Wang, F. Wang, E. Wang, B. Chen. Notice of Retraction: The sup nhỏ nhất); Thứ ba, sau mỗi bƣớc khai thác k-itemset phổ research of improved apriori algorithm for mining association rules. 11th IEEE Inter Conf on Communication Technology, (2008), 513-516. biến thì tập dữ liệu dạng bit đƣợc giới hạn dựa vào số item có [10] Y. Guo, Z. Wang. A vertical format algorithm for mining frequent trong giao dịch. Về mặt thời gian thực hiện, thuật toán DFS- itemsets. 2nd International Conference on Advanced Computer Control, Apriori hiệu quả hơn so với thuật toán cải tiến AprioriTID-bit. 4,(2010) 11-13. Tuy nhiên, nhóm tác giả chƣa thực hiện so sánh với các thuật [11] J. Singh, H. Ram. Improving Efficiency of Apriori Algorithm Using toán cải tiến dựa theo Apriori gần đây. Mặc dù vậy, kết quả và Transaction Reduction. Inte Journal of Scientific and Research kiến trúc của thuật toán cho thấy đây là thuật toán triển vọng, Publications, 3(1), (2013), 1-4. có khả năng mở rộng trên môi trƣờng phân tán. [12] H. Singh, R. Dhir. A New Efficient Matrix Based Frequent Itemset Mining Algorithm with Tags. Inter Journal of Future Computer and Nghiên cứu tiếp theo của nhóm tác giả là so sánh DFS- Communication, (2013), 355-358. Apriori với các thuật toán cải tiến khác và tiến hành nghiên cứu [13] M. A. Maolegi, B. Arkok. An Improved Apriori Algorithm for Association mở rộng thuật toán trên môi trƣờng phân tán xử lý dữ liệu lớn. Rules. International Journal on Natural Language Computing (IJNLC) , 3(1), (2014), 21-29. TÀI LIỆU THAM KHẢO [14] V. Vijayalakshmi, A. Pethalakshmi. An Efficient Count Based Transaction Reduction Approach for Mining Frequent Patterns. Procedia [1] R. Agrawal, T. Imilienski, A. Swami. Mining association rules between Computer Science, 47, (2015), 52-61. sets of large databases. Proc of the ACM SIGMOD Int Conf on Management of Data, Washington, DC, (1993), 207-216. [15] S. Aditya, M. Hemanth, C.K. Lakshmikanth, K. Suneetha. Effective algorithm for frequent pattern mining. 2017 Inter Conf on Energy, [2] R. Agrawal, R. Srikant. Fast Algorithms for Mining Association Rules in Large Databases. VLDB 1994, (1994), 487-499. Communication, Data Analytics and Soft Computing (ICECDS), (2017), 704-708. [3] R. Agrawal, R. Srikant. Mining sequential patterns. Proceedings of the Eleventh International Conference on Data Engineering, (1995), 3-14. [16] L. Xu, L. Qiao, F. Zhao, B. Yang, Q. Wang, P. Ding, L. Li. Improvement and Application of Apriori Algorithm Based on Equalization. IEEE [4] C.L. Carter, H.J. Hamilton, N. Cercone. Share Based Measures for Fourth International Conference on Data Science in Cyberspace (DSC), Itemsets. PKDD1997, (1997), 14-24 (2019), 635-641. [5] A. Inokuchi, T. Washio, H. Motoda. An Apriori-Based Algorithm for [17] H. Qiu, G. Rong, C. Yuan, Y. Huang. YAFIM: A Parallel Frequent Mining Frequent Substructures from Graph Data. PKDD’00, Itemset Mining Algorithm with Spark. IEEE Inter Parallel & Distributed 1910,(2000), 13-23 Processing Symposium Workshops, (2014), 1664-1671. [6] G. C. Lan, T. P. Hong, H. Y. Lee, and C. W. Lin. Mining Weighted [18] S. Rathee, M. Kaul, A. Kashyap. R-Apriori: an efficient apriori based Frequent Itemsets. Proceedings of the 30th workshop on Combinatorial algorithm on spark. In: Proceedings of the 8th workshop on Ph.D. Mathematics and Computation Theory (Alg’30), (2013), 85-89. workshop in information and knowledge management. ACM, (2015), 1-8. [7] A. Savasere, E. Omiecinski, S.B. Navathe. An Efficient Algorithm for [19] S. Raj, D. Ramesh, M. Sreenu, K.K. Sethi. EAFIM: efficient apriori- Mining Association Rules in Large Databases. VLDB, (1995), 432-444. based frequent itemset mining algorithm on Spark for big transactional [8] J. Lei, B. Zhang, L. Jianhua. A New Improvement on Apriori Algorithm. data. Knowledge and Information Systems, 62, (2020), 3565-3583. 2006 International Conference on Computational Intelligence and Security 1, (2006): 840-844. ISBN 978-604-80-7468-5 140