Thạc Sĩ Một số phương pháp khai phá luật kết hợp trên cơ sở dữ liệu gia tăng

3

MỤC LỤC
LỜI CAM ĐOAN 1
LỜI CẢM ƠN . 2
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT . 5
DANH MỤC HÌNH VẼ 6
DANH MỤC BẢNG BIỂU . 7
CHƯƠNG 1: KHAI PHÁ LUẬT KẾT HỢP 9
1.1 Tổng quan về khai phá dữ liệu . 9
1.2 Giới thiệu về khai phá luật kết hợp 10
1.3 Một số khái niệm cơ bản [3, 5, 7] 11
1.3.1 Cơ sở dữ liệu giao tác . 11
1.3.2 Tập mục thường xuyên . 13
1.3.3 Luật kết hợp 14
1.4 Một số thuật toán khai phá luật kết hợp . 16
1.4.1 Thuật toán AIS 16
1.4.2 Thuật toán Apriori . 18
CHƯƠNG 2: KHAI PHÁ LUẬT KẾT HỢP TRÊN CƠ SỞ DỮ LIỆU GIA TĂNG
21
2.1 Mở đầu 21
2.2 Thuật toán xử lý dữ liệu gia tăng theo chiều dọc - Thuật toán Gia tăng 1 . 21
2.2.1 Ý tưởng thuật toán 21
2.2.2 Chuyển đổi cơ sở dữ liệu sang chiều dọc . 23
2.2.3 Các thủ tục phụ trợ 24
2.2.4 Tìm tập mục ứng viên . 27
2.2.5 Tính độ hỗ trợ của tập mục ứng viên . 28
2.2.6 Khai phá tập thường xuyên . 29
2.2.7 Xử lý dữ liệu gia tăng 31
2.2.8 Ví dụ minh họa . 32
2.2.9 Nhận xét về thuật toán gia tăng 1 34
2.3 Thuật toán xử lý dữ liệu gia tăng theo chiều ngang – Thuật toán Gia tăng 2 35 4

2.3.1 Ý tưởng thuật toán 35
2.3.2 Xây dựng cây gia tăng . 36
2.3.3 Khai phá tập thường xuyên . 39
2.3.4 Lưu trữ và khôi phục cây gia tăng . 41
2.3.5 Ví dụ minh họa . 44
2.3.6 Nhận xét về thuật toán Gia tăng 2 . 47
2.3.7 Đề xuất ý tưởng cải tiến cấu trúc cây gia tăng . 47
CHƯƠNG 3: CÀI ĐẶT CHƯƠNG TRÌNH THỬ NGHIỆM 53
3.1 Mô tả chương trình chạy 53
3.2 Thử nghiệm đánh giá thuật toán Gia tăng 1 . 56
3.2.1 Thử nghiệm và đánh giá thuật toán trên nội dung 1, 2 . 56
3.2.2 Thử nghiệm và đánh giá thuật toán trên nội dung 3 . 60
3.3 Kết luận . 62
KẾT LUẬN . 64
TÀI LIỆU THAM KHẢO . 65