Luận văn Nghiên cứu cải tiến thuật toán phân lớp sử dụng cây quyết định đệ quy

71 CHƯƠNG 4. ỨNG DỤNG KIỂM CHỨNG Để minh họa cho phần lý thuyết ở các chương trên, phần này sẽ mô tả một ứng dụng đơn giản cài đặt thuật toán Hybrid Data dưới dạng xử lý tuần tự và một phiên bản khác áp dụng mô hình song song hóa được mô tả trong chương 3. 4.1 TỔNG QUAN VỀ ỨNG DỤNG Để minh họa cho thuật toán Hybrid Data, luận văn đã xây dựng một chương trình ứng dụng dựa trên cơ sở lý thuyết đã trình bày. Ứng dụng này được xây dựng bằng ngôn ngữ lập trình Visual Basic.Net (trên nền tảng công nghệ Microsoft .Net 2005) chạy trên Windows XP Service Pack 2 với cơ sở dữ liệu là Microsoft SQL Server 2000 Service Pack 4. Cấu hình máy tính dùng để chạy ứng dụng là Intel P4 2.3GHz với 1GB RAM, đĩa cứng 80GB. Xin lưu ý là như mục tiêu của luận văn này đề ra, thuật toán Hybrid Data chỉ nhằm mục đích cải tiến tốc độ thực thi nhưng không làm sai lệch kết quả cuối cùng của cây quyết định (xem thêm chương 3). Chính vì vậy ứng dụng này không đề cập đến độ chính xác của kết quả, trong các bước ở chương một thì ứng dụng này chỉ tập trung vào pha xây dựng cây quyết định. Ngoài ra, phần thực nghiệm cũng cài đặt thêm các cải tiến nâng cao cho thuật toán gốc (xem thêm chương ba phần 3.3) Cũng như các thuật toán và ứng dụng khai mỏ dữ liệu khác, lần lượt tuần tự thực hiện các bước như chương một đã trình bày. Ứng dụng thực thi trên cơ sở dữ liệu SQL Server 2000, chính vì vậy phải tập hợp dữ liệu trong một bảng dữ liệu chính duy nhất (gọi là master table, được lưu trữ với tên “tblTraining”). Cấu trúc của bảng này rất đơn giản, bao gồm một cột chứa nhãn lớp, xin lưu ý là để cho thuận tiện cột này sẽ chứa thuộc tính classID của nhãn lớp thay vì chứa giá trị nhãn lớp (mỗi giá trị nhãn lớp sẽ có một giá trị thuộc tính classID để phân biệt); vì vậy kết quả các nút lá sẽ chứa các giá trị classID của các nhãn lớp. Nếu muốn suy ra các nhãn lớp chỉ tham chiếu đến giá trị nhãn tương ứng thông qua giá trị classID tương ứng. Tương tự như trên, bảng tblTraining cũng có một cột gọi là Rid để phân biệt các bộ dữ liệu PDF created with pdfFactory Pro trial version www.pdffactory.com 72 với nhau. Các cột còn lại là các cột thuộc tính khác, tên các cột này đặt tùy ý, chương trình sẽ tự động ánh xạ và xử lý tên thuộc tính tương ứng với từng giá trị cụ thể mà không cần sự can thiệp từ bên ngoài. Ngoài ra, trong phần thực nghiệm tôi cũng sử dụng bộ tạo dữ liệu Generator [15, tr.18-20] tạo ra các dữ liệu thử nghiệm, bộ Generator này đã được dùng để tạo dữ liệu thử nghịêm trong thuật toán SLIQ [11], SPRINT [7] và Rain Forest [6]. Có hai phân lớp: GroupA và GroupB với quy ước không thuộc GroupA tức thuộc GroupB, hai phân lớp này sử dụng hai hàm tạo dữ liệu là hàm 1 và hàm 7 như sau: · Hàm 1: Age GroupA. Hàm này tạo ra cây với mức độ ít liên hệ giữa các thuộc tính, mô hình cây kết quả không quá lớn. · Hàm 7: (0.67 x (salary + commission) – 0.2 x loan – 20000) > 0 => GroupA. Hàm này tạo ra cây với mức độ liên hệ giữa các thuộc tính rất nhiều, mô hình cây kết quả khá phức tạp. Dữ liệu sẽ được tạo một cách ngẫu nhiên trên từng thuộc tính với bộ Generator, cấu trúc của bảng dữ liệu thử nghiệm được mô tả như sau: Bảng 4.1: Cấu trúc bảng tblTraning được tạo ra từ bộ Generator. Thuộc tính Mô tả Tổng số giá trị khác biệt Salary Miền giá trị (20000, 150000) 130000 Commission Nếu Salary >= 75000 thì commission = 0; ngược lại miền giá trị (10000, 75000) 65000 Age Miền giá trị (20,80) 61 Education Miền giá trị (0, 4) 5 Car Miền giá trị (1,10) 10 ZipCode Miền giá trị (1,9) 9 HouseValue Miền giá trị (50000, 150000) * ZipCode 1350000 HomeYears Miền giá trị (1,30) 30 Loan Miền giá trị (0,500000) 500000 PDF created with pdfFactory Pro trial version www.pdffactory.com 73 4.2 ỨNG DỤNG TRÊN MÁY ĐƠN (XỬ LÝ TUẦN TỰ) Hình 4.1: Giao diện chính của ứng dụng trên máy đơn. Trên giao diện chính của ứng dụng có hai ô “Begin” và “End” cho biết thời điểm bắt đầu và kết thúc của thuật toán. Ô “Total time” cho biết tổng thời gian thực thi của thuật toán. Ứng dụng trên có hai chức năng: thực thi thuật toán hoàn toàn tự động mà không xét đến tham số StopLevel; thực thi thuật toán dựa trên tham số StopLevel. Tham số này được đưa vào nhằm làm cho thuật toán nhanh chóng đạt đến điều kiện dừng bằng cách tại mỗi bước đệ qui, nếu tổng số bộ dữ liệu hiện hành nhỏ hơn tham số này thì thuật toán sẽ dừng sớm, nhãn xuất hiện nhiều nhất sẽ được trả về. Đây cũng là một trong những cách đẩy nhanh quá trình tạo cây “bằng cách thực hiện pha cắt tỉa cây (pruning)” ngay trong quá trình tạo cây [16]. Lưu ý tham PDF created with pdfFactory Pro trial version www.pdffactory.com 74 số này đặc biệt quan trọng, sẽ ảnh hưởng rất nhiều đến độ chính xác của kết quả cũng như thời gian thực thi của thuật toán. Bên dưới là cây quyết định được tạo ra được thể hiện bằng một “tree view control”, nút có chữ Root phía trước được quy ước là nút gốc và nút có chữ LV là nút lá của cây. Xét tại cùng mức (level) của cây các nút có chữ L là nút thuộc nhánh trái và nút có chữ R là nút thuộc nhánh phải. Hình 4.2: Kết quả thuật toán trong trường hợp StopLevel = 3. PDF created with pdfFactory Pro trial version www.pdffactory.com 75 Hình 4.3: Kết quả thuật toán trong trường hợp StopLevel = 8. Như vậy khi tham số StopLevel càng lớn thì chiều cao cây quyết định càng nhỏ (và hiển nhiên thời gian thực thi thuật toán càng giảm). PDF created with pdfFactory Pro trial version www.pdffactory.com 76 So sánh SPRINT và Rain Forest - Hàm 1 0 2000 4000 6000 8000 10000 12000 14000 16000 18000 20000 22000 24000 0.0 0.5 1.0 1.5 2.0 2.5 Số dòng dữ liệu (triệu) Th ờ i g ia n (g iâ y) SPRINT Hybrid Data Rain Forest Đồ thị 4.4: So sánh kết quả trong trường hợp xử lý tuần tự với Hàm 1. So sánh SPRINT và Rain Forest - Hàm 7 0 2000 4000 6000 8000 10000 12000 14000 16000 18000 20000 22000 24000 26000 28000 30000 32000 0.0 0.5 1.0 1.5 2.0 2.5 Số dòng dữ liệu (triệu) Th ờ i g ia n (g iâ y) SPRINT Hybrid Data Rain Forest Đồ thị 4.5: So sánh kết quả trong trường hợp xử lý tuần tự với Hàm 7. PDF created with pdfFactory Pro trial version www.pdffactory.com 77 Với ưu điểm của mình, Hybrid Data rõ ràng vượt trội hơn các thuật toán khác trong trường hợp sự liên hệ giữa các thuộc tính không nhiều với cây kết quả tạo ra không lớn (hàm 1) và ngay cả trong trường hợp các thuộc tính có nhiều mối quan hệ với nhau dẫn đến cây kết quả được tạo ra khá phức tạp (hàm 7). Tập dữ liệu 200,000 dòng 0 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 4 5 6 7 8 9 Số thuộc tính Th ờ i g ia n (g iâ y) SPRINT Hybrid Data Rainforest - Hybrid Đồ thị 4.6: So sánh kết quả thuật toán trong trường hợp thay đổi số thuộc tính. Nhìn trên đồ thị nhận thấy đối với lượng dữ liệu trung bình chọn ngẫu nhiên từ tập dữ liệu chính, khi tăng số lượng thuộc tính lên, thời gian thực thi của SPRINT tăng rất nhanh nhưng Rain Forest và Hybrid Data tương đối tăng không tuyến tính. PDF created with pdfFactory Pro trial version www.pdffactory.com 78 4.4 ỨNG DỤNG XỬ LÝ SONG SONG Hình 4.7: Giao diện chính của ứng dụng xử lý song song. Ứng dụng xử lý song song hoàn toàn giống với ứng dụng tuần tự, trên giao diện chính của ứng dụng chỉ hiển thị thêm danh sách các địa chỉ IP của các máy con PDF created with pdfFactory Pro trial version www.pdffactory.com 79 trong ô “Host lists”. Khi khởi tạo ứng dụng song song, đầu tiên sẽ xuất hiện một hộp thoại nhập liệu yêu cầu người dùng nhập vào số máy con tham gia vào quá trình xử lý song song. Máy chủ sẽ đợi đến khi tất cả các máy con tham gia đầy đủ (tổng số máy con kết nối với máy chủ bằng số máy mà người dùng đã nhập vào). Ứng dụng song song được chạy thực nghiệm trong môi trường mạng 10MB/s; 54MB/s và 100MB/s. Số máy tham gia thử nghiệm ứng dụng là 5 máy (4 máy con và một máy chủ). Cấu hình của các máy lần lượt là: Bảng 4.2: Cấu hình các máy tham gia xử lý song song. Số thứ tự máy Cấu hình Máy chủ P.IV HyberThreading 2.2Ghz, 1 GB RAM, đĩa cứng 80GB, network card 100 MB/s. Máy con 1 P.IV HyberThreading 2.2Ghz, 1 GB RAM, đĩa cứng 40GB, network card 100MB/s Máy con 2 P.IV HyberThreading 2.2Ghz, 1 GB RAM, đĩa cứng 40GB, network card 100MB/s Máy con 3 P.IV HyberThreading 2.2Ghz, 1 GB RAM, đĩa cứng 40GB, network card 100MB/s Máy con 4 P.IV HyberThreading 2.2Ghz, 1 GB RAM, đĩa cứng 40GB, network card 100MB/s Tại thời điểm thực thi, máy chủ sẽ khởi tạo các tiến trình trên máy con, gửi thông điệp cho các máy con và nhận kết quả trả về. Toàn bộ cây quyết định được tạo ra sẽ được lưu trữ và hiển thị tại máy chủ như trường hợp của ứng dụng máy đơn. Lưu ý, hiệu năng của các thiết bị mạng cũng đóng một vai trò quan trọng trong quá trình thực thi, với các tập dữ liệu lớn thì khi thay đổi từ mạng 10MB/s sang mạng 54MB/s (wifi) và 100MB/s, tốc độ chương trình được cải thiện khoảng từ 4-7% (xem đồ thị 4.8). PDF created with pdfFactory Pro trial version www.pdffactory.com 80 Đối với trường hợp máy chủ thuần chỉ thao tác đồng bộ, điều khiển các tiến trình máy con so với máy chủ chứa dữ liệu và các thao tác cơ bản, hiệu suất thực hiện trong trường hợp sau tăng từ 6-11% (xem đồ thị 4.9). 0 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 50000 60000 70000 80000 90000 100000 số dòng dữ liệu Th ời g ia n (g iâ y) 10MB/s 54MB/s 100MB/s Đồ thị 4.8: So sánh tốc độ thực thi với các tốc độ mạng khác nhau. PDF created with pdfFactory Pro trial version www.pdffactory.com 81 0 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 50000 60000 70000 80000 90000 100000 Số dòng dữ liệu Th ời g ia n (g iâ y) Dynamic Static Đồ thị 4.9: So sánh tốc độ thực thi với nút gốc kiểu static và dynamic node. PDF created with pdfFactory Pro trial version www.pdffactory.com