Sử dụng cây quyết định trong khai phá dữ liệu

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

------------

PHẠM THỊ PHƢƠNG THẢO

SỬ DỤNG CÂY QUYẾT ĐỊNH TRONG

KHAI PHÁ DỮ LIỆU

Chuyên ngành: Khoa học máy tính

Mã số: 60.48.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Ngƣời hƣớng dẫn khoa học: GS.TS Vũ Đức Thi

Thái nguyên – Năm 2011

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

ii

LỜI CAM ĐOAN

Tôi xin cam đoan toàn bộ nội dung luận văn này là do tôi tự sƣu tầm, tra cứu

thông tin trên mạng Internet, trong một số sách tham khảo để sắp xếp, hoàn thiện

cho phù hợp với nội dung yêu cầu của đề tài.

Đến nay, nội dung luận văn của tôi chƣa từng đƣợc công bố hay xuất bản

dƣới bất kỳ hình thức nào. Nếu sai tôi xin chịu hoàn toàn trách nhiệm.

Ngày 15 tháng 09 năm 2011

Tác giả

Phạm Thị Phương Thảo

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

iii

LỜI CẢM ƠN

Trong suốt quá trình học tập và thực hiện đề tài, em đã nhận đƣợc sự giúp đỡ

tận tình và những chỉ bảo ân cần của các Thày cô trong viện Công nghệ thông tin –

Viện khoa học và công nghệ Việt nam, các Thày cô trong trƣờng đại học Công nghệ

Thông tin và Truyền thông, cùng các bạn bè đồng nghiệp. Đặc biệt là sự giúp đỡ

của GS.TS Vũ Đức Thi, ngƣời thầy trực tiếp hƣớng dẫn, đƣa ra ý trƣởng, định

hƣớng, đóng góp các ý kiến chuyên môn và tận tình giúp đỡ em trong suốt quá trình

nghiên cứu và thực hiện luận văn.

Qua đây cho phép em đƣợc bày tỏ lời cảm ơn tới tất cả các thầy cô giáo ở

Viện Công nghệ thông tin và trƣờng đại học Công nghệ Thông tin và Truyền thông,

đã giảng dạy và tạo mọi điều kiện thuận lợi giúp đỡ chúng em trong quá trình học

tập, nghiên cứu.

Cuối cùng, tôi xin cảm ơn đến gia đình, các bạn bè đồng nghiệp đã chia sẻ

động viên giúp đỡ tôi về chuyên môn cũng nhƣ về mọi mặt trong cuộc sống, đó là

nguồn động viên khích lệ giúp tôi có nghị lực hơn để hoàn thành khoá học.

Học viên

Phạm Thị Phương Thảo

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

iv

MỤC LỤC

LỜI CAM ĐOAN ............................................................................................................ii

LỜI CẢM ƠN ................................................................................................................ iii

MỤC LỤC.......................................................................................................................iv

DANH MỤC CÁC BẢNG VÀ CÁC HÌNH TRONG LUẬN VĂN..............................vi

LỜI MỞ ĐẦU..................................................................................................................1

Chƣơng 1:.........................................................................................................................3

TÌM HIỂU NHỮNG KIẾN THỨC TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU .............3

1.1. Tính cấp bách của việc khai phá dữ liệu...............................................................3

1.2. Mục tiêu của khai phá dữ liệu...............................................................................4

1.3. Quá trình phát hiện tri thức...................................................................................6

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

1.5. Các dạng dữ liệu có thể khai phá..........................................................................9

1.6. Các hƣớng tiếp cận và kỹ thuật áp dụng.............................................................10

1.7. Một số lĩnh vực ứng dụng của khai phá dữ liệu. ................................................10

1.8. Lựa chọn các kỹ thuật khai phá. .........................................................................11

1.9. Một số phƣơng pháp khai phá dữ liệu phổ biến. ................................................12

1.9.1.Cây quyết định và luật. .................................................................................12

1.9.2. Phƣơng pháp suy diễn và quy nạp. ..............................................................13

1.9.3. Luật kết hợp. ................................................................................................13

1.9.4. Phân nhóm và phân đoạn. ............................................................................13

1.9.5. Mạng neural .................................................................................................14

1.9.6. Giải thuật di truyền ......................................................................................14

Chƣơng 2:.......................................................................................................................15

KỸ THUẬT KHAI PHÁ DỮ LIỆU SỬ DỤNG CÂY QUYẾT ĐỊNH ........................15

2.1. Giới thiệu kỹ thuật khai phá dữ liệu sử dụng cây quyết định.............................15

2.2. Thuật toán sử dụng cho việc xây dựng cây quyết định ......................................17

2.2.1. Thuật toán CLS ............................................................................................17

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

v

2.2.2. Thuật toán ID3 .............................................................................................22

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

2.3. Rút gọn cây quyết định .......................................................................................47

2.4. Rút gọn các luật từ cây quyết định .....................................................................54

2.5. Đánh giá, kết luận về các thuật toán xây dựng cây quyết định ..........................55

Chƣơng 3:.......................................................................................................................57

CÀI ĐẶT THỬ NGHIỆM .............................................................................................57

3.1. Thiết kế tổng thể .................................................................................................57

3.2. Chuẩn bị dữ liệu..................................................................................................58

3.3. Thiết kế chƣơng trình..........................................................................................66

3.4. Kết qủa thực nghiệm và đánh giá ......................................................................67

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN .....................................................................68

TÀI LIỆU THAM KHẢO..............................................................................................69

PHỤ LỤC.......................................................................................................................70

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

vi

DANH MỤC CÁC BẢNG VÀ CÁC HÌNH

TRONG LUẬN VĂN

Danh mục các bảng

Bảng 2.1 Tập dữ liệu huấn luyện quyết định chơi tennis...............................................18

Bảng 2.2 Bảng thống kê mức độ nguy hiểm khi lái xe và độ tuổi của lái xe ...............42

Bảng 2.3. Bảng thông tin phân bổ lớp của thuộc tính Tuổi ...........................................42

Bảng 2.4. Bảng thông tin phân bổ lớp của thuộc tính Loại xe.......................................43

Bảng 2.5: Tìm ngƣỡng cho phép tách với thuộc tính Tuổi ............................................45

Bảng 3.1. Bảng dữ liệu về những giấu hiệu của bệnh nhân nhiễm cúm H1N1 .............58

Bảng 3.2. Bảng tập dữ liệu con ứng với Cổ họng = Ho thƣờng ....................................61

Bảng 3.3. Bảng tập dữ liệu con ứng với Cổ họng = Ho khan........................................63

Bảng phụ lục: Logarit cơ số hai của các số nguyên từ 1 đến 100..................................70

Danh mục các hình

Hình 1.1: Quá trình phát hiện tri thức ..............................................................................6

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

Hình 2.1: Khai triển cây theo thuộc tính quang cảnh.....................................................18

Hình 2.2:Khai triển cây theo thuộc tính Quang cảnh-Nhiệt độ .....................................19

Hình 2.3: Khai triển cây theo thuộc tính Quang cảnh-Nhiệt độ-độ ẩm.........................19

Hình 2.4: Khai triển cây theo thuộc tính Quang cảnh-nhiệt độ-độ ẩm-Gió...................20

Hình 2.5:Khai triển cây theo thuộc tính quang cảnh-độ ẩm ..........................................21

Hình 2.6: Khai triển cây theo thuộc tính quang cảnh-độ ẩm -gió..................................21

Hình 2.7: Khai triển cây quyết định theo thuộc tính quang cảnh ..................................29

Hình 2.8: Xây dựng cây theo thuộc tính độ ẩm .............................................................32

Hình 2.9: Khai triển cây theo thuộc tính quang cảnh –độ ẩm........................................32

Hình 2.10: Khai triển cây theo thuộc tính quang cảnh = “âm u”...................................33

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

vii

Hình 2.11: Cây quyết định theo thuộc tính quang cảnh-độ ẩm-gió ...............................35

Hình 2.12. Cây quyết định đi chơi Tennis sử dụng thuật toán ID3 ...............................35

Hình 2.13 : Khai triển cây theo thuộc tính Loại xe........................................................45

Hình 2.14: Khai triển cây theo thuộc tính Loại xe-Tuổi................................................47

Hình 2.15. Cây kết quả sử dụng thuật toán C4.5 ...........................................................47

Hình 2.16: Cây trƣớc khi cắt tỉa.....................................................................................49

Hình 2.17. Cây trƣớc khi cắt tỉa .....................................................................................52

Hình 2.18. Cây sau khi cắt tỉa ........................................................................................53

Hình 3.1: Khai triển cây quyết định theo thuộc tính “Cổ Họng”...................................60

Hình 3.2: Khai triển cây quyết định theo thuộc tính Cổ Họng = “Ho có đờm” ............61

Hình 3.3: Khai triển cây quyết định theo thuộc tính Đầu ..............................................63

Hình 3.4: Khai triển cây quyết định theo thuộc tính Mũi ..............................................64

Hình 3.5: Cây quyết định sử dụng thuật toán ID3 .........................................................65

Hình 3.7. Giao diện chính của chƣơng trình.................................................................66

Hình 3.8. Dữ liệu đƣợc nhập vào cho chƣơng trình......................................................66

Hình 3.9. Giao diện xây dựng cây quyết định................................................................67