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
O(|∆||U|2
1. Giới thiệu
). At the end of this paper an illustrative example is also provided to show the
application potential of the algorithm.
Bài toán rút gọn tập 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 này thuộc lớp NP-khó [3].Vì vậy, đôi khi người ta chỉ tìm một rút gọn (nhằm
thu gọn kích thước của hệ thống thông tin). Trong bài báo này, chúng tôi đề xuất một
thuật toán tìm một rút gọn tối thiểu tập thuộc tính ứng với một họ phủ quyết định tập
thô. Độ phức tạp của thuật toán là O(|∆||U|2
2. Các khái niệm cơ sở
), tương đương với các thuật toán tìm một rút
gọn tập thuộc tính trong lý thuyết tập thô cổ điển.
Phủ tập thô và suy dẫn phủ
Cho U là một tập vũ trụ, C là một họ các tập con khác rỗng của U. C được gọi là
một phủ của U nếu ∪C = U.Với C = {C1, C2,..,Cn} là một phủ của U. Với mọi x∈U, đặt
Cx=∩{Cj: Cj ∈ C, x∈Cj}. Cov(C) = {Cx: 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 ∆ = { Ci: i=1,..m} là một họ phủ của U. Với mọi x∈U, đặt ∆x=∩{Cix:
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(33).2009
65
Cix ∈ Cov(Ci), x ∈Cix } 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 ∆.
( ) { : },
xx
XX∆ =∪∆ ∆ ⊆
() { : }
xx
XX∆ =∪ ∆ ∆ ∩ ≠∅
3. Rút gọn tập thuộc tính của các hệ thống quyết định nhất quán và không nhất
quán
Gọi ∆ = { Ci: i=1,..m} là một họ phủ của U, D là thuộc tính quyết định, U/D là
một phân hoạch trên U. Nếu ∀x∈U, ∃Dj ∈U/D mà ∆x ⊆ Dj
, thì hệ quyết định (U,∆,D)
được gọi là hệ quyết định nhất quán và ký hiệu Cov(∆)≤ U/D. Ngược lại, (U,∆,D) được
gọi là hệ quyết định không nhất quán. Miền dương của D ứng với ∆ được định nghĩa:
Một phủ không cần thiết của một họ phủ ứng với hệ quyết định nhất quán, không nhất
quán lần lượt cũng được xác định:
Cho (U,∆,D={d}) là một hệ quyết định nhất quán. Với Ci∈∆, nếu Cov(∆-{Ci})
≤ U/D, thì Ci thuộc ∆ được nói là không cần thiết đối với D, ngược lại Ci đượ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à ∀Ci ∈P, Cov(∆-{Ci
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,
Ci ∈∆, D là một thuộc tính quyết định tương ứng với ∆ trên U và d: U → Vd 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ì Ci là quan hệ trong ∆ không
cần thiết đối với D. Ngược lại, Ci
4. Thuật toán rút gọn tập thuộc tính ứng với họ phủ tập thô
là quan hệ cần thiết đối với D.
Nhận xét 3.1. Từ định nghĩa của đại lượng ∆x. Với D = {d}, d(x) là một hàm
quyết định d: U → Vd xác định từ tập vũ trụ U vào tập giá trị Vd
- Với mỗi xi, xj ∈U, nếu ∆xi ⊆ ∆xj, thì d(xi) = d([xi]
. Ta có các kết quả sau:
D) = d(∆xi) = d(∆xj) = d(xj) =
d([xj]D
- Nếu d(∆xi) ≠ d(∆xj), thì ∆xi ∩ ∆xj = ∅, có nghĩa là ∆xi ⊄ ∆xj và ∆xj ⊄ ∆xi.
).
Từ nhận xét trên và các kết quả trong [4], chúng tôi chứng minh được 2 định lý sau:
Định lý 3.1. Cho (U,∆,D={d}) là một hệ quyết định phủ, P ⊆ ∆, chúng ta có:
a. (U,∆,D={d}) là một hệ quyết định phủ nhất quán khi thỏa:
/
() ()
XUD
POS D X
∆
∈
= ∆
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(33).2009
66
[]
xD
xU x
xU
∈
∆∩ =
∆
∑
b. Giả sử Cov(∆)≤ U/D, Ci ∈∆, Ci là không cần thiết, có nghĩa là Cov(∆-{Ci
( )( )( ) ( )0
xi xj xi xj xi xj
xi U xj U
P Pd d
∈∈
∆ ∩∆ ∪ ∩ ∆ − ∆ =
∑∑
}) ≤ U/D
khi và chỉ khi
ở đây, Cov(∆-{Ci})={Px: x∈U}, Cov(∆)={∆x
Chứng minh:
: x ∈U}
a. Từ định nghĩa của một hệ quyết định nhất quán, rõ ràng với mỗi x
∈
U,
∆
x
⊆
[x]D
luôn
luôn đúng, vì vậy chúng ta có: có nghĩa là:
[]
xD
xU x
xU
∈
∆∩ =
∆
∑
b. Nếu đặt Cov(
∆
-{Ci})=Cov(P)={Px: 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 xi, xj∈U
thỏa d(∆xi)≠ d(∆xj) ta có quan hệ giữa xi, xj ứng với ∆ tương đương với quan hệ của
chúng đối với P, nghĩa là ∆xi ⊄ ∆xj and ∆xj ⊄ ∆xi ⇔ Pxi⊄ Pxj, Pxj ⊄ Pxi
Theo nhận xét 3.1, d(
∆
.
xi)
≠
d(
∆
xj)
⇒
(
∆
xi
∩∆
xj)=
∅
, khi đó ta cũng có (Pxi
∩
Pxj
( ( )( )0
xi xj xi xj
PP∆ ∩∆ ∪ ∩ =
)=
∅
, nên
-Nếu xi, xj
∈
U thỏa d(
∆
xi)=d(
∆
xj
( ) ( )0d xi d xj∆−∆ =
)
⇒
. Nói khác hơn, khi Ci
( )( )( ) ( )0
xi xj xi xj xi xj
xi U xj U
P Pd d
∈∈
∆ ∩∆ ∪ ∩ ∆ − ∆ =
∑∑
không
cần thiết ta có:
(đ.p.cm)
Định lý 3.2. Cho (U,∆,D={d}) là một hệ quyết định không nhất quán. P ⊆ ∆,
POSP(D)= POS∆(D) nếu và chỉ nếu∀xi
[] [] 0
xi i D xi i D
xi U xi 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
∀
xi
∈
U,
∆
xi
⊆
[xi]D
⇔
Pxi
⊆
[xi]D có nghĩa là
∀
xi
[] []
DD
xi x xi Pxi x Pxi∆∩=∆⇔∩=
∈
U, . Nói khác
hơn ta có điều phải chứng minh.
5. Thuật toán rút gọn thuộc tính của họ quyết định phủ tập thô
Input: Cho hệ quyết định phủ S = (U,∆,D={d}).
Output: Một rút gọn thuộc tính RD of ∆.
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(33).2009
67
Method:
Bước 1: Tính
[]
xD
xU 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 Ci
( ( )( ) ( )0
xi xj xi xj xi xj
xi U xj U
P Pd d
∈∈
∆ ∩∆ ∪ ∩ ∆ − ∆ =
∑∑
∈∆ do if
{ở đây ∆ - {Ci }= {Px: x∈U}} then ∆:= ∆ - {Ci
Endfor;
};
goto Bước 6.
End;
Bước 5: Begin
for each Ci
[] [] 0
xi i D xi i D
xi U xi xi
x Px
P
∈

∆∩ ∩
−=

∆

∑
∈∆ do if
then ∆:= ∆ - {Ci };{ở đây ∆ - {Ci
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 = {x1, x2,.., x9}, ∆ = {Ci
C
, i=1..4}, và
1={{x1,x2,x4,x5,x7,x8},{x2,x3,x5,x6,x8,x9
C
}},
2={{x1,x2,x3,x4,x5,x6},{x4,x5,x6,x7,x8,x9}},
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 4(33).2009
68
C3={{x1,x2,x3},{x4,x5,x6,x7,x8,x9},{x5,x6,x8,x9
C
}},
4={{x1,x2,x4,x5},{x2,x3,x5,x6},{x4,x5,x7,x8},{x5,x6,x8,x9
U/D={{x
}}
1,x2,x3}, {x4,x5,x6}, {x7,x8,x9
CI = 9 ⇒ S là một hệ nhất quán.
}}
Bước 2: P - {C1}, Tính P1,.., P
( ( )( ) ( )0
xi xj xi xj xi xj
xi U xj U
P Pd d
∈∈
∆ ∩∆ ∪ ∩ ∆ − ∆ =
∑∑
9
∆=∆ - {C1}={C2,C3,C4}. C1
Bước 3: P=∆ - {C
là không cần thiết, loại bỏ
2}, Tính P1,.., P
( ( )( ) ( )0
xi xj xi xj xi xj
xi U xj U
P Pd d
∈∈
∆ ∩∆ ∪ ∩ ∆ − ∆ =
∑∑
9
∆=∆ - {C2}= {C3,C4}. C2
Bước 4:
là không cần thiết, loại bỏ
P= ∆ - {C3}, Tính P1,.., P
9
( ( )( ) ( )0
xi xj xi xj xi xj
xi U xj U
P Pd d
∈∈
∆ ∩∆ ∪ ∩ ∆ − ∆ ≠
∑∑
(bởi vì chúng ta có thể thấy:(∆1∩∆4)=∅, nhưng (P1∩P4)≠∅, |d(∆1)-d(∆4
C
)|≠0)
3 là cần thiết, không thể loại bỏ, ∆={C3,C4
Bước 5:
}.
P= ∆ - {C4}, Tính P1,.., P
9
( ( )( ) ( )0
xi xj xi xj xi xj
xi U xj U
P Pd d
∈∈
∆ ∩∆ ∪ ∩ ∆ − ∆ ≠
∑∑
(bởi vì chúng ta có thể thấy:(∆6∩∆7)=∅, nhưng (P6∩P7)≠∅, |d(∆6)-d(∆7
C
)|≠0)
4 là cần thiết, không thể loại bỏ, ∆={C3,C4
Bước 6: RD= {C3,C4} là một rút gọn họ phủ tập thô. Ứng với rút gọn này 2 thuộc tính
tương ứng với C1, C2 bị loại bỏ.
}.
7. Kết luận
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 dựa
vào một họ phủ quyết định tập thô. Nó dựa trên các một số kết quả của Chen Degang và
các cộng sự. Độ phức tạp của giải thuật là O(|∆||U|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.