Extended rough set model based on modified data-driven valued tolerance relation

1 Introduction

Classical rough set theory developed by Pawlak in 1982 [1], as a powerful soft computing tool to handle imprecise, uncertain, and vague information, has been extensively and successfully applied in the field of machine learning, data mining and decision analysis [2–8]. The classical rough set theory based on the conventional indiscernibility relation, is not suitable for analyzing incomplete information systems (IIS), where some attribute values are unknown or missing. But in practice, because of the errors of data measuring, the limitation of acquiring data, some human factors, etc., IIS often occur in knowledge acquisition. The semantics of missing attribute values in IIS has been analyzed by many researchers. Generally, there are four kinds of missing attribute values: "lost values" (the values that were recorded but currently are unavailable), "do not care" conditions (the original values were irrelevant), restricted "do not care" conditions (similar to ordinary "do not care" conditions but interpreted differently, these missing attribute values may occur when in the same data set where there are "lost values" and "do not care" conditions), and "attribute-concept values" (these missing attribute values may be replaced by any attribute value limited to the same concept) [9–15]. Therefore, many researchers have paid attention to IIS in recent years and endeavored to find out solutions. There are usually two methods in rough set theory to deal with IIS: data reparation [16–20] and model extension [21–27]. Compared with data reparation, model extension does not change the original information of IIS. At present, various extensions of classical rough set model have been proposed, in which the indiscernibility relation was extended to some non-equivalence relations (or called generalized indiscernibility relations) such as tolerance relation [9], non-symmetric similarity relation [10], limited tolerance relation [11], valued tolerance relation [12] and characteristic relation [13] etc. The generalized indiscernibility relation is a basic and core concept of rough set in incomplete information system. Attribute reduction and rule extraction are both based on the generalized indiscernibility relation. The classification performance of the generalized indiscernibility relation will affect the results of attribute reduction and rule extraction. However, these existing generalized indiscernibility relations have their own limitations, so proposing a new generalized indiscernibility relation, which can get better classification results, is essential and important.

The tolerance relation is too relaxed. In the tolerance relation, two objects that do not have any known same attribute values may be considered as indiscernible, and classified in the same class. The non-symmetric similarity relation is too strict. In the non symmetric similarity relation, two objects having a lot of known same attribute values may be separated, and classified in the different classes. In the limited tolerance relation, two objects may be considered as similar when they have only one known same attribute value. This condition is too lenient for an IIS with a large number of attributes. The characteristic relation, which is a generalization of both tolerance relation and non-symmetric similarity relation, cannot avoid their limitations. In the valued tolerance relation, we must know the prior probability distribution of the IIS in advance. Unfortunately, this is very difficult for a new IIS with some missing attribute values. So, it is usually supposed that there exists a uniform distribution among the attribute values. Obviously, this is too subjective and unreasonable. In addition, the threshold of tolerance degree is usually selected based on the prior domain knowledge, and it is also difficult to select a suitable threshold for different IIS.

Based on the idea of data-driven data mining [28], data-driven valued tolerance relation was proposed by Wang [29]. The frequency of an attribute value is approximately regarded as the probability of appearance of this value, and then, an approximate probability distribution among the attribute values can be derived. This calculation method of tolerance degree does not require any prior knowledge except the data set. An auto-selection algorithm of tolerance degree threshold is proposed, which does not require any prior domain knowledge except the data set. The data-driven valued tolerance relation can resolve the problems of the valued tolerance relation. However, when predicting probability of the unknown attribute value of an object, it regards the frequency of an attribute value approximately as the probability of appearance of this value, without considering the effects of other known attribute values of this object on predicting unknown attribute value. In order to solve the defect of data-driven valued tolerance relation, In this paper, considering both the frequency of the known attribute values and the influence weight to predict the unknown attribute values. Modified data-driven valued tolerance relation (MDVT) is defined, which can make full use of the prior knowledge of information system. On this basis, an extended rough set model based on modified data-driven valued tolerance relation is proposed. Some properties of the new model are analyzed. Experimental results show that the MDVT can get better classification results than other generalized indiscernibility relations.

The rest of the paper is organized as follows. In Section 2, we review several kinds of typical generalized indiscernibility relations as our foundations for the subsequent discussion. In Section 3, modified data-driven valued tolerance relation is defined. In Section 4, extended rough set model based on modified data-driven valued tolerance relation is proposed. Some properties of the new model are analyzed. Some simulation experimental results are discussed in section 5. At last, in section 6, we conclude this paper.

2 Typical generalized indiscernibility relations

In this section, we review relevant definitions of tolerance relation, non-symmetric similarity relation, limited tolerance relation, and data-driven valued tolerance relation as our foundations for the subsequent discussion.

Formally, an information system (IS) is a quadruple (U, AT, V, f), where U is a non-empty finite set of objects, called the universe; AT is a non-empty finite set of attributes; V is the union of attribute domains V = ∪ _a∈ATV _a , V _a where is the value set of attribute a; f : U × AT → V is an information function which assigns particular values from domains of attribute to objects, such as ∀a ∈ AT, x ∈ U, f (x, a) ∈ V _a , where f (x, a) denotes the value of attribute for object. If some attribute values are missing, the IS is an incomplete information system (IIS), otherwise it is a complete information system (CIS). In an IIS, the missing attribute value is denoted by "*".

In this section, to solve the limitations of the data-driven valued tolerance relation, considering both the frequency of the known attribute values and the influence weight to predict the unknown attribute values, and then, a modified data-driven valued tolerance relation is defined.

Definition 6. Consider attribute b of IIS (U, AT, V, f) and set V b ′ = { ( k b 1 , b 1 ) , ( k b 2 , b 2 ) , ⋯ , ( k b m , b m ) } , where b₁, b₂, ⋯ , b _m are all known attribute values of b, and k b i denotes the cardinality of set {x∈ U|b (x) = b _i  }. The frequency of appearance of b _i on the attribute b is defined as: f b i = k b i ∑ j = 1 m k b j(13)

Definition 7. Consider attribute b of IIS (U, AT, V, f) and set V b ′ = { ( k b 1 , b 1 ) , ( k b 2 , b 2 ) , ⋯ , ( k b m , b m ) } , where b₁, b₂, ⋯ , b _m are all known attribute values of b, and k b i denotes the cardinality of set {x∈ U|b (x) = b _i  }. Y _i  ={ y ∈ U|b (y) = b _i  } (1 ≤ i ≤ m), For any x ∈ U, b (x) =*, the influence weight of b _i on b (x) is defined as: w b ( b i , x ) = ∑ y ∈ Y i I b ( x , y ) ∑ j = 1 m ∑ y ∈ Y j I b ( x , y )(14)

where I b ( x , y ) = n + 1 | AT | , n  =  | { a ∈ AT|a (x) =   a (y) ≠ * } |, |AT| denotes the cardinality of set AT. Obviously, 0 < I _b  (x, y) ≤ 1. if ∀a ∈ AT - b, a (x) = a (y), then I _b  (x, y) = 1, if ∀a ∈ AT - b, a (x) ≠ a (y), then I b ( x , y ) = 1 | AT | .

Property 1. For IIS (U, AT, V, f), b ∈ AT, set V b ′ = { ( k b 1 , b 1 ) , ( k b 2 , b 2 ) , ⋯ , ( k b m , b m ) } , where b₁,b₂, ⋯,b _m are all known attribute values of b, ∀x ∈ U, then 0 < w _b  (b _i , x) ≤ 1.

Proof. From Definition 7, we have that 0 < ∑ y ∈ Y i I b ( x , y ) ≤ ∑ j = 1 m ∑ y ∈ Y j I b ( x , y ) . Hence, 0 < ∑ y ∈ Y i I b ( x , y ) ∑ j = 1 m ∑ y ∈ Y j I b ( x , y ) ≤ 1 , Therefore, 0 < w _b  (b _i , x) ≤ 1.

Property 2. For IIS (U, AT, V, f), b ∈ AT, set V b ′ = { ( k b 1 , b 1 ) , ( k b 2 , b 2 ) , ⋯ , ( k b m , b m ) } , where b₁,b₂, ⋯,b _m are all known attribute values of b, ∀x ∈ U, then ∑ i = 1 m w b ( b i , x ) = 1 .

Proof. From Definition 7, we have that w b ( b i , x ) = ∑ y ∈ Y i I b ( x , y ) ∑ j = 1 m ∑ y ∈ Y j I b ( x , y ) , Hence, ∑ i = 1 m w b ( b i , x ) = ∑ i = 1 m ∑ y ∈ Y i I b ( x , y ) ∑ j = 1 m ∑ y ∈ Y j I b ( x , y ) = 1 .

Definition 8. Consider attribute b of IIS (U, AT, V, f) and set V b ′ = { ( k b 1 , b 1 ) , ( k b 2 , b 2 ) , ⋯ , ( k b m , b m ) } , where b₁, b₂, ⋯ , b _m are all known attribute values of b, and k b i denotes the cardinality of set {x∈ U|b (x) = b _i  }. the frequency of appearance of b _i on the attribute b is f _{b i} , For any x ∈ U, b (x) =*, the influence weight of b _i on x is w _b  (b _i , x), then the probability of b (x) = b _i is defined as: P ( b ( x ) = b i ) = f b i × w b ( b i , x ) ∑ i = j m ( f b i × w b ( b i , x ) )(15)

Definition 9. Consider attribute b of IIS (U, AT, V, f) and set V b ′ = { ( k b 1 , b 1 ) , ( k b 2 , b 2 ) , ⋯ , ( k b m , b m ) } , where b₁, b₂, ⋯ , b _m are all known attribute values of b, and k b i denotes the cardinality of set {x∈ U|b (x) = b _i  }. For any x ∈ U, b (x) =*, the probability of b (x) = b _i is P (b (x) = b _i ). Then, for IIS (U, AT, V, f), B ⊆ AT, and ∀x, y ∈ U, the probability P_{b} (x, y) that x is similar to y with respect to attribute b ∈ B is calculated as: P { b } ( x , y ) = { 1 , b ( x ) = b ( y ) ∧ b ( x ) ≠ * ∧ b ( y ) ≠ * 0 , b ( x ) ≠ b ( y ) ∧ b ( x ) ≠ * ∧ b ( y ) ≠ * P ( b ( x ) = b i ) , b ( x ) = * ∧ b ( y ) = b i ; P ( b ( y ) = b i ) , b ( x ) = b i ∧ b ( y ) = * ; ∑ i = 1 m ( P ( b ( x ) = b i ) × P ( b ( y ) = b i ) ) , b ( x ) = * ∧ b ( y ) = * ;(16)

Then the probability that two objects are possibly same with respect to attribute set B is calculated as: P B ( x , y ) = ∏ b ∈ B P { b } ( x , y ) × N B ( x , y )(17) where N _B  (x, y) is the weight factor of objects x and y based on the known same attribute values with respect to, i.e., N B ( x , y ) = | { b ∈ B | b ( x ) = b ( y ) ≠ * } | | B |(18) where |X| denotes the cardinality of set X.

Definition 10. For IIS (U, AT, V, f) and attribute set B ⊆ AT, modified data-driven valued tolerance relation MDVT is defined as: MDVT B λ = { ( x , y ) ∈ U × U | P B ( x , y ) ≥ λ } ∪ I U(19)

where I _U  ={ (x, x) |x ∈ U } is the identity relation on U, λ is the threshold of tolerance degree. In this paper, λ > 0 is calculated as follows.

Consider IIS (U, AT, V, f) and tolerance relation T _B with B ⊆ AT. For any x ∈ U, tolerance class T _B  (x) can be calculated. Based on modified data-driven valued tolerance relation, according to the calculation method of tolerance degree, for any y in T _B  (x), tolerance degree P _B  (x, y) can be calculated. Therefore, the threshold in the modified data-driven valued tolerance relation can be calculated as [28]:

λ = min { min x ∈ U { max y ∈ T B ( x ) { P B ( x , y ) } } , max x ∈ U { min y ∈ T B ( x ) { P B ( x , y ) } } }(20) Eq. (20) gives a method to calculate the tolerance degree threshold automatically, which does not require any prior domain knowledge except the data set. The purpose of this calculation method is to select a suitable threshold, which is neither too large nor too small, so the classification results based on the tolerance degree threshold will be reasonable.

Obviously, MDVT B λ is a reflexive and symmetric relation, but not necessarily transitive.

The modified data-driven valued tolerance class for any object x ∈ U is defined as: MDVT B λ ( x ) = { y ∈ U | P B ( x , y ) ≥ λ } ∪ x(21)

Example 2. Let us consider the incomplete information system given in Table 1

From Table 1 we can see that a₄ (x₅) =*, a₄ (x₆) =*, set V a 4 ′ = { ( 2 , 1 ) , ( 2 , 2 ) } , where 1 and 2 are all known attribute values of a₄, Y₁ ={ y ∈ U|a₄ (y) =1 } = { x₁, x₂ }, Y₂ ={ y ∈ U|a₄ (y)  =  2 } = { x₃, x₄ }. We take a₄ (x₅) and a₄ (x₆) for example to illustrate the calculation method of the probability of a₄ (x₅) = 1, a₄ (x₅) = 2, a₄ (x₆) = 1, a₄ (x₆) = 2.

First, we calculate the frequency of appearance of 1 and 2 on the attribute a₄. According to Definition 6, we have f a 4 = 1 = 0.5 f a 4 = 2 = 0.5

Second, we calculate the influence weight of 1 and 2 on a₄ (x₅), a₄ (x₆). According to Definition 7, we have I a 4 ( x 5 , x 1 ) = I a 4 ( x 5 , x 2 ) = 1 I a 4 ( x 5 , x 3 ) = I a 4 ( x 5 , x 4 ) = 0.25 I a 4 ( x 6 , x 1 ) = I a 4 ( x 6 , x 2 ) = 0.25 I a 4 ( x 6 , x 3 ) = I a 4 ( x 6 , x 4 ) = 1 Then we have w a 4 ( 1 , x 5 ) = 1 + 1 1 + 1 + 0.25 + 0.25 = 0.8 w a 4 ( 2 , x 5 ) = 0.25 + 0.25 1 + 1 + 0.25 + 0.25 = 0.2 w a 4 ( 1 , x 6 ) = 0.25 + 0.25 0.25 + 0.25 + 1 + 1 = 0.2 w a 4 ( 2 , x 6 ) = 1 + 1 0.25 + 0.25 + 1 + 1 = 0.8

Finally, we calculate the probability of a₄ (x₆) = 1, a₄ (x₆) = 2, a₄ (x₇) = 1, a₄ (x₇) = 2. According to Definition 8, we have P ( a 4 ( x 5 ) = 1 ) = 0.5 × 0.8 0.5 × 0.8 + 0.5 × 0.2 = 0.8 P ( a 4 ( x 5 ) = 2 ) = 0.5 × 0.2 0.5 × 0.8 + 0.5 × 0.2 = 0.2 P ( a 4 ( x 6 ) = 1 ) = 0.5 × 0.2 0.5 × 0.2 + 0.5 × 0.8 = 0.2 P ( a 4 ( x 6 ) = 2 ) = 0.5 × 0.8 0.5 × 0.2 + 0.5 × 0.8 = 0.8

From Table 1, According to the analysis of Example 1, the probability of a₄ (x₅) = 1 should greater than that of a₄ (x₅) = 2, whereas the probability of a₄ (x₆) = 2 should greater than that of a₄ (x₆) = 1. From our calculation results, we can see that P (a₄ (x₅) = 1) > P (a₄ (x₅) = 2), P (a₄ (x₆) = 1) < P (a₄ (x₆) = 2). which is consistent with the truth.

Definition 11. For IIS (U, AT, V, f) and attribute set B ⊆ AT, the definitions of lower approximation MDVT _ B λ ( X ) and upper approximation MDVT ¯ B λ ( X ) of object set X based on the modified data-driven valued tolerance relation are that MDVT _ B λ ( X ) = { x ∈ U | MDVT B λ ( x ) ⊆ X }(22) MDVT ¯ B λ ( X ) = { x ∈ U | MDVT B λ ( x ) ∩ X ≠ Φ }(23)

Definition 12. Considering IIS (U, AT, V, f) and attribute set B ⊆ AT, then positive region POS B λ ( X ) , negative region NEG B λ ( X ) and boundary region BND B λ ( X ) of object set X with reference to B is further defined as: POS B λ ( X ) = MDVT _ B λ ( X )(24) NEG B λ ( X ) = U - MDVT ¯ B λ ( X )(25) BND B λ ( X ) = MDVT ¯ B λ ( X ) - MDVT _ B λ ( X )(26)

By comparing the tolerance relation, non-symmetric similarity relation, limited tolerance relation, and data-driven valued tolerance relation, we can get the following Properties.

Property 3. Considering IIS (U, AT, V, f), ∀X ⊆ U and ∀B ⊆ AT, 0 ≤ λ ≤ 1, then MDVT _ B λ ( X ) ⊆ X ⊆ MDVT ¯ B λ ( X ) .

Proof. The proof can easily be completed according to Definition (11)

Property 4. Considering IIS (U, AT, V, f), ∀X ⊆ Y ⊆ U and ∀B ⊆ AT, 0 ≤ λ ≤ 1, then MDVT _ B λ ( X ) ⊆ MDVT _ B λ ( Y ) and MDVT ¯ B λ ( X ) ⊆ MDVT ¯ B λ ( Y ) .

Proof.  The proof can easily be completed according to Definition (11).

Property 5. Considering IIS (U, AT, V, f), ∀X ⊆ U and ∀B ⊆ AT, 0 ≤ λ₁ ≤ λ₂ ≤ 1, then MDVT _ B λ 1 ( X ) ⊆ MDVT _ B λ 2 ( X ) and MDVT ¯ B λ 2 ( X ) ⊆ MDVT ¯ B λ 1 ( X ) .

Proof.  The proof can easily be completed according to Definition (11)

Property 6. Considering IIS (U, AT, V, f), ∀x ∈ U and ∀A ⊆ B ⊆ AT, then MDVT B λ ⊆ MDVT A λ and MDVT B λ ( x ) ⊆ MDVT A λ ( x ) are not true.

The proof of Property 6 is shown in the following Example 3.

Example 3. Suppose an incomplete information system is given in Table 2, where U ={ x₁, x₂, x₃, x₄ } is the object set, and AT ={ a₁, a₂, a₃, a₄ } is the attribute set. A, B, C ⊆ AT, let A ={ a₁, a₂, a₃ }, B ={ a₂, a₃, a₄ } and C ={ a₁, a₂, a₃, a₄ }, then A ⊆ C and B ⊆ C.

According to Eq. (17), we have P A ( x 1 , x 2 ) = 1 × 1 × 12 13 × 2 3 = 24 39 = 0.615 P B ( x 1 , x 2 ) = 1 × 10 11 × 10 11 × 1 3 = 100 363 = 0.275 P C ( x 1 , x 2 ) = 1 × 1 × 14 15 × 14 15 × 2 4 = 98 225 = 0.436

So there are P _B  (x₁, x₂)   <  P _C  (x₁, x₂)   <  P _A  (x₁, x₂), therefore, ∀ (x, y) ∈ U × U, if A ⊆ B, based on MDVT, the relationship between P _A  (x, y) and P _B  (x, y) is uncertain. By the definition MDVT B λ of and MDVT B λ ( x ) , it is clear that MDVT B λ ⊆ MDVT A λ and MDVT B λ ( x ) ⊆ MDVT A λ ( x ) are not true.

Property 6 shows that the modified data-driven valued tolerance relation and its tolerance class are not necessarily monotonically decreasing with the growth of attribute set. Furthermore, it is easy to get the following Property 7 from Property 6.

Property 7. Considering IIS (U, AT, V, f), ∀x ∈ U and ∀A ⊆ B ⊆ AT, then MDVT _ A λ ( X ) ⊆ MDVT _ B λ ( X ) and MDVT ¯ B λ ( X ) ⊆ MDVT ¯ A λ ( X ) are not always true.

Property 7 shows that in the modified data-driven valued tolerance relation, with the increase of attribute set, the lower approximation is not necessarily monotonically increasing, and the upper approximation is not necessarily monotonically decreasing. These properties are not consistent with the corresponding properties based on the indiscernibility relation in CIS.

As MDVT is an reflexive and symmetric generalized indiscernibility relation, in order to demonstrate the effectiveness of MDVT proposed in this paper, we compare its classification accuracy with that of other three typical reflexive and symmetric generalized indiscernibility relations, which are tolerance relation, limited tolerance relation and data-driven valued tolerance relation. The detailed introductions of these typical relations are shown in Section 2. As non-symmetric similarity relation is a reflexive and transitive relation, but not necessarily symmetric, we do not compare classification accuracy of MDVT with that of non-symmetric similarity relation.

The classification accuracy of the generalized indiscernibility relation is defined as follows [29, 30]. Firstly, for a given CIS S₁ = (U, AT, V, f), let E ={ (x, y) ∈ U × U| ∀ b ∈ AT, b (x) = b (y) } be an equivalence relation on U, and [x]  _E be the equivalence class of x in U, then the classification U/E ={ [x]  _E |x ∈ U } can be got. Secondly, CIS S₁ is modified by introducing some percentage of randomly chosen missing attribute values, and then IIS S₂ = (U°, AT, V, f) is derived. Let R be a generalized indiscernibility relation on U°, R (x) be the generalized indiscernibility class of x in U, then the classification U/R ={ R (x) |x ∈ U } can be derived. Finally, the classification accuracy can be defined as: u R = ∑ x ∈ U | [ x ] E ∩ R ( x ) | | [ x ] E ∪ R ( x ) | | U | R is symmetric(27) where |X| denotes the cardinality of set X. Obviously, u _R  ∈ [0, 1], and the greater u _R is, the better classification of R.

In our experiments, six complete data sets from UCI Machine Learning Repository [31] are used as shown in Table 3, which are Zoo, Monk, Spect, Hayes, TicTacToe and Chess. In Table 3, the first column is the name of data sets, the second column is the number of condition attributes and the third column is the number of decision attributes. All these six data sets are complete. Each complete data set is modified by introducing 10%, 30% and 50% randomly chosen missing attribute values, and then 18 incomplete data sets (X-a% represents data set X missing a% data) are derived. For each incomplete data set, we run the experiments 100 times and get the average result, which is used as the final classification accuracy. The experimental results are shown in Table 4, where T, L, DVT and MDVT denote tolerance relation, limited tolerance relation, data-driven valued tolerance relation and modified data-driven valued tolerance relation, respectively.

Figure 1 plots the classification accuracy from Table 4. In these plots, the X-axis represents the percentage of randomly chosen missing attribute values, and the Y-axis represents the classification accuracy. From Table 4 and Fig.1, we can see that the classification accuracy of MDVT is higher than that of T, L on all test data sets. The classification accuracy of MDVT is generally higher than that of DVT on all test data sets except the Monk-50% and Hayes-50%. Note that with the increasing of missing attribute values, the classification accuracy deteriorate for all test data sets. However, the classification accuracies of T and L decrease quickly with the increasing of the incomplete degree of data set, whereas the classification accuracies of DVT and MDVT is relatively stable. The experimental results show that the modified data-driven valued tolerance relation can get better classification accuracy than that of other generalized indiscernibility relations.

OPEN IN VIEWER

Fig.1

Classification accuracies for the data sets used in the experiment.

Incomplete information is one of the most difficult problems of data mining. In order to deal with incomplete information, various extended models of classical rough set theory have been proposed. The datadriven valued tolerance relation does not require any prior knowledge except the data set, which can solve the problems of the valued tolerance relation. However, when predicting probability of the unknown attribute value of an object, it regards the frequency of an attribute value approximately as the probability of appearance of this value, without considering the effects of other known attribute values of this object on predicting probability of unknown attribute value. In this paper, to solve the limitations of data-driven valued tolerance relation, modified data-driven valued tolerance relation is defined, which not only considering the frequency of an attribute value, but also considering the effects of other known attribute values of an object on predicting probability of unknown attribute value of this object. On this basis, the extended rough set model based on modified data-driven valued tolerance relation is proposed. Some properties of the new model are analyzed. Experimental results show that the modified data-driven valued tolerance relation can get better classification accuracy than that of other generalized indiscernibility relations. In the future, we will investigate the attribute reduction and rule extraction based on the new generalized indiscernibility relation. Its effectiveness in dealing with incomplete information system will be further inspected.