Thạc Sĩ Nghiên cứu phương pháp cây quyết định và cài đặt mô phỏng thuật toán id3

MỤC LỤC
LỜI MỞ ĐẦU . 1
Phần 1: TỔNG QUAN VỀ PHÁT HIỆN TRI THỨC VÀ 2
KHAI PHÁ DỮ LIỆU 2
1.1. Khái quát chung về phát hiện tri thức và khai phá dữ liệu. . 2
1.2. Quá trình khám phá tri thức . 3
1.2.1. Hình thành và định nghĩa bài toán 4
1.2.2. Thu thập và tiền xử lý dữ liệu 4
1.2.3. KPDL và rút ra các tri thức . 5
1.2.4. Phân tích và kiểm định kết quả 5
1.2.5. Sử dụng các tri thức phát hiện được 5
1.3. Quá trình KPDL 6
1.3.1. Gom dữ liệu ( gatherin ) 6
1.3.2. Trích lọc dữ liệu ( selection ) . 7
1.3.3. Làm sạch và tiền xử lý dữ liệu ( cleansing preprocessing preparation ). . 7
1.3.4. Chuyển đổi dữ liệu ( transformation ) . 7
1.3.5. Phát hiện và trích mẫu dữ liệu ( pattern extraction and discovery) 7
1.3.6. Đánh giá kết quả ( evaluation of result ) . 7
1.4. Chức năng của KPDL 8
1.5. Các kỹ thuật KPDL . 8
1.5.1. Phân lớp dữ liệu: . 8
1.5.2. Phân cụm dữ liệu: 9
1.5.3. Khai phá luật kết hợp: . 9
1.5.4. Hồi quy: . 9
1.5.5. Giải thuật di truyền: 9
1.5.6. Mạng nơron: 9
1.5.7. Cây quyết định. 10
1.6. Các dạng dữ liệu có thể khai phá được . 10
1.7. Các lĩnh vực liên quan và ứng dụng của KPDL 10
1.7.1. Các lĩnh vực liên quan đến khám phá tri thức và KPDL . 10
1.7.2. Ứng dụng của KPDL . 11
1.8. Các thách thức và hướng phát triển của KPDL. 12
Phần 2: CÂY QUYẾT ĐỊNH VÀ CÁC THUẬT TOÁN KHAI PHÁ DỮ
LIỆU BẰNG CÂY QUYẾT ĐỊNH 13
2.1 Cây quyết định . 13
2.1.1 Mô tả 13
2.1.2 Định nghĩa cây quyết định . 13
2.1.3 Ưu điểm của cây quyết định. 15
2.1.4 Vấn đề xây dựng cây quyết định 16
2.1.5 Rút ra các luật từ cây quyết định. 17
2.2 Các thuật toán KPDL bằng cây quyết định . 18
2.2.1 Thuật toán CLS 18
2.2.2. Thuật toán ID3 . 23
2.2.3. Thuật toán C4.5 . 38
2.2.4. Thuật toán SLIQ . 52
2.2.5. Cắt tỉa cây quyết định 61
2.2.6. Đánh giá và kết luận về các thuật toán xây dựng cây quyết định. 66
Phần 3: CÀI ĐẶT MÔ PHỎNG THUẬT TOÁN ID3 69
3.1. Mô tả bài toán . 69
3.2. Màn hình nhập dữ liệu của chương trình 69
3.3. Màn hình phân tích dữ liệu đưa ra kết quả của chương trình . 70
Phần 4: KẾT LUẬN 71
TÀI LIỆU THAM KHẢO . 72
Tài Liệu Tiếng Việt 72
Tài Liệu Tiếng Anh 72
Danh Sách Website 72

LỜI MỞ ĐẦU
Trong nhiều năm qua, cùng với sự phát triển của công nghệ thông tin và ứng
dụng của công nghệ thông tin trong nhiều lĩnh vực của đời sống xã hội, thì lượng dữ
liệu được các cơ quan thu thập và lưu trữ ngày một nhiều lên. Theo thống kê thì
trong lượng dữ liệu đó chỉ có khoảng từ 5% đến 10% dữ liệu là luôn được phân tích,
số còn lại người ta không biết sẽ phải làm gì với chúng. Tuy nhiên con người vẫn
tiếp tục thu thập và lưu trữ dữ liệu vì cho rằng chúng ẩn chứa những giá trị nhất
định nào đó, chẳng hạn có thể cung cấp cho họ thông tin đưa ra quyết định chiến
lựoc một cách nhanh chóng trong một lúc nào đó. Chính do lượng dữ liệu được lưu
trữ ngày càng nhiều lên đến mức khổng lồ thì các phương pháp quản trị và khai thác
dữ liệu truyền thống ngày càng không đáp ứng được nhu cầu của thực tế và đã làm
phát triển một khuynh hướng kỹ thuật mới đó là Kỹ thuật khám phá tri thức và
KPDL (Khai phá dữ liệu).
Kỹ thuật khám phá tri thức và KPDL đã và đang được nghiên cứu, ứng dụng
trong nhiều lĩnh vực khác nhau trên thế giới. Tại Việt Nam, kỹ thuật này còn tương
đối mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa vào một số ứng dụng
thực tế; đặc biệt trong lĩnh vực giáo dục đào tạo thì chưa có một ứng dụng thiết thực
nào. Hiện nay vấn đề khám phá tri thức và KPDL cũng đang thu hút được sự quan
tâm của nhiều người và nhiều công ty phát triển ứng dụng công nghệ thông tin ở
nước ta.
Luận văn này bao gồm các nội dung sau:
Chương 1: Tổng quan về phát hiện tri thức và khai phá dữ liệu.
Chương 2: Cây quyết định và các thuật toán khai phá dữ liệu bằng cây quyết định.
Chương 3: Cài đặt mô phỏng thuật tóan ID3