Information Technology Reference
In-Depth Information
Definition 11.6
Suppose R is a family set of equivalence relation, and let R
∈
R.
If IND(R)=IND(R-R) then relation R is dispensable in R, or indispensable
otherwise. If every relation R in family set R is indispensable then R is called as
independent, or dependent otherwise.
Definition 11.7
If Q
⊆
P is independent, and IND(Q)=IND(P), then Q is a
reduct of relation family set P. The set of all indispensable relations is called as
the core of P, denoted as CORE(P).
Apparently, a family set P has more than one reduct.
The following theorem is an important property of the relationship between
core and reduct.
Theorem 11.1
The core of family set P is equal to the intersection of all reducts,
that is
CORE(P)=
RED(P) (11.4)
where RED(P) is the family set of all reducts of P.
ŝ
We can observe from above theorem that the concept of core has two aspects
of meanings: first, it can be viewed as the basis of calculation for all reducts. This
is because the core is incorporated in every reduct and its calculation is indirect;
second, the core can be explained as the assembly of the most important
components of knowledge, which can not be deleted in the reduction process.
The most common method to generate reduction is to add relations that can be
reduced one by one and check them. Note that the number of ways to add
relations is equal to the base number of the power set of reducible relation sets. In
the best case, all irreducible relation sets are the unique reduct. So how to
calculate all reducts and to calculate an optimal reduct (such as minimal relations)
are NP problems.
11.2.2
Relative Reduction
This section extends the concepts of reduction and core. Before that, let's define
the concept of positive region of a classification related with another classification.
Definition 11.8
Suppose P and Q are the family set of equivalence relations on
U. The so-called P-positive region of Q, denoted as POSP(Q), is defined as
POSP(Q)=
G
Q
P*(X) (11.5)
X
∈
U
/
