Đánh giá hiệu quả của thuật toán khai phá luật kết hợp trong môi trường xử lý song song
ĐÁNH GIÁ HIỆU QUẢ CỦA THUẬT TOÁN KHAI PHÁ LUẬT KẾT HỢP
TRONG MÔI TRƯỜNG XỬ LÝ SONG SONG
EVALUATING THE EFFECTIVENESS OF ASSOCIATION RULES MINING
ALGORITHMS IN PARALLEL PROCESSING ENVIRONMENT
Nguyễn Đăng Cẩm, Nguyễn Thành Sơn
Trường đại học Sư phạm Kỹ thuật TP.HCM
TÓM TẮT
Luật kết hợp chỉ ra mối quan hệ, sự kết hợp hay mối tương quan giữa các đối tượng trong cơ sở
dữ liệu. Khai phá luật kết hợp là là bài toán đã và đang được quan tâm nghiên cứu trong lĩnh vực
khai phá dữ liệu. Các thuật toán thường được sử dụng trong khai phá luật kết hợp là Apriori, FP-
Growth. Mục đích của bài báo là đánh giá hiệu quả của các thuật toán Apriori, FP-Growth và
Apriori cải tiến trong môi trường xử lý song song. Việc so sánh các thuật toán dựa vào hai yếu tố
thời gian thực thi và hiệu suất của thuật toán sử dụng. Kết quả thực nghiêm trên các bộ dữ liệu
thực cho thấy rằng trong môi trường xử lý song song, thuật toán PF-Growth thực thi hiệu quả
nhất.
Từ khóa: Khai phá dữ liệu; Khai phá luật kết hợp; Apriori; FP-Growth
ABSTRACT
An association rule indicates the relationship, association, or correlation between objects in the database.
Association Rule Mining is a problem which has received an increasing amount of attention lately in data
mining. Appriori and FP-Growth are commonly used algorithms in association rule mining. The aim of the
paper is to evaluate the effectiveness of the Apriori, FP_Growth and Improved Apriori in parallel
processing environment. The comparison is based on execution time and the performence. The experimental
results showed that in parallel processing environment the FP-growth algorithm is the most efficiency one.
Keywords: Data Mining; Association Rule Mining; Apriori; FP-Growth
1. GIỚI THIỆU
thiết.
Hai hướng tiếp cận chính trong thiết kế
thuật toán khai phá luật kết hợp song song là
mô hình song song dữ liệu, mô hình song song
thao tác.
Khai phá dữ liệu là một quá trình đầy hứa
hẹn và phát triển trong phân tích dữ liệu và nó
được ứng dụng trong nhiều lĩnh vực. Khai phá
dữ liệu là cốt lõi của quá trình “Phát hiện tri
thức từ cơ sở dữ liệu” (Knowledge Discovery
in Database-KDD), là quá trình khai phá, trích
xuất, khai thác và sử dụng những dữ liệu có
giá trị tiềm ẩn từ bên trong lượng lớn dữ liệu
được lưu trữ trong các cơ sở dữ liệu (CSDL),
kho dữ liệu, trung tâm dữ liệu… lớn hơn là
Big Data.
Bài báo này nhằm mục đích đánh giá hiệu
quả giữa các thuật toán Apriori, Apriori cải
tiến, Apriori cải tiến và FP-Growth trong môi
trường xử lý song song.
Phần còn lại của bài báo bao gồm: Phần
2 trình bày các khái niệm cơ bản và các công
trình liên quan. Phần 3 giới thiệu về các giải
thuật khai phá luật kết hợp và khai phá luật kết
hợp sử dụng giải thuật song song. Cách tiếp
cận của đề tài nghiên cứu được trình bày trong
phần 4. Phần 5 là kết quả thực nghiệm. Phần
6 là kết luận và hướng phát triển của đề tài.
Các thuật toán khai phá luật kết hợp tuần
tự khi sử dụng với dữ liệu lớn sẽ mất nhiều
thời gian. Vì vậy, yêu cầu cần có những thuật
toán song song hiệu quả cho việc phát hiện các
luật kết hợp trong khai phá dữ liệu là rất cần
2. CÁC KHÁI NIỆM CƠ BẢN VÀ CÁC
-
Trong [2], Aiman Moyaid Said, Dr. P D
D. Dominic và Dr. Azween B Abdullah,
đã cài đặt và so sánh thuật toán cải tiến của
Fpgrowth, AFOPT, Nonordfp, Fpgrowth*
với dữ liệu T10I4D100k, T40I10D100K,
Mushroom, Connect4. Với thuật toán
Fpgrowth chạy trên dữ liệu T10I4D100k,
T40I10D100K, Mushroom, Connect4.
Kết luận hiệu suất của thuật toán APFOPT
là ổn định nhất trên hầu hết các loại dữ
liệu.
CÔNG TRÌNH LIÊN QUAN
2.1. Các khái niệm cơ bản
▪ I = {i1, i2, …in} là tập bao gồm n mục
phân biệt (item – còn gọi là các thuộc
tính – attribute)
▪ D = {t1, t2, …tm} là tập gồm m giao dịch
gọi là cơ sở dữ liệu giao dịch, mỗi t có một
định danh duy nhất được ký hiệu là TID
(Transaction Identification) và chứa tập
các mục trong I.
-
Trong [3], Zhi-Hong Deng và Sheng -
Long Lv trình bày một thuật toán hiệu quả
được gọi là FIN để khai thác các tập mục
thường xuyên. Để đánh giá hiệu suất của
FIN, họ đã tiến hành các thí nghiệm để so
sánh nó với PrePost và FP-growth∗ trên
nhiều bộ dữ liệu thực và tổng hợp. Kết quả
thử nghiệm cho thấy rằng FIN có hiệu suất
cao trên cả thời gian chạy và mức sử dụng
bộ nhớ.
▪ Một luật định nghĩa sự kéo theo có dạng
X ⇒ Y trong đó X,Y ⊆ I và X ∩ Y =
Ø.
X gọi là phần mệnh đề điều kiện
Y gọi là mệnh đề kết quả của luật
tương ứng
▪ Độ phổ biến
Supp(X) = |X| / |D|
-
Trong [4],Dawen Xia, Yanhui Zhou,
Zhuobo Rong, và Zili Zhang đề xuất một
thuật toán FP-Growth sử dụng giải thuật
song song cải tiến (IPFP), sử dụng
MapReduce để thực hiện thuật toán FP-
Growth sử dụng giải thuật song song. Do
đó cải thiện hiệu suất tổng thể và hiệu quả
khai phá các tập mục phổ biến.
Supp(X ⇒ Y) = |{T ⊆ D:X ∪ Y ⊆
T}| / |D|
▪ Độ tin cậy
Supp(X⇒Y)
Conf(X⇒Y) =
Supp(X)
2.2. Các công trình liên quan
3. MỘT SỐ GIẢI THUẬT KHAI PHÁ
LUẬT KẾT HỢP VÀ KHAI PHÁ
LUẬT KẾT HỢP SỬ DỤNG THUẬT
TOÁN SONG SONG
-
Trong [1], Z. H. Deng, Z. Wang và J. Jiang
đề xuất một kiểu dữ liệu mới theo chiều
dọc gọi là N-list, bắt nguồn từ FP-tree-like
gọi là PPC-Tree. Dựa trên cấu trúc dữ liệu
N-list, phát triển một thuật toán khai thác
hiệu quả là PrePost, để khai thác tập mục
phổ biến.
Các quả thực nghiệm cho thấy thuật toán
PrePost hiệu quả nhanh nhất trong tất cả
các trường hợp. Mặc dù thuật toán sẽ tốn
nhiều bộ nhớ khi các bộ dữ liệu nhỏ.
3.1. Giải thuật khai phá luật kết hợp
3.1.1. Thuật toán Apriori
Một trong những thuật toán đầu tiên khai
phá luật kết hợp là do RaKesh Agrawal,
Tomasz Imielinski, Anin Sawami đưa ra vào
năm 1993 [5], là nền tảng cho việc phát triển
những thuật toán sau này. Thuật toán sinh tập
mục ứng cử từ những tập mục phổ biến ở bước
trước, sử dụng kĩ thuật “tỉa” để bỏ đi tập mục
ứng cử không thỏa mãn ngưỡng hỗ trợ cho
trước
-
-
Phải duyệt CSDL nhiều lần.
Số lượng lớn tập ứng cử được tạo ra làm
gia tăng sự phức tạp không gian.
Để xác định độ support của các tập ứng
cử, thuật toán luôn phải quyét lại toàn bộ
CSDL.
-
Nội dung thuật toán Apriori
-
Tìm tất cả các tập phổ biến 1- hạng mục
(C1).
3.1.2. Thuật toán Apriori cải tiến
Để nâng cao hiệu quả khai phá các
itemset phổ biến, Girja Shankar và Latita
Bargadiya [6] đã thảo luận về hai vấn đề của
thuật toán Apriori.
-
Tạo các tập ứng viên kích thước k - hạng
mục (k - candidate itemset) từ các tập phổ
biến có kích thước (k-1) - hạng mục. Ví
dụ, tạo ứng viên C2 từ tập phổ biến C1.
Kiểm tra độ phổ biến của các ứng cử trên
CSDL và loại các ứng cử không phổ biến
ta được Li (i = {1, 2, ..., k}).
-
-
Đầu tiên, chúng ta cần phải quét các cơ
sở dữ liệu nhiều lần và ở lần thứ hai, nó sẽ tạo
ra itemset ứng cử lớn, sẽ tăng thời gian và sự
phức tạp không gian. Để khắc phục những
khuyết điểm đầu tiên chúng ta tìm
frequent_one_itemset của cơ sở dữ liệu sau đó
tạo ra tập power của frequent_one_itemset và
khởi tạo itemset count = 0. Gọi power set này
thiết lập là Global power set. Khi chúng tôi
quét cơ sở dữ liệu để đếm itemset, đầu tiên
chúng tôi xóa các item từ giao dịch đó không
có mặt trong danh sách frequent_one_itemset.
Sau khi quá trình xóa chúng tôi tạo ra Local
Power set của các item còn lại của giao dịch
và so sánh với các Global power set. Khi phù
hợp thì tăng số lượng itemset lên một. Bước
này sẽ làm giảm nhiều lần quét của cơ sở dữ
liệu.
Dừng khi không tạo được tập phổ biến
hay tập ứng cử Lk = {} hay Ck = {}.
Mã giả thuật toán Apriori
Dữ liệu vào: Tập các giao dịch D, ngưỡng
hỗ trợ minsup
Dữ liệu ra: Tập trả lời bao gồm các tập
mục phổ biến trên D
Phương pháp:
L1 = {large 1-itemset};
for (k = 2; Lk-1 ≠ 휙; k++) do begin
Ck = apriori_gen(Lk-1); // sinh tập
mục ứng cử mới Ck;
forall giao dịch t ∈ D do begin
Ct = subset(Ck, t); // các tập mục
ứng cử chứa trong t;
forall tập mục ứng cử ci ∈ Ct do
ci.count ++ ;
end;
Nội dung thuật toán:
Input:
1) Cơ sở dữ liệu D với định dạng (Tid,
itemset)
2) Ngưỡng hỗ trợ tối thiểu: min-sup;
Output: Li, itemset trong D;
Dưới đây là biểu đồ xử lý:
1) L1 = tìm frequent_one_itemset (D);
Lk = {ci ∈ Ck|ci.count ≥ minsup}
end;
Answer = ∪kLk ;
Ưu điểm thuật toán Apriori
-
Là thuật toán đơn giản, dễ hiểu và dễ cài
đặt.
Thuật toán Apriori tìm tập mục phổ biến
thực hiện tốt bởi rút gọn kích thước các
tập ứng cử nhờ kỹ thuật “tỉa”.
2)
Tạo
power
set
L1
(frequent_one_itemset(D)) và khởi tạo
itemset count = 0, và gọi nó là Global power
set;
-
3) Quét cơ sở dữ liệu D đến hết.
Nhược điểm thuật toán Apriori
i) Đọc itemset từ giao dịch và xóa các
item không ở trong L1 và sau đó tạo ra
local power set các item còn lại của giao
dịch.
Bước 4: Đệ quy xây dựng FP-Tree điều
kiện đến khi FP-Tree điều kiện còn một nhánh
duy nhất (single path) tiến hành sinh tất cả tổ
hợp mục phổ biến.
ii) So sánh local power set với Global
power set từng cái một và nếu itemset phù
hợp thì tăng số lượng itemset lên 1 trong
Global power set.
3.2. Khai phá luật kết hợp sử dụng giải
thuật song song
3.2.1. Thuật toán song song sử dụng
Apriori cải tiến
Tỉa các ứng cử itemset.
4) Quét Global power set và kiểm tra từng
itemset đếm ứng cử itemset;
Dựa vào thuật toán Apriori cải tiến, thuật
toán này ta sử dụng mô hình “Chủ-Tớ”.
Nội dung thuật toán:
Nếu độ hỗ trợ của ứng cử itemset là nhỏ
hơn minsup sau đó xóa item set đó từ
Global power set.
Input:
1) Cơ sở dữ liệu D với định dạng (Tid,
itemset), Tid là một id kinh doanh và itemset
là itemset tương ứng với công việc kinh
doanh. D1, D2, D3,…,Dp: các phân hoạch
CSDL, p là số các bộ xử lý.
2) Ngưỡng hỗ trợ tối thiểu: min-sup;
Output: Li, itemset trong D;
Dưới đây là biểu đồ xử lý:
1) L1i = tìm frequent_one_itemset (Di); //
bộ xử lý thứ i
5) Giữ lại itemset của Global power set sẽ
là itemset phổ biến được yêu cầu.
3.1.3. Thuật toán FP-Growth
Thuật toán FP-Growth được giới thiệu
bởi Jiawei Hai, Jian Pei và Yiwen Yin 2000
[7], sẽ khắc phục được các nhược điểm của
thuật toán Apriori.
Nội dung thuật toán:
2) Nhận L1(i) từ bộ xử lý tớ
Bước 1: Xây dựng FP-Tree:
Tạo power set L1 (frequent_one_itemset
(D)) và khởi tạo itemset count = 0, và gọi nó
là Global power set;
3) Bộ xử lý chủ quét cơ sở dữ liệu D đến
hết.
Đọc itemset từ giao dịch và xóa các
item không ở trong L1 và sau đó tạo ra local
power set các item còn lại của giao dịch.
Gửi local power set và (Global power
set)i tới các bộ xử lý tớ
- Duyệt CSDL lần một, xác định các mục
phổ biến L và sắp xếp chúng theo độ hỗ trợ.
- Duyệt qua CSDL lần hai, với mỗi giao
dịch T sắp xếp các mục theo thứ tự tập L. Giả
sử các mục phổ biến trong T có dạng [p|P] với
p là mục cần đưa vào FP-Tree và P là danh
sách các mục còn lại, N là nút cần chèn. Nếu
nút con của N giống p, tăng count nút con đó
lên 1. Ngược lại, tạo nút con mới cho N có tên
mục là p, count = 1. Tiếp tục chèn P vào nút
con vừa xét.
4) Bộ xử lý tớ i
So sánh local power set với (Global
power set)i từng cái một và nếu itemset phù
hợp thì tăng số lượng itemset lên 1 trong
(Global power set)i.
Bước 2: Xây dựng cơ sở mẫu điều kiện
(Conditional Patern Bases) cho mỗi mục phổ
biến.
Bước 3: Xây dựng FP-Tree điều kiện
(Conditional FP-Tree) cho mỗi mục phổ biến
trong cơ sở mẫu điều kiện.
5) Bộ xử lý chủ nhận (Global power set)i
từ bộ xử lý tớ
Quét Global power set và kiểm tra
từng item set đếm ứng cử itemset;
Nếu đếm itemset của ứng cử itemset là
ít hơn minsup sau đó xóa item set đó từ Global
power set.
6) Giữ lại itemset của Global power set sẽ
là itemset phổ biến được yêu cầu.
• Giai đoạn cuối cùng là thực thi việc
khai phá bằng cách xây dựng đệ qui
các mẫu điều kiện cơ sở và các CFPTs
cho đến khi nó sinh tất cả các tập mục
phổ biến.
3.2.2. Thuật toán song song sử dụng
4. KHAI PHÁ LUẬT KẾT HỢP
TRONG MÔI TRƯỜNG XỬ LÝ
SONG SONG
FP-Growth
Dựa vào thuật toán Fp-Tree tuần tự.
Thuật toán này [8], ta xây dựng một số Fp-tree
cục bộ trong môi trường bộ nhớ phân tán và
sử dụng mô hình “Chủ - Tớ”.
4.1. Cách tiếp cận chung của các giải
thuật khai phá luật kết hợp
Cách tiếp cận chung của các giải thuật
khai phá luật kết hợp thường được thực hiện
qua hai giai đoạn:
Thuật toán khai phá luật kết hợp gồm hai
nhiệm vụ chính:
Xây dựng song song FP-Tree
Khai phá song song và sinh tập mục phổ
biến.
(1) Tìm tất cả các tập mục dữ liệu có độ
hỗ trợ thỏa ngưỡng tối thiểu cho trước, gọi
là tập các mục dữ liệu thường xuyên.
(2) Tìm ra những luật kết hợp từ những tập
mục dữ liệu thường xuyên thỏa độ tin cậy
cho trước.
(1) Xây dựng song song FP-Tree
• Ta chia CSDL giao dịch D cho P bộ
xử lý.
• Mỗi bộ xử lý tính toán đếm hỗ trợ
(flocal(i)) của mỗi mục i bằng cách
quét phân hoạch CSDL cục bộ DN/P,
tất cả các bộ xử lý đếm flocal (i) cục
bộ đến bộ xử lý Chủ.
Các công trình nghiên cứu về bài toán khai
phá luật kết hợp thường tập trung đề xuất mới
hoặc cải tiến thuật toán thực hiện trong giai
đoạn 1 tìm tất cả các tập mục phổ biến.
4.2. Khai phá luật kết hợp sử dụng giải
• Bộ xử lý Chủ tập hợp tất cả các mục
và kết hợp chúng lại để sinh số đếm hỗ
trợ tổng thể (fglocal (i)).
thuật song song
Khai phá luật kết hợp sử dụng giải thuật
song song dựa trên ý tưởng của khai phá luật
kết hợp, thực hiện song song hóa nhằm đáp
ứng sự tăng lên nhanh chóng của dữ liệu và
giảm thời gian thực hiện.
• Tập các 1-itemset phổ biến thu được
sẽ được truyền cho tất cả các bộ xử lý
trong nhóm.
• Bước tiếp theo là xây dựng các FP-
Tree cục bộ, Mỗi bộ xử lý quét CSDL
cục bộ DN/P của nó và chèn các mục
phổ biến vào trong cây FP-Tree
(2) Khai phá song song và sinh tập mục
phổ biến
Các giải thuật xử lý song song được áp
dụng trong giai đoạn tìm các tập mục phổ biến
nhằm giảm thời gian thực thi của giai đoạn này.
Trong các thuật toán dùng trong khai phá luật
kết hợp, thuật toán FP-Growth thường được
sử dụng trong các giải thuật xử lý song song
vì tính hiệu quả của nó.
• Trong giai đoạn đầu, ta xét toàn bộ FP-
Tree và tạo ra các mẫu điều kiện cơ sở.
• Trong giai đoạn tiếp theo, ta tập hợp
các mẫu điều kiện cơ sở từ các bộ xử
lý để xây dựng FP-Tree điều kiện cơ
sở (CFPT) cho mỗi mục phổ biến.
Khai phá luật kết hợp trong môi trường xử
lý song song được thực hiện qua các bước sau:
(1) Cơ sở dữ liệu ban đầu được phân hoạch
cho các bộ xử lý; (2) Mỗi bộ xử lý thực hiện
thuật toán FP-Growth để phát sinh tập mục
phổ biến cục bộ; (3) Bộ xử lý chủ tổng hợp
các tập mục phổ biến cục bộ từ các bộ xử lý
khác để phát sinh các tập mục phổ biến toàn
cục; (4) Các luật kết hợp được phát sinh từ tập
mục phổ biến toàn cục.
tạo ra bằng cách sử dụng trình tạo từ nhóm
nghiên cứu của IBM Almaden Quest, có
100000 giao dịch; dữ liệu BMS_WebView_1
chứa 59.602 giao dịch dữ liệu nhấp chuột từ
một trang web thương mại điện tử.
5.3. Kết quả thực nghiệm
Chúng tôi cài đặt các thuật toán Apriori,
Apriori cải tiến, Apriori cải tiến sử dụng giải
thuật song song, FP-Growth và FP-Growth sử
dụng giải thuật song song, so sánh các thuật
toán dựa vào thời gian thực thi và số lượng tài
nguyên mà thuật toán sử dụng.
Hình 1 minh họa các bước thực hiện của
thuật toán khai phá luật kết hợp FP-Growth
trong môi trường xử lý song song.
5.3.1. Thời gian thực thi
Hình 2, 3, 4 Mô tả kết quả thực nghiệm
về thời gian thực thi của các thuật toán được
tính bằng giây.
80
70
Apriori
Apriori cải tiến
FP-Growth
FP-Growth song song
Apriori cải tiến song song
60
50
40
30
20
10
0
50
60
70
80
Độ hỗ trợ
Hình 1. Mô hình giải thuật song song dùng
Hình 2. Thời gian thực thi của các thuật
toán với bộ dữ liệu mushroom.
thuật toán FP-Growth
5. KẾT QUẢ THỰC NGHIỆM
5.1. Môi trường thực nghiệm
80
60
40
20
0
Hệ thống thử nghiệm được cài đặt bằng
C# trên nền Microsoft Windows 10 Enterprise
64bit, .Net Framework 4.5, thực hiện trên
CPU Intel® Core™ i5-3210M CPU @
2.50GHz 2.50GHz, RAM 12.0GB, SSD
240GB. Hệ thống phần mềm được sử dụng:
Visual Studio 2017 Enterprise, Microsoft’s
Message Passing Interface (MS-MPI) [9].
5
6
7
8
9
Độ hỗ trợ
Apriori
Apriori cải tiến
FPGrowth
FPGrowth song song
Apriori cải tiến song song
5.2. Các tập dữ liệu thực nghiệm
Gồm 3 cơ sử dữ liệu: Dữ liệu
mushroom.dat được lấy từ bộ dữ liệu của UCI,
có 8124 giao dịch; dữ liệu T10I4D100K được
Hình 3. Thời gian thực thi của các thuật
toán với bộ dữ liệu T10I4D100K.
Apriori cải tiến
24.93 86.09
24.97 89.65
50.32 283.68
120
100
80
60
40
20
0
FPGrowth
FPGrowth song song
Apriori cải tiến song
song
51.40 286.83
2.5
3
3.5
4
4.5
Bảng 3. Kết quả về số lượng tài nguyên (mà
thuật toán cần sử dụng) với độ hỗ trợ được
chọn là 3.5% với bộ dữ liệu
Độ hỗ trợ
Apriori
Apriori cải tiến
FPGrowth
FPGrowth song song
Apriori cải tiến song song
BMS_WebView_1
Độ hỗ trợ (%)
3.5
Hình 4. Thời gian thực thi của các thuật
toán với bộ dữ liệu BMS_WebView_1.
CPU RAM
Tài nguyên
(%)
(MB)
Apriori
24.90 79.61
24.95 80.09
24.97 81.42
42.79 199.75
Kết quả thực nghiệm cho thấy thời gian
thực thi của thuật toán FP-Growth sử dụng
giải thuật song song là nhanh nhất, thời gian
thực thi của thuật toán Apriori cải tiến và
Apriori cải tiến sử dụng giải thuật song song
thời tăng đột biến khi độ hỗ trợ nhỏ.
Apriori cải tiến
FPGrowth
FPGrowth song song
Apriori cải tiến song
song
46.73 196.61
5.3.2. Tài nguyên thuật toán sử dụng
Kết quả thực nghiệm cho thấy số lượng tài
nguyên sử dụng của các thuật toán trong môi
trường xử lý song song gần gấp hai lần thuật
toán tuần tự cả về bộ nhớ RAM (Mb) và phần
trăm % CPU.
Bảng 1, 2, 3 trình bày kết quả thực nghiệm
về hiệu suất (số lượng tài nguyên sử dụng) của
các thuật toán.
Bảng 1. Kết quả về số lượng tài nguyên (mà
thuật toán cần sử dụng) với độ hỗ trợ được
chọn là 60% với bộ dữ liệu mushrom.
5.4. Nhận xét kết quả thực nghiệm
Kết quả thực nghiệm cho thấy thời gian
thực thi của thuật toán FP-Growth, FP-
Growth song song nhỏ hơn thuật toán Apriori
tuần tự, thuật toán Apriori cải tiến, Apriori cải
tiến song song trên các bộ dữ liệu. Ta thấy FP-
Growth song song thời gian thực hiện nhanh
hơn FP-Growth và ổn định trên các bộ dữ liệu.
Độ hỗ trợ (%)
60
CPU RAM
Tài nguyên
(%)
(MB)
Apriori
Apriori cải tiến
FPGrowth
24.94 68.15
24.86 67.41
24.97 71.54
44.21 132.75
Thuật toán Apriori cải tiến thời gian thực
thi nhanh hơn thuật toán Apriori tuần tự với
độ hỗ trợ lớn, nhưng với đỗ hỗ trợ nhỏ thì số
lượng tập các 1-item lớn, nên thuật toán
Apriori sinh ra rất nhiều tập mục ứng cử, do
đó thời gian thực thi của Apriori cải tiến lớn
hơn rất nhiều so với Apriori tuần tự.
FPGrowth song song
Apriori cải tiến song song 51.72 148.08
Bảng 2. Kết quả về số lượng tài nguyên (mà
thuật toán cần sử dụng) với độ hỗ trợ được
chọn là 7% với bộ dữ liệu T10I4D100K
Độ hỗ trợ (%)
Tài nguyên
Apriori
7
CPU RAM
Số lượng tài nguyên (mà thuật toán cần sử
dụng) của thuật toán sử dụng giải thuật song
(%)
(MB)
24.96 87.42
song lớn hơn khoảng 2 lần thuật toán tuần tự,
trong đó số lượng tài nguyên mà thuật toán
FP-Growth song song sử dụng ít hơn thuật
toán Apriori cải tiến song song.
dụng giải thuật song song đã giải quyết được
vấn đề khai phá dữ liệu trên dữ liệu lớn về tốc
độ xử lý.
Trong tương lai chúng tôi sẽ tiếp tục
nghiên cứu sâu hơn về các thuật toán khai phá
luật kết hợp sử dụng giải thuật song song, tìm
cách cải tiến và khắc phục nhược điểm của các
giải thuật song song hiện có, xây dựng các
thuật toán mới nhằm đạt hiệu quả tốt hơn.
6. KẾT LUẬN VÀ HƯỚNG PHÁT
TRIỂN
Bài báo đã trình bày và so sánh hiệu quả
về một số thuật toán khai phá luật kết hợp và
thuật toán khai phá luật kết hợp sử dụng giải
thuật song song, qua đó ta thấy thuật toán sử
TÀI LIỆU THAM KHẢO
[1]
Z. H. Deng, Z. Wang，and J. Jiang, A New Algorithm for Fast Mining Frequent Itemsets
Using N-Lists. SCIENCE CHINA Information Sciences, 55 (9), 2008 - 2030, 2012.
[2] Aiman Moyaid SaidA, Dr. P D D. DominicB, Dr. Azween B AbdullahC, "A Comparative
Study of FP-growth Variations," In IJCSNS International Journal of Computer Science and
Network Security, no. VOL.9 No.5, pp. 266-272, May 2009.
[3] Zhi-HongDeng and Sheng-LongLv, "Fast mining frequent itemsets using Nodesets,"
Expert Systems with Applications, no. Volume 41, Issue 10, pp. 4505-4512, August 2014.
[4] Dawen Xi, Yanhui Zhou, Zhuobo Rong and Zili Zhang, "IPFP: An Improved Parallel FP-
Growth Algorithm for Frequent Itemsets Mining," Proceedings 59th ISI World Statistics
Congress, vol. Hong Kong (Session CPS026), p. 4034, 25-30 August 2013.
[5] R. Agrawal and R. Srikant, Fast algorithms for minning association rules, In 20th
VL.DBConf, Sept, 1994.
[6] Girja Shankar and Latita Bargadiya, "A New Improved Apriori Algorithm For Association
Rules Mining," International Journal of Engineering Research & Technology (IJERT), no.
Vol. 2 Issue 6, June 2013.
[7] Jiawei Han, Jian Pei, and Yiwen Yin, "Mining Frequent Patterns without Candidate
Generation," SIGMOD', p. 196, 2000.
[8] Yi Wang, Haoyuan Li, Dong Zhang, Ming Zhang, Edward Chang, PFP: Parallel FP-Growth
for Query Recommendation, ACM, 2001.
[9] Douglas Gregor and Benjamin Martin, MPI.NET Tutorial in C#, Open Systems Laboratory,
Indiana University., 2008.
Tác giả chịu trách nhiệm bài viết:
TP.HCM, ngày….tháng…..năm…..
Xác nhận của giảng viên hướng dẫn
Họ tên: Nguyễn Đăng Cẩm
Đơn vị: Trường ĐH Sư Phạm Kỹ Thuật Tp.HCM
Điện thoại: 0979371093
(Ký & ghi rõ họ tên)
Email: [email protected]
BÀI BÁO KHOA HỌC
THỰC HIỆN CÔNG BỐ THEO QUY CHẾ ĐÀO TẠO THẠC SỸ
Bài báo khoa học của học viên
có xác nhận và đề xuất cho đăng của Giảng viên hướng dẫn
Bản tiếng Việt ©, TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP. HỒ CHÍ MINH và TÁC GIẢ
Bản quyền tác phẩm đã được bảo hộ bởi Luật xuất bản và Luật Sở hữu trí tuệ Việt Nam.
Nghiêm cấm mọi hình thức xuất bản, sao chụp, phát tán nội dung khi chưa có sự đồng ý
của tác giả và Trường Đại học Sư phạm Kỹ thuật TP. Hồ Chí Minh.
ĐỂ CÓ BÀI BÁO KHOA HỌC TỐT, CẦN CHUNG TAY BẢO VỆ TÁC QUYỀN!
Thực hiện theo MTCL & KHTHMTCL Năm học 2017-2018 của Thư viện Trường Đại học
Sư phạm Kỹ thuật Tp. Hồ Chí Minh.
9 trang
09/01/2024
12460
Free
Bạn đang xem tài liệu "Đánh giá hiệu quả của thuật toán khai phá luật kết hợp trong môi trường xử lý song song", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- danh_gia_hieu_qua_cua_thuat_toan_khai_pha_luat_ket_hop_trong.pdf
