Luận Văn Khai phá dữ liệu bằng cây quyết định

MỤC LỤC

LỜI MỞ ĐẦU 3

Chương 1: Tổng quan về khai phá dữ liệu 4

1.1. Khám phá tri thức và khai phá dữ liệu là gì? 4

1.2. Quá trình phát hiện tri thức 5

1.2.1. Hình thành và định nghĩa bài toán 5

1.2.2. Thu thập và tiền xử lý dữ liệu 6

1.2.3. Khai phá dữ liệu và rút ra các tri thức 6

1.2.4. Phân tích và kiểm định kết quả 7

1.2.5. Sử dụng các tri thức phát hiện được 7

1.3. Quá trình khai phá dữ liệu 7

1.3.1. Gom dữ liệu (gatherin) 8

1.3.2. Trích lọc dữ liệu (selection) 8

1.3.3. Làm sạch và tiền xử lý dữ liệu (cleansing preprocessing). 8

1.3.4. Chuyển đổi dữ liệu (transformation) 91.3.5. Phát hiện và trích mẫu dữ liệu ( pattern extraction and discovery) 9

1.3.6. Đánh giá kết quả mẫu (evaluation of result ) 9

1.4. Chức năng của khai phá dữ liệu 9

1.5. Các kỹ thuật khai phá dữ liệu 10

1.5.1. Phân lớp dữ liệu: 10

1.5.2. Phân cụm dữ liệu: 10

1.5.3. Khai phá luật kết hợp: 10

1.5.4. Hồi quy: 11

1.5.5. Giải thuật di truyền: 11

1.5.6. Mạng nơron: 11

1.5.7. Cây quyết định. 12

1.6. Các dạng dữ liệu có thể khai phá được 12

1.7. Các lĩnh vực liên quan đến khai phá dữ liệu và ứng dụng của khai phá dữ liệu 12

1.7.1. Các lĩnh vực liên quan đến phát hiện tri thức và khai phá dữ liệu 12

1.7.2. Ứng dụng của khai phá dữ liệu 12

1.8. Các thách thức và hướng phát triển của phát hiện tri thức và khai phá dữ liệu. 13

Chương 2: Khai phá dữ liệu bằng cây quyết định 14

2.1. Cây quyết định 14

2.1.1. Định nghĩa cây quyết định 14

2.1.2. Ưu điểm của cây quyết định 15

2.1.3. Vấn đề xây dựng cây quyết định 15

2.1.4. Rút ra các luật từ cây quyết định. 16

2.2. Các thuật toán khai phá dữ liệu bằng cây quyết định 16

2.2.1. Thuật toán CLS 16

2.2.2. Thuật toán ID3 17

2.2.3. Thuật toán C4.5 19

2.2.4. Thuật toán SLIQ[5] 23

2.2.5. Cắt tỉa cây quyết định 26

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 28

Chương 3: Xây dựng chương trình dêmo 30

3.1. Mô tả bài toán 30

3.2. Thu thập và tiền xử lý dữ liệu 30

3.3. Chương trình 31

Chương 4. KẾT LUẬN 32

4.1 Đánh Giá 32

4.1.1 Lý thuyết 32

4.1.2 Ứng dụng 32

4.2 Hướng Phát Triển 32




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. Người ta lưu trữ những dữ liệu này vì cho rằng nó ẩn chứa những giá trị nhất định nào đó. Tuy nhiên theo thống kê thì chỉ có một lượng nhỏ của những dữ liệu này (khoảng từ 5% đến 10%) là luôn được phân tích, số còn lại họ không biết sẽ phải làm gì và có thể làm gì với những dữ liệu này, nhưng họ vẫn tiếp tục thu thập và lưu trữ vì hy vọng những dữ liệu này sẽ cung cấp cho họ những thông tin quý giá một cách nhanh chóng để đưa ra những quyết định kịp thời vào một lúc nào đó. Chính vì vậy, các phương pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp ứng được thực tế đã làm phát triển một khuynh hướng kỹ thuật mới đó là Kỹ thuật phát hiện tri thức và khai phá dữ liệu (KDD - Knowledge Discovery and Data Mining).

Kỹ thuật phát hiện tri thức và khai phá dữ liệu đã 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à bắt đầu đưa vào một số ứng dụng thực tế. Vì vậy, hiện nay ở nước ta vấn đề phát hiện tri thức và khai phá dữ liệu đ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. Trong phạm vi đề tài nghiên cứu khoa học này của em, em sẽ trình bày những nội dung sau:

Chương 1: Tìm hiểu những kiến thức tổng quan về khám phá tri thức và khai phá dữ liệu.

Chương 2: Nghiên cứu kỹ thuật khai phá dữ liệu bằng cây quyết định.

Chương 3: Xây dựng ứng dụng demo cho kỹ thuật khai phá dữ liệu bằng cây quyết định