Information Technology Reference
In-Depth Information
NP-hard problem, thus it is necessary to simplify the calculation process and find
the optimal or suboptimal reduct with the help of heuristic information.
Existing reduction algorithms usually use core as the start to calculate reducts,
and then compute the best or the minimal reduct (defined by users). Employing
attribute importance degrees as heuristic information, the algorithms add
attributes to a set one by one according to their importance degrees. Once the
attribute set is a reduct, the algorithm stops. For different algorithms, the
measures of attribute importance are different. Current researchers mainly focus
on the following measures.
(1) Measure based on the movement of dependency
Suppose
is a decision table, C and D are condition attribute set and decision
attribute set respectively. Let
S
R
⊂
C
, then for each attribute
a
∈
C
−
R
, the
importance degree is defined as follows:
SGF
(
a,R,D
)=
k
(
R
∪{
a
},
D
)−
k
(
R,D
)
where
)).
The degree can also be defined as follows:
SGF
k
(
R,D
)=
card
(
POS
R
(
D
))/
card
(
POS
C
(
D
(
a,R,D
)=γ
R∪{a}
−γ
R
where γ
R
=
).
Basic ideas of the two definitions are same. If a decision table is given,
card(POS
C
(D)) and card(U) are both constant. Although the values of importance
degrees are different, the order of attributes arranged by their importance degrees
is same.
(2) Measure based on information entropy
Suppose
card
(
POS
R
(
D
))/
card
(
U
H
(
D/R
) is the condition entropy of
R
related with
D
, the importance
degree of attribute a is defined as:
SGF
})
(3) Measure based on the frequency of attributes in discernibility matrix
Assume
(
a,R,D
)=
H
(
D/R
)−
H
(
D/ R
∪{
a
M
is a discernibility matrix generated from decision table
S
, and let
p
(
a
) be the frequency of attribute a in
M
, which defines the frequency of
a
in
M
.
Thus, the importance degree of attribute a is defined as:
SGF
(
a,R,D
)= p(
a
)
11.4.3
Reduction of Inconsistent Decision Tables
If all decision rules generated from a decision table are consistent, the table is
consistent, otherwise it is inconsistent. It is easy to reduce a consistent decision
