TRƢỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
------------
BÁO CÁO THỰC TẬP
TỐT NGHIỆP
ĐỀ TÀI: KHAI PHÁ DỮ LIỆU BẰNG CÂY QUYẾT ĐỊNH VÀ
ỨNG DỤNG
Giảng viên hƣớng dẫn: Ths. Trần Hùng Cƣờng
Sinh viên thực hiện: Nguyễn Bá Nguyện
Lớp: Khoa học máy tính 3
Khóa: 4
Hà Nội, Tháng 3 năm 2013
LỜI MỞ ĐẦU
Trong thời đại ngày nay, yếu tố quyết định thành công trong mọi lĩnh vực luôn gắn
liền với việc nắm bắt, thống kê và khai thác thông tin hiệu quả. Dữ liệu ngày càng lớn
nên việc tìm ra những thông tin tiềm ẩn trong chúng càng khó khăn hơn.
Khai phá tri thức là một lĩnh vực nghiên cứu mới, mở ra một thời kỳ trong việc
tìm ra thông tin hữu ích. Nhiệm vụ cơ bản của lĩnh vực này là khai phá tri thức trong
cơ sở dữ liệu, khai phá dữ liệu trong cơ sở dữ liệu không phải là một hệ thống phân
tích tự động mà là một quá trình tƣơng tác thƣờng xuyên giữa con ngƣời với cơ sở dữ
liệu đƣợc sự trợ giúp của nhiều phƣơng pháp và công cụ tin học.
Em xin bày tỏ sự biết ơn sâu sắc của mình tới Ths Trần Hùng Cƣờng ngƣời đã trực
tiếp hƣớng dẫn, chỉ bảo tận tình, cung cấp tài liệu và phƣơng pháp nghiên cứu khoa
học để em hoàn thành bản luận văn này. Em xin gửi lời cảm ơn tới các thầy cô giáo đã
dạy dỗ trong quá trình em theo học tại Trƣờng.
Trong suốt quá trình nghiên cứu, mặc dù đã hết sức cố gắng nhƣng chắc chắn bài
luận không tránh khỏi những thiếu sót, rất mong quý thầy cô góp ý để luận văn đƣợc
hoàn chỉnh hơn.
Em xin chân thành cảm ơn!
Ký tên
Nguyện
Nguyễn Bá Nguyện
TÓM TẮT NỘI DUNG
Nội dung luận văn em xin trình bày bao gồm ba chƣơng:
Chƣơng một: giới thiệu chung về công nghệ khai phá trí thức, các khái niệm cơ bản, ý
nghĩa và tầm quan trọng của việc khai phá tri thức.
Chƣơng hai: trình bày các phƣơng pháp khai phá dữ liệu bằng cây quyết định, khái
niệm cơ bản về cây quyết định, các thuật toán xây dựng cây quyết định: CLS, ID3,
C4.5, rút gọn các luật quyết định và đánh giá các thuật toán xây dựng cây quyết định.
Chƣơng ba: cài đặt chƣơng trình hỗ trợ ra quyết đinh bằng cây quyết đinh dựa trên
thuật toán C4.5.
MỤC LỤC
LỜI MỞ ĐẦU .............................................................................................................. 2
TÓM TẮT NỘI DUNG ............................................................................................... 3
MỤC LỤC ................................................................................................................... 4
DANH SÁCH HÌNH VẼ ............................................................................................. 6
PHẦN MỞ ĐẦU ......................................................................................................... 7
CHƢƠNG 1: GIỚI THIỆU CHUNG VỀ KHAI PHÁ TRI THỨC ......................... 8
1.1 Phát hiện tri thức và khai phá dữ liệu........................................................................... 8
1.2 Quá trình phát hiện tri thức từ cơ sở dữ liệu ................................................................ 8
1.2.1. Hình thành và định nghĩa bài toán. ...................................................... 9
1.2.2. Thu thập và xử lý dữ liệu. ..................................................................... 9
1.2.3. Khai thác dữ liệu và rút ra tri thức ..................................................... 10
1.2.4. Phân tích và đánh giá tri thức ............................................................ 10
1.2.5. Sử dụng tri thức phát hiện được ......................................................... 10
1.3. Khai phá dữ liệu ......................................................................................................... 11
1.3.1. Các quan niệm về khai phá dữ liệu. .................................................... 11
1.3.2. Quá trình khái phá dữ liệu. ................................................................. 12
1.3.3. Kiến trúc của hệ thống khai phá dữ liệu. ............................................ 14
1.4. Các kỹ thuật khai phá dữ liệu ..................................................................................... 15
1.4.1. Phân lớp dữ liệu .................................................................................. 15
1.4.2. Phân cụm dữ liệu ................................................................................ 16
1.4.3. Cây quyết định .................................................................................... 16
1.4.4. Luật kết hợp ......................................................................................... 16
1.4.5. Hồi quy ................................................................................................ 16
1.4.6. Mạng Nơron ........................................................................................ 16
1.4.7. Giải thuật di truyền ............................................................................. 17
CHƢƠNG 2: CÁC PHƢƠNG PHÁP KHAI PHÁ DỮ LIỆU BẰNG CÂY
QUYẾT ĐỊNH ......................................................................................................... 18
2.1 Cây quyết định ........................................................................................................... 18
2.1.1 Giới thiệu ............................................................................................ 18
2.1.2 Các kiểu cây quyết định ...................................................................... 18
2.1.3 Ưu điểm của cây quyết định ............................................................... 19
2.1.4 Phân lớp dữ liệu bằng cây quyết định ................................................ 19
2.1.5 Xây dựng cây quyết định. .................................................................... 21
2.1.6 Rút ra luật từ cây quyết định .............................................................. 22
2.2 Các thuật toán xây dựng cây quyết định .................................................................... 22
2.2.1 Thuật toán CLS ................................................................................... 22
2.2.2 Thuật toán ID3 .................................................................................... 23
2.2.3 Thuật toán C4.5 ................................................................................... 25
2.2.4 Cắt tỉa cây quyết định .......................................................................... 31
2.2.5 Đánh giá và kết luận về các thuật toán xây dựng cây quyết định ....... 33
CHƢƠNG 3: CẶT ĐẶT CHƢƠNG TRÌNH KHAI PHÁ DỮ LIỆU SỬ DỤNG
CÂY QUYẾT ĐỊNH ................................................................................................. 36
3.1 Bài toán thực tế .......................................................................................................... 36
3.2 Cài đặt thuật toán....................................................................................................... 36
3.3 Hình ảnh demo ........................................................................................................... 40
KẾT LUẬN ................................................................................................................ 44
TÀI LIỆU THAM KHẢO ......................................................................................... 45