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.v
Danh sách hình vẽ.vi
MỞ ĐẦU.1
Chương 1. TỔNG QUAN VỀ RÚT GỌN THUỘC TÍNH THEO TIẾP CẬN TẬP THÔ MỜ.7
1.1. Một số khái niệm trong lý thuyết tập thô.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 xấp xỉ và tập thô.8
1.2. Một số khái niệm trong lý thuyết tập thô 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 xấp xỉ mờ và tập thô mờ .15
1.3. Tổng quan về rút gọn thuộc tí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 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ờ .19
1.4.1. Rút gọn thuộc tính trên bảng quyết định mờ theo tiếp cận 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 cận 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 cận tập thô mờ.30
1.5. Tóm tắt các đóng góp của luận án.35
1.6. Kết luận.35
Chương 2. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH SỬ DỤNG ĐỘ
PHỤ THUỘC MỜ VÀ KHOẢNG CÁCH MỜ.36
2.1. Mở đầu .36ii
2.2. Rút gọn thuộc tính sử dụng độ phụ thuộc mờ.37
2.2.1. Rút gọn thuộc tính sử dụng độ phụ thuộc theo tiếp cận filter.37
2.2.2. Rút gọn thuộc tính sử dụng độ phụ thuộc mờ theo tiếp cận filter.39
2.2.3. Rút gọn thuộc tính sử dụng độ phụ thuộc mờ theo tiếp cận filter-wrapper .44
2.2.4. Thực nghiệm các thuật toán.46
2.3. Rút gọn thuộc tính sử dụng khoảng cách mờ.53
2.3.1. Xây dựng khoảng cách mờ giữa hai tập 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ử dụng khoảng cách mờ theo tiếp cận filter .60
2.3.4. Rút gọn thuộc tính sử dụng khoảng cách mờ theo tiếp cận filter-wrapper.64
2.3.5. Thực nghiệm các thuật toán .67
2.4. Kết luận chương 2.71
Chương 3. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH THAY ĐỔI SỬ
DỤNG KHOẢNG CÁCH MỜ .73
3.1. Mở đầu .73
3.2. Thuật toán gia tăng filter-wrapper tìm tập rút gọn xấp xỉ khi bổ sung tập đối tượ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. Thực nghiệm thuật toán .82
3.3. Thuật toán filter-wrapper tìm tập rút gọn khi loại bỏ tập đối tượng .89
3.3.1. Công thức cập nhật khoảng cách mờ khi loại 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 loại bỏ tập đối tượng.92
3.4. Kết luận chương 3.96
KẾT LUẬN.97
Danh mục các công trình của tác giả.98
Tài liệu tham khảo.99
117 trang |
Chia sẻ: trungkhoi17 | Lượt xem: 510 | Lượt tải: 2
Bạn đang xem trước 20 trang tài liệu Luận án Một số phương pháp lai ghép trong rút gọn thuộc tính theo tiếp cận tập thô mờ - Nguyễn Văn Thiện, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
CR u u u u , 2 4 5 5, , 1CR u u u u , 2 4 5 6, , 0CR u u u u .
Từ đó, hàm thuộc của các đối tượng đối với miền dương mờ
CR
POS d là:
1 3 6 2 4 51 1 1, , , ,sup , 1C CRCPOS d R u u u R u u uu u u , 2 1RCPOS d u ,
3 1RCPOS d
u , 4 1RCPOS d
u , 5 1RCPOS d
u , 6 1RCPOS d
u .
Từ đó: 1
CR
d
Áp dụng các bước của Thuật toán F_FRSAR ta có
1
0.167
cR
d ,
2
0
cR
d ,
3
0.167
cR
d ,
4
0.5
cR
d ,
5
0.467
cR
d ,
6
0.467
cR
d . Chọn thuộc tính 4c có độ quan trọng lớn nhất và 4P c . Thực
hiện vòng lặp While. Xét các thuộc tính 1c
ta có:
44
,4 4 1 4
1 1 0.5 0.5c c c cR R RSIG c d d . Tương tự 4 2 0.5cRSIG c ,
4
3 0cRSIG c , 4 5 0.5cRSIG c , 4 6 0.5cRSIG c . Không mất tính tổng quát, chọn
thuộc tính 1c có độ quan trọng lớn nhất và 1 4,P c c . Khi đó ta có
,1 4
1
c c CR R
d d , do đó thuật toán dừng và 1 4,P c c là một tập rút gọn của
bảng quyết định DS.
2.2.3. Rút gọn thuộc tính sử dụng độ phụ thuộc mờ theo tiếp cận filter-
wrapper
Xét bảng quyết định ,DS U C D với 1 2, ,..., mC a a a và R là quan hệ
tương đương mờ xác định trên miền giá trị thuộc tính. Đặt
CR
D . Theo thuật
toán F_FRSAR, giả sử các thuộc tính
1 2
, ,...i ia a được thêm vào tập rỗng theo giá trị
lớn nhất của độ quan trọng thuộc tính cho đến khi tồn tại 1,2,...t m sao cho
, ,...,
1 2
a a ai i it
R
D . Kết thúc thuật toán filter F_FRSAR, ta thu được tập rút gọn
1 2
, ,...,
ti i i
B a a a và độ chính xác phân lớp trên tập dữ liệu được tính trên B.
Mặt khác, theo định nghĩa miền dương mờ trong lý thuyết tập thô mờ và [76,
77, 78, 79] ta có
, ,...,
1 1 2 1
...
a a a a ai i i i it
R R R
D D D . Với ngưỡng
cho
trước, đặt
1
,...,
kk i i
B a a thỏa mãn
BkR
D và
1
B ak ik
R
D
. Khi đó, kB được
gọi là tập rút gọn xấp xỉ ngưỡng . Nếu kB và 1 ,...,k tk i iB a a được sử dụng để
xây dựng bộ phân lớp, công bố [91] cho thấy, độ chính xác phân lớp trên
1
,...,
k tk i i
B a a
chưa chắc đã tốt hơn trên kB . Giả sử kB có độ chính xác phân lớp
tốt hơn
1
,...,
k tk i i
B a a
. Khi đó, nếu chọn kB
là kết quả của thuật toán thì kB
có độ
chính xác phân lớp cao hơn, có số lượng thuộc tính ít hơn nên khả năng khái quát
hóa và hiệu năng thực hiện các thuật toán phân lớp sẽ cao hơn. Điều đó dẫn đến
hướng tiếp cận lai ghép tìm tập rút gọn xấp xỉ, là sự kết hợp giữa filter (lọc) và
wrapper (gói). Phương pháp filter tìm ra các tập rút gọn xấp xỉ, phương pháp
45
wrapper kiểm tra độ chính xác phân lớp của các tập rút gọn xấp xỉ để chọn tập rút
gọn có độ chính xác cao nhất. Với hướng tiếp cận này, độ chính xác phân lớp trên
tập rút gọn tìm được cao hơn so với các phương pháp lọc truyền thống. Tuy nhiên,
thời gian thực hiện sẽ lớn hơn vì phải thực hiện các bộ phân lớp.
Thuật toán filter-wrapper tìm tập rút gọn xấp xỉ sử dụng độ phụ thuộc mờ
được mô tả như sau:
Thuật toán FW_FRSAR (Filter-Wrapper Fuzzy Rough Set based Attribute
Reduction): Thuật toán filter-wrapper tìm tập rút gọn xấp xỉ sử dụng độ phụ thuộc
mờ.
Đầu vào: Bảng quyết định ,DS U C D với 1 2, ,..., nC a a a , quan hệ tương
đương mờ R xác định trên miền giá trị thuộc tính điều kiện.
Đầu ra: Tập rút gọn xấp xỉ xS có độ chính xác phân lớp tốt nhất.
// Khởi tạo
1. :B ; 0D
; :S ;
2. Tính độ phụ thuộc mờ
CR
D ;
// Giai đoạn filter, tìm các ứng viên cho tập rút gọn
// Thêm dần vào P các thuộc tính có độ quan trọng lớn nhất
3. While
B CR R
D D do
4. Begin
5. Với mỗi a C B tính
B a BB R R
SIG a D D
6. Chọn ma C B sao cho B m B
a C B
SIG a Max SIG a
;
7.
mB B a ; ;S S B
8. End;
// Giai đoạn Wrapper,tìm tập rút gọn có độ chính xác phân lớp cao nhất
9. Đặt t S //t là số phần tử của S, S chứa các chuỗi thuộc tính được
chọn tại mỗi bước lặp của vòng lặp While, nghĩa là
46
1 1 2 1 2
, , ,..., , ,...,
ti i i i i i
S a a a a a a ;
10. Đặt
1 1 2 1 21 2
, , ,..., , ,...,
ti i i t i i i
S a S a a S a a a
11. For j = 1 to t
12. Begin
13. Tính độ chính xác phân lớp trên
jS bằng một bộ phân lớp sử dụng
phương pháp 10-fold;
14. End
15. x joS S với joS có độ chính xác phân lớp lớn nhất.
Return xS ;
Tiếp theo, chúng tôi đánh giá độ phức tạp thời gian của thuật toán filter-
wrapper FW_FRSAR, gọi tắt là độ phức tạp. Giả sử D d và ký hiệu ,C U tương
ứng là số thuộc tính điều kiện và số đối tượng của DS. Theo mục 2.2.2, độ phức tạp
của thuật toán filter F_FRSAR là 2 2*O C U , do đó độ phức tạp của giai đoạn filter
(từ câu lệnh 3 đến 8) là 2 2*O C U . Độ phức tạp của giai đoạn wrapper (từ câu lệnh
số 9 đến số 15) phụ thuộc vào độ phức tạp của bộ phân lớp được sử dụng. Giả sử độ
phức tạp của bộ phân lớp là O T , khi đó độ phức tạp của giai đoạn wrapper là
*O C T . Vì vậy, độ phức tạp của thuật toán FW_FRSAR là 2 2* *O C U O C T
2.2.4. Thực nghiệm các thuật toán
2.2.4.1. Bộ dữ liệu thử nghiệm và môi trường thử nghiệm
Chúng tôi chọn 8 bộ dữ liệu mẫu từ lấy từ kho dữ liệu UCI [103] cho ở Bảng
2.2 để tiến hành thử nghiệm. Môi trường thử nghiệm là máy tính PC với cấu hình
Intel(R) Core(TM) i7-3770CPU @3.40 GHz, sử dụng hệ điều hành Windows 7, 32
bit. Công cụ lập trình thực hiện các thuật toán là ngôn ngữ C# và công cụ phân tích
dữ liệu R.
47
Bảng 2.2. Bộ dữ liệu thử nghiệm thuật toán F_FRSAR, FW_FRSAR
STT Bộ dữ liệu Mô tả
Số đối
tượng
Số thuộc tính điều kiện
Số lớp
quyết
định
Tất
cả
Thuộc
tính định
danh
(nominal)
Thuộc
tính
thực
(Real-
valued)
1 Ecoli Protein Localization
Sites
336 7 0 7 8
2 Ionosphere Johns Hopkins
University
Ionosphere database
351 34 0 34 2
3 WDBC Wisconsin
diagnostic breast
cancer
569 30 0 30 2
4 Wpbc Wisconsin
Prognostic Breast
Cancer
198 33 0 33 2
5 Wine Wine recognition
data
178 13 0 13 3
6 Glass Glass Identification
Database
214 9 0 9 7
7 Magic04 MAGIC gamma
telescope data 2004
19020 10 0 10 2
8 Page-
blocks
Blocks
Classification
5473 10 0 10 5
2.2.4.2. Đánh giá độ chính xác phân lớp của thuật toán F_FRSAR với các thuật
toán khác theo tiếp cận tập thô mờ và thuật toán RSAR theo tiếp cận tập thô truyền
thống
1) Đánh giá độ chính xác phân lớp của thuật toán F_FRSAR theo tiếp cận tập thô
mờ với thuật toán RSAR theo tiếp cận tập thô truyền thống
Trước hết, chúng tôi tiến hành thử nghiệm nhằm đánh giá độ chính xác phân
lớp của thuật toán F_FRSAR với thuật toán RSAR theo tiếp cận tập thô truyền
thống. Với thuật toán filter theo tiếp cận tập thô mờ F_FRSAR, chúng tôi dùng
48
quan hệ tương đương mờ R trên miền giá trị của thuộc tính
kc C như sau [54, 68,
76]
1 4* , 0.25
( , ) max( ) min( ) max( ) min( )
0,
k
k i k j k i k j
c i j k k k k
c u c u c u c u
R u u c c c c
otherwise
Với max , mink kc c tương ứng là giá trị lớn nhất và giá trị nhỏ nhất của
miền giá trị thuộc tính kc . Trên thuộc tính quyết định d chúng tôi sử dụng quan
hệ tương đương dR . Phân hoạch / d dU R x x U với
( , ) 1ddx y U R x y là một lớp tương đương. Khi đó, lớp tương đương dx
được xem là lớp đương đương mờ, ký hiệu là
d
x , với hàm thuộc 1
d
x
y nếu
d
y x và 0
d
x
y nếu
d
y x .
Để tiến hành thử nghiệm, chúng tôi thực hiện các công việc sau:
- Cài đặt, thực hiện thuật toán rời rạc hóa dữ liệu equal-width [64] và thuật
toán RSAR để tìm tập rút gọn theo tiếp cận tập thô.
- Cài đặt, thực hiện thuật toán F_FRSAR để tìm tập rút gọn trực tiếp từ bảng
quyết định ban đầu theo tiếp cận tập thô mờ.
- Chúng tôi sử dụng bộ phân lớp SVM và C4.5 trong công cụ R để tính độ
chính xác phân lớp trên tập rút gọn thu được bởi hai thuật toán . Chúng tôi sử dụng
phương pháp kiểm tra chéo 10-fold, nghĩa là bộ dữ liệu được chia thành 10 phần
xấp xỉ bằng nhau, lấy ngẫu nhiên 1 phần làm bộ dữ liệu kiểm tra, 9 phần còn lại làm
dữ liệu huấn luyện. Quá trình được lặp lại 10 lần.
Bảng 2.3 là kết quả thử nghiệm trên 8 bộ số liệu được chọn với U là số đối
tượng, C là số thuộc tính điều kiện, R là số thuộc tính của tập rút gọn.
49
Bảng 2.3. Độ chính xác phân lớp của F_FRSAR và RSAR
ST
T
Bộ số
liệu
U C
Rút gọn thuộc tính theo tiếp
cận tập thô (RSAR)
Rút gọn thuộc tính theo
tiếp cận tập thô mờ
(F_FRSAR)
R Độ chính
xác phân
lớp SVM
Độ chính
xác phân
lớp C4.5
R Độ chính
xác phân
lớp SVM
Độ chính
xác phân
lớp C4.5
1 Ecoli 336 7 5 0.851 0.819 7 0.865 0.855
2 Ionospher
e
351 34 10 0.814 0.802 15 0.937 0.915
3 Wdbc 569 30 8 0.795 0.784 19 0.980 0.975
4 Wpbc 198 33 7 0.718 0.704 19 0.825 0.818
5 Wine 178 13 4 0.814 0.802 10 0.955 0.920
6 Glass 214 9 5 0.815 0.795 7 0.891 0.882
7 Magic04 1902
0
10 4 0.745 0.715 6 0.782 0.765
8 Page-
blocks
5473 10 5 0.758 0.725 7 0.865 0.855
Hình 2.1. Độ chính xác phân lớp của F_FRSAR và RSAR
50
Từ Bảng 2.3 và Hình 2.1 ta thấy, trên tất cả các tập dữ liệu, tập rút gọn của
F_FRSAR nhiều thuộc tính hơn RSAR. Độ chính xác phân lớp trên tập rút gọn của
F_FRSAR cao hơn độ chính xác phân lớp trên tập rút gọn của RSAR.
2) Đánh giá độ chính xác phân lớp của thuật toán F_FRSAR với các thuật toán
khác theo tiếp cận tập thô mờ
Tiếp theo, chúng tôi tiến hành thử nghiệm để đánh giá thuật toán filter đề xuất
F_FRSAR với thuật toán filter tìm tập rút gọn theo tiếp cận tập thô mờ sử dụng
lượng thông tin tăng thêm (information gain) mờ dựa trên entropy Shannon mờ, gọi
là thuật toán GAIN_RATIO_AS_FRS trong công trình [45]. Sở dĩ chọn thuật toán
GAIN_RATIO_AS_FRS để so sánh với thuật toán đề xuất vì thuật toán
GAIN_RATIO_AS_FRS được chứng minh là hiệu quả hơn các thuật toán sử dụng
ma trận phân biệt mờ (công trình số 1, phần danh mục các công trình của tác giả).
Để tiến hành thử nghiệm, chúng tôi cài đặt thuật toán
GAIN_RATIO_AS_FRS trong [45] sử dụng cùng quan hệ tương đương mờ với
thuật toán F_FRSAR. Chúng tôi cũng sử dụng phương pháp 10-fold như mô tả ở
trên (mục 2.2.4.2) để đánh giá độ chính xác phân lớp với bộ phân lớp SVM và C4.5
trong công cụ R, vì bộ phân lớp SVM và C4.5 cũng được chọn trong thử nghiệm
của công bố số [45]. Kết quả thực hiện hai thuật toán được mô tả ở Bảng 2.4 như
sau:
Bảng 2.4. Độ chính xác phân lớp của GAIN_RATIO_AS_FRS và F_FRSAR
STT
Bộ số
liệu
U C
Thuật toán
GAIN_RATIO_AS_FRS
[45]
Thuật toán F_FRSAR
R Độ chính
xác phân
lớp SVM
Độ chính
xác phân
lớp C4.5
R Độ chính
xác phân
lớp SVM
Độ chính
xác phân
lớp C4.5
1 Ecoli 336 7 6 0.814 0.802 7 0.865 0.855
2 Ionos
phere
351 34 13 0.916 0.904 15 0.937 0.915
3 Wdbc 569 30 17 0.925 0.917 19 0.980 0.975
4 Wpbc 198 33 17 0.815 0.804 19 0.825 0.818
5 Wine 178 13 9 0.910 0.902 10 0.955 0.920
51
6 Glass 214 9 7 0.891 0.882 7 0.891 0.882
7
Magic
04
1902
0
10 6 0.782 0.765 6 0.782 0.765
8
Page-
blocks
5473 10 6 0.852 0.848 7 0.865 0.855
Hình 2.2. Độ chính xác phân lớp của GAIN_RATIO_AS_FRS và F_FRSAR
Từ Bảng 2.4 và Hình 2.2 ta thấy, trên cùng một quan hệ tương đương mờ được
sử dụng, độ chính xác phân lớp sau khi thực hiện thuật toán đề xuất F_FRSAR cao
hơn độ chính xác phân lớp sau khi thực hiện thuật toán GAIN_RATIO_AS_FRS
trong [45]. Tập rút gọn của thuật toán đề xuất F_FRSAR bảo toàn miền dương mờ
và nhiều thuộc tính hơn so với thuật toán GAIN_RATIO_AS_FRS trong [45].
2.2.4.3. Đánh giá độ chính xác phân lớp của thuật toán filter-wrapper FW_FRSAR
với thuật toán filter F_FRSAR và các thuật toán filter khác theo tiếp cận tập thô mờ
Trong mục này, chúng tôi tiến hành thử nghiệm đánh giá thuật toán filter-
wrapper FW_FRSAR với thuật toán filter F_FRSAR và thuật toán filter
GAIN_RATIO_AS_FRS trong [45]. Việc đánh giá dựa trên hai tiêu chuẩn: độ
chính xác phân lớp và thời gian thực hiện của các thuật toán. Cả 3 thuật toán đề sử
dụng quan hệ tương đương mờ ở mục 2.2.4.2. Chúng tôi cũng sử dụng phương pháp
10-fold như mô tả ở mục 2.2.4.2 để đánh giá độ chính xác phân lớp với bộ phân lớp
C4.5 trong công cụ R.
52
1) So sánh độ chính xác phân lớp của FW_FRSAR, F_FRSAR và
GAIN_RATIO_AS_FRS
Kết quả so sánh độ chính xác phân lớp của 3 thuật toán được mô tả ở Bảng 2.5.
Trong đó, U là số đối tượng, C là số thuộc tính điều kiện, R là số thuộc tính của
tập rút gọn.
Bảng 2.5. Độ chính xác phân lớp FW_FRSAR, F_FRSAR, GAIN_RATIO_AS_FRS
STT
Tập dữ
liệu
Tập dữ liệu
ban đầu
Thuật toán
FW_FRSAR
Thuật toán
F_FRSAR
Thuật toán
GAIN_RATIO
_AS_FRS [45]
U C R Độ chính
xác phân
lớp C4.5
R Độ chính
xác phân
lớp C4.5
R Độ chính
xác phân
lớp C4.5
1 Ecoli 336 7 5 0.901 7 0.855 6 0.802
2 Ionosphere 351 34 8 0.946 15 0.915 13 0.904
3 Wdbc 569 30 6 0.975 19 0.975 17 0.917
4 Wpbc 198 33 12 0.867 19 0.818 17 0.804
5 Wine 178 13 5 0.920 10 0.920 9 0.902
6 Glass 214 9 4 0.924 7 0.882 7 0.882
7 Magic04 19020 10 4 0.886 6 0.765 6 0.765
8
Page-
blocks
5473 10 5 0.906 7 0.855 6 0.848
Kết quả ở Bảng 2.5 cho thấy, số thuộc tính tập rút gọn của thuật toán filter-
wrapper FW_FRSAR nhỏ hơn nhiều, đặc biệt là đối với các bộ dữ liệu Wdbc,
Ionosphere. Hơn nữa, độ chính xác của FW_FRSAR cao hơn F_ FRSAR và
GAIN_RATIO_AS_FR, độ chính xác FW_FRSAR bằng F_FRSAR trên 2 bộ dữ
liệu Wdbc và Wine. Nguyên nhân là giai đoạn wrapper, thuật toán FW_FRSAR tính
độ chính xác phân lớp trên tất cả các ứng cử viên tập rút gọn sinh bởi F_FRSAR và
tìm ứng cử viên có độ chính xác phân lớp tốt nhất.
Như vậy, thuật toán đề xuất filter-wrapper FW_FRSAR đáp ứng mục tiêu đặt
ra là giảm thiểu số thuộc tính tập rút gọn, từ đó giảm thiểu độ phức tạp của mô hình
mà vẫn cố gắng bảo toàn độ chính xác phân lớp (độ chính xác phân lớp còn cao hơn
các phương pháp filter).
53
2) So sánh thời gian thực hiện của FW_FRSAR, F_FRSAR và
GAIN_RATIO_AS_FRS
Kết quả so sánh thời gian thực hiện của 3 thuật toán được mô tả ở Bảng 2.6.
Thời gian tính bằng giây (s), trong đó thời gian thực hiện thuật toán filter-wrapper
FW_FRSAR được tách thành hai giai đoạn: thời gian thực hiện thủ tục filter và
wrapper.
Bảng 2.6. Thời gian thực hiện FW_FRSAR, F_FRSAR, GAIN_RATIO_AS_FRS
STT Bộ dữ liệu U C
Thuật toán FW_FRSAR Thuật toán
F_FRSAR
Thuật toán
GAIN_RATIO
_AS_FRS
[45]
Thủ tục
Filer
Thủ tục
Wrapper
Tổng
cộng
1 Ecoli 336 7 2.38 1.24 3.62 2.86 2.95
2 Ionosphere 351 34 12.64 6.92 19.56 14.87 15.04
3 Wdbc 569 30 22.15 8.74 30.89 24.12 26.08
4 Wpbc 198 33 8.56 6.28 14.84 9.12 9.88
5 Wine 178 13 0.58 1.22 1.80 0.62 0.74
6 Glass 214 9 0.82 0.66 1.48 0.88 1.02
7 Magic04 19020 10 894.26 124.49 1018.75 914.86 948.16
8
Page-
blocks
5473 10 98.64 22.16 120.80 112.76 126.28
Kết quả ở Bảng 2.6 cho thấy, thời gian thực hiện thuật toán FW_FRSAR cao
hơn hai thuật toán filter F_FRSAR và GAIN_RATIO_AS_FRS vì phải thực hiện
các bộ phân lớp trong giai đoạn wrapper. Chú ý rằng thời gian thực hiện thủ tục
filter trong thuật toán FW_FRSAR nhỏ hơn F_FRSAR và GAIN_RATIO_AS_FRS
vì thủ tục filter không phải kiểm tra lại tập rút gọn tìm được. Với 2 thuật toán filter,
thời gian thực hiện thuật toán đề xuất F_FRSAR nhỏ hơn một chút so với thuật toán
GAIN_RATIO_AS_FRS vì không phải tính toán các công thức entropy Shannon.
2.3. Rút gọn thuộc tính sử dụng khoảng cách mờ
Trong mấy năm gần đây, nhóm nghiên cứu của Nguyễn Long Giang và cộng
sự đã sử dụng các độ đo khoảng cách để giải quyết bài toán rút gọn thuộc tính trong
bảng quyết định theo tiếp cận tập thô truyền thống [9, 24, 57, 65] và bảng quyết
54
định không đầy đủ theo tiếp cận tập thô dung sai [9, 10, 12, 25, 58]. Theo tiếp cận
tập thô mờ, nhóm nghiên cứu đã mở rộng các độ đo khoảng cách đã đề xuất thành
các độ đo khoảng cách mờ và đã có một số kết quả trong việc sử dụng độ đo khoảng
cách mờ để giải quyết bài toán rút gọn thuộc tính trên bảng quyết định có miền giá
trị số. Trong công trình [8], nhóm tác giả xây dựng độ đo khoảng cách Jaccard mờ
giữa hai tập thuộc tính dựa trên khoảng cách Jaccard giữa hai tập hợp hữu hạn và
chứng minh một số tính chất của nó. Trong công trình [3], các tác giả đã sử dụng
khoảng cách Jaccard mờ trong [8] để giải quyết bài toán rút gọn thuộc tính trực tiếp
trên bảng quyết định gốc có miền giá trị số. Trong công trình [18], các tác giả xây
dựng độ đo khoảng cách phân hoạch mờ và sử dụng khoảng cách phân hoạch mờ
giải quyết bài toán rút gọn thuộc tính trên bảng quyết định có miền giá trị số.
Tiếp tục hướng nghiên cứu này, với mục tiêu tìm kiếm các độ đo khoảng cách
hiệu quả (có công thức tính toán đơn giản) giải quyết bài toán rút gọn thuộc tính,
giảm thiểu thời gian thực hiện, trong phần này chúng tôi xây dựng độ đo khoảng
cách mờ mới (sau đây gọi là khoảng cách mờ) dựa trên độ đo khoảng cách phân
hoạch trong công trình [48]. Sử dụng khoảng cách mờ được xây dựng, chúng tôi đề
xuất phương pháp filter-wrapper rút gọn thuộc tính trong bảng quyết định nhằm
nâng cao độ chính xác phân lớp và giảm thiểu số lượng thuộc tính tập rút gọn.
2.3.1. Xây dựng khoảng cách mờ giữa hai tập mờ
Cho bảng quyết định ,DS U C D với 1 2, ,..., nU x x x , ,P Q C và
i iPK P x x U , i iQK Q x x U là hai phân hoạch trên P và Q. Trong
công trình [48], Liang và các cộng sự đã chứng minh
1
1
,
U
i iP Q
i
x x
D K P K Q
U U
với i i i i i iP Q P Q P Qx x x x x x là khoảng cách phân hoạch giữa
K P và K Q . Dựa trên khoảng cách phân hoạch, trong mục này chúng tôi xây
dựng một độ đo khoảng cách giữa hai tập mờ, gọi là khoảng cách mờ.
55
Định nghĩa 2.3. [63] Cho U là tập hữu hạn, khác rỗng các đối tượng. Một độ đo
khoảng cách trên U là một ánh xạ : 0,d U U thỏa mãn các điều kiện sau với
mọi , ,x y z U
1P , 0d x y , , 0d x y khi và chỉ khi x y .
2P , ,d x y d y x .
3P , , ,d x y d y z d x z .
Điều kiện 3P được gọi là tiên đề bất đẳng thức tam giác.
Bổ đề 2.1. Cho ba số thực a, b, m với a b . Khi đó ta có min , min ,a b a m b m
Mệnh đề 2.1. Cho ba tập mờ , ,A B C trên cùng tập đối tượng U. Khi đó ta có các mệnh
đề sau:
1) Nếu A B thì B B C A A C .
2) Nếu A B thì C C A C C B .
3) A A B C C A C C B
Chứng minh.
1) Vì A B , với mọi ix U ta có i iB Ax x . Áp dụng Bổ đề 2.1 ta có:
min , min ,i i i i i iB B C CA Ax x x x x x
1 1 1 1
min , min ,
U U U U
i i i i i iB B C CA A
i i i i
x x x x x x
B A B C A C B B C A A C
2) Vì A B , với mọi ix U ta có i iB Ax x
min , min ,i i i iB C A Cx x x x
min , min ,i i i i i iC C C B CAx x x x x x
1 1 1 1
min , min ,
U U U U
i i i i i iC C C B CA
i i i i
x x x x x x
C C A C C B .
56
3) Từ A C A , áp dụng tính chất 1) ta có A A B A C A C B (1)
Mặt khác, từ A B B , áp dụng tính chất 2) ta có C C A B C C B (2)
Từ (1) và (2) ta có: A A B C C A A C A C B C C A
C A B C C C B .
Mệnh đề 2.2. Cho hai tập mờ ,A B trên tập đối tượng U. Khi đó
,d A B A B A B là một khoảng cách mờ giữa A và B .
Chứng minh.
Rõ ràng A B A B nên , 0d A B . Hơn nữa, , ,d A B d B A . Để
,d A B là độ đo khoảng cách, ta cần chứng minh bất đẳng thức tam giác. Không mất
tính chất tổng quát ta chứng minh , , ,d A B d A C d B C . Áp dụng tính chất 3)
của Mệnh đề 2.1 ta có:
A A B C C A C C B (1)
A A C B B A B B C (2)
Cộng (1) với (2), vế với vế ta được:
2 2 2A B A B A C A C B C B C (3)
Mặt khác, với hai số thực bất kỳ a, b ta luôn có max , min ,a b a b a b . Từ
đó ta có với mọi ix U , max , min ,i i i i i iB B BA A Ax x x x x x ,
nghĩa là A B A B A B . Do đó, từ (3) thu được:
A B A B A C A C B C B C
Hay , , ,d A B d A C d B C . Từ đó, ,d A B là một khoảng cách giữa hai
tập mờ A và B , gọi là khoảng cách mờ. Dựa trên khoảng cách mờ này, mục tiếp theo
chúng tôi xây dựng khoảng cách phân hoạch mờ.
57
2.3.2. Xây dựng khoảng cách mờ giữa hai phân hoạch mờ
Mệnh đề 2.3. Cho bảng quyết định ,DS U C D với 1 2, ,..., nU x x x và PR ,
QR là hai phân hoạch mờ sinh bởi hai quan hệ tương đương mờ PR , QR trên
,P Q C . Khi đó:
2
1
1
,
n
P Q i i i iP Q P Q
i
D R R x x x x
n
là một khoảng cách mờ giữa PR và QR , gọi là khoảng cách phân hoạch mờ.
Chứng minh.
Rõ ràng , 0P QD R R và , ,P Q Q PD R R D R R . Ta
cần chứng minh bất đẳng thức tam giác. Không mất tính chất tổng quát, với mọi
, ,P Q SR R R ta chứng minh
, , ,P Q P S Q SD R R D R R D R R . Từ Mệnh đề 2.2, với mọi
ix U ta có: , , ,i i i i i iP Q P S Q Sd x x d x x d x x . Từ đó:
, ,P Q P SD R R D R R
2 2
1 1
1 1n n
i i i i i i i iP Q P Q P S P S
i i
x x x x x x x x
n n
2 2 2
1 1 1
1 1 1
, , , ,
n n n
Q Si i i i i iP Q P S Q S
i i i
d x x d x x d x x D R R
n n n
Dễ thấy rằng, ,P QD R R đạt giá trị nhỏ nhất là 0 khi và chỉ khi
P QR R và ,P QD R R đạt giá trị lớn nhất là 1 khi và chỉ khi
PR và QR (hoặc PR và QR Do đó,
0 , 1P QD R R .
58
Mệnh đề 2.4. Cho PR là một phân hoạch mờ trên , khi đó ta có:
, , 1P PD R D R
Chứng minh. Giả sử 1 2, ,...,P nP P PR x x x . Khi đó
2
1
1
,
n
P i P
i
D R x
n
, 2
1
1
,
n
P i P
i
D R n x
n
. Từ đó ta có
, , 1P PD R D R .
Mệnh đề 2.5. Cho bảng quyết định ,DS U C D với 1 2, ,..., nU x x x và R là
quan hệ tương đương mờ xác định trên miền giá trị tập thuộc tính điều kiện, khi đó
khoảng cách mờ giữa hai tập thuộc tính C và C D được xác định như sau:
2
1
1
,
n
C C D i i iC C D
i
D R R x x x
n
Chứng minh. Từ Mệnh đề 2.3 ta có:
2
1
1
,
n
C C D i i i iC C D C C D
i
D R R x x x x
n
2 2
1 1
1 1n n
i i i i i i i iC C D C D C C D
i i
x x x x x x x x
n n
Dễ thấy rằng 10 , 1C C DD R R
n
. , 0C C DD R R khi
CR D và 1, 1C C DD R R
n
khi CR và i iDx x với
1 i n .
Mệnh đề 2.6. Cho bảng quyết định ,DS U C D với 1 2, ,..., nU x x x , B C và
R là quan hệ tương đương mờ xác định trên miền giá trị tập thuộc tính điều kiện.
Khi đó , ,B B D C C DD R R D R R
Chứng minh: Từ B C , theo [93] ta có C BR R , nghĩa là i iC Bx x với
1 i n , suy ra i iC Bx x với 1 i n . Xét đối tượng ix U ta có:
59
1 1
min ,
i i iC C D
n n
i i i j j jx x xC C D
j j
x x x x x x
1 1
min ,
i i iB B D
n n
i i i j j jx x xB B D
j j
x x x x x x
(1) Với j i Dx x ta có 1i D jx x , do đó
0i i i i i iC C D B B Dx x x x x x
(2) Với j i Dx x ta có 0i D jx x , do đó i i i i iC C D C Bx x x x x
i i iB B Dx x x .
Từ (1), (2) ta có:
Các file đính kèm theo tài liệu này:
- luan_an_mot_so_phuong_phap_lai_ghep_trong_rut_gon_thuoc_tinh.pdf