Rút gọn thuộc tính của bảng quyết định sử dụng miền dương mờ

Cao Chính Nghĩa, Vũ Đức Thi, Tân Hạnh, Nguyễn Long Giang
Tạp chí KHOA HỌC CÔNG NGHỆ 
THÔNG TIN VÀ TRUYỀN THÔNG
Số 2 (CS.01) 2016 3
RÚT GỌN THUỘC TÍNH CỦA BẢNG QUYẾT ĐỊNH 
SỬ DỤNG MIỀN DƯƠNG MỜ
Cao Chính Nghĩa1, Vũ Đức Thi2, Tân Hạnh3, Nguyễn Long Giang
4 
1Học viện Cảnh sát nhân dân, Bộ Công an 
2Đại học Sư phạm Kỹ thuật Hưng Yên 
3Học viện Công nghệ Bưu chính Viễn thông 
4Viện Công nghệ thông tin
Tóm tắt: 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 khi áp dụng trên các 
bảng quyết định có miền giá trị số thực cần phải 
rời rạc hóa dữ liệu. Việc rời rạc hóa dữ liệu dẫn 
đến mất mát thông tin làm ảnh hưởng đến độ chính 
xác phân lớp dữ liệu. 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 có miền 
giá trị số thực theo tiếp cận tập thô mờ khắc phục 
được hạn chế trên. Trong bài báo này, chúng tôi đề 
xuất hai phương pháp rút gọn thuộc tính sử dụng 
miền dương mờ dựa trên phân hoạch mờ và quan 
hệ tương tự mờ. Phân tích đánh giá từng phương 
pháp, kết luận phương pháp sử dụng quan hệ tương 
tự mờ có khả năng áp dụng thực tế.
Từ khóa: tập thô mờ, bảng quyết định mờ, phân 
hoạch mờ, quan hệ tương tự mờ, miền dương mờ, 
rút gọn thuộc tính, tập rút gọn.1
I. MỞ ĐẦU
Rút gọn thuộc tính là bài toán quan trọng trong bước 
tiền xử lý số liệu với mục tiêu là giảm số chiều dữ liệu 
(số thuộc tính) nhằm tăng tính hiệu quả của các thuật 
toán khai phá dữ liệu. 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ô truyền thống của 
Pawlak được thực hiện trên các bảng quyết định có 
miền giá trị rời rạc [6]. Đối với các bảng quyết định 
có miền giá trị số thực, cần phải rời rạc hóa dữ liệu 
trước khi áp dụng các phương pháp rút gọn thuộc tính 
Tác giả liên hệ: Cao Chính Nghĩa 
Email: ccnghia@gmail.com
Đến tòa soạn: 23/7/2016, chỉnh sửa: 30/8/2016, chấp nhận đăng: 
03/9/2016. 
theo tiếp cận tập thô truyền thống dẫn đến mất mát 
thông tin, làm hạn chế độ chính xác phân lớp của dữ 
liệu. Để khắc phục vấn đề này, D. Dubois và các cộng 
sự đề xuất mô hình tập thô mờ (fuzzy rough set) kết 
hợp giữa lý thuyết tập thô và lý thuyết tập mờ [1]. Lý 
thuyết tập mờ đóng vai trò bảo toàn ngữ nghĩa của dữ 
liệu, còn lý thuyết tập thô bảo toàn tính không phân 
biệt được của dữ liệu. 
Các công trình nghiên cứu về rút gọn thuộc tính 
theo tiếp cận tập thô mờ đang được phát triển [2, 5, 
7, 9, 10] và cần nhiều hơn nữa sự đóng góp kết quả 
của cộng đồng nghiên cứu.
Trong bài báo này, chúng tôi đề xuất hai phương 
pháp rút gọn thuộc tính điển hình sử dụng miền 
dương mờ theo tiếp cận tập thô mờ dựa trên phân 
hoạch mờ và quan hệ tương tự mờ. Phương pháp 
dựa trên phân hoạch mờ áp dụng cho lớp bài toán 
rút gọn thuộc tính của bảng quyết định mờ. Phương 
pháp sử dụng quan hệ tương tự mờ áp dụng cho lớp 
bài toán rút gọn thuộc tính của bảng quyết định có 
miền giá trị số thực. Dựa trên phân tích đánh giá 
từng phương pháp đi đến kết luận là các phương 
pháp rút gọn thuộc tính của bảng quyết định dựa 
trên quan hệ tương tự mờ là có khả năng áp dụng 
thực tế và được cộng đồng quan tâm nghiên cứu 
sôi động lâu nay. Dưới đây trình bày một số khái 
niệm cơ bản về tập thô mờ; các phương pháp rút 
gọn thuộc tính của bảng quyết định sử dụng miền 
dương mờ và kết quả thực nghiệm; kết luận và 
hướng phát triển tiếp theo.
RÚT GỌN THUỘC TÍNH CỦA BẢNG QUYẾT ĐỊNH SỬ DỤNG MIỀN DƯƠNG MỜ
Tạp chí KHOA HỌC CÔNG NGHỆ 
THÔNG TIN VÀ TRUYỀN THÔNG4 Số 2 (CS.01) 2016
II. MỘT SỐ KHÁI NIỆM CƠ BẢN VỀ TẬP 
THÔ MỜ
Hệ thông tin là một cặp ( , )IS U A= trong đó U là 
tập hữu hạn, khác rỗng các đối tượng; A là tập khác 
rỗng, hữu hạn các thuộc tính. Mỗi thuộc tính a A∈ 
xác định một ánh xạ: : aa U V→ với aV là tập giá 
trị của thuộc tính a A∈ . Bảng quyết định là dạng 
đặc biệt của hệ thông tin trong đó tập các thuộc tính 
A bao gồm hai tập con tách biệt nhau: tập các thuộc 
tính điều kiện C và tập các thuộc tính quyết định 
D, ký hiệu là ( ),DS U C D= È với C DÇ = ∅ . Bảng 
quyết định mờ là bảng quyết định mà các giá trị của 
thuộc tính là các tập mờ.
A. Quan hệ tương tự mờ
Cho hệ thông tin là một cặp IS = (U, A). Một quan 
hệ R xác định trên U được gọi là quan hệ tương tự mờ 
(fuzzy similarity relation) nếu thỏa mãn các điều kiện 
sau đây [5].
1) Tính phản xạ: ( ), 1,R x x x U= ∀ ∈
2) Tính đối xứng: ( ) ( ), , , ,R x y R y x x y U= ∀ ∈
3) Tính bắc cầu max - min:
 ( ) ( ) ( ){ }, min , , ,R x z R x y R y z≥ với mọi , ,x y z U∈ . 
B. Phân hoạch mờ
Cho bảng quyết định ( ),DS U C D= È , mỗi tập 
thuộc tính P C⊆ xác định một quan hệ tương tự 
(tương đương) mờ. Tương tự trong lý thuyết tập thô 
truyền thống, dựa trên quan hệ tương tự mờ, mỗi 
tập thuộc tính P C⊆ xác định một phân hoạch mờ 
như sau:
với { }( ){ }/ : /U P a P U IND a= ⊗ ∈ (1)
 { }: , ,A B X Y X A Y B X Y⊗ = Ç ∀ ∈ ∀ ∈ Ç ¹ ∅ .
Mỗi phần tử thuộc U/P là một lớp tương đương mờ 
(fuzzy equivalence class)
với [ ] ( ) ( ),P Px y x yµ µ= . 
Ví dụ, nếu { },P a b= , { }( ) { }/ ,a aU IND a N Z= và 
U/IND({b}) = {Nb, Zb}, khi đó
{ }/ , , ,a b a b a b a bU P N N N Z Z N Z Z= Ç Ç Ç Ç . 
Hàm thành viên của các đối tượng trong lớp tương 
đương mờ được xác định dựa trên lý thuyết tập 
mờ [4].
( ) ( ) ( ) ( )( )1 1 2... , ,...,n nF F F F Fx min x x xµ µ µ µÇ Ç = (2)
C. Tập thô mờ định nghĩa theo phân hoạch mờ
Dựa vào các lớp tương đương mờ, khái niệm tập 
xấp xỉ dưới và xấp xỉ trên được mở rộng thành tập 
xấp xỉ dưới mờ (fuzzy lower approximation) và 
xấp xỉ trên mờ (fuzzy upper approximation). Với 
tập thuộc tính P C⊆ , hàm thành viên của các đối 
tượng thuộc tập xấp xỉ dưới mờ và tập xấp xỉ trên 
mờ được xác định [1,7].
( ) ( ) ( ) ( ){ }
/
sup , inf 1 ,PX F F Xy UF U P
x min x max y yµ µ µ µ
∈∈
 
= − 
 
(3)
( ) ( ) ( ) ( ){ }
/
sup ,sup ,F F XPX
F U P y U
x min x min y yµ µ µ µ
∈ ∈
 
=  
 
(4)
với ký hiệu inf X, sup X tương ứng là cận dưới 
đúng và cận trên đúng của tập hợp X. F là các lớp 
tương đương mờ của phân hoạch mờ /U P . Bộ 
,PX PX được gọi là một tập thô mờ.
III. RÚT GỌN THUỘC TÍNH CỦA BẢNG 
QUYẾT ĐỊNH SỬ DỤNG MIỀN DƯƠNG MỜ
A. Rút gọn thuộc tính của bảng quyết định sử dụng 
miền dương mờ dựa trên phân hoạch mờ
Phương pháp này được áp dụng cho lớp bài toán 
có bảng quyết định mờ, giá trị hàm thuộc của các 
đối tượng nằm trong khoảng [0,1]. Trong lý thuyết 
tập thô truyền thống, khái niệm miền dương được 
định nghĩa là giao của tất cả các tập xấp xỉ dưới. 
Với ,P Q A⊆ , hàm thành viên của đối tượng thuộc 
miền dương mờ trong mô hình tập thô mờ được 
xác định [7].
( ) ( ) ( )
/
sup
P PXPOS Q X U Q
x xµ µ
∈
= (5)
Lực lượng của miền dương mờ được tính theo công 
thức [7].
Cao Chính Nghĩa, Vũ Đức Thi, Tân Hạnh, Nguyễn Long Giang
Tạp chí KHOA HỌC CÔNG NGHỆ 
THÔNG TIN VÀ TRUYỀN THÔNG
Số 2 (CS.01) 2016 5
( ) ( ) ( ) ( )P PPOS Q POS Qx Ux xµ µ∈= ∑ (6)
Phương pháp heuristic tìm một tập rút gọn nhỏ 
nhất của bảng quyết định mờ bao gồm các bước: 
Định nghĩa tập rút gọn, định nghĩa độ quan trọng 
của thuộc tính và xây dựng thuật toán heuristic tìm 
một tập rút gọn nhỏ nhất dựa trên độ quan trọng 
của thuộc tính.
Định nghĩa 1. Cho bảng quyết định ( ),DS U C D= È 
và tập thuộc tính P C⊆ . Nếu
1) POS ( ) POS ( )( ) ( )P CD Dx xµ µ= 
2) {p}POS ( ) POS ( ), ( ) ( )P CD Dp P x xµ µ−∀ ∈ ¹
(7)
thì P là một tập rút gọn của C dựa trên miền dương 
mờ.
Định nghĩa 2. Cho bảng quyết định DS (U,C D)= È
, B C⊂ và b C B∈ − . Độ quan trọng của thuộc 
tính b đối với tập thuộc tính B được định nghĩa:
( )
{b}POS ( ) POS ( )
( ) ( )
B BB D DSIG b x xµ µÈ= − (8)
Thuật toán tìm một tập rút gọn nhỏ nhất của bảng 
quyết định sử dụng miền dương mờ ở công thức (6) 
dựa trên phân hoạch mờ được mô tả như sau:
Thuật toán F_RSAR 1 (Fuzzy Rough Set based 
Attribute Reduction).
Đầu vào: Bảng quyết định mờ ( ),DS U C D= È
Đầu ra: Một tập rút gọn nhỏ nhất P.
1. P ← ∅ ; POS ( )| ( ) | 0D xµ ∅ = ;
2. Tính POS ( ) ( )C D xµ ;
3. While POS ( ) POS ( )( ) ( )P CD Dx xµ µ¹ Do
4. Begin
5. For c C P∈ − tính 
( )
{c}POS ( ) POS ( )
( ) ( )
P PP D DSIG c x xµ µÈ= − ;
6. Chọn mc C P∈ − sao cho 
( ) { ( )}P m P
c C P
SIG c Max SIG c
∈ −
=
;
7. { }mP P c← È ;
8. End;
//Loại bỏ các thuộc tính dư thừa trong P nếu có
9. For each a P∈ 
10. Begin
11. Tính 
{ } ( )
( )
P aPOS D
xµ
−
;
12. If 
{ }POS ( ) POS ( )
( ) ( )
P a CD D
x xµ µ
−
= then
 { }P P a= − ;
13. End;
14. Return P ;
Ví dụ 1. Cho bảng quyết định ( )DS C D= È với 
{ , , }, { }C a b c D d= = trong công trình [7] được mô 
tả ở Bảng 1. Giá trị các thuộc tính a, b, c được biểu 
diễn bởi hai tập mờ N và Z tương ứng là (Na, Za), 
(Nb, Zb), ( Nc, Zc) [7].
Bảng I. Bảng quyết định mô tả Ví dụ 1
Đối 
tượng
a b c
DNa Za Nb Zb Nc Zc
c1 c2 c3 c4 c5 c6
1 0,8 0,2 0,6 0,4 1 0 No
2 0,8 0,2 0 0,6 0,2 0,8 Yes
3 0,6 0,4 0,8 0,2 0,6 0,4 No
4 0 0,4 0,6 0,4 0 1 Yes
5 0 0,6 0,6 0,4 0 1 Yes
6 0 0,6 0 1 0 1 No
Áp dụng các bước của Thuật toán F_RSAR 1 tìm 
một tập rút gọn của bảng quyết định, đầu tiên tính 
/ {{1,3,6},{2,4,5}}U D = , POS ( ) ( ) 3.4C D xµ = , tiếp 
theo tính các tập xấp xỉ dưới đối với các thuộc tính 
a, b và c. Xét thuộc tính a, với lớp tương đương 
{1,3,6}X = , {1,3,6} ( )a xµ được tính:
{ } ( ) ( ) ( ) { } ( ){ }1,3,6 1,3,6
/
sup , inf 1 ,F Fa y UF U a
x min x max y yµ µ µ µ
∈∈
 = − 
 
RÚT GỌN THUỘC TÍNH CỦA BẢNG QUYẾT ĐỊNH SỬ DỤNG MIỀN DƯƠNG MỜ
Tạp chí KHOA HỌC CÔNG NGHỆ 
THÔNG TIN VÀ TRUYỀN THÔNG6 Số 2 (CS.01) 2016
Xét lớp tương đương mờ Na trên thuộc tính a:
( ) ( ) { } ( ){ }( )1,3,6, inf 1 ,a aN Ny Umin x max y yµ µ µ∈ −
Đối tượng 1 được tính:
{ }( )0.8, inf 1,0.2,1,0.4,1,1 0.2min =
Vì vậy {1,3,6} (1) 0.2Naµ = . Tương tự với {2,4,5}X =
, tính được {2,4,5} (1) 0.2Naµ = . Theo công thức (5) 
tính được tương tự với ( ) (1) 0.2NaPOS Dµ = , tương 
tự ( ) (1) 0.2ZaPOS Dµ = , vậy ( ) (1) 0.2aPOS Dµ = . Tương 
tự ta có: ( ) ( )2 0.2aPOS Dµ = , ( ) ( )3 0.4aPOS Dµ =
, ( ) ( )4 0.4aPOS Dµ = , ( ) ( )5 0.4aPOS Dµ = , 
( ) ( )6 0.4aPOS Dµ = . Theo công thức (6), hàm thuộc 
( ) ( ) 2aPOS D xµ = . Tính tương tự ( ) ( ) 2.4bPOS D xµ =
, ( ) ( ) 1.6cPOS D xµ = , theo F_RSAR 1 ta có P={b}. 
Áp dụng tiếp các bước của F_RSAR 1 ta có 
P={a,b}.
Thuật toán F_RSAR 1 tìm một tập rút gọn nhỏ 
nhất bảo toàn miền dương mờ, có độ phức tạp tính 
toán là ( )AO U c× , với U số lượng đối tượng, A
là số lượng thuộc tính điều kiện, c là số lượng các 
tập mờ biểu diễn cho mỗi thuộc tính điều kiện [2]. 
Trong khi đó, tập rút gọn tìm được bởi thuật toán 
FuzzyQuickReduct của R. Jensen và các cộng sự 
[7] không bảo toàn miền dương mờ. Tuy nhiên, 
F_RSAR 1 luôn có độ phức tạp là hàm mũ của 
số thuộc tính điều kiện khi tính POS ( ) ( )C D xµ , bằng 
FuzzyQuickReduct trong trường hợp xấu nhất. Do 
vậy, thuật toán F_RSAR 1 chỉ mang tính học thuật, 
không khả thi khi áp dụng thực tế.
B. Rút gọn thuộc tính của bảng quyết định sử dụng 
miền dương mờ dựa trên quan hệ tương tự mờ
Phương pháp sử dụng quan hệ tương tự mờ giải 
quyết bài toán rút gọn trực tiếp thuộc tính trên bảng 
quyết định có miền giá trị số thực. Theo hướng tiếp 
cận này, giá trị hàm thuộc của các đối tượng trên 
các tập mờ được xem là các giá trị cụ thể của ma 
trận quan hệ mờ; ma trận quan hệ mờ được định 
nghĩa mềm dẻo bằng một quan hệ tương tự mờ nào 
đó trên các tập thuộc tính điều kiện. Phương pháp 
tiếp cận này không cần phải tính tất cả các phân 
hoạch mờ, do vậy tránh được độ phức tạp tính toán 
là hàm mũ của thuộc tính điều kiện theo cách tiếp 
cận dựa trên phân hoạch mờ. Do vậy, cách tiếp cận 
này được nghiên cứu sâu rộng, có tính ứng dụng 
thực tế cao.
1. Ma trận quan hệ mờ
Cho { }1,..., nU x x= là tập hữu hạn, khác rỗng n đối 
tượng, R là một quan hệ tương tự mờ trên U . Ma 
trận quan hệ của R trên U , ký hiệu là ( )M R , được 
xác định ( )( ) ,ij i jM R r R x x= = là giá trị của quan 
hệ giữa đối tượng ix và jx , [ ]0,1ijr ∈ với mọi 
i,j=1..n.
Quan hệ tương tự mờ R xác định một phân hoạch mờ 
(fuzzy partition) trên U, ký hiệu { } 1/
n
i R i
U R x
=
=    , 
với i Rx   là một tập mờ, được gọi là lớp tương đương 
mờ. i Rx   được biểu diễn dựa trên lý thuyết tập mờ 
là: 1 2
1 2
...i i ini R
n
r r r
x
x x x
  = + + +    
  
; lực lượng của tập 
mờ i Rx   được tính: 
1
n
i ijR
j
x r
=
=   ∑ .
2. Tập thô mờ định nghĩa theo quan hệ tương tự mờ
Giả sử F là một tập mờ trên U và R là một quan hệ 
tương tự mờ, khi đó tập mờ xấp xỉ dưới ( )R F và 
tập mờ xấp xỉ trên ( )R F của F là các tập mờ và 
hàm thuộc của các đối tượng x U∈
được xác định 
như sau [1, 10]:
( ) ( ) [ ] ( ) ( )( )inf max 1 ,R FR F xy Ux y yµ µ µ∈= − (9)
( ) ( ) [ ] ( ) ( )( )sup ,R FxR F y Ux min y yµ µ µ∈= (10)
Cao Chính Nghĩa, Vũ Đức Thi, Tân Hạnh, Nguyễn Long Giang
Tạp chí KHOA HỌC CÔNG NGHỆ 
THÔNG TIN VÀ TRUYỀN THÔNG
Số 2 (CS.01) 2016 7
Với [ ] ( ) ( ), ( , )R Rx y x y R x yµ µ= = [1,10], cặp 
( ) ( )( ),R F R F được gọi là tập thô mờ. 
Cho bảng quyết định có miền giá trị thuộc tính 
số thực ( ),DS U C D= È với { }1,..., nU u u= , 
{ }1,..., mC c c= . Giả sử một quan hệ tương tự mờ R 
xác định trên miền giá trị của thuộc tính kc C∈ , ký 
hiệu { }( )kR c với k = 1... m. Khi đó R(C) là quan 
hệ R xác định trên tập thuộc tính điều kiện C. Khái 
niệm miền dương POS
c
(D) trong lý thuyết tập thô 
truyền thống được mở rộng thành khái niệm miền 
dương mờ của tập thuộc tính D đối với tập thuộc 
tính C dựa trên quan hệ R, ký hiệu là POSR(C)(D). 
POSR(C)(D) là một tập mờ mà hàm thuộc của các 
đối tượng x U∈ được định nghĩa [10].
( ) ( ) ( ) ( ) ( )( )/
sup
R CPOS D R C XX U D
x xµ µ
∈
= (11)
Lực lượng của miền dương mờ dựa trên quan hệ R 
được xác định [10].
( ) ( ) ( ) ( ) ( ) ( )R C R CPOS D POS Dx Ux xµ µ∈= ∑ (12)
Cho bảng quyết định có miền giá trị thuộc tính số DS 
= (U, C )DS DÈ với P, Q C⊆ và R(P) , R(Q), là quan hệ R 
trên tập thuộc tính P, Q tương ứng. Khi đó ta có R(P 
( ),DS U C D= È Q = R(P) ( ) ) ( )R P R QÈ Ç [5], nghĩa là với mọi ,x y U∈
, ( )( ) ( )( ) ( )( ){ }, min , , ,R P Q x y R P x y R Q x yÈ =
. Giả sử ( )( ) ( )R Pij
n n
M R P r
×
 =    
và 
( )( ) ( )R Qij
n n
M R Q r
×
 =    là các ma trận quan hệ của 
R trên tập thuộc tính P và Q tương ứng, khi đó ma 
trận quan hệ của R trên tập thuộc tính P ( ),DS U C D= È Q là:
( )( ) ( )R P Qij
n n
M R P Q r
È
×
 È =    với
( ) ( ) ( ){ }min ,R P Q R P R Qij ij ijr r rÈ =
(13)
Tiếp theo, chúng tôi đề xuất phương pháp heuristic 
tìm một tập rút gọn nhỏ nhất của bảng quyết định 
có miền giá trị số thực dựa trên quan hệ tương tự 
mờ, bao gồm các bước: định nghĩa tập rút gọn dựa 
trên miền dương mờ, định nghĩa độ quan trọng của 
thuộc tính và xây dựng thuật toán heuristic tìm tập 
rút gọn nhỏ nhất dựa trên tiêu chuẩn độ quan trọng 
của thuộc tính.
Định nghĩa 3. Cho bảng quyết định có miền giá trị 
thuộc tính số ( ),DS U C D= È , quan hệ tương tự mờ 
R và tập thuộc tính P C⊆ . Nếu
1) ( ) ( ) ( ) ( ) ( )( )R P R CPOS D POS Dx xµ µ=
2)
 ( )
( )
( ) ( ) ( )( { }), R P p R CPOS D POS Dp P x xµ µ−∀ ∈ ¹
(14)
thì P là một tập rút gọn nhỏ nhất của C dựa trên 
miền dương mờ của thuộc tính.
Định nghĩa 4. Cho bảng quyết định có miền giá 
trị thuộc tính số ( ),DS U C D= È và quan hệ tương 
tự mờ R xác định trên miền giá trị thuộc tính. Với 
B C⊂ , độ quan trọng của thuộc tính b C B∈ − đối 
với tập thuộc tính B dựa trên quan hệ R được định 
nghĩa:
( )
( {b}) ( )( ) POS ( ) POS ( )
( ) ( )
R B R BR B D DSIG b x xµ µÈ= − (15)
Độ quan trọng của thuộc tính ở công thức (15) 
được sử dụng làm tiêu chuẩn lựa chọn thuộc tính 
cho thuật toán heuristic tìm tập rút gọn nhỏ nhất 
dựa trên miền dương mờ như sau.
Thuật toán F_RSAR 2 (Fuzzy Rough Set based 
Attribute Reduction) 
Đầu vào: Bảng quyết định giá trị thuộc tính số 
( ),DS U C D= È , quan hệ tương tự mờ R.
Đầu ra: Một tập rút gọn nhỏ nhất P.
1. 
( )POS ( )
; | ( ) | 0;
R DP xµ ∅← ∅ =
2. Tính 
( )POS ( )
( )
R C D
xµ ;
3. While 
( ) ( )POS ( ) POS ( )
( ) ( )
R P R CD D
x xµ µ¹ Do
4. Begin
5. For c C P∈ − tính 
RÚT GỌN THUỘC TÍNH CỦA BẢNG QUYẾT ĐỊNH SỬ DỤNG MIỀN DƯƠNG MỜ
Tạp chí KHOA HỌC CÔNG NGHỆ 
THÔNG TIN VÀ TRUYỀN THÔNG8 Số 2 (CS.01) 2016
( )
( {c}) ( )POS ( ) POS ( )
( ) ( )
R P R PP D DSIG c x xµ µÈ= − ;
6. Chọn mc C P∈ − sao cho 
( ) { ( )}P m P
c C P
SIG c Max SIG c
∈ −
= ;
7. { }mP P c← È ;
8. End;
//Loại bỏ các thuộc tính dư thừa trong P nếu có
9. For each a P∈ 
10. Begin
11. Tính ( { }) ( ) ( )R P aPOS D xµ − ;
12. If 
( { }) ( )POS ( ) POS ( )
( ) ( )
R P a R CD D
x xµ µ
−
= 
13. then { }P P a= − ;
14. End;
15. Return P ;
Ví dụ 2. Xét bảng quyết định ( ),DS U C D= È ,
1 2 3 4 5 6{ , , , , , }C c c c c c c= 
cho ở Ví dụ 1 (Bảng 1). 
Định nghĩa quan hệ tương tự mờ { }( ); 1..6kR c k =
trên kc C∈ như sau: 
{ }( ) 1 4* , 0.25( , ) max( ) min( ) max( ) min( )
0,
i j i j
k i j k k k k
x x x x
R c x x c c c c
otherwise
 − −
 − ≤
=  − −


(16)
M(R({C}))được tính thông qua các ma trận 
quan hệ tương tự mờ trên các thuộc tính điều 
kiện { }( )( ); 1..6kM R c k = k = 1 ... 6. Từ đó tính được 
( )POS ( )
( ) .
R C D
xµ
( )
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0
) ,
0
(
1
M R C
 
 
 
 
=  
 
 
  
 
( ) ( ) ( )( ) ( ) ( ) 6R C R CPOS D POS Dx Ux xµ µ∈= =∑
Áp dụng các bước của Thuật toán F_RSAR 2 tìm 
được tập rút gọn nhỏ nhất P = {c4, c1} , tương ứng 
với P = {b, a} của các thuộc tính trước khi mờ hóa.
Thuật toán F_RSAR 2 tìm được một tập rút gọn 
nhỏ nhất dựa trên độ quan trọng của thuộc tính sử 
dụng miền dương mờ. F_RSAR 2 tính toán miền 
dương mờ của thuộc tính thông qua ma trận quan 
hệ mờ, có độ phức tạp tính toán O(|C|3 |U|2) với |U| 
số lượng đối tượng, |C| là số lượng thuộc tính điều 
kiện, tránh được độ phức tạp tính toán là hàm mũ 
của số thuộc tính điều kiện như F_RSAR 1. Dễ thấy 
rằng, tập rút gọn thu được của Thuật toán F_RSAR 
2 cũng bảo toàn miền dương.
C. Thực nghiệm
Để đánh giá khả năng ứng dụng trong thực tế của 
F_RSAR 2, chúng tôi tiến hành cài đặt thuật toán 
F_RSAR 2 và thuật toán GAIN_RATIO_AS_FRS 
(gọi tắt là thuật toán GRAF) tìm tập rút gọn sử 
dụng lượng thông tin tăng thêm (gain ratio) theo 
tiếp cận tập thô mờ trong công trình [3] để so sánh 
với thuật toán đề xuất F_RSAR 2 về thời gian thực 
hiện và số lượng thuộc tính của tập rút gọn thu 
được. Chúng tôi chọn GRAF[3] vì đây là đây là 
công bố mới, có kết quả tốt nhất về phương pháp 
tìm một tập rút gọn tốt nhất đã được công bố cho 
đến thời điểm hiện nay theo tiếp cận tập thô mờ. 
Chúng tôi không cài đặt F_RSAR 1 để so sánh với 
F_RSAR 2 vì sự so sánh này không có ý nghĩa khi 
đã kết luận độ phức tạp tính toán của F_RSAR 1 
là hàm mũ của số thuộc tính điều kiện, không khả 
thi khi ứng dụng thực tế. Để tiến hành thử nghiệm, 
chúng tôi cài đặt cả hai thuật toán bằng ngôn ngữ 
C# trên máy Pentium 2 Duo 2.20 GHz CPU, 2 GB 
RAM, hệ điều hành Windows 7, chạy thử nghiệm 
với 5 bộ số liệu lấy từ kho dữ liệu UCI[8].
Với mỗi bộ số liệu, giả sử |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, t là thời gian thực hiện thuật toán (đơn vị 
là giây), các thuộc tính điều kiện được đánh số là 1, 
2,... , |C|. Kết quả thực hiện được mô tả ở Bảng II.
Cao Chính Nghĩa, Vũ Đức Thi, Tân Hạnh, Nguyễn Long Giang
Tạp chí KHOA HỌC CÔNG NGHỆ 
THÔNG TIN VÀ TRUYỀN THÔNG
Số 2 (CS.01) 2016 9
Bảng II. Kết quả thực hiện 
Thuật toán F_RSAR 2 và GRAF[3]
TT Bộ số liệu |U| |C|
Thuật 
toán 
F_RSAR 2
Thuật 
toán 
GRAF[3]
|R| t |R| t
1 Ionosphere 351 34 12 0,96 12 1,01
2 Wpbc 198 33 15 0,61 17 0,65
3 Wine 178 13 6 0,23 6 0,25
4 Glass 214 9 7 0,40 8 0,45
5 Magic04 19020 10 9 5,96 9 6,25
Kết quả thử nghiệm cho thấy:
- Trên các bộ số liệu Ionosphere.data, Wine.data, 
Magic04.data, tập rút gọn thu được bởi Thuật 
toán F_RSAR 2 và Thuật toán GRAF[3] là như 
nhau. Tuy nhiên, với bộ số liệu Wpbc.data, 
Glass.data, tập rút gọn thu được bởi Thuật toán 
F_RSAR 2 tối thiểu hơn tập rút gọn thu được 
bởi Thuật toán GRAF[3]. 
- Thời gian thực hiện của F_RSAR 2 nhỏ hơn 
GRAF[3], đặc biệt là trên các bộ số liệu lớn 
thì sự chênh lệnh này càng nhiều do thuật toán 
GRAF[3] phải tính logarit trong các công thức 
tính entropy shanon.
IV. KẾT LUẬN
Mô hình tập thô mờ do D. Dubois và các cộng 
sự [1] đề xuất là công cụ hiệu quả để 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ị thuộc tính số thực. Trong 
bài báo này, chúng tôi đề xuất hai phương pháp 
heuristic tìm một tập rút gọn nhỏ nhất của bảng 
quyết định có miền giá trị thuộc tính số thực sử 
dụng miền dương mờ dựa trên phân hoạch mờ và 
quan hệ tương tự mờ. Miền dương mờ trong F_
RSAR 1 được xác định dựa trên phân hoạch mờ ở 
công thức (6). Miền dương mờ trong F_RSAR 2 
được xác định dựa trên ma trận quan hệ tương tự 
mờ ở công thức (12). Thực nghiệm trên các bộ số 
liệu UCI[8] cho thấy, F_RSAR 2 có khả năng ứng 
dụng thực tế. Định hướng nghiên cứu tiếp theo là 
tìm kiếm các độ đo hiệu quả để giải quyết bài toán 
rút gọn thuộc tính theo tiếp cận tập thô mờ.
TÀI LIỆU THAM KHẢO
[1] D. Dubois and H. Prade. Rough fuzzy sets 
and fuzzy rough sets. International Journal of 
General Systems, 17, pp. 191-209, 1990.
[2] C.C. Eric Tsang, Degang Chen, S. Daniel 
Yeung, Xi-Zhao Wang, and W.T. John Lee. 
Attributes Reduction Using Fuzzy Rough Sets, 
IEEE Transactions On Fuzzy Systems, Vol. 16, 
No. 5, October 2008.
[3] Jianhua Dai and Qing Xu. Attribute selection 
based on information gain ratio in fuzzy 
rough set theory with application to tumor 
classification. Applied Soft Computing 13, pp. 
211–221, 2013.
[4] Lotfi Aliasker Zadeh. Fuzzy sets. Information 
and Control, pp. 338-353, 1965.
[5] Qinghua Hu, Daren Yu, Zongxia Xie. 
Information-preserving hybrid data reduction 
based on fuzzy-rough techniques. Pattern 
Recognition Letters 27, 2006, pp. 414-423.
[6] Z. Pawlak. Rough sets. International Journal 
of Computer and Information Sciences, 11(5): 
341-356, 1982.
[7] Richard Jensen and Qiang Shen. Fuzzy–rough 
attribute reduction with application to web 
categorization. Fuzzy Sets and Systems, 
Volume 141, Issue 3, pp. 469-485, 2004.
[8] The UCI machine learning repository, http://
archive.ics.uci.edu/ml/datasets.html.
[9] Xiao Zhang, Changlin Mei, Degang Chen, 
Jinhai Li, Feature selection in mixed data: A 
method using a novel fuzzy rough set-based 
information entropy, PatternRecognition 56, 
pp.1-15, 2016.
[10] Yi Cheng. Forward approximation and 
backward approximation in fuzzy rough sets. 
Neurocomputing, Volume 148, pp. 340-353, 2014.
RÚT GỌN THUỘC TÍNH CỦA BẢNG QUYẾT ĐỊNH SỬ DỤNG MIỀN DƯƠNG MỜ
Tạp chí KHOA HỌC CÔNG NGHỆ 
THÔNG TIN VÀ TRUYỀN THÔNG10 Số 2 (CS.01) 2016
FUZZY POSITIVE REGION BASED 
ATTRIBUTE REDUCTION 
IN DECISION TABLES
Abstract: Traditional rough set based attribute 
reduction methods has performed on the decision 
tables with real value attribute domain needs to be 
discretized data. The discretized data can be lost 
information which will affect the quality of data 
classification. To overcome this drawback, attribute 
reduction performs directly on the decision table 
with real value attribute according to fuzzy rough 
set approach has proved effective. In this paper, 
we propose two attribute reduction methods using 
fuzzy positive region based on fuzzy partition and 
fuzzy similarity relation. Analyzing and evaluating 
for each method which concludes the method using 
fuzzy similarity relation has practical application.
Keywords: Fuzzy rough set, fuzzy decision table, 
fuzzy partition, fuzzy similarity relation, fuzzy 
positive region, attribute reduction, reduct.
Cao Chính Nghĩa, nhận bằng 
Thạc sĩ năm 2006 tại Đại học Công 
nghệ, Đại học Quốc gia Hà Nội. 
Hiện công tác tại Học viện Cảnh 
sát nhân dân, Bộ Công an. Lĩnh 
vực nghiên cứu: cơ sở dữ liệu, khai 
phá dữ liệu và học máy.
Vũ Đức Thi, nhận bằng Tiến sĩ 
năm 1987 tại Học viện Khoa học 
Hungary, học hàm Phó Giáo sư 
năm 1991, Giáo sư năm 2009. 
Hiện đang công tác tại Đại học Sư 
phạm Kỹ thuật Hưng Yên. Lĩnh vực 
nghiên cứu: cơ sở dữ liệu, khai phá 
dữ liệu và học máy.
Nguyễn Long Giang, nhận bằng 
Tiến sĩ năm 2012 tại Viện Công 
nghệ thông tin, Viện Hàn lâm khoa 
học Việt Nam. Hiện đang công tác 
tại Viện Công nghệ thông tin, Viện 
Hàn lâm khoa học Việt Nam. Lĩnh 
vực nghiên cứu: cơ sở dữ liệu, khai 
phá dữ liệu và học máy.
Tân Hạnh, nhận bằng Tiến sĩ 
năm 2009 tại Viện Công nghệ 
Grenoble, Pháp. Hiện đang công 
tác tại Học viện Công nghệ Bưu 
chính Viễn Thông, Thành phố Hồ 
Chí Minh. Lĩnh vực nghiên cứu: 
cơ sở dữ liệu, tìm kiếm thông 
tin, phục hồi thông tin, hệ thống 
phân tán.