Ngày nay công nghệ thông tin luôn luôn phát triển và không ngừng đổi m ới, cùng với sựphát triển đó là các hệthống thông tin phục vụviệc tựđộng hoá trong các lĩnh vực của con người cũng được triển khai vượt bậc. Điều đó đã tạo ra những dòng dữ liệu khổng lồ. Nhiều hệquản trịCSDL mạnh cũng đã ra đời giúp chúng ta khai thác hiệu quảnguồn tài nguyên đã thu thập được.
Với lượng dữliệu, thông tin thu thập được ngày càng nhiều như vậy đòi hỏi chúng ta phải trích rút ra những thông tin tiềm ẩn nhằm đưa ra các quyết định đúng đắn trong công việc. Xuất phát từ thực tiễn đó, vào những năm cuối của thế kỷ 20 khai phá dữliệu ra đời. Đây là m ột lĩnh vực nghiên cứu khá mới mẻ của ngành khoa học máy tính và khai phá tri thức (KDD). Nó đã thu hút sự quan tâm của rất nhiều người ở các lĩnh vực khác nhau như : các hệCSDL, thống kê, nhận dạng, máy học, trí tuệ nhân
tạo...

MỤC LỤC
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ................................ ...... 5
DANH MỤC CÁC HÌNH VẼ ................................ ................................ ............ 6
LỜI MỞ ĐẦU ................................ ................................ ................................ .... 7
Chương 1 ................................ ................................ ................................ .......... 9
TỔNG QUAN KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI THỨC............ 9
1.1. Khái niệm phát hiện tri thức và khai phá dữ liệu ................................ ...... 9
1.2. Các bước trong quá trình phát hiện tri thức[7] ................................ ........ 10
1.3. Kiến trúc hệ thống khai phá dữ liệu ................................ ........................ 12
1.4.1. Cơ sở dữ liệu quan hệ ................................ ................................ ...... 12
1.4.2. Kho dữ liệu ................................ ................................ ...................... 12
1.4.3. Cơ sở dữ liệu không gian ................................ ................................ . 13
1.4.4. Cơ sở dữ liệu văn bản ................................ ................................ ...... 13
1.4.5. Dữ liệu Web................................ ................................ ..................... 13
1.5. Các phương pháp khai phá dữ liệu ................................ ......................... 13
1.5.1. Các thành phần của giải thuật khai phá dữ liệu ................................ 14
1.5.2. Phương pháp suy diễn / quy nạp ................................ ...................... 16
1.5.3. Phương pháp ứng dụng K-láng giềng ................................ ............... 16
1.5.4. Phương pháp sử dụng cây quyết định và luật[14] ............................. 17
1.5.5. Phương pháp phát hiện luật kết hợp ................................ ................. 18
1.6. Các nhiệm vụ trong khai phá dữ liệu ................................ ...................... 19
1.6.1. Phát hiện các luật tối ưu truy vấn ngữ nghĩa................................ ..... 20
1.6.2. Phát hiện sự phụ thuộc Cơ sở dữ liệu ................................ ............... 20
1.6.3. Phát hiện sự sai lệch................................ ................................ ......... 21
1.6.4. Phát hiện luật kết hợp................................ ................................ ....... 21
1.6.5. Mô hình hoá sự phụ thuộc ................................ ................................ 21
1.6.6. Mô hình hoá nhân quả................................ ................................ ...... 22
1.6.7. Phân cụm, nhóm ................................ ................................ .............. 22
1.6.8. Phân lớp ................................ ................................ ........................... 23
1.6.9. Hồi quy ................................ ................................ ............................ 23
1.6.10. Tổng hợp ................................ ................................ ....................... 23
1.7. Các thách thức và giải pháp cơ bản ................................ ........................ 24
1.7.1. Thách thức ................................ ................................ ....................... 24
1.7.2. Một số giải pháp ................................ ................................ .............. 25
1.8. Kết luận................................ ................................ ................................ .. 25
Chương 2 ................................ ................................ ................................ ........ 26
CƠ SỞ LÝ THUYẾT CỦA LUẬT KẾT HỢP, MỘT SỐ THUẬT TOÁN
PHÁT HIỆN LUẬT KẾT HỢP ................................ ................................ ..... 26
2.1. Lý thuyết về luật và luật kết hợp ................................ ............................ 26
2.1.1. Luật thừa ................................ ................................ .......................... 26
2.1.2. Luật kết hợp ................................ ................................ ..................... 27
2.1.3. Một số tính chất của luật kết hợp[6] ................................ ................. 30
2.1.4. Phát biểu bài toán khai phá luật kết hợp[8] ................................ ...... 31
2.1.5. Một số hướng tiếp cận trong khai phá luật kết hợp........................... 32
2.2. Các đặc trưng của luật kết hợp ................................ ............................... 34
2.2.1. Không gian tìm kiếm của luật ................................ .......................... 34
2.2.2. Độ hỗ trợ của luật ................................ ................................ ............ 36
2.3.Một số giải thuật cơ bản khai phá các tập phổ biến ................................ . 36
2.3.1.Kỹ thuật BFS ................................ ................................ .................... 37
2.3.2.Kỹ thuật DFS ................................ ................................ .................... 44
2.5. Thuật toán AIS ................................ ................................ ....................... 44
2.5.1. Bài toán đặt ra ................................ ................................ .................. 44
2.5.2. Thuật toán AIS ................................ ................................ ................. 45
2.6. Thuật toán SETM ................................ ................................ ................... 47
2.6.1. Bài toán đặt ra ................................ ................................ .................. 47
2.6.2. Thuật toán SETM ................................ ................................ ............ 47
2.7. Thuật toán CHARM[9] ................................ ................................ .......... 50
2.7.1. Tư tưởng thuật toán CHARM ................................ .......................... 50
2.7.1.1. Cơ sở lý thuyết ................................ ................................ .......... 50
2.7.2.2. Bài toán đặt ra................................ ................................ ............ 52
2.7.2. Thuật toán CHARM ................................ ................................ ......... 53
2.8. Kết luận................................ ................................ ................................ .. 56
Chương 3 ................................ ................................ ................................ ........ 57
ỨNG DỤNG KHAI PHÁ LUẬT KẾT HỢP TRONG ĐÀO TẠO .............. 57
3.1. Bài toán ................................ ................................ ................................ .. 57
3.2. Đặc tả dữ liệu ................................ ................................ ......................... 58
3.3. Chương trình thử nghiệm minh họa................................ ........................ 63
3.4. Kết luận ................................ ................................ .............................. 66
KẾT LUẬN................................ ................................ ................................ ...... 67
PHỤ LỤC ................................ ................................ ................................ ........ 68
TÀI LIỆU THAM KHẢO ................................ ................................ ................ 77