Information Technology Reference
In-Depth Information
Attribute set
B
is a reduct of
A
, if
B
is the minimal attribute subset that
satisfies the following condition:
B
ŝ
c
ij
¬
∅
, for each non-empty element
c
ij
¬
∅ in M(
S
).
In other words, reducts are the minimal attribute subsets, which can discern
all objects that are distinguished by the whole attribute set
.
Because M(S) is symmetrical and c
ii
=
∅
for each i=1,2,…,n, M(S) can be
expressed by its lower triangle part (1
±
j<i
±
n
A
).
) corresponds to only one discernibility
function. The function is defined as follows:
The discernibility function of information system S is a boolean function with
m-dimension variables
Each discernibility matrix M(
S
a
1
,…,a
m
(
a
i
∈
A
i
=1,…,
m
). It is the conjunction of
∨
c
ij
,
where
∨
c
ij
is the disjunction of elements in
c
ij
¬
∅).
According to the correspondence between functions and reductions,
A.Skowron proposed a method for calculating the reduction RED(
c
ij
(1
±
j<i
±
n
and
S
) of
information system S. Its steps are as follows.
(1) Calculate the discernibility matrix M(
S
) of information system
S
;
(2) Calculate the discernibility function f
M(S)
corresponding to M(
);
(3) Calculate the minimal disjunction paradigm of f
M(S)
, where each element in
the disjunction paradigm is a reduct.
S
Note, all reducts can be computed with the method. However, the method is
only propitious to very small data set.
Table 11.1 Information table
A
U
a
b
c
d
e
u
1
1 0 2 1 0
u
2
0 0 1 2 1
u
3
2 0 2 1 0
u
4
0 0 2 2 2
u
5
1 1 2 1 0
To reduce a decision table, we can use the discernibility matrix based method
to reduce condition attributes. We use the decision attributes to generate
equivalent classes, and disregard the objects with same decision attribute values.
The table in Table 11.1 is a decision table, where
a, b, c, d
are its condition
attributes and
is its decision attribute. Then, the discernibility matrix of it is
illustrated as Table 11.2.
e
