# Extended Tolerance Relation to Define a New Rough Set Model in Incomplete Information Systems

Authors: Do Van Nguyen; Koichi Yamada; Muneyuki Unehara
Journal: Advances in Fuzzy Systems
 (2013)

---

## Abstract

This paper discusses and proposes a rough set model for an incomplete information system, which defines an extended tolerance relation using frequency of attribute values in such a system. It first discusses some rough set extensions in incomplete information systems. Next,  “probability of matching” is defined from data in information systems and then measures the degree of tolerance. Consequently, a rough set model is developed using a tolerance relation defined with a threshold. The paper discusses the mathematical properties of the newly developed rough set model and also introduces a method to derive reducts and the core.


---

## Body

## 1. Introduction

Rough set theory [1, 2] was first proposed by Pawlak as a means to analyze vague descriptions of items. The original rough sets approach presupposes that all objects in an information system have precise attribute values. Problems arise when some of the values are unknown, which sometimes happens in the real world. Therefore, it is necessary to develop a theory which enables classifications of objects even if there is only partial information available. The rough set model proposed by Kryszkiewicz [3, 4], for example, introduced indiscernibility based on tolerance relation to deal with missing values in the information system. In these approaches, a missing value was considered as a special value that may take any possible value.However,tolerance relation sometimes leads to a poor result with respect to approximation. Stefanowski and Tsoukiàs [5, 6] discussed the limitation and introduced similarity relation to refine the results obtained by using tolerance relation approach. Wang [7] gave some examples to prove that similarity relation may results in lost information and proposed limited tolerance relation. Yang et al. [8] also generalized a reasonable and flexible classification in incomplete information system by “new binary relation.”In fact, there is an array of methods to handle incomplete objects [9, 10]. Some approaches replace missing values with the most common value [11], while the other considers “unknown” itself as a new value for the attribute and treats it in the same way as ordinary values [10]. Actually, the method of handling missing values should be chosen depending on the characteristics and requirements of applications. In general, approaches deal with unavailable values based on one of the following two interpretations [12]. The first is “lost value” in which unknown values of attributes are already lost. Similarity relation [5] is one example of this semantics. The second is “do not care,” which may be potentially replaced by any value in the domain. Such incomplete decision tables were broadly studied in numerous researches [3, 4]. Grzymala-Busse [13–17] built a characteristic relation based on both “lost value” case and “do not care” case.In this paper, we study “probability of matching” and propose a new method of handling missing values in incomplete information systems based on tolerance degree. Our approach adopts the “lost value” interpretation. The approach is useful in knowledge acquisition from incomplete information systems, in which some object values appear frequently and others do not.The paper is organized as follows. Section2 discusses tolerance relation to deal with incomplete information and its drawback. This section also introduces some extensions to avoid the issues of tolerance relation. The next section—Section 3—is to find out how the frequency of attributes values affect the probability of matching among objects on an attribute. From this, in Section 4, we propose a tolerance relation calledextended tolerance relation and discuss the advantage of the approach. Section 5 introduces approximation spaces based on three ways. Finally, methods to derive reduct and core shall be explained in Section 6.


## 2. Rough Set in Incomplete Tables

In this section, we discuss several rough set extensions in incomplete decision tables with their issues. An information system is defined as a pairI=(U,A), where U is a nonempty finite set of objects called the universe and A is a nonempty finite set of attributes. For every a∈A, there is a mapping from U into a space,fa:U→Va, and Va is called the value set of  a  [1, 2].IfU contains at least one object with an unknown (missing or null) value, then I is called an incomplete information system, otherwise complete [3, 4]. In incomplete information systems, objects may contain several unknown attribute values, but we do not assume the case where all objects take the unknown value for an attribute. Unknown values are denoted by special symbol “*” in incomplete information systems and are supposed to be contained in the setVa.A decision table defined byDT=(U,A∪{d}) is an information system, where d∉A is a distinguished attribute called decision [18]. In a similar manner to information systems, a decision table may be incomplete, otherwise complete. However, all decision values are known both in complete and incomplete decision tables.In a complete decision table, the relationEQUP(x,y), P⊆A denotes a binary relation between objects that are equivalent in terms of values of attributes in P [1]. The equivalence relation is reflexive, symmetric, and transitive. Let EP(x)={y∈U∣EQUP(y,x)} be the set of all objects that are equivalent to  x by P, and let it be called equivalence class.


### 2.1. Tolerance Relation

A tolerance relationTORP(x,y), P⊆A denotes a binary relation between objects that are possibly equivalent in terms of values of attributes. In incomplete information systems [3, 4], tolerance relation is defined by
(1)TORP(x,y)⟺∀a∈P,(fa(x)=fa(y))∨(fa(x)=*)∨(fa(y)=*),
where ∨ denotes disjunction.The relation is reflexive and symmetric but does not need to be transitive. LetTP(x)={y∈U∣TORP(y,x)} be the set of objects which are in relation with x in terms of P in the sense of the above tolerance relation. Due to the symmetric property, x is also tolerant to elements in TP(x).Rough sets based ontolerance relation in incomplete information systems are defined in a similar way to those in complete information systems [1]. LetX⊆U  and  P⊆A. Then, apprT_PX is the lower approximation [3, 4] of X in terms of P,  if and only if
(2)apprT_PX={x∈U∣TP(x)⊆X},apprT¯PX is the upper approximation of X in terms of P, if and only if
(3)apprT¯PX={x∈U∣TP(x)∩X≠ϕ}.Now, we illustrate the above concepts with an incomplete decision table from [10]. The decision table is shown in Table 1.Table 1
An example of dataset with missing values.
Cases
Temperature
Headache
Nausea
Decision (flu)
x
1
High
*
No
Yes
x
2
Very high
Yes
Yes
Yes
x
3
*
No
No
No
x
4
High
Yes
Yes
Yes
x
5
High
*
Yes
No
x
6
Normal
Yes
No
No
x
7
Normal
No
Yes
No
x
8
*
Yes
*
YesFrom Table1, we can induce approximation space for X-group of people such that the value of flu is no based on all condition attributes:
(4)apprT_AX={x7},apprT¯AX={x1,x3,x4,x5,x6,x7,x8}.The approximations are quite poor. Moreover, there exist objects which intuitively could be classified inX, while they are not in the lower approximation. Take, for instance, objectx6; we have its complete description, and intuitively there is no other object perceived as very tolerant to it. However, it is not included into the lower approximation of X. This is due to missing attribute values of objects  x8,  which is actually tolerant tox6according to Equation (1).


### 2.2. Similarity Relation

In the approach proposed by Stefanowski [5, 6], it is assumed that an object x can be considered as similar to another object y only if all known attribute values of x are the same as those of y. Such a relation shall not be symmetric. If one object has more complete description than the other, the inverse relation shall not hold. More formally, given an information system I=(U,A) and an attribute setP⊆A, the similarity relation is defined as follows:
(5)SIMP(x,y)⟺∀a∈P,(fa(x)=*)∨(fa(x)=fa(y)).It is easy to observe that this relation is reflexive and transitive although not necessarily symmetric. Now for each object, we can induce two similarity sets:SP(x)={y∈U∣SIMP(y,x)}, the set of objects similar to x (note that the arguments of SIMP is not (x,y)), andSP-1(x)={y∈U∣SIMP(x,y)}, the set of objects to which x is similar.Clearly,SP(x) and SP-1(x) are two different sets. We can now introduce the definitions of approximation space of a set X⊆U as follows:
(6)apprS_PX={x∈U∣SP-1(x)⊆X},apprS¯PX=⋃{SP(x)∣x∈X}.By the definition ofsimilarity relation and tolerance relationintroduced in this section, we can see that the conditions for which similarity relation holds are a subset of the conditions for which tolerance relation holds (we can see that if SIMP(x,y),then TORP(x,y)). Hence, tolerance classes of elements in U shall be “wider” than the respective similarity classes [5, 6].


### 2.3. Limited Tolerance Relation

Lets compare the attributes ofx4 with those of x5 in Table 1. According to our intuition, x4 seems similar to x5 due to the same description in temperature and nausea. However, it is actually not, though x5 is similar to x4 according to the Equation (5). In a huge system, two objects may be considered as distinct, in terms of similarity relation, because of little missing information. For example, objects x with (*,1,2,3,4,5,6,7,8,9) and y with (0,*,2,3,4,5,6,7,8,9), where the vectors are abbreviate representation of attribute values of the objects, are tolerant according to Equation (1) and intuitively similar to each other. However, they do not satisfy the nonsymmetric similarity relation. To avoid such problem, Wang [7] developed a novel limited tolerance(LT)relation.LetOP(x)={a∣a∈P,fa(x)≠*}; limited tolerance relation is defined on U as follows:
(7)LTORP(x,y)⟺(∀a∈P;fa(x)=fa(y)=*)∨((OP(x)∩OP(y)≠ϕ)hhhhhhhhh∧(∀a∈P;fa(x)≠*∧fa(y)hhhhhhhhhhh≠*⟶fa(x)=fa(y))).In the formula, the condition thatfa(x)≠*∧fa(y)≠*→fa(x)=fa(y) is equivalent to(fa(x)=*)∨(fa(y)=*)∨(fa(x)=fa(y)). Thus, the two objects that satisfy TORP(x,y) but not LTORP(x,y) are only those satisfying OP(x)∩OP(y)=ϕ.Generally speaking, two objects are inlimited tolerance relation if they are in one of the two cases. The first case is that all attribute values of the two objects are missing. The second is a case where there is at least an attribute having an ordinary value for both objects and the two objects have the same value for those attributes. Obviously, limited tolerance relation is reflexive and symmetric but not necessarily transitive.Thus,limited tolerance class is denoted by
(8)LTP(x)={y∈U∣LTORP(y,x)}.Based on that, approximation space is defined as follows:(9)apprLT_PX={x∈U∣LTP(x)⊆X},apprLT¯PX={x∈U∣LTP(x)∩X≠ϕ}.Wang [7] also proved that tolerance relation and similarity relation are the two extremities for extending indiscernibility relation, and limited tolerance relation happens to be between tolerance and similar relations,
(10)apprT_PX⊆apprLT_PX⊆apprS_PX,apprS¯PX⊆apprLT¯PX⊆apprT¯PX.


## 2.1. Tolerance Relation

A tolerance relationTORP(x,y), P⊆A denotes a binary relation between objects that are possibly equivalent in terms of values of attributes. In incomplete information systems [3, 4], tolerance relation is defined by
(1)TORP(x,y)⟺∀a∈P,(fa(x)=fa(y))∨(fa(x)=*)∨(fa(y)=*),
where ∨ denotes disjunction.The relation is reflexive and symmetric but does not need to be transitive. LetTP(x)={y∈U∣TORP(y,x)} be the set of objects which are in relation with x in terms of P in the sense of the above tolerance relation. Due to the symmetric property, x is also tolerant to elements in TP(x).Rough sets based ontolerance relation in incomplete information systems are defined in a similar way to those in complete information systems [1]. LetX⊆U  and  P⊆A. Then, apprT_PX is the lower approximation [3, 4] of X in terms of P,  if and only if
(2)apprT_PX={x∈U∣TP(x)⊆X},apprT¯PX is the upper approximation of X in terms of P, if and only if
(3)apprT¯PX={x∈U∣TP(x)∩X≠ϕ}.Now, we illustrate the above concepts with an incomplete decision table from [10]. The decision table is shown in Table 1.Table 1
An example of dataset with missing values.
Cases
Temperature
Headache
Nausea
Decision (flu)
x
1
High
*
No
Yes
x
2
Very high
Yes
Yes
Yes
x
3
*
No
No
No
x
4
High
Yes
Yes
Yes
x
5
High
*
Yes
No
x
6
Normal
Yes
No
No
x
7
Normal
No
Yes
No
x
8
*
Yes
*
YesFrom Table1, we can induce approximation space for X-group of people such that the value of flu is no based on all condition attributes:
(4)apprT_AX={x7},apprT¯AX={x1,x3,x4,x5,x6,x7,x8}.The approximations are quite poor. Moreover, there exist objects which intuitively could be classified inX, while they are not in the lower approximation. Take, for instance, objectx6; we have its complete description, and intuitively there is no other object perceived as very tolerant to it. However, it is not included into the lower approximation of X. This is due to missing attribute values of objects  x8,  which is actually tolerant tox6according to Equation (1).


## 2.2. Similarity Relation

In the approach proposed by Stefanowski [5, 6], it is assumed that an object x can be considered as similar to another object y only if all known attribute values of x are the same as those of y. Such a relation shall not be symmetric. If one object has more complete description than the other, the inverse relation shall not hold. More formally, given an information system I=(U,A) and an attribute setP⊆A, the similarity relation is defined as follows:
(5)SIMP(x,y)⟺∀a∈P,(fa(x)=*)∨(fa(x)=fa(y)).It is easy to observe that this relation is reflexive and transitive although not necessarily symmetric. Now for each object, we can induce two similarity sets:SP(x)={y∈U∣SIMP(y,x)}, the set of objects similar to x (note that the arguments of SIMP is not (x,y)), andSP-1(x)={y∈U∣SIMP(x,y)}, the set of objects to which x is similar.Clearly,SP(x) and SP-1(x) are two different sets. We can now introduce the definitions of approximation space of a set X⊆U as follows:
(6)apprS_PX={x∈U∣SP-1(x)⊆X},apprS¯PX=⋃{SP(x)∣x∈X}.By the definition ofsimilarity relation and tolerance relationintroduced in this section, we can see that the conditions for which similarity relation holds are a subset of the conditions for which tolerance relation holds (we can see that if SIMP(x,y),then TORP(x,y)). Hence, tolerance classes of elements in U shall be “wider” than the respective similarity classes [5, 6].


## 2.3. Limited Tolerance Relation

Lets compare the attributes ofx4 with those of x5 in Table 1. According to our intuition, x4 seems similar to x5 due to the same description in temperature and nausea. However, it is actually not, though x5 is similar to x4 according to the Equation (5). In a huge system, two objects may be considered as distinct, in terms of similarity relation, because of little missing information. For example, objects x with (*,1,2,3,4,5,6,7,8,9) and y with (0,*,2,3,4,5,6,7,8,9), where the vectors are abbreviate representation of attribute values of the objects, are tolerant according to Equation (1) and intuitively similar to each other. However, they do not satisfy the nonsymmetric similarity relation. To avoid such problem, Wang [7] developed a novel limited tolerance(LT)relation.LetOP(x)={a∣a∈P,fa(x)≠*}; limited tolerance relation is defined on U as follows:
(7)LTORP(x,y)⟺(∀a∈P;fa(x)=fa(y)=*)∨((OP(x)∩OP(y)≠ϕ)hhhhhhhhh∧(∀a∈P;fa(x)≠*∧fa(y)hhhhhhhhhhh≠*⟶fa(x)=fa(y))).In the formula, the condition thatfa(x)≠*∧fa(y)≠*→fa(x)=fa(y) is equivalent to(fa(x)=*)∨(fa(y)=*)∨(fa(x)=fa(y)). Thus, the two objects that satisfy TORP(x,y) but not LTORP(x,y) are only those satisfying OP(x)∩OP(y)=ϕ.Generally speaking, two objects are inlimited tolerance relation if they are in one of the two cases. The first case is that all attribute values of the two objects are missing. The second is a case where there is at least an attribute having an ordinary value for both objects and the two objects have the same value for those attributes. Obviously, limited tolerance relation is reflexive and symmetric but not necessarily transitive.Thus,limited tolerance class is denoted by
(8)LTP(x)={y∈U∣LTORP(y,x)}.Based on that, approximation space is defined as follows:(9)apprLT_PX={x∈U∣LTP(x)⊆X},apprLT¯PX={x∈U∣LTP(x)∩X≠ϕ}.Wang [7] also proved that tolerance relation and similarity relation are the two extremities for extending indiscernibility relation, and limited tolerance relation happens to be between tolerance and similar relations,
(10)apprT_PX⊆apprLT_PX⊆apprS_PX,apprS¯PX⊆apprLT¯PX⊆apprT¯PX.


## 3. Probability of Matching

“The most common attribute value of an attribute” is a method of handling missing value summarized by Grzymala-Busse [9, 10]. In this method, missing values are replaced by the most common value of the attribute. In different words, a missing attribute value is replaced by the most probable known attribute value, where such probabilities are represented by frequencies of corresponding attribute values. This method of handling missing attribute values is implemented, for example, in well-known machine learning algorithm CN2 [11]. Grymala-Busse illustrated the method [10] by the example from Table 1. For case x1, the value of headacheis replaced by yessince in Table 1 the attribute headachehas four values yesand two values no. Similarly, for case x3, the value of temperatureis highsince the attribute temperaturehas the value very highonce, normaltwice, and highthree times.Using this notion, suppose that the value domains are known, first, we define minimum probability that each value of an attribute appears based on the frequency in the dataset for each concept. Then, the minimum probability that two objects have the same values is defined in order to propose a tolerance relation.The probability that a valuej∈Va,j≠* appears as a value of a certain object is between |Va(j)|/|U| and {|Va(j)|+|Va(*)|}/|U|, where Va(j) and Va(*) are sets of objects whose value of attribute “a” is “j” and “*,” respectively. If fa(x)≠*, that is, the attribute value of an object x is not missing, the probability that fa(x) appears is between |E{a}(x)|/|U| and {|E{a}(x)|+|Va(*)|}/|U|.Let us define probabilitiesρa(oba(j)) andρa(x), which are the minimum probabilities that a value of attribute “a” is “j,” oba(j) is an object whose value of attribute “a” is “j,” and the minimum probability that an attribute value fa(x)≠* appears, respectively. The minimum probabilities are given as follows:
(11)ρa(oba(j))=|Va(j)||U|,ρa(x)=|E{a}(x)||U|,iffa(x)≠*.The minimum probabilities take a value in[0,1] in general, but they are greater than zero if oba(j)∈U  and x∈U and less than one when there is at least a missing value for “a” in U.The minimum probabilities of attribute values are illustrated in the Table2. From this table, we can see that in the information system in Table 1, the value high of temperature occurs more frequently than the other values. The most frequent values of headache and nausea happen to be “yes.”Table 2
Minimum probabilities of attribute values.
Attribute
Value
Probabilities
Temperature
Very high
0.125
Temperature
High
0.375
Temperature
Normal
0.250
Headache
Yes
0.500
Headache
No
0.250
Nausea
Yes
0.500
Nausea
No
0.375Now, we define the probability of matching between objectsx and y on an attribute a if one of their attribute values is missing.Definition 1.
LetI=(U,A) be an incomplete information system. Given that a∈A andx,y∈U, if the value of either x or y is missing on “a,” probability of matching between x and y on “a” denoted by θa(x,y) is defined as the minimum estimation of probability that x and y take the same value on “a” and is given by the following equation:
(12)θa(x,y)={ρa(x),iffa(x)≠*,.hfa(y)=*,ρa(y),iffa(x)=*,.hfa(y)≠*,∑j∈Va,j≠*{ρa(oba(j))}2,iffa(x)=*,.hfa(y)=*,whenx≠y. Otherwise, θa(x,y)=θa(x,x)=1.If one of the two objects has a certain value,fa(x),  for example, the least probability value that fa(x) appears in attribute of y is ρa(x) assuming that the other objects with missing values on a take another value j≠fa(x). If both of them are missing, we take the sum of joint probability on all values in attribute domain within the same explanation.It should be noted thatρa(x)>0 and ρa(y)>0 in the case because x,y∈U, and that ρa(oba(j))>0at least for a value j≠* because we do not assume the case where all objects take the unknown value for an attribute. They are also less than 1.0, because x or/and y takes the missing value. Thus, in the case of x≠y,0<θa(x,y)<1 is guaranteed.Take the attributea = temperature, for example, in Table 1. The minimum probability that value fa(x3) is the same as fa(x1) is 0.375, and the minimum probability that the value fa(x3) is similar to fa(x8) is 0.1252+0.3752+0.252=0.219.


## 4. Extended Tolerance Relation

To define whether objectsx and y are tolerant or not, we introduce the concept tolerance degree between two objects by combining two relation indexes. One takes a binary value representing a binary equivalence relation defined by attributes with a known value in both the objects. The other is an index defined by attributes with the missing value in either of the objects. It is obtained from probability of matching assuming that θa(x,y) is independent of each other among attributes.Limited tolerance relation was defined basically using attributes whose values are available in both x and y. We define a binary function that represents that LT relation can hold between the objects in the case of OP(x)∩OP(y)≠ϕ and utilize it.Definition 2.
LetI=(U,A) be an incomplete information system and attribute set P⊆A and x,y∈U. LetOP(x)={a∣a∈P,fa(x)≠*}; the equivalence existence is defined by the following function:
(13)ΘP(x,y){1,if|OP(x)∩OP(y)|if>0∧(fa∀a∈OP(x)∩OP(y),>01∧if1fa(x)=fa(y))0,otherwise;ΘP(x,x)=1 is assumed in any case.It is clear that objectsx,y have LT relation if  ΘP(x,y)=1, but ΘP(x,y)=1 does not hold necessarily even if x,y have LT relation; for example, in the case where for all  a∈P,fa(x)=fa(y)=* for different x and y.Now, we define atolerance degree between x and y by combining the equivalence existence with probability of matching defined in the previous section.Definition 3.
LetI=(U,A) be an incomplete information system and attribute set P⊆A and x,y∈U. The parameterized tolerance degree of x and y in terms of P is defined as follows:
(14)φPm(x,y)={0,if∃a∈OP(x)∩OP(y)≠ϕ,fa(x)≠fa(y),m∏∀a∈P-(OP(x)∩OP(y))θa(x,y)+(1-m)ΘP(x,y),otherwise,wherem is a parameter taking a value in (0, 0.5]. If OP(x)∩OP(y)=P, ∏∀a∈P-(OP(x)∩OP(y))θa(x,y)=1 is assumed. Thus, φPm(x,y)=1 in the case. Obviously, φPm(x,x)=1 and φPm(x,y)=φPm(y,x). Then, the reason why m∈(0,0.5] shall be explained below.In (14), when ΘP(x,y)=1, that is, when fa(x)=fa(y) for all a∈OP(x)∩OP(y), it is satisfied that 1-m<φPm(x,y)≤1.0.φPm(x,y)=1 holds only in two cases; one is the case where x=y, and the other is the case where OP(x)∩OP(y)=P and ∀a∈P, fa(x)=fa(y).WhenΘP(x,y)=0, there are two cases; one is a case where there is a∈OP(x)∩OP(y)≠ϕ such that fa(x)≠fa(y). In this case, φPm(x,y)=0. The other is the case where OP(x)∩OP(y)=ϕ. In this case, 0<φPm(x,y)<m, considering that 0<θa(x,y)<1 for x≠y. Therefore, m could be understood as a value that separates the following cases:(a)
φPm(x,y)>1-m:OP(x)∩OP(y)≠ϕ and x, y have the same value for all attributes in OP(x)∩OP(y);(b)
m>φPm(x,y)>0:  OP(x)∩OP(y)=ϕ;(c)
φPm(x,y)=0: OP(x)∩OP(y)≠ϕ and  x,y  have a different value at least for an attribute in OP(x)∩OP(y).In order to separate the cases between (a) and (b),m should satisfy 1-m≥m. From those above, we have the constraint of m∈(0,0.5]. If m<0.5, φPm(x,y) never takes a value between m and 1-m. Hence, we define the tolerance degree by fixing m=0.5, though φPm(x,y) never takes the value of 0.5 as known from the conditions of (a) and (b):
(15)φP(x,y)={0,if∃a∈OP(x)∩OP(y),fa(x)≠fa(y),12∏∀a∈P-(OP(x)∩OP(y))θa(x,y)+12ΘP(x,y),otherwise.The tolerance degree withm=0.5 lets us differentiate the three cases discussed before by seeing whether the degree is greater/less than 0.5 or whether it is greater than/equal to zero. This feature might be useful, because the users can control conditions of the tolerance based on equivalence existence and probability of matching with just a threshold value. This process shall be discussed in the next step.Table3 shows the tolerance degree among objects in terms of all attributes.Table 3
Tolerance degree among objects in terms of all attributes.
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
1
0
0.547
0
0
0
0
0.035
x
2
0
0
0
0
0
0.531
x
3
0
0
0
0
0
x
4
0.750
0
0
0.594
x
5
0
0
0.047
x
6
0
0.547
x
7
0In fact, we can choose another probability of matching on an attribute for (14) and (15). For example, instead of using θa(x,y) defined in (12), we can choose θa(x,y)=1/|Va| [5, 6]. The choice might depend on probability distribution of attribute values in each system.The probabilistic terms in our tolerance degree look similar to those used by Stefanowski [6]. However, our approach uses probabilistic terms as pieces of evidence to derive tolerance relations. Furthermore, this term is combined with equivalence existence to define the relation. On the other hand, in probabilistic approach proposed in [6], the authors suppose a priori assumption that there exists a uniform probability distribution on every attribute domain and compute tolerance classes based on the joint probability distribution. Their aim seems to define approximation spaces applicable in many cases. Such tolerance classes could be used in some applications, but we believe not in most.Now, we defineextended tolerance relation by controlling tolerance degree with a threshold.Definition 4.
Given that incomplete information systemI=(U,A) and attribute setP⊆A and given a threshold α, the extended tolerance relation is defined as follows:
(16)ETRPα(x,y)⟺φP(x,y)≥α.It is easy to observe that this relation is reflexive and symmetric but not necessarily transitive. In Table3, if a threshold α=0.5 is given, x4is tolerant to x5based on this relation.By changing the threshold, we are able to get the same results as those by the relations discussed in the previous sections. For example, in the case oftolerance relation, the set of objects tolerant to x5 is {x4,x5,x8} in Table 1. From Table 3, we also get {x4,x5,x8} as the set of objects tolerant to x5 using extended tolerance relation with α=0.01. Similarly, we have the same result as limited tolerance relation: {x4,x5}, if α=0.5.Now, we can formalize these connections by the following propositions.Proposition 5.
LetI=(U,A)be an incomplete information system. Given that P⊆Aand x∈U, if α→0,then ETRPα(x,y)⇔TORP(x,y).This proposition shows that withα→0, extended tolerance relation can get the same results as tolerance relation.Proof.
Whenα→0,ETRPα(x,y) is obtained as
(17)ETRPα(x,y)⟺φP(x,y)>0⟺[OP(x)∩OP(y)=ϕ∧∀a∈P,hhhhhθa(x,y)>0]∨[∀a∈OP(x)∩OP(y)≠ϕ,fa(x)=fa(y)]⟺[∀a∈P,(fa(x)=*)∨(fa(y)=*)]∨[∀a∈OP(x)∩OP(y)≠ϕ,fa(x)=fa(y)]⟺TORP(x,y).Proposition 6.
LetI=(U,A)be an incomplete information system. Given that P⊆Aand x∈U, if α=0.5, then ETRPα(x,y)⇒LTORP(x,y)for any x,y, and ETRPα(x,y)⇐LTORP(x,y) except the case such thatOP(x)=OP(y)=ϕ.This proposition notices that withα=0.5, extended tolerance relation is an expansion of limited tolerance relation.Proof.
Whenα=0.5,ETRPα(x,y) is obtained as
(18)ETRPα(x,y)⟺φP(x,y)≥0.5⟺ΘP(x,y)=1⟺[OP(x)∩OP(y)≠ϕ]∧[∀a∈OP(x)∩OP(y),fa(x)=fa(y)]⟹LTOPP(x,y).
Then, it is evident thatLTORP(x,y)⇒ETRPα(x,y) except the case where OP(x)=OP(y)=ϕ.Proposition 7.
LetI=(U,A)be an incomplete information system. Given that P⊆Aand x∈U, if   α=1.0, then ESRPα(x,y)⇔EQUP(x,y)if x≠y.This proposition shows that withα=1.0, extended tolerance relation is able to get the same results as equivalence relation.Proof.
Consider that(19)ESRPα(x,y)⟺φP(x,y)=1.
As discussed before,φP(x,y)=1 holds only in the two cases where x=y and where OP(x)∩OP(y)=P and for alla∈P,fa(x)=fa(y), which is equivalent to EQUP(x,y).It should be noted that similarity/tolerance relations discussed in this paper are introduced to cope with incomplete information. However, we could also define those relations even in complete information tables. For example, the relation “subclass-of” is a similarity relation. It is clearly transitive, but not necessarily symmetric. We can also take the relation “friend-of” as an example of tolerance relation and examine its properties in the same way.Definition 8.
LetI=(U,A)  be an incomplete information system. Given that P⊆A  and x,y,z∈U, if φP(y,x)>φP(z,x), then  y  is more tolerant to  x  than  z  based on extended tolerance relation.Property 1.
LetI=(U,A)be an incomplete information system. Given that P⊆A and x,y,z∈U, if OP(x)∩OP(y)≠ϕ,foralla∈OP(x)∩OP(y),fa(x)=fa(y), and OP(x)∩OP(z)=ϕ, then y is more tolerant to x than z based on extended tolerance relation.Proof.
SinceOP(x)∩OP(y)≠ϕ,foralla∈OP(x)∩OP(y),fa(x)=fa(y), from (15) we have φP(y,x)>0.5. Also, from (15) with OP(x)∩OP(z)=ϕ, we have φP(z,x)<0.5. Hence, φP(y,x)>φP(z,x). This is defined as  y  is more tolerant to  x  than  z  based on extended tolerance relation.Now, with a relation, we can derive a neighbourhood, which consists ofsuccessor and predecessor sets, of an object [19, 20]. Due to symmetric property of extended tolerance relation, successor is the same set as predecessor. Hence, for this relation, we can introduce for any object x∈U a tolerant set:
(20)ETPα(x)={y∈U∣ETRPα(y,x)}.In the example shown in Table1, given the thresholdα=0.04,  P=A, from Table 3, we have
(21)ETA0.04(x8)={x2,x4,x5,x6,x8}.Property 2.
LetI=(U,A) be an incomplete information system,  P⊆A. Then, for all x∈U, if α≤β, then ETPα(x)⊇ETPβ(x).Proof.
Consider the following:(22)ETPα(x)={y∈U∣ETRPα(y,x)}={y∈U∣φP(y,x)≥α}={y∈U∣φP(y,x)≥β}∪{y∈U∣α≤φP(y,x)<β}=ETPβ(x)∪{x∈U∣α≤φP(y,x)<β}⊇ETPβ.Hence, the cardinality of the tolerance set ofx shall decrease if we increase the threshold to control the tolerance degree.


## 5. Lower and Upper Approximations

For complete decision tables, lower and upper approximations are defined on the basis ofindiscernibility relation [1, 2]. They can also be defined in different ways, for example, using set elements or concepts represented by subsets. In the case of nonequivalence relations, which may not need to be reflexive, symmetric nor transitive, approximation spaces defined in such different ways may lead to variant results [14]. This section shall introduce lower and upper approximation definitions based on singleton, subset, and concept methods which are first studied and generalized by Grzymala-Busse [14, 19].


### 5.1. Singleton Definition

Singleton lower approximation is(23)SingleAppr_PαX={x∈U∣ETPα(x)⊆X}.Singleton upper approximation is(24)SingleAppr¯PαX={x∈U∣ETPα(x)∩X≠ϕ}.In the example shown in Table1, given the thresholdα=0.6 and  P=A, from Table 3, we have approximation space for the concept X={x∈U∣Decison(x)=no}:
(25)SingleAppr_P0.6X={x3,x6,x7},SingleAppr¯P0.6X={x3,x4,x5,x6,x7}.


### 5.2. Subset Definition

Subset lower approximation is(26)SubAppr_PαX=⋃{ETPα(x)∣x∈U,ETPα(x)⊆X}.Subset upper approximation is(27)SubAppr¯PαX=⋃{ETPα(x)∣x∈U,ETPα(x)∩X≠ϕ}.


### 5.3. Concept Definition

Concept lower approximation is(28)ConAppr_PαX=⋃{ETPα(x)∣x∈X,ETPα(x)⊆X}.Concept upper approximation is(29)ConAppr¯PαX=⋃{ETPα(x)∣x∈X,ETPα(x)∩X≠ϕ}.The difference between subset and concept definitions may be missed easily. In subset definition, extended tolerance classes of all elements in the universal set are examined, while only elements inX are examined in the case of concept definition.Obviously, singleton lower and upper approximations ofX are subsets of the subset lower and upper approximations of X, respectively. The subset lower approximation is the same set as the concept lower approximation. The concept upper approximation, however, is a subset of the subset upper approximation.Rough set approximations could be generalized with some other approaches [20–22]. Actually, the above three definitions are classified as constructive rough set formulations by Yao [20], where rough set formulations are divided into two different groups: constructive and algebraic methods. The notion of singleton definition is indeed the same as the element based definition suggested by Yao. Meanwhile, subset definition is an expansion of concept definition and also undoubtedly is the same as the granule based definition in the Yao study. These definitions are special cases of the subsystem based definition by Yao when the covering is the set of equivalence/similarity/tolerance classes.


### 5.4. Properties of Approximations

Approximation spaces defined based onextended tolerance relation have some properties suggested by Pawlak [1, 2] as well as other properties. We discuss them in detail below.Property 3.
LetI=(U,A) be an incomplete information system, X,Y⊆U,  and  P,Q⊆A. Table 4 shows which properties of the original rough set model are satisfied with singleton, subset, and concept definitions.Table 4
Properties of approximations based on the three definitions.
Properties
Singleton
Subset
Concept
1a
appr
_
P
α
X
⊆
X
✓
✓
✓
1b
X
⊆
appr
¯
P
α
X
✓
✓
✓
2a
appr
_
P
α
ϕ
=
ϕ
✓
✓
✓
2b
appr
¯
P
α
ϕ
=
ϕ
✓
✓
✓
3a
appr
_
P
α
U
=
U
✓
✓
✓
3b
appr
¯
P
α
U
=
U
✓
✓
✓
4a
X
⊆
Y
⇒
appr
_
P
α
X
⊆
appr
_
P
α
Y
✓
✓
✓
4b
X
⊆
Y
⇒
appr
¯
P
α
X
⊆
appr
¯
P
α
Y
✓
✓
✓
5a
appr
_
P
α
(
X
∪
Y
)
⊇
appr
_
P
α
X
∪
appr
_
P
α
Y
✓
✓
✓
5b
appr
¯
P
α
(
X
∪
Y
)
=
appr
¯
P
α
X
∪
appr
¯
P
α
Y
✓
✓
6a
appr
_
P
α
(
X
∩
Y
)
=
appr
_
P
α
X
∩
appr
_
P
α
Y
✓
6b
appr
¯
P
α
(
X
∩
Y
)
⊆
appr
¯
P
α
X
∩
appr
¯
P
α
Y
✓
✓
✓
7a
appr
_
P
α
X
=
appr
_
P
α
(
appr
_
P
α
X
)
✓
✓
7b
appr
_
P
α
X
=
appr
¯
P
α
(
appr
_
P
α
X
)
7c
appr
¯
P
α
X
=
appr
¯
P
α
(
appr
¯
P
α
X
)
7d
appr
¯
P
α
X
=
appr
_
P
α
(
appr
¯
P
α
X
)
8a
appr
_
P
α
X = ~(appr¯Pα(~X))
✓
✓
✓
8b
appr
¯
P
α
X = ~(appr_Pα(~X))
✓
✓
✓
“✓” indicates that the property is satisfied. appr_PαX and appr¯PαX are lower and upper approximations that can be defined by singleton, subset, and concept methods.
~
X: denotes a complementary set of X.These properties within our approach can be proved the same as those in the Grzymala-Busse and Wojciech Rzasa study [19] and the Pawlak research [2]. Approximation spaces of those definition methods, in general, do not have properties 7a–7d. However, they are likely to satisfy the weaker versions of 7a–7d, which are defined by Yao [21].Besides this, our tolerance relation is controlled by the threshold of tolerance degree. Thus, new properties for the threshold can be introduced as shown below.Property 4.
LetI=(U,A) be an incomplete information system, X⊆U,and  P⊆A. The following properties shall hold for arbitrary lower approximation appr_PαX  and upper approximation appr¯PαX defined by singleton, subset, and concept methods:(9a)
ifα≤β⇒appr_PαX⊆appr_PβX,(9b)
ifα≤β⇒appr¯PαX⊇appr¯PβX.Proofs.Proof of (9a).
Take an elementx∈appr_PαX. From any of the lower approximation definitions, ETPα(x)⊆X is derived. Since ETPα(x)⊇ETPβ(x) from Property 2, we get that ETPβ(x)⊆X, and then x∈appr_PβX. Thus, if x∈appr_PαX, then x∈appr_PβX(note that x∈ETPαX).Proof of (9b).
Take an elementx∈appr¯PβX. From any of the upper approximation definitions, ETPβ(x)∩X≠ϕ is derived. Since ETPα(x)⊇ETPβ(x) from Property 2, we get that ETPα(x)∩X≠ϕ, and then x∈appr¯PαX. Thus, if x∈appr¯PβX, then x∈appr¯PαX(note that x∈ETPαX).


## 5.1. Singleton Definition

Singleton lower approximation is(23)SingleAppr_PαX={x∈U∣ETPα(x)⊆X}.Singleton upper approximation is(24)SingleAppr¯PαX={x∈U∣ETPα(x)∩X≠ϕ}.In the example shown in Table1, given the thresholdα=0.6 and  P=A, from Table 3, we have approximation space for the concept X={x∈U∣Decison(x)=no}:
(25)SingleAppr_P0.6X={x3,x6,x7},SingleAppr¯P0.6X={x3,x4,x5,x6,x7}.


## 5.2. Subset Definition

Subset lower approximation is(26)SubAppr_PαX=⋃{ETPα(x)∣x∈U,ETPα(x)⊆X}.Subset upper approximation is(27)SubAppr¯PαX=⋃{ETPα(x)∣x∈U,ETPα(x)∩X≠ϕ}.


## 5.3. Concept Definition

Concept lower approximation is(28)ConAppr_PαX=⋃{ETPα(x)∣x∈X,ETPα(x)⊆X}.Concept upper approximation is(29)ConAppr¯PαX=⋃{ETPα(x)∣x∈X,ETPα(x)∩X≠ϕ}.The difference between subset and concept definitions may be missed easily. In subset definition, extended tolerance classes of all elements in the universal set are examined, while only elements inX are examined in the case of concept definition.Obviously, singleton lower and upper approximations ofX are subsets of the subset lower and upper approximations of X, respectively. The subset lower approximation is the same set as the concept lower approximation. The concept upper approximation, however, is a subset of the subset upper approximation.Rough set approximations could be generalized with some other approaches [20–22]. Actually, the above three definitions are classified as constructive rough set formulations by Yao [20], where rough set formulations are divided into two different groups: constructive and algebraic methods. The notion of singleton definition is indeed the same as the element based definition suggested by Yao. Meanwhile, subset definition is an expansion of concept definition and also undoubtedly is the same as the granule based definition in the Yao study. These definitions are special cases of the subsystem based definition by Yao when the covering is the set of equivalence/similarity/tolerance classes.


## 5.4. Properties of Approximations

Approximation spaces defined based onextended tolerance relation have some properties suggested by Pawlak [1, 2] as well as other properties. We discuss them in detail below.Property 3.
LetI=(U,A) be an incomplete information system, X,Y⊆U,  and  P,Q⊆A. Table 4 shows which properties of the original rough set model are satisfied with singleton, subset, and concept definitions.Table 4
Properties of approximations based on the three definitions.
Properties
Singleton
Subset
Concept
1a
appr
_
P
α
X
⊆
X
✓
✓
✓
1b
X
⊆
appr
¯
P
α
X
✓
✓
✓
2a
appr
_
P
α
ϕ
=
ϕ
✓
✓
✓
2b
appr
¯
P
α
ϕ
=
ϕ
✓
✓
✓
3a
appr
_
P
α
U
=
U
✓
✓
✓
3b
appr
¯
P
α
U
=
U
✓
✓
✓
4a
X
⊆
Y
⇒
appr
_
P
α
X
⊆
appr
_
P
α
Y
✓
✓
✓
4b
X
⊆
Y
⇒
appr
¯
P
α
X
⊆
appr
¯
P
α
Y
✓
✓
✓
5a
appr
_
P
α
(
X
∪
Y
)
⊇
appr
_
P
α
X
∪
appr
_
P
α
Y
✓
✓
✓
5b
appr
¯
P
α
(
X
∪
Y
)
=
appr
¯
P
α
X
∪
appr
¯
P
α
Y
✓
✓
6a
appr
_
P
α
(
X
∩
Y
)
=
appr
_
P
α
X
∩
appr
_
P
α
Y
✓
6b
appr
¯
P
α
(
X
∩
Y
)
⊆
appr
¯
P
α
X
∩
appr
¯
P
α
Y
✓
✓
✓
7a
appr
_
P
α
X
=
appr
_
P
α
(
appr
_
P
α
X
)
✓
✓
7b
appr
_
P
α
X
=
appr
¯
P
α
(
appr
_
P
α
X
)
7c
appr
¯
P
α
X
=
appr
¯
P
α
(
appr
¯
P
α
X
)
7d
appr
¯
P
α
X
=
appr
_
P
α
(
appr
¯
P
α
X
)
8a
appr
_
P
α
X = ~(appr¯Pα(~X))
✓
✓
✓
8b
appr
¯
P
α
X = ~(appr_Pα(~X))
✓
✓
✓
“✓” indicates that the property is satisfied. appr_PαX and appr¯PαX are lower and upper approximations that can be defined by singleton, subset, and concept methods.
~
X: denotes a complementary set of X.These properties within our approach can be proved the same as those in the Grzymala-Busse and Wojciech Rzasa study [19] and the Pawlak research [2]. Approximation spaces of those definition methods, in general, do not have properties 7a–7d. However, they are likely to satisfy the weaker versions of 7a–7d, which are defined by Yao [21].Besides this, our tolerance relation is controlled by the threshold of tolerance degree. Thus, new properties for the threshold can be introduced as shown below.Property 4.
LetI=(U,A) be an incomplete information system, X⊆U,and  P⊆A. The following properties shall hold for arbitrary lower approximation appr_PαX  and upper approximation appr¯PαX defined by singleton, subset, and concept methods:(9a)
ifα≤β⇒appr_PαX⊆appr_PβX,(9b)
ifα≤β⇒appr¯PαX⊇appr¯PβX.Proofs.Proof of (9a).
Take an elementx∈appr_PαX. From any of the lower approximation definitions, ETPα(x)⊆X is derived. Since ETPα(x)⊇ETPβ(x) from Property 2, we get that ETPβ(x)⊆X, and then x∈appr_PβX. Thus, if x∈appr_PαX, then x∈appr_PβX(note that x∈ETPαX).Proof of (9b).
Take an elementx∈appr¯PβX. From any of the upper approximation definitions, ETPβ(x)∩X≠ϕ is derived. Since ETPα(x)⊇ETPβ(x) from Property 2, we get that ETPα(x)∩X≠ϕ, and then x∈appr¯PαX. Thus, if x∈appr¯PβX, then x∈appr¯PαX(note that x∈ETPαX).


## 6. Reducts and Core

The concept of reducts and core was introduced by Pawlak [2] for complete information system. In this section, we shall propose a method to derive reduct and core for incomplete information systems based on extended tolerance relation. A subset of conditional attributes P⊆Ais a reduct of an incomplete information system, if the tolerance classes induced by P are the same as the tolerance classes induced by all attributes in set A and no attribute can be removed from set P without changing the tolerance classes.Definition 9.
The comparison, Boolean function between two relations in terms of two attribute setsP,Q⊆A in an incomplete information system is defined as
(30)ϖα(P,Q)=(∀(x,y)∈U×U,ETRPα(x,y)⟺ETRQα(x,y)).Ifϖα(P,Q)=1, the two relations developed from two different attribute sets P,Q make the same tolerance classes.Definition 10.
In the incomplete decision table, the function∂P:U→F(Vd), where P⊆A and F(Vd) is the power set of Vd, is defined as
(31)∂Pα(x)={i∣i=fd(y),y∈ETRPα(x)},wherefd(y) is the decision value of an object y.Definition 11.
The comparison Boolean function between two relations in terms of attribute setsP,Q⊆A in an incomplete decision table is defined as
(32)ϖ′α(P,Q)=(ETRPα(x,y)⟺ETRQα(x,y))∀(x,y)∈U×Γx,ETRPα(x,y)⟺ETRQα(x,y)),
where
(33)Γx={z∈U:d(z)∉∂Pα(x)}.Proposition 12.
The attributea∈A is indispensable in A if and only if ϖα(A-{a},A)=0 for incomplete information system and ϖ′α(A-{a},A)=0 for incomplete decision tables.This proposition is applied to both incomplete information systems and incomplete decision tables. Consider thatϖα(A-{a},A)=0 or ϖ′α(A-{a},A)=0  means that if a is removed from A, the tolerance classes based on extended tolerance relation in terms of A-{a} are different from the tolerance classes based on A. Hence, a is indispensable in A.Proof.
a is indispensable in A if and only if (∃(x)∈U,ETA-{a}α(x)≠ETAα(x)) if and only if (∃(x,y)∈U×U,ETRA-{a}α(y,x)⇎ETRPα(y,x))ϖα(A-{a},A)=0, from Definition 9, or ϖ′α(A-{a},A)=0 from Definition 11.Definition 13.
The core ofA is the set of all indispensable attributes and defined by core(A)={a∈A∣ϖα(A-{a},A)=0} for incomplete information system and core(A)={a∈A∣ϖ′α(A-{a},A)=0} for incomplete decision table.Proposition 14.
A subsetP⊆A is a reduct of the incomplete information system (or decision table) with threshold α if and only if(i)
ϖα(P,A)=1for incomplete information systems (orϖ′α(P,A)=1for decision tables);(ii)
For alla∈P,ϖα(P-{a},P)=0for incomplete information systems (or∀a∈P,ϖ′α(P-{a},P)=0for decision tables).Proof.
Following the definition of reducts stated at the beginning of Section6,   P⊆A is a reduct if and only if (i)
the tolerance classes induced byP are the same as the tolerance classes induced by all attributes in set A;(ii)
no attribute can be removed from setP without changing the tolerance classes.
Based on Definitions9 and 10, we have (i) ⇔ϖα(P,A)=1 for incomplete information systems (or ⇔ϖ′α(P,A)=1 for decision tables).
For the second condition, (ii) means all attributes inP are indispensable. Consequently, (ii) ⇔for all a∈P,ϖα(P-{a},P)=0 for incomplete information systems (or ⇔foralla∈P,ϖ′α(P-{a},P)=0 for decision tables), according to Proposition 12.In the example shown in Table1, given the thresholdα=0.6, using the method of deriving core, all attributes including temperature, headache, and nausea are indispensable. Hence, in this system, {temperature, headache, nausea} is the core. The core also happens to be the only one reduct of this incomplete information system with α=0.6.


## 7. Conclusion

This paper studies a rough set theory for incomplete information systems and establishes a new model based on tolerance degree calledextended tolerance relation based rough set model. Frequency of attribute values appearing in the decision table is used to estimate the probability of matching among data items on an attribute. Then, tolerance degree is calculated based on the existence of equivalence on some attributes and probability of matching. Given a threshold to control tolerance degree, a tolerance relation is defined.The approach is an extension of some rough set models and could solve the problem existing intolerance relation of Kryszkiewicz. By adjusting the threshold, we are able to get the same results as tolerance, limited tolerance, and equivalence relations. The variable threshold also gives us a means to widen or thin the boundary region between lower and upper approximations. Actually, various lower and upper approximations are obtained using the approach, and the user can choose a threshold that suits his/her requirements.The paper also discussed the mathematical properties ofextended tolerance relation based rough set model and proposed a method to derive reducts and core.Further research includes finding an algorithm to collect rules within the approach discussed. That is a significant application of rough set theory in knowledge acquisition from data.



---

*Source: 372091-2013-09-30.xml*