TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(33).2009

64

RÚT GỌN TẬP THUỘC TÍNH CỦA HỆ QUYẾT ĐỊNH
DỰA VÀO HỌ PHỦ TẬP THÔ
ON THE ATTRIBUTE REDUCTION OF DECISION SYSTEMS BASED ON
A FAMILY OF COVERING ROUGH SETS

Nguyễn Đức Thuần
Trường Đại học Nha Trang
Nguyễn Xuân Huy
Viện Công nghệ thông tin, Hà Nội

TÓM TẮT
Rút gọn thuộc tính là một bài toán quan trọng trong lý thuyết tập thô. Bài toán tìm rút
gon tối thiểu của một hệ thống thông tin nói chung, và bài toán rút gọn của một hệ thống thông
tin không đầy đủ nói riêng là một bài toán NP-khó. Lý do chính là do sự tổ hợp các thuộc tính.
Trong bài báo này, chúng tôi đề xuất một thuật toán rút gọn tập thuộc tính. Thuật toán là sự
phát triển các kết quả của Cheng Degang và cộng sự trong hệ quyết định phủ nhất quán và
không nhất quán. Độ phức tạp của giải thuật là O(|∆||U|
2
ABSTRACT
). Trong phần cuối bài báo chúng tôi
trình bày một ví dụ minh họa thể hiện hiệu năng của giải thuật.
Attribute reduction is an important issue in the rough set theory. It has been proved that
finding the minimal reduction of an information system is a NP-hard problem, so is finding the
minimal reduction of an incomplete information system. The main reason for this problem is
caused by a combination of attributes. In this paper, we theoretically study an attribute reduction
algorithm. This is based on the results given by Chen Degang and his colleages in the
consistent and inconsistent covering decision system. The time complexity of this algorithm is

j
}. Cov(C) = {C
x
: x∈U} cũng là một phủ của U. Chúng ta gọi là
một phủ suy dẫn của C. Khái niệm phủ suy dẫn của một họ phủ tập thô cũng được định
nghĩa tương tự: Cho ∆ = { C
i
: i=1, m} là một họ phủ của U. Với mọi x∈U, đặt ∆
x
=∩{C
ix
:
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(33).2009

65

C
ix
∈ Cov(C
i
), x ∈C
ix
} thì Cov(∆)= {∆
x
Với mỗi X
⊆
U, xấp xỉ dưới và xấp xỉ trên của X tương ứng với Cov(∆) được định
nghĩa như sau:
: x ∈U} cũng là một phủ của U. Chúng ta gọi nó
là một phủ suy dẫn của ∆.

i
thuộc ∆ được nói là không cần thiết đối với D, ngược lại C
i
được nói là
cần thiết đối với D. Tập P ⊆ ∆ thỏa Cov(P) ≤ U/D, nếu mọi phần tử thuộc P là cần thiết,
có nghĩa là ∀C
i
∈P, Cov(∆-{C
i
Giả sử U là một tập vũ trụ hữu hạn và ∆ = {C
}) ≤ U/D là sai, thì P được gọi là một rút gọn của D. Rút
gọn của một hệ quyết định nhất quán là một tập tối thiểu các thuộc tính điều kiện đảm
bảo chắc chắn các luật quyết định là nhất quán.
i
: i=1, m} là một họ các phủ của U,
C
i
∈∆, D là một thuộc tính quyết định tương ứng với ∆ trên U và d: U → V
d
là hàm
quyết định được định nghĩa d(x) = [x]
D
. (U,∆,D) là một hệ quyết định phủ không nhất
quán khi POS
∆
(D)≠U. Nếu POS
∆
(D)=POS
∆-{Ci}
(D), thì C

TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(33).2009

66

[]
xD
xU
x
x
U
∈
∆∩
=
∆
∑

b. Giả sử Cov(∆)≤ U/D, C
i
∈∆, C
i
là không cần thiết, có nghĩa là Cov(∆-{C
i
( )( )( ) ( )0
xi xj xi xj xi xj
xi U xj U
P Pd d
∈∈
∆ ∩∆ ∪ ∩ ∆ − ∆ =
∑∑
}) ≤ U/D

∆∩
=
∆
∑

b. Nếu đặt Cov(
∆
-{C
i
})=Cov(P)={P
x:
x
∈
U}, Cov(
∆
)={
∆
x
Theo [4](định lý 4.5) P là 1 rút gọn hay C
: x
∈
U}
i
là không cần thiết nếu với mọi cặp x
i
, x
j
∈U
thỏa d(∆
xi

∆
xj
)
⇒
(
∆
xi
∩∆
xj)=
∅
, khi đó ta cũng có (P
xi
∩
P
xj
( ( )( )0
xi xj xi xj
PP∆ ∩∆ ∪ ∩ =
)=
∅
, nên

-Nếu x
i
, x
j
∈
U thỏa d(
∆
xi

x Px
P
∈

∆∩ ∩
−=

∆

∑
∈U, ta có

Chứng minh:
Đây là kết quả trực tiếp từ 3 tính chất của đị nh lý 5.2 trong [4]. Từ điều kiện
∀
x
i
∈
U,
∆
x
i

⊆
[x
i
]
D

⇔

x
x
CI
∈
∆∩
=
∆
∑

Bước 2: If CI = |U| {S là một hệ quyết định nhất quán } thì đến bước 3, ngược
lại đến bước 5.
Bước 3: Tính ∆
x
, d(∆
x
Bước 4: Begin
), ∀x∈U.
for each C
i
( ( )( ) ( )0
xi xj xi xj xi xj
xi U xj U
P Pd d
∈∈
∆ ∩∆ ∪ ∩ ∆ − ∆ =
∑∑
∈∆ do if

{ở đây ∆ - {C
i

Endfor;
}= {Px: x∈U}}
End;
Bước 6: RD= ∆; thuật toán kết thúc.
Thuật toán này có độ phức tạp là đa thức theo |U|. Thật vậy,
Ở bước 1, độ phức tạp tính CI là O(|U|). Bước 2, độ phức tạp là O(1).
Bước 3, độ phức tạp là O(|U|). Bước 4, độ phức tạp tính ∑∑() là O(|U|
2
), do đó độ phức
tạp của bước này là O(|∆||U|
2
Vì vậy, độ phức tạp của cả giải thuật là O(|∆||U|
), vì i=1 |∆|.Bước 5, tương tự độ phức tạp ở bước 3, độ
phức tạp là O(|∆||U|2). Bước 6, độ phức tạp O(1).
2
6. Ví dụ minh họa
) (ở đây chúng ta bỏ qua thời gian tính
∆xi, Pxi, với i= 1 |∆|).
Bước 1:
Giả sử U = {x
1
, x
2
, , x
9
}, ∆ = {C
i
C
, i=1 4}, và
1

2
,x
3
,x
4
,x
5
,x
6
},{x
4
,x
5
,x
6
,x
7
,x
8
,x
9
}},
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(33).2009

68

C
3
={{x
1

2
,x
4
,x
5
},{x
2
,x
3
,x
5
,x
6
},{x
4
,x
5
,x
7
,x
8
},{x
5
,x
6
,x
8
,x
9
U/D={{x

∆ ∩∆ ∪ ∩ ∆ − ∆ =
∑∑
9 ∆=∆ - {C
1
}={C
2
,C
3
,C
4
}. C
1
Bước 3: P=∆ - {C
là không cần thiết, loại bỏ
2
}, Tính P
1
, , P
( ( )( ) ( )0
xi xj xi xj xi xj
xi U xj U
P Pd d
∈∈
∆ ∩∆ ∪ ∩ ∆ − ∆ =
∑∑
9


4
)=∅, nhưng (P
1
∩P
4
)≠∅, |d(∆
1
)-d(∆
4
C
)|≠0)
3
là cần thiết, không thể loại bỏ, ∆={C
3
,C
4
Bước 5:
}.
P= ∆ - {C
4
}, Tính P
1
, , P

9

( ( )( ) ( )0
xi xj xi xj xi xj
xi U xj U
P Pd d

2
TÀI LIỆU THAM KHẢO
). So sánh với các kết quả của thuật
toán của Chen Degang, kết quả chúng tôi có được là hoàn toàn tương thích. Trong thời
gian đến, chúng tôi sẽ cài đặt thử nghiệm trên các tập dữ liệu UCI nhằm có thể đánh giá
chi tiết hơn
[1] William Zhu, Fei-Yue Wang, Reduction and axiomization of covering generalized
rough sets, Information Sciences,152 (2003) 217-230.
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(33).2009

69

[2] Eric C.C.Tsang, Degang Chen, John W.T.Lee, Daniel S.Yeung, On The Upper
Approximations of covering generalized Rough sets, Proceeding of the Third
International Conference on Machine Learning and Cybernetic, Shanghai, 26-29
August 2004.
[3] Guo-Ying Wang, Jun Zhao, Jiu-Jiang An, Yu Wu, Theoretical Study on Attribute
Reduction of Rough set Theory: Comparision of Algebra and Information Views,
Proceedings of Third IEEE International Conference on Cognitive Informatics
(ICCI’ 04), 0-7695-2190-8/04.
[4] Cheng Degang, Wang Changzhong, Hu Quinghua, A new approach to attribute
reduction of consistent and inconsistent covering rough sets, Information
Sciences,177 (2007) 3500- 3518.