Một phương pháp mới rút gọn thuộc tính trong bảng quyết định không đầy đủ sử dụng metric

OV ER (U), quan hằ thự tỹ bở phên (COV ER (U) ,≺) ữủc ành nghắa nhữ sau.
ffiành nghắa 2.1. [10]. Cho hằ thổng tin khổng Ưy ừ IS = (U,A, V, f) vợi P,Q ⊆ A. Ta
nõi:
1) Phừ U/SIM (P ) v  phừ U/SIM (Q) l  nhữ nhau (viát U/SIM (P ) = U/SIM (Q)),
khi v  ch¿ khi ∀u ∈ U, SP (u) = SQ (u).
2) U/SIM (P ) màn hỡn U/SIM (Q) (viát U/SIM (P ) ≺ U/SIM (Q)) khi v  ch¿ khi
∀ui ∈ U, SP (ui) ⊆ SQ (ui).
Trản (COV ER (U) ,≺), phƯn tỷ nhọ nhĐt gồi l  phừ rới rÔc ω = {SA (u) = {u} /u ∈ U} v 
phƯn tỷ lợn nhĐt gồi l  phừ mởt khối δ = {SA (u) = {U} /u ∈ U}.
Tẵnh chĐt 2.1. [10]. Cho hằ thổng tin khổng Ưy ừ IS = (U,A, V, f)
1) Náu P ⊆ Q ⊆ A thẳ U/SIM (Q) ≺ U/SIM (P ).
2) Náu P,Q ⊆ A thẳ SP∪Q (u) = SP (u) ∩ SQ (u) vợi ∀u ∈ U .
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. Nhữ vêy, bÊng quyát ành l  hằ thổng tin DS = (U,C ∪D,V, f) trong õ C ∩D = ∅. Vợi
a ∈ C náu Va chựa giĂ trà rộng (biºu diạn l  '*') thẳ DS ữủc gồi l  khổng Ưy ừ, ngữủc lÔi
DS ữủc gồi l  Ưy ừ. Khổng mĐt tẵnh chĐt tờng quĂt, giÊ thiát D ch¿ gỗm mởt thuởc tẵnh
quyát ành duy nhĐt d v  ∗ /∈ Vd.
3. LIANG ENTROPY Mé RậNG V€ CC TNH CH‡T
3.1. Liang entropy mð rởng cừa têp thuởc tẵnh
ffiành nghắa 3.1. Cho hằ thổng tin khổng Ưy ừ IIS = (U,A, V, f), P ⊆ A v  U/SIM (P ) ={
SP (u1) , SP (u2) , ..., SP
(
u|U |
)}
. Liang entropy mð rởng cừa P l  Ôi lữủng IE (P ), xĂc ành
nhữ sau
IE(P ) =
|U |∑
i=1
1
|U |
(
1− |SP (ui)||U |
)
trong õ |SP (u)| ch¿ lỹc lữủng têp SP (u). Náu U/SIM (P ) = ω thẳ IE(P ) Ôt giĂ trà lợn
nhĐt l  1 − 1/ |U |. Náu U/SIM (P ) = δ thẳ IE(P ) Ôt giĂ trà nhọ nhĐt l  0. Nhữ vêy
0 ≤ IE (P ) ≤ 1− 1/ |U |.
132 NGUY™N LONG GIANG, NGUY™N THANH TềNG, Vễ ffiÙC THI
Mằnh ã 3.1. Cho hằ thổng tin Ưy ừ IS = (U,A, V, f), P ⊆ A vợi P ⊆ A v  U/P =
{P1, P2, ..., Pm}. Ta cõ
IE(P ) =
|U |∑
i=1
1
|U |
(
1− |SP (ui)||U |
)
=
m∑
i=1
|Pi|
|U |
(
1− |Pi||U |
)
= E(P )
vợi E(P ) l  Liang entropy trong [6].
Chựng minh. GiÊ sỷ Pi = {ui1, ui2, ..., uisi} vợi |Pi| = si v 
m∑
i=1
si = |U |. Ta cõ:
Pi = SP (ui1) = SP (ui2) = ... = SP (uisi) , |Pi| = |SP (ui1)| = |SP (ui2)| = ... = |SP (uisi)| = si
,
|Pi|
|U |
(
1− |Pi||U |
)
=
1
|U |
(
|Pi| − |Pi| |Pi||U |
)
=
1
|U |
(
1− |SP (ui1)||U | + 1−
|SP (ui2)|
|U | + ...+ 1−
|SP (uisi)|
|U |
)
E(P ) =
m∑
i=1
|Pi|
|U |
(
1− |Pi||U |
)
=
m∑
i=1
si∑
k=1
1
|U |
(
1− |SP (uik) ||U |
)
=
|U |∑
i=1
1
|U |
(
1− |SP (ui) ||U |
)
= IE(P )

ffiành nghắa 3.2. Liang entropy mð rởng cừa P ∪Q l  Ôi lữủng IE (P ∪Q), xĂc ành nhữ
sau
IE(P ∪Q) =
|U |∑
i=1
1
|U |
(
1− |SP∪Q(ui)||U |
)
=
|U |∑
i=1
1
|U |
(
1− |SP (ui) ∩ SQ(ui)||U |
)
3.2. Liang entropy mð rởng cõ iãu kiằn
ffiành nghắa 3.3. Cho hằ thổng tin khổng Ưy ừ IIS = (U,A, V, f) v  P,Q ⊆ A. GiÊ sỷ
U/SIM (P ) =
{
SP (u1) , SP (u2) , ..., SP
(
u|U |
)}
v 
U/SIM (Q) =
{
SQ (u1) , SQ (u2) , ..., SQ
(
u|U |
)}
.
Liang entropy mð rởng cõ iãu kiằn cừa Q khi  biát P ữủc ành nghắa bði
IE(Q |P ) = 1|U |
|U |∑
i=1
( |SP (ui)| − |SQ(ui) ∩ SP (ui)|
|U |
)
MậT PHìèNG PHP MẻI RểT GÅN THUậC TNH TRONG BƒNG QUY˜T ffiÀNH 133
Mằnh ã 3.2. Cho hằ thổng tin Ưy ừ IS = (U,A, V, f), P ⊆ A vợi P,Q ⊆ A. GiÊ sỷ
U/P = {P1, P2, ..., Pm}, U/Q = {Q1, Q2, ..., Qn}. Ta cõ
IE(Q |P ) = 1|U |
|U |∑
i=1
( |SP (ui)| − |SQ(ui) ∩ SP (ui)|
|U |
)
=
n∑
i=1
m∑
j=1
|Qi ∩ Pj |
|U |
∣∣∣Qci − P cj ∣∣∣
|U | = E(Q |P )
vợi Qci = U −Qi, P cj = U − Pj v  E (Q |P ) l  Liang entropy cõ iãu kiằn trong [6].
Chựng minh. GiÊ sỷ Qi ∩ Pj =
{
ui1, ui2, ..., uisj
}
vợi |Qi ∩ Pj | = sj v  |Qi| = ti, khi õ
m∑
j=1
sj = ti v 
n∑
i=1
ti = |U |. Ta cõ
Qi ∩ Pj = SQ (ui1) ∩ SP (ui1) = SQ (ui2) ∩ SP (ui2) = ... = SQ
(
uisj
) ∩ SP (uisj)
|Qi ∩ Pj | = |SQ (ui1) ∩ SP (ui1)| = |SQ (ui2) ∩ SP (ui2)| = ...
=
∣∣SQ (uisj) ∩ SP (uisj)∣∣ = sj
|Qi ∩ Pj |
∣∣∣Qci − P cj ∣∣∣ = |Qi ∩ Pj | |Qci ∩ Pj | = |Qi ∩ Pj | |Pj − (Qi ∩ Pj)|
= |SP (ui1)− (SQ (ui1) ∩ SP (ui1))|+ |SP (ui2)− (SQ (ui2) ∩ SP (ui2))|+ ...+
+
∣∣SP (uisi)− (SQ (uisj) ∩ SP (uisj))∣∣
=
sj∑
k=1
|SP (uik)− (SQ (uik) ∩ SP (uik))| =
sj∑
k=1
|SP (uik)| − |SQ (uik) ∩ SP (uik)|.
Do õ
m∑
j=1
|Qi ∩ Pj |
∣∣∣Qci − P cj ∣∣∣ = m∑
j=1
sj∑
k=1
|SP (uik)| − |SQ (uik) ∩ SP (uik)|
=
ti∑
k=1
|SP (uik)| − |SQ (uik) ∩ SP (uik)|
⇔
n∑
i=1
m∑
j=1
|Qi ∩ Pj |
∣∣∣Qci − P cj ∣∣∣ = n∑
i=1
ti∑
k=1
|SP (uik)| − |SQ (uik) ∩ SP (uik)|
=
|U |∑
i=1
|SP (ui)| − |SQ (ui) ∩ SP (ui)|
⇔ IE(Q |P ) = 1|U |
|U |∑
i=1
( |SP (ui)|−|SQ(ui)∩SP (ui)|
|U |
)
=
n∑
i=1
m∑
j=1
|Qi∩Pj |
|U |
|Qci−P cj |
|U | = E(Q |P )

3.3. Mởt số tẵnh chĐt cừa Liang entropy mð rởng
Mằnh ã 3.3. Cho hằ thổng tin Ưy ừ IIS = (U,A, V, f) vợi P,Q,R ⊆ A.
a) Náu U/SIM (P ) ≺ U/SIM (Q) thẳ IE (P ) ≥ IE (Q) v  IE (P ) = IE (Q) khi v  ch¿
khi U/SIM (P ) = U/SIM (Q).
b) Náu U/SIM (P ) ≺ U/SIM (Q) thẳ IE (P ∪Q) = IE (P ).
134 NGUY™N LONG GIANG, NGUY™N THANH TềNG, Vễ ffiÙC THI
c) IE (P ∪Q) ≥ IE (P ) v  IE (P ∪Q) ≥ IE (Q).
d) IE (P ∪Q) = IE (P ) + IE (Q |P ) = IE (P ) + IE (P |Q).
e) 0 ≤ IE (Q |P ) ≤ 1− 1/ |U |. IE (Q |P ) = 0 khi v  ch¿ khi U/SIM (P ) ≺U/SIM (Q),
IE (Q |P ) = 1− 1/ |U | khi v  ch¿ khi U/SIM (P ) = δ v  U/SIM (Q) = ω.
f) Náu U/SIM (P ) ≺U/SIM (Q) thẳ IE (R |Q) ≥ IE (R |P ).
g) Náu U/SIM (P ) ≺U/SIM (Q) thẳ IE (P |R ) ≥ IE (Q |R ).
Chựng minh. a) ffiữủc suy ra tứ ffiành nghắa 3.1 v  ffiành nghắa 2.1.
b) ffiữủc suy ra tứ ffiành nghắa 3.1, ffiành nghắa 3.2, ffiành nghắa 2.1 v  Tẵnh chĐt 2.1.
c) ffiữủc suy ra tứ a).
d) Tứ ffiành nghắa 3.1, ffiành nghắa 3.2 v  ffiành nghắa 3.3 ta cõ
IE(Q |P ) = 1|U |
|U |∑
i=1
|SP (ui)|−|SP (ui)∩SQ(ui)|
|U | = 1− 1|U |
|U |∑
i=1
|SP (ui)∩SQ(ui)|
|U | −1+ 1|U |
|U |∑
i=1
|SP (ui)|
|U |
= 1|U |
|U |∑
i=1
1− |SP (ui)∩SQ(ui)||U | − 1|U |
|U |∑
i=1
1− |SP (ui)||U | = IE(P ∪Q)− IE (P )
Do õ: IE (P ∪Q) = IE (P ) + IE (P |Q). Do tẵnh chĐt ối xựng cừa IE (P ∪Q) nản
ta cụng cõ IE (P ∪Q) = IE (Q) + IE (P |Q).
e) Hiºn nhiản IE (Q |P ) ≥ 0. Theo phƯn d), IE (Q |P ) = IE (P ∪Q) − IE (P ) nản
IE (Q |P ) = 0 ⇔ IE (P ∪Q) = IE (P ). Vẳ U/SIM (P ∪Q) ≺ U/SIM (P ) nản theo
phƯn a) ta cõ:
IE (P ∪Q) = IE (P )⇔ U/SIM (P ∪Q) = U/SIM (P )⇔ U/SIM (P ) ≺U/SIM (Q)
M°t khĂc, theo phƯn d) v  ffiành nghắa 3.1 ta cõ
IE (Q |P ) = IE (P ∪Q) − IE (P ) , IE (P ∪Q) ≤ 1 − 1/ |U | , IE (P ) ≥ 0 nản suy ra
IE (Q |P ) ≤ 1− 1/ |U |.
DĐu ‘ =  xÊy ra khi v  ch¿ khi IE (P ) = 0 ∧ IE (P ∪Q) = 1 − 1/ |U |, nghắa l 
U/SIM (P ) = δ v  U/SIM (P ∪Q) = ω. ffiiãu n y tữỡng ữỡng vợi U/SIM (P ) = δ
v  U/SIM (Q) = ω.
f) GiÊ sỷ U/SIM (R) =
{
SR (u1) , SR (u2) , ..., SR
(
u|U |
)}
. Tứ U/SIM (P ) ≺U/SIM (Q)
ta cõ SP (ui) ⊆ SQ (ui) vợi mồi ui ∈ U, i = 1.. |U | v 
(SQ (ui)− SP (ui)) ∩ SR (ui) ⊆ SQ (ui)− SP (ui)
⇔ (SQ (ui) ∩ SR (ui))− (SP (ui) ∩ SR (ui)) ⊆ SQ (ui)− SP (ui)
⇔ |(SQ (ui) ∩ SR (ui))− (SP (ui) ∩ SR (ui))| ≤ |SQ (ui)− SP (ui)| (3.1)
MậT PHìèNG PHP MẻI RểT GÅN THUậC TNH TRONG BƒNG QUY˜T ffiÀNH 135
Do SP (ui) ⊆ SQ (ui) nản SP (ui) ∩ SR (ui) ⊆ SQ (ui) ∩ SR (ui) v  (3.1) tữỡng ữỡng:
|SQ (ui) ∩ SR (ui)| − |SP (ui) ∩ SR (ui)| ≤ |SQ (ui)| − |SP (ui)|
⇔ |SQ (ui)| − |SQ (ui) ∩ SR (ui)| ≥ |SP (ui)| − |SP (ui) ∩ SR (ui)|
⇔ 1|U |
n∑
i=1
|SQ(ui)|−|SQ(ui)∩SR(ui)|
|U | ≥ 1|U |
n∑
i=1
|SP (ui)|−|SP (ui)∩SR(ui)|
|U | ⇔ IE (R |Q) ≥ IE (R |P )
g) Tứ U/SIM (P ) ≺U/SIM (Q) nản vợi mồi ui ∈ U, i = 1.. |U | ta cõ SP (ui) ⊆ SQ (ui).
GiÊ sỷ U/SIM (R) =
{
SR (u1) , SR (u2) , ..., SR
(
u|U |
)}
, khi õ:
SP (ui) ∩ SR (ui) ⊆ SQ (ui) ∩ SR (ui) ⇔ |SP (ui) ∩ SR (ui)| ≤ |SQ (ui) ∩ SR (ui)|
⇔ |SR (ui)| − |SP (ui) ∩ SR (ui)| ≥ |SR (ui)| − |SQ (ui) ∩ SR (ui)|
⇔ 1|U |
|U |∑
i=1
|SR(ui)|−|SP (ui)∩SR(ui)|
|U | ≥ 1|U |
|U |∑
i=1
|SR(ui)|−|SQ(ui)∩SR(ui)|
|U | ⇔ IE(P |R ) ≥ IE(Q |R )

4. METRIC TR–N HÅ CC PHế V€ CC TNH CH‡T
Mởt metric trản têp hủp 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, y) ≥ 0, iãu kiằn d (x, y) = 0 khi v  ch¿ khi x = y.
P(2) d (x, y) = d (y, x).
P(3) d (x, y) + d (y, z) ≥ d (x, z).
ffiiãu kiằn P (3) ữủc gồi l  tiản ã bĐt ¯ng thực tam giĂc
Dỹa trản kát quÊ trong [11], chúng tổi ã xuĐt mởt metric trản hồ cĂc phừ trong hằ thổng
tin khổng Ưy ừ sỷ dửng Liang entropy mð rởng v  nghiản cựu mởt số tẵnh chĐt cừa chúng.
Bờ ã 4.1. Cho hằ thổng tin khởng Ưy ừ IIS = (U,A, V, f). Vợi mồi P,Q,R ⊆ A.
a) IE (P |R ) + IE (Q |P ∪R ) = IE (P ∪Q |R ).
b) IE (Q |P ) + IE (P |R ) ≥ IE (Q |R ).
Chựng minh. GiÊ sỷ:
U/SIM (P ) =
{
SP (u1) , SP (u2) , ..., SP
(
u|U |
)}
U/SIM (Q) =
{
SQ (u1) , SQ (u2) , ..., SQ
(
u|U |
)}
U/SIM (R) =
{
SR (u1) , SR (u2) , ..., SR
(
u|U |
)}
136 NGUY™N LONG GIANG, NGUY™N THANH TềNG, Vễ ffiÙC THI
a) Thêt vêy IE (P |R ) + IE (Q |P ∪R ) =.
= 1|U |
|U |∑
i=1
|SR(ui)|−|SP (ui)∩SR(ui)|+|SP∪R(ui)|−|SP∪R(ui)∩SQ(ui)|
|U |
= 1|U |
|U |∑
i=1
|SR(ui)|−|SP∪R(ui)|+|SP∪R(ui)|−|SP∪R(ui)∩SQ(ui)|
|U |
= 1|U |
|U |∑
i=1
|SR(ui)|−|SP (ui)∩SQ(ui)∩SR(ui)|
|U |
= 1|U |
|U |∑
i=1
|SR(ui)|−|SR(ui)∩SP∪Q(ui)|
|U | = IE (P ∪Q |R )
b) Do U/SIM (P ∪R) ≺U/SIM (P ) , U/SIM (P ∪Q) ≺U/SIM (Q) nản Ăp dửng Mằnh
ã 3.3 phƯn a) ta cõ IE (Q |P ) ≥ IE (Q |P ∪R) , IE (P ∪Q |R ) ≥ IE (Q |R ). Sỷ
dửng kát quÊ ð phƯn a) ta cõ IE (Q |P ) + IE (P |R ) ≥ IE (Q |P ∪R ) + IE (P |R ) =
IE (P ∪Q |R ) ≥ IE (Q |R ).

ffiành lỵ 4.1. Cho hằ thổng tin khổng Ưy ừ IIS = (U,A, V, f). Vợi P,Q ⊆ A giÊ sỷ
K (P ) = U/SIM (P ) ,K (Q) = U/SIM (Q). Khi õ vợi mồi K (P ) ,K (Q) ∈ COV ER (U),
Ănh xÔ dE : COV ER (U)ì COV ER (U)→ [0,∞) xĂc ành bði
dE (K (P ) ,K (Q)) = IE (P |Q) + IE (Q |P )
l  mởt metric trản têp COV ER(U).
Chựng minh. (P1) Theo Mằnh ã 3.3 phƯn e), dE (K (P ) ,K (Q)) ≥ 0 vợi mồiK (P ) ,K (Q) ∈
COV ER (U) , dE (K (P ) ,K (Q)) = 0⇔ (IE (Q |P ) = 0) ∧ (IE (P |Q) = 0).
⇔ (U/SIM (P ) ≺ U/SIM (Q)) ∧ (U/SIM (Q) ≺ U/SIM (P ))⇔ K (P ) = K (Q)
(P2) Tứ ành nghắa cừa dE suy ra dE (K (P ) ,K (Q)) = dE (K (Q) ,K (P )) vợi mồi K (P ),
K (Q) ∈ COV ER (U).
(P3) Vợi mồi K (P ) ,K (Q) ,K (R) ∈ COV ER (U), Ăp dửng Bờ ã 4.1 phƯn b)
IE (Q |P ) + IE (P |R ) ≥ IE (Q |R ) (4.1)
IE (R |P ) + IE (P |Q) ≥ IE (R |Q) (4.2)
Cởng (4.1) vợi (4.2) theo vá vợi vá thu ữủc:
dE (K (Q) ,K (P )) + dE (K (P ) ,K (R)) ≥ dE (K (Q) ,K (R))
Tứ (P1), (P2), (P3) kát luên dE (K (P ) ,K (Q)) l  mởt metric trản têp COV ER(U)

MậT PHìèNG PHP MẻI RểT GÅN THUậC TNH TRONG BƒNG QUY˜T ffiÀNH 137
Mằnh ã 4.1. Cho hằ thổng tin Ưy ừ IIS = (U,A, V, f) vợi P ⊆ A. Ta cõ
dE (K (P ) ,K (A)) =
1
|U |
|U |∑
i=1
|SP (ui)| − |SA(ui)|
|U |
Chựng minh. Tứ giÊ thiát P ⊆ A suy ra U/SIM (A) ≺ U/SIM (P ), theo Mằnh ã 3.3
phƯn e) ta cõ IE (P |A) = 0. M°t khĂc, cụng tứ P ⊆ A ta cõ SA (ui) ⊆ SP (ui), hay
SP (ui) ∩ SA (ui) = SA (ui) vợi mồi ui ∈ U, i = 1.. |U |. Do õ
dE (K (P ) ,K (A)) = IE (P |A) + IE (A |P ) = IE (A |P )
= 1|U |
|U |∑
i=1
|SP (ui)|−|SP (ui)∩SA(ui)|
|U | =
1
|U |
|U |∑
i=1
|SP (ui)|−|SA(ui)|
|U |

Mằnh ã 4.2. Cho bÊng quyát ành khổng Ưy ừ IDS = (U,C ∪D,V, f). Náu B ⊆ C thẳ
dE (K (B) ,K (B ∪D)) ≥ dE (K (C) ,K (C ∪D))
Chựng minh. X²t bÊng quyát ành khổng Ưy ừ IDS = (U,C ∪D,V, f) , U = {u1, u2, ..., un}
v  B ⊆ C. Vợi mồi ui ∈ U, i = 1..n ta cõ SC (ui) ⊆ SB (ui), do õ:
(SB (ui)− SC (ui)) ∩ SD (ui) ⊆ SB (ui)− SC (ui)
⇔ (SB (ui) ∩ SD (ui))− (SC (ui) ∩ SD (ui)) ⊆ SB (ui)− SC (ui)
⇔ |(SB (ui) ∩ SD (ui))− (SC (ui) ∩ SD (ui))| ≤ |SB (ui)− SC (ui)| (4.3)
Do SC (ui) ⊆ SB (ui) nản SC (ui)∩SD (ui) ⊆ SB (ui)∩SD (ui) v  (4.3) tữỡng ữỡng vợi:
|SB (ui) ∩ SD (ui)| − |SC (ui) ∩ SD (ui)| ≤ |SB (ui)| − |SC (ui)|
⇔ |SB (ui)| − |SB (ui) ∩ SD (ui)| ≥ |SC (ui)| − |SC (ui) ∩ SD (ui)| (4.4)
Do SB (ui) ∩ SD (ui) ⊆ SB (ui) , SC (ui) ∩ SD (ui) ⊆ SC (ui) nản (4.4) tữỡng ữỡng vợi:
|SB (ui) ∪ (SB (ui) ∩ SD (ui))| − |SB (ui) ∩ (SB (ui) ∩ SD (ui))| ≥
|SC (ui) ∪ (SC (ui) ∩ SD (ui))| − |SC (ui) ∩ (SC (ui) ∩ SD (ui))| (4.5)
Do SB∪D (ui) = SB (ui) ∩ SD (ui) , SC∪D (ui) = SC (ui) ∩ SD (ui) nản (4.5) tữỡng ữỡng
vợi:
⇔
n∑
i=1
|SB(ui)|−|SB∪D(ui)|
|U |2 ≥
n∑
i=1
|SC(ui)|−|SC∪D(ui)|
|U |2 (4.6)
Do B ⊂ B ∪D,C ⊂ C ∪D nản theo Mằnh ã 4.1, cổng thực (4.6) tữỡng ữỡng vợi
dE (K (B) ,K (B ∪D)) ≥ dE (K (C) ,K (C ∪D))

5. RểT GÅN THUậC TNH TRONG BƒNG QUY˜T ffiÀNH KHặNG ffi†Y
ffiế SÛ DệNG METRIC
5.1. Têp rút gồn cừa bÊng quyát ành khổng Ưy ừ dỹa trản metric
ffiành nghắa 5.1. Cho bÊng quyát ành khổng Ưy ừ IDS = (U,C ∪D,V, f). R ⊆ C ữủc
gồi l  mởt rút gồn cừa C dỹa trản metric náu thọa mÂn iãu kiằn:
138 NGUY™N LONG GIANG, NGUY™N THANH TềNG, Vễ ffiÙC THI
(1) dE (K (R) ,K (R ∪D)) = dE (K (C) ,K (C ∪D)) .
(2) ∀r ∈ R, dE (K (R− {r}) ,K (R− {r} ∪D)) 6= dE (K (C) ,K (C ∪D)) .
5.2. ffiở quan trồng cừa thuởc tẵnh dỹa trản metric
ffiành nghắa 5.2. Cho bÊng quyát ành khổng Ưy ừ IDS = (U,C ∪D,V, f) vợi B ⊆ C.
ffiở quan trồng cừa thuởc tẵnh b ∈ C −B ữủc ành nghắa
SIGB (b) = dE (K (B) ,K (B ∪D))− dE (K (B ∪ {b}) ,K (B ∪ {b} ∪D))
vợi giÊ thiát S∅ (ui) = U vợi mồi ui ∈ U, i = 1.. |U |.
5.3. ThuƠt toĂn tẳm têp rút gồn cừa bÊng quyát ành khổng Ưy ừ sỷ dửng
metric
ị tữðng cừa thuêt toĂn l  xuĐt phĂt tứ têp R = ∅, lƯn lữủt bờ sung v o têp R thuởc tẵnh
cõ ở quan trồng lợn nhĐt cho án khi tẳm ữủc têp rút gồn.
Thuêt toĂn 5.1. Tẳm têp rút gồn cừa bÊng quyát ành khổng Ưy ừ.
ffiƯu v o: BÊng quyát ành khổng Ưy ừ IDS = (U,C ∪D,V, f).
ffiƯu ra: Têp rút gồn R.
1. R = ∅;
2. Tẵnh dE (K (R) ,K (R ∪D)) ;
3. Tẵnh dE (K (C) ,K (C ∪D)) ;
// Thảm dƯn v o R cĂc thuởc tẵnh cõ ở quan trồng lợn nhĐt
4. While dE (K (R) ,K (R ∪D)) 6= dE (K (C) ,K (C ∪D)) do
5. Begin
6. For each a ∈ C −R
7. Begin
8. Tẵnh dE (K (R ∪ {a}) ,K (R ∪ {a} ∪D)) ;
9. Tẵnh SIGR (a) = dE (K (R) ,K (R ∪D))− dE (K (R ∪ {a}) ,K (R ∪ {a} ∪D)) ;
10. End;
11. Chồn am ∈ C −R sao cho SIGR (am) = Max
a∈C−R
{SIGR (a)} ;
12. R = R ∪ {am} ;
13. Tẵnh dE (K (R) ,K (R ∪D)) ;
14. End;
// LoÔi bọ cĂc thuởc tẵnh dữ thứa trong R náu cõ
15. For each a ∈ R
16. Begin
17. Tẵnh dE (K (R− {a}) ,K (R− {a} ∪D)) ;
MậT PHìèNG PHP MẻI RểT GÅN THUậC TNH TRONG BƒNG QUY˜T ffiÀNH 139
BÊng 6.1. Kát quÊ thỹc hiằn Thuêt toĂn IQBAR v  Thuêt toĂn 5.1
STT Bở số liằu |U | |C| Thuêt toĂn IQBAR Thuêt toĂn 5.1
|R| t |R| t
1 Hepatitis.data 155 19 4 1.296 4 0.89
2 Lung-cancer.data 32 56 4 0.187 4 0.171
3 Automobile.data 205 25 5 3 5 1.687
4 Anneal.data 798 38 9 179 9 86.921
5 Voting Records 435 16 15 25.562 15 16.734
6 Credit Approval 690 15 7 29.703 7 15.687
18. If dE (K (R− {a}) ,K (R− {a} ∪D)) = dE (K (C) ,K (C ∪D)) then R = R− {a} ;
19. End;
20. Return R;
Vợi bữợc thảm dƯn v o R cĂc thuởc tẵnh cõ ở quan trồng lợn nhĐt, têp thuởc tẵnh R thu
ữủc tứ cƠu lằnh tứ 4 án 14 thọa mÂn iãu kiằn bÊo to n khoÊng cĂch dE (K (R) ,K (R ∪D)) =
dE (K (C) ,K (C ∪D)). Vợi bữợc loÔi bọ cĂc thuởc tẵnh dữ thứa trong R náu cõ, cƠu lằnh tứ 15
án 19 Êm bÊo têp R l  tối thiºu, nghắa l  ∀r ∈ R, dE (K (R− {r}) ,K ((R− {r}) ∪D)) 6=
dE (K (C) ,K (C ∪D)). Theo ffiành nghắa 5.1, têp R thu ữủc l  têp rút gồn cừa bÊng quyát
ành dỹa trản metric.
ffiº tẵnh SIGR (a) ta ch¿ cƯn tẵnh SR∪{a}(ui), SR∪{a}∪D(ui), vẳ SR(ui), SR∪D(ui) Â
ữủc tẵnh ð vỏng l°p trữợc. ffiở phực tÔp º tẵnh SR∪{a}(ui) khi  biát SR(ui) vợi mồi
ui ∈ U l  O
(
|U |2
)
, do õ giÊ sỷ D = {d}, ở phực tÔp º tẵnh tĐt cÊ cĂc SIGE (a) l 
(|C|+ (|C| − 1) + ...+ 1) ∗ |U |2 = (|C| ∗ (|C| − 1) /2) ∗ |U |2 = O
(
|C|2|U |2
)
. ffiở phực tÔp º
chồn thuởc tẵnh cõ ở quan trồng lợn nhĐt l  |C|+ (|C| − 1) + ... + 1 = |C| ∗ (|C| − 1) /2 =
O
(
|C|2
)
. Do õ, ở phực tÔp cừa thuêt toĂn l  O
(
|C|2|U |2
)
. ffiở phực tÔp n y tốt hỡn ở
phực tÔp cừa cĂc thuêt toĂn trong [2, 3, 18].
6. THÛ NGHI›M THUŁT TON
C i °t Thuêt toĂn IQBAR[3] v  Thuêt toĂn 5.1 bơng ngổn ngỳ C + +.Trản mĂy tẵnh
PC vợi cĐu hẳnh Pentium dual core 2.13 GHz CPU, 1GB bở nhợ RAM, sỷ dửng hằ iãu h nh
Windows XP Proessional, chÔy thỷ nghiằm hai thuêt toĂn vợi 6 bở số liằu lĐy tứ kho dỳ liằu
UCI [17]. 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 s). BÊng 6.1
mổ tÊ kát quÊ thỹc hiằn cừa hai thuêt toĂn.
Kát quÊ thỷ nghiằm cho thĐy, têp rút gồn thu ữủc khi thỹc hiằn Thuêt toĂn 5.1 v  Thuêt
toĂn IQBAR trản 6 bở số liằu l  nhữ nhau. Tuy nhiản, thới gian thỹc hiằn Thuêt toĂn 5.1
nhanh hỡn Thuêt toĂn IQBAR, do õ Thuêt toĂn 5.1 hiằu quÊ hỡn Thuêt toĂn IQBAR.
140 NGUY™N LONG GIANG, NGUY™N THANH TềNG, Vễ ffiÙC THI
7. K˜T LUŁN
Trản hằ thổng tin khổng Ưy ừ, b i bĂo  thỹc hiằn cĂc nởi dung nghiản cựu sau:
1) ffiã xuĐt Liang entropy mð rởng v  nghiản cựu mởt số tẵnh chĐt cừa chúng.
2) XƠy dỹng mởt metric trản hồ cĂc phừ sỷ dửng Liang entropy mð rởng.
3) ffiã xuĐt thuêt toĂn heuristic tẳm têp rút gồn cừa bÊng quyát ành khổng Ưy ừ sỷ
dửng metric ữủc xƠy dỹng vợi ở phực tÔp O
(
|C|2|U |2
)
. Chựng minh bơng lỵ thuyát
v  thỹc nghiằm, thuêt toĂn ã xuĐt hiằu quÊ hỡn thuêt toĂn trong [2, 3, 18].
T€I LI›U THAM KHƒO
[1] K.S. Chin, J.Y. Liang, C.Y. Dang, Rough set data analysis algorithms for incomplete information
systems, Proceedings of the 9th international conference on Rough sets, fuzzy sets, data
mining, and granular computing, RSFDGrC'03, (2003) 264268.
[2] B. Huang, X. He, X.Z. Zhou, Rough computational methods based on tolerance matrix, Auto-
matica Sinica 30 (2004) 363370.
[3] B. Huang, H. X. Li, X. Z. Zhou, Attribute reduction based on information quantity under
incomplete information systems, Systems Application Theory & Practice 34 (2005) 5560.
[4] M. Kryszkiewicz, Rough set approach to incomplete information systems, Information Science
112 (1998) 3949.
[5] J.H. Li, K.Q. Shi, A algorithm for attribute reduction based on knowledge granularity,Computer
Applications 26 (6) (2006) 7677.
[6] J.Y Liang, K.S. Chin, C.Y. Dang, C.M.YAM Richard, New method for measuring uncertainty
and fuzziness in rough set theory, International Journal of General Systems 31 331342.
[7] J.Y. Liang, Y.H. Qian, Axiomatic approach of knowledge granulation in information system,
Lecture Notes in Artificial Intelligence 4304 (2006) 10741078.
[8] J.Y. Liang, Y.H. Qian, Information granules and entropy theory in information systems, Infor-
mation Sciences, 51 (2008) 118.
[9] J.Y. Liang, Z.B. Xu, The algorithm on knowledge reduction in incomplete information systems,
International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 10 1 (2002)
95103.
[10] J.Y. Liang, Z.Z. Shi, D.Y. Li, M.J. Wierman, The information entropy, rough entropy and
knowledge granulation in incomplete information system, International Journal of General
Systems 35 (6) (2006) 641654.
[11] Nguyạn Thanh Tũng, Vã mởt metric trản hồ cĂc phƠn hoÔch cừa mởt têp hủp hỳu hÔn, TÔp chẵ
Tin hồc v  ffiiãu khiºn hồc 26 (1) (2010) 7375.
MậT PHìèNG PHP MẻI RểT GÅN THUậC TNH TRONG BƒNG QUY˜T ffiÀNH 141
[12] Y.H. Qian, J.Y. Liang, Combination entropy and combination granulation in incomplete infor-
mation system, RSKT, 2006 (184190).
[13] Y.H. Qian, J.Y. Liang, New method for measuring uncertainty in incomplete information sys-
tems, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems
(2008).
[14] Y.H. Qian, J.Y. Liang, C.Y. Dang, Knowledge structure, knowledge granulation and knowledge
distance in a knowledge base, International Journal of Approximate Reasoning 50 (2009)
174188.
[15] Y.H. Qian, J.Y. Liang, C.Y. Dang, F. Wang, W. Xu, Knowledge distance in information systems,
Journal of Systems Science and Systems Engineering 16 (2007) 434449.
[16] D. Shifei, D. Hao, Research and Development of Attribute Reduction Algorithm Based on Rough
Set, IEEE, CCDC, 2010 (648653).
[17] The UCI machine learning repository, 
[18] X.Z. Zhou, B. Huang, Rough set-based attribute reduction under incomplete Information Sys-
tems, Journal of Nanjing University of Science and Technology 27 (2003) 630636.
Ng y nhên b i 20 - 12 - 2011