Information Technology Reference
In-Depth Information
k
≠1, the algorithm is
inconsistent. If the PQ-algorithm has a dependency degree
Obviously,
0
≤
k
≤1. If
k
=1, the algorithm is consistent; if
k
, we call the
dependency degree of
Q
on
P
is
k
, denoted as
P
¼
k
Q
.
11.4.2
Reduction of Consistent Decision Tables
We know that the property of indiscernibility can be used to the reduction of
knowledge. Given an attribute set
C
⊆
A
in knowledge representation system
S
,
A
is redundant if and only if IND(
A
−
C
)=IND(
A
). If
A-C
is redundant in
A
and
C
is
dependent in
S, C
is the reduct of
A
.
Here, the problem discussed is expressed by logic form, and we use the
consistency of algorithm to determine and reduce.
Given a consistent algorithm (
P, Q
) and
a
∈
P
, if and only if ((
P
−{
a
}), Q) is
consistent, we call a is omissible in (
P, Q
), otherwise it is not omissible.
If all attributes of
) is
independent. Given attribute subset
R
⊆
P
, if (
R, Q
) is independent and consistent,
then
R
is the
P
reduct of algorithm (
P, Q
). If attribute subset
R
is the
P
reduct of
algorithm (
P
are not omissible in algorithm (
P, Q
), (
P, Q
). The reduction of algorithm is to
reduce unnecessary condition attributes, and it is the reduction of the dimensions
of knowledge representation spaces.
In algorithm (
P, Q
), (
R, Q
) is the reduct of (
P, Q
), the set of all attributes that are not omissible is called as
the core of algorithm (
P, Q
P, Q
), denoted as CORE(
P, Q
).
Proposition 11.7
CORE(P, Q)= RED(P, Q)
Here, RED(P, Q) is the set of all reducts of algorithm (P, Q).
Besides, we introduce some properties of attributes in decision tables.
Proposition 11.8
Decision table T=(U, A, C, D) is consistent, if and only if
¼
C
D.
From proposition 11.8, we can easily test the consistency by calculating the
dependency of condition attributes to decision attribute. If the degree of
dependency is equal to 1, we say the decision table is consistent, otherwise
inconsistent.
Proposition 11.9
Each decision table T=(U, A, C, D) can be uniquely
decomposed to two decision tables T
1
=(U
1
, A, C, D) and T
2
=(U
2
, A, C, D), where
C
¼
1
D in T
1
and C
¼
0
D in T
2
. Here, U
1
=POS
C
(D), U
2
=
∪
BN
C
(X) and
X
∈
U|IND(D)
