Một số tính chất của phủ suy dẫn từ họ phủ tập thô

 TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT Tập 7, Số 3, 2017 276–286 276 
MỘT SỐ TÍNH CHẤT CỦA PHỦ SUY DẪN TỪ HỌ PHỦ TẬP THÔ 
Nguyễn Đức Thuầna* 
aKhoa Công nghệ Thông tin, Trường Đại học Nha Trang, Khánh Hoà, Việt Nam 
Lịch sử bài báo 
Nhận ngày 10 tháng 01 năm 2017 | Chỉnh sửa ngày 30 tháng 04 năm 2017 
Chấp nhận đăng ngày 07 tháng 07 năm 2017 
Tóm tắt 
Lý thuyết tập thô là một công cụ hiệu quả và cần thiết để xử lý tính mơ hồ và hạt trong hệ 
thống thông tin. Phủ dựa trên lý thuyết tập thô (phủ tập thô) được đề xuất như một sự tổng 
quát của lý thuyết tập thô cổ điển. Do phủ tập thô là tổng quát và phức tạp hơn, vì vậy cần 
thiết phát triển các cấu trúc mới, phức tạp nhằm phát hiện tính chất đặc trưng của nó. Trong 
bài báo này, chúng tôi nghiên cứu phủ suy dẫn từ họ phủ tập thô. Một số kết quả lý thuyết 
liên quan đến độ đo tính đặc trưng của tri thức được phát hiện. 
Từ khóa: Đặc trưng tri thức; Họ phủ tập thô; Phủ suy dẫn; Tập thô. 
1. ĐẶT VẤN ĐỀ 
Trong nhiều ứng dụng thực tế, dữ liệu được tổ chức dưới dạng một phủ, thay cho 
các phân hoạch. Phủ được xây dựng trên tập thô xuất phát từ mối quan hệ dung sai thường 
được đề xuất, nghiên cứu nhằm xử lý các hệ thống thông tin thiếu dữ liệu. Với mục đích 
phát huy hiệu năng của phủ tập thô, nhiều tác giả đã nghiên cứu tính chất toán học, phát 
hiện các tính chất đặc trưng của phủ tập thô như: Rút gọn hệ thống thông tin và xây dựng 
hệ tiên đề cho phủ tập thô (William & Fei, 2002); Rút gọn tri thức và độ đo tri thức đặc 
trưng dựa vào phủ tập thô (Shi & Gong, 2008); Các phép xấp xỉ dựa vào phủ tập thô (Yao 
& Yao, 2012); Các độ đo cho phủ tập thô (Jianhua, Debiao, Huashi, & Haowei, 2014); 
và các toán tử láng giềng cho phủ tập thô (Lynn, Mauricio, Chriss, & Jonatan, 2016). Với 
mong muốn tìm được công cụ hiệu năng cao nhằm xử lý các hệ thống thông tin không 
đầy đủ, chúng tôi nhận thấy rằng phủ suy dẫn từ họ phủ tập thô được đề cập trong các bài 
báo của các tác giả Shi và Gong (2008); Shiping, Zhu, Quingxin và Fan (2012) có nhiều 
tiềm năng. Sự mở rộng các phủ suy dẫn này dựa trên các láng giềng các phần tử cũng cho 
* Tác giả liên hệ: Email: thuan.inf@ntu.edu.vn 
 TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [CHUYÊN SAN KHOA HỌC TỰ NHIÊN VÀ CÔNG NGHỆ] 277 
kết quả khả quan. Trong bài báo này chúng tôi khảo sát tính chất toán học của phủ suy 
dẫn, đề xuất một độ đo dùng để phân lớp dữ liệu trong các hệ thống thông tin quyết định 
không đầy đủ. 
Cấu trúc của bài báo gồm bốn mục: Mục 1 đặt vấn đề; Mục 2 nêu một số khái 
niệm cơ sở; Mục 3 nêu một số kết quả đạt được. Cuối cùng là kết luận và hướng phát 
triển của bài báo. 
2. MỘT SỐ KHÁI NIỆM CƠ SỞ 
Định nghĩa 1: Phủ tập thô (William & Fei, 2002) 
Cho U là tập vũ trụ, C là một họ các tập con khác rỗng của U. Nếu UC  , C 
được gọi là một phủ của U. Cặp ),( CU gọi là một không gian xấp xỉ phủ. 
Định nghĩa 2: Hệ thống láng giềng (Shi & Gong, 2008) 
Cho C là 1 phủ của U, Ux , hệ thống láng giềng của x, ký hiệu C(C,x), 
C(C,x) = }|{ KxCK , viết gọn C(x) 
Định nghĩa 3: Mô tả tối thiểu của x (William & Fei, 2002) 
Cho ),( CU là một không gian xấp xỉ phủ, Ux họ tập hợp 
}(|{)( SKKSSxCSKxCKxMd    được gọi là mô tả 
tối thiểu của x. 
Định nghĩa 4: Láng giềng của x (Lynn và ctg., 2016). 
Cho ),( CU là một không gian xấp xỉ phủ, Ux , một láng giềng của x ký hiệu 
)(xNC , xác định như sau: )}(|{)( xMdKCKxNC  
Mệnh đề 1: (Yao & Yao, 2012) 
Cho ),( CU là một không gian xấp xỉ phủ, Ux thì  )(xNC C(C,x). 
278 Nguyễn Đức Thuần 
Định nghĩa 5: (Shi & Gong, 2008) 
Cho },..,,{ 21 nCCCC là một phủ của U, Ux  , }|)({)( UxxMdCCov  
cũng là một phủ của U, chúng ta nói nó là một phủ suy dẫn của C. 
Định nghĩa 6: (Shi & Gong, 2008) 
Cho {C1, C2,...Cm} là một họ phủ của U, ,Ux  đặt 
CovxMdxMdx  )(|)({ (Ci), mi ,1  } thì }|{)( UxCov x cũng là một 
phủ của U, và chúng ta gọi là một phủ suy dẫn của . 
Nhận xét 1: Từ Định nghĩa 3 và Định nghĩa 6 ta có 
c
Cx xN )( 
Nếu là một phân hoạch của U, thì )( Cov cũng là một phân hoạch của U, khi 
đó x là một lớp tương đương chứa x. 
Định nghĩa 7: Phủ mịn hơn (Jianhua và ctg., 2014) 
Cho C1, C2 là 2 phủ của U. Nếu Ux  , C1(x) và C2(x) thỏa: 
(1) 212211 :)(),( KKxCKxCK    
(2) 211122 :)(),( KKxCKxCK    
Thì nói rằng C1 mịn hơn C2, ký hiệu C1 C2. 
Định nghĩa 8: Xấp xỉ dưới (Shi & Gong, 2008) 
Cho ),( CU là một không gian xấp xỉ phủ, UX  , xấp xỉ dưới của X ứng với 
không gian xấp xỉ phủ ),( CU được xác định bởi (1). 
})(|{)( XxNUxXC C  (1) 
 TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [CHUYÊN SAN KHOA HỌC TỰ NHIÊN VÀ CÔNG NGHỆ] 279 
Định nghĩa 9: (Shi & Gong, 2008) 
Cho là một họ phủ của U, P và Q là 2 phủ thuộc . Miền dương của Q ứng với 
P được xác định ( ) ( )P
X Q
POS Q P X
 . 
Định nghĩa 10: Mức đặc trưng (Shi & Gong, 2008) 
Cho ),,,,( GDFUS là một hệ thống thông tin quyết định phủ, trong đó U là 
tập vũ trụ, là một họ phủ của U, F là hàm thông tin, D thuộc tính quyết định, G là quan 
hệ tương đương phân hoạch theo thuộc tính quyết định D. Với mỗi C , mức đặc trưng 
của C đối với D được xác định như trong Công thức (2). 
U
DUPOS
U
DUPOS
Dsig
CCovCov
C
)/()/(
)(
}){()( 
 (2) 
Bổ đề 1: (Jianhua và ctg., 2014) 
Cho C1, C2 là 2 phủ của U, nếu C1 C2 thì )()(
21
xNxN CC  , x Ur 
Chứng minh: 
111 :)()(1 KyxCKxNy C   , do C1 C2 nên 
211122 :)(),( KKxCKxCK    , do đó )()(, 2222 xCyxCKKy   
Nói khác hơn, )(
2
xNy C 
Định nghĩa 11: Hệ thống thông tin quyết định không đầy đủ 
Một hệ thống tin là một bộ bốn thành phần S=, trong đó: U là tập hữu 
hạn khác rỗng (tập vũ trụ); A là tập hữu hạn khác rỗng các thuộc tính; 
a
a A
V V
, với 
( ) ,a aV Dom a V  ; 
:f U A V , ( , ) af x a v V ; Nếu ,c A x U mà ( , )f x c
không xác định thì S gọi là hệ thống thông tin không đầy đủ hay hệ thống thông tin có 
thuộc tính thiếu dữ liệu; S được gọi là hệ thống thông tin quyết định nếu 
, ,A C D C D C    là tập thuộc tính điều kiện, D là tập thuộc tính quyết định. Hệ 
280 Nguyễn Đức Thuần 
thống thông tin quyết định ký hiệu thu gọn là S ( , , )U C D 
3. MỘT SỐ KẾT QUẢ ĐẠT ĐƯỢC 
Bổ đề 2: Cho },..,,{ 21 mCCC là một họ phủ của U, nếu C1 C2 thì x U :
xx CC }){(}){( 21  
Chứng minh: Ký hiệu .)(
3
' 
m
i
Cx xN i
 Ta có: 
'
1 )(}){\( 2 xCx xNC  ; 
.)(}){\( '2 1 xCx xNC  Từ Bổ đề 1, nếu C1 C2 thì )()( 21 xNxN CC  nên 
xx CC }){(}){( 21  
Mệnh đề 1: Cho },..,,{ 21 mCCC là một họ phủ của U, nếu C1 C2 thì: 
(1) }){(}){( 12 CCovCCov  ; 
(2) )/()/( }){(}){( 12 DUPOSDUPOS CCovCCov  . 
Chứng minh: 
(1) Là kết quả trực tiếp từ Bổ đề 2, Định nghĩa 6 và Định nghĩa 7; 
(2) )(}){()/(
/
1}){( 1
XCCovxDUPOSx
DUX
CCov 
  , mà 
XCXC xx   }){(}){( 21 do xx CC }){(}){( 12  (bổ đề 
2) 
Vì vậy, )/(}){( 2 DUPOSx CCov . Nói khác hơn, 
)/()/( }){(}){( 12 DUPOSDUPOS CCovCCov  . 
Mệnh đề 2: 
Cho ),,,,( GDFUS là một hệ thống thông tin quyết định phủ. Nếu C1 C2 thì 
)()(
21
DsigDsig CC 
Chứng minh: là kết quả trực tiếp từ Định nghĩa 10, kết quả (b) của Mệnh đề 1. 
 TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [CHUYÊN SAN KHOA HỌC TỰ NHIÊN VÀ CÔNG NGHỆ] 281 
Nhận xét 2: Bài toán phân lớp, xây dựng cây quyết định, rút trích luật quyết định 
là bài toán quan trọng trong lĩnh vực khai phá dữ liệu. Đối với các hệ thống thông tin 
quyết định không đầy đủ cũng có nhiều tác giả quan tâm và đưa ra các giải pháp tiếp cận 
bài toán khác nhau (Marzena, 1998; Li, Li, & Wu, 2009). Các giải pháp này thường điểm 
mấu chốt là tìm các thuộc tính phân chia các đối tượng vào các lớp xấp xỉ các lớp quyết 
định nhanh nhất. Tư tưởng chung trong việc lựa chọn thuộc tính phân chia là sử dụng 
thuộc tính xấp xỉ phân lớp tốt nhất tập thuộc tính quyết định trên tập đối tượng cần phân 
chia. Để làm điều này, trong hệ thống thông tin đầy đủ một số tác giả đã đề xuất các độ 
đo để xác định thuộc tính phân chia (Nguyễn, 2010). Trong hệ thống thông tin không đầy 
đủ, từ tính chất ở Mệnh đề 2 cho thấy thuộc tính phân lớp mịn hơn thì mức đặc trưng cao 
hơn, có nghĩa là sự phân lớp của thuộc tính này xấp xỉ phân lớp của tập thuộc tính quyết 
định là tốt nhất, vì vậy có thể sử dụng làm độ đo để xác định thuộc tính phân chia các đối 
tượng. Để minh họa độ đo mức đặc trưng trên một hệ thống thông tin không đầy đủ, 
chúng ta xem xét ví dụ như sau: 
Ví dụ: Xét hệ thống thông tin quyết định không đầy đủ S=(U, AT, D) như trong 
Bảng 1. Trong đó, },,,,,{ 654321 uuuuuuU là tập vũ trụ; AT={Price, Mileage, Size, 
Max_Speed} là tập thuộc tính điều kiện; D thuộc tính quyết định. 
Bảng 1. Ví dụ về hệ thống thông tin quyết định không đầy đủ S = (U, AT, D) 
U Price (p) Mileage (M) Size (S) Max_speed (A) D 
u1 High High Full Low Good 
u2 Low * Full Low Good 
u3 * * Compact High Poor 
u4 High * Full High Good 
u5 * * Full High Excel 
u6 Low High Full * Good 
Xét quan hệ dung sai trên mỗi thuộc tính như sau: 
,ATA  SIM(A) = {(x,y) UxU: A(x)=A(y) or A(x)= * or A(y)=*} 
Ta có các phủ của U: 
282 Nguyễn Đức Thuần 
}},,,{},,,,{{ 653254311 uuuuuuuuCC P 
}},,,,,{{ 6543212 uuuuuuCC M 
}}{},,,,,{{ 3654213 uuuuuuCC S 
}},,,{},,,{{ 65436214 uuuuuuuCC A 
},,,{ 4321 CCCC ; }}{},{},,,,{{/ 536421 uuuuuuDU 
}{};{};,{};{};,{};{ 65543621 654321 uuuuuuuu uuuuuu 
:}){( 1C 
};,,{}){( 6211 1 uuuC u };,,{}){( 6211 2 uuuC u };{}){( 31 3 uC u 
};,,{}){( 6541 4 uuuC u };,,{}){( 6541 5 uuuC u };{}){( 61 6 uC u 
:}){( 2C 
};{}){( 12 1 uC u };,{}){( 622 2 uuC u };{}){( 32 3 uC u 
};,{}){( 542 4 uuC u };{}){( 52 5 uC u };{}){( 62 6 uC u 
:}){( 3C 
};{}){( 13 1 uC u };,{}){( 623 2 uuC u };,{}){( 533 3 uuC u 
};,,{}){( 5433 4 uuuC u };,{}){( 533 5 uuC u };{}){( 63 6 uC u 
:}){( 4C 
};,,{}){( 5414 1 uuuC u };,,{}){( 6524 2 uuuC u };{}){( 34 3 uC u 
 TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [CHUYÊN SAN KHOA HỌC TỰ NHIÊN VÀ CÔNG NGHỆ] 283 
};,,{}){( 5414 4 uuuC u };{}){( 54 5 uC u };,,{}){( 6524 6 uuuC u 
};,,,{)/( 6321}){( 1 uuuuDUPOS CCov };,,,,{)/( 65321}){( 2 uuuuuDUPOS CCov 
};,,{)/( 621}){( 3 uuuDUPOS CCov };,{)/( 53}){( 4 uuDUPOS CCov 
};,,,,{)/( 65321)( uuuuuDUPOSCov 
2
1
)(;
3
1
)(;0)(;
6
1
)(
4321
 DsigDsigDsigDsig CCCC 
Chọn thuộc tính phân chia tập đối tượng là Max_Speed (A), U được phân thành 
hai lớp: 
Max_Speed (A)= Low  },,,{},,{ 6421621 uuuuDuuu Good  
Max_Speed (A)= High  },,,{ 6543 uuuu 
Xét hệ thống thông tin quyết định S’={U1,AT1, D}, với U1= },,,{ 6543 uuuu , 
AT1={Price (P), Mileage (M), Size (S)} 
Ta có các phủ của U1: 
 }},,,{{}};,,{},,,{{ 6543
''
2653543
''
1 uuuuCCuuuuuuCC MP 
 }},,{},{{ 6543
''
3 uuuuCC S ; },,{
'
3
'
2
'
1
' CCC ; U1/D = }}{},,{},{{ 5643 uuuu 
 },{};{};,{};{ 65
'
5
,
54
'
3
'
6543
uuuuuu uuuu 
};{}){( 3
'
1
'
3
uC u };,,{}){( 654
'
1
'
4
uuuC u 5
' '
1 4 5 6( { }) { , , };uC u u u 
6
' '
1 4 5 6( { }) { , , };uC u u u 
};{}){( 3
'
2
'
3
uC u };,{}){( 54
'
2
'
4
uuC u };{}){( 5
'
2
'
5
uC u 
};,{}){( 65
'
2
'
6
uuC u 
284 Nguyễn Đức Thuần 
};,{}){( 53
'
3
'
3
uuC u };,,{}){( 543
'
3
'
4
uuuC u };,{}){( 53
'
3
'
5
uuC u 
};,,{}){( 653
'
3
'
6
uuuC u 
' '
1
1 3( { })
( / ) { }
Cov C
POS U D u
 ; ' '
2
1 3 5( { })
( / ) { , }
Cov C
POS U D u u
 
)/( 1}){( '3'
DUPOS
CCov
' ' '
1 2 3
1 1
( ) ; ( ) 0; ( )
4 2C C C
sig D sig D sig D 
Chọn thuộc tính phân chia tập đối tượng là Size (S), U1 được phân thành 2 lớp: 
Size (S)= Compact }{}{ 33 uDu Poor  ; Size (S)= Full },,{ 654 uuu 
Xét hệ thống thông tin quyết định S’ = {U2,AT2, D}, với U2= },,{ 654 uuu , 
AT2={Price (P), Mileage (M)}. Ta có các phủ của U2: 
}},,{{}};,{},,{{ 654
""
26554
""
1 uuuCCuuuuCC MP , 
}}{},,{{/ 5642 uuuDU 
};,{ "2
"
1
" CC };,{ 54
"
4
uuu };{ 5
"
5
uu };,{ 65
"
6
uuu 
},,{}){(}){(}){( 654
"
1
""
1
""
1
"
654
uuuCCC uuu 
},{}){( 54
"
2
"
4
uuC u ; }{}){( 5
"
2
"
5
uC u ; },{}){( 65
"
2
"
6
uuC u 
 
)/( 2}){( "1"
DUPOS
CCov
; )/(}{)/( 2)(52}){( ""2"
DUPOSuDUPOS
CovCCov 
3
1
)("
1
 Dsig
C
; 0)("
2
 Dsig
C
 Chọn thuộc tính Price (P) để phân lớp, U2 phân 
thành Price=High },{ 54 uu ; Price=Low },{ 65 uu ; và không còn phân chia được nữa. 
Như vậy ta xây dựng được cây quyết định biểu diễn bởi Hình 1, suy dẫn được 2 luật quyết 
định tương ứng: 
(1) GoodDLowSpeedMax _ 
 TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [CHUYÊN SAN KHOA HỌC TỰ NHIÊN VÀ CÔNG NGHỆ] 285 
(2) PoorDCompactSizeHighSpeedMax  _ 
Hình 1. Cây quyết định 
4. KẾT LUẬN 
Trong bài báo này, chúng tôi phát hiện được một số tính chất toán học về phủ suy 
dẫn từ họ phủ tập thô liên quan đến mức đặc trưng của phủ đối với họ phủ, và mối quan 
hệ giữa láng giềng của một đối tượng x ứng với 2 phủ có mối quan hệ mịn hơn. Những 
kết quả này có thể dùng để phát triển thành độ đo hỗ trợ xây dựng cây quyết định hay rút 
trích đặc trưng. Trong thời gian đến, chúng tôi sẽ thử nghiệm trên các bộ dữ liệu UCI để 
đánh giá cụ thể hơn. 
TÀI LIỆU THAM KHẢO 
Jianhua, D., Debiao, H., Huashi, S., & Haowei, T. (2014). Uncertainty measurement for 
covering rough sets. International Journal of Uncertainty, Fuzziness and 
Knowledge-Base Systems, 22(2), 217-233. 
Li, P., Li, F., & Wu, Q. (2009). Uncertainty analysis to the decision rule of incomplete 
information system. Paper presented at The Information Technology and 
Applications Conference, USA. 
Lynn, D., Mauricio, R., Chriss, C., & Jonatan, G. (2016). Neighborhood operator for 
covering-based rough sets. International Sciences, 336, 21-24. 
Marzena, K. (1998). Rough set approach to incomplete information system. Information 
Sciences, 112, 39-49. 
286 Nguyễn Đức Thuần 
Mauricio, R., Chris, C., & Jonatan, G. (2013). Characterization of neighborhood 
operators for covering based rough sets using duality and adroitness. Paper 
presented at The Eureka-2013, Fourth International Workshop Conference, USA. 
Nguyễn, T. T. (2010). Về một metric trên họ các phân hoạch của một tập hữu hạn. Tạp 
chí Tin học và Điều khiển học, 20(1), 75-87. 
Shi, Z., & Gong, Z. (2008). Knowledge reduction and knowledge significance measure 
based on covering rough sets. International Journal of Pure and Applied 
Mathematics, 48(1), 1-9. 
Shiping, W., Zhu, W., Quingxin, Z., & Fan, M. (2012). Covering base. Journal of 
Information and Computer Sciences, 9(5), 1343-1355. 
William, Z., & Fei, Y. W. (2002). Reduction and axiomatization of covering generalized 
rough sets. Information Sciences, 152, 217-230. 
Yao, Y. Y., & Yao, B. (2012). Covering based rough sets approximation. Information 
Sciences, 200, 91-107. 
SOME PROPERTIES OF INDUCED COVER FROM FAMILY OF 
COVERING ROUGH SETS 
Nguyen Duc Thuana* 
aThe Faculty of Information Technology, Nhatrang University, Khanhhoa, Vietnam 
*Corresponding author: Email: thuan.inf@ntu.edu.vn 
Article history 
Received: January 10th, 2017 | Received in revised form: April 30th, 2017 
Accepted: July 07th, 2017 
Abstract 
Rough set theory is an efficient and essential tool for dealing with vagueness and granularity 
in information systems. Covering based rough set theory is proposed as a significant 
generalization of classical rough sets. It is more general and complex than classical rough 
set theory, hence there is much need to develop sophisticated structures to characterize 
covering-based rough sets. In this paper, we studied induced cover from family of covering 
rough set. Some theoretical results related to the measuring significance of knowledge were 
obtained and investigated. 
Keywords: Family of covering rough set; Induced cover; Knowledge significance; Rough 
set.