Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Nghiên cứu rút gọn tập thuộc tính trong hệ quyết định giá trị tập
Nội dung xem thử
Mô tả chi tiết
i
BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG
HỌC VIỆN KỸ THUẬT QUÂN SỰ
-------------------
PHÙNG THỊ THU HIỀN
NGHIÊN CỨU RÚT GỌN TẬP THUỘC TÍNH
TRONG HỆ QUYẾT ĐỊNH GIÁ TRỊ TẬP
Chuyên ngành : Cơ sở toán học cho tin học
Mã số : 62.46.01.10
LUẬN ÁN TIẾN SĨ TOÁN HỌC
HÀ NỘI – 2014
ii
LỜI CAM ĐOAN
Nghiên cứu sinh
Tôi xin cam đoan luận án này là công trình
nghiên cứu của riêng tôi. Các kết quả được viết
chung với các tác giả khác đều được sự đồng ý của
các đồng tác giả trước khi đưa vào luận án. Các kết
quả được trình bày trong luận án là mới, các số liệu
là trung thực và chưa từng được ai công bố trong
các công trình nào khác./.
iii
LỜI CẢM ƠN
Luận án được hoàn thành dưới sự hướng dẫn, chỉ bảo tận tình của PGS.TS
Nguyễn Bá Tường, người mà từ đó tác giả đã học được nhiều điều quí giá. Tác giả
cũng đã nhận được sự hướng dẫn và sự quan tâm giúp đỡ về nhiều mặt, cùng với
những đòi hỏi nghiêm khắc của PGS.TS Hà Quang Thụy. Tác giả xin bày tỏ lòng
biết ơn sâu sắc và chân thành tới những người Thầy đã giúp tác giả hoàn thành
những mục tiêu đặt ra của luận án.
Tác giả xin chân thành cảm ơn tới tập thể các thầy cô giáo, các nhà khoa học
thuộc: Học viện Kỹ thuật Quân sự, Trường Đại học Công nghệ (đặc biệt là Phòng
Thí nghiệm Công nghệ Tri thức - KTLab) - Đại học Quốc gia Hà Nội, Trường Đại
học Kinh tế Kỹ thuật Công nghiệp đã giúp đỡ về chuyên môn và tạo điều kiện thuận
lợi cho tác giả trong suốt thời gian học tập và nghiên cứu.
Tác giả cũng xin bày tỏ lòng biết ơn đến các bạn đồng nghiệp đã giúp đỡ và có
những trao đổi, chia sẻ những kinh nghiệm về chuyên môn, có nhiều ý kiến đóng
góp quý báu cho tác giả trong quá trình nghiên cứu.
Tác giả mãi biết ơn những người thân, đặc biệt là chồng và các con, đã luôn
chia sẻ mọi khó khăn và là chỗ dựa vững chắc về tinh thần và tạo mọi điều kiện cho
tác giả trong suốt thời gian hoàn thành luận án.
iv
MỤC LỤC
LỜI CẢM ƠN..................................................................................................................................................iii
DANH MỤC CÁC THUẬT NGỮ...........................................................................................................vii
BẢNG KÝ HIỆU, TỪVIẾT TẮT............................................................................................................viii
DANH MỤC BẢNG......................................................................................................................................x
DANH MỤC HÌNH VẼ................................................................................................................................xi
MỞĐẦU............................................................................................................................................................1
Chương 1. LÝ THUYẾT TẬP THÔ VÀ CÁC MỞRỘNG.................................................................9
1.1. Hệ thông tin và tập thô..............................................................................................................................9
1.1.1. Hệ thông tin............................................................................................................... 9
1.1.2. Quan hệ không phân biệt được.............................................................................. 10
1.1.3. Các tập xấp xỉ.......................................................................................................... 12
1.1.4. Các tính chất của xấp xỉ ......................................................................................... 15
1.1.5. Độ chính xác của xấp xỉ......................................................................................... 16
1.1.6. Bảng quyết định...................................................................................................... 16
1.1.7. Quan hệ dung sai .................................................................................................... 18
1.2. Hệ thông tin giá trịtập.............................................................................................................................19
1.2.1. Khái niệm................................................................................................................ 19
1.2.2. Quan hệ dung sai trong hệ thông tin giá trị tập..................................................... 20
1.2.3. Bảng quyết định giá trị tập..................................................................................... 21
1.2.4. Tập thô theo quan hệ dung sai............................................................................... 21
1.3. Kết luận......................................................................................................................................................22
Chương 2. RÚT GỌN THUỘC TÍNH THEO LÝ THUYẾT TẬP THÔ........................................24
2.1. Giới thiệu chung.......................................................................................................................................24
2.2. Rút gọn thuộc tính trong hệ thông tin...................................................................................................25
2.2.1. Tập rút gọn và tập lõi.............................................................................................. 25
2.2.2. Ma trận phân biệt và hàm phân biệt ...................................................................... 30
2.2.3. Phụ thuộc xấp xỉ ..................................................................................................... 33
2.2.3.1. Hàm thành viên thô ................................................................................. 34
v
2.2.3.2. Độ phụ thuộc xấp xỉ ................................................................................ 35
2.3. Rút gọn thuộc tính trong hệ thông tin giá trịtập.................................................................................35
2.3.1. Tập rút gọn trong hệ thông tin (bảng quyết định) giá trị tập................................ 36
2.3.2. Ma trận phân biệt.................................................................................................... 36
2.3.3. Rút gọn thuộc tính sử dụng đối tượng đại diện .................................................... 38
2.4. Kết luận......................................................................................................................................................40
Chương 3. RÚT GỌN THUỘC TÍNH TRONG HỆ QUYẾT ĐỊNH GIÁ TRỊTẬP SỬDỤNG
HÀM PHÂN BIỆT THEO BẢNG PHÂN BIỆT NGẪU NHIÊN....................................................42
3.1. Cơ sởlýthuyết..........................................................................................................................................42
3.1.1. Hàm phân biệt mở rộng.......................................................................................... 42
3.1.2. Bảng phân biệt ngẫu nhiên ................................................................................... 44
3.1.3. Bảng ngẫu nhiên dung sai..................................................................................... 49
3.1.4. Dàn giá trị thuộc tính.............................................................................................. 54
3.2. Thuật toán tìm tập rút gọn thuộc tính trong bảng quyết định giá trị tập................. 57
3.2.1. Thuật toán 3.1. tìm tập rút gọn thuộc tính GMDSDT.......................................... 57
3.2.2. Độ phức tạp thuật toán GMDSDT........................................................................ 58
3.2.3. Ví dụ minh họa ....................................................................................................... 58
3.3. Thực nghiệm thuật toán GMDSDT.....................................................................................................61
3.3.1. Cài đặt thuật toán.................................................................................................... 62
3.3.2. Chuẩn bị số liệu thực nghiệm................................................................................ 62
3.3.3. Thi hành thực nghiệm thuật toán........................................................................... 62
3.4. Thuật toán tìm tập xấp xỉtrong hệ thông tin giá trịtập......................................................................65
3.4.1. Đặt vấn đề ............................................................................................................... 65
3.4.2. Thuật toán tìm tập xấp xỉ dưới và xấp xỉ trên VASDT............................. .66
3.4.3. Độ phức tạp của thuật toán VASDT..................................................................... 66
3.4.4. Ví dụ minh họa thuật toán tìm tập xấp xỉ.............................................................. 67
3.5. Kết luận......................................................................................................................................................68
Chương 4. RÚT GỌN THUỘC TÍNH TRONG HỆ QUYẾT ĐỊNH GIÁ TRỊTẬP SỬDỤNG
HÀMPHÂN BIỆT THEO MA TRẬN PHÂN BIỆT MỞRỘNG...................................................70
vi
4.1. Chọn mẫu đại diện cho bài toán tìm tập rút gọn.................................................................................70
4.1.1. Đặt vấn đề ............................................................................................................... 70
4.1.2. Chọn tập đối tượng đại diện trong hệ thông tin giá trị tập .................................. 71
4.1.2.1. Cơ sở lý thuyết......................................................................................... 71
4.1.2.2. Thuật toán chọn đối tượng đại diện trên hệ thông tin giá trị tập............. 73
4.1.2.3. Ví dụ minh họa ........................................................................................ 74
4.1.3. Chọn tập đối tượng đại diện trong bảng quyết định giá trị tập ........................... 75
4.1.3.1. Cơ sở lý thuyết......................................................................................... 75
4.1.3.2. Thuật toán chọn đối tượng đại diện trên bảng quyết định giá trị tập ...... 78
4.1.3.3. Ví dụ minh họa ........................................................................................ 79
4.2. Rút gọn thuộc tính trong bảng quyết địnhgiá trịtập sửdụng hàm phân biệt mởrộng...............80
4.2.1. Cơ sở lý thuyết........................................................................................................ 80
4.2.2. Thuật toán tìm tập rút gọn trong bảng quyết định giá trị tập sử dụng hàm phân
biệt mở rộng................................................................................................................. 85
4.2.3. Đánh giá độ phức tạp của thuật toán RGDSDT................................................... 86
4.2.4. Ví dụ minh họa thuật toán RGDSDT.................................................................... 87
4.3. Rút gọn thuộc tính trong bảng quyết định giá trịtập khi bổ sung và loại bỏ thuộc tính.............89
4.3.1. Cơ sở lý thuyết........................................................................................................ 89
4.3.2. Một số thuật toán gia tăng tìm tập rút gọn thuộc tính RSDTAAS và RSDTDA..... 95
4.3.3. Đánh giá độ phức tạp của các thuật toán RSDTAAS và RSDTDAS................. 96
4.3.4. Ví dụ minh họa thuật toán RSDTAAS và RSDTDAS........................................ 97
4.4. Thực nghiệm thuật toán RGDSDT...................................................................................................100
4.4.1. Cài đặt thuật toán RGDSDT................................................................................ 100
4.4.2. Thi hành thực nghiệm thuật toán RGDSDT....................................................... 100
4.5. Kết luận chương 4.................................................................................................................................102
KẾT LUẬN VÀ KIẾN NGHỊ.................................................................................................................103
DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ.........................................................................105
TÀI LIỆU THAM KHẢO........................................................................................................................106
vii
DANH MỤC CÁC THUẬT NGỮ
Thuật ngữ tiếng Việt Thuật ngữ tiếng Anh
Bảng ngẫu nhiên dựa trên quan hệ dung sai Tolerance Based Contingency Table
Bảng phân biệt Contingency Table
Bảng quyết định Decision Table
Bảng quyết định giá trị tập Set valued Decision Information System
Hàm phân biệt Discernibility Function
Hệ thông tin Information System
Hệ thông tin đầy đủ Complete Information System
Hệ thông tin giá trị tập Set valued Information System
Hệ thông tin không nhất quán Inconsistent Information System
Ma trận không phân biệt được Indiscernibility Matrix
Quan hệ dung sai Tolerance Relation
Quan hệ không phân biệt được Indiscernibility Relation
Rút gọn thuộc tính Attribute Reduction
Tập lõi Core
Tập rút gọn Reduct
Tập thô Rough Set
Xấp xỉ dưới Lower Approximation
Xấp xỉ trên Upper Approximation
viii
BẢNG KÝ HIỆU, TỪ VIẾT TẮT
Ký hiệu, từ viết tắt Diễn giải
S U A V f ,,,
Hệ thông tin
T U C D V f , , ,
Bảng quyết định
IS U A V f ,,,
Hệ thông tin giá trị tập
DS U C d V f ( , , , )
Bảng quyết định giá trị tập
|X| Số phần tử (lực lượng) của tập X
u a
Giá trị của đối tượng
u
tại thuộc tính
a
IND B
Quan hệ
B
không phân biệt
B
u
Lớp tương đương chứa
u
của quan hệ
IND B U B/
Phân hoạch của
U
sinh bởi tập thuộc tính
B
COVER U
Tập tất cả các phủ của U
( ) B
u
Hàm quyết định suy rộng của đối tượng
u
đối với
B
BX B
xấp xỉ dưới của
X
trong hệ thông tin
BX B
xấp xỉ trên của
X
trong hệ thông tin
BN X B
B
miền biên của X trong hệ thông tin
POS D B
B
miền dương của
D
trong hệ thông tin
TB
Quan hệ dung sai của tập thuộc tính B
( ) T X B
Xấp xỉ trên của
X
trong hệ thông tin giá trị tập
( ) T X B
Xấp xỉ dưới của
X
trong hệ thông tin giá trị tập
( ) TB
BND X
Miền biên của X trong hệ thông tin giá trị tập
( ) TB
NEG X
Miền ngoài của X trong hệ thông tin giá trị tập
( ) TB
POS X
Miền dương của X trong hệ thông tin giá trị tập
CTB
Bảng ngẫu nhiên của tập thuộc tính B
TCTB
Bảng ngẫu nhiên dựa trên quan hệ dung sai
của tập thuộc tính B
MDT
Ma trận phân biệt
discern A( )
Hàm phân biệt
ix
P
IS
Hệ thông tin giá trị tập đại diện
DSP
Bảng quyết định giá trị tập đại diện
UP
Tập đối tượng đại diện của hệ thông tin giá trị tập
RP
Tập rút gọn dựa trên miền dương
R
Tập rút gọn dựa trên hàm quyết định suy rộng
RM
Tập rút gọn dựa trên ma trận phân biệt
RDF
Tập rút gọn dựa trên hàm phân biệt mở rộng
RCF
Tập rút gọn dựa trên hàm phân biệt
x
DANH MỤC BẢNG
Bảng 1.1. Một ví dụ vềhệ thông tin.............................................................................................................10
Bảng 1.2.Bảng quyết định vềbệnh cúm.....................................................................................................17
Bảng 1.3. Hệ thông tin giá trịtập.................................................................................................................19
Bảng 2.1.Bảng rút gọn thứnhất của hệ thống bệnh cúm
R1
.................................................................27
Bảng 2.2.Bảng rút gọn thứhai của hệ thống bệnh cúm
R2
..................................................................28
Bảng 2.3. Ma trận phân biệt được xây dựng từBảng 1.2.......................................................................31
Bảng 2.4. Ma trận phân biệt của bảng quyết định giá trịtập được xây dựng từBảng 1.3...............35
Bảng 3.1.Bảng phân biệt ngẫu nhiên biểu diễn giá trịtập thuộc tính..............................................49
Bảng 3.2.Minh họa giá trị của hàm phân biệt........................................................................................54
Bảng 3.3.Bảng quyết định giá trịtập gồm 4 cột thuộc tính
1 2 3 4 ( , , , ) a a a a ........................................59
Bảng 3.4. Kết quả thực hiện Thuật toán GMDSDT.................................................................................64
Bảng 3.5. Tập rút gọn của Thuật toán GMDSDT....................................................................................64
Bảng 3.6.Bảng quyết định giá trịtập gồm 4 cột thuộc tính điều kiện và cột
X d ................................67
Bảng 4.1. Bảng quyết định giá trịtập.........................................................................................................74
Bảng 4.2. Hệ thông tin giá trịtập đại diện từBảng 4.1...........................................................................75
Bảng 4.3. Bảng quyết định giá trịtập đại diện từBảng 4.1....................................................................79
Bảng 4.4. Bảng quyết định giá trịtập khi bổ sung
5 6 a a, .....................................................................90
Bảng 4.5. Kết quả thực hiện Thuật toán RGDSDT và Thuật toán GMDSDT..............................100
Bảng 4.6. Tập rút gọn của Thuật toán RGDSDTvà Thuật toán GMDSDT..................................101
xi
DANH MỤC HÌNH VẼ
Hình 3.1. Cấu trúc dàn của bảng quyết định giá trịtập..........................................................................56
Hình 3.2. Minh họa các thuật toán tìm tập rút gọn..................................................................................63
Hình 3.3.Minh họa thuật toán sửdụng hàm phân biệt...........................................................................63
1
MỞ ĐẦU
Tính cấp thiết của đề tài
Lý thuyết tập thô được Zdzislaw Pawlak đề xuất vào năm 1982 [36, 38] mở ra
một tiếp cận mới về tính không chắc chắn (uncertainty). Xuất phát điểm của lý
thuyết tập thô là khái niệm hệ thông tin (information system) được sử dụng để biểu
diễn dữ liệu có được về miền ứng dụng. Một hệ thông tin [35] là một bộ bốn
S U A V f ,,,
bao gồm một tập (vũ trụ) gồm hữu hạn các đối tượng
U ( ) U ,
một tập hữu hạn các thuộc tính
A
của các đối tượng (
A ,
một tập hữu hạn các
giá trị V (V ), và một hàm thông tin f : U A V. Tương ứng với mỗi thuộc
tính
a A
là tập giá trị tương ứng
( , ) , V f u a V u U a
. Trực quan hóa, một hệ
thông tin được trình bày dưới dạng một bảng hai chiều với các hàng là các đối
tượng u trong U (số lượng hàng là ||U||), các cột là các thuộc tính a trong A (số cột là
||A||) và phần tử tại hàng u, cột a là giá trị f(u,a). Khái niệm hệ thông tin làm nền
tảng của một loạt khái niệm như tập sơ cấp (elementary set hay atom), tập hợp
thành (composed set, còn được gọi là tập mô tả được), bảng quyết định (decision
table, còn được gọi là hệ quyết định: decision system), quan hệ không phân biệt
được (indiscernibility relation), không gian xấp xỉ (approximation space), tập xấp
xỉ (approximation set) v.v. cùng với một tập phong phú các tính chất liên quan [36,
37, 38, 39, 40, 41, 42] làm nền tảng cho các tiếp cận đại số và logic cũng như một
số tiếp cận toán học đối với tính không chắc chắn. Theo Zdzislaw Pawlak và
Andrzej Skowron [42], Andrzej Skowron và cộng sự [54], lý thuyết tập thô có ưu
điểm chính là không cần bất kỳ thông tin sơ bộ và bổ sung nào về dữ liệu như phân
bố xác suất trong thống kê, chuyển nhượng xác suất cơ bản trong lý thuyết chứng
minh, một mức hàm thành viên hoặc giá trị khả năng trong lý thuyết tập mờ. Chính
từ ưu điểm đó, lý thuyết tập thô giữ một vị trí nền tảng quan trọng trong trí tuệ nhân
tạo (artificial intelligence) và khoa học nhận thức (cognitive sciences), đặc biệt
trong một loạt lĩnh vực nghiên cứu như học máy (machine learning), các hệ thống
thông minh (intelligent systems), lập luận quy nạp (inductive reasoning), nhận dạng