ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
NGUYỄN ANH TUẤN
RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH
KHÔNG ĐẦY ĐỦ CÓ DỮ LIỆU THAY ĐỔI
THEO TIẾP CẬN MÔ HÌNH TẬP THÔ DUNG SAI
LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH
THÁI NGUYÊN - 2022
ii
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH
KHÔNG ĐẦY ĐỦ CÓ DỮ LIỆU THAY ĐỔI
THEO TIẾP CẬN MÔ HÌNH TẬP THÔ DUNG SAI
Chuyên ngành: Khoa học máy tính
Mã số: 9 48 01 01
LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH
THÁI NGUYÊN - 2022
i
MỤC LỤC
MỤC LỤC ......................................................................................................... i
BẢNG CÁC KÝ HIỆU, TỪ VIẾT TẮT ....................................................... v
DANH MỤC CÁC BẢNG ............................................................................. vi
DANH MỤC HÌNH VẼ ............................................................................... viii
MỞ ĐẦU .......................................................................................................... 1
CHƯƠNG 1. TỔNG QUAN VỀ HỆ THÔNG TIN VÀ PHƯƠNG PHÁP
RÚT GỌN THUỘC TÍNH THEO TIẾP CẬN TẬP THÔ DUNG SAI .... 8
1.1. Mở đầu ....................................................................................................... 8
1.2. Các khái niệm cơ bản về hệ thông tin ....................................................... 8
1.2.1. Hệ thông tin đầy đủ và mô hình tập thô truyền thống .................... 8
1.2.2. Hệ thông tin không đầy đủ và mô hình tập thô dung sai .............. 12
1.3. Phương pháp rút gọn thuộc tính theo tiếp cận tập thô dung sai ............... 14
1.3.2. Phương pháp rút gọn thuộc tính theo tiếp cận lai ghép lọc - đóng gói .. 17
1.3.3. Bài toán phân lớp trong khai phá dữ liệu ..................................... 18
1.4. Các nghiên cứu liên quan và các vấn đề còn tồn tại ................................ 21
1.4.1. Các nghiên cứu liên quan đến rút gọn thuộc tính trong bảng quyết
định không đầy đủ ........................................................................................... 21
1.4.2. Các nghiên cứu liên quan đến rút gọn thuộc tính trong bảng quyết
định thay đổi .................................................................................................... 22
1.4.3. Các vấn đề còn tồn tại và mục tiêu nghiên cứu của luận án ........ 26
1.5. Bộ dữ liệu thực nghiệm ............................................................................. 27
1.6. Kết luận chương 1 ..................................................................................... 27
ii
CHƯƠNG 2. PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG
QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ KHI TẬP ĐỐI TƯỢNG THAY ĐỔI .. 28
2.1. Mở đầu ..................................................................................................... 28
2.2. Phương pháp gia tăng tìm tập rút gọn của bảng quyết định không đầy đủ
khi bổ sung, loại bỏ tập đối tượng ................................................................... 29
2.2.1. Thuật toán gia tăng lọc - đóng gói tìm tập rút gọn của bảng quyết
định trong trường hợp bổ sung tập đối tượng ................................................ 30
2.2.2. Thuật toán gia tăng lọc - đóng gói tìm tập rút gọn của bảng quyết
định trong trường hợp loại bỏ tập đối tượng .................................................. 37
2.3. Phương pháp gia tăng tìm tập rút gọn của bảng quyết định không đầy đủ khi
tập đối tượng thay đổi giá trị ............................................................................ 43
2.3.1. Công thức gia tăng tính khoảng cách khi tập đối tượng thay đổi giá trị 43
2.3.2. Thuật toán gia tăng lọc - đóng gói tìm tập rút gọn của bảng quyết
định không đầy đủ khi tập đối tượng thay đổi giá trị ...................................... 48
2.3.3. Thực nghiệm, đánh giá thuật toán FWIA_U_Obj......................... 52
2.3.4. Đánh giá thuật toán FWIA_U_Obj so với việc thực hiện gián tiếp
hai thuật toán IDS_IFW_DO và IDS_IFW_AO .............................................. 58
2.4. Kết luận chương 2 .................................................................................... 61
CHƯƠNG 3. PHƯƠNG PHÁP RÚT GỌN THUỘC TÍNH TRONG BẢNG
QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ KHI TẬP THUỘC TÍNH THAY ĐỔI 62
3.1. Mở đầu ..................................................................................................... 62
3.2. Phương pháp gia tăng tìm tập rút gọn của bảng quyết định không đầy đủ khi
bổ sung tập thuộc tính. ..................................................................................... 63
3.2.1. Công thức cập nhật khoảng cách khi bổ sung tập thuộc tính ....... 63
3.2.2. Thuật toán gia tăng lọc - đóng gói tìm tập rút gọn của bảng quyết
định không đầy đủ khi bổ sung tập thuộc tính. ............................................... 67
iii
3.2.3. Thực nghiệm, đánh giá thuật toán FWIA_AA ............................... 69
3.3. Phương pháp gia tăng tìm tập rút gọn của bảng quyết định không đầy đủ
khi loại bỏ tập thuộc tính. ................................................................................ 74
3.3.1. Công thức gia tăng cập nhật khoảng cách khi loại bỏ tập thuộc tính. 74
3.3.2. Thuật toán gia tăng lọc - đóng gói tìm tập rút gọn của bảng quyết
định không đầy đủ khi loại bỏ tập thuộc tính. ................................................. 76
3.3.3. Thực nghiệm, đánh giá thuật toán FWIA_DA .............................. 79
3.4. Phương pháp gia tăng tìm tập rút gọn của bảng quyết định không đầy đủ khi
tập thuộc tính thay đổi giá trị ............................................................................ 84
3.4.1. Công thức gia tăng tính khoảng cách khi tập thuộc tính thay đổi giá trị 84
3.4.2. Thuật toán gia tăng lọc - đóng gói tìm tập rút gọn của bảng quyết
định không đầy đủ khi tập thuộc tính thay đổi giá trị ..................................... 88
3.4.3. Thực nghiệm, đánh giá thuật toán FWIA_U_Attr ......................... 91
3.4.4. Thực nghiệm, đánh giá thuật toán FWIA_U_Attr so với việc thực
hiện gián tiếp hai thuật toán FWIA_DA và FWIA_AA ................................... 96
3.5. Kết luận chương 3 .................................................................................... 99
KẾT LUẬN .................................................................................................. 100
DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC CỦA LUẬN ÁN ....... 102
TÀI LIỆU THAM KHẢO .......................................................................... 103