MỤC LỤC
MỞ ĐẦU ………………………………………………………………………………………. 3
CHƯƠNG 1. TỔNG QUAN KHAI PHÁ MẪU DÃY THƯỜNG
XUYÊN VÀ MỘT SỐ MỞ RỘNG ………………………………………………………. 5
1.1. GIỚI THIỆU …………………………………………………………………………. 5
1.2. MỘT SỐ KHÁI NIỆM CƠ BẢN …………………………………………………… 6
1.3. KHAI PHÁ MẪU DÃY THƯỜNG XUYÊN ……………………………………… 9
1.3.1. Thuật toán GSP: ……………………………………………………………. 10
1.3.2. Thuật toán PrefixSpan: ………………………………………………….. 13
a) Một số định nghĩa: ………………………………………………………………….. 13
b) Mô tả thuật toán: ……………………………………………………………………. 15
1.4. MỞ RỘNG BÀI TOÁN KHAI PHÁ MẪU DÃY THƯỜNG XUYÊN ………… 17
1.5. KẾT LUẬN CHƯƠNG 1 …………………………………………………………. 19
CHƯƠNG 2. KHAI PHÁ MẪU DÃY LỢI ÍCH CAO ………………… 21
2.1. GIỚI THIỆU ……………………………………………………………………….. 21
2.2. BÀI TOÁN KHAI PHÁ MẪU DÃY LỢI ÍCH CAO ……………………………. 23
2.3. THUẬT TOÁN UL, US …………………………………………………………. 28
2.3.1. Thuật toán UL: ……………………………………………………………… 28
2.3.2. Thuật toán US: ……………………………………………………………… 32
2.4. THUẬT TOÁN PHUS …………………………………………………………… 35
2.4.1. Bảng lợi ích: …………………………………………………………………. 36
2.4.2. Bảng chỉ mục: ………………………………………………………………. 37
2.5. KẾT LUẬN CHƯƠNG 2 …………………………………………………………. 44
CHƯƠNG 3. KHAI PHÁ MẪU DÃY LỢI ÍCH CAO VỚI
KHOẢNG CÁCH THỜI GIAN …………………………………………………………. 46
3.1. GIỚI THIỆU ……………………………………………………………………….. 46
3.2. BÀI TOÁN KHAI PHÁ MẪU DÃY LỢI ÍCH CAO VỚI KHOẢNG CÁCH THỜI
GIAN 47
3.2.1. Một số định nghĩa: ………………………………………………………… 47
3.2.2. Khai phá mẫu dãy lợi ích cao với khoảng cách thời gian …… 51
3.2.3. Thuật toán UIL: ……………………………………………………………. 52
a) Ràng buộc thời gian: ……………………………………………………………….. 52
b) Bảng lợi ích: ………………………………………………………………………….. 52
c) Giảm dần cận trên lợi ích swu ………………………………………………….. 53
3.2.4. Thử nghiệm thuật toán UIL …………………………………………….. 60
3.3. KẾT LUẬN CHƯƠNG 3 …………………………………………………………. 66
CHƯƠNG 4. KẾT LUẬN VÀ KIẾN NGHỊ ……………………………….. 67
TÀI LIỆU THAM KHẢO ……………………………………………………………. 69
