Đồ Án Tìm hiểu và cài đặt một số thuật toán tìm luật phân lớp

MỤC LỤC: Trang

Lời nói đầu 3
Phần 1: Tìm hiểu về phân lớp dữ liệu 4
1.1 Phân lớp dữ liệu là gì?
1.2 Một số ứng dụng phân lớp tiêu biểu
1.3 Tiến trình phân lớp dữ liệu
1.4 Tiền xử lý dữ liệu để tiến hành phân lớp
1.5 Các phương pháp phân lớp
1.6 Tiêu chuẩn để đánh giá các phương pháp phân lớp
1.7 Độ chính xác trong phân lớp
Phần 2: Phân lớp dữ liệu dựa vào các rút gọn (Reducts) 7
2.1 Định nghĩa rút gọn
2.2 Ma trận phân biệt
2.3 Hàm phân biệt
2.4 Tìm các reduct từ hàm phân biệt (sử dụng luật để rút gọn hàm phân biệt)
2.5 Xác định các lớp tương đương của thuộc tính kết quả
2.6 Tìm các lớp tương đương ứng với từng Reduct (tập các thuộc tính)
2.7 Xây dựng các luật phân lớp dựa vào các Lớp tương đương của thuộc tính kết quả và các Lớp tương đương ứng với từng Reduct
2.8 Rút gọn tập luật thu được
Phần 3: Phân lớp dữ liệu bằng cách xây dựng cây quyết định 11
3.1 Khái niệm cây quyết định
3.2 Tạo cây quyết định, các tiêu chuẩn để xây dựng cây quyết định
3.3 Rút luật phân lớp từ cây quyết định
3.4 Overfitting trong phân lớp bằng cây quyết định
Phần 4: Cài đặt thuật toán Phân lớp dữ liệu dựa vào các rút gọn 15
(Minh họa bằng C#)
4.1 Cấu trúc dữ liệu 16
4.2 Cài đặt 17
Phần 5: Cài đặt thuật toán xây dựng cây quyết định để phân lớp dữ liệu 24
(Minh họa bằng C#)
5.1 Cấu trúc dữ liệu 25
5.2 Cài đặt 25
Nhận xét và kết luận 31
Hướng phát triển 32
Tài liệu tham khảo 33
Phụ lục 34
Phụ lục A: Các Form của chương trình 34
Phụ lục B: Kết quả thực thi chương trình với tập dữ liệu test thử 42












Lời nói đầu
Ngày nay, vấn đề làm thế nào để có được các thông tin hữu ích từ các cơ sở dữ liệu khổng lồ đang rất được quan tâm phát triển, công việc đó được người ta đặt cho tên gọi là Data Mining. Và phân lớp dữ liệu là một trong những bài toán cơ bản và có rất nhiều ứng dụng của Data Mining. Có nhiều thuật toán để phân lớp dữ liệu, trong khuôn khổ khóa luận này, em xin trình bày hai thuật toán khá tiêu biểu và hiệu quả để tìm các luật phân lớp cho tập dữ liệu huấn luyện, đó là thuật toán tìm luật phân lớp bằng cách xây dựng cây quyết định và dùng ma trận phân biệt của tập dữ liệu huấn luyện để tìm các reduct, từ đó thành lập các lớp tương đương để tạo luật phân lớp.
Phần cài đặt chỉ sử dụng ý tưởng của thuật toán, cách thể hiện là của riêng cá nhân, cho nên về bố cục cài đặt giải thuật có thể gây khó hiểu, tuy nhiên vẫn đảm bảo tính chính xác của thuật toán. Và trong quá trình tìm hiểu, em đã thêm vào một số cải tiến làm tăng tốc độ thực hiện chương trình (ví dụ như loại bỏ các record sinh luật phân lớp vô nghĩa trước khi bắt đầu phân lớp ), và dùng giao diện chương trình hỗ trợ để mang lại tính tiện dụng cho người sử dụng.
Các khái niệm và thuật toán liên quan cũng được trình bày chi tiết trong khóa luận.
Em xin chân thành cảm ơn Thầy Đỗ Phúc đã rất nhiệt tình trong giảng dạy, cho em có được những kiến thức quí báo để thực hiện khóa luận này. Em mong tiếp tục nhận được sự góp ý từ Thầy để em có được sự hiểu biết hoàn chỉnh hơn về bài toán hữu ích này.