- Trang Chủ
- Cơ sở dữ liệu
- Tổng luận về khai thác song song tập phổ biến từ dữ liệu giao dịch trên bộ xử lý đa nhân
Xem mẫu
- Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020)
Tổng Luận về Khai Thác Song Song Tập Phổ Biến
từ Dữ Liệu Giao Dịch trên Bộ Xử Lý Đa Nhân
Phan Thành Huấn1,2 , Lê Hoài Bắc3
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
Khoa Công nghệ Thông tin, Trƣờng Đại học Khoa học Tự nhiên, ĐHQG.HCM-VN
Email: huanphan@hcmussh.edu.vn, lhbac@fithcmus.edu.vn
Tóm tắt - Trong gần ba mươi năm qua, khai thác luật kết hợp gian trong khai thác tập phổ biến, nhiều nhà nghiên cứu đã đề
luôn được nhiều nhà nghiên cứu quan tâm và đề xuất nhiều thuật xuất thuật toán khai thác hiệu quả tập phổ biến dựa vào các
toán hiệu quả cho bài toán tìm kiếm các mối tương quan tiềm ẩn cấu trúc lƣu trữ rút gọn không gian tìm kiếm nhƣ SE-Tree,
giữa các item trong dữ liệu. Cùng với sự bùng nổ của dữ liệu lớn Prefix-Tree, IT-Tree, FP-Tree,… Tuy nhiên, trong thực tế việc
và phát triển vượt bậc của kỹ thuật phần cứng, một số nhà phát sinh tập phổ biến tốn nhiều thời gian và có số lƣợng
nghiên cứu đã nâng cao hiệu năng khai thác luật kết hợp bằng itemset rất lớn. Vì vậy, một số nhà nghiên cứu đã đề xuất khai
cách sử dụng môi trường tính toán song song trên các bộ xử lý đa thác tập phổ biến đóng CFI (Closed Frequent Itemset) có số
nhân – giúp giảm thiểu thời gian khai thác đáng kể. Trong bài lƣợng ít hơn tập phổ biến nhƣ thuật toán A-Close [4], Charm
viết này, chúng tôi khảo sát và tổng luận về một số thuật toán
khai thác song song tập phổ biến (bước quan trọng của khai thác [5], ... Song song đó, một số nhà khoa học khác cũng đề xuất
luật kết hợp) trên bộ xử lý đa nhân. Điều này giúp các nhà khai thác tập phổ biến tối đại MFI (Maximal Frequent
nghiên cứu có sự lựa chọn giải pháp kỹ thuật phù hợp khi cần Itemset) nhƣ thuật toán Pincer-Search [6], Mafia [7], …
nâng cao hiệu năng trong khai thác dữ liệu lớn. Sau cùng, chúng Ở một số ứng dụng thực tế, việc sử dụng các tập FI, CFI
tôi đưa ra khuyến nghị và định hướng nghiên cứu của nhóm và MFI tốn rất nhiều chi phí tính toán cũng nhƣ s ố lƣợng
trong sự gia tăng như vũ bão của dữ liệu thu thập. itemset phổ biến rất lớn. Bayardo đề xuất khai thác tập phổ
biến có chiều dài tối đa LFI (Maximu m Length Frequent
Từ khóa – bộ xử lý đa nhân, khai thác song song, luật kết hợp, Itemset) đây là tập con của tập phổ biến FI và chỉ chứa các
tập phổ biến. itemset phổ biến có chiều dài tối đa nhƣ thuật toán Max-Miner
[8], DepthProject [9], ...
I. GIỚI THIỆU Năm 1995, Park đã phát triển thuật toán PDM [10] tựa
Apriori chạy trên hệ thống tính toán phân tán (HT3PT) để
Khai thác luật kết hợp là một kỹ thuật quan trọng trong lĩnh nâng cao hiệu năng khai thác dữ liệu. Những năm sau: Zaki,
vực khai thác dữ liệu. Mục tiêu khai thác là phát hiện những Agrawal và Han cũng lần lƣợt đề xuất các thuật toán CCPD
mố i tƣơng quan giữa các item trong tập dữ liệu. Năm 1993, [11], AprioriHybrid [12] và IDD [13] theo hƣớng tiếp cận tựa
Agrawal và đồng sự đề xuất mô hình đầu tiên của bài toán khai Apriori. Năm 1997, Zaki đã đề xuất thuật toán Par-Eclat [14]
thác luật kết hợp là mô hình nhị phân hay còn gọi là mô hình khai thác luật kết hợp trên HT3PT theo hƣớng tiếp cận trên
cơ bản, phân tích dữ liệu giao dịch, phát hiện các mối tƣơng cấu trúc dàn (lattice). Đến năm 2003, Chung dựa trên thuật
quan giữa các mặt hàng đã bán tại các siêu thị. Từ đó có kế toán Max-Miner [8] của Bayardo và hiệu chỉnh thực hiện trên
hoạch bố trí, sắp xếp, kinh doanh hợp lý, đồng thời tổ chức sắp HT3PT gọi là thuật toán Par-MaxMiner. Tuy nhiên, các
xếp các quầy gần nhau nhƣ thế nào để có doanh thu trong các HT3PT tồn tại hạn chế lớn là phụ thuộc vào đƣờng truyền trao
phiên giao dịch là lớn nhất. Ngoài ra, có thể áp dụng tri thức đổi thông tin giữa các máy tính. Năm 2004, Javed đề xuất
này để dự đoán số lƣợng các mặt hàng đƣợc bán chạy nhất thuật toán PFP [16] dựa trên cấu trúc FP-Tree để khai thác
trong thời gian sắp tới. Tổng hợp các tri thức này để lên kế song song tập phổ biến trên máy tính có nhiều Bộ xử lý
hoạch cho hoạt động, sản xuất, kinh doanh một cách thuận tiện (BXL), các thuật toán này cũng tồn tại hạn chế về độ trễ cao
hơn nhằm giảm bớt thời gian thống kê, tìm hiểu thị trƣờng,... khi các BXL cần giao tiếp. Năm 2005, Intel đã cho ra đời thế
Các thuật toán tuần tự đƣợc đề xuất cho khai thác luật kết hệ BXL chứa nhiều nhân xử lý (BXLĐN), kéo theo nhiều
hợp chia thành 2 pha [1-9]: công trình khai thác hiệu quả tập phổ biến trên BXLĐN nhƣ
FP-array [17], PLCM [20],… cho đến nay.
Pha 1: Tìm tất cả các kết hợp thỏa ngƣỡng phổ biến tối Phần 2, bài báo trình bày các khái niệm cơ bản về khai thác
thiểu minsup - pha tốn khá nhiều thời gian xử lý; luật kết hợp, tập phổ biến, thuật toán Apriori và tính toán hiệu
Pha 2: sinh luật kết hợp lần lƣợt từ các kết hợp thỏa minsup năng cao. Phần 3, khảo sát về một số thuật toán khai thác song
ở pha 1 và các luật kết hợp này phải thỏa ngƣỡng tin cậy tối song tập phổ biến trên BXLĐN trong nhiều năm qua theo
thiểu minconf. hƣớng tiếp cận sử dụng cấu trúc dữ liệu và chiến lƣợc tìm kiếm
tƣơng ứng. Tổng luận về một số thuật toán khai thác song song
Agrawal đã đề xuất thuật toán Apriori [1] - khai thác tập
tập phổ biến trên BXLĐN trong phần 4; kết luận và hƣớng phát
phổ biến FI (Frequent Itemset), thuật toán quét dữ liệu nhiều
triển đƣợc trình bày trong phần 5.
lần và có độ phức tạp dạng hàm mũ . Để cải tiến về mặt thời
ISBN: 978-604-80-5076-4 296
- Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020)
II. CÁC KHÁI NIỆM CƠ BẢN m
l ClmCrm l 3m 2m 1 1
m l
r
(2)
Hầu hết các thuật toán khai thác luật kết hợp đã đề xuất
A. Khai thác luật kết hợp đều tập trung kỹ thuật cải tiến ở Pha 1 (xác định các kết hợp
Cho I = {i1 , i2,..., i m } là tập gồ m m thuộc tính, mỗ i thuộc thỏa minsup). Tất cả thuật toán này cho rằng Pha 1 chiếm
tính gọi là item. Tập các item X ={i1 , i 2,..., i k}, ij I (1 j k) nhiều thời gian trong cả quá trình khai thác luật kết hợp. Tuy
gọi là itemset, itemset có k item gọi là k-itemset. Ɗ là dữ liệu nhiên, theo phân tích ở trên thì Pha 2 là phức tạp hơn và có
giao dịch, có n bản ghi phân biệt gọi là tập các giao dịch T = không gian sinh lớn; hay nói khác hơn là thuật toán 1 thì pha
{t1 , t 2,..., t n }, mỗi giao dịch t k ={i k1 , ik2,..., ikm }, ikj I (1 k j m). nào cũng cần thiết cải tiến và nâng cao hiệu năng tính toán.
Định nghĩ a 1: Cho X, Y I với X Y = , luật kết hợp là Chẳng hạn nhƣ: ta có itemset X={A, B, C}, m = 3 th ì tổng số
một mệnh đề kéo theo có dạng X Y, thỏa hai ngưỡng độ đo luật kết hợp sinh ra từ itemset X đƣợc tính là
cho trước (minsup – độ phổ biến tối thiểu; minconf – độ tin C13 C22 C12 C23 C11 3 1 2 3 1 12 , nghĩa là với itemset
cậy tối thiểu), trong đó X gọi là tiền đề và Y là kết luận.
X có 3 item thì cần xem xét 12 luật kết hợp có thỏa ngƣỡng
Định nghĩ a 2 : Độ phổ biến (support) của itemset X I, ký minconf hay không. Tƣơng tự, nếu itemset X có 4 item (m = 4)
hiệu sup(X) - tỷ lệ giữa số giao dịch trong Ɗ có chứa X và n thì cần xem xét 50 luật kết hợp thỏa minconf. Ngoài ra, phân
giao dịch. tích trên cũng cho ta thấy rõ về không gian tìm kiếm ở cả 2
Định nghĩa 3: Độ phổ biến của luật kết hợp X Y, ký pha đều không phụ thuộc vào số lượng giao dịch của dữ liệu
hiệu sup(X Y) - tỷ lệ giữa số giao dịch trong Ɗ chứa {X Ɗ, mà ch ỉ phụ thuộc vào số lƣợng item (thuộc tính) của dữ
Y} và n giao dịch. liệu khai thác.
Định nghĩ a 4 : Độ tin cậy (confident) của luật kết hợp X Bảng 1. Ƣớc tính không gian sinh các kết hợp
Y, ký h iệu conf(X Y) - tỷ lệ giữa số giao d ịch chứa {X Y} và số lƣợng luật kết hợp đƣợc sinh từ m-itemset
và số giao dịch chứa X trong Ɗ. m 10 20 30 40 50 60 70 80
Mã giả thuật toán 1: khai thác luật kết hợp P1 210 -1 220 -1 230 -1 240 -1 25 0 -1 260 -1 27 0 -1 28 0 -1
Đầu vào: Dữ liệu Ɗ, minsup, minconf P2 310 -211 +1 320 -221 +1 330 -231 +1 34 0 -241 +1 350 -25 1 +1 360 -261 +1 370 -271 +1 380 -28 1 +1
Đầu ra: Tập luật kết hợp thỏa minsup, minconf P2 /P1 57 3.325 191x10 3 11x10 6 637x10 6 36x10 9 2x10 12 122x10 12
1. FI = { }//tập chứa các kết hợp m
P1 : không gian sinh các kết hợp (2 – 1);
2. Với mỗi Z Ƥ 1(I), thực hiện: P2 : số lƣợng LKH đƣợc sinh từ m-itemset (3m – 2m+1 +1).
3. Nếu sup(Z) minsup thì Định nghĩ a 5 : Cho X I, X gọi là itemset phổ biến –
4. FI = FI Z nếu sup(X) ≥ minsup, trong đó minsup là ngƣỡng phổ biến tối
5. AR = { }//tập chứa luật kết hợp thiểu (do người dùng chỉ định). Ký h iệu FI là tập hợp chứa các
6. Với mỗi fi FI, thực hiện: itemset phổ biến.
7. Nếu conf(X {fi \ X}) minconf thì Định nghĩa 6: Cho X I, X đƣợc gọi là itemset phổ biến
8. AR = AR (X {fi \ X}) đóng – nếu X là i temset phổ b iến và không có tập cha cùng độ
9. Trả về AR phổ biến. Ký hiệu CFI là tập hợp chứa các itemset phổ biến
(Ƥ 1 (I): tất cả các powerset của I có ít nhất một item) đóng.
Thuật toán 1 đƣợc chia thành 2 pha Định nghĩa 7: Cho X I, X đƣợc gọi là itemset phổ biến
Pha 1: (dòng 1 đến 4) đây là pha tìm tất cả các kết hợp tối đại – nếu X là itemset phổ biến và không có tập cha là
thỏa ngƣỡng minsup; itemset phổ biến. Ký hiệu MFI là tập hợp chứa các itemset
Pha 2 : (dòng 5 đến 8) sinh các luật kết hợp lần lƣợt từ các phổ biến tối đại.
kết hợp thỏa minsup ở pha 1 và các luật kết hợp này phải thỏa Ngoài ra, kh i cần khai thác các luật kết hợp có số thuộc
tính nhiều nhất thì các nhà nghiên cứu còn đề xuất khai thác
ngƣỡng tin cậy tối thiểu minconf (luật kết hợp X {fi \ X} có
tập phổ biến có chiều dài tối đa – chính là tập con của tập phổ
tiền đề X và kết luận Y={fi \ X}, X Y = ).
biến tối đại và có chiều dài tối đa.
Phân tích không gian tìm kiếm thuật toán 1:
Pha 1: dữ liệu giao dịch Ɗ có | I | = m, tất cả các kết hợp Định nghĩa 8: Cho X FI, X đƣợc gọi là itemset phổ
đƣợc sinh từ I có ít nhất một item - Ƥ 1 (I), chúng ta có không biến có chiều dài tối đa nếu Y FI t h ì |X| |Y|, t ức là số
gian các kết hợp giữa các item đƣợc sinh ra từ m item là 2m – lƣợng item của it emset X lớn hơn hoặc bằng số lƣợng item
1, đây chính là không gian tìm kiếm ở pha 1 cho v iệc xác đ ịnh của bất kỳ itemset phổ biến có trong FI. Ký hiệu LFI là tập
các kết hợp thỏa ngƣỡng minsup. hợp chứa các itemset phổ biến có chiều dài tối đa.
Pha 2: sau kh i xác định đƣợc tập các kết hợp hay itemset Một số tính chất của itemset phổ biến: đây là các tính
thỏa minsup, pha này sinh luật kết hợp lần lƣợt từ các itemset. chất nền tảng sử dụng cho việc rút gọn không gian tìm kiếm –
các tính chất này đƣợc gọi là tính chất Apriori/ bao đóng giảm
Giả sử, cho itemset X có m item, l (1 l m) và r (1 r m-l)
(Downward Closure Property - DCP).
là số item ở tiền đề và kết luận. Khi đó, ta có Clm số cách chọn Tính chất 1: (độ phổ biến của tập con) Cho X, Y I, nếu X
tiền đề có l item trên m item từ itemset X và Crm l số cách chọn Y thì sup(X) sup(Y);
kết luận có r item trên (m-l) item còn lại từ itemset X. Dƣới Tính chất 2: Một itemset con khác rỗng của một itemset
đây là công thức tính số luật kết hợp đầy đủ đƣợc sinh từ phổ biến cũng là itemset phổ biến - X Y, sup(Y) ≥ minsup:
itemset X: sup(X) ≥ minsup;
m
l
m
r Cl Cr
m l m l
(1) Chứng minh: theo tính chất 1, ta có sup(X) sup(Y) và
sup(Y) minsup thì sup(X) minsup ■.
Áp dụng tam thức Newton, công thức (1) đƣợc viết lại:
ISBN: 978-604-80-5076-4 297
- Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020)
Tính chất 3: Một itemset chứa một itemset không phổ biến không vƣợt quá ngƣỡng 500.000 MIPS (triệu phép tính trên
cũng là itemset không phổ biến - X Y, sup(X) < minsup: giây) [41]. Để giải quyết các bài toán có khối lƣợng tính toán
sup(Y) < minsup. lớn đòi hỏi một giải pháp mới; đó chính là giải pháp (3).
Chứng minh: theo tính chất 1, ta có sup(Y) sup(X) và Chính động lực này đã thúc đẩy việc ra đời các hệ thống máy
sup(X) < minsup thì sup(Y) < minsup ■. tính có khả năng tính toán song song mạnh.
Các dạng bài toán trong tính toán hiệu năng cao:
B. Thuật toán Apriori - Nặng về Xử l ý (co mpute intensive) – Một bài toán duy
Thuật toán do Agrawal đề xuất năm 1993 [1], đƣợc đánh nhất đòi hỏi một lƣợng lớn tính toán;
giá mang tính chất lịch sử trong lĩnh vực khai thác luật kết - Nặng về Bộ nhớ (memo ry intensive) – Một bài toán
hợp, vì đã vƣợt xa tầm của các thuật toán quen thuộc trong duy nhất đòi hỏi một lƣợng lớn bộ nhớ;
lĩnh vực này. Apriori là thuật toán nền tảng để tìm các tập phổ - Nặng về Dữ liệu (data intensive) – Một bài toán duy
biến sử dụng phƣơng pháp sinh ứng viên. Thuật toán có đặc nhất hoạt động trên một tập dữ liệu lớn;
điểm là t ìm kiếm theo chiều rộng sử dụng tính chất Apriori: - Thông lượng cao (throughput intensive) – Nhiều bài
bất kỳ (k-1)-itemset không phổ biến thì nó không thể là tập con toán không liên quan đƣợc tính toán đồng loạt.
của k-itemset phổ biến. Định luật Amdahl:
Mã giả thuật toán 2: khai thác tập phổ biến Định luật g iả đ ịnh kích thƣớc bài toán là cố định và thời
Đầu vào: Dữ liệu Ɗ, minsup gian chạy của các phần tuần tự của chƣơng trình là độc lập với
Đầu ra: Tập FI chứa itemsets thỏa ngƣỡng minsup số lƣợng BXL. Nếu là tỷ lệ thời gian chạy của phần chƣơng
1. Sinh ứng viên Ck+1 từ k-itemset phổ biến; trình thực hiện tuần tự (không song song hóa đƣợc):
2. Quét dữ liệu - tính độ phổ biến của các ứng viên; 1
3. Thêm các ứng viên vào danh sách (k+1)-itemset. S (3)
Ưu điểm: Thuật toán dựa trên một nhận xét khá đơn giản
là bất kỳ itemset con nào của itemset phổ biến cũng là itemset S là tỷ lệ tối đa khi song song hóa toàn bộ chƣơng trình,
phổ biến (tính chất 2). Do đó, trong quá trình đi t ìm tập ứng cho dù có thêm vào bao nhiêu BXL. Điều này đặt ra một giới
viên, thuật toán chỉ dùng đến tập ứng viên vừa xuất hiện ở hạn về tính hữu ích khi gia tăng BXL.
bƣớc ngay trƣớc đó, không dùng đến tất cả tập ứng viên (cho Định luật Gustafson:
đến thời điểm đó). Nhờ vậy, bộ nhớ đƣợc giải phóng đáng kể. Định luật Gustafson là một nguyên lý khác trong tính toán,
Nhược điểm: Thuật toán phải quét dữ liệu (max+1) lần liên quan chặt chẽ đến định luật Amdahl. Mức độ tăng tốc
với max là ch iều dài của itemset phổ biến dài nhất. Thuật toán với P bộ xử lý là
Apriori giảm không gian dựa vào tính chất Apriori. Tuy nhiên, S (1 )P (4)
khi số itemset phổ biến đƣợc sinh ra lớn, max lớn hay minsup S tăng tuyến tính khi số lƣợng BXL tăng. Định luật
nhỏ sẽ dẫn đến việc phát sinh ra rất nhiều tập ứng viên và phải Gustafson cho thấy: sức mạnh song song thực sự của một hệ
duyệt dữ liệu rất nhiều lần, thuật toán có chi phí cao. Trong thống nhiều BXL chỉ có thể đạt đƣợc kh i phần lớn khối lƣợng
thực tế, cần phải sinh 2100 ứng viên (trong trƣờng hợp xấu công việc của bài toán đƣợc xử lý song song.
nhất) để tìm itemset phổ biến có kích thƣớc 100.
Từ những nhƣợc điểm trên, nhiều nhà nghiên cứu đã đề III. KHẢO SÁT MỘT SỐ THUẬT TOÁN KHAI THÁC
xuất các thuật toán tăng hiệu năng sinh các tập phổ biến dựa SONG SONG TẬP PHỔ BIẾN TRÊN BXLĐN
trên việc tổ chức lƣu trữ dữ liệu và các ch iến lƣợc tìm kiếm A. Khảo sát về cấu trúc dữ liệu và chiến lược tìm kiếm
hiệu quả tƣơng ứng.
Ngoài một số thuật toán có hƣớng tiếp cận theo Apriori,
C. Tính toán hiệu năng cao chúng tôi trình bày khảo sát các cấu trúc dữ liệu thông dụng
Trong thực tế có nhiều bài toán có độ phức tạp rất lớn mà đƣợc sử dụng bởi nhiều nhóm tác g iả cho việc lƣu trữ không
sức mạnh siêu máy t ính hiện tại cũng chƣa giải quyết đƣợc. Vì gian tìm kiếm trong quá trình khai thác song song tập phổ biến
vậy ngƣời ta gọi đây là các thách đố. Chúng ta có thể tham và các chiến lƣợc t ìm kiếm phù hợp cùng với không gian lƣu
khảo [38, 39] để h iểu hơn về các thách đố này. Hiện nay có rất trữ. Các chiến lƣợc tìm kiếm trên cấu trúc cây: tìm kiếm theo
nhiều lĩnh vực khoa học cần khoa học tính toán nhƣ hóa học, chiều sâu (Depth First Search - DFS), t ìm kiếm theo ch iều
vật lý hạt nhân, vũ trụ học, cơ lƣu chất, sinh học, y học… rộng (Breadth First Search - BFS) hoặc kết hợp cả hai ch iến
Khoa học tính toán giúp giải quyết nhiều vấn đề trên mô hình lƣợc trên.
toán để tiên đoán trƣớc kết quả thử nghiệm và nhƣ vậy g iúp 1) Cấu trúc dàn - Lattice
rút ngắn quá trình thử nghiệm. Nhiều bài toán cần giải quyết Đây là cấu trúc dữ liệu đƣợc sử dụng nhiều trong các thuật
trên môi trƣờng tính toán lƣới nhƣ trong [40] càng cho thấy sự toán đề xuất. Dữ liệu g iao dịch Ɗ có | I | = m, tất cả các kết
cần thiết của sức mạnh tính toán trong lĩnh vực khoa học và hợp (powerset) đƣợc sinh từ I - Ƥ(I), chúng ta có không gian
công nghệ phát triển . các kết hợp giữa các item đƣợc sinh ra từ m item là 2 m, đây
Nhằm đáp ứng yêu cầu t ính toán trong khoa học và công chính là không gian tìm kiếm đầy đủ.
nghệ, ba giải pháp đƣợc đề nghị: Năm 1999, Pasquier đề xuất thuật toán A-Close [4] dựa
1) Tăng tốc độ tính toán của bộ xử lý; trên cấu trúc dàn để khai thác tập phổ biến đóng (gần 2.000
2) Tìm một giải thuật tốt hơn để giải quyết; trích dẫn).
3) Sử dụng kỹ thuật xử lý song song. Chiến lược tì m kiếm trên dàn: kết hợp cả 2 chiều (Top-
Giải pháp (1) và (2) đòi hỏi nhiều thời gian để có kết quả Down và Bottom-Up).
cũng nhƣ có nhiều giới hạn. Theo công nghệ hiện nay, khả
năng của máy tính có một bộ xử lý đã đƣợc chứng minh là
ISBN: 978-604-80-5076-4 298
- Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020)
Hình 4. Cây IT -T ree
Chiến lược tìm kiếm: theo chiều sâu.
Hình 1. Cấu trúc dàn - Lattice Ưu điểm: đơn giản, đảm bảo khai thác đầy đủ tập phổ biến
và tính toán nhanh độ phổ biến;
Ưu điểm: tổ chức lƣu t rữ đơn giản, đảm bảo khai thác đầy Nhược điểm: mất cân bằng trong quá trình khai thác và
đủ tập phổ biến và phù hợp cho dữ liệu tăng trƣởng; lƣu trữ tốn nhiều bộ nhớ.
Nhược điểm: để lƣu trữ không gian kết hợp của m item thì 5) Cây FP-Tree (Frequent Pattern Tree)
cần 2m kết hợp - chiếm nhiều bộ nhớ trong quá trình khai thác. Năm 2000, Jiawei Han và đồng sự đã đề xuất cấu trúc FP-
2) Cây liệt kê - Set Enumeration Tree (SE-Tree) Tree [2] (gần 9.000 trích dẫn) và thuật toán FP-gro wth dùng
Năm 1989, Bayardo đề xuất thuật toán Max-Miner [8] dựa cho việc khai thác các itemset phổ biến. Đây là dạng cây mở
trên cây liệt kê (trên 2.000 trích dẫn) để khai thác tập phổ biến rộng từ Prefix-Tree, có thêm bảng header lƣu t rữ item, độ phổ
có chiều dài tối đa. Đây là dạng rút gọn của cấu trúc dàn. biến và liên kết đến nút trong cây. Từ đây, cấu trúc FP-Tree
đƣợc nhiều nhà nghiên cứu sử dụng và cải tiến.
Hình 5. Cây FP-T ree
Hình 2. Cây liệt kê - Set Enumeration T ree (SE-T ree) Mặc dù, cấu t rúc FP-Tree đƣợc rút gọn hơn so với các cấu
Chiến lược tìm kiếm: theo chiều sâu DFS. trúc trên, nhƣng FP-Tree là dạng mở rộng từ Prefix-Tree, nên
Ưu điểm: cây b iểu diễn rút gọn các liên kết của cấu trúc vẫn tồn tại nhiều hạn chế tƣơng tự nhƣ Prefix-Tree, nghĩa là
dàn, đảm bảo khai thác đầy đủ tập phổ biến; cây mất cân bằng.
Nhược điểm: mất cân bằng trong quá trình khai thác (phụ B. Một số thuật toán khai thác song song tập phổ biến trên
thuộc vào độ phổ biến của item). Bộ xử lý đa nhân
3) Cây tiền tố (Prefix – Tree)
Năm 2002, Liu đề xuất thuật toán OpportuneProject [3] dựa Trong phần này, chúng tôi khảo sát cả công trình khai thác
trên cấu trúc cây tiền tố (gần 300 trích dẫn) để khai thác nhanh tập phổ biến trên HT3PT (1995 – 2003) [10-15]; thuật toán
PFP [16] khai thác trên hệ thống nhiều BXL; cùng với sự phát
tập phổ biến.
triển mạnh mẽ về kỹ thuật phần cứng cho ra đời các BXL đa
nhân thì nhiều thuật toán nâng cao hiệu năng khai thác tập phổ
biến trên BXLĐN cũng đƣợc công bố nhƣ thuật toán FP-array
[17], PLCM [20],…
Bảng 2, t rình bày mốc thời g ian của một số thuật toán khai
thác song song tập phổ biến từ năm 1995 đến 2020, cùng với
hƣớng tiếp cận sử dụng cấu trúc dữ liệu và số trích dẫn của
công trình [10-37] (Park [10] đến Karthik [37]).
Bảng 2. T ổng hợp các công trình khai thác tập phổ biến song song
trên bộ xử lý đa nhân/ Grid
Tác giả Hướng #Trích
Thuật toán Xử lý Năm
đứng đầu tiế p cận dẫn
Hình 3. Cây tiền tố (Prefix-T ree) J. S. Park PDM Apriori Nodes 389 1995
Tƣơng tự nhƣ cây liệt kê, nội dung lƣu trữ đƣợc rút gọn M. J. Zaki CCPD Apriori Nodes 200 1996
thông qua tiền tố. R. Agarwal AprioriHybrid Apriori Nodes 1.734 1996
E. H. Han IDD Apriori Nodes 259 1997
4) Cây IT-Tree (Itemset Tidset Tree)
M. J. Zaki Par-Eclat Lattice Nodes 1.872 1997
Năm 1999, Zaki đề xuất thuật toán Charm [5] cùng với cấu S. M. Chung Par-MaxMiner SE-T ree Nodes 16 2003
trúc IT-Tree (Itemset Tidset Tree) tƣơng tự cấu trúc cây liệt kê A. Javed PFP FP-T ree Many CPU 99 2004
và kết hợp lƣu trữ mã giao dịch của itemset (1.500 trích dẫn). L. Liu FP-array FP-T ree CPU 148 2007
ISBN: 978-604-80-5076-4 299
- Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020)
Tác giả
Thuật toán
Hướng
Xử lý
#Trích
Năm
Tuy nhiên, hiệu năng của thuật toán LPAS tối đa chỉ nhanh
đứng đầu tiế p cận dẫn hơn MATI là 18,11%.
S. H. Adil Apriori* Apriori GPU 34 2009 Năm 2017, Jiang đề xuất thuật toán PFP-growth [32] khai
J. Zhou GPU-FPM Apriori GPU 52 2010
B. Negrevergne PLCM SE-T ree CPU 48 2010
thác song song tập phổ biến trên BXLĐN dựa trên thuật toán
H. Li MG SE-T ree GPU 14 2010 FP-gro wth; phần thực nghiệm trên GeFo rce GTX 980 Ti
G. T eodoro T reeProjection* SE-T ree CPU,GPU 27 2010 (2.816 CUDA cores) cho thấy thuật toán chƣa hiệu quả trên dữ
K. M. Yu MAT I Apriori CPU 20 2011 liệu có số lượng items lớn (dữ liệu thực mật độ thƣa Retail có
F. Zhang GPApriori Apriori GPU 61 2011 16.470 items, trung b ình 10 items/giao dịch và 88.162 g iao
C. Silvestri gpuDCI Lattice GPU 24 2012 dịch – kho dữ liệu UCI). Nhó m tác g iả chƣa quan tâm đến g iải
B. Missaoui P-ST M SE-T ree CPU 2 2013 pháp cân bằng tải. Song song đó, nhóm tác giả Wang đã đề
D. Nguyen PMCAR IT -Tree CPU 37 2014
xuất thuật toán D2P-Apriori [34]; phần thực nghiệm t rên
F. Wang GPU-FP-growth FP-T ree GPU 9 2014
B. Negrevergne ParaMiner Lattice CPU 56 2014
GeForce GTX 1080 (2.560 CUDA cores) với các ngƣỡng
K. M. Yu LPAS Apriori CPU 5 2015 minsup lớn - chƣa thể hiện rõ hiệu suất của thuật toán.
Ö. M. Soysal MASP Lattice CPU 6 2015 Năm 2019, Huan đã đề xuất thuật toán NPA-CFI [35] –
H. Jiang PFP-growth FP-T ree GPU 3 2017 thuật toán song song khai thác tập phổ biến đóng trên BXLĐN
K. W. Chon GMiner Apriori GPU 16 2018 theo hƣớng tiếp cận giải pháp (2). Thuật toán NPA-CFI, phân
Y. Wang D2P- Apriori Apriori GPU 1 2018 chia thành 3 Pha độc lập, tác vụ song song tự nhiên trên Pha 1
H. Phan NPA-CFI Prefix-Tree CPU 2019 và Pha 3. Điều này đã làm g ia tăng hiệu năng của thuật toán
Y. C. Wu GFPG-LLMA FP-T ree GPU 2019 đáng kể. Tuy nhiên, ở Pha 3 của thuật toán vẫn chƣa đề cập
P. Karthik Apriori Apriori GPU 2020
đến giải pháp cân bằng tải. Cùng thời điểm trên, Wu đề xuất
Bảng 2, cho chúng ta thấy các thuật toán khai thác song thuật toán GFPG-LLMA [36] – thực nghiệm trên GeForce
song tập phổ biến trên BXLĐN từ năm 2007 đến nay – ngoài
GTX 1070 (1.920 CUDA cores), h iệu suất chƣa cao và nhóm
các thuật toán dựa trên thuật toán Apriori, các thuật toán còn tác giả cũng bỏ ngỏ vấn đề cân bằng tải.
lại đều sử dụng 5 dạng cấu trúc dữ liệu đƣợc khảo sát ở trên
Nhìn chung, phần lớn các công trình nghiên cứu lựa chọn
(từ Hình 1 đến Hình 5).
giải pháp (3) cho bài toán khai thác song song tập phổ biến và
IV. TỔNG LUẬN MỘT SỐ THUẬT TOÁN KHAI THÁC chƣa thật sự quan tâm đến vấn đề cân bằng tải.
SONG SONG TẬP PHỔ BIẾN TRÊN BXLĐN C. Xác định tới hạn theo định luật Amdahl và Gustafson
Chúng tôi đã khảo sát gần 30 công trình nghiên cứu liên
A. Chiến lược tìm kiếm
quan khai thác song song tập phổ biến trên BXLĐN, chƣa
Khảo sát một số thuật toán ở phần 3, cho thấy: Ngoài các thấy công trình đề cập đến vấn đề tới hạn theo cả 2 định luật.
thuật toán tiếp cận tựa Apriori – áp dụng chiến lƣợc tìm kiếm
BFS. Phần lớn các thuật toán sử dụng cấu trúc cây – chiến lƣợc D. Đánh giá hiệu năng của giải thuật trên BXLĐN
tìm kiếm DFS. Giải thuật DFS thông thƣờng đƣợc thiết kế Các g iải thuật trên chƣa tính toán cụ thể hiệu suất khai thác
dạng hàm đệ quy, điều này dẫn đến những hạn chế khi thực tập phổ biến trên từng nhân xử lý (Core). Chúng tôi khảo sát
hiện trên BXLĐN – hệ thống dễ treo, khó mở rộng trên dữ liệu và chọn lựa phƣơng pháp tính hiệu năng [35] trên từng nhân
lớn. Vì vậy, cần có giải pháp biến DFS thành BFS hoặc sử xử lý theo phƣơng trình nhƣ sau:
dụng vòng lặp để khử đệ quy cho giải thuật này. Mặt khác, các TS TS
cấu trúc cây đƣợc khảo sát ở phần 3 đã thể hiện rõ tính mất cân HS 1 TM (5)
bằng của cây – Điều này, cho thấy trong các giải thuật khai c c
thác song song tập phổ biến cần quan tâm đến vấn đề cân bằng Trong đó:
tải trên các BXL để có một giải thuật thật sự hiệu quả. - TS : thời gian thực hiện tuần tự
- TM : thời gian thực hiện tính song song trên BXLĐN
B. Cân bằng tải (Load Balancing) cho tính toán song song - c: số lƣợng nhân của CPU (số core)
Trong gần 30 công trình đƣợc khảo sát, chúng tôi chỉ nêu Đây là cơ sở khi so sánh các giải thuật song song theo định
một số công trình tƣơng đối nổi bật: hƣớng của giải pháp (2) – tìm giải thuật tốt hơn.
Năm 1996, Zaki đề xuất thuật toán CCPD [11] khai thác
song song tập phổ biến trên hệ thống phân tán dựa trên thuật V. KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN
toán Apriori và Zaki đã đề xuất giải pháp cân bằng tải bằng Trong bài viết này, chúng tôi khảo sát và tổng luận về một
cách lƣợng giá công việc thực hiện trên mỗi itemset và chọn số thuật toán khai thác song song tập phổ biến trên BXLĐN
lƣợc đồ tốt nhất (ít mất cân bằng nhất) phân bổ vào các node theo hƣớng tiếp cận phân tích cấu trúc dữ liệu và chiến lƣợc
xử lý khác nhau. tìm kiếm trên không gian sinh, đƣợc sử dụng trong khai thác
Năm 2010, Yu đề xuất thuật toán MATI [23] và LPAS [30] song song tập phổ biến trong một số công trình suốt hơn hai
khai thác song song tập phổ biến trên BXLĐN dựa t rên thuật mươi năm qua. Qua đó, giúp các nhà nghiên cứu trong lĩnh vực
toán Apriori; nhóm tác g iả đã đề xuất giải pháp cân bằng tải khai thác dữ liệu có đầy đủ cở sở khi lựa chọn giải pháp kỹ
bằng cách đƣa ra khái niệm itemset-block ở bƣớc sinh k- thuật phù hợp cho bài toán khai thác song song tập phổ biến
itemset phổ biến (k > 1) theo item tiền tố; bƣớc sinh (k+1)- trên BXLĐN. Bên cạnh đó, tổng luận còn cho thấy chƣa có
itemset trên từng itemset-block . Yu đã cải tiến MATI bằng nhiều đề xuất quan tâm đến vấn đề cân bằng tải và một số công
cách sắp xếp thứ tự độ phổ biến khi phân chia itemset-block trình chỉ mang t ính thực nghiệm chuyển từ thuật toán tuần tự
đƣợc gọi là thuật toán LPAS. Yu đã thực nghiệm so sánh số sang môi trƣờng tính toán song song – giải pháp (3).
ứng viên sinh ra ở thuật toán LPAS giảm 29% so với MATI.
ISBN: 978-604-80-5076-4 300
- Hội nghị Quốc gia lần thứ 23 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2020)
Dựa trên các khảo sát và tổng luận một số thuật toán khai [19] J. Zhou, K. M. Yu*, B. C. Wu. Parallel Frequent Patterns Mining
thác song song tập phổ biến trên BXLĐN đƣợc trình bày ở Algorithm on GPU. IEEE International Conference on Systems Man and
Cybernetics (SMC2010), (2010), 435-440.
phần 3 và 4: Tƣơng lai, chúng tôi sẽ nghiên cứu tìm kiếm g iải
[20] B. Negrevergne, A. T ermier, J. F. Méhaut, T. Uno. Discovering Closed
thuật tốt hơn để có thể khai thác song song tập phổ biến trên dữ Frequent Itemsets on Multicore: Parallelizing Computations and
liệu giao dịch cỡ lớn, có trọng số, cũng nhƣ mở rộng trên các Optimizing Memory Accesses. HPCS’10 IEEE: (2010), 521–528.
hệ thống tính toán phân tán nhƣ Hadoop, Sprak…Ngoài ra, [21] H. Li, N. Zhang. Mining maximal frequent itemsets on graphics
chúng tôi cũng tập trung quan tâm đến việc tìm kiếm giải pháp processors. Fuzzy Systems and Knowledge Discovery (FSKD) 2010
cho vấn đề cân bằng tải để đảm bảo hiệu năng cao nhất khi Seventh International Conference on, vol. 3, (2010), 1461-1464.
thực hiện trên BXLĐN. [22] G. T eodoro, N. Mariano, J. W. Meira, R. Ferreira. Tree Projection-
Based Frequent Itemset Mining on Multicore CPUs and GPUs. 2010
LỜI CẢM ƠN 22nd Int Symposium on Computer Architecture and High Performance
Nghiên cứu đƣợc tài trợ bởi Viện Đào tạo và Nâng cao Computing, Petropolis, (2010), 47-54.
TP.HCM trong đề tài có mã số V2019.09. [23] K. M. Yu, S. H. Wu. An Efficient Load Balancing Multi-core Frequent
Patterns Mining Algorithm. 10th Int Conf on Trust, Security and Privacy
in Computing and Communications, Changsha, (2011), 1408-1412.
TÀI LIỆU THAM KHẢO [24] F. Zhang, Y. Zhang, J. Bakos. Gpapriori: Gpu-accelerated Frequent
Itemset Mining. Proc. of the 2011 IEEE International Conference on
[1] R. Agrawal, T. Imilienski, A. Swami. Mining association rules between
Cluster Computing, (2011), 590-594.
sets of large databases. Proceedings of the ACM SIGMOD International
Conference on Management of Data, Washington, DC, (1993), 207-216. [25] C. Silvestri, S. Orlando. gpuDCI: Exploiting GPUs in Frequent Itemset
Mining. Parallel Distributed and Network-Based Processing (PDP) 2012
[2] J. Han, J. Pei, Y. Yin. Mining Frequent Patterns without Candidate
20th Euromicro International Conference on, (2012), 416-425.
Generation. SIGMOD Conf. 2000, (2000), 1-12. (FP-tree,FI)
[26] B. Missaoui, K. Arour, Y. Slimani. Parallel Binary Approach for
[3] J. Liu, Y. Pan, K. Wang, J. Han. Mining frequent item sets by Frequent Itemsets Mining. International Journal of Computer and
opportunistic projection. KDD 2002, (2002), 229-238. (Prefix-Tree,FI) Communication Engineering, (2013), 230.
[4] N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal. Discovering frequent
[27] D. Nguyen, B. Vo, B. Le. Efficient strategies for parallel mining class
closed itemsets for association rules. Proceecings of the 5th Int Conf on
association rules. Expert Syst. Appl. 41(10): (2014), 4716-4729.
Database Theory, LNCS, Springer-Verlag, Jerusalem, Israel, (1999),
398–416. (lattice – Aclose) [28] F. Wang, B. Yuan. Parallel Frequent Pattern Mining without Candidate
Generation on GPUs. Data Mining Workshop (ICDMW) 2014 IEEE
[5] M.J. Zaki, C. J. Hsiao. CHARM: An Efficient Algorithm for Closed
International Conference on, (2014), 1046-1052.
Association Rule Mining. (1999), 1-20. (IT-Tree)
[29] B. Negrevergne, A. T ermier, M. C. Rousset, J. F. Méhaut. ParaMiner: A
[6] D. Lin, Z. M. Kedem. Pincer-Search: A New Algorithm for Discovering Generic Pattern Mining Algorithm for Multi-Core Architectures. Data
the Maximum Frequent Itemset. EDBT Conference Proceedings, (1998), Min Knowl Disc 28(3): (2014), 593–633.
105-110. (Pincer)
[30] Ö. M. Soysal, E. Gupta, H. Donepudi. A sparse memory allocation data
[7] D. Burdick, M. Calimlim, J. Gehrke. MAFIA: A Maximal Frequent
structure for sequential and parallel association rule mining. The
Itemset Algorithm for Transactional Databases. Proc of the ICDE Conf,
Journal of Supercomputing, (2015).
(2001), 443-452.
[31] K. M. Yu, S. H. Liu, L. W. Zhou, S. H. Wu. Apriori-based High
[8] R. J. Bayardo. Efficiently mining long patterns from databases. in Proc.
Efficiency Load Balancing Parallel Data Mining Algorithms on Multi-
The ACM SIGMOD Int. Conf. on Management of data, (1998), 85-93.
core Architectures. Int Journal of Grid and HPC, 7, (2015), 77.
(SE-T ree)
[32] H. Jiang, H. Meng. A Parallel FP-Growth Algorithm Based on GPU. e-
[9] R. Agarwal, C. Aggarwal, V. V. V. Prasad. Depth First Generation of Business Engineering (ICEBE) IEEE 14th Int Conf on, (2017), 97-102.
Long Patterns. In Proc. ACM SIGMOD, (2000), 108-118.
[33] K. W. Chon, S. H. Hwang, M. S. Kim. Gminer: A fast gpu-based
[10] J. S. Park, M. S. Chen, P. S. Yu. Efficient Parallel and Data Mining for
frequent itemset mining method for large-scale data. Information
Association Rules. CIKM 1995: (1995), 31-36.
Sciences, 439-440, (2018), 19 – 38.
[11] M. J. Zaki, M. Ogihara, S. Parthasarathy, W. Li. Parallel Data Mining
[34] Y. Wang, T. Xu, S. Xue, Y. Shen. D2P-Apriori: A deep parallel
for Association Rules on Shared-Memory Multi-Processors. SC 1996:
frequent itemset mining algorithm with dynamic queue. 10th Int Conf on
(1996), 43.
Advanced Computational Intelligence, Xiamen, (2018), 649-654.
[12] R. Agrawal, J. C. Shafer. Parallel mining of association rules. in IEEE [35] H. Phan. An Efficient Mining Algorithm of Closed Frequent Itemsets on
Transactions on Knowledge and Data Engineering, vol. 8, no. 6, pp. Multi-core Processor. In: Li J., Wang S., Qin S., Li X., Wang S. (eds)
962-969, (1996), doi: 10.1109/69.553164. Adv. Data Mining and Applications. ADMA 2019: (2019), 107-118.
[13] E. Han, G. Karypis and V. Kumar. Scalable Parallel Data Mining for
[36] Y. C. Wu, M. Y. Yeh, T . W. Kuo. Fast Frequent Pattern Mining without
Association Rules. Proc. ACM Special Interest Group on Management
Candidate Generations on GPU by Low Latency Memory Allocation.
of Data (SIGMOD), (1997).
Big Data (Big Data) IEEE Int Conf on, (2019), 1407-1416.
[14] M. J. Zaki, S. Parthasarathy, M. Ogihara, W. Li. Parallel Algorithms for
[37] P. Karthik, J. B. Saira. Frequent Item Set Mining of Large Datasets
Discovery of Association Rules. Data Min. Knowl. Discov. 1(4): (1997),
Using CUDA Computing. In: Das K., Bansal J., Deep K., Nagar A.,
343-373.
Pathipooranam P., Naidu R. (eds) Soft Computing for Problem Solving.
[15] S.M. Chung, C. Luo. Parallel mining of maximal frequent itemsets from AISC, Springer, 1057, (2020), 739-747.
databases. Tools with Artificial Intelligence 2003. Proceedings. 15th [38] Grand Challenges to Computational Science. Future Generation
IEEE International Conference on, (2003), 134-139. Computer Systems 5, Special Double Issue, No. 2&3, (1989).
[16] A. Javed, A. Khokhar. Frequent pattern mining on message passing
[39] San Diego Supercomputer Center (SDSC). Grand Challenge Equations.
multiprocessor systems. Distributed and Parallel Databases, 16(3),
University of California. San Diego, (1999).
(2004), 321-334.
[40] I. Foster, C. Kesselman. The Grid 2 – Blueprint for a new computing
[17] L. Liu, E. Li, Y. Zhang, Z. Tang. Optimization of Frequent Itemset
infrastructure. the 2nd edition, Morgan Kaufmann, (2004).
Mining on Multiple-Core Processor. VLDB ’07: (2007), 1275–1285.
[41] A.S. T anenbaum. Distributed Operating Systems. Prentice Hall, (1990).
[18] S. H. Adil, S. Qamar. Implementation of association rule mining using
CUDA. 2009 International Conference on Emerging Technologies,
Islamabad, (2009), 332-336.
ISBN: 978-604-80-5076-4 301
nguon tai.lieu . vn
