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ờ

.4 1 0 No 
 0.8 0.2 0 0.6 0.2 0.8 Yes 
 0.6 0.4 0.8 0.2 0.6 0.4 No 
 0 0.4 0.6 0.4 0 1 Yes 
 u5 0 0.6 0.6 0.4 0 1 Yes 
 u6 0 0.6 0 1 0 1 No 
 Chúng tôi sử dụng quan hệ tương đương mờ xác định trên miền giá trị của 
thuộc tính cCk như sau [54, 68, 76] 
 ck u i c k u j c k u i c k u j 
 1 4* , 0.25
 R c (,) u u 
 k ij max(ck ) min( c k ) max( c k ) min( c k ) 
 0,otherwise
 Với max cckk , min 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 ck Áp dụng các bước của Thuật toán F_FRSAR tìm một tập 
rút gọn của bảng quyết định. Trước hết, tính các ma trận quan hệ trên các thuộc tính 
điều kiện MR c1 , MR c2 , MR c3 , MR c4 , MR c5 , MR c6 . Từ đó, 
 OCU 22 
tính ma trận MR C : 
 43 
 1 0 0 0 0 0
 0 1 0 0 0 0
 0 0 1 0 0 0
 MR()C 
 0 0 0 1 0 0
 0 0 0 0 1 0
 0 0 0 0 0 1
 Ta có U/,,,,, d u1 u 3 u 6 u 2 u 4 u 5 . Xét X u1,, u 3 u 6, xấp xỉ mờ dưới 
 RXC là tập mờ với hàm thuộc của xU tính bởi 
 R u,, u u x inf max 1 x y ,  u,, u u y 
 C 1 3 6 yU C 1 3 6 
 1 0 0 0 0 0
 u 
 Từ ma trận MC ta có  1C 
 u1 u 2 u 3 u 4 u 5 u 6
 Do đó  u1 inf 1,1,1,1,1,1 1 , tương tự ta có 
 RC u1,, u 3 u 6
  u2 0 ,  u3 1 ,  u4 0 ,  u5 0 , 
 RC u1,, u 3 u 6 RC u1,, u 3 u 6 RC u1,, u 3 u 6 RC u1,, u 3 u 6
  u6 1 ,  u1 0 ,  u2 1 ,  u3 0 , 
 RC u1,, u 3 u 6 RC u2,, u 4 u 5 RC u2,, u 4 u 5 RC u2,, u 4 u 5
  u4 1,  u5 1,  u6 0 . 
 RC u2,, u 4 u 5 RC u2,, u 4 u 5 RC u2,, u 4 u 5
 Từ đó, hàm thuộc của các đối tượng đối với miền dương mờ POS d là: 
 RC  
  u 1
 POS d u1 sup  u 1 ,  u 1 1 , POS d 2 , 
 R  RCC u1,,,, u 3 u 6 R u 2 u 4 u 5  R  
 C C
 POS d u3 1 , POS d u4 1 , POS d u5 1 , POS d u6 1 . 
 RC  RC  RC  RC  
Từ đó:  d 1 
 RC  
 Áp dụng các bước của Thuật toán F_FRSAR ta có  d 0.167 , 
 Rc1
 d 0 ,  d 0.167 ,  d 0.5 ,  d 0.467 , 
 Rc2 Rc3 Rc4 Rc5
 d 0.467. Chọn thuộc tính c4 có độ quan trọng lớn nhất và Pc 4. Thực 
 Rc6
hiện vòng lặp While. Xét các thuộc tính c ta có: 
 1 
 44 
 SIG c1  d d 1 0.5 0.5 . Tương tự SIG c2 0.5 , 
 RRR c4 c 4, c 1 c 4 R c4
SIG c3 0 , SIG c5 0.5 , SIG c6 0.5 . Không mất tính tổng quát, chọn 
 R c4 R c4 R c4
thuộc tính c1 có độ quan trọng lớn nhất và P c14, c  . Khi đó ta có 
 dd 1  , do đó thuật toán dừng và là một tập rút gọn của 
 RR c14, c C
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 
 DS  U, C D C a, a ,..., a
 Xét bảng quyết định với 12 và R làm quan hệ 
 aa, ,...
tương đương mờ xác định trên miền giá trị thuộc tính. Đặt  D . Theoii12 thuật 
 RC 
toán F_FRSAR, giả sử các thuộc tính được thêm vào tập rỗng theo giá trị 
 tm 1,2,... 
lớn nhất của độ quan trọng thuộc tính cho đến khi tồn tại sao cho 
D . Kết thúc thuật toán filter F_FRSAR, ta thu được tập rút gọn 
 R a, a ,..., a 
 i12 i it 
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. 
 i12 i it 
 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ó  DDD  ...   . Với ngưỡng  cho 
 RRR ai a i, a i a i ,..., a i
 1 1 2B a,..., a 1 t  
 k i1 ik 
trước, đặt thỏa mãn  D và  D . Khi đó, được 
 RBk RBaki 
 Bk k 1
 
gọi là tập rút gọn xấpB xỉ ngư aỡ,...,ng a . Nếu và được sử dụng để 
 k ikt 1 i 
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 
 chưa chắc đã tốt hơn trên . Giả sử có độ chính xác phân lớp 
tốt hơn . Khi đó, nếu chọn là kết quả của thuật toán thì 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ờ 
 DS  U, C D 
đượ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 với C a12, a ,..., an, quanR hệ tương 
đương mờ 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ỉ Sx có độ chính xác phân lớp tốt nhất. 
 // Khởi tạo 
 1. B : ;   D 0 ; S : ; 
 2. Tính độ phụ thuộc mờ ; 
 // 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 DD do 
 RRBC 
 4. Begin 
 5. Với mỗi a C B tính SIG a  D D 
 B RRB a B 
 6. Chọn am C B sao cho SIGB a m Max SIG B a ; 
 a C B 
 7. B  B a ; SSB ; 
 m
 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 
 tS 
 9. Đặt //t là số phầnD tử của S, S chứa các chuỗi thuộc tính được 
 RC 
 chọn tại mỗi bước lặp của vòng lặp While, nghĩa là 
 46 
 S a, a , a ,..., a , a ,..., a ; CU,
 i1 i 1 i 2 i 1 i 2 it 
 10. Đặt S a, S a , a ,..., S a , a ,..., a 
 12 i1 i 1 i 2 t i 1 i 2 it 
 11. For j = 1 to t 
 12. Begin 
 13. Tính độ chính xác phân lớp trên S j bằng một bộ phân lớp sử dụng 
 phương pháp 10-fold; 
 14. End 
 15. SSx jo với S jo có độ chính xác phân lớp lớn nhất. 
Return Sx ; 
 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ử và ký hiệ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à OCU 22* , do đó độ phức tạp của giai đoạn filter 
(từ câu lệnh 3 đến 8) là . Độ 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à OTDd ,  khi đó độ phức tạp của giai đoạn wrapper là 
OCT * . Vì vậy, độ phức tạp của thuật toán FW_FRSAR là OCUOCT 22** 
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 
 Số thuộc tính điều kiện 
 Tất Thuộc Thuộc 
 Số lớp 
 Số đối cả tính định tính 
STT Bộ dữ liệu Mô tả quyết 
 tượng danh thực 
 định 
 (nominal) (Real-
 valued) 
 1 Ecoli Protein Localization 336 7 0 7 8 
 Sites 
 2 Ionosphere Johns Hopkins 351 34 0 34 2 
 University 
 Ionosphere database 
 3 WDBC Wisconsin 569 30 0 30 2 
 diagnostic breast 
 cancer 
 4 Wpbc Wisconsin 198 33 0 33 2 
 Prognostic Breast 
 Cancer 
 5 Wine Wine recognition 178 13 0 13 3 
 data 
 6 Glass Glass Identification 214 9 0 9 7 
 Database 
 7 Magic04 MAGIC gamma 19020 10 0 10 2 
 telescope data 2004 
 8 Page- Blocks 5473 10 0 10 5 
 Classification 
 blocks 
 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ờ trên miền giá trị của thuộc tính như sau [54, 68, 
76] 
 R
 Với 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 . Trên thuộc tính quyết định d chúng tôi sử dụng quan 
hệ tương đương R . Phân hoạch U/ R  x x U với 
 d d d  
x y U R( x , y ) 1 là một lớp tương đương. Khi đó, lớp tương đương x 
  d d   d
được xem là lớp đương đương mờ, ký hiệu là x , với hàm thuộc  y 1 nếu 
 d xd
yx   và  y 0 nếu yx   . 
 d xd d
 Để 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 
 cCk 
quyết định ban đầu theo tiếp cận tập thô mờ. 
 ck u i c k u j c k u i c k u j 
 - Chúng tôi sử 1d ụng 4* bộ phân lớp SVM và , C4.5 trong công cụ R 0.25 để tính độ 
 R c (,) u u 
 k ij max(ck ) min( c k ) max( c k ) min( c k )
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 
 0,otherwise
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ằngmax nhau, cckk lấ ,y min 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á ctrìnhk đượ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 
 Rút gọn thuộc tính theo tiếp Rút gọn thuộc tính theo 
 cận tập thô (RSAR) tiếp cận tập thô mờ 
ST Bộ số (F_FRSAR) 
 C 
T liệu Độ chính Độ chính Độ chính Độ chính 
 xác phân xác phân xác phân xác phân 
 lớp SVM lớp C4.5 lớp SVM lớp C4.5 
1 Ecoli 336 7 5 0.851 0.819 7 0.865 0.855 
2 Ionospher 351 34 10 0.814 0.802 15 0.937 0.915 
 e 
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 10 4 0.745 0.715 6 0.782 0.765 
 0 
8 Page- 5473 10 5 0.758 0.725 7 0.865 0.855 
 blocks 
 U
 R 
 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 
 Thuật toán Thuật toán F_FRSAR 
 GAIN_RATIO_AS_FRS 
 Bộ số [45] 
STT U C 
 liệu Độ chính Độ chính Độ chính Độ chính 
 xác phân xác phân xác phân xác phân 
 lớp SVM lớp C4.5 lớp SVM lớp C4.5 
1 Ecoli 336 7 6 0.814 0.802 7 0.865 0.855 
 R
2 Ionos 351 34 13 0.916 0.904 15 0.937 0.915 
 phere 
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 
 Magic 1902
7 10 6 0.782 0.765 6 0.782 0.765 
 04 0 
 Page-
8 5473 10 6 0.852 0.848 7 0.865 0.855 
 blocks 
 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 đó, là số đối tượng, là số thuộc tính điều kiện, 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 
 Tập dữ liệu Thuật toán Thuật toán Thuật toán 
 ban đầu FW_FRSAR F_FRSAR GAIN_RATIO 
 Tập dữ _AS_FRS [45] 
STT 
 liệu 
 U C R Độ chính Độ chính Độ chính 
 xác phân xác phân xác phân 
 lớp C4.5 lớp C4.5 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 
 Page-
 8 5473 10 5 0.906 7 0.855 6 0.848 
 blocks 
 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à 
 U
tìm ứng cử viên có độ chính xác phân lớp tốt nhất. 
 NhưC vậy, thuật toán đề xuất filterR-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 
 Thuật toán FW_FRSAR Thuật toán Thuật toán 
 F_FRSAR GAIN_RATIO 
STT Bộ dữ liệu 
 Thủ tục Thủ tục Tổng _AS_FRS 
 Filer Wrapper cộng [45] 
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 
 Page-
 8 5473 10 98.64 22.16 120.80 112.76 126.28 
 blocks 
 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, 
 U C
 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 U x12, x ,..., xn , PQC,  và 
K P x x U , K Q x x U là hai phân hoạch trên P và Q. Trong 
  iiP   iiQ 
công trình [48], Liang và các cộng sự đã chứng minh 
 U xx
 1  iiPQ 
 DKPKQ , 
 UU 
 i 1 
 x x x  x x  x
 với  iPQPQPQ i  i  i  i  i  là khoảng cách phân hoạch giữa 
KP và KQ . 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ạ d: U U  0, thỏa mãn các điều kiện sau với 
mọi x,, y z U 
 P 1 d x,0 y , d x,0 y khi và chỉ khi xy . 
 P 2 d x,, y d y x . 
 P 3 d x,,, y d y z d x z . 
 Điều kiện đượ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 ab . Khi đó ta có a b min a , m min b , m 
Mệnh đề 2.1. Cho ba tập mờ ABC,, trên cùng tập đối tượng U. Khi đó ta có các mệnh 
đề sau: 
 1) Nếu AB thì BBCAAC   . 
 2) Nếu AB thì CCACCB   . 
 3) AABCCACCB    
Chứng minh. 
 1) Vì AB , với mọi xU ta có xx . Áp dụng Bổ đề 2.1 ta có: 
 i BA ii 
  x  x min  x ,  x min  x ,  x 
 BBCCiAA i i i i i 
 UUUU
 x  x min  x ,  x min  x ,  x
 BBCC i AA i  i i  i i 
 i 1 i 1 i 1 i 1
    BABCACBBCAAC
 AB xU xx 
 2) Vì , với mọi i ta có BA ii 
 minx ,  x min  x ,  x
 BCAC i i i i 
 CCCBC xi min A x i ,  x i  x i min  x i ,  x i 
 UUUU
 x min  x ,  x  x min  x ,  x
 CCCBC i  A