B GIÁO DỤC VÀ ĐÀO TẠO
VIỆN HÀN LÂM KHOA HỌC
VÀ CÔNG NGHỆ VIT NAM
HC VIN KHOA HỌC VÀ CÔNG NGHỆ
……..….***………
NGUYỄN VĂN THIỆN
MT S PHƢƠNG PHÁP LAI GHÉP TRONG RÚT GN
THUỘC TÍNH THEO TIẾP CN TẬP THÔ MỜ
LUẬN ÁN TIẾN SĨ MÁY TÍNH VÀ CÔNG NGH THÔNG TIN
Hà Nội 2018
VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIT NAM
HC VIN KHOA HỌC VÀ CÔNG NGHỆ
……..….***………
NGUYỄN VĂN THIỆN
MT S PHƢƠNG PHÁP LAI GHÉP TRONG RÚT
GN THUỘC TÍNH THEO TIẾP CN TẬP THÔ MỜ
LUẬN ÁN TIẾN SĨ MÁY TÍNH VÀ CÔNG NGHỆ THÔNG TIN
Chuyên ngành : Hệ thống thông tin
Mã số: 9 48 01 04
Ngƣời hƣớng dn khoa hc:
1. PGS.TS. Nguyn Long Giang
2. TS. Nguyễn Nhƣ Sơn
Hà Nội 2018
i
MC LC
MC LC ............................................................................................................................................................... i
Danh mc các thut ng ..................................................................................................................................... iii
Bng các ký hiu, t viết tt ............................................................................................................................... iv
Danh sách bng ..................................................................................................................................................... v
Danh sách hình v ................................................................................................................................................ vi
M ĐU ............................................................................................................................................................... 1
Chương 1. TNG QUAN V RÚT GN THUC TÍNH THEO TIP CN TP THÔ M . 7
1.1. Mt s khái niệm trong thuyết tp t ...................................................................... 7
1.1.1. H thông tin và bảng quyết định ........................................................................ 7
1.1.2. Quan h tương đương ........................................................................................ 7
1.1.3. Các tập xp x và tập thô .................................................................................... 8
1.2. Mt s khái niệm trong thuyết tp t m ............................................................... 9
1.2.1. Quan h tương đương mờ .................................................................................. 9
1.2.2. Ma trận tương đương mờ ................................................................................. 10
1.2.3. Phân hoạch m ................................................................................................. 12
1.2.4. Các tập xp x m và tập thô mờ ..................................................................... 15
1.3. Tng quan v rút gn thuộc nh .................................................................................. 16
1.3.1. Rút gọn thuộc tính ............................................................................................ 16
1.3.2. Tiếp cận filter, wrapper trong rút gọn thuộc tính ............................................. 17
1.4. Các nghn cu liên quan đến rút gọn thuc nh theo tiếp cn tp tmờ ............ 19
1.4.1. Rút gọn thuộc tính trên bảng quyết định m theo tiếp cn tập thô mờ ............ 20
1.4.2. Rút gọn thuộc tính trực tiếp trên bảng quyết định theo tiếp cn tập thô mờ. .. 22
1.4.3. Phương pháp gia tăng rút gọn thuộc tính trong bảng quyết định thay đổi theo
tiếp cn tập thô mờ ....................................................................................................... 30
1.5. Tóm tắt các đóng p của lun án ............................................................................... 35
1.6. Kết lun .......................................................................................................................... 35
Cơng 2. T GN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH S DNG Đ
PH THUC M VÀ KHOẢNG CÁCH M .................................................................. 36
2.1. M đầu ........................................................................................................................... 36
ii
2.2. Rút gn thuc nh s dng đ ph thuc m ............................................................ 37
2.2.1. Rút gọn thuộc tính sử dụng độ ph thuc theo tiếp cn filter .......................... 37
2.2.2. Rút gọn thuộc tính sử dụng độ ph thuc m theo tiếp cn filter.................... 39
2.2.3. Rút gọn thuộc tính sử dụng độ ph thuc m theo tiếp cn filter-wrapper ..... 44
2.2.4. Thc nghim các thut toán ............................................................................... 46
2.3. Rút gn thuc tính s dng khong cách m ................................................................. 53
2.3.1. Xây dựng khoảng cách mờ gia hai tp m .................................................... 54
2.3.2. Xây dựng khoảng cách mờ giữa hai phân hoạch m ....................................... 57
2.3.3. Rút gọn thuộc tính sử dng khoảng cách mờ theo tiếp cn filter .................... 60
2.3.4. Rút gn thuộc tính sử dng khong cách mờ theo tiếp cn filter-wrapper ............. 64
2.3.5. Thc nghim c thuật toán ............................................................................... 67
2.4. Kết lun chương 2 ......................................................................................................... 71
Cơng 3. RÚT GN THUC NH TRONG BẢNG QUYT ĐỊNH THAY ĐỔI S
DNG KHONG CÁCH MỜ ................................................................................................................. 73
3.1. M đầu ........................................................................................................................... 73
3.2. Thuật tn gia tăng filter-wrapper m tập t gn xp x khi b sung tp đối ng
75
3.2.1. Công thức gia tăng tính khoảng cách mờ khi b sung tập đối tượng .............. 75
3.2.2. Thuật toán gia tăng filter-wrapper tìm tập rút gọn khi b sung tập đối tượng 78
3.2.3. Thc nghim thut toán ................................................................................... 82
3.3. Thuật tn filter-wrapper tìm tập rút gọn khi loi b tập đi ng ........................ 89
3.3.1. Công thức cp nht khoảng cách mờ khi loi b tập đối tượng ...................... 89
3.3.2. Thuật toán filter-wrapper tìm tập rút gọn khi loi b tập đối tượng ................ 92
3.4. Kết lun chương 3 ......................................................................................................... 96
KT LUN ......................................................................................................................................................... 97
Danh mc các công trình ca tác gi .............................................................................................................. 98
Tài liu tham kho .............................................................................................................................................. 99
iii
Danh mục các thuật ng
Thut ng tiếng Vit
Thut ng tiếng Anh
Tập thô
Rough Set
Tập thô mờ
Fuzzy Rough Set
H thông tin
Information System
Bng quyết định
Decision Tables
Bng quyết định m
Fuzzy Decision Tables
Quan h tương đương
Equivalence Relation
Quan h tương đương mờ
Fuzzy Equivalence Relation
Phân hoch m
Fuzzy Partition
Ma trận tương đương mờ
Fuzzy Equivalence Matrix
Lớp tương đương m
Fuzzy equivalence Classes
Xp x dưới m
Fuzzy Lower Approximation
Xp x trên mờ
Fuzzy Upper Approximation
Miền dương mờ
Fuzzy Positive Region
Độ ph thuc m ca thuc tính
Fuzzy Dependency Degree
Attribute Reduction
Tập rút gọn
Reduct
Phương pháp gia tăng
Incremental Methods
Khoảng cách mờ
Fuzzy Distance
Lc
Filter
Đóng gói
Wrapper