CHƯƠNG 4 THỰC NGHIỆM – ĐÁNH GIÁ THUẬT TOÁN
4.2 CHƯƠNG TRÌNH THỰC NGHIỆM
Chương trình các thuật toán được lấy từ nguồn http://www.philippe-fournier- viger.com/spmf/index.php?link=algorithms.php. Các mã nguồn đƣợc viết bằng java, chạy trên trình biên dịch mã nguồn mở Eclipse. Chúng tôi nghiên cứu và việt hóa một số chức năng. Khi thực hiện chương trình, màn hình chính có cấu trúc như hình 4.1
Hình 4.1. Màn hình chính
Combobox d ng để chọn thuật toán thực hiện. Ở đây có 2 thuật toán để chọn là thuật toán TopKRules và thuật toán TNR. Khi chọn thuật toán TNR, các textbox cho nhập
hệ số k (số luật không dƣ thừa cần tìm), ngƣỡng tối thiểu của độ tin cậy (minconf) và số delta để đảm bảo thuật toán chạy chính xác.
Với textbox chọn file dữ liệu, chúng ta có thể chọn file dữ liệu cần thực thi dưới dạng file.txt ví dụ ở đây ta có thể chọn Chess.txt, Retail.txt, Connect.txt và Pumsb.txt.
Mục textbox chọn file xuất kết quả ta có thể chỉ định một file.txt đã có sẵn hay một file mới để ghi các luật tìm đƣợc sau quá trình khai thác.
Dấu check ở mục “Mở file kết quả khi thuật toán kết thúc” nếu đƣợc check sẽ tự động mở file kết quả ra màn hình.
Nút lệnh “thực hiện” sẽ thực hiện quá trình khai thác theo các thuật toán và CSDL đã chọn, xuất kết quả ra file.txt và hiển thị thời gian thực thi, khối lƣợng bộ nhớ tối đa mà thuật toán chiếm trong quá trình thực thi.
Để đảm bảo kết quả khách quan, chúng tôi chạy mỗi thí nghiệm 5 lần ứng với c ng một CSDL và hệ số k, ghi nhận kết quả của 5 lần chạy và lấy giá trị trung bình của chúng.
Bảng kết quả thực nghiệm đƣợc ghi trong bảng 4.2.
Bảng 4.2 Kết quả thực nghiệm với TopKRules và TNR
Dataset Algorithm Execution Time (ms) Maximum Memory Usage (MB)
k = 10 k = 20 k = 30 k = 10 k = 20 k = 30
Chess TopKRules 116 60 28 32 23.98 8.53
TNR 223 125 62 12.93 29.40 26
Retail TopKRules 5943 6807 8034 1546.70 1584.10 1615 TNR 5102 6231 9876 1636.40 1672.50 1693.40
Connect TopKRules 619 635 537 152.70 268.71 318.50 TNR 814 876 789 339.95 386.75 520.53
pumsb TopKRules 669 717 1188 374.14 397.47 429.69 TNR 721 923 1322 484.79 462.22 453.06
Ứng với bảng kết quả trên, chúng tôi vẽ đồ thị để so sánh thời gian chạy và bộ nhớ sử dụng tối đa đối với từng bộ CSDL.
Với CSDL Chess, Thời gian thực hiện của TNR cao hơn so với TopKRules, tuy nhiên việc sử dụng bộ nhớ không thể hiện đƣợc ƣu điểm của thuật toán nào.
(a) (b)
Hình 4.2. So sánh thời gian thực hiện (a) và sử dụng bộ nhớ (b) của hai thuật toán TopKRules và TNR trên CSDL Chess
(a) (b)
Hình 4.3. So sánh thời gian thực hiện (a) và sử dụng bộ nhớ (b) của hai thuật toán TopKRules và TNR trên CSDL Retail
0 50 100 150 200 250
k=10 k=20 k=30
TopKRules TNR
Đối với kết quả thực nghiệm trên CSDL Retail hình 4.3 chúng ta thấy, về thời gian thực hiện, thuật toán TNR tốt hơn đối với hệ số k thấp và cao hơn đối với hệ số k lớn hơn.
Về phần sử dụng bộ nhớ thì thuật toán TNR luôn cao hơn so với TopKRules.
(a) (b)
Hình 4.4. So sánh thời gian thực hiện (a) và sử dụng bộ nhớ (b) của hai thuật toán TopKRules và TNR trên CSDL Connect
(a) (b)
Hình 4.5. So sánh thời gian thực hiện (a) và sử dụng bộ nhớ (b) của hai thuật toán TopKRules và TNR trên CSDL Pumsb
0 200 400 600 800 1,000 1,200 1,400
k=10 k=20 k=30
TopKR…
TNR 0
100 200 300 400
k=10 k=20 k=30
TopKRules
Nhƣ vậy qua kết quả thực nghiệm trên 4 CSDL mẫu, chúng ta thấy thuật toán TNR cần thời gian và bộ nhớ cao hơn so với thuật toán TopKRules. Điều này có thể lý giải là do giải thuật tìm kiếm thay thế các luật dƣ thừa trong tập trung gian là mất nhiều thời gian và bộ nhớ hơn. Thay vào đó, kết quả các luật tìm đƣợc là không tồn tại luật dƣ thừa trong tập kết quả. Ngoài ra, tuy thuộc vào độ chính xác của thuật toán, nếu xảy ra tình trạng, hệ số delta thấp không đủ để thuật toán TNR chạy cho kết quả chính xác thì chúng ta phải thực hiện lại thuật toán với delta cao hơn, nhƣ vậy thời gian chạy sẽ cao hơn nhiều và tăng tỷ lệ thuận với độ lớn của số delta.
PHẦN KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
Kết luận
Luận văn đã trình bày đƣợc phần lý thuyết về khai thác luật kết hợp và các thuật toán khai thác k luật kết hợp, luật kết hợp không dƣ thừa. Trong đó nêu rõ thuật toán khai thác k luật kết hợp, các ví dụ minh họa. Luật văn cũng nêu một số khái niệm về luật dƣ thừa và các chiến lƣợc cải tiến trong thủ tục tìm kiếm và thay thế các luật dƣ thừa trong tập luật kết quả để thực sự thu đƣợc tập các luật mà trong đó không tồn tại luật dƣ thừa.
Do quá trình thay thế luật có thể phát sinh trường hợp mỗi luật ra được tìm thấy bởi chiến lƣợc 2 đã chiếm một vị trí trong tập luật kết quả và nhƣ vậy sự hiện diện của nó trong tập kết quả có thể làm tăng biến minsup cục bộ (do chính minsup của luật ra). Nếu điều đó xảy ra, thuật toán có thể bị bỏ qua một số luật có độ hỗ trợ thấp hơn luật ra nhƣng các luật bị bỏ đi này không là luật dƣ thừa. Nhƣ vậy, cần khắc phục tình trạng các luật không dƣ thừa có minsup thấp hơn luật dƣ thừa bị bỏ đi chúng tôi đề xuất sử dụng biến Δ và một biến đếm cục bộ.
Chúng tôi đã thêm một biến đếm cục bộ. Biến này đƣợc tăng thêm 1 sau mỗi lần loại bỏ 1 luật từ tập kết quả của Chiến lƣợc 2. Sau đó, khi thuật toán kết thúc, biến đếm được so sánh với Δ. Nếu giá trị biến đếm thấp hơn hoặc bằng Δ, người d ng được thông báo rằng kết quả là chính xác. Ngược lại, người d ng được thông báo rằng kết quả có thể không chính xác. Trong trường hợp này, người d ng có thể chọn để chạy lại thuật toán với một giá trị Δ cao hơn.
Kết quả thực nghiệm cho thấy rằng thuật toán TNR có thời gian chạy và chi phí bộ nhớ cao hơn so với thuật toán tìm k luật kết hợp (TopKRules). Điều này đã đƣợc chúng tôi giải thích ở phần thực nghiệm của chương 4.
Hướng phát triển
Việc thay đổi số Δ nhiều lần là một hạn chế lớn của thuật toán TNR. Trong tương lai chúng tôi sẽ nghiên cứu và đề xuất phương pháp chọn Δ sao cho hiệu quả, để số lần phải chạy lại là ít nhất.
Ngoài ra, thời gian thực hiện của thuật toán TNR còn khá cao so với thuật toán tìm k luật kết hợp. Việc cải tiến thủ tục tìm kiếm và thay thế theo hướng tiếp cận các luật có tiềm năng là luật dƣ thừa thay vì phải quét tất cả các luật trong tập kết quả nhƣ hiện nay để tìm luật dƣ thừa. Nếu thực hiện đƣợc điều này, thuật toán mới sẽ cho kết quả chính xác với thời gian chạy ít hơn rất nhiều.
Việc áp dụng thuật toán khai thác luật kết hợp với thời gian chạy ngắn hơn thay vì sử dụng thuật toán như hiện nay cũng sẽ được chúng tôi đưa vào hướng nghiên cứu tiếp theo.