Methods for Lower Approximation Reduction in Inconsistent Decision Table Based on Tolerance Relation ()
1. Introduction
The rough set theory, proposed by Pawlak in the early 1980s [1], is an extension of the classical set theory for modeling uncertainty or imprecision information. The research has recently roused great interest in the theoretical and application fronts, such as machine learning, pattern recognition, data analysis, and so on.
Attribute reduction is one of the hot research topics of rough set theory. Much study on this area had been reported and many useful results were obtained [2-8]. However, most work was based on consistent information systems, and the main methodology has been developed under equivalence relations (indiscernibility relations). In practice, most of information systems are not only inconsistent, but also based on tolerance relations because of various factors. The tolerance of properties of attributes plays a crucial role in those systems. For this reason, J. Jarinen [9-13] proposed an extension rough sets theory, called the rough sets based on tolerances to take into account the tolerance relation properties of attributes. This innovation is mainly based on substitution of the indiscernibility relation by a tolerance relation. And many studies have been made in DRSA [14-18]. But useful results of attribute reductions are very poor in inconsistent information systems based on tolerance relations until now.
In this paper, the lower approximation reduction is proposed in inconsistent information systems based on tolerance relations. Moreover, some properties are discussed. Furthermore, judgment theorem and discernibility matrix are obtained, from which an approach to lower approximation reductions can be provided in inconsistent information systems based on tolerance relations.
2. Rough Sets and Information Systems Based on Tolerance Relations
The following recalls necessary concepts and preliminaries required in the sequel of our work. Detailed description of the theory can be found in [5,17].
An information system with decisions is an ordered quadruple
, where
is a non-empty finite set of objects;
is a non-empty finite attributes set;
denotes the set of condition attributes;
denotes the set of decision attributes, and
;
,
is the value of ![](https://www.scirp.org/html/24-7400807\1f066696-2c39-4b1d-a6c2-a4186f0d1f65.jpg)
for
,
is the domain of
, where
;
,
is the value of
for
,
is the domain of
,
.
If a binary relation T on the universe U is reflexive and symmetric, it is called a tolerance relation on U. The set of all tolerance relations on U is denoted by
. A tolerance relation T can construct a covering of the universe U, not a partition. For any tolerance relation
and
denote
;
;
where
means x and
have the tolerance
, or
and
haven’t the tolerance
, and the
is called the tolerance neighborhood or tolerance class of the object
.
An information system is called an information system based on tolerance relations, in brief TIS, if all relations of condition attributes are tolerance relations.
In general, we call an information system based on tolerance relations with decision to be a decision table based tolerance relations, denoted by
, that is
. Thus the following definition can be obtained.
Definition 2.1. Let
be a decision table based on tolerance relations, for any
, denote
and
are tolerance relations of information system
.
If we denote
;
then the following properties of a tolerance relation are trivial.
Proposition 2.1. Let
be a tolerance relation. The following hold.
(1)
is reflexive, symmetric, but not transitive, so it is not an equivalence relation.
(2) If
, then
.
(3) If
, then ![](https://www.scirp.org/html/24-7400807\aa965480-d605-459e-a02b-b50d358579d4.jpg)
(4)
constitutes a covering of
.
For any subset
of
, and
of
define
;
,
and
are said to be the lower and upper approximation of
with respect to a tolerance relation
. And the approximations have also some properties which are similar to those of Pawlak approximation spaces.
Proposition 2.2. Let
be an information systems based on tolerance relation and
, then its lower and upper approximations satisfy the following properties.
(1)![](https://www.scirp.org/html/24-7400807\55498da0-8a17-4c3b-89e1-b965b503a64b.jpg)
(2) ![](https://www.scirp.org/html/24-7400807\298f9032-4d81-465b-b23d-bae36dd918ea.jpg)
(3) ![](https://www.scirp.org/html/24-7400807\84fa1edc-5ed7-42ad-a212-d08c13560412.jpg)
(4) ![](https://www.scirp.org/html/24-7400807\242a4d5a-4c43-480c-9033-e78587a63dec.jpg)
(5) ![](https://www.scirp.org/html/24-7400807\ab99aac1-3a7a-41f7-a996-3998b6dc2d15.jpg)
(6) If
, then
and
;
where
is the complement of
.
Definition 2.2. For an information system based on tolerance relations with decisions
, if
, then this information system is consistent, otherwise, this system is inconsistent.
Example 2.1. Given an information system based on tolerance relations in Table 1.
Define the tolerance relation
as following:
![](https://www.scirp.org/html/24-7400807\904677a2-632a-49c2-b604-8eb3dfd8d5d5.jpg)
From the table, we have
![](https://www.scirp.org/html/24-7400807\91099366-af0d-41ef-9a9b-a64a7d9884be.jpg)
and
![](https://www.scirp.org/html/24-7400807\3ae7a125-9e94-414d-8754-a99ae79153cf.jpg)
Obviously, by the above, we have
, so the system in Table 1 is inconsistent.
For simple description, the following information system with decisions is based on tolerance relations, i.e. information systems based on tolerance relations.
3. Theories of Lower Approximation Reduction in Inconsistent Information Systems Based on Tolerance Relation
Let
be an information system based on tolerance relations with decisions, and![](https://www.scirp.org/html/24-7400807\44698716-21af-4a1e-b884-c30a3b5879db.jpg)
Table 1. An information system based on tolerance relations.
![](https://www.scirp.org/html/24-7400807\642f0909-7596-4de2-a3a2-e05d0cda7aa5.jpg)
be tolerance relations derived from condition attributes set
and decision attributes set
respectively. For
, denote
![](https://www.scirp.org/html/24-7400807\2daf53c3-ad80-4f11-9d3c-2b1b361583f5.jpg)
![](https://www.scirp.org/html/24-7400807\a39ae96d-685a-4f71-a173-2eed96a251ec.jpg)
where
. Furthermore, we said
is the lower approximation function about attributions sets B.
Definition 3.1. Let
and
be two vectors with
dimensions. If
, we said that
is equal to
, denoted by
. If
, we said that
is less than
, denoted by
. Otherwise, If it exists
such that
, we said
is not less than
, denoted by
.
Such as
, and
.
From the above, we can have the following propositions immediately.
Proposition 3.1. Let
be an information system based on tolerance relations with decisions. If
, then
.
Definition 3.2. Let
be an Inconsistent information system. If
, for all, we say that
is a lower approximation consistent set of
. If
is a lower approximation consistent set, and no proper subset of
is lower approximation consistent set, then
is called an lower approximation consistent reduction of
.
Example 3.1. Consider the system in Table 1.
For the system in Table 1, we denote
![](https://www.scirp.org/html/24-7400807\835be3a0-c155-45cd-b312-91915b8aa1d1.jpg)
We can have
![](https://www.scirp.org/html/24-7400807\9b690b94-33ec-49c6-95cb-4b001091e552.jpg)
![](https://www.scirp.org/html/24-7400807\e70635f3-c8a5-4981-ac92-98c24d6d0479.jpg)
![](https://www.scirp.org/html/24-7400807\4f5d2896-8318-432a-8cd5-0742e910b6f7.jpg)
When
, it can be easily checked that
, for all
. So that
, and
is a lower approximation consistent set of
. Furthermore, we can examine that
and
are not lower approximation consistent set of
. That is to say
is a lower approximation reduction of
.
Moreover, it can be easily calculated that
and
are not lower approximation consistent sets of
. Thus there exist only one lower approximation reduction of
in the system of Table 1, which is
.
In the following, detailed judgment theorems of lower approximation reduction are obtained.
4. Methods for Attribute Reduction in Inconsistent Information Systems Based on Tolerance Relations
This section provides approaches to lower approximation reduction in inconsistent information systems.
Definition 4.1. Let
be an information system, Denote
![](https://www.scirp.org/html/24-7400807\32990027-b1dc-4f70-8fd6-75bbd62194c0.jpg)
![](https://www.scirp.org/html/24-7400807\f9f29172-e0ff-43a9-bd80-b4bd74dcc29e.jpg)
is called lower approximation discernibility attribute set, and matrixes
is referred to lower approximation discernibility matrix of
respectively.
Theorem 4.1. Let
be an information system,
, then
is a lower approximation consistent set
if
, then exists
such that
, for any
.
Proof.
Assume that exists
, for any
, and
, if
, then
.
Since B is a lower approximation consistent set, therefore, for any
, we can have
. According to
, so we can obtain
and
. Moreover for
, then
, therefore
and
. Hence we have
, which is contradiction.
Supposed that
isn’t a lower approximation consistent set, then exists
, such that
, therefore exists
and
. So we can have
and
.
Moreover,
, so there exists ![](https://www.scirp.org/html/24-7400807\7c2f020d-8325-4ff2-8009-acc6e888fe80.jpg)
and
, i.e.
. In addition, we can have that exists
such that
, which is contradict with
.
Therefore
is a lower approximation consistent set.
Theorem 4.2. Let
be an information system.
, then
is a lower approximation consistent set if and only if for any
, we can have
.
Proof.
For any
, there exists
such that
, so according to Theorem 4.1, we can have that exists
such that
, so
.
Therefore, if
is a lower approximation consistent set then for any
, we can have
.
If for any
,
, then exists
such that
, so we have
, and
.
Therefore
is a lower approximation consistent set according to Theorem 4.1.
Definition 4.2. Let
be an information system,
is referred to lower approximation discernibility matrix of
, denote
![](https://www.scirp.org/html/24-7400807\ab5b895b-2774-436d-ae6b-a2b4a5284eba.jpg)
is called discernibility formula of lower approximation.
Theorem 4.3. Let
be an information system. The minimal disjunctive normal form of discernibility formula of lower approximation is
![](https://www.scirp.org/html/24-7400807\160c3e03-a1a1-4c8f-999a-a5a588fb80ba.jpg)
Denote
, then
is just set of all distribution reductions of
.
Proof. It follows directly from Theorem 4.1 and the definition of minimal disjunctive normal of the discernibility formula of lower approximation.
Theorem 4.3 provides a practical approach to lower
Table 2. Lower approximation discernibility matrix ML.
![](https://www.scirp.org/html/24-7400807\de21e8d9-3df0-47b8-874a-51fea81abb4b.jpg)
approximation reductions of information systems with decisions based on tolerance relation. The following we will consider the system in Table 1 using this approach.
Example 4.1. For the system in Table 1, the function of distribution and maximum distribution have been obtained in Example 3.1. In additional, we can have
![](https://www.scirp.org/html/24-7400807\f6def888-04ef-4f97-815b-9259fa2baa72.jpg)
The above table (Table 2) is the lower approximation discernibility matrix of system in Table 1.
Consequently, we have
![](https://www.scirp.org/html/24-7400807\a3a091c8-0947-4424-8179-b1a7c03d4c60.jpg)
Therefore, we obtain that
is all lower approximation reduction of information system in Table 1, which accords with the result of Example 3.1.
5. Conclusion
It is well known that most of information systems are not only inconsistent, but also based on tolerance relations because of various factors in practice. Therefore, it is important to study the lower approximation reduction in inconsistent information systems. In this paper, we are concerned with approaches to the problem. The lower approximation reduction is introduced in inconsistent information systems based on tolerance relations. The judgment theorem and discernibility matrix are obtained, from which we can provide the approach to attribute reductions in inconsistent information systems based on tolerance relations.