ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
HOÀNG THỊ KIM OANH
KHAI PHÁ DỮ LIỆU DỰA TRÊN BẢNG QUYẾT ĐỊNH
NHỜ LÝ THUYẾT TẬP THÔ
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Hà Nội - 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
HOÀNG THỊ KIM OANH
KHAI PHÁ DỮ LIỆU DỰA TRÊN BẢNG QUYẾT ĐỊNH
NHỜ LÝ THUYẾT TẬP THÔ
Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60480104
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƢỜI HƢỚNG DẪN KHOA HỌC: GS.TS. VŨ ĐỨC THI
Hà Nội - 2014
1
LỜI CẢM ƠN
Trước tiên, tôi xin gửi lời cảm ơn chân thành nhất tới GS.TS Vũ Đức Thi,
Viện Công nghệ thông tin – Đại học Quốc gia Hà Nội đã tận tình hướng dẫn, định
hướng, đóng góp những ý kiến quý báu cho tôi trong quá trình thực hiện luận văn.
Tôi xin chân thành cảm ơn các Thầy, Cô giáo trong Trường Đại học Công
nghệ - Đại học Quốc gia Hà Nội đã tận tình giảng dạy và truyền thụ cho tôi những
kiến thức quý báu trong suốt quá trình học tập tại trường. Đồng thời, tôi cũng xin
cảm ơn gia đình, bạn bè, những người luôn khuyến khích và giúp đỡ tôi trong mọi
hoàn cảnh khó khăn. Tôi xin cảm ơn cơ quan và các đồng nghiệp đã hết sức tạo điều
kiện cho tôi trong suốt quá trình học tập và làm luận văn này.
Hà Nội, ngày tháng 6 năm 2014
Học viên
Hoàng Thị Kim Oanh
2
LỜI CAM ĐOAN
Tôi xin cam đoan những kiến thức trình bày trong luận văn này là do tôi
tìm hiểu, nghiên cứu và trình bày lại theo cách hiểu của tôi. Trong quá trình làm
luận văn tôi có tham khảo các tài liệu có liên quan và đã ghi rõ nguồn tài liệu
tham khảo đó. Phần lớn những kiến thức tôi trình bày trong luận văn này chưa
được trình bày hoàn chỉnh trong bất cứ tài liệu nào.
Hà Nội, ngày tháng 6 năm 2014
Học viên
Hoàng Thị Kim Oanh
3
MỤC LỤC
LỜI CẢM ƠN ............................................................................................................................................................ 1
LỜI CAM ĐOAN..................................................................................................................................................... 2
MỤC LỤC ................................................................................................................................................................... 3
DANH MỤC CÁC THUẬT NGỮ .................................................................................................................... 5
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ........................................................................... 6
DANH MỤC CÁC BẢNG ................................................................................................................................... 7
DANH MỤC CÁC HÌNH VẼ ............................................................................................................................. 8
MỞ ĐẦU ...................................................................................................................................................................... 9
Chƣơng 1. KHAI PHÁ DỮ LIỆU THEO TIẾP CẬN TẬP THÔ .................................................... 12
1.1. Hệ thông tin ........................................................................................................................... 12
1.2. Bảng quyết định .................................................................................................................... 13
1.3. Quan hệ không phân biệt được ............................................................................................ 14
1.4. Các tập xấp xỉ ........................................................................................................................ 16
1.5. Tập rút gọn và tập lõi ............................................................................................................ 18
1.6. Ma trận phân biệt và hàm phân biệt .................................................................................... 20
Chƣơng 2. PHƢƠNG PHÁP RÚT GỌN THUỘC TÍNH VÀ SINH LUẬT TRÊN BẢNG
QUYẾT ĐỊNH ........................................................................................................................................................ 21
2.1. Phương pháp rút gọn thuộc tính trên bảng quyết định ...................................................... 21
2.2. Phương pháp rút gọn thuộc tính dựa trên entropy Shannon ............................................. 25
2.2.1. Entropy Shannon trên bảng quyết định .................................................................. 25
2.2.2. Tập lõi của bảng quyết định dựa trên Entropy Shannon ........................................ 26
2.2.3. Tập rút gọn của bảng quyết định dựa trên Entropy Shannon .................................. 27
2.2.4. Độ quan trọng của thuộc tính dựa trên entropy Shannon ....................................... 27
2.2.5. Thuật toán tìm tập rút gọn của bảng quyết định sử dụng Entropy Shannon .......... 28
2.3. Sinh luật quyết định trên tập rút gọn của bảng quyết định ................................................ 34
2.3.1. Luật quyết định ....................................................................................................... 34
2.3.2. Các độ đo đánh giá hiệu năng tập luật quyết định trên các tập rút gọn .................. 35
2.3.3. Thuật toán sinh luật quyết định dựa trên tập rút gọn của bảng quyết định ............. 38
Chƣơng 3. THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ ...................................................................... 40
3.1. Bài toán .................................................................................................................................. 40
3.2. Một số kết quả thử nghiệm .................................................................................................. 40
