Bước 2: Duyệt danh sách ứng viên, tính DBV và Itemset cho tập trung gian bằng các tính giao và hội tương ứng từ các phần tử trong danh sách ứng viên. Tính MG cho phần tử trung gian, sau đó đưa phần tử trung gian vào danh sách để gọi đệ qui.
Bước 3: Kiểm tra số phần tử trong danh sách gọi đệ qui, nếu chỉ có một phần tử việc gọi đệ qui được dừng và tìm được một MG cho Ck+1. Nếu số phần tử trong danh sách từ hai trở lên thì tiếp tục gọi đệ qui để tạo MG. Thuật toán dừng khi việc gọi đệ qui kết thúc và tất cả MG của Ck+1 được tìm thấy.
5. Kết quả thực nghiệm và so sánh
- Thuật toán BVCL là thuật toán khai thác Dàn các tập phổ biến đóng có sử dụng dynamic bit vector (DBV) và dynamic superset bit vector (DSBV) nhằm khai thác tất cả các tập phổ biến đóng có độ hỗ trợ thoả điều kiện lớn hơn hoặc bằng ngưỡng minSup với một cơ sở dữ liệu và một ngưỡng (minSup) đã cho trước. Tạo quan hệ cha – con giữa các tập.
- Thuật toán CharmL tương tự cũng khai thác Dàn các tập phổ biến đóng.
- Thuật toán MG-Charm khai thác tất cả tập sinh của các tập phổ biến đóng.
- Thuật toán BVCLct là thuật toán cải tiến của thuật toán gốc BVCL với mục đích khai thác đồng thời tập sinh và Dàn các tập phổ biến đóng.
- Nếu tính luôn cả việc khai thác tập phổ biến đóng và xây dựng dàn thì tổng thời gian khai thác từ dàn có chậm hơn đôi chút so với khai thác trực tiếp. Tuy nhiên, nếu chúng ta tiếp tục khai thác trên dàn với các minConf khác thì thời gian khai thác từ dàn sẽ hiệu quả hơn.
Trong chương này, trình bày so sánh thời gian chạy và bộ nhớ bị chiếm dụng giữa các thuật toán sau:
i. BVCL
ii. CharmL
iii. BVCL + MG. ( chạy riêng có xuất tập sinh và Dàn FCIs)
iv. BVCL cải tiến ( xuất đồng thời tập sinh và Dàn FCIs)
Các thuật toán được chạy thử nghiệm trên các trường hợp dữ liệu tổng hợp và dữ liệu thực tế. Dữ liệu tổng hợp và dữ liệu thực tế được lấy từ nguồn http://www.philippe- fournier-viger.com/spmf/index.php?link=datasets.php.
Số giao dịch | Số item | |
chess | 3196 | 75 |
mushroom | 8124 | 119 |
pumsb | 49046 | 2113 |
Retail | 88162 | 16470 |
T10I4D100K | 49046 | 2113 |
Có thể bạn quan tâm!
-
Đề Xuất Thuật Toán Khai Thác Dàn Các Tập Phổ Biến Đóng Và Cải Tiến -
Đặc Tả Và Phân Tích Thuật Toán Input: Csdl Giao Dịch: Db, Minsup. -
Khai thác dàn tập phổ biến đóng sử dụng cấu trúc DSBV - 7 -
Khai thác dàn tập phổ biến đóng sử dụng cấu trúc DSBV - 9
Xem toàn bộ 72 trang tài liệu này.
Các thuật toán trong luận văn được chạy trên máy có cấu hình: core i3 2.4GHz, 4GB Ram. Windows 10. Sử dụng Access 2007 chứa CSDL giao dịch.
5.1 Bộ dữ liệu Chess.
Bộ dữ liệu này có được từ các nước cờ trong trò chơi. Bộ dữ liệu gồm 3196 giao dịch với 75 hạng mục phân biệt.
Bảng 3.1: Bộ dữ liệu chess
Minsup (%) | FCIs | |
chess (3196 transactions) (75 items) | 86 | 1467 |
87 | 1194 | |
88 | 935 | |
89 | 696 | |
90 | 503 |
Bảng 3.2: Kết quả thực nghiệm thu được với bộ dữ liệu Chess
Minsup (%) | 86 | 87 | 88 | 89 | 90 | |
BVCL | 4.5 | 3.2 | 2 | 1.3 | 0.8 | |
CharmL | 122 | 81 | 48 | 26 | 13 | |
BVCL cải tiến | 5 | 3.4 | 2.3 | 1.5 | 0.9 | |
BVCL+MG | 78 | 52 | 31 | 17 | 9.4 | |
database: chess | ||||||
Memory(MB) | Minsup (%) | 86 | 87 | 88 | 89 | 90 |
BVCL | 8 | 8 | 6 | 4.7 | 4.5 | |
CharmL | 12.3 | 10 | 8 | 6.2 | 6 |
BVCL cải tiến | 9.4 | 9.1 | 6.7 | 5.7 | 5.3 |
BVCL+MG | 15.4 | 13 | 10 | 8.5 | 7 |
140
time(s) 120
100
80
60
40
20
BVCL
CharmL
BVCL cải tiến
BVCL+MG
0
86
87
88
89
90
supp(%)
DB: chess
Hình 3.4: biểu đồ so sánh thời gian thực thi của bộ dữ liệu Chess
memory 18
(MB)
16
14
12
10
8
6
4
2
0
BVCL
CharmL
BVCL cải tiến
BVCL+MG
86 87 88 89 90
supp(%)
DB: chess
Hình 3.5: biểu đồ so sánh bộ nhớ chiếm dụng của bộ dữ liệu Chess
Biểu đồ hình 3.4 cho thấy sự vượt trội về thời gian thục thi của thuật toán BVCL và BVCL cải tiến. Thuật toán BVCL cải tiến có chậm hơn đôi chút so với thuật toán BVCL gốc. Tuy nhiên, nếu BVCL có khai thác tập sinh sử dụng MG-Charm thì sẽ chậm hơn rất nhiều so với BVCL cải tiến.
Biểu đồ hình 3.5 cho thấy sự tối ưu về bộ nhớ của thuật toán BVCL và BVCL cải tiến. Thuật toán BVCL cải tiến chiếm dụng bộ nhớ hơn đôi chút so với thuật toán BVCL
gốc. Tuy nhiên, nếu BVCL có khai thác tập sinh sử dụng MG-Charm thì thuật toán BVCL cải tiến ưu việt hơn nhiều.
Thời gian chạy trung bình của BVCL nhanh hơn so với CharmL: 24.6 lần. Bộ nhớ tiêu tốn trung bình của BVCL ít hơn so với CharmL: 26.6%.
Thời gian chạy trung bình của BVCL cải tiến nhanh hơn so với BVCL+MG: 14.3 lần. Bộ nhớ tiêu tốn trung bình của BVCL ít hơn so với CharmL: 32.8%.
5.2 Bộ dữ liệu Mushroom.
Bộ dữ liệu này chứa các thuộc tính của các loài nấm khác nhau. Gồm 8124 trường hợp (giao dịch) của 119 loài nấm (hạng mục) khác nhau.
Bảng 3.3: Bộ dữ liệu Mushroom
Minsup (%) | FCIs | |
mushroom (8124 transactions) (119 items) | 20 | 1203 |
25 | 688 | |
30 | 427 | |
35 | 260 | |
40 | 140 |
Bảng 3.4: Kết quả thực nghiệm thu được với bộ dữ liệu Mushroom
Minsup (%) | 20 | 25 | 30 | 35 | 40 | |
BVCL | 6.4 | 2.9 | 1.5 | 0.7 | 0.4 | |
CharmL | 300 | 95 | 36 | 13 | 4 | |
BVCL cải tiến | 8.4 | 3.5 | 2 | 0.9 | 0.5 | |
BVCL+MG | 219 | 72 | 28 | 10.7 | 3.5 | |
database: mushroom | ||||||
Memory(MB) | Minsup (%) | 20 | 25 | 30 | 35 | 40 |
BVCL | 9.8 | 6.8 | 5.5 | 4.7 | 4 | |
CharmL | 32 | 16.5 | 10.8 | 7.6 | 5.6 | |
BVCL cải tiến | 21 | 11 | 8.4 | 6.1 | 4.6 | |
BVCL+MG | 37 | 19 | 12.7 | 8.6 | 6.4 |
350
time(s)
300
250
200
150
100
50
0
DB: mushroom
BVCL
CharmL
BVCL cải tiến
BVCL+MG
20
25
30
35
40
supp(%)
Hình 3.6: Biểu đồ so sánh thời gian thực thi của bộ dữ liệu Mushroom
memory
(MB)
40
35
30
25
20
15
10
5
0
BVCL
CharmL
BVCL cải tiến
BVCL+MG
DB: mushroom
20
25
30
35
40
supp(%)
Hình 3.7: Biểu đồ so sánh bộ nhớ chiếm dụng của bộ dữ liệu Mushroom
Tương tự với bộ dữ liệu Chess, hình 3.6 và hình 3.7 cho thấy sự vượt trội về cả tốc độ thực thi và bộ nhớ chiếm dụng của thuật toán BVCL và BVCL cải tiến.
Thời gian chạy trung bình của BVCL nhanh hơn so với CharmL: 37.6 lần. Bộ nhớ tiêu tốn trung bình của BVCL ít hơn so với CharmL: 57.5%.
Thời gian chạy trung bình của BVCL cải tiến nhanh hơn so với BVCL+MG: 21.8 lần. Bộ nhớ tiêu tốn trung bình của BVCL ít hơn so với CharmL: 38.9%.
5.3 Bộ dữ liệu Pumsb.
Bộ dữ liệu này chứa các thông tin về điều tra dân số. Bộ dữ liệu gồm 49046 giao dịch với 2113 hạng mục phân biệt.
Bảng 3.5: Bộ dữ liệu Pumsb
Minsup (%) | FCIs | |
pumsb (49046 transactions) (2113 items) | 91 | 960 |
92 | 612 | |
93 | 368 | |
94 | 216 | |
95 | 110 |
Bảng 3.6: Kết quả thực nghiệm thu được với bộ dữ liệu Pumsb
minsup | 91 | 92 | 93 | 94 | 95 | |
BVCL | 10.3 | 5.8 | 3.1 | 1.7 | 0.8 | |
CharmL | 402 | 164 | 59.7 | 21 | 5.6 | |
BVCL cải tiến | 11.4 | 6.5 | 3.5 | 1.9 | 0.9 | |
BVCL+MG | 395 | 164 | 61 | 22 | 6.3 | |
database: pumsb | ||||||
Memory(MB) | minsup | 91 | 92 | 93 | 94 | 95 |
BVCL | 20 | 17 | 14 | 13 | 11 | |
CharmL | 31 | 24 | 19 | 14 | 12.7 | |
BVCL cải tiến | 22 | 18 | 15 | 13.8 | 11.7 | |
BVCL+MG | 38 | 26 | 21 | 18.4 | 13.9 |
time(s)
450
400
350
300
250
200
150
100
50
0
BVCL
CharmL
BVCL cải tiến
BVCL+MG
91 92 93 94 95
DB: pumsb
supp(%)
Hình 3.8: Biểu đồ so sánh thời gian thực thi của bộ dữ liệu Pumsb
40
memory
(MB)
35
30
25
20
15
10
BVCL
CharmL
BVCL cải tiến
BVCL+MG
5
0
91
92
93
94
95
DB: pumsb
supp(%)
Hình 3.9: Biểu đồ so sánh bộ nhớ chiếm dụng của bộ dữ liệu Pumsb
Tương tự với 2 bộ dữ liệu trên, hình 3.8 và hình 3.9 cho thấy sự vượt trội về cả tốc độ thực thi và bộ nhớ chiếm dụng của thuật toán BVCL và BVCL cải tiến.
Thời gian chạy trung bình của BVCL nhanh hơn so với CharmL: 30.1 lần. Bộ nhớ tiêu tốn trung bình của BVCL ít hơn so với CharmL: 25.5%.
Thời gian chạy trung bình của BVCL cải tiến nhanh hơn so với BVCL+MG: 26.8 lần. Bộ nhớ tiêu tốn trung bình của BVCL ít hơn so với CharmL: 31.4%.
5.4 Bộ dữ liệu Retail.
Bộ dữ liệu này chứa các thông tin về giao dịch của công ty bán lẻ trực tuyến. Bộ dữ liệu gồm 88162 giao dịch với 16470 hạng mục phân biệt.
Bảng 3.7: Bộ dữ liệu Retail
minsup(%) | FCIs | |
Retail (88162 transactions) (16470 items) | 5 | 16 |
6 | 15 | |
7 | 13 | |
8 | 13 | |
9 | 12 |
Bảng 3.8: Kết quả thực nghiệm thu được với bộ dữ liệu Retail
5 | 6 | 7 | 8 | 9 | ||
BVCL | 0.2 | 0.15 | 0.15 | 0.16 | 0.14 | |
CharmL | 0.31 | 0.28 | 0.25 | 0.23 | 0.2 | |
BVCL cải tiến | 0.17 | 0.14 | 0.12 | 0.12 | 0.11 | |
BVCL+MG | 0.47 | 0.39 | 0.39 | 0.34 | 0.36 | |
database: Retail | ||||||
Memory(MB) | 5 | 6 | 7 | 8 | 9 | |
BVCL | 13 | 10 | 9 | 8.5 | 8.2 | |
CharmL | 14 | 11 | 9.5 | 9.2 | 8.5 | |
BVCL cải tiến | 13.5 | 10.2 | 9.2 | 9 | 8.3 | |
BVCL+MG | 15 | 12 | 11 | 10.3 | 10 | |
60
time(s)
50
40
30
20
10
BVCL+MG
BVCL cải tiến CharmL BVCL
0
5
6
7
8
9
supp(%)
DB: Retail
Hình 3.10: Biểu đồ so sánh thời gian thực thi của bộ dữ liệu Retail