Incremental update of rough set approximation under the grade indiscernibility relation

Junfang Luo; Yaya Liu; Keyun Qin; Heng Ding

doi:10.2991/ijcis.2017.10.1.15

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Volume 10, Issue 1, 2017, Pages 212 - 233

Incremental update of rough set approximation under the grade indiscernibility relation

Authors

Junfang Luo¹^,junfangluo@163.com, Yaya Liu¹^,1109731034@qq.com, Keyun Qin¹^{, *}^,keyunqin@263.net, Heng Ding²^,dh_swjtu@163.com

^*Corresponding author.

Corresponding Author

Keyun Qinkeyunqin@263.net

Received 28 March 2016, Accepted 30 September 2016, Available Online 1 January 2017.

DOI: 10.2991/ijcis.2017.10.1.15 How to use a DOI?
Keywords: Rough set; Fuzzy relation; The grade indiscernibility relation; Incremental learning; Approximation operators
Abstract: The incremental updating of lower and upper approximations under the variation of information systems is an important issue in rough set theory. Many incremental updating approaches with respect to different kinds of indiscernibility relations have been proposed. The grade indiscernibility relation is a fuzzification of classical Pawlak’s indiscernibility relation which can characterize the similarity between objects more precisely. Based on fuzzy rough set model, this paper discusses the approaches for dynamically acquiring of the upper and lower approximations with respect to the grade indiscernibility relation when adding and removing an attribute or an object, and changing the attribute value of the object, respectively. Since the approaches are used in succession, they make the approximations can be updated correctly and effectively when any kind of possible change in the information system. Finally, extensive experiments on data sets from University of California, Irvine (UCI) show that the incremental methods effectively reduce the computing time in comparison with the traditional non-incremental method.
Copyright: © 2017, the Authors. Published by Atlantis Press.
Open Access: This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

1. Introduction

Rough set theory, a mathematical tool for dealing with vagueness and uncertainty, was introduced by Pawlak in 1982¹. It can be used in attribute value representation models to describe the dependencies among attributes, evaluate the significance of attributes and derive decision rules^2,3,4,5,6. Rough set-based data analysis starts from a data table, also called an information system, which contains data about objects of interest that are characterized by a finite set of attributes. Objects with the same information are indiscernible and the indiscernibility relation generated in this way forms the mathematical basis for the theory of rough sets. By using the indiscernibility relation, a rough set is characterized by a pair of sets, called the lower and upper approximations. In recent years, classical rough sets have been extended to several general models, such as covering rough set model⁷, fuzzy rough set model⁸, variable precision rough set model⁹, generalized rough set model¹⁰, probabilistic rough set model¹¹, etc.

With the rapid development of modern information technology, different types of data have increased dramatically. In many real-time cases, information systems may evolve over time, in other words, some new information becomes available continuously while some information is no longer useful. One can retrain the system from scratch whenever adding or removing data(attributes or objects), which is known as a non-incremental approach¹². However, the non-incremental approach becomes very costly or even intractable as the number of data grows. Alternatively, one can also apply an incremental learning scheme¹². The essence of incremental learning is to allow the learning process to take place in a continuous and progressive manner rather than a one-shot experience¹³. The research on updating knowledge incrementally has shown its importance in many areas, such as clinical decision making, intrusion detection, stock evaluation, and text categorization¹⁴. Some incremental learning methods with respect to rough set theory have been proposed^14,15,16,17. Chan firstly put forward an incremental method for updating the approximations of a crisp concept based on the lower and upper boundary sets¹⁵. Li et al. presented an incremental method of updating decision rules when multi-attributes are deleted or added simultaneously under rough set based on the characteristic relation¹⁶. Zhang et al. investigated the approach for updating approximations under neighborhood rough sets¹⁷. Cheng proposed two incremental methods for the fast computing of the rough fuzzy approximations based on the boundary set and the cut sets of a fuzzy set, respectively¹⁴. These studies have significantly enriched the theory of rough set and guided a way for dynamic data mining, even big data mining.

The indiscernibility relation is a key notion of rough set theory, which partitions the object set of an information system into a collection of equivalence classes. Zhao proposed the notion of grade indiscernibility relation which is a fuzzy relation for information system to characterize the difference between the grades of discernibility¹⁸. Based on fuzzy rough set model⁸, Qin investigated rough approximation operators based on the grade indiscernibility relation¹⁹. For the sake of better applying of the grade indiscernibility relation, Luo extend it to incomplete information system²⁰. The value tolerance relation based rough approximation operators are investigated²¹. In this way, we defined the approximation operators based on the grade indiscernibility relation in the same manner²⁰. Furthermore, the rule acquisition and attribute reduction are discussed, and the advantages of the grade of indiscernibility relation are also explained. In this paper, we discusses the approaches for incrementally acquiring approximations based on the grade indiscernibility relation when the information system changes. Due to these approaches are used in succession, they can effectively updated approximations when any possible changes in the information system occur. In order to show the succession of the approaches, examples in this paper are used as input from the output of the example before it. And it should be noted that the order of the information system changes can be arbitrary.

This paper is arranged as follows. In Section 2, we review some fundamental concepts of Pawlak rough sets and the grade indiscernibility relation. The remainders of the sections are focused on the approaches for incrementally updating approximations based on the grade indiscernibility relation when the information system varies with time. With changes of the attribute set, we discuss how to acquire approximation operators in Section 3. In Section 4, we investigate the methods for updating approximations when adding or removing an object in the universal set. The approaches for updating approximations when changing the attribute value of object is given in Section 5. In Section 6, we analyze the time complexity of algorithms presented in Section 3,4,5. In Section 7, the incremental methods are evaluated on data sets from UCI. Finally we conclude the work of this paper and preview the further work.

2. Preliminaries

In this section, for our further development, we briefly review some basic notions of Pawlak rough set¹ and the grade indiscernibility relation¹⁸. Meanwhile, the traditional non-incremental algorithm of calculating approximations is presented.

2.1. The grade indiscernibility relation

Definition 1 ¹

An information system is a quadruple S = (U,A,V,F), where

(1)
U = {x₁,x₂,⋯,x_n} is a nonempty finite set of objects called the universe of discourse;
(2)
A is a nonempty finite set of attributes;
(3)
V=∪a∈AVa , V_a is the values domain of a;
(4)
f : U × A → V is an information function such that f(x,a) ∈ V_a, for any x ∈ U, a ∈ A.

Definition 2 ¹

Let S = (U,A,V,F) be an information system, B ⊆ A, the indiscernibility relation ind(B) induced by B is defined as:

ind(B)={(x,y)∈U×U;∀b∈B(f(x,b)=f(y,b))}.

Clearly, ind(B) is an equivalence relation. If (x,y) ∈ ind(B), then x and y are indiscernible with respect to B. It is noticed that, if x and y are discernible with respect to B, i.e. (x,y) ∉ ind(B), then there exists at least one attribute b ∈ B such that f(x,b) ≠ f(y,b). Thus the grade of discernibility may be different for different pairs of objects. The difference has not been described in Pawlak’s indiscernibility relation. To address this issue, Zhao proposed the grade indiscernibility relation for information system¹⁸, which is defined as follows.

Definition 3 ¹⁸

Let S = (U,A,V,F) be an information system, B ⊆ A, the grade indiscernibility relationship GR_B on B is a binary fuzzy relation on U, i.e. GR_B : U × U → [0, 1], and for any x,y ∈ U,

GRB(x,y)=1|B||{b∈B;f(x,b)=f(y,b)}|.

According to this definition, GR_B(x,y) represents the proportion of undistinguishable attribute of x and y in B. Clearly, (x,y) ∈ ind(B) if and only if GR_B(x,y) = 1. Thus, GR_B is a kind of fuzzification of a indiscernibility relation ind(B). It is noticed that GR_B is a reflexive and symmetric fuzzy relation, but not necessarily transitive, i.e., GR_B(x,y) ∧ GR_B(y,z) ≤ GR_B(x,z) is not necessarily hold. From the point of fuzzy rough set model⁸, Qin presented approximation operators based on grade indiscernibility relation¹⁹.

Definition 4 ¹⁹

Let S = (U,A,V,F) be an information system, B ⊆ A. For any fuzzy subset μ ∈ F(U), the lower approximation GR¯B(μ) and the upper approximations GR¯B(μ) of μ are defined as follows:

∀x∈U, GR¯B(μ)(x)=∧y∈U((1−GRB(x,y))∨μ(y)); GR¯B(μ)(x)=∨y∈U(GRB(x,y)∧μ(y)).

In this definition, if X ∈ P(U) is a subset of U, then

GR¯B(X)(x)=∧y∈U−X(1−GRB(x,y)),GR¯B(X)(x)=∨y∈XGRB(x,y).

Clearly, by the reflexivity of GR_B(x,y), we have GR¯B(X)⊆X⊆GR¯B(X) for any X ⊆ U.

2.2. The non-incremental algorithm of computing approximations

In order to get the approximations based on the grade indiscernibility relation, the non-incremental method will firstly build the relation matrix and then get the approximations from the matrix. The calculation process of the traditional way can be represented as the following Steps in Algorithm 2.1.

Step 1: Input S = (U,A,V,f), X, B.
Step 2: Build the relation matrix M_n×m, where n = |X|, m = |U − X|.
Mn×m=GRB(xi,xj)=1|B||{b∈B|,f(xi,b)=f(xj,b)}|,
x_i ∈ X, x_j ∈ U − X.
Step 3: Calculate the lower approximations GR¯B(X)(xi)=∧y∈U−X(1−GRB(xi,y))=1−∨y∈U−XGRB(xi,y) and the set Yxi∧={y∈U−X;∨y∈U−XGRB(xi,y)} , x_i ∈ X
Step 4: Calculate the upper approximations GR¯B(X)(xj)=∨y∈XGRB(xj,y) and the set Yxj∨={y∈X;∨y∈XGRB(xj,y)} , x_j ∈ U − X.
Step 5: Output the M_n×m; GR¯B(X)(xi) and Yxi∧ , x_i ∈ X; GR¯B(X)(xj and Yxj∨ , x_j ∈ U − X; GR¯B(X)(xi)=0 , x_i ∈ U − X; GR¯B(X)(xj=1 , x_j ∈ X.

Algorithm 2.1

(The traditional non-incremental algorithm of computing approximations)

It is easy to see that Algorithm 2.1 has a time complexity of O(|X| |U − X| |B|), which is mainly decided by the time cost of building the relation matrix in Step 2. The following Example 1 shows the progress of using the Algorithm 2.1 to get the approximations based on the grade indiscernibility relation.

Example 1

Let U = {x₁,x₂,x₃,x₄,x₅,x₆} be the universal set, A = {b₁,b₂,b₃,b₄,b₅} be the conditional attribute set, B = {b₁,b₂,b₃,b₄}, X = {x₂,x₃,x₆} be the decision set. The related information system is given in Table 1.

	b₁	b₂	b₃	b₄	b₅	d
x₁	2	2	1	1	3	U − X
x₂	2	2	1	2	2	X
x₃	2	2	2	1	3	X
x₄	1	1	1	2	2	U − X
x₅	1	2	2	2	3	X
x₆	1	1	2	2	2	U − X

From the Step 2 of Algorithm 2.1 we have a relation matrix M_3×3, where GR_B(x,y), x_i ∈ X, x_j ∈ U − X.

x1 x4 x5M3×3=x2x3x6(3/42/42/43/402/403/43/4)

The first column is the object that x_i ∈ X. The first row is the object that x_j ∈ U − X.

From the step 3 of algorithm 2.1 we have the lower approximations:

GR¯B(X)(x2)=∧y∈U−X(1−GRB(x2,y)=1−∨y∈U−XGRB(x2,y)=1−34=14 , and Yx2∧={y;∨y∈U−XGRB(x2,y)}={x1} .
GR¯B(X)(x3)=∧y∈U−X(1−GRB(x3,y)=1−∨y∈U−XGRB(x3,y)=1−34=14 , and Yx3∧={y;∨y∈U−XGRB(x3,y)}={x1} .
GR¯B(X)(x6)=∧y∈U−X(1−GRB(x6,y)=1−∨y∈U−XGRB(x6,y)=1−34=14 , and Yx6∧={y;∨y∈U−XGRB(x6,y)}={x4,x5} .
GR¯B(X)(xi)=0 , x_i ∈ {x₁,x₄,x₅}.

From the step 4 of algorithm 2.1 we have the upper approximations:

GR¯B(X)(x1)=∨y∈XGRB(x1,y)=34 , and Yx1∨={y∈X;∨y∈XGRB(x1,y)}={x2,x3} .
GR¯B(X)(x4)=∨y∈XGRB(x4,y)=34 , and Yx4∨={y∈X;∨y∈XGRB(x4,y)}={x6} .
GR¯B(X)(x5)=∨y∈XGRB(x5,y)=34 , and Yx5∨={y∈X;∨y∈XGRB(x5,y)}={x6} .
GR¯B(X)(xj)=1 , x_j ∈ {x₂,x₃,x₆}.

3. Incrementally updating approximations while adding or removing an attribute

The traditional non-incrementally update method is based on static information system, which has huge time complexity as the number of data grows. Incremental update method can improve the efficiency by using the existing approximation knowledge¹⁸.

3.1. Incrementally updating approximations when adding an attribute

Proposition 1

Let S = (U,A,V,F) be an information system, B ⊆ A, b ∈ A and b ∉ B. For any x,y ∈ U,

GRB∪{b}(x,y)=|B|·GRB(x,y)+GR{b}(x,y)|B|+1={|B|·GRB(x,y)+1|B|+1,f(x,b)=f(y,b);|B|·GRB(x,y)|B|+1,f(x,b)≠f(y,b).

Proof.

This proof is straightforward.

Proposition 2

Let S = (U,A,V,F) be an information system, B ⊆ A, b ∈ A, b ∉ B, X ⊆ U. The lower and upper approximations of X by adding b to B can be updated respectively as follows.

Lower approximation: If x_i ∈ U − X, then GR¯B∪{b}(X)(xi)=GR¯B(X)(xi)=0 ; If x_i ∈ X, then
GR¯B∪{b}(X)(xi)={|B|GR¯B(X)(xi)|B|+1,∃y∈Yxi∧(f(xi,b)=f(y,b));1+|B|GR¯B(X)(xi)|B|+1,∀y(y∈Yxi∧→f(xi,b)≠f(y,b)).

Where Yxi∧={y∈U−X;GR¯B(X)(xi)=1−GRB(xi,y)}={y;∨y∈U−XGRB(xi,y)} .
Upper approximation: If x_j ∈ X, then GR¯B∪{b}(X)(xj)=GR¯B(X)(xj)=1 ; If x_j ∈ U − X, then
GR¯B∪{b}(X)(xj)={|B|GR¯B(X)(xj)+1|B|+1,∃y∈Yxj∨(f(xj,b)=f(y,b));|B|GR¯B(X)(xj)|B|+1,∀y(y∈Yxj∨→f(xj,b)≠f(y,b)).

Proof.

Lower approximation: For any x_i ∈ U − X, It is obviously that GR¯B∪{b}(X)(xi)=GR¯B(X)(xi)=0 .

For any x_i ∈ X, if ∃y∈Yxi∧ such that f(x_i,b) = f(y,b), then GR¯B∪{b}(X)(xi)=1−GRB∪{b}(xi,y)=1−|B|GRB(xi,y)+1|B|+1=1−|B|(1−GR¯B(X)(xi))+1|B|+1=|B|GR¯B(X)(xi)|B|+1 .

If f(x_i,b) ≠ f(y,b) for any y∈Yxi∧ , then
GR¯B∪{b}(X)(xi)=∧y∈U−X(1−GRB∪{b}(xi,y))=1−(GRB∪{b}(xi,y0)∨(∨y∈U−X−Yxi∧,f(xi,b)=f(y,b)GRB∪{b}(xi,y)))=1− (|B|GRB(xi,y0)|B|+1∨(∨y∈U−X−Yxi∧,f(xi,b)=f(y,b)|B|GRB(xi,y)+1|B|+1),
where y0∈Yxi∧ . For any y∈U−X−Yxi∧ , we have GR_B(x_i,y₀) > GR_B(x_i,y), that is |B|GRB(xi,y0)|B|+1≥|B|GRB(xi,y)+1|B|+1 . Therefore, GR¯B∪{b}(X)(xi)=1−|B|GRB(xi,y0)|B|+1=|B|GR¯B(X)(xi)+1|B|+1 .
Upper approximation: For any x_j ∈ X, it is obviously that GR¯B∪{b}(X)(xj)=GR¯B(X)(xj)=1 .

For any x_j ∈ U − X, if ∃y∈Yxj∨ , such that f(x_j,b) = f(y,b), then GR¯B∪{b}(X)(xj)=GRB∪{b}(xj,y)=|B|GRB(xj,y)+1|B|+1=|B|GR¯B(X)(xj)+1|B|+1 .

If f(x_j,b) ≠ f(y,b) for any y∈Yxj∨ , then
GR¯B∪{b}(X)(xj)=∨y∈XGRB∪{b}(xj,y)=GRB∪{b}(xj,y0)∨(∨y∈X−Yxj∨,f(xj,b)=f(y,b)GRB∪{b}(xj,y))=|B|GRB(xj,y0)|B|+1 ∨ (∨y∈X−Yxj∨,f(xj,b)=f(y,b)|B|GRB(xj,y)+1|B|+1),
where y0∈Yxj∨ . For any y∈X−Yxj∨ , we have GR_B(x_j,y₀) > GR_B(x_j,y), that is |B|GRB(xj,y0)|B|+1≥|B|GRB(xj,y)+1|B|+1 . Therefore, GR¯B∪{b}(X)(xj)=|B|GRB(xj,y0)|B|+1=|B|GR¯B(X)(xj)|B|+1 .

Particularly, if Yxi∧={yk} and Yxj∨={yl} are subsets of the universe with single element, the lower and upper approximations of X by adding b to B can be updated respectively as follows.

Lower approximation: If x_i ∈ U − X, then GR¯B∪{b}(X)(xi)=GR¯B(X)(xi)=0 ; If x_i ∈ X, then
GR¯B∪{b}(X)(xi)={|B|GR¯B(X)(xi)|B|+1,f(xi,b)=f(yk,b);|B|GR¯B(X)(xi)+1|B|+1,f(xi,b)≠f(yk,b).
Upper approximation: If x_j ∈ X, then GR¯B∪{b}(X)(xj)=GR¯B(X)(xj)=1 ; If x_j ∈ U − X, then
GR¯B∪{b}(X)(xj)={|B|GR¯B(X)(xj)+1|B|+1,f(xj,b)=f(yl,b);|B|GR¯B(X)(xj)|B|+1,f(xj,b)≠f(yl,b).

Since the incremental update approaches need to use the set of Yxi∧ and Yxj∨ , in order to maintain the continuity of the approaches, Yxi∧ and Yxj∨ also need to update.

Proposition 3

The set of Yxi∧ and Yxj∨ by adding b to B can be updated respectively as follows.

Yxi∧*={{y∈Yxi∧;f(xi,b)=f(y,b)},∃y∈Yxi∧(f(xi,b)=f(y,b));{y;∨y∈U−XGRB∪{b}(xi,y)},∀y(y∈Yxi∧→f(xi,b)≠f(y,b)).Yxj∨*={{y∈Yxj∨;f(xj,b)=f(y,b)},∃y∈Yxj∨(f(xj,b)=f(y,b));{y;∨y∈XGRB∪{b}(xj,y)},∀y(y∈Yxj∨→f(xj,b)≠f(y,b)).

Step 1: Input the relation matrix M_n×m; GR¯B(X)(xi) , Yxi∧ , x_i ∈ X; GR¯B(X)(xj , Yxj∨ , x_j ∈ U − X; the increasing attribute b.
Step 2: We get a new relation matrix
Mn×m*=GRB∪{b}(xi,xj)={|B|·GRB(xi,xj)+1|B|+1,f(xi,b)=f(xj,b);|B|·GRB(xi,xj)|B|+1,f(xi,b)≠f(xj,b).
x_i ∈ X, x_j ∈ U − X. // According to Proposition 1.
Step 3: Calculate the lower approximations x_i ∈ X.

If ∃y∈Yxi∧ , such that f(x_i,b) = f(y,b), then GR¯B∪{b}(X)(xi)=|B|GR¯B(X)(xi)|B|+1 and Yxi∧*={y∈Yxi∧;f(xi,b)=f(y,b)} .

Else GR¯B∪{b}(X)(xi)=1+|B|GR¯B(X)(xi)|B|+1 and Yxi∧*={y;∨y∈U−XGRB∪{b}(xi,y)} . // According to Proposition 2 and 3.
Step 4: Calculate the upper approximations x_j ∈ U − X.

If ∃y∈Yxj∨ , such that f(x_j,b) = f(y,b) then GR¯B∪{b}(X)(xj)= |B|GR¯B(X)(xj)+1|B|+1 and Yxj∨*={y∈Yxj∨;f(xj,b)=f(y,b)} .

Else GR¯B∪{b}(X)(xj)= |B|GR¯B(X)(xj)|B|+1 and Yxj∨*={y;∨y∈XGRB∪{b}(xj,y)} . // According to Proposition 2 and 3.
Step 5: Output the relation matrix Mn×m* ; GR¯B∪{b}(X)(xi) , Yxi∧* , x_i ∈ X; GR¯B∪{b}(X)(xj) , Yxj∨* , x_j ∈ U − X; GR¯B∪{b}(X)(xi)=0 , x_i ∈ U − X; GR¯B∪{b}(X)(xj)=1 , x_j ∈ X.

Algorithm 3.1

(Incremental algorithm for updating approximations when adding an attribute b)

The time complexity of Algorithm 3.1 is O(|X| |U − X|), which is mainly decided by the time cost of building the relation matrix in Step 2. In the following Example 2, We use the results from Example 1 to demonstrate how algorithm 3.1 update the approximations when adding an attribute.

Example 2

We consider the information system given in Table 1. Let U = {x₁,x₂,x₃,x₄,x₅,x₆} be the universal set, B = {b₁,b₂,b₃,b₄} be the conditional attribute set, X = {x₂,x₃,x₆} be the decision set. Adding an attribute b₅ to B.

Using the result of Example 1.

x1 x4 x5M3×3=x2x3x6(3/42/42/43/402/403/43/4)

GR¯B(X)(x2)=14 , Yx2∧={x1} ; GR¯B(X)(x3)=14 , Yx3∧={x1} ; GR¯B(X)(x6)=14 , Yx6∧={x4,x5} ; GR¯B(X)(xi)=0 , x_i ∈ {x₁,x₄,x₅}.

GR¯B(X)(x1)=34 , Yx1∨={x2,x3} ; GR¯B(X)(x4)=34 , Yx4∨={x6} ; GR¯B(X)(x5)=34 , Yx5∨={x6} ; GR¯B(X)(xj)=1 , x_j ∈ {x₂,x₃,x₆}.

From the Step 2 of Algorithm 3.1 we have a new relation matrix M3×3* :

x1 x4 x5M3×3*=x2x3x6(3/53/52/54/503/504/53/5)

The lower and upper approximations of X = {x₂,x₃,x₆} by adding b₅ to B are updated as follows.

From the step 3 of algorithm 3.1 we have the lower approximations:

GR¯B∪{b5}(X)(x2) : For any y∈Yx2∧ , f(x₂,b₅) ≠ f(y,b₅). So we have GR¯B∪{b5}(X)(x2)=1+14+1=25 and Yx2∧*={y;∨y∈U−XGRB∪{b5}(x2,y)}={x1,x4} .
GR¯B∪{b5}(X)(x3) : ∃x1∈Yx3∧ , such that f(x₃,b₅) = f(x₁,b₅), then GR¯B∪{b5}(X)(x3)=14+1=15 and Yx3∧*={y∈Yx3∧;f(x,b5)=f(y,b5)}={x1} .
GR¯B∪{b5}(X)(x6) : ∃x4∈Yx6∧ , such that f(x₆,b₅) = f(x₄,b₅), then GR¯B∪{b5}(X)(x6)=14+1=15 and Yx6∧*={y∈Yx6∧;f(x,b5)=f(y,b5)}={x4} .
GR¯B∪{b5}(X)(xi)=0 , x_i ∈ {x₁,x₄,x₅}.

From the step 4 of algorithm 3.1 we have the upper approximations:

GR¯B∪{b5}(X)(x1) : ∃x2∈Yx1∨ , such that f(x₁,b₅) = f(x₂,b₅), then GR¯B∪{b5}(X)(x1)=3+14+1=45 and Yx1∨*={y∈Yx1∨;f(x1,b5)=f(y,b5)}={x3} .
GR¯B∪{b5}(X)(x4) : ∃x6∈Yx4∨ , such that f(x₄,b₅) = f(x₆,b₅), then GR¯B∪{b5}(X)(x4)=3+14+1=45 and Yx4∨*={y∈Yx4∨;f(x4,b5)=f(y,b5)}={x6} .
GR¯B∪{b5}(X)(x5) : For any y∈Yx5∨ , f(x₅,b₅) ≠ f(y,b₅), so we have GR¯B∪{b5}(X)(x5)=34+1=35 and Yx5∨*={y;∨y∈XGRB∪{b5}(x5,y)}={x3,x6} .
GR¯B∪{b5}(X)(xj)=1 , x_j ∈ {x₂,x₃,x₆}.

3.2. Incrementally updating approximations when removing an attribute

Proposition 4

Let S = (U,A,V,F) be an information system, B ⊆ A, b ∈ B. For any x,y ∈ U,

GRB−{b}(x,y)=|B|·GRB(x,y)−GR{b}(x,y)|B|−1={|B|·GRB(x,y)+1|B|+1,f(x,b)=f(y,b);|B|·GRB(x,y)|B|+1,f(x,b)≠f(y,b).

Proof.

This proof is straightforward.

Proposition 5

Let S = (U,A,V,F) be an information system, B ⊆ A, b ∈ B, X ⊆ U. The lower and upper approximations of X by removing b from B can be updated respectively as follows.

Lower approximation: If x_i ∈ U − X, then GR¯B−{b}(X)(xi)=GR¯B(X)(xi)=0 ; If x_i ∈ X, then
GR¯B−{b}(X)(xi)={|B|GR¯B(X)(xi)−1|B|−1,∃y∈Yxi∧(f(xi,b)≠f(y,b));|B|GR¯B(X)(xi)|B|−1,∀y(y∈Yxi∧→f(xi,b)=f(y,b)).

Where Yxi∧={y∈U−X;GR¯B(X)(xi)=1−GRB(xi,y)}={y;∨y∈U−XGRB(xi,y)} .
Upper approximation: If x_j ∈ X, then GR¯B−{b}(X)(xj)=GR¯B(X)(xj)=1 ; If x_j ∈ U − X, then
GR¯B−{b}(X)(xj)={|B|GR¯B(X)(xj)|B|−1,∃y∈Yxj∨(f(xj,b)≠f(y,b));|B|·GRB(x,y)|B|−1,f(x,b)≠f(y,b).

Where Yxj∨={y∈X;GR¯B(X)(xj)=GRB(xj,y)}={y;∨y∈XGRB(xj,y)} .

Proof.

Lower approximation: For any x_i ∈ U − X, it is obviously that GR¯B−{b}(X)(xi)=GR¯B(X)(xi)=0 .

For any x_i ∈ X, if ∃y∈Yxi∧ , such that f(x_i,b) ≠ f(y,b), then GR¯B−{b}(X)(xi)=1−GRB−{b}(xi,y)=1−|B|GRB(xi,y)|B|−1=1−|B|1−GR¯B(X)(xi))|B|−1=|B|GR¯B(X)(xi)−1|B|−1 .

If f(x_i,b) = f(y,b) for any y∈Yxi∧ , then
GR¯B−{b}(X)(xi)=∧y∈U−X(1−GRB−{b}(xi,y))=1−(GRB−{b}(xi,y0)∨(∨y∈U−X−Yxi∧,f(xi,b)≠f(y,b)GRB−{b}(xi,y)))=1−(|B|GRB(xi,y0)−1|B|−1∨(∨y∈U−X−Yxi∧,f(xi,b)≠f(y,b)|B|GRB(xi,y)|B|−1),
where y0∈Yxi∧ . For any y∈U−X−Yxi∧ , we have GR_B(x_i,y₀) > GR_B(x_i,y), that is |B|GRB(xi,y0)−1|B|−1≥|B|GRB(xi,y)|B|−1 . Therefore, GR¯B−{b}(X)(xi)=1−|B|GRB(xi,y0)−1|B|−1=|B|GR¯B(X)(xi)|B|−1 .
Upper approximation: For any x_j ∈ X, it is obviously that GR¯B−{b}(X)(xj)=GR¯B(X)(xj)=1 . For any x_j ∈ U − X, if ∃y∈Yxj∨ such that f(x_j,b) ≠ f(y,b), then GR¯B−{b}(X)(xj)=GRB−{b}(xj,y)=|B|GRB(xj,y)|B|−1=|B|GR¯B(X)(xj)|B|−1 .

If f(x_j,b) = f(y,b) for any y∈Yxj∨ , then
GR¯B−{b}(X)(xj)=∨y∈XGRB−{b}(xj,y)=GRB−{b}(xj,y0)∨(∨y∈X−Yxj∨,f(xj,b)≠f(y,b)GRB−{b}(xj,y))=|B|GRB(xj,y0)−1|B|−1∨(∨y∈X−Yxj∨,f(xj,b)≠f(y,b)|B|GRB(xj,y)|B|−1),
where y0∈Yxj∨ . For any y∈X−Yxj∨ , we have GR_B(x_j,y₀) > GR_B(x_j,y), that is |B|GRB(xj,y0)−1|B|−1≥|B|GRB(xj,y)|B|−1 . Therefore, GR¯B−{b}(X)(xj)=|B|GRB(xj,y0)−1|B|−1=|B|GR¯B(X)(xj)−1|B|−1 .

Particularly, if Yxi∧={yk} and Yxj∨={yl} are subsets of the universe with single element, the lower and upper approximations of X by removing b from B can be updated respectively as follows.

Lower approximation: If x_i ∈ U − X, then GR¯B−{b}(X)(xi)=GR¯B(X)(xi)=0 . If x_i ∈ X, then
GR¯B−{b}(X)(xi)={|B|GR¯B(X)(xi)−1|B|−1,f(xi,b)≠f(yk,b);|B|GR¯B(X)(xi)|B|−1,f(xi,b)=f(yk,b).
Upper approximation: If x_j ∈ X, then GR¯B−{b}(X)(xj)=GR¯B(X)(xj)=1 . If x_j ∈ U − X, then
GR¯B−{b}(X)(xj)={|B|GR¯B(X)(xj)|B|−1,f(xj,b)≠f(yl,b);|B|GR¯B(X)(xj)−1|B|−1,f(xj,b)=f(yl,b).

Proposition 6

The set of Yxi∧ and Yxj∨ by removing b from B can be updated respectively as follows.

Yxi∧*={{y∈Yxi∧;f(xi,b)=f(y,b)},∃y∈Yxi∧(f(xi,b)≠f(y,b));{y;∨y∈U−XGRB−{b}(xi,y)},∀y(y∈Yxi∧→f(xi,b)=f(y,b)).Yxj∨*={{y∈Yxj∨;f(xj,b)=f(y,b)};∃y∈Yxj∨(f(xj,b)≠f(y,b)),{y;∨y∈XGRB−{b}(xj,y)};∀y(y∈Yxj∨→f(xj,b)=f(y,b)).

Step 1: Input the relation matrix M_n×m; GR¯B(X)(xi) , Yxi∧ , x_i ∈ X; GR¯B(X)(xj , Yxj∨ , x_j ∈ U − X.
Step 2: We get a new relation matrix
Mn×m*=GRB−{b}(xi,xj)={|B|·GRB(xi,xj)+1|B|+1,f(xi,b)=f(xj,b);|B|·GRB(xi,xj)|B|+1,f(xi,b)≠f(xj,b).
x_i ∈ X, x_j ∈ U − X. // According to Proposition 4.
Step 3: Calculate the lower approximations x_i ∈ X

If ∃y∈Yxi∧(f(xi,b)≠f(y,b) , then GR¯B−{b}(X)(xi)=|B|GR¯B(X)(xi)−1|B|−1 and Yxi∧*={y∈Yxi∧;f(xi,b)=f(y,b)} .

Else Yxi∧*={y;∨y∈U−XGRB−{b}(xi,y)} and GR¯B−{b}(X)(xi)=|B|GR¯B(X)(xi)|B|−1 . // According to Proposition 5 and 6.
Step 4: Calculate the upper approximations x_j ∈ U − X

If ∃y∈Yxj∨(f(xj,b)≠f(y,b)) , then GR¯B−{b}(X)(xj)=|B|GR¯B(X)(xj)|B|−1 and Yxj∨*={y∈Yxj∨;f(xj,b)=f(y,b)} .

Else GR¯B−{b}(X)(xj)=|B|GR¯B(X)(xj)−1|B|−1 and Yxj∨*={y;∨y∈XGRB−{b}(xj,y)} . // According to Proposition 5 and 6.
Step 5: Output the relation matrix Mn×m* ; GR¯B(X)(xi) , Yxi∧ , x_i ∈ X; GR¯B(X)(xj , Yxj∨ , x_j ∈ U − X; GR¯B(X)(xi)=0 , x_i ∈ U − X; GR¯B(X)(xj=1 , x_j ∈ X.

Algorithm 3.2

(Incremental algorithm for updating approximations when removing an attribute b)

The Algorithm 3.2 has a time complexity of O(|X| |U − X|), which is mainly decided by Step 2. In the following Example 3, We use the results from Example 2 to demonstrate how algorithm 3.2 update the approximations when removing an attribute.

Example 3

We consider the information system given in Table 1. Let U = {x₁,x₂,x₃,x₄,x₅,x₆} be the universal set, B = {b₁,b₂,b₃,b₄,b₅} be the conditional attribute set, X = {x₂,x₃,x₆} be the decision set. Removing an attribute b₂ from B.

Using the result of Example 2.

x1 x4 x5M3×3=x2x3x6(3/53/52/54/503/504/53/5)

GR¯B(X)(x2)=25 , Yx2∧={x1,x4} ; GR¯B(X)(x3)=15 , Yx3∧={x1} ; GR¯B(X)(x6)=15 , Yx6∧={x4} ; GR¯B(X)(xi)=0 , x_i ∈ {x₁,x₄,x₅}.

GR¯B(X)(x1)=45 , Yx1∨={x3} ; GR¯B(X)(x4)=45 , Yx4∨={x6} ; GR¯B(X)(x5)=35 , Yx5∨={x3,x6} ; GR¯B(X)(xj)=1 , x_j ∈ {x₂,x₃,x₆}.

From the Step 2 of Algorithm 3.2 we have a new relation matrix M3×3*

x1 x4 x5M3×3*=x2x3x6(2/43/41/43/402/403/43/4)

The lower and upper approximations of X = {x₂,x₃,x₆} by removing b₂ from B are updated as follows.

From the step 3 of algorithm 3.2 we have the lower approximations:

GR¯B−{b2}(X)(x2) : ∃x4∈Yx2∧ , such that f(x₂,b₂) ≠ f(x₄,b₂), then GR¯B−{b2}(X)(x2)=2−15−1=14 and Yx2∧*={y∈Yx2∧;f(x,b2)≠f(y,b2)}={x4} .

For any y∈Yx3∧ , f(x₃,b₂) = f(y,b₂), so we have GR¯B−{b2}(X)(x3)=15−1=14 and Yx3∧*={y;∨y∈U−XGRB−{b2}(x3,y)}={x1} .

For any y∈Yx6∧ , f(x₆,b₂) = f(y,b₂), so we have GR¯B−{b2}(X)(x6)=15−1=14 and Yx6∧*={y;∨y∈U−XGRB−{b2}(x6,y)}={x4,x5} .
GR¯B−{b2}(X)(xi)=0 , x_i ∈ {x₁,x₄,x₅}.

From the step 4 of algorithm 3.2 we have the upper approximations:

GR¯B−{b2}(X)(x1) : For any y∈Yx1∨ , f(x₁,b₂) = f(y,b₂), so we have GR¯B−{b2}(X)(x1)=4−15−1=34 and Yx1∨*={y;∨y∈XGRB−{b2}(x1,y)}={x3} .
GR¯B−{b2}(X)(x4) : For any y∈Yx4∨ , f(x₄,b₂) = f(y,b₂), so we have GR¯B−{b2}(X)(x4)=4−15−1=34 and Yx4∨*={y;∨y∈XGRB−{b2}(x4,y)}={x2,x6} .
GR¯B−{b2}(X)(x5) : ∃x6∈Yx5∨ , such that f(x₅,b₂) ≠ f(x₆,b₂), then GR¯B−{b2}(X)(x5)=35−1=34 and Yx5∨*={y∈Yx5∨;f(x5,b2)≠f(y,b2)}={x6} .
GR¯B−{b2}(X)(xj)=1 , x_j ∈ {x₂,x₃,x₆}.

4. Incrementally updating approximations while adding or removing an object

In this section, we consider the problem of updating approximations based on the garde indiscernibility relation of a target concept in terms of adding or removing an object.

4.1. Incrementally updating approximations when adding an object

Proposition 7

Let S = (U,A,V,F) be an information system, B ⊆ A, x^∨ ∉ U, X ⊆ U, U^∨ = U ∪ {x^∨}. The lower and upper approximations of X by adding x^∨ to U can be updated respectively as follows.

Lower approximation: When x_i ∈ U^∨ − X, we have GR¯B∨(X)(xi)=0 . When x_i ∈ X, we have:
- If 1−GRB(xi,x∨)>GR¯B(X)(xi) , then GR¯B∨(X)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧ .
- If 1−GRB(xi,x∨)=GR¯B(X)(xi) , then GR¯B∨(X)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧∪{x∨} .
- If 1−GRB(xi,x∨)<GR¯B(X)(xi) , then GR¯B∨(X)(xi)=1−GR¯B(xi,x∨) and Yxi∧*={x∨} .
Upper approximation: If x_j ∈ X, GR¯B∨(X)(xj)=1 ; If x_j ∈ U^∨ − {x^∨} − X, then GR¯B∨(X)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨ . If x_j = x^∨, then GR¯B∨(X)(x∨)=∨y∈XGRB(x∨,y) and Yx∨∨*={y;∨y∈XGRB(x∨,y)} .

Proof.

Lower approximation:

If x_i ∈ X, we have GR¯B∨(X)(xi)=∧y∈(U−X)∪{x∨}(1−GRB(xi,y))=(1−GRB(xi,x∨))∧(∧y∈U−X(1−GRB(xi,y)))=(1−GRB(xi,x∨))∧GR¯B(X)(xi) . If x ∈ U^∨ − X, it is obviously that GR¯B∨(X)(xi)=GR¯B(X)(xi)=0 .
Upper approximation:

If x_j ∈ X, it is obviously that GR¯B∨(X)(xj)=GR¯B(X)(xj)=1 . If x_j ∈ U^∨ − {x^∨} − X, we have GR¯B∨(X)(xj)=∨y∈XGRB(xj,y)=GR¯B(X)(xj) . If x_j = x^∨, we have GR¯B∨(X)(xj)=∨y∈XGRB(xj,y) .

Step 1: Input the relation matrix M_n×m; GR¯B(X)(xi) , Yxi∧ , x_i ∈ X; GR¯B(X)(xj , Yxj∨ , x_j ∈ U − X; the increasing object x^∨.
Step 2: We get a new relation matrix Mn×(m+1)* . // Calculate GR_B(x^∨,x_i), x_i ∈ X.
Step 3: Calculate the lower approximations x_i ∈ X
- If 1−GRB(xi,x∨)>GR¯B(X)(xi) , then GR¯B∨(X)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧ .
- If 1−GRB(xi,x∨)=GR¯B(X)(xi) , then GR¯B∨(X)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧∪{x∨} .
- If 1−GRB(xi,x∨)<GR¯B(X)(xi) , then GR¯B∨(X)(xi)=1−GRB(xi,x∨) and Yxi∧*={x∨} . // According to Proposition 7.
Step 4: Calculate the upper approximations x_j ∈ U^∨ − X

If x_j ∈ U^∨ − {x^∨} − X, then GR¯B∨(X)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨ .

GR¯B∨(X)(x∨)=∨y∈XGRB(x∨,y) and Yx∨∨*={y;∨y∈XGRB(x∨,y)} . // According to Proposition 7.
Step 5: Output the relation matrix Mn×(m+1)* ; GR¯B∨(X)(xi) , Yxi∧* , x_i ∈ X; GR¯B∨(X)(xj) , YxJ∨* , x_j ∈ U^∨ − X. GR¯B∨(X)(xi)=0 , x_j ∈ U^∨ − X, GR¯B∨(X)(xj)=1 , x_j ∈ X.

Algorithm 4.1

(Incremental algorithm for updating approximations when adding an object x^∨ to U − X)

The time complexity of Algorithm 4.1 is O(|X| |B|), which is mainly decided by Step 2. In the following Example 4, We use the results from Example 3 to demonstrate how algorithm 4.1 update the approximations when adding an object to U − X.

Example 4

We consider the information system given in Table 2. Let U = {x₁,x₂,x₃,x₄,x₅,x₆} be the universal set, B = {b₁,b₃,b₄,b₅} be the conditional attribute set, X = {x₂,x₃,x₆} be the decision set. Adding an object x₇ ∈ Ψ to U − X, U^∨ = U ∪ {x₇}.

	b₁	b₃	b₄	b₅	d
x₁	2	1	1	3	U − X
x₂	2	1	2	2	X
x₃	2	2	1	3	X
x₄	1	1	2	2	U − X
x₅	1	2	2	3	U − X
x₆	1	2	2	2	X

Using the result of Example 3.

x1 x4 x5M3×3=x2x3x6(2/43/41/43/402/403/43/4)

GR¯B(X)(x2)=14 , Yx2∧={x4} ; GR¯B(X)(x3)=14 , Yx3∧={x1} ; GR¯B(X)(x6)=14 , Yx6∧={x4,x5} ; GR¯B(X)(xi)=0 , x_i ∈ {x₁,x₄,x₅}.

GR¯B(X)(x1)=34 , Yx1∨={x3} ; GR¯B(X)(x4)=34 , Yx4∨={x2,x6} ; GR¯B(X)(x5)=34 , Yx5∨={x6} ; GR¯B(X)(xj)=1 , x_j ∈ {x₂,x₃,x₆}.

From the Step 2 of Algorithm 4.1 we have a new relation matrix:

x1 x4 x5 x7 M3×4*=x2x3x6(2/43/41/41/43/402/41/403/43/43/4)

The lower and upper approximations of X = {x₂,x₃,x₆} by adding x₇ to U − X are updated as follows.

From the step 3 of algorithm 4.1 we have the lower approximations:

GR¯B∨(X)(x2) : Since 1−GRB(x2,x7)>GR¯B(X)(x2) , then GR¯B∨(X)(x2)=GR¯B(X)(x2)=14 and Yx2∧*=Yx2∧={x4} .
GR¯B∨(X)(x3) : Since 1−GRB(x3,x7)>GR¯B(X)(x3) , then GR¯B∨(X)(x3)=GR¯B(X)(x3)=14 and Yx3∧*=Yx3∧={x1} .
GR¯B∨(X)(x6) : Since 1−GRB(x6,x7)=GR¯B(X)(x6) , then GR¯B∨(X)(x6)=GR¯B(X)(x6)=14 and Yx6∧*=Yx6∧∪{x7}={x4,x5,x7} .
GR¯B∨(X)(xi)=GR¯B(X)(xi)=0 , x_i ∈ {x₁,x₄,x₅,x₇}.

From the step 4 of algorithm 4.1 we have the upper approximations:

GR¯B∨(X)(x7)=∨y∈{x2,x3,x6}GRB(x7,y)=34 , Yx7∨*={y;∨y∈{x2,x3,x6}GRB(x7,y)}={x6} .
GR¯B∨(X)(xj)=GR¯B(X)(xj) , Yxj∨*=Yxj∨ , x_j ∈ {x₁,x₄,x₅}.
GR¯B∨(X)(xj)=1 , x_j ∈ {x₂,x₃,x₆}.

Proposition 8

Let S = (U,A,V,F) be an information system, B ⊆ A, x^∨ ∉ U, X ⊆ U, U^∨ = U ∪ {x^∨}.

The lower and upper approximations of X^∨ = X ∪ {x^∨} by adding x^∨ to X can be updated respectively as follows.

Lower approximation: If x_i ∈ U^∨ − X^∨, then GR¯B∨(X∨)(xi)=0 ; If x_i ∈ X, then GR¯B∨(X∨)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧ . If x_i = x^∨, then GR¯B∨(X∨)(x∨)=∧y∈U∨−X∨(1−GRB(x∨,y)) and Yx∨∧*={y;∨y∈U−XGRB(x∨,y)} .
Upper approximation: When x_j ∈ X^∨, we have GR¯B∨(X∨)(xj)=1 . When x_j ∈ U^∨ − X^∨, we have:
- If GRB(xj,x∨)>GR¯B(X)(xj) , then GR¯B∨(X∨)(xj)=GRB(xj,x∨) and Yxj∨*={x∨} .
- If GRB(xj,x∨)=GR¯B(X)(xj) , then GR¯B∨(X∨)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨∪{x∨} .
- If GRB(xj,x∨)<GR¯B(X)(xj) , then GR¯B∨(X∨)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨ .

Proof.

This proof is similar to that of Proposition 7.

Step 1: Input the relation matrix M_n×m; GR¯B(X)(xi) , Yxi∧ , x_i ∈ X; GR¯B(X)(xj , Yxj∨ , x_j ∈ U − X; the increasing object x^∨.
Step 2: We get a new relation matrix M(n+1)×(m+1)* . // Calculate GR_B(x^∨,x_j), x_j ∈ U − X.
Step 3: Calculate the lower approximations x_i ∈ X^∨

If x_i ∈ X, then GR¯B∨(X∨)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧ . If x_i = x^∨, then GR¯B∨(X∨)(x∨)=∧y∈U∨−X∨(1−GRB(x∨,y)) and Yx∨∧*={y;∨y∈U−XGRB(x∨,y)} . // According to Proposition 8.
Step 4: Calculate the upper approximations x_j ∈ U^∨ − X^∨
- If GRB(xj,x∨)>GR¯B(X)(xj) , then GR¯B∨(X∨)(xj)=GRB(xj,x∨) and Yxj∨*={x∨} .
- If GRB(xj,x∨)=GR¯B(X)(xj) , then GR¯B∨(X∨)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨∪{x∨} .
- If GRB(xj,x∨)<GR¯B(X)(xj) , then GR¯B∨(X∨)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨ . // According to Proposition 8.
Step 5: Output the relation matrix M(n+1)×m* ; GR¯B∨(X∨)(xi) , Yxi∧* , x_i ∈ X^∨; GR¯B∨(X∨)(xj) , Yxj∨* , x_j ∈ U^∨ − X^∨; GR¯B∨(X∨)(xi)=0 , x_i ∈ U^∨ − X^∨, GR¯B∨(X∨)(xj)=1 , x_j ∈ X^∨.

Algorithm 4.2

(Incremental algorithm for updating approximations when adding an object x^∨ to X)

The Algorithm 4.2 has a time complexity of O(|U − X| |B|), which is mainly decided by Step 2. In the following Example 5, We use the results from Example 4 to demonstrate how algorithm 4.2 update the approximations when adding an object to X.

Example 5

We consider the information system given in Table 3. Let U = {x₁,x₂,x₃,x₄,x₅,x₆,x₇} be the universal set, B = {b₁,b₃,b₄,b₅} be the conditional attribute set, X = {x₂,x₃,x₆} be the decision set. Adding x₈ ∈ Φ to X, X^∨ = X ∪ {x₈}.

	b₁	b₃	b₄	b₅	d
x₁	2	1	1	3	U − X
x₂	2	1	2	2	X
x₃	2	2	1	3	X
x₄	1	1	2	2	U − X
x₅	1	2	2	3	U − X
x₆	1	2	2	2	X
x₇	1	2	2	1	U − X

Using the result of Example 4.

x1 x4 x5 x7 M3×4=x2x3x6(2/43/41/41/43/402/41/403/43/43/4)

GR¯B(X)(x2)=14 , Yx2∧={x4} ; GR¯B(X)(x3)=14 , Yx3∧={x1} ; GR¯B(X)(x6)=14 , Yx6∧={x4,x5,x6} ; GR¯B(X)(xi)=0 , x_i ∈ {x₁,x₄,x₅,x₇}.

GR¯B(X)(x1)=34 , Yx1∨={x3} ; GR¯B(X)(x4)=34 , Yx4∨={x2,x6} ; GR¯B(X)(x5)=34 , Yx5∨={x6} ; GR¯B(X)(x7)=34 , Yx5∨={x6} ; GR¯B(X)(xj)=1 , x_j ∈ {x₂,x₃,x₆}.

From the Step 2 of Algorithm 4.2 we have a new relation matrix M4×4* :

x1 x4 x5 x7 M4×4*=x2x3x6x8(2/43/41/41/43/402/41/403/43/43/42/43/41/41/4)

The lower and upper approximations of X^∨ = {x₂,x₃,x₆,x₈} by adding x₈ to X are updated as follows.

From the step 3 of algorithm 4.2 we have the lower approximations:

GR¯B∨(X∨)(x8)=∧y∈{x1,x4,x5,x7}(1−GRB(x8,y))=14 , and Yx8∧*={y;∨y∈{x1,x4,x5,x7}GRB(x8,y)}={x4} .
GR¯B∨(X∨)(xi)=GR¯B(X)(xi) , Yxi∧*=Yxi∧ , x_i ∈ {x₂,x₃,x₆}.
GR¯B∨(X∨)(xi)=0 , x_i ∈ {x₁,x₄,x₅,x₇}.

From the step 4 of algorithm 4.2 we have the upper approximations:

GR¯B∨(X∨)(x1) : Since GRB(x1,x8)<GR¯B(X)(x1) , then GR¯B∨(X∨)(x1)=GR¯B(X)(x1)=34 and Yx1∨*=Yx1∨={x3} .
GR¯B∨(X∨)(x4) : Since GRB(x4,x8)=GR¯B(X)(x4) , then GR¯B∨(X∨)(x4)=GR¯B(X)(x4)=34 and Yx4∨*=Yx4∨∪{x8}={x2,x6,x8} .
GR¯B∨(X∨)(x5) : Since GRB(x5,x8)<GR¯B(X)(x5) , then GR¯B∨(X∨)(x5)=GR¯B(X)(x5)=34 and Yx5∨*=Yx5∨={x6} .
GR¯B∨(X∨)(x7) : Since GRB(x7,x8)<GR¯B(X)(x7) , then GR¯B∨(X∨)(x7)=GR¯B(X)(x7)=34 and Yx7∨*=Yx7∨={x6} .
GR¯B∨(X∨)(xj)=1 , x_j ∈ {x₂,x₃,x₆,x₈}.

4.2. Incrementally updating approximations when removing an object

Proposition 9

Let S = (U,A,V,F) be an information system, B ⊆ A, x^∧ ∈ U and x^∧ ∉ X, X ⊆ U, U^∧ = U − {x^∧}. The lower and upper approximations of X by removing x^∧ from U can be updated respectively as follows.

Lower approximation: If x_i ∈ U^∧ − X, then GR¯B∧(X)(xi)=GR¯B(X)(xi)=0 . If x_i ∈ X, then we have:
- If GR¯B(X)(xi)=1−GRB(xi,x∧) , then GR¯B∧(X)(xi)=∧y∈U∧−X(1−GRB(xi,y)) and Yxi∧*={y;∨y∈U∧−XGRB(xi,y)} .
- If ∃y∈Yxi∧ , such that GR¯B(X)(xi)=1−GRB(xi,y) , then GR¯B∧(X)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧−{x∧} .
Upper approximation: GR¯B∧(X)(xj)=1 , x_j ∈ X, and GR¯B∧(X)(xj)=GR¯B(X)(xj) , Yxi∨*=Yxi∨ , x_j ∈ U^∧ − X.

Step 1: Input the relation matrix M_n×m; GR¯B(X)(xi) , Yxi∧ , x_i ∈ X; GR¯B(X)(xj , Yxj∨ , x_j ∈ U − X.
Step 2: We get a new relation matrix Mn×(m−1)* . // Delete GR_B(x^∧,x_i), x_i ∈ X from the relation matrix M_n×m.
Step 3: Calculate the lower approximations x_i ∈ X

If ∃y∈Yxi∧ , such that GR¯B(X)(xi)=1−GRB(xi,y) , then GR¯B∧(X)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧−{x∧} .

Else GR¯B∧(X)(xi)=∧y∈U∧−X(1−GRB(xi,y)) and Yxi∧*={y;∨y∈U∧−XGRB(xi,y)} . // According to the Proposition 9.
Step 4: Calculate the upper approximations x_j ∈ U^∧ − X

GR¯B∧(X)(xj)=GR¯B(X)(xj) , Yxi∨*=Yxi∨ . // According to the Proposition 9.
Step 5: Output the relation matrix Mn×(m−1)* ; GR¯B∧(X)(xi) , Yxi∧* , x_i ∈ X; GR¯B∧(X)(xj) , Yxi∨* , x_j ∈ U^∧ − X; GR¯B∧(X)(xi)=0 , x_i ∈ U^∧ − X and GR¯B∧(X)(xj)=1 , x_j ∈ X.

Algorithm 4.3

(Incremental algorithm for updating approximations when removing an object x^∧ from U − X)

The Algorithm 4.3 has a time complexity of O(|X|), which is mainly decided by Step 2. In the following Example 6, We use the results from Example 5 to demonstrate how algorithm 4.3 update the approximations when removing an object from U − X.

Example 6

We consider the information system given in Table 4. Let U = {x₁,x₂,x₃,x₄,x₅,x₆,x₇,x₈} be the universal set, B = {b₁,b₃,b₄,b₅} be the conditional attribute set, X = {x₂,x₃,x₆,x₈} be the decision set. Removing x₄ ∈ Ψ from U − X.

	b₁	b₃	b₄	b₅	d
x₁	2	1	1	3	U − X
x₂	2	1	2	2	X
x₃	2	2	1	3	X
x₄	1	1	2	2	U − X
x₅	1	2	2	3	U − X
x₆	1	2	2	2	X
x₇	1	2	2	1	U − X
x₈	2	1	2	2	X

Using the result of Example 5.

x1 x4 x5 x7 M4×4=x2x3x6x8(2/43/41/41/43/402/41/403/43/43/42/43/41/41/4)

GR¯B(X)(x2)=14 , Yx2∧={x4} ; GR¯B(X)(x3)=14 , Yx3∧={x1} ; GR¯B(X)(x6)=14 , Yx6∧={x4,x5,x7} ; GR¯B(X)(x8)=14 , Yx8∧={x4} ; GR¯B(X)(xi)=0 , x_i ∈ {x₁,x₄,x₅,x₇}.

GR¯B(X)(x1)=34 , Yx1∨={x3} ; GR¯B(X)(x4)=34 , Yx4∨={x2,x6,x8} ; GR¯B(X)(x5)=34 , Yx5∨={x6} ; GR¯B(X)(x7)=34 , Yx7∨={x6} ; GR¯B(X)(xj)=1 , x_j ∈ {x₂,x₃,x₆,x₈}.

From the Step 2 of Algorithm 4.3 we have a new relation matrix M4×3* :

x1 x5 x7M4×3*=x2x3x6x8(2/41/41/43/42/41/403/43/42/41/41/4)

The lower and upper approximations of X = {x₂,x₃,x₆,x₈} by removing x₄ from U − X be updated as follows:

From the step 3 of algorithm 4.3 we have the lower approximations:

GR¯B∧(X)(x2) : Since GR¯B(X)(x2)=1−GRB(x2,x4) , then GR¯B∧(X)(x2)=∧y∈{x1,x5,x7}(1−GRB(x2,y))=24 and Yx2∧*={y;∨y∈{x1,x5,x7}GRB(x2,y)}={x1} .
GR¯B∧(X)(x3) : Since Yx3∧={x1} , GR¯B(X)(x3)=1−GRB(x3,x1) , then GR¯B∧(X)(x3)=GR¯B(X)(x3)=14 and Yx3∧*=Yx3∧−{x4}={x1} .
GR¯B∧(X)(x6) : Since ∃x5∈Yx6∧ , such that GR¯B(X)(x5)=1−GRB(x6,x5) , then GR¯B∧(X)(x6)=GR¯B(X)(x6)=14 and Yx6∧*=Yx6∧−{x4}={x5,x7} .
GR¯B∧(X)(x8) : Since GR¯B(X)(x8)=1−GRB(x8,x4) , then GR¯B∧(X)(x8)=∧y∈{x1,x5,x7}(1−GRB(x8,y))=24 and Yx8∧*={y;∨y∈{x1,x5,x7}GRB(x8,y)}={x1} .
GR¯B∧(X)(xi)=GR¯B(X)(xi)=0 , x_i ∈ {x₁,x₅,x₇}.

From the step 4 of algorithm 4.3 we have the upper approximations:

GR¯B∧(X)(xj)=GR¯B(X)(xj) , Yxi∨*=Yxi∨ , x_j ∈ {x₁,x₅,x₇}, and GR¯B∧(X)(xj)=1 , x_j ∈ {x₂,x₃,x₆,x₈}.

Proposition 10

Let S = (U,A,V,F) be an information system, B ⊆ A, U^∧ = U − {x^∧}, x^∧ ∈ X, X ⊆ U. The lower and upper approximations of X^∧ = X − {x^∧} by removing x^∧ from X can be respectively updated as follows.

Lower approximation: GR¯B∧(X∧)(xi)=0 , x_i ∈ U^∧ − X^∧, and GR¯B∧(X∧)(xi)=GR¯B(X)(xi) , Yxi∧*=Yxi∧ , x_i ∈ X^∧.
Upper approximation: If x_j ∈ X^∧, then GR¯B∧(X∧)(xj)=GR¯B(X)(xj)=1 . If x_j ∈ U^∧ −X^∧, we have:
- If GR¯B(X)(xj)=GRB(xj,x∧) , then GR¯B∧(X∧)(xj)=∨y∈X∧GRB(xj,y) and Yxj∨*={y;∨y∈X∧GRB(xj,y)} .
- If ∃y∈Yxj∨ , such that GR¯B(X)(xj)=GRB(xj,y)≠GRB(xj,x∧) , then GR¯B∧(X∧)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨−{x∧} .

Step 1: Input the relation matrix M_n×m; GR¯B(X)(xi) , Yxi∧ , x_i ∈ X; GR¯B(X)(xj , Yxj∨ , x_j ∈ U − X.
Step 2: We get a new relation matrix M(n−1)×m* . // Delete GR_B(x^∧,x_j), x_j ∈ U − X from the relation matrix M_n×m.
Step 3: Calculate the lower approximations x_i ∈ X^∧
- GR¯B∧(X∧)(xi)=GR¯B(X)(xi) , Yxi∧*=Yxi∧ . // According to the Proposition 10.
Step 4: Calculate the upper approximations x_j ∈ U^∧ − X^∧

If ∃y∈Yxj∨ , such that GR¯B(X)(xj)=GRB(xj,y)≠GRB(xj,x∧) , then GR¯B∧(X∧)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨−{x∧} .

Else GR¯B∧(X∧)(xj)=∨y∈X∧GRB(xj,y) and Yxj∨*={y;∨y∈X∧GBB(xj,y)} . // According to the Proposition 10.
Step 5: Output the relation matrix M(n−1)×m* ; GR¯B∧(X∧)(xi) , Yxi∧* , x_i ∈ X^∧; GR¯B∧(X∧)(xj) , Yxj∨* , x_j ∈ U^∧ − X^∧; GR¯B∧(X∧)(xi)=0 , x_i ∈ U^∧ − X^∧, and GR¯B∧(X∧)(xj)=GR¯B(X)(xj)=1 , x_j ∈ X^∧.

Algorithm 4.4

(Incremental algorithm for updating approximations when removing an object x^∧ from X)

The Algorithm 4.4 has a time complexity of O(|U − X|), which is mainly decided by Step 2. In the following Example 7, We use the results from Example 6 to demonstrate how algorithm 4.4 update the approximations when removing an object from X.

Example 7

We consider the information system given in Table 5. Let U = {x₁,x₂,x₃,x₅,x₆,x₇,x₈} be the universal set, B = {b₁,b₃,b₄,b₅} be the conditional attribute set, X = {x₂,x₃,x₆,x₈} be the decision set. Removing x₃ ∈ Φ from X, X^∧ = X − {x₃}.

	b₁	b₃	b₄	b₅	d
x₁	2	1	1	3	U − X
x₂	2	1	2	2	X
x₃	2	2	1	3	X
x₅	1	2	2	3	U − X
x₆	1	2	2	2	X
x₇	1	2	2	1	U − X
x₈	2	1	2	2	X

Using the result of Example 6.

x1 x5 x7M4×3=x2x3x6x8(2/41/41/43/42/41/403/43/42/41/41/4)

GR¯B(X)(x2)=24 , Yx2∧={x1} ; GR¯B(X)(x3)=14 , Yx3∧={x1} ; GR¯B(X)(x6)=14 , Yx6∧={x5,x7} ; GR¯B(X)(x8)=24 , Yx8∧={x1} ; GR¯B(X)(xi)=0 , x_i ∈ {x₁,x₅,x₇}.

GR¯B(X)(x1)=34 , Yx1∨={x3} ; GR¯B(X)(x5)=34 , Yx5∨={x6} ; GR¯B(X)(x7)=34 , Yx7∨={x6} ; GR¯B(X)(xj)=1 , x_j ∈ {x₂,x₃,x₆,x₈}.

From the Step 2 of Algorithm 4.4 we have a new relation matrix M3×3* :

x1 x5 x7M3×3*=x2x6x8(2/41/41/403/43/42/41/41/4)

The lower and upper approximations of X^∧ = {x₂,x₆,x₈} by removing x₃ from X be updated as follows:

From the step 3 of algorithm 4.4 we have the lower approximations:

GR¯B∧(X∧)(xi)=GR¯B(X)(xi) , Yxi∧*=Yxi∧ , x_i ∈ {x₂,x₆,x₈}, and GR¯B∧(X∧)(xi)=0 , x_i ∈ {x₁,x₅,x₇}.

From the step 4 of algorithm 4.4 we have the upper approximations:

GR¯B∧(X∧)(x1) : Since GR¯B(X)(x1)=GRB(x1,x3) , then GR¯B∧(X∧)(x1)=∨y∈{x2,x6,x8}GRB(x1,y)=24 and Yx1∨*={y;∨y∈{x2,x6,x8}GRB(x1,y)}={x2,x8} .
GR¯B∧(X∧)(x5) : Since Yx5∨={x6} , GR¯B(X)(x5)=GRB(x5,x6)≠GRB(x5,x3) , then GR¯B∧(X∧)(x5)=GR¯B(X)(x5)=34 and Yx5∨*=Yx5∨−{x3}={x6} .
GR¯B∧(X∧)(x7) : Since Yx7∨={x6} , GR¯B(X)(x7)=GRB(x7,x6)≠GRB(x7,x3) , then GR¯B∧(X∧)(x7)=GR¯B(X)(x7)=34 and Yx7∨*=Yx7∨−{x3}={x6} .
GR¯B∧(X∧)(xj)=GR¯B(X)(xj)=1 , x_j ∈ {x₂,x₆,x₈}.

5. Incrementally updating approximations when changing the attribute value of the object

In practical situation, the attribute values of the object are likely to change, as well. In this section, we discuss the methods of incrementally updating approximations based on the grade indiscernibility relation when changing the decision attribute value and the conditional attribute value of the object, respectively.

5.1. Incrementally updating approximations when changing the decision attribute value of the object

Proposition 11

Let S = (U,A,V,F) be an information system, B ⊆ A, X ⊆ U, x^∨ ∈ U and x^∨ ∉ X. The lower and upper approximations of X^∨ = X ∪ {x^∨} by changing the decision attribute value of x^∨ from U − X to X can be updated respectively as follows.

Lower approximation: If x_i ∈ U − X^∨, we have GR¯B(X∨)(xi)=GR¯B(X)(xi)=0 . If x_i ∈ X^∨, we have:
- If ∃y∈Yxi∧ , such that GR¯B(X)(xi)=1−GRB(xi,y)≠1−GRB(xi,x∨) , then GR¯B(X∨)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧−{x∨} .
- If GR¯B(X)(xi)=1−GRB(xi,x∨) or x_i = x^∨, then GR¯B(X∨)(xi)=∧y∈U−X∨(1−GRB(xi,y)) and Yxi∧*={y;∨y∈U−X∨GRB(xi,y)} .
Upper approximation: If x_j ∈ X^∨, we have GR¯B(X∨)(xj)=1 . If x_j ∈ U − X^∨, we have:
- If GRB(xj,x∨)>GR¯B(X)(xj) , then GR¯B(X∨)(xj)=GRB(xj,x∨) and Yxj∨*={x∨} .
- If GRB(xj,x∨)=GR¯B(X)(xj) , then GR¯B(X∨)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨∪{x∨} .
- If GRB(xj,x∨)<GR¯B(X)(xj) , then GR¯B(X∨)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨ .

Step 1: Input the relation matrix M_n×m; GR¯B(X)(xi) , Yxi∧ , x_i ∈ X; GR¯B(X)(xj , Yxj∨ , x_j ∈ U − X.
Step 2: We get a new relation matrix M(n+1)×(m−1)* . // Delete GR_B(x^∨, x_i), x_i ∈ X from the relation matrix M_n×m and calculate GR_B(x^∨,x_j), x_j ∈ U − X^∧.
Step 3: Calculate the lower approximations x_i ∈ X^∨

If ∃y∈Yxi∧ , such that GR¯B(X)(xi)=1−GRB(xi,y)≠1−GRB(xi,x∨) , then GR¯B(X∨)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧−{x∨} .

Else GR¯B(X∨)(xi)=∧y∈U−X∨(1−GRB(xi,y)) and Yxi∧*={y;∨y∈U−X∨GRB(xi,y)} . // According to the Proposition 11.
Step 4: Calculate the upper approximations x_j ∈ U − X^∨
- If GRB(xj,x∨)>GR¯B(X)(xj) , then GR¯B(X∨)(xj)=GRB(xj,x∨) and Yxj∨*={x∨} .
- If GRB(xj,x∨)=GR¯B(X)(xj) , then GR¯B(X∨)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨∪{x∨} .
- If GRB(xj,x∨)<GR¯B(X)(xj) , then GR¯B(X∨)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨ . // According to the Proposition 11.
Step 5: Output the relation matrix M(n+1)×(m−1)* ; GR¯B(X∨)(xi) , Yxi∧* , x_i ∈ X^∨; GR¯B(X∨)(xj) , Yxj∨* , x_j ∈ U − X^∨; GR¯B(X∨)(xi)=0 , x_i ∈ U − X^∨, and GR¯B(X∨)(xj)=1 , x_j ∈ X^∨.

Algorithm 5.1

(Incremental algorithm for updating approximations when changing the decision attribute value of x^∨, x^∨ ∈ U − X to x^∨ ∈ X)

The Algorithm 5.1 has a time complexity of O(|U − X| |B|), which is mainly decided by Step 2. In the following Example 8, We use the results from Example 7 to demonstrate how algorithm 5.1 update the approximations when changing the decision value of the object from U − X to X.

Example 8

We consider the information system given in Table 6. Let U = {x₁,x₂,x₅,x₆,x₇,x₈} be the universal set, B = {b₁,b₃,b₄,b₅} be the conditional attribute set, X = {x₂,x₆,x₈} be the decision set. Changing the decision attribute value of x₅ to X from U − X, X^∨ = X ∪ {x₅}.

	b₁	b₃	b₄	b₅	d
x₁	2	1	1	3	U − X
x₂	2	1	2	2	X
x₅	1	2	2	3	U − X
x₆	1	2	2	2	X
x₇	1	2	2	1	U − X
x₈	2	1	2	2	X

Using the result of Example 7.

x1 x5 x7M3×3=x2x6x8(2/41/41/403/43/42/41/41/4)

GR¯B(X)(x2)=24 , Yx2∧={x1} ; GR¯B(X)(x6)=14 , Yx6∧={x5,x7} ; GR¯B(X)(x8)=24 , Yx8∧={x1} ; GR¯B(X)(xi)=0 , x_i ∈ {x₁,x₅,x₇}.

GR¯B(X)(x1)=24 , Yx1∨={x2,x8} ; GR¯B(X)(x5)=34 , Yx5∨={x6} ; GR¯B(X)(x7)=34 , Yx7∨={x6} ; GR¯B(X)(xj)=1 , x_j ∈ {x₂,x₆,x₈}.

From the Step 2 of Algorithm 5.1 we have a new relation matrix M4×2* :

x1x7M4×2*=x2x6x8x5(2/41/403/42/41/41/43/4)

The lower and upper approximations of X^∨ = {x₂,x₅,x₆,x₈} by changing the decision attribute value x₅ ∈ U − X to x₅ ∈ X are updated as follows:

From the step 3 of algorithm 5.1 we have the lower approximations:

GR¯B(X∨)(x2) : Since Yx2∧={x1} , GR¯B(X)(x2)=1−GRB(x2,x1) , then GR¯B(X∨)(x2)=GR¯B(X)(x2)=24 and Yx2∧*=Yx2∧−{x5}={x1} .
GR¯B(X∨)(x6) : Since ∃x7∈Yx6∧ , such that GR¯B(X)(x6)=1−GRB(x6,x7) , then GR¯B(X∨)(x6)=GR¯B(X)(x6)=14 and Yx6∧*=Yx6∧−{x5}={x7} .
GR¯B(X∨)(x8) : Since Yx8∧={x1} , GR¯B(X)(x8)=1−GRB(x8,x1) , then GR¯B(X∨)(x8)=GR¯B(X)(x8)=24 and Yx8∧*=Yx8∧−{x5}={x1} .
GR¯B(X∨)(x5) : GR¯B(X∨)(x5)=∧y∈{x1,x7}(1−GRB(x5,y))=14 and Yx8∧*={y;∨y∈{x1,x7}GRB(x5,y)}={x7} .
GR¯B(X∨)(xi)=GR¯B(X)(xi)=0 , x ∈ {x₁,x₇}.

From the step 4 of algorithm 5.1 we have the upper approximations:

GR¯B(X∨)(x1) : Since GRB(x1,x5)<GR¯B(X)(x1) , then GR¯B(X∨)(x1)=GR¯B(X)(x1)=24 and Yx1∨*=Yx1∨={x2,x8} .
GR¯B(X∨)(x7) : Since GRB(x7,x5)=GR¯B(X)(x7) , then GR¯B(X∨)(x7)=GR¯B(X)(x7)=34 and Yx7∨*=Yx7∨∪{x5}={x5,x6} .
GR¯B(X∨)(xj)=GR¯B(X)(xj)=1 , x_j ∈ {x₂,x₅,x₆,x₈}.

Proposition 12

Let S = (U,A,V,F) be an information system, B ⊆ A, X ⊆ U, x^∧ ∈ X. The lower and upper approximations of X^∧ = X − {x^∧} by changing the decision attribute value of x^∧ from X to U − X can be updated respectively as follows.

Lower approximation: If x_i ∈ U − X^∧, we have GR¯B(X∧)(xi)=0 ; If x_i ∈ X^∧, we have:
- If 1−GRB(xi,x∧)>GR¯B(X)(xi) , then GR¯B(X∧)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧ .
- If 1−GRB(xi,x∧)=GR¯B(X)(xi) , then GR¯B(X∧)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧∪{x∧} .
- If 1−GRB(xi,x∧)<GR¯B(X)(xi) , then GR¯B(X∧)(xi)=1−GRB(xi,x∧) and Yxi∧*={x∧} .
Upper approximation: If x_j ∈ X^∧, we have GR¯B(X∧)(xj)=GR¯B(X)(xj)=1 ; If x_j ∈ U − X^∧, we have:
- If ∃y∈Yxj∨ , such that GR¯B(X)(xj)=GRB(xj,y) , then GR¯B(X∧)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨−{x∧} .
- If GR¯B(X)(xj)=GRB(xj,x∧) , or x_j = x^∧, then GR¯B(X)(xj)=∨y∈X∧GRB(xj,y) and Yxj∨*={y;∨y∈X∧GRB(xj,y)} .

Step 1: Input the relation matrix M_n×m; GR¯B(X)(xi) , Yxi∧ , x_i ∈ X; GR¯B(X)(xj , Yxj∨ , x_j ∈ U − X.
Step 2: We get a new relation matrix M(n+1)×(m−1)* . // Delete GR_B(x^∧,x_j), x_j ∈ U − X from the relation matrix M_n×m and calculate GR_B(x^∨, x_i), x_i ∈ X^∨.
Step 3: Calculate the lower approximations x_i ∈ X^∧
- If 1−GRB(xi,x∧)>GR¯B(X)(xi) , then GR¯B(X∧)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧ ;
- If 1−GRB(xi,x∧)=GR¯B(X)(xi) , then GR¯B(X∧)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧∪{x∧} ;
- If 1−GRB(xi,x∧)<GR¯B(X)(xi) , then GR¯B(X∧)(xi)=1−GRB(xi,x∧) and Yxi∧*={x∧} . // According to the Proposition 12.
Step 4: Calculate the upper approximations x_j ∈ U − X^∧

If ∃y∈Yxj∨ , such that GR¯B(X)(xj)=GRB(xj,y) , then GR¯B(X∧)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨−{x∧} ;

Else GR¯B(X)(xj)=∨y∈X∧GRB(xj,y) and Yxj∨*={y;∨y∈X∧GRB(xj,y)} . // According to the Proposition 12.
Step 5: Output the relation matrix M(n+1)×(m−1)* ; GR¯B(X∧)(xi) , Yxi∧* , x_i ∈ X^∧; GR¯B(X∧)(xj) and Yxj∨* , x_j ∈ U − X^∧; GR¯B(X∧)(xi)=0 , x_i ∈ U − X^∧, and GR¯B(X∧)(xj)=1 , x_j ∈ X^∧.

Algorithm 5.2

(Incremental algorithm for updating approximations when changing the decision attribute value of x^∧, x^∧ ∈ X to x^∧ ∈ U − X)

The Algorithm 5.2 has a time complexity of O(|X| |B|), which is mainly decided by Step 2. In the following Example 9, We use the results from Example 8 to demonstrate how algorithm 5.2 update the approximations when changing the decision attribute value of the object from X to U − X.

Example 9

We consider the information system given in Table 7. Let U = {x₁,x₂,x₅,x₆,x₇,x₈} be the universal set, B = {b₁,b₃,b₄,b₅} be the conditional attribute set, X = {x₂,x₅,x₆,x₈} be the decision set. Changing the decision attribute value of x₈ from X to U − X, X^∧ = {x₂,x₅,x₆}.

	b₁	b₃	b₄	b₅	d
x₁	2	1	1	3	U − X
x₂	2	1	2	2	X
x₅	1	2	2	3	X
x₆	1	2	2	2	X
x₇	1	2	2	1	U − X
x₈	2	1	2	2	X

Using the result of Example 8.

x1x7M4×2=x2x6x8x5(2/41/403/42/41/41/43/4)

GR¯B(X)(x2)=24 , Yx2∧={x1} ; GR¯B(X)(x6)=14 , Yx6∧={x7} ; GR¯B(X)(x8)=24 , Yx8∧={x1} ; GR¯B(X)(x5)=14 , Yx5∧={x7} ; GR¯B(X)(xi)=0 , x_i ∈ {x₁,x₇}.

GR¯B(X)(x1)=24 , Yx1∨={x2,x8} ; GR¯B(X)(x7)=34 , Yx7∨={x5,x6} ; GR¯B(X)(xj)=1 , x_j ∈ {x₂,x₅,x₆,x₈}.

From the Step 2 of Algorithm 5.2 we have a new relation matrix M3×3* :

x1 x7 x8M3×3*=x2x6x5(2/41/44/403/42/41/43/41/4)

The lower and upper approximations of X^∧ = {x₂,x₅,x₆} by changing the decision attribute value x₈ ∈ X to x₈ ∈ U − X, are updated as follows:

From the step 3 of algorithm 5.2 we have the lower approximations:

GR¯B(X∧)(x2) : Since 1−GRB(x2,x8)<GR¯B(X)(x2) , then GR¯B(X∧)(x2)=1−GRB(x2,x8)=0 and Yx2∧*={x8} .
GR¯B(X∧)(x6) : Since 1−GRB(x6,x8)>GR¯B(X)(x6) , then GR¯B(X∧)(x6)=GR¯B(X)(x6)=14 and Yx6∧*=Yx6∧={x7} .
GR¯B(X∧)(x5) : Since 1−GRB(x5,x8)>GR¯B(X)(x5) , then GR¯B(X∧)(x5)=GR¯B(X)(x5)=14 and Yx5∧*=Yx5∧={x7} .
GR¯B(X∧)(xi)=GR¯B(X)(xi)=0 , x ∈ {x₁,x₇,x₈}.

From the step 4 of algorithm 5.2 we have the upper approximations:

GR¯B(X∧)(x1) : Since ∃x2∈Yx1∨ , such that GR¯B(X)(x1)=GRB(x1,x2) , then GR¯B(X∧)(x1)=GR¯B(X)(x1)=24 and Yx1∨*=Yx1∨−{x8}={x2} .
GR¯B(X∧)(x7) : Since ∃x6∈Yx7∨ , such that GR¯B(X)(x7)=GRB(x7,x6) , then GR¯B(X∧)(x7)=GR¯B(X)(x7)=34 and Yx7∨*=Yx7∨−{x8}={x5,x6} .
GR¯B(X∧)(x8) : GR¯B(X)(x8)=∨y∈{x2,x5,x6}GRB(x8,y)=44 and Yx8∨*={y;∨y∈{x2,x5,x6}GRB(x8,y)}={x2} .
GR¯B(X∧)(xj)=GR¯B(X)(xj)=1 , x_j ∈ {x₂,x₅,x₆}.

5.2. Incremental updating approximations when changing the conditional attribute value of the object

Proposition 13

Let S = (U,A,V,F) be an information system, B ⊆ A, b ∈ B, changing the conditional attribute value f(x^*,b) to f^*(x^*,b), f^*(x^*,b) ≠ f(x^*,b), x^* ∈ U. For any y ∈ U,

GRB*(x*,y)={|B|·GRB(x*,y)+1|B|,f*(x*,b)=f(y,b);|B|·GRB(x*,y)−1|B|,f*(x*,b)≠f(y,b).

Proposition 14

Let S = (U,A,V,F) be an information system, B ⊆ A, X ⊆ U, x^* ∈ X. The lower and upper approximations of X by changing the conditional attribute value of x^*, f(x^*,b) to f^*(x^*,b) (f(x^*,b) ≠ f^*(x^*,b)) can be updated respectively as follows.

Lower approximation: If x_i ∈ U − X, then GR¯B*(X)(xi)=0 . If x_i ∈ X, we have
- If x_i ∈ X − {x^*}, then GR¯B*(X)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧ .
- If x_i = x^*, then GR¯B*(X)(x*)=∧y∈U−X(1−GRB*(x*,y)) and Yxi∧*={y;∨y∈U−XGRB*(x*,y)} .
Upper approximation: If x_j ∈ X, then GR¯B*(X)(xj)=1 . If x_j ∈ U − X, we have:
- If GR¯B(X)(xj)=GRB(xj,x*) , then GR¯B*(X)(xj)=∨y∈XGRB*(xj,y) and Yxj∨*={y;∨y∈XGRB*(xj,y)} .
- If ∃y∈Yxj∨ , such that GR¯B(X)(xj)=GRB(xj,y) , we have:
- If GR¯B(X)(xj)>GRB*(xj,x*) , then GR¯B*(X)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨−{x*} .
- If GR¯B(X)(xj)=GRB*(xj,x*) , then GR¯B*(X)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨∪{x*} .
- If GR¯B(X)(xj)<GRB*(xj,x*) , then GR¯B*(X)(xj)=GRB*(xj,x*) and Yxj∨*={x*} .

Step 1: Input the relation matrix M_n×m; GR¯B(X)(xi) , Yxi∧ , x_i ∈ X; GR¯B(X)(xj) , Yxj∨ , x_j ∈ U − X; The changing attribute value of x^*: f(x^*,b).
Step 2: We get a new relation matrix Mn×m* . Changing the value GR_B(x^*,y) to GRB*(x*,y) of the relation matrix M_n×m,
GRB*(x*,y)={|B|·GRB(x*,y)+1|B|,f*(x*,b)=f(y,b);|B|·GRB(x*,y)−1|B|,f*(x*,b)≠f(y,b).
y ∈ U − X // According to Proposition 13.
Step 3: Calculate the lower approximations x_i ∈ X
- If x_i ∈ X − {x^*}, then GR¯B*(X)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧ .
- If x_i = x^*, then GR¯B*(X)(x*)=∧y∈U−X(1−GRB*(x*,y)) and Yx*∧*={y;∨y∈U−XGRB*(x*,y)} . // According to Proposition 14.
Step 4: Calculate the upper approximations x_j ∈ U − X
- If ∃y∈Yxj∨ , such that GR¯B(X)(xj)=GRB(xj,y) , we have:
- If GR¯B(X)(xj)>GRB*(xj,x*) , then GR¯B*(X)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨−{x*} .
- If GR¯B(X)(xj)=GRB*(xj,x*) , then GR¯B*(X)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨∪{x*} .
- If GR¯B(X)(xj)<GRB*(xj,x*) , then GR¯B*(X)(xj)=GRB*(xj,x*) and Yxj∨*={x*} .
Else GR¯B*(X)(xj)=∨y∈XGRB*(xj,y) and Yxj∨*={y;∨y∈XGRB*(xj,y)} . // According to Proposition 14.
Step 5: Output the relation matrix Mn×m* ; GR¯B*(X)(xi) , Yxi∧* , x_i ∈ X; GR¯B*(X)(xj) , Yxj∨* , x_j ∈ U −X; GR¯B*(X)(xi)=0 , x_i ∈ U − X, and GR¯B*(X)(xj)=1 , x_j ∈ X.

Algorithm 5.3

(Incremental algorithm for updating approximations when changing the conditional attribute value f(x^*,b) to f^*(x^*,b), x^* ∈ X)

The Algorithm 5.3 has a time complexity of O(|U − X| |B|), which is mainly decided by Step 2. In the following Example 10, We use the results from Example 9 to demonstrate how algorithm 5.3 update the approximations when changing the attribute value f(x^*,b) to f^*(x^*,b), x^* ∈ X.

Example 10

We consider the information system given in Table 8. Let U = {x₁,x₂,x₅,x₆,x₇,x₈} be the universal set, B = {b₁,b₃,b₄,b₅} be the conditional attribute set, X = {x₂,x₅,x₆} be the decision set. Changing f(x₅,b₃) = 2 to f^*(x₅,b₃) = 1.

	b₁	b₃	b₄	b₅	d
x₁	2	1	1	3	U − X
x₂	2	1	2	2	X
x₅	1	2	2	3	X
x₆	1	2	2	2	X
x₇	1	2	2	1	U − X
x₈	2	1	2	2	U − X

Using the result of Example 9.

x1 x7 x8 M3×3=x2x6x5(2/41/44/403/42/41/43/41/4)

GR¯B(X)(x2)=0 , Yx2∧={x8} ; GR¯B(X)(x6)=14 , Yx6∧={x7} ; GR¯B(X)(x5)=14 , Yx5∧={x7} ; GR¯B(X)(xi)=0 , x_i ∈ {x₁,x₇,x₈}.

GR¯B(X)(x1)=24 , Yx1∨={x2} ; GR¯B(X)(x7)=34 , Yx7∨={x5,x6} ; GR¯B(X)(x8)=44 , Yx8∨={x2} ; GR¯B(X)(xj)=1 , x_j ∈ {x₂,x₅,x₆}.

From the Step 2 of Algorithm 5.3 we have a new relation matrix M3×3* :

x1 x7 x8 M3×3*=x2x6x5(2/41/44/403/42/42/42/42/4)

The lower and upper approximations of X = {x₂,x₅,x₆} by changing f(x₅,b₃) to f^*(x₅,b₃) are updated as follows.

From the step 3 of algorithm 5.3 we have the lower approximations:

GR¯B*(X)(xi)=GR¯B(X)(xi) , Yxi∧*=Yxi∧ , x_i ∈ {x₂,x₆}.
GR¯B*(X)(x5)=∧y∈{x1,x7,x8}(1−GRB*(x5,y))=24 and Yx5∧*={y;∨y∈{x1,x7,x8}GRB*(x5,y)}={x1,x7,x8} .

From the step 4 of algorithm 5.3 we have the upper approximations:

GR¯B*(X)(x1) : Since ∃x2∈Yx1∨ , GR¯B(X)(x1)=GRB(x1,x2) , and GR¯B(X)(x1)=GRB*(x1,x5) , then GR¯B*(X)(x1)=GR¯B(X)(x1)=24 and Yx1∨*=Yx1∨∪{x5}={x2,x5} .
GR¯B*(X)(x7) : Since ∃x6∈Yx7∨ , GR¯B(X)(x7)=GRB(x7,x6) , and GR¯B(X)(x7)>GRB*(x7,x5) , then GR¯B*(X)(x7)=GR¯B(X)(x7)=34 , and Yx7∨*=Yx7∨−{x5}={x6} .
GR¯B*(X)(x8) : Since ∃x2∈Yx8∨ , GR¯B(X)(x8)=GRB(x8,x2) , and GR¯B(X)(x8)>GRB*(x8,x5) , then GR¯B*(X)(x8)=GR¯B(X)(x8)=44 , and Yx8∨*=Yx8∨−{x5}={x2} .

Proposition 15

Let S = (U,A,V,F) be an information system, B ⊆ A, X ⊆ U, x^* ∈ U − X. The lower and upper approximations of X by changing the conditional attribute value of x^*, f(x^*,b) to f^*(x^*,b) (f(x^*,b) ≠ f^*(x^*,b)) can be updated respectively as follows.

Lower approximation: If x_i ∈ U − X, then GR¯B*(X)(xi)=0 . If x_i ∈ X, we have
- If GR¯B(X)(xi)=GRB(xi,x*) , then GR¯B*(X)(xi)=∧y∈U−X(1−GRB*(xi,y)) and Yxi∧*={y;∨y∈U−XGRB*(xi,y)} .
- If ∃y∈Yxi∧ , such that GR¯B(X)(xi)=GRB(xi,y) , we have:
- If GR¯B(X)(xi)>GRB*(xi,x*) , then GR¯B*(X)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧−{x*} ;
- If GR¯B(X)(xi)=GRB*(xi,x*) , then GR¯B*(X)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧∪{x*} ;
- If GR¯B(X)(xj)<GRB*(xj,x*) , then GR¯B*(X)(xj)=GRB*(xj,x*) and Yxj∧*={x*} .
Upper approximation: If x_j ∈ X, then GR¯B*(X)(xj)=1 . If x_j ∈ U − X, we have:
- If x_j ∈ U − X − {x^*}, then GR¯B*(X)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨ .
- If x_j = x^*, then GR¯B*(X)(x*)=∨y∈XGRB*(x*,y) and Yx*∧*={y;∨y∈XGRB*(x*,y)} .

Step 1: Input the relation matrix M_n×m; GR¯B(X)(xi) , Yxi∧ , x_i ∈ X; GR¯B(X)(xj , Yxj∨ , x_j ∈ U − X; The changing attribute value of x^*: f(x^*,b).
Step 2: We get a new relation matrix Mn×m* . Changing the value GR_B(x^*,y) to GRB*(x*,y) of the relation matrix M_n×m,
GRB*(x*,y)={|B|·GRB(x*,y)+1|B|,f*(x*,b)=f(y,b);|B|·GRB(x*,y)−1|B|,f*(x*,b)≠f(y,b).
y ∈ X // According to Proposition 13.
Step 3: Calculate the lower approximations x_i ∈ X
- If ∃y∈Yxi∧ , such that GR¯B(X)(xi)=GRB(xi,y) , we have:
- If GR¯B(X)(xi)>GRB*(xi,x*) , then GR¯B*(X)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧−{x*} ;
- If GR¯B(X)(xi)=GRB*(xi,x*) , then GR¯B*(X)(xi)=GR¯B(X)(xi) and Yxi∧*=Yxi∧∪{x*} ;
- If GR¯B(X)(xj)<GRB*(xj,x*) , then GR¯B*(X)(xj)=GRB*(xj,x*) and Yxj∧*={x*} .
Else GR¯B*(X)(xi)=∧y∈U−X(1−GRB*(xi,y)) and Yxi∧*={y;∨y∈U−XGRB*(xi,y)} . // According to Proposition 15.
Step 4: Calculate the upper approximations x_j ∈ U − X
- If x_j ∈ U − X − {x^*}, then GR¯B*(X)(xj)=GR¯B(X)(xj) and Yxj∨*=Yxj∨ .
- If x_j = x^*, then GR¯B*(X)(x*)=∨y∈XGRB*(x*,y) and Yx*∧*={y;∨y∈XGRB*(x*,y)} . // According to Proposition 15.
Step 5: Output the relation matrix Mn×m* ; GR¯B*(X)(xi) , Yxi∧* , x_i ∈ X; GR¯B*(X)(xj) , Yxj∨* , x_j ∈ U − X; GR¯B*(X)(xi)=0 , x_i ∈ U − X, and GR¯B*(X)(xj)=1 , x_j ∈ X.

Algorithm 5.4

(Incremental algorithm for updating approximations when changing the conditional attribute value f(x^*,b) to f^*(x^*,b), x^* ∈ U − X)

The time complexity of the Algorithm 5.4 is O(|X| |B|), which is mainly decided by the time cost of building the information system matrix in Step 2. In the following Example 11, We use the results from Example 10 to demonstrate how algorithm 5.4 update the approximations when changing the conditional attribute value f(x^*,b) to f^*(x^*,b), x^* ∈ U − X.

Example 11

We consider the information system given in Table 9. Let U = {x₁,x₂,x₅,x₆,x₇,x₈} be the universal set, B = {b₁,b₃,b₄,b₅} be the conditional attribute set, X = {x₂,x₅,x₆} be the decision set. Changing f(x₈,b₄) = 2 to f^*(x₈,b₄) = 1.

	b₁	b₃	b₄	b₅	d
x₁	2	1	1	3	U − X
x₂	2	1	2	2	X
x₅	1	1	2	3	X
x₆	1	2	2	2	X
x₇	1	2	2	1	U − X
x₈	2	1	2	2	U − X

	b₁	b₃	b₄	b₅	d
x₁	2	1	1	3	U − X
x₂	2	1	2	2	X
x₅	1	1	2	3	X
x₆	1	2	2	2	U − X
x₇	1	2	2	1	U − X
x₈	2	1	1	2	U − X

Using the result of Example 10.

x1 x7 x8M3×3=x2x6x5(2/41/44/403/42/42/42/42/4)

GR¯B(X)(x2)=0 , Yx2∧={x8} ; GR¯B(X)(x6)=14 , Yx6∧={x7} ; GR¯B(X)(x5)=24 , Yx5∧={x1,x7,x8} ; GR¯B(X)(xi)=0 , x_i ∈ {x₁,x₇,x₈}.

GR¯B(X)(x1)=24 , Yx1∨={x2,x5} ; GR¯B(X)(x7)=34 , Yx7∨={x6} ; GR¯B(X)(x8)=44 , Yx8∨={x2} ; GR¯B(X)(xj)=1 , x_j ∈ {x₂,x₅,x₆}.

From the Step 2 of Algorithm 5.4 we have a new relation matrix M3×3* :

x1 x7 x8M3×3*=x2x6x5(2/41/43/403/41/42/42/41/4)

The lower and upper approximations of X = {x₂,x₅,x₆} by changing f(x₈,b₄) to f^*(x₈,b₄) are updated as follows.

From the step 3 of algorithm 5.4 we have the lower approximations:

GR¯B*(X)(x2) : Since GR¯B(X)(x2)=GRB(x2,x8) , then GR¯B*(X)(x2)=∧y∈{x1,x7,x8}(1−GRB*(x2,y))=34 and Yx2∧*={y;∨y∈{x1,x7,x8}GRB*(x2,y)}={x8} ;
GR¯B*(X)(x6) : Since ∃x7∈Yx6∧ , such that GR¯B(X)(x6)=GRB(x6,x7) , and GR¯B(X)(x6)>GRB*(x6,x8) then GR¯B*(X)(x6)=GR¯B*(X)(x6)=14 and Yx6∧*=Yx6∧−{x8}={x7} ;
GR¯B*(X)(x5) : Since ∃x7∈Yx5∧ , such that GR¯B(X)(x5)=GRB(x5,x7) , and GR¯B(X)(x5)>GRB*(x5,x8) then GR¯B*(X)(x5)=GR¯B(X)(x5)=24 and Yx5∧*=Yx5∧−{x8}={x1,x7} .

From the step 4 of algorithm 5.4 we have the upper approximations:

GR¯B*(X)(xj)=GR¯B(X)(xj) , Yxj∨*=Yxj∨ , x_j ∈ {x₁,x₇}.
GR¯B*(X)(x8)=∨y∈{x2,x5,x6}GRB*(x8,y)=24 and Yx8∧*={y;∨y∈{x2,x5,x6}GRB*(x8,y)}={x1,x7} .

6. Algorithm analysis

The time complexities of all the incrementally updating algorithms proposed in this paper are list in the Table 11 as follow.

Operation	Non-incremental algorithm	Time Complexity	Incremental algorithm	Time Complexity
Adding an attribute b	Algorithm 2.1	O(\|X\| \|U − X\| \|B\|)	Algorithm 3.1	O (\|X\| \|U − X\|)
Removing an attribute b			Algorithm 3.2	O(\|X\| \|U − X)
Adding an object x ∈ U − X			Algorithm 4.1	O(\|X\| \|B\|)
Adding an object x ∈ X			Algorithm 4.2	O(\|U − X\| \|B\|)
Removing an object x ∈ U − X			Algorithm 4.3	O(\|X\|)
Removing an object x ∈ X			Algorithm 4.4	O(\|U − X\|)
x ∈ U − X → x ∈ X			Algorithm 5.1	O(\|U − X\| \|B\|)
x ∈ X → x ∈ U − X			Algorithm 5.2	O(\|X\| \|B\|)
f(x,b) → f^*(x,b), x ∈ X			Algorithm 5.3	O(\|U − X\| \|B\|)
f(x,b) → f^*(x,b), x ∈ U − X			Algorithm 5.4	O(\|X\| \|B\|)

From the Table 11 we can see that the proposed incrementally updating algorithms has lower time complexity for every operation on data. In addition to the time cost, it is obviously that every incrementally updating algorithm will use less memory space to get the information updated, because there is no need to rebuild the whole relation matrix in an incrementally updating algorithm.

The incrementally updating algorithms could be seen as a group of functions to update the existing results to keep the relation matrix, approximation and the set of Yxj∨ and Yxi∧ changing in right way when the information system changed. And we can use different types of the incrementally updating algorithms in any order and with any number of times to adapt to any possible changing in the information system. For example, we can use Algorithm 3.2 once and then use Algorithm 4.1 or 4.2 twice when the basic data need a changing of adding two objects and removing an attribute. And we should note that putting the removing type Algorithm before others will also make the time cost reduced a bit more.

7. Experimental evaluation

In this section, we compare the computational time of the non-incremental algorithm and the proposed incremental algorithms on different data sets shown in Table 12. The three data sets used herein came from the University of California, Irvine (UCI) Machine Learning Repository (www.ics.uci.edu/). In data set Dermatology, we delete some attributes with missing values. Experiments were performed on a 2.40GHz Pentium Server with 8GB of memory, running Windows 10. Algorithms were code in Matlab r2012a.

ID	Data set	Number of objects	Number of attributes	Decision classes	Missing value
1	Zoo	101	17	7	No
2	Dermatology	366	33	7	Yes
3	Chess	3196	36		No

From the following experimental results, it is clear that the incremental algorithm outperform the traditional non-incremental algorithm in different cases, Table 13 (Where NIA is the non-incrementally updating algorithm and IA is the incrementally updating algorithm) shows that the proposed methods can effectively update approximations when the information system changes.

Operation	Zoo		Dermatology		Chess
Operation	NIA	IA	NIA	IA	NIA	IA
Adding an attribute b	0.0115	0.0083	0.1735	0.0064	15.8108	0.2609
Removing an attribute b	0.0115	0.0077	0.1774	0.0065	15.8190	0.2316
Adding an object x ∈ U − X	0.0123	0.0030	0.1582	0.0052	15.9404	0.1340
Adding an object x ∈ X	0.0120	0.0081	0.1485	0.0074	16.2771	0.1263
Removing an object x ∈ U − X	0.0101	0.0044	0.1708	0.0049	15.9115	0.1308
Removing an object x ∈ X	0.0114	0.0067	0.1697	0.0057	16.0953	0.1302
x ∈ U − X → x ∈ X	0.0117	0.0055	0.1726	0.0054	15.9011	0.1641
x ∈ X → x ∈ U − X	0.0112	0.0099	0.1744	0.0067	15.7100	0.1548
f(x,b) → f^*(x,b), x ∈ X	0.0120	0.0079	0.1795	0.0067	15.9708	0.1184
f(x,b) → f^*(x,b), x ∈ U − X	0.0115	0.0030	0.1623	0.0060	15.8709	0.1442

Table 13.

Comparisons of computational time between non-incremental algorithm and incremental simplified algorithm when objects and attributes increase simultaneously(s).

8. Conclusion

This paper discusses the approaches of incrementally updating of the rough approximations based on the grade indiscernibility relation when complete information system is varied. Taking full use of the existing information make the time cost of the approaches reduced a lot especially when dealing with the large-scale data. In the future, we will discuss the methods of dynamic updating of the rough approximations based on the grade indiscernibility relation in incomplete information system. Moreover, the incremental updating approaches of the decision rules with respect to grade indiscernibility relation is another important and interesting issue to be addressed.

Acknowledgements

This work was partially supported by the National Natural Science Foundation of China (Grant No. 61473239, 61175044, 61372187), the Fundamental Research Funds for the Central Universities of China (Grant No. 2682014ZT28), and the open research fund of key laboratory of intelligent network information processing, Xihua University (szjj2014-052).

References

1.Z Pawlak, Rough sets, International Journal of Computer and Information Sciences, Vol. 11, 1982, pp. 341-356.

2.Z Pawlak, Rough sets-theoretical aspects of reasoning about data, Kluwer Academic Publishers, 1991.

3.Z Pawlak, Rough set theory and its applications to data analysis, Cybernetics and Systems, Vol. 29, 1998, pp. 661-688.

4.A Skowron, Extracting laws from decision tables: a rough set approach, Computational Intelligence, Vol. 11, 1995, pp. 371-388.

5.YY Yao and PJ Lingras, Interpretations of belief functions in the theory of rough sets, Information Sciences, Vol. 104, 1998, pp. 81-106.

6.WX Zhang, JS Mi, and WZ Wu, Approaches to knowledge reductions in inconsistent systems, International journal of intelligent systems, Vol. 18, 2003, pp. 989-1000.

7.Z Bonikowski, E Bryniarski, and U Wybraniec, Extensions and intentions in the rough set theory, Information Sciences, Vol. 107, 1998, pp. 149-167.

8.D Dubois and H Prade, Rough fuzzy set and fuzzy rough sets, International Journal of General System, Vol. 17, 1990, pp. 191-209.

9.W Ziarko, Variable precision rough set model, Journal of Computer and System Sciences, Vol. 46, 1993, pp. 39-59.

10.YY Yao, Relational interpretations of neighborhood operators and rough set approximation operators, Information Sciences, Vol. 111, 1998, pp. 239-259.

11.YY Yao, Probabilistic rough set approximations, International Journal of Approximate Reasoning, Vol. 49, 2008, pp. 255-271.

12.RS Michalski, Knowledge repair mechanisms: evolution vs. revolution, in Proceedings of the Third International Machine Learning Workshop (1985), pp. 116-119.

13.A Bouchachia and R Mittermeir, Towards incremental fuzzy classifiers, Soft Computing, Vol. 11, 2007, pp. 193-207.

14.Y Cheng, The incremental method for fast computing the rough fuzzy approximations, Data and Knowledge Engineering, Vol. 70, 2011, pp. 84-100.

15.CC Chan, A rough set approach to attribute generalization in data mining, Information Sciences, Vol. 107, 1998, pp. 169-176.

16.TR Li, D Ruan, W Geert, J Song, and Y Xu, A rough set based characteristic relation approach for dynamic attribute generalization in data mining, Knowledge-Based Systems, Vol. 20, 2007, pp. 485-494.

17.JB Zhang, TR Li, D Ruan, and D Liu, Neighborhood rough sets for dynamic data mining, International Journal of Intelligent Systems, Vol. 27, 2012, pp. 317-342.

18.Y Zhao and YY Yao, Data analysis based on discernibility and indiscernibility, Information Sciences, Vol. 177, 2007, pp. 4959-4976.

19.KY Qin and JF Luo, Rough set model based on grade indiscernibility relation, Computer Science, Vol. 42, 2015, pp. 240-243.

20.JF Luo and KY Qin, The rough set model based on grade indiscernibility relation, in 2015 IEEE International Conferences on Computer and Information Technology (2015), pp. 1366-1371.

21.KY Qin, JF Luo, and Z Pei, Rough Approximations Based on Valued Tolerance Relations, Fundamenta Informaticae, Vol. 142, 2015, pp. 183-194.

22.M Lichman, UCI Machine Learning Repository, University of California, Irvine, School of Information and Computer Sciences, 2013. http://archive.ics.uci.edu/ml

23.N Shan and W Ziarko, Data-based acquisition and incremental modification of classification rules, Computational Intelligence, Vol. 11, 1995, pp. 357-370.

24.YY Yao and TY Lin, Generalization of rough sets using modal logics, Intelligent Automation and Soft Computing, Vol. 2, 1996, pp. 103-119.

25.QS Zhou, TR Li, et al., Research on properties of approximations in rough sets based on characteristic relation when object varies with time, Computer Science, Vol. 39, 2012, pp. 191-197.

26.SY Li, TR Li, and D Liu, Incremental updating approximations in dominance-based rough sets approach under the variation of the attribute set, Knowledge-Based Systems, Vol. 40, 2013, pp. 17-26.

27.HM Chen, TR Li, C Luo, SJ Horng, and GY Wang, A decision-theoretic rough set approach for dynamic data mining, IEEE Transactions on Fuzzy Systems, Vol. 23, 2015, pp. 1958-1970.

28.HM Chen, TR Li, D Ruan, JH Lin, and CX Hu, A rough-set-based incremental approach for updating approximations under dynamic maintenance environments, IEEE Transactions on Knowledge and Data Engineering, Vol. 25, 2013, pp. 274-284.

29.L Feng, TR Li, D Ruan, and S Gou, A vague-rough set approach for uncertain knowledge acquisition, Knowledge-Based Systems, Vol. 24, 2011, pp. 837-843.

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Journal: International Journal of Computational Intelligence Systems
Volume-Issue: 10 - 1
Pages: 212 - 233
Publication Date: 2017/01/01
ISSN (Online): 1875-6883
ISSN (Print): 1875-6891
DOI: 10.2991/ijcis.2017.10.1.15 How to use a DOI?
Open Access: This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

Cite this article

ris enw bib

TY  - JOUR
AU  - Junfang Luo
AU  - Yaya Liu
AU  - Keyun Qin
AU  - Heng Ding
PY  - 2017
DA  - 2017/01/01
TI  - Incremental update of rough set approximation under the grade indiscernibility relation
JO  - International Journal of Computational Intelligence Systems
SP  - 212
EP  - 233
VL  - 10
IS  - 1
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.2017.10.1.15
DO  - 10.2991/ijcis.2017.10.1.15
ID  - Luo2017
ER  -

download .riscopy to clipboard

International Journal of Computational Intelligence Systems

Incremental update of rough set approximation under the grade indiscernibility relation

1. Introduction

2. Preliminaries

2.1. The grade indiscernibility relation

Definition 1 1

Definition 2 1

Definition 3 18

Definition 4 19

2.2. The non-incremental algorithm of computing approximations

Example 1

3. Incrementally updating approximations while adding or removing an attribute

3.1. Incrementally updating approximations when adding an attribute

Proposition 1

Proof.

Proposition 2

Proof.

Proposition 3

Example 2

3.2. Incrementally updating approximations when removing an attribute

Proposition 4

Proof.

Proposition 5

Proof.

Proposition 6

Example 3

4. Incrementally updating approximations while adding or removing an object

4.1. Incrementally updating approximations when adding an object

Proposition 7

Proof.

Example 4

Proposition 8

Proof.

Example 5

4.2. Incrementally updating approximations when removing an object

Proposition 9

Example 6

Proposition 10

Example 7

5. Incrementally updating approximations when changing the attribute value of the object

5.1. Incrementally updating approximations when changing the decision attribute value of the object

Proposition 11

Example 8

Proposition 12

Example 9

5.2. Incremental updating approximations when changing the conditional attribute value of the object

Proposition 13

Proposition 14

Example 10

Proposition 15

Example 11

6. Algorithm analysis

7. Experimental evaluation

8. Conclusion

Acknowledgements

References

Cite this article

Definition 1 ¹

Definition 2 ¹

Definition 3 ¹⁸

Definition 4 ¹⁹