Incrementally updating approximation in incomplete information systems under the variation of objects

Nội dung text: Incrementally updating approximation in incomplete information systems under the variation of objects

1. Journal of Computer Science and Cybernetics, V.36, N.4 (2020), 365–379 DOI 10.15625/1813-9663/36/4/14650 INCREMENTALLY UPDATING APPROXIMATION IN INCOMPLETE INFORMATION SYSTEMS UNDER THE VARIATION OF OBJECTS TRAN T. T. HUYEN1,*, LE BA DUNG2, NGUYEN DO VAN3, MAI VAN DINH4 1MITI, Academy of Military Science and Technology 2IOIT, Vietnam Academy of Science and Technology 3Military College of Tank-Armour Officers 4HMI Lab, UET, Vietnam National University Abstract. In covering approximation space, the rough membership functions give numerical charac- terizations of covering-based rough set approximations. It is considered as a tool for establishing the relationship between covering-based rough sets and fuzzy covering-based rough sets. In this paper, we introduce a new method to update the approximation sets with rough membership functions in covering approximation space. Firstly, we present the third types of rough membership functions and study their properties. And then, we consider the change of them while simultaneously adding and removing objects in the information system. Based on that change, we propose a method for upda- ting the approximation sets when the objects vary over time. We proved that the method facilitates knowledge maintenance without retrain from scratch. Keywords. Rough set; Incomplete information systems; Covering-based rough set; The third types of rough membership functions; Incremental learning. 1. INTRODUCTION Rough set theory was originally proposed by Pawlak in 1982 [27] and now it is used as a useful mathematical tool to solve problems containing uncertain data in information systems and data analysis. However, it can only be used in the complete information systems while real data is often imperfect. Therefore, many extensions have been made in recent years to deal with this problem. Some scholars have extended rough sets by replacing the equivalent relation with other binary relations. Those approaches are based on two cases. One is Lost value [13] in which unknown values of attributes are already lost and the other is Do not care [6–8, 15], which may be potentially replaced by any value in the domain. In addition, the researchers also extended the rough set based on coverings of the universe of discourse [14, 20, 25]. First, Zakowski built the first type of covering-based rough sets by covering instead of a partition of the universe [20]. Bonikowski et al. used the concepts of extension and intension to propose the second type of covering-based rough sets [20]. And Pomykala included interior and closure operators from topology in the second type of covering-based rough sets [14]. Wang et al. established relationships between four matroidal structures of coverings and the second type of covering-based rough sets [5]. Tsang et al. introduced the third type of covering-based rough sets [9], and Zhu discussed difference *Corresponding author. E-mail addresses: Huyenmit82@gmail.com(T.T.T Huyen); lbdung@ioit.ac.vn (L.B. Dung); ngdovan@gmail.com (N.D. Van); maivandinhvn@gmail.com (M.V.Dinh) c 2020 Vietnam Academy of Science & Technology
2. 366 TRAN T. T. HUYEN et al. between this model and Pawlaks rough sets [28]. Zhu and Wang studied the fourth type of covering-based rough sets and established axiomatic systems for the lower and upper approximation operators [21]. The dynamic information system can be divided into three aspects: variation of objects, variation of attributes, and variation of attributes values. As the information changes, the approximation sets also change. Thence, incremental learning techniques are used for mining dynamic databases. The main idea of those methods is using the results obtained previously in order to facilitate knowledge maintenance in the changing database without exploiting the total database from scratch. Based on rough set theory, studies on incremental data analysis have been developed. A method for incremental updating rough approximations in informa- tion system under the characteristic relation-based rough sets is proposed by Li et al. [18]. Chen et al. discussed a method for incremental approach for updating approximations of variable precision rough-set model [12]. They updated the properties of information granu- lation and approximations with the refining and coarsening of attribute values. Luo et al. proposed incrementally updating approximations in the set-valued information systems [3]. Then, Luo et al. introduced an incremental method for updating probabilistic approximati- ons when adding and removing objects based on characteristic relation [4]. It is easy to see that these incremental methods are all used to the ratio of overlap in the equivalence class without considering the degree of overlap in a basic set. The third type of rough membership function is defined the highest ratio of overlap in a decision set. If conditional probability pays close attention to the classification of an equivalence class then the third type of rough membership function pays close attention to the decision class. In this paper, we propose a method for updating the approximation sets based on the third type of rough membership function in the incomplete system when the objects vary. This paper is organized as follows: Section 2 briefly reviews some basic concepts of Pawlaks rough sets and covering-based rough sets. Section 3 gives the concept and some properties of the third type of rough membership function by neighborhood operator in covering approximation space. Section 4 introduces an incremental updating method with approximation sets in covering approximation space and Section 5 presents the conclusions. 2. PRELIMINARIES In this section, we briefly review some existing definitions and results of Pawlaks rough sets and covering-based rough sets. The main idea of a rough set is based on the partition or indiscernibility relation to define subsets called the lower and upper approximation sets to approximate description of arbitrary subset in the universe. This partition or equivalence relation is still restrictive for various applications. Therefore, it is not applicable in information systems containing imperfect data. To deal with this problem, Kryszkiewicz introduced indiscernibility based on tolerance relations [15]. Here, a missing value was considered as a special value that may take any possible value. Definition 1. [15] An information system usually is defined as IS = (U, A, V, f) where U is a non-empty finite set of objects, A is a non-empty finite set of attributes, V = {Va |a ∈ A} is a domain of attribute a, f is a function from U × A into V.
3. INCREMENTALLY UPDATING APPROXIMATION ININCOMPLETE 367 If U contains at least an unknown value object, then IS is called an incomplete infor- mation system, denoted as IIS, otherwise complete. In incomplete information systems, unknown values are denoted by special symbol “ ∗ ” and are supposed to be contained in the set Va. In practice, if we have A = C ∪{d}, where C denotes a nonempty finite set of conditional attributes and d∈ / C is a distinguished attribute called decision, then IS = (U, C ∪{d}, V, f) is called a decision table. Definition 2. [15] Let IIS = (U, C ∪ {d}, V, f) be an incomplete information system, and P ⊆ C. Then a Tolerance relation TORP denotes a binary relation between objects that are possibly equivalent in terms of values of attributes and defined as TORP = {(x, y) ∈ U × U |∀a ∈ P, fa(x) = fa(y) ∨ fa(x) = ∗ ∨ fa(y) = ∗} , (1) where fa(x), fa(y) denote the values of objects x and y on a, ∨ denotes disjunction. This relation is reexive and symmetric but does not need to be transitive. Let TP (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. Definition 3. [15] Let IIS = (U, C ∪ {d}, V, f) be an incomplete information system, and P ⊆ C, X ⊆ U. The lower and upper approximations of X in terms of P are defined as follows appr (X) = {x ∈ U |T (x) ⊆ X } , (2) P P apprP (X) = {x ∈ U |TP (x) ∩ X 6= ∅} . (3) Definition 4. [25] Let U be a universe of discourse and C be a family of subsets of U. Then C is called a covering of U if none of elements of C is empty and ∪ {C |C ∈ C} = U. If K is an element of C, K is called a covering block. Furthermore, (U, C) is called a covering approximation space and denoted it by CAS. In the incomplete information system IIS = (U, C ∪ {d}, V, f), with P ⊆ C, let C = {TP i(x)} then C is called a special characteristic covering of U [9]. Next, we recall some definitions of covering, which shall be needed in the sequel. Definition 5. [25] Let CAS = (U, C) be a covering approximation space. For any x ∈ U, T NC(x) = {K ∈ C : x ∈ K} is called the neighborhood of x. Definition 6. [5] Let CAS = (U, C) be a covering approximation space. CovC(X) = {NC(x): x ∈ U} is called the covering of neighborhoods induced by C. Definition 7. [5] Given U be a discourse of universe. A ⊆ U is called a fuzzy set, or rather a fuzzy subset of U, if exist a function assigning each element x of U a value A(x) ∈ [0, 1]. At that time, the family of all fuzzy subsets of U, i.e., the set of all functions from U to [0, 1] is called the fuzzy power set of U and denoted as P(U).
4. 368 TRAN T. T. HUYEN et al. 3. ROUGH SET MODEL BASED ON THE THIRD TYPE OF ROUGH MEMBERSHIP FUNCTION One of the fundamental notions of set theory is the rough membership function. It was used to measure the uncertainty of a set in an information system. In Pawlak rough set, the rough membership function was also used to present numerical characterizations of rough set approximations. Yao made a survey on existing studies, and gave some new results on the decision-theoretic rough set model based on rough membership function [23]. Greco et al. introduced a generalization of the original definition of rough sets and variable precision rough sets using the concept of absolute and relative rough membership functions [17]. Ge et al. constructed a kind of rough membership function based on covering rough set [22]. It is considered the fourth type of rough membership. In CAS = (U, C) with x ∈ U, X ∈ P(U), they defined the rough membership function as follows |X ∩ C|  ϕX (x) = max |x ∈ C, C ∈ C . C |C| X Based on this definition, we realize that ϕC (x) is only related to the covering blocks containing x. Yang et al. defined the first type of rough membership function as follows [1] X |X ∩ NC (X)| σC = , |NC (X)| T where NC (X) = {C ∈ C|x ∈ C}. The above definition means, in the case that object x related both the covering C and X, then it is important to measure the rough membership of x to X with respect C. After that, they defined the second and third types of rough mem- bership functions by generalizing the first and fourth types of rough membership functions, respectively. Here the second type of rough membership shows the ratio of |X ∩ NC(x)| and |NC(x)|, and the third type of rough membership shows the highest ratio of |X ∩ C| and |X|. Since NC(x) ⊆ C, then the second type of rough membership function is always less than or equal to the third type of rough membership function. In the following, we review the definition about the third type of rough membership function in a covering approximation space and its properties. Definition 8. [1] Let CAS = (U, C) be a covering approximation space. For any x ∈ U, X ∈ P(U), the third type of rough membership function is defined as follows ( 0,X = ∅, X VC (x) = n |X∩C| o (4) max |X| |x ∈ C, C ∈ C ,X 6= ∅. X Here, VC (x) is considered maximum coverage measure. If given a rule C → X then X VC (x) means the elements C are the most general in the decision class X. With x ∈ X and X X 6= ∅ then VC (x) > 0. X Based on Definition 8, some properties of VC (x) are presented as follows. Proposition 9. [1] Let CAS = (U, C) be a covering approximation space. For any X ∈ P(U), ∀x ∈ X, the following statements hold X (i) 0 ≤ VC (x) ≤ 1,
5. INCREMENTALLY UPDATING APPROXIMATION ININCOMPLETE 369 X (ii) If ∃C ∈ C such that ∅= 6 C ⊆ C, then VC (y) = 1, ∀y ∈ C. According to the proposition above, assume that C = {C1,C2, , Cm}, if x ∈ Ci, then Ci Ci VC (x) = 1, for i = 1, 2, , m. Thus, the family CV = {VC |i = 1, 2, , m} is a fuzzy β−covering of U for β ∈ [0, 1]. Definition 10. [1] Let CAS = (U, C) be a covering approximation space. 0 ≤ ρ 6 1 and X ∈ P(U). The graded lower and graded upper approximations based on covering of X with respect to (U, C) based on the parameter ρ are defined, respectively, as follows n o C (X) = x ∈ U V (∼X) (x) ≤ ρ , (5) ρ C n o C (X) = x ∈ U V (X) (x) > ρ , (6) ρ C where ∼ X denotes a complementary set of X. Below are the definitions of the positive region, negative region, upper boundary region, lower boundary region and boundary region based on covering. Definition 11. [1] Let CAS = (U, C) be a covering approximation space. 0 ≤ ρ 6 1 and X ∈ P(U). The positive region, negative region, upper boundary region, lowers boundary region and boundary region are defined as POSρ(X) = Cρ (X) ∩ Cρ (X) ; (7) NEGρ(X) = U − (Cρ (X) ∪ Cρ (X)); (8) LBNDρ(X) = Cρ (X) − Cρ (X) ; (9) UBNDρ(X) = Cρ (X) − Cρ (X) ; (10) BNDρ(X) = LBNDρ(X) ∪ UBNDρ(X). (11) The sets POSρ(X), NEGρ(X), LBNDρ(X), UBNDρ(X), BNDρ(X) are also called the graded covering-based positive region, negative region, lower boundary region, upper boun- dary region and boundary region of X, respectively. From the definition above we can get the following properties of approximation space directly as: (i) Cρ (U) = U; (ii) Cρ (∅) = ∅; (iii) Cρ (∼ X) =∼ Cρ (X); (iv) Cρ (∼ X) =∼ Cρ (); (v) If ∃C ∈ C such that X ⊆ C, then X ⊆ Cρ (X); (vi) If ∃C ∈ C such that ∼ X ⊆ C, then Cρ (X) ⊆ X;
   (vii) Cρ (X) ⊆ Cρ Cρ (X) ;
   (viii) Cρ Cρ (X) ⊆ Cρ (X);
6. 370 TRAN T. T. HUYEN et al. (ix) C0 (X) = {x ∈ U|C ⊆ X, x ∈ C ∈ C}, C0 (X) = {x ∈ U||X ∩ C| 6= ∅, ∃C ∈ C, such that x ∈ C}; (x) If |A| = | ∼ A|, then Cρ (X) = {x ∈ U||C| − |X ∩ C| ≤ ρ|X|, x ∈ C ∈ C, and Cρ (X) = {x ∈ U||X ∩ C| > ρ|X|, ∃C ∈ C such that x ∈ C; (xi) If 0 ≤ ρ1 ≤ ρ2 < 1, then Cρ2 (X) ⊆ Cρ1 (X) and Cρ2 (X) ⊆ Cρ1 (X). 4. UPDATE APPROXIMATION SETS IN DYNAMIC COVERING INFORMATION SYSTEMS Yao et al. studied the minimum, maximum and average rough membership functions, and their properties [24]. Xu and Zhang proposed new lower and upper approximations and obtained some important properties in generalized rough set induced by a covering [19]. Shi et al. discussed the uncertainty of covering in the covering approximation space and presented an approach which measures these similarities using a triangular norm [26]. Lin et al. presented three types of covering based multi-granulation rough sets by using different covering approximation operators [11]. In the dynamic systems, researchers investigated knowledge reduction by using incremen- tally updating approaches. Lang et al. provided some methods to computing the type−1 and type−2 characteristic matrices of dynamic coverings when the objects vary [10]. Cai et al. studied knowledge reduction of dynamic covering decision information systems caused by altering attribute values [16]. Hu et al. proposed a method for updating approximations based on equivalence relation matrix, diagonal matrix and cut matrix in multigranulation rough set when a single granular structure evolves over time [2]. In such an approach, there is a problem as to whether there is a way to update the approximation sets without using matrices. To deal with this issue, we propose a method to update the approximation sets based on the third type of rough membership function. Let IIS = (U, C ∪ {d}, V, f) be an incomplete decision table and P ⊆ C. We call CP = {TP (x)|x ∈ U} a special characteristic covering. We describe this information system at time step t, when the object has not changed, as IIS(t) = (U (t),C(t) ∪ {d}(t), V, f). At time step t + 1, when adding object x and deleting object x occur simultaneously, the information is denoted as IIS(t+1) = (U (t+1),C(t+1) ∪ {d}(t+1), V, f). According to Definition 10, to update the lower and upper approximation sets, we first need to consider their change when the third type of rough membership function changes. For simplicity, we denote V (t) the third type of rough membership function at time t and V (t+1) at time t + 1. In the following, we consider the change of approximation sets when the third type of rough member functions increases, decreases or is constant. We first consider the change of approximation sets when the third type of rough membership function does not change. Theorem 12. Suppose that at time t + 1, the third type of rough membership functions does not change, i.e.,V (t+1) = V (t), then (t+1) (t) 0 Cρ (X) = Cρ (X) − ∆ + ∆ , (12)
7. INCREMENTALLY UPDATING APPROXIMATION ININCOMPLETE 371 where (t) 0 (X) ∆ = {x|x ∈ Cρ (X)}, and ∆ = {x|V (x) > ρ}. (13) (t+1) (t) Cρ (X) = Cρ (X) − ∆1 + ∆2, (14) where (t) (∼X) ∆1 = {x|x ∈ Cρ (X)} and ∆2 = {x|V (x) ≤ ρ}. (15) Proof. It can be directly deduced from Definition 10.  Next, we will update the approximation sets as the third type of rough membership functions increases over time. Theorem 13. Suppose that at time t + 1, the third type of rough membership functions increases, i.e., V (t+1) > V (t), then If V (X)(t+1) > V (X)(t) then (t+1) (t) Cρ (X) = Cρ (X) − ∆1 + ∆2, (16) where (X) (X) ∆1 = {x|V (x) > ρ}, and ∆2 = {x|V (x) > ρ}. (17) If V (∼X)(t+1) > V (∼X)(t) then (t+1) (t) 0 Cρ (X) = Cρ (X) − ∆ + ∆ , (18) where ∆ = {x, x ∈ U|V (∼X)(x) ≤ ρ, V (∼X)(t+1)(x) > ρ}, and ∆0 = {x|V (∼X)(x) ≤ ρ}. (19) Proof. If V (X)(t+1) > V (X)(t) > ρ and V (X)(x) ∧ V (X)(x) > ρ then (16) hold based on Definition 10. If V (∼X)(t+1) > V (∼X)(t), since V (∼X)(t) ≤ ρ, we consider two cases: + Case 1: If V (∼X)(t+1)(x) ≤ ρ then (∼X) (t) (t+1) (t) If V (x) ≤ ρ ⇒ x ∈ Cρ (X) ⇒ Cρ (X) = Cρ (X) − {x}. (∼X) (t+1) (t+1) (t) If V (x) ≤ ρ ⇒ x ∈ Cρ (X) ⇒ Cρ (X) = Cρ (X) ∪ {x}. (∼X)(t+1) + Case 2: If V (x) > ρ, based on Definition 10, x does not belong to Cρ(X) at (∼X) (∼X) time t + 1, furthermore, if V (x) ≤ ρ, V (x) ≤ ρ, then (18) holds.  And finally, we consider the change of the approximation sets when the third type of rough membership function decreases. Theorem 14. Suppose that at time t + 1, the third type of rough membership functions decreases, i.e., V (t+1) < V (t), then If V (X)(t+1) < V (X)(t) then (t+1) (t) 0 Cρ (X) = Cρ (X) − ∆ + ∆ , (20)
8. 372 TRAN T. T. HUYEN et al. where ∆ = {x, x ∈ U|V (X)(x) > ρ, V (X)(t+1)(x) ≤ ρ}, and ∆0 = {x|V (X)(x) > ρ}. (21) If V (∼X)(t+1) < V (∼X)(t) then (t+1) (t) Cρ (X) = Cρ (X) − ∆1 + ∆2, (22) where (∼X) (∼X) ∆1 = {x|V (x) ≤ ρ}, and ∆2 = {x|V (x) ≤ ρ}. (23) Proof. The proof of this theorem is to that of Theorem 13.  In the following, we study the changing trend of the third type of rough membership functions when adding and removing objects simultaneously. Let IIS(t) = (U (t),C(t) ∪ {d}(t), V, f) be an information system at time t, with which the (t) (t) n (t) (t) (t) o tolerance classes and decision classes, respectively, are U /T OLP = TP 1,TP 2, , TP m (t) (t) n (t) (t) (t)o and U {d} = D1 ,D2 , , Dn . And the information system at time t + 1 is IIS(t+1) = (U (t+1),C(t+1) ∪ {d}(t+1), V, f) (t+1). (t+1) with which the tolerance classes and decision classes, respectively, are U T OLP = n (t+1) (t+1) (t+1)o (t+1) (t+1) n (t+1) (t) (t+1)o TP 1 ,TP 2 , , TP m and U {d} = D1 ,D2 , , Dn . In order to easily update the third type of rough membership functions, in the following, we show how to update the tolerance and decision classes. We assume that, at time t + 1, object x is added and object x is deleted simultaneously. Then, the change of tolerance and decision classes at time t + 1 can be obtained as follows  T (t) − {x} if x ∈ T (t) ∧ x∈ / T (t),  P i P i P i  T (t) ∪ {x} if x ∈/ T (t) ∧ x ∈ T (t), T (t+1) = P i P i P i (24) P i T (t) ∪ {x} − {x} if x ∈ T (t) ∧ x ∈ T (t),  P i P i P i  (t) TP i , otherwise.  (t) (t) (t)  Dj − {x} if x ∈ Dj ∧ x∈ / Dj ,   D(t) ∪ {x} if x ∈/ D(t) ∧ x ∈ D(t), D(t+1) = j j j (25) j D(t) ∪ {x} − {x} if x ∈ D(t) ∧ x ∈ D(t),  j j j  (t)  Dj , otherwise. Here we assume that object x belongs to existing tolerance classes and decision classes. In the opposite case, x will form a new class, respectively. S Since {TP i} is a family of subset of U with TP i 6= ∅ and TP i = U, then we consider CP = {TP 1,TP 2, , TP n} a special characteristic covering and (U, CP ) a covering approximation space. When {TP i} changes, the changing trend of the third type of rough membership functions is as follows. Theorem 15. Let IIS = (U, C∪{d}, V, f) be an information system, where U = {u1, u2, , un}, P ⊆ C, D ⊆ U, T OLP is a tolerance relation on U. Suppose, object x is added and object x is deleted simultaneously from time t to time t + 1. And
9. INCREMENTALLY UPDATING APPROXIMATION ININCOMPLETE 373 If  (t+1) (t+1)  (t) (t) 1. x∈ / TP i ∧ x∈ / D ∧ x ∈/ TP i ∧ x ∈/ D ,  (t+1) (t+1)  (t) (t) 2. x∈ / TP i ∧ x∈ / D ∧ x ∈ TP i ∧ x ∈/ D ,  (t+1) (t+1)  (t) (t) 3. x∈ / TP i ∧ x ∈ D ∧ x ∈/ TP i ∧ x ∈ D ,  (t+1) (t+1)  (t) (t) 4. x ∈ TP i ∧ x∈ / D ∧ x ∈/ TP i ∧ x ∈/ D ,  (t+1) (t+1)  (t) (t) 5. x ∈ TP i ∧ x∈ / D ∧ x ∈ TP i ∧ x ∈/ D ,  (t+1) (t+1)  (t) (t) 6. x ∈ TP i ∧ x ∈ D ∧ x ∈ TP i ∧ x ∈ D then V (D)(t+1) = V (D)(t). If  (t+1) (t+1)  (t) (t) 7. x∈ / TP i ∧ x∈ / D ∧ x ∈/ TP i ∧ x ∈ D ,  (t+1) (t+1)  (t) (t) 8. x∈ / TP i ∧ x ∈ D ∧ x ∈ TP i ∧ x ∈ D ,  (t+1) (t+1)  (t) (t) 9. x ∈ TP i ∧ x∈ / D ∧ x ∈/ TP i ∧ x ∈ D ,  (t+1) (t+1)  (t) (t) 10. x ∈ TP i ∧ x ∈ D ∧ x ∈/ TP i ∧ x ∈/ D ,  (t+1) (t+1)  (t) (t) 11. x ∈ TP i ∧ x ∈ D ∧ x ∈ TP i ∧ x ∈/ D ,  (t+1) (t+1)  (t) (t) 12. x ∈ TP i ∧ x ∈ D ∧ x ∈/ TP i ∧ x ∈ D , then V (D)(t+1) > V (D)(t). If  (t+1) (t+1)  (t) (t) 13. x∈ / TP i ∧ x∈ / D ∧ x ∈ TP i ∧ x ∈ D ,  (t+1) (t+1)  (t) (t) 14. x∈ / TP i ∧ x ∈ D ∧ x ∈/ TP i ∧ x ∈/ D ,  (t+1) (t+1)  (t) (t) 15. x∈ / TP i ∧ x ∈ D ∧ x ∈ TP i ∧ x ∈/ D ,  (t+1) (t+1)  (t) (t) 16. x ∈ TP i ∧ x∈ / D ∧ x ∈ TP i ∧ x ∈ D , then V (D)(t+1) < V (D)(t). Proof.  (t+1) (t+1)  (t) (t) 1. Since x∈ / TP i ∧ x∈ / D ∧ x ∈/ TP i ∧ x ∈/ D (t+1) (t) (t+1) (t) ⇒ TP i = TP i and D = D (t+1) (t+1) (t) (t) (t+1) (t) ⇒ |TP i ∩ D | = |TP i ∩ D | and |D | = |D | ( ) ( ) T (t+1)∩D(t+1) T (t)∩D(t) ⇒ max P i x ∈ T (t+1) = max P i x ∈ T (t) . |D(t+1)| P i |D(t)| P i
10. 374 TRAN T. T. HUYEN et al. According to Definition 8, V (D)(t+1) = V (D)(t). The proof of 2, 3, 4, 5, and 6 is similar to that of 1.  (t+1) (t+1)  (t) (t) 7. Since x∈ / TP i ∧ x∈ / D ∧ x ∈/ TP i ∧ x ∈ D (t+1) (t) (t+1) (t) ⇒ TP i = TP i and D = D − {x} (t+1) (t+1) (t) (t) (t+1) (t) (t) ⇒ |TP i ∩ D | = |TP i ∩ D | and |D | = |D | − 1 P i |D(t+1)| |D(t)| ( ) ( ) T (t+1)∩D(t+1) T (t)∩D(t) ⇒ max P i x ∈ T (t+1) > max P i x ∈ T (t) . |D(t+1)| P i |D(t)| P i According to Definition 8, V (D)(t+1) > V (D)(t). The proof of 8, 9, 10, 11, and 12 is similar to that of 7.  (t+1) (t+1)  (t) (t) 13. Since x∈ / TP i ∧ x∈ / D ∧ x ∈ TP i ∧ x ∈ D (t+1) (t) (t+1) (t) ⇒ TP i = TP i − {x} and D = D − {x} (t+1) (t+1) (t) (t) (t+1) (t) (t) ⇒ |TP i ∩ D | = |TP i ∩ D | − 1 and |D | = |D | − 1 < |D |, T (t+1)∩D(t+1) T (t)∩D(t) P i < P i |D(t+1)| |D(t)| ( ) ( ) T (t+1)∩D(t+1) T (t)∩D(t) ⇒ max P i x ∈ T (t+1) < max P i x ∈ T (t) . |D(t+1)| P i |D(t)| P i According to Definition 8, V (D)(t+1) < V (D)(t). The proof of 14, 15, and 16 is similar to that of 13.  Theorem 16. Let IIS = (U, C∪{d}, V, f) be an information system, where U = {u1, u2, , un}, P ⊆ C, D ⊆ U, T OLP is a tolerance relation on U. Suppose, object x is added and object x is deleted simultaneously from time t to time t + 1. And If  (t+1) (t+1)  (t) (t) 1. x∈ / TP i ∧ x∈ / D ∧ x ∈/ TP i ∧ x ∈/ D ,  (t+1) (t+1)  (t) (t) 2. x∈ / TP i ∧ x∈ / D ∧ x ∈/ TP i ∧ x ∈ D ,  (t+1) (t+1)  (t) (t) 3. x∈ / TP i ∧ x ∈ D ∧ x ∈/ TP i ∧ x ∈ D ,  (t+1) (t+1)  (t) (t) 4. x∈ / TP i ∧ x ∈ D ∧ x ∈ TP i ∧ x ∈ D ,  (t+1) (t+1)  (t) (t) 5. x ∈ TP i ∧ x∈ / D ∧ x ∈ TP i ∧ x ∈/ D ,  (t+1) (t+1)  (t) (t) 6. x ∈ TP i ∧ x ∈ D ∧ x ∈/ TP i ∧ x ∈ D ,  (t+1) (t+1)  (t) (t) 7. x ∈ TP i ∧ x ∈ D ∧ x ∈ TP i ∧ x ∈ D , then V (∼D)(t+1) = V (∼D)(t).
11. INCREMENTALLY UPDATING APPROXIMATION ININCOMPLETE 375 If  (t+1) (t+1)  (t) (t) 8. x∈ / TP i ∧ x∈ / D ∧ x ∈ TP i ∧ x ∈ D ,  (t+1) (t+1)  (t) (t) 9. x∈ / TP i ∧ x ∈ D ∧ x ∈/ TP i ∧ x ∈/ D ,  (t+1) (t+1)  (t) (t) 10. x ∈ TP i ∧ x∈ / D ∧ x ∈/ TP i ∧ x ∈/ D ,  (t+1) (t+1)  (t) (t) 11. x ∈ TP i ∧ x∈ / D ∧ x ∈/ TP i ∧ x ∈ D ,  (t+1) (t+1)  (t) (t) 12. x ∈ TP i ∧ x∈ / D ∧ x ∈ TP i ∧ x ∈ D ,  (t+1) (t+1)  (t) (t) 13. x ∈ TP i ∧ x ∈ D ∧ x ∈/ TP i ∧ x ∈/ D , then V (∼D)(t+1) > V (∼D)(t). If  (t+1) (t+1)  (t) (t) 14. x∈ / TP i ∧ x∈ / D ∧ x ∈ TP i ∧ x ∈/ D ,  (t+1) (t+1)  (t) (t) 15. x∈ / TP i ∧ x ∈ D ∧ x ∈ TP i ∧ x ∈/ D ,  (t+1) (t+1)  (t) (t) 16. x ∈ TP i ∧ x ∈ D ∧ x ∈ TP i ∧ x ∈/ D , then V (∼D)(t+1) < V (∼D)(t). Proof. The proof of Theorem 16 is similar to that of Theorem 15.  This section shows a method for updating approximation sets when object x is added and object x is deleted in the incomplete information system. Next, we will present an example to illustrate this method. Example 17. Given an information system is in Table 1. Table 1. An incomplete information system at time step t Car a1 a2 a3 a4 d x1 Low High Full High Excel. x2 Medium Medium Full Low Excel. x3 Low Medium Medium * Poor x4 Low * * High Poor x5 High Low Full High Good x6 High * Full High Good x7 High Low Full High Poor x8 High Low Full High Good Let C = {a1, a2, a3, a4}. Based on Definition 2, we have TC (1) = {1},TC (2) = {2},TC (3) = TC (4) = {3, 4}, TC (5) = TC (6) = TC (7) = TC (8) = {5, 6, 7, 8}. From there we get the partition and the third type of rough membership function
12. 376 TRAN T. T. HUYEN et al. (t). (t) n (t) (t) (t) (t)o U T OLC = TC1,TC2,TC3,TC4 , where (t) (t) (t) (t) TC1 = {1},TC2 = {2},TC3 = {3, 4},TC4 = {5, 6, 7, 8}. With D(t) = {3, 4, 7}, we can calculate the third type of rough membership functions as follows 2 2 1 1 1 1 (t) 0 0 V D = + + 3 + 3 + 3 + 3 + 3 + 3 , TC x1 x2 x3 x4 x5 x6 x7 x8 1 1 3 3 3 3 (t) 0 0 V ∼D = 5 + 5 + + + 5 + 5 + 5 + 5 . TC x1 x2 x3 x4 x5 x6 x7 x8 Let ρ = 0.3. According to Definition 10, the graded covering-based lower and upper approximations of D(t) can be obtained as follows (t) C0.3(D ) = {x1, x2, x3, x4}, (t) C0.3(D ) = {x3, x4, x5, x6, x7, x8}. Next, suppose that at time t + 1, object x9 is added and object x1 is deleted shown in Table 2. Table 2. An incomplete information system at time step t + 1 Car a1 a2 a3 a4 d x2 Medium Medium Full Low Excel. x3 Low Medium Medium * Poor x4 Low * * High Poor x5 High Low Full High Good x6 High * Full High Good x7 High Low Full High Poor x8 High Low Full High Good x9 Low * Medium High Good Then the tolerance classes can be updated as follows (t+1) (t) TC1 = TC1 − {x1} = ∅, (t+1) (t) TC2 = TC2 = {x2}, (t+1) (t) TC3 = TC3 ∪ {x9} = {x3, x4, x9}, (t+1) (t) TC4 = TC4 = {x5, x6, x7, x8}. (t+1) (t) (t+1) (t) Since x9 ∈/ D ∧ x1 ∈/ D then D = D .
13. INCREMENTALLY UPDATING APPROXIMATION ININCOMPLETE 377 According to Theorem 15 and Theorem 16, the third type of rough membership functions is calculated as follows 2 2 1 1 1 1 2 (t+1) 0 V D = + 3 + 3 + 3 + 3 + 3 + 3 + 3 , TC x2 x3 x4 x5 x6 x7 x8 x9 1 3 3 3 3 1 (t+1) 0 0 V ∼D = 5 + + + 5 + 5 + 5 + 5 + 5 . TC x2 x3 x4 x5 x6 x7 x8 x9 Based on Theorem 13 and Theorem 14, the graded covering-based lower and upper approximations of D(t+1) can be updated as follows (t+1) (t) C0.3(D ) = C0.3(D ) − {x1} ∪ {x9} = {x2, x3, x4, x9}, (t+1) (t) C0.3(D ) = C0.3(D ) ∪ {x9} = {x3, x4, x5, x6, x7, x8, x9}. By the above example, we illustrate that by using the third type of rough membership functions we can update the approximation sets. When the objects are added and deleted simultaneously from time t to time t + 1, the third type of rough membership functions will change. Based on this change, we can update the approximation sets by modifying the original sets. According to the above example, to fix the approximation set, we just need to ( ( calculate the V D t+1)(x ) and V (∼D) t+1)(x ) without recalculating all the objects. TC 9 TC 9 5. CONCLUSION Approximation sets are important concepts of the rough set theory. When the objects change over time, the approximation set also change. Our contribution is to introduce a met- hod for updating graded covering-based approximation sets in the incomplete information systems under the objects variation. At that time, the approximation sets can be formally based on the third type of rough membership function. When the objects vary, they lead to the variations of tolerance classes and decision classes. This makes the third type of rough membership function change. Based on the change of the third type of rough mem- bership function, we suggest a way of maintenance approximation sets. The approximation sets can be updated by modifying the partial sets without recomputing sets from the very beginning when the objects vary. Our future work will focus on algorithm development, ex- perimentation, evaluation and comparison in real databases for the validation of the proposed approaches. REFERENCES [1] B. Yang, B. Q. Hu and J. Qiao, “Three-way decisions with rough membership functions in covering approximation space,” Fundamenta Informaticae, vol. 165, pp. 157–191, 2019. [2] BP. Hu and H. Wong, “Generalized interval-valued fuzzy variable precision rough sets,” Inter- national Journal of Fuzzy Systems, vol. 16, no. 4, pp. 554–565, 2014. [3] T. R. L. C. Luo and H. M. Chen, “Dynamic maintenance of approximations in setvalued ordered decision systems under the attribute generalization,” Information Sciences, vol. 257, pp. 210– 228, 2014.
14. 378 TRAN T. T. HUYEN et al. [4] C. Luo, T. Li and Y. Yao, “Dynamic probabilistic rough sets with incomplete data,” Information Sciences, 2017. [Online]. Available: doi:10.1016/j.ins.2017.06.040 [5] C. Wang, D. chen, B. Sun and Q. Hu, “Communication between information systems with covering based rough sets,” Information Sciences, vol. 2012.216, pp. 17–33, 2012. [Online]. Available: [6] Do Van Nguyen, Koichi Yamada and M. Unehara, “Rough set model based on parameterized probabilistic similarity relation in incomplete decision tables,” in SCIS-ISIS 2012, Kobe, Japan, November 2012, pp. 20–24. [7] ——, “Extended tolerance relation to define a new rough set model in incomplete information systems,” Advances in Fuzzy Systems, vol. 2013, 2013. [8] ——, “On probability of matching in probability based rough set definitions,” in 2013 IEEE International Conference on Systems, Man, and Cybernetics, 2013. [9] E. Tsang, D. Chen, J. Lee and D. Yeung, “On the upper approximations of covering genera- lized rough sets,” in Proceedings of 2004 International Conference on Machine Learning and Cybernetics, vol. IEEE Cat. No.04EX826, 2004. [10] G. Lang, D. Miao, T. yang and M. Cai, “Knowledge reduction of dynamic covering decision information systems when varying covering cardinalities,” Information Sciences, vol. 346-347, pp. 336–260, 2016. [Online]. Available: [11] G. P. Lin, J. Y. Liang and Y. H. Qian, “Multigranulation rough sets : from partition to covering,” Inform. Sci, vol. 241, pp. 101–118, 2013. [12] H.M. Chen, T.R. Li, D. Ruan, J.H. Lin and C. Hu, “A rough-set based incremental approach for updating approximations under dynamic maintenance environments,” IEEE Transactions on Knowledge and Data Engineering, vol. 25, no. 2, pp. 274–284, 2013. [13] J. Stefanowski and A. Tsouki, “On the extension of rough sets under incomplete information,” Lecture Notes in ArtificialIntelligence, vol. 1711, pp. 73–81, 1999. [14] J.A. Pomykala, “Approximation operations in approximation space,” Bulletin Polonaise Aca- demy of Science, vol. 35 (9-10), pp. 653–662, 1987. [15] M. Kryszkiewicz, “Rough set approach to incomplete information systems,” Information Science, vol. 112, pp. 39–49, 1998. [16] M.J. Cai, Q.G. Li and J. Ma, “Knowledge reduction of dynamic covering decision information systems caused by variations of attribute values,” in J.Mach, Learn & Cyber, 2015. [17] S. Greco, B. Matarazzo and R. Sowinski, “Parameterized rough set model using rough mem- bership and bayesian confirmation measures,” International Journal of Approximate Reasoning, vol. 49, no. 2, pp. 285–300, 2008. [18] T. R. Li, D. Ruan, W. Geert, J. Song and Y. Xu, “A rough sets based characteristic relation ap- proach for dynamic attribute generalization in data mining,” Knowledge Based Systems, vol. 20, pp. 485–494, 2007. [19] W. Xu and W. X. Zhang, “Measuring roughness of generalized rough sets induced by a covering,” Fuzzy Sets and Systems, vol. 158, pp. 2443–245, 2007.
15. INCREMENTALLY UPDATING APPROXIMATION ININCOMPLETE 379 [20] W. Zakowski, “Approximations in the space (u; ),” Demonstratio Mathematica, vol. 16, pp. 761–769, 1983. [21] W. Zhu and F. Wang, “On three types of covering-based rough sets,” IEEE Transactions on Knowledge and Data Engineeringa, vol. 19, no. 8, pp. 1131–1144, August 12007. [22] X. Ge, P. Wang and Z. Yun, “The rough membership functions on four types of covering-based rough sets and their applications,” Information Sciences, vol. 390, pp. 1–14, 2017. [23] Y. Y. Yao and S. K. M. Wong, “A decision-theoretic framework for approximating concepts,” International Journal of Man-Machine Studies, vol. 37, no. 6, 1992. [24] Y. Yao and B. Yao, “Covering based rough set approximations,” Information Sciences, vol. 200, pp. 91–107, 2012. [25] Z. Bonikowski, E. Bryniarski and U. Wybraniec-Skardowska, “Extensions and intentions in the rough set theory,” Information Sciences, vol. 107, pp. 149–167, 1998. [26] Z. H. Shi and Z. T. Gong, “The further investigation of covering-based rough sets: uncertainty characterization, similarity measure and generalized models,” Inform. Sci, vol. 180, pp. 3745– 3763, 2010. [27] Z. Pawlak, “Rough sets,” in J. of Computer and Information Sciences, vol. 11, 1982, pp. 341–356. [28] W. Zhu, “Relationship among basic concepts in covering-based rough sets,” Information Sciences, vol. 179, no. 14, pp. 2478–2486, 2004. [Online]. Available: ins.2009.02.013 Received on November 27, 2019 Revised on November 24, 2020