BỘ THÔNG TIN VÀ TRUYỀN THÔNG
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
CAO CHÍNH NGHĨA
NGHIÊN CỨU CÁC PHƯƠNG PHÁP RÚT GỌN
THUỘC TÍNH VÀ SINH LUẬT QUYẾT ĐỊNH
THEO TIẾP CẬN TẬP THÔ MỜ
LUẬN ÁN TIẾN SĨ KỸ THUẬT
HÀ NỘI - 2017
BỘ THÔNG TIN VÀ TRUYỀN THÔNG
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
CAO CHÍNH NGHĨA
NGHIÊN CỨU CÁC PHƯƠNG PHÁP RÚT GỌN
THUỘC TÍNH VÀ SINH LUẬT QUYẾT ĐỊNH
THEO TIẾP CẬN TẬP THÔ MỜ
CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN
MÃ SỐ: 62.48.01.04
LUẬN ÁN TIẾN SĨ KỸ THUẬT
NGƯỜI HƯỚNG DẪN KHOA HỌC:
1. GS.TS. VŨ ĐỨC THI
2. TS. TÂN HẠNH
HÀ NỘI - 2017
LỜI CẢM ƠN
Luận án này được hoàn thành với sự nỗ lực không ngừng của tác giả và sự
giúp đỡ hết mình từ các thầy giáo hướng dẫn, bạn bè và người thân. Đầu tiên, tác
giả xin bày tỏ lời tri ân tới GS.TS Vũ Đức Thi và TS. Tân Hạnh, những thầy giáo đã
tận tình hướng dẫn tác giả hoàn thành luận án này.
Tác giả xin gửi lời cảm ơn tới các thầy, cô giáo và cán bộ của Học viện Công
nghệ Bưu chính Viễn thông - Bộ Thông tin và Truyền thông, là cơ sở đào tạo đã
luôn tạo điều kiện để NCS có thể hoàn thành luận án của mình.
Tác giả xin gửi lời cảm ơn sâu sắc đến TS. Nguyễn Long Giang - một người
thầy thầm lặng và các cán bộ Phòng Tin học quản lý, Viện Công nghệ Thông tin,
Viện Khoa học và Công nghệ Việt Nam đã nhiệt tình giúp đỡ và tạo ra môi trường
nghiên cứu tốt để tác giả hoàn thành công trình của mình; cảm ơn các thầy cô và các
đồng nghiệp ở các nơi mà tác giả tham gia viết bài đã có những góp ý chính xác để
tác giả có được những công bố như ngày hôm nay.
Tác giả xin gửi lời cảm ơn tới Đảng ủy, Ban Giám đốc Học viện Cảnh sát
Nhân dân, các đồng nghiệp Bộ môn Toán - Tin học nơi tác giả công tác đã ủng hộ
để luận án được hoàn thành đúng thời hạn.
Cuối cùng, tác giả xin gửi tới bạn bè, người thân lời cảm ơn chân thành nhất
vì đã đồng hành cùng tác giả trong suốt thời gian qua. Con xin cảm ơn Cha, Mẹ và
gia đình đã luôn là chỗ dựa vững chắc về tinh thần và vật chất, cũng là những người
luôn mong mỏi cho con thành công; cảm ơn vợ và các em đã gánh vác công việc gia
đình thay cho anh; xin lỗi các con vì phần nào đó đã chịu thiệt thòi trong thời gian
bố học tập nghiên cứu, chính các con là nguồn động lực lớn lao giúp bố hoàn thành
được công việc khó khăn này.
Hà Nội, tháng 11 năm 2016
Cao Chính Nghĩa
LỜI CAM ĐOAN
Các kết quả trình bày trong luận án là công trình nghiên cứu của tôi được
hoàn thành dưới sự hướng dẫn của GS.TS. Vũ Đức Thi, TS. Tân Hạnh và TS.
Nguyễn Long Giang. Những kết quả trình bày là mới và chưa từng được công bố ở
các công trình của người khác.
Tôi xin chịu trách nhiệm về những lời cam đoan của mình.
Cao Chính Nghĩa
i
MỤC LỤC
MỤC LỤC ....................................................................................................................... i
Danh mục các thuật ngữ................................................................................................ iii
Bảng các ký hiệu, từ viết tắt .......................................................................................... iv
Danh sách bảng ............................................................................................................ vii
Danh sách hình vẽ ....................................................................................................... viii
MỞ ĐẦU ....................................................................................................................... 1
CHƯƠNG 1. CÁC KIẾN THỨC CƠ SỞ ....................................................................... 9
1.1.
Một số khái niệm về tập thô ............................................................................. 9
1.1.1.
Hệ thông tin .............................................................................................. 9
1.1.2.
Các tập xấp xỉ ......................................................................................... 10
1.1.3.
Miền dương ............................................................................................ 11
1.1.4.
Bảng quyết định...................................................................................... 11
1.2.
Một số khái niệm về tập thô mờ xác định trên bảng quyết định miền giá trị thực
...................................................................................................................... 11
1.2.1.
Bảng quyết định miền giá trị thực ........................................................... 12
1.2.2.
Quan hệ tương đương mờ ....................................................................... 12
1.2.3.
Ma trận tương đương mờ ........................................................................ 13
1.2.4.
Phân hoạch mờ và lớp tương đương mờ .................................................. 14
1.2.5.
Các tập xấp xỉ mờ ................................................................................... 17
1.2.6.
Miền dương mờ ...................................................................................... 17
1.3.
Một số khái niệm về tập thô mờ xác định trên bảng quyết định mờ ................ 18
1.3.1.
Bảng quyết định mờ ................................................................................ 18
1.3.2.
Phân hoạch mờ và lớp tương đương mờ .................................................. 20
1.3.3.
Các tập xấp xỉ mờ ................................................................................... 21
1.3.4.
Miền dương mờ ...................................................................................... 21
1.4.
Rút gọn thuộc tính trong bảng quyết định....................................................... 23
1.4.1.
Tổng quan về rút gọn thuộc tính ............................................................. 23
1.4.2.
thô
Tổng quan về rút gọn thuộc tính trong bảng quyết định theo tiếp cận tập
............................................................................................................... 26
1.4.3.
Định hướng nghiên cứu của luận án ........................................................ 28
1.5.
Kết luận chương 1.......................................................................................... 29
ii
CHƯƠNG 2. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH MIỀN GIÁ
TRỊ THỰC SỬ DỤNG MIỀN DƯƠNG MỜ VÀ KHOẢNG CÁCH JACCARD MỜ .. 30
2.1.
Đặt vấn đề ..................................................................................................... 30
2.2.
Rút gọn thuộc tính sử dụng miền dương mờ ................................................... 31
2.2.1.
Phương pháp rút gọn thuộc tính sử dụng miền dương mờ ....................... 32
2.2.2.
Thử nghiệm và đánh giá kết quả ............................................................. 37
2.3.
Rút gọn thuộc tính sử dụng khoảng cách Jaccard mờ ..................................... 44
2.3.1.
Khoảng cách Jaccard mờ và các tính chất ............................................... 44
2.3.2.
Phương pháp rút gọn thuộc tính sử dụng khoảng cách Jaccard mờ .......... 52
2.3.3.
Thử nghiệm và đánh giá kết quả ............................................................. 56
2.4.
Kết luận chương 2.......................................................................................... 61
CHƯƠNG 3. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH MIỀN GIÁ
TRỊ THỰC SỬ DỤNG KHOẢNG CÁCH PHÂN HOẠCH MỜ .................................. 63
3.1.
Đặt vấn đề ..................................................................................................... 63
3.2.
Khoảng cách phân hoạch mờ và các tính chất ................................................ 64
3.3.
Phương pháp rút gọn thuộc tính sử dụng khoảng cách phân hoạch mờ ........... 70
3.4.
Thử nghiệm và đánh giá kết quả .................................................................... 77
3.5.
Kết luận chương 3.......................................................................................... 82
CHƯƠNG 4. RÚT GỌN THUỘC TÍNH VÀ SINH LUẬT TRÊN BẢNG QUYẾT
ĐỊNH MỜ ................................................................................................................... 84
4.1.
Đặt vấn đề ..................................................................................................... 84
4.2.
Phương pháp rút gọn thuộc tính của bảng quyết định mờ ............................... 87
4.3.
Phương pháp sinh luật quyết định của bảng quyết định mờ ............................ 91
4.3.1.
Luật quyết định mờ ................................................................................. 92
4.3.2.
Sinh luật quyết định từ bảng quyết định mờ ............................................ 93
4.3.3.
Thử nghiệm và đánh giá kết quả ........................................................... 105
4.4.
Kết luận chương 4........................................................................................ 110
KẾT LUẬN ............................................................................................................... 112
Danh mục các công trình của tác giả .......................................................................... 114
TÀI LIỆU THAM KHẢO .......................................................................................... 115
iii
Danh mục các thuật ngữ
Thuật ngữ tiếng Việt
Thuật ngữ tiếng Anh
Bảng quyết định
Decision Table
Bảng quyết định miền giá trị thực
Numerical Decision Table
Bảng quyết định mờ
Fuzzy Decision Table
Hệ thông tin
Information System
Khoảng cách mờ
Fuzzy Distance
Luật quyết định mờ
Fuzzy Decision Rule
Ma trận tương đương mờ
Fuzzy Equivalent Relational Matrix
Miền dương mờ
Fuzzy Positive Region
Quan hệ tương đương
Equivalent Relation
Quan hệ tương đương mờ
Fuzzy Equivalent Relation
Rút gọn thuộc tính
Attribute Reduction
Tập mờ
Fuzzy Set
Tập rút gọn
Reduct
Tập thô
Rough Set
Tập thô mờ
Fuzzy Rough Set
Xấp xỉ dưới
Lower Approximation
Xấp xỉ trên
Upper Approximation
Xấp xỉ dưới mờ
Fuzzy Lower Approximation
Xấp xỉ trên mờ
Fuzzy Upper Approximation
iv
Bảng các ký hiệu, từ viết tắt
Ký hiệu, từ viết tắt
U
IS
,A
Diễn giải
Hệ thông tin
D T U , C D
Bảng quyết định
DT U , C D
Bảng quyết định mờ
U
Số đối tượng
C
Số thuộc tính điều kiện trong bảng quyết định
A
Số thuộc tính
u a
Giá trị của đối tượng u tại thuộc tính a
P
Quan hệ P không phân biệt
IN D
u P
Lớp tương đương chứa u của quan hệ IND P
Lớp tương đường mờ chứa u của quan hệ tương đương mờ
ui R
RP
P
U/P
Phân hoạch của U sinh bởi tập thuộc tính P
P
Phân hoạch mờ theo tập thuộc tính P
PX
Pxấp xỉ dưới của X
PX
Pxấp xỉ trên của X
PN
P
X
POS
P
D
Pmiền biên của X
Pmiền dương của D
S I G P b
Độ quan trọng của thuộc tính b với tập thuộc tính P
(u )
A
Hàm thuộc của đối tượng u với tập mờ
A
H
P
E P
Entropy Shannon
Entropy Liang
v
DNF
d
NF
R P , RQ
C , C
D
Khoảng cách phân hoạch mờ giữa hai phân hoạch mờ R P
và R Q
Khoảng cách phân hoạch mờ giữa hai tập thuộc tính C và
CD
Khoảng cách Jaccard mờ giữa hai tập mờ và B
A
D FJ ( , B )
A
d FJ
C , C
D
Khoảng cách Jaccard mờ giữa hai tập thuộc tính C và
CD
F_RSAR1
F_RSAR2
FJ_DBAR
FJ_RBAR
NF_DBAR
Thuật toán rút gọn thuộc tính dựa trên miền dương mờ
F_RSAR1 (Fuzzy Rough Set Based Attribute Reduction 1)
Thuật toán rút gọn thuộc tính dựa trên miền dương mờ
F_RSAR2 (Fuzzy Rough Set Based Attribute Reduction 2)
Thuật toán rút gọn thuộc tính dựa trên khoảng cách Jaccard
mờ (Fuzzy Jaccard Distance Based Attribute Reduction)
Thuật toán sinh luật quyết định mờ dựa trên khoảng cách
Jaccard mờ (Fuzzy Jaccard Rule Based Attribute Reduction)
Thuật toán rút gọn thuộc tính dựa trên khoảng cách phân
hoạch mờ (New Fuzzy Distance Based Attribute Reduction)
Thuật toán rút gọn thuộc tính dựa trên miền dương mờ
FAR-VPFRS
(Forward Attribute Reduction Based On Variable Precision
Fuzzy-Rough Model)
Thuật toán rút gọn thuộc tính dựa trên miền dương mờ cải
FA-FPR
tiến (Forward Approximation - Fuzzy Positive Region
Reduction)
Thuật toán rút gọn thuộc tính dựa trên Entropy cải tiến
FA-FSCE
(Forward Approximation - Fuzzy Conditional Entropy To
Design A Heuristic Feature Selection Algorithm)
vi
Thuật toán rút gọn thuộc tính dựa trên Entropy tăng thêm
GRAF
(Attribute Selection Based On Information Gain Ratio In
Fuzzy Rough Set Theory)
MRBFA
MRBBA
Thuật toán sinh luật quyết định mờ dựa trên xấp xỉ tiến
(Mine Rules Based On The Forward Approximation)
Thuật toán sinh luật quyết định mờ dựa trên xấp xỉ lùi (Mine
Rules Based On The Backward Approximation)
vii
Danh sách bảng
Bảng 1.1. Bảng quyết định miền giá trị thực.................................................................... 12
Bảng 1.2. Bảng quyết định mờ chơi thể thao ................................................................... 18
Bảng 1.3. Bảng quyết định mờ của Ví dụ 1.3 .................................................................. 22
Bảng 2.1. Bảng quyết định miền giá trị thực của Ví dụ 2.1 .............................................. 34
Bảng 2.2. Bộ dữ liệu thử nghiệm ..................................................................................... 37
Bảng 2.3. Kết quả thực nghiệm của F_RSAR2, FAR-VPFRS ......................................... 40
Bảng 2.4. Tập rút gọn của F_RSAR2, FAR-VPFRS ........................................................ 42
Bảng 2.5. Độ chính xác phân lớp C4.5 của F_RSAR2, FAR-VPFRS .............................. 42
Bảng 2.6. Kết quả thực nghiệm của FJ_DBAR và GRAF ............................................... 57
Bảng 2.7. Tập rút gọn thu được bởi FJ_DBAR và GRAF ................................................ 59
Bảng 2.8. Độ chính xác phân lớp C4.5 của FJ_DBAR và GRAF ..................................... 59
Bảng 3.1. Mối liên hệ giữa khoảng cách phân hoạch mờ và entropy thông tin ................. 69
Bảng 3.2. Kết quả thực nghiệm của FA_FSCE, FA_FPR, NF_DBAR ............................. 78
Bảng 3.3. Tập rút gọn của FA_FSCE, FA_FPR, NF_DBAR .......................................... 80
Bảng 3.4. Độ chính xác phân lớp C4.5 của FA_FSCE, FA_FPR, NF_DBAR .................. 80
Bảng 4.1. Bảng quyết định mờ chơi thể thao biểu diễn lại Bảng 1.2 ................................ 89
Bảng 4.2. Bảng quyết định mờ chơi thể thao đã rút gọn thuộc tính .................................. 97
Bảng 4.3. Khoảng cách Jaccard mờ trực tiếp giữa các biến ngôn ngữ của Bảng 4.2 ......... 98
Bảng 4.4. Kết quả gán nhãn của Bảng 4.2 với (α=0.245; β=0.9) ................................... 100
Bảng 4.5. Kết quả gán nhãn của Bảng 4.2 với (α=0.245; β=0.8) ................................... 101
Bảng 4.6. Kết quả gán nhãn của Bảng 4.2 với (α=0.26) ................................................ 103
Bảng 4.7. Kết quả thực nghiệm của MRBFA, MRBBA và FJ_RBAR ........................... 108
viii
Danh sách hình vẽ
Hình 1.1. Quá trình lựa chọn thuộc tính .......................................................................... 25
Hình 1.2. Lựa chọn thuộc tính theo hướng tiếp cận lọc & đóng gói ................................. 26
Hình 1.3. Mô hình phương pháp heuristic rút gọn thuộc tính .......................................... 27
Hình 2.1. Thời gian thực hiện của F_RSAR2, FAR-VPFRS ............................................ 41
Hình 2.2. Độ chính xác phân lớp C4.5 của F_RSAR2, FAR-VPFRS .............................. 43
Hình 2.3. Thời gian thực hiện của FJ_DBAR và GRAF ................................................. 58
Hình 2.4. Độ chính xác phân lớp C4.5 của FJ_DBAR và GRAF ..................................... 61
Hình 3.1. Thời gian thực hiện của FA_FSCE, FA_FPR, NF_DBAR ............................... 79
Hình 3.2. Độ chính xác phân lớp C4.5 của FA_FSCE, FA_FPR và NF_DBAR ............. 81
Hình 4.1. Phân lớp dữ liệu theo các luật quyết định mờ ................................................... 86
Hình 4.2. Độ chính xác phân lớp của MRBFA, MRBBA và FJ_RBAR......................... 109
Hình 4.3. Độ phân tán dữ liệu của MRBFA, MRBBA và FJ_RBAR ............................. 109
1
MỞ ĐẦU
Rút gọn thuộc tính và sinh luật quyết định (luật phân lớp) là hai bài toán
quan trọng trong quá trình khám phá tri thức từ dữ liệu. Rút gọn thuộc tính thuộc
giai đoạn tiền xử lý dữ liệu còn sinh luật quyết định thuộc giai đoạn khai phá dữ
liệu. Rút gọn thuộc tính của bảng quyết định là quá trình lựa chọn tập con nhỏ nhất
của tập thuộc tính điều kiện, loại bỏ các thuộc tính dư thừa mà bảo toàn thông tin
phân lớp của bảng quyết định, gọi là tập rút gọn (reduct). Kết quả rút gọn thuộc tính
ảnh hưởng trực tiếp đến hiệu quả thực hiện các nhiệm vụ khai phá: Gia tăng tốc độ,
cải thiện chất lượng, tính dễ hiểu của các kết quả thu được. Sinh luật quyết định là
bước tiếp theo của rút gọn thuộc tính trong khai phá dữ liệu nhằm đánh giá chất
lượng phân lớp của dữ liệu thông qua độ hỗ trợ của tập luật quyết định. Độ chính
xác phân lớp được đánh giá thông qua tỷ lệ phân lớp đúng theo luật quyết định trên
tổng số lớp của tập dữ liệu.
Các kỹ thuật rút gọn thuộc tính được phân thành hai loại: Lựa chọn thuộc
tính (Attribute selection) và biến đổi thuộc tính (Attribute transformation) [44]. Lựa
chọn thuộc tính là chọn ra một tập con tốt nhất (theo một nghĩa nào đó) từ tập dữ
liệu ban đầu. Biến đổi thuộc tính là thực hiện việc biến đổi các thuộc tính của tập dữ
liệu ban đầu thành một tập dữ liệu với các thuộc tính mới có số lượng ít hơn sao cho
bảo tồn được thông tin nhiều nhất. Các công trình nghiên cứu về rút gọn thuộc tính
thường tập trung vào nghiên cứu các kỹ thuật lựa chọn thuộc tính. Lựa chọn thuộc
tính là quá trình lựa chọn một tập con gồm P thuộc tính từ tập gồm A thuộc tính
(PA) sao cho không gian thuộc tính được thu gọn lại một cách tối ưu theo một tiêu
chuẩn nhất định. Hiện nay có hai cách tiếp cận chính đối với bài toán lựa chọn
thuộc tính: Lọc (filter) và đóng gói (wrapper). Cách tiếp cận kiểu lọc thực hiện việc
lựa chọn thuộc tính độc lập với thuật toán khai phá sử dụng sau này. Các thuộc tính
được chọn chỉ dựa trên độ quan trọng của chúng trong việc mô tả dữ liệu. Ngược lại
với cách tiếp cận lọc, lựa chọn thuộc tính kiểu đóng gói tiến hành việc lựa chọn
bằng cách áp dụng ngay kỹ thuật khai phá cụ thể, độ chính xác của kết quả được lấy
làm tiêu chuẩn để lựa chọn các tập con thuộc tính [44].
2
Lý thuyết tập thô (Rough set) do Pawlak đề xuất [66] là công cụ hiệu quả
giải quyết bài toán rút gọn thuộc tính trong bảng quyết định và được cộng đồng
nghiên cứu về tập thô thực hiện lâu nay. Trong lý thuyết tập thô, dữ liệu được biểu
diễn thông qua một hệ thông tin IS U , A với U là tập các đối tượng và A là tập
các thuộc tính. Phương pháp tiếp cận chính của lý thuyết tập thô là dựa trên quan hệ
không phân biệt được để đưa ra các tập xấp xỉ biểu diễn tập đối tượng cần quan sát.
Bảng quyết định là một hệ thông tin IS với tập thuộc tính A được chia thành hai
tập con khác rỗng rời nhau C và D , lần lượt được gọi là tập thuộc tính điều kiện và
tập thuộc tính quyết định. Nói cách khác, DT U , C D với C D . Bảng
quyết định là mô hình thường gặp trong thực tế, khi mà giá trị dữ liệu tại các thuộc
tính điều kiện có thể cung cấp cho ta thông tin về giá trị của thuộc tính quyết định.
Các phương pháp rút gọn thuộc tính theo tiếp cận lý thuyết tập thô đều thực
hiện trên các bảng quyết định có miền giá trị rời rạc. Trong thực tế, miền giá trị
thuộc tính của các bảng quyết định thường chứa giá trị thực. Ví dụ, thuộc tính trọng
lượng cơ thể và huyết áp trong bảng dữ liệu bệnh nhân thường là các giá trị thực,
liên tục. Để thực hiện các phương pháp rút gọn thuộc tính theo tiếp cận tập thô,
miền giá trị thuộc tính thực, liên tục cần được rời rạc hóa. Tuy nhiên, các phương
pháp rời rạc hóa không bảo toàn sự khác nhau ban đầu giữa các đối tượng trong dữ
liệu gốc và do đó làm giảm độ chính xác phân lớp sau khi rút gọn thuộc tính. Để
giải quyết bài toán rút gọn thuộc tính trực tiếp trên các bảng quyết định có miền giá
trị thực, trong mấy năm gần đây các nhà nghiên cứu đề xuất hướng tiếp cận mới sử
dụng lý thuyết tập thô mờ.
Lý thuyết tập thô mờ (Fuzzy rough set) do Dubois, D., và Prade, H., [32],
[33] đề xuất là sự kết hợp của lý thuyết tập thô và lý thuyết tập mờ nhằm xấp xỉ các
tập mờ dựa trên một quan hệ tương đương mờ (fuzzy equivalent relation) được xác
định trên miền giá trị thuộc tính. Lý thuyết tập thô truyền thống dựa trên quan hệ
tương đương để xấp xỉ tập hợp, trong đó độ tương đương của hai đối tượng là 1 nếu
chúng tương đương, ngược lại là 0 nếu chúng không tương đương. Lý thuyết tập thô
3
mờ sử dụng quan hệ tương đương mờ thay thế quan hệ tương đương, độ tương
đương mờ của hai đối tượng là một giá trị nằm trong đoạn [0,1] cho thấy tính gần
nhau, hay khả năng phân biệt giữa hai đối tượng. Do đó, quan hệ tương đương mờ
bảo toàn sự khác nhau, hay độ tương đương, giữa các đối tượng và các phương pháp
rút gọn thuộc tính theo tiếp cận tập thô mờ có tiềm năng trong việc bảo toàn độ
chính xác phân lớp sau khi thực hiện các phương pháp rút gọn thuộc tính.
Chủ đề nghiên cứu về rút gọn thuộc tính theo tiếp cận tập thô mờ đã thu hút
sự quan tâm của các nhà nghiên cứu trong mấy năm gần đây. Các nghiên cứu liên
quan đến rút gọn thuộc tính theo tiếp cận tập thô mờ tập trung giải quyết hai bài toán
chính:
1) Bài toán thứ nhất là rút gọn thuộc tính trực tiếp trên các bảng quyết định
có miền giá trị thực (miền giá trị thuộc tính là các số thực) không qua
bước rời rạc hoá dữ liệu [15], [18], [24], [26], [36], [38], [39], [63], [79],
[80], [97]. Với bài toán này, đối tượng nghiên cứu là các bảng quyết định
miền giá trị thực. Một quan hệ tương đương mờ được định nghĩa trên
miền giá trị của thuộc tính. Quan hệ này cho phép xác định các ma trận
tương đương mờ. Dựa trên ma trận quan hệ tương đương mờ, các toán tử
của tập thô mờ được xây dựng như lớp tương đương mờ, tập xấp xỉ dưới
mờ và xấp xỉ trên mờ, miền dương mờ... Lớp tương đương mờ là đơn vị
cơ sở để xây dựng các độ đo hiệu quả giải quyết bài toán rút gọn thuộc
tính. Các kết quả nghiên cứu theo hướng tiếp cận này tập trung vào ba
nhóm chính: Nhóm các phương pháp sử dụng miền dương mờ [9], [38][40], [72], nhóm phương pháp sử dụng ma trận phân biệt mờ [15], [18],
[26], [80], nhóm phương pháp sử dụng entropy thông tin mờ [24], [38][40], [88], [89]. Thực nghiệm trên một số bộ số liệu lấy từ kho dữ liệu
UCI [99] cho thấy, các phương pháp rút gọn thuộc tính theo hướng tiếp
cận này có độ chính xác phân lớp cao hơn các phương pháp rút gọn thuộc
tính theo tiếp cận tập thô truyền thống. Tuy nhiên, chưa có nghiên cứu đầy
đủ để so sánh, đánh giá các phương pháp đã có về độ chính xác phân lớp
4
và thời gian thực hiện. Do đó, việc tìm kiếm các phương pháp hiệu quả
hơn các phương pháp đã công bố theo hướng tiếp cận này nhằm nâng cao
độ chính xác phân lớp và thời gian thực hiện là vấn đề nghiên cứu thứ
nhất của luận án.
2) Bài toán thứ hai là rút gọn thuộc tính và sinh luật trực tiếp trên bảng quyết
định mờ, là bảng quyết định mà giá trị thuộc tính là các tập mờ [9], [44],
[45], [47]-[51], [74], [88], [89]. Với bài toán này, đối tượng nghiên cứu là
các bảng quyết định mờ (là các bảng quyết định sau khi được mờ hóa
bằng các tập mờ). Các phân hoạch mờ được tính toán trên miền giá trị các
thuộc tính. Trên cơ sở đó, các lớp tương đương mờ được xác định. Các
lớp tương đương mờ là đơn vị tính toán cơ sở để tính toán các toán tử
trong lý thuyết tập thô mờ như các tập xấp xỉ mờ, miền dương mờ và là
đơn vị cơ sở để tính toán các độ đo sử dụng để giải quyết bài toán rút gọn
thuộc tính. Sinh luật là bài toán tiếp theo của rút gọn thuộc tính nhằm sinh
tập luật phân lớp dữ liệu. Các nghiên cứu liên quan đến việc giải quyết bài
toán sinh luật quyết định trên bảng quyết định mờ phải kể đến các công
trình [19], [21], [44], [51], [56], [74], [92]. Các công bố này sử dụng các
độ đo khác nhau nhằm trích lọc hệ luật mờ như sử dụng miền dương mờ
và một số độ đo khác. Việc tìm kiếm các độ đo nhằm nâng cao hiệu quả
của phương pháp trích lọc hệ luật mờ về thời gian thực hiện và độ chính
xác phân lớp là vấn đề nghiên cứu thứ hai của luận án.
Kỹ thuật sử dụng khoảng cách đóng vai trò quan trọng trong khai phá dữ
liệu. Trên thế giới, kỹ thuật này được nhiều người quan tâm nghiên cứu và áp dụng
vào việc giải quyết các bài toán như phân lớp, phân cụm, lựa chọn đặc trưng,…Ở
Việt Nam, luận án tiến sĩ của tác giả Nguyễn Long Giang là công trình nghiên cứu
khá đầy đủ về một số phương pháp rút gọn thuộc tính của bảng quyết định theo tiếp
cận lý thuyết tập thô, đặc biệt là phương pháp sử dụng khoảng cách [4]. Phương
pháp rút gọn thuộc tính sử dụng khoảng cách theo tiếp cận tập thô được chứng minh
là mang lại hiệu quả hơn so với các phương pháp khác [4]. Do đó, việc phát triển
5
các độ đo khoảng cách theo tiếp cận tập thô mờ (gọi là khoảng cách mờ) có tiềm
năng trong việc giải quyết bài toán rút gọn thuộc tính và sinh luật theo tiếp cận tập
thô mờ.
Từ các phân tích nêu trên, nghiên cứu sinh đặt ra mục tiêu nghiên cứu như
sau:
1) Với bài toán thứ nhất, nghiên cứu sinh tiếp tục nghiên cứu các phương
pháp hiệu quả rút gọn thuộc tính trực tiếp trên các bảng quyết định có
miền giá trị thực theo tiếp cận tập thô mờ. Tính hiệu quả dựa trên hai tiêu
chí đánh giá: Nâng cao độ chính xác phân lớp và cải thiện hiệu năng (thời
gian thực hiện) so với các phương pháp khác đã công bố. Việc tìm kiếm
các phương pháp dựa trên các độ đo khoảng cách đã được sử dụng trong
lý thuyết tập thô.
2) Với bài toán thứ hai, nghiên cứu sinh nghiên cứu các phương pháp hiệu
quả rút gọn thuộc tính và sinh luật quyết định trên bảng quyết định mờ.
Tính hiệu quả dựa trên hai tiêu chí đánh giá là độ chính xác phân lớp và
thời gian thực hiện.
Với mục tiêu đặt ra, luận án thu được các kết quả chính như sau:
1) Đề xuất các phương pháp rút gọn thuộc tính trực tiếp trên bảng quyết
định miền giá trị thực theo tiếp cận tập thô mờ, bao gồm:
-
Phương pháp rút gọn thuộc tính sử dụng miền dương mờ nhằm cải tiến
một số phương pháp dựa trên miền dương mờ đã công bố trước đó [38]
để tìm tập rút gọn không dư thừa thuộc tính và bảo toàn miền dương mờ.
Kết quả này công bố trong công trình [CCN1], [CCN2].
-
Phương pháp rút gọn thuộc tính sử dụng khoảng cách Jaccard mờ và
khoảng cách phân hoạch mờ. Khoảng cách Jaccard mờ được nghiên cứu
sinh xây dựng dựa trên khoảng cách Jaccard giữa hai tập hợp hữu hạn [4]
để đo khoảng cách giữa hai tập mờ. Khoảng cách phân hoạch mờ được
xây dựng dựa trên khoảng cách mờ giữa hai tập mờ do nghiên cứu sinh
6
đề xuất. Thực nghiệm trên một số bộ dữ liệu lấy từ kho dữ liệu UCI [99]
chứng minh hai phương pháp sử dụng khoảng cách mờ hiệu quả hơn các
phương pháp đã công bố trên cả hai tiêu chí: Độ chính xác phân lớp và
thời gian thực hiện trên một số bộ dữ liệu thực nghiệm. Các kết quả này
góp phần hình thành nhóm phương pháp rút gọn thuộc tính sử dụng
khoảng cách mờ theo tiếp cận tập thô mờ, được công bố trong các công
trình [CCN3], [CCN4].
2) Đề xuất phương pháp rút gọn thuộc tính và sinh luật trong bảng quyết
định mờ theo tiếp cận tập thô mờ. Phương pháp rút gọn thuộc tính sử
dụng miền dương mờ được công bố trong công trình [CCN2], phương
pháp sinh hệ luật mờ trên bảng quyết định mờ sử dụng khoảng cách
Jaccard mờ được công bố trong [CCN5]. Bằng lý thuyết và thực nghiệm
chứng minh phương pháp đề xuất tương đương với các phương pháp
khác trên tiêu chí độ chính xác phân lớp dữ liệu.
Đối tượng nghiên cứu của luận án là các bảng quyết định có miền giá trị
thực và bảng quyết định mờ.
Phạm vi nghiên cứu của luận án tập trung trọng tâm vào hai bài toán:
1) Bài toán thứ nhất là rút gọn thuộc tính của bảng quyết định miền giá trị
thực trong bước tiền xử lý số liệu.
2) Bài toán thứ hai là rút gọn thuộc tính và sinh luật quyết định của bảng
quyết định mờ.
Phương pháp nghiên cứu của luận án là nghiên cứu lý thuyết và nghiên
cứu thực nghiệm. Về nghiên cứu lý thuyết: Các định lý, mệnh đề trong luận án
được chứng minh chặt chẽ dựa vào các kiến thức cơ bản và các kết quả nghiên cứu
đã công bố. Về nghiên cứu thực nghiệm: Luận án thực hiện cài đặt các thuật toán,
chạy thử nghiệm thuật toán với các bộ số liệu lấy từ kho dữ liệu UCI [99], so sánh
và đánh giá kết quả thực nghiệm so với kết quả nghiên cứu lý thuyết và các công bố
khác để khẳng định được tính đúng đắn của kết quả nghiên cứu.
7
Bố cục của luận án gồm phần mở đầu và bốn chương nội dung, phần kết
luận và danh mục các tài liệu tham khảo. Cụ thể như sau:
Chương 1 trình bày một số khái niệm cơ bản gồm: Một số khái niệm về lý
thuyết tập thô; một số khái niệm cơ bản về tập thô mờ xác định trên bảng quyết định
miền giá trị thực; một số khái niệm về tập thô mờ xác định trên bảng quyết định mờ;
tổng quan về bài toán rút gọn thuộc tính. Các kiến thức cơ sở này được sử dụng trong
các chương sau, là các đóng góp chính của luận án.
Chương 2 trình bày các kết quả nghiên cứu về các phương pháp rút gọn thuộc
tính trong bảng quyết định miền giá trị thực sử dụng miền dương mờ và khoảng cách
Jaccard mờ, bao gồm:
1) Đề xuất cải tiến một thuật toán rút gọn thuộc tính của bảng quyết định dựa
trên miền dương mờ; đây là phương pháp tìm một tập rút gọn sử dụng
quan hệ tương đương mờ theo tiếp cận tập thô mờ có độ phức tạp tính toán
là hàm đa thức và bảo toàn miền dương mờ. Phương pháp đề xuất khắc
phục được một số hạn chế về thời gian tính toán hàm mũ như công bố của
nhóm tác giả trong [44] và bảo toàn miền dương mờ, tìm được một tập rút
gọn với số thuộc tính là nhỏ nhất, loại bỏ được các thuộc tính dư thừa như
trong công bố của nhóm tác giả trong [38].
2) Xây dựng thuật toán rút gọn thuộc tính của bảng quyết định miền giá trị
thực sử dụng khoảng cách Jaccard mờ. Khoảng cách Jaccard mờ được
nghiên cứu sinh xây dựng dựa trên khoảng cách Jaccard giữa hai tập hợp
hữu hạn [4] để đo khoảng cách giữa hai tập mờ. Kết quả so sánh đánh giá
phương pháp đề xuất với các phương pháp khác dựa trên hai tiêu chuẩn:
Độ chính xác phân lớp dữ liệu và thời gian thực hiện của phương pháp.
Chương 3 trình bày kết quả nghiên cứu về phương pháp rút gọn thuộc tính
trong bảng quyết định miền giá trị thực sử dụng độ đo khoảng cách phân hoạch mờ,
bao gồm:
8
1) Đề xuất độ đo khoảng cách phân hoạch mờ dựa trên khoảng cách mờ giữa
hai tập mờ.
2) Xây dựng thuật toán rút gọn thuộc tính của bảng quyết định miền giá trị
thực sử dụng khoảng cách phân hoạch mờ. Kết quả so sánh đánh giá
phương pháp đề xuất với các phương pháp khác dựa trên hai tiêu chuẩn:
Độ chính xác phân lớp dữ liệu và thời gian thực hiện của phương pháp.
Chương 4 trình bày phương pháp rút gọn thuộc tính và sinh luật quyết
định của bảng quyết định mờ dựa trên tập thô mờ. Phương pháp rút gọn thuộc tính
sử dụng miền dương mờ, phương pháp sinh luật sử dụng khoảng cách Jaccard mờ.
Dựa trên lý thuyết và các thực nghiệm, chứng minh rằng phương pháp đề xuất là
tương đương với các phương pháp khác dựa trên tiêu chí độ chính xác phân lớp dữ
liệu và thời gian thực hiện; độ phức tạp tính toán của các phương pháp sinh luật
quyết định trong trường hợp tổng quát là O( C D U ) với |C| là số biến ngôn ngữ của
tất cả các thuộc tính điều kiện, |D| là số biến ngôn ngữ của tất cả các thuộc tính
quyết định, |U| là số đối tượng của bảng dữ liệu.
Cuối cùng, phần kết luận nêu những đóng góp của luận án, hướng phát triển
tiếp theo và những vấn đề quan tâm của tác giả.
- Xem thêm -