{'fraction_non_alphanumeric': 0.04514446227929374, 'fraction_numerical': 0.015399277688603531, 'mean_word_length': 4.181133056133056, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Incremental update of rough set approximation under the grade indiscernibility relation

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.


Introduction
Rough set theory, a mathematical tool for dealing with vagueness and uncertainty, was introduced by Pawlak in 1982 1 . 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 setbased 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 re-lation 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 7 , fuzzy rough set model 8 , variable precision rough set model 9 , generalized rough set model 10 , probabilistic rough set model 11 , 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 12 . 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 12 . 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 13 . 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 14 . 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 15 . 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 16 . Zhang et al. investigated the approach for updating approximations under neighborhood rough sets 17 . 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 14 . 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 18 . Based on fuzzy rough set model 8 , Qin investigated rough approximation operators based on the grade indiscernibility relation 19 . For the sake of better applying of the grade indiscernibility relation, Luo extend it to incomplete information system 20 . The value tolerance relation based rough approximation opera-tors are investigated 21 . In this way, we defined the approximation operators based on the grade indiscernibility relation in the same manner 20 . 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.

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

The grade indiscernibility relation
x n } is a nonempty finite set of objects called the universe of discourse; (2) A is a nonempty finite set of attributes; (4) f : U × A → V is an information function such that f (x, a) ∈ V a , for any x ∈ U, a ∈ A.
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 18 , which is defined as follows.
Definition 3 18 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, 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 8 , Qin presented approximation operators based on grade indiscernibility relation 19 .

Definition 4 19
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 ap-proximations GR B (µ) of µ are defined as follows: In this definition, if X ∈ P(U) is a subset of U, Clearly, by the reflexivity of GR B (x, y), we have GR B (X) ⊆ X ⊆ GR B (X) for any X ⊆ U.

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. Algorithm 2.1 (The traditional non-incremental algorithm of computing approximations) Step 1: Input S = (U, A, V, f ), X, B.
Step 3: Calculate the lower approximations Step 4: Calculate the upper approximations Step 5: Output the M n×m ; GR B (X)( 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. 6 } be the decision set. The related information system is given in Table 1.
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: From the step 4 of algorithm 2.1 we have the upper approximations:

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 18 .

Incrementally updating approximations when adding an attribute
Proof. This proof is straightforward.
The lower and upper approximations of X by adding b to B can be updated respectively as follows. Lower approximation: For any For any 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 Upper approximation: Since the incremental update approaches need to use the set of Y ∧ x i and Y ∨ x j , in order to maintain the continuity of the approaches, Y ∧ x i and Y ∨ x j also need to update.

Proposition 3 The set of Y ∧
x i and Y ∨ x j by adding b to B can be updated respectively as follows. Step 1: Input the relation matrix M n×m ; Step 2: We get a new relation matrix Step 3: Calculate the lower approximations // According to Proposition 2 and 3.
Step 4: Calculate the upper approximations x j ∈ U − X.
Step 5: Output the relation matrix M * n×m ; 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 Using the result of Example 1.
From the Step 2 of Algorithm 3.1 we have a new relation matrix M * 3×3 : The lower and upper approximations of X = {x 2 , x 3 , x 6 } by adding b 5 to B are updated as follows.
From the step 3 of algorithm 3.1 we have the lower approximations: From the step 4 of algorithm 3.1 we have the upper approximations:

Incrementally updating approximations when removing an attribute
Proof. This proof is straightforward.
The lower and upper approximations of X by removing b from B can be updated respectively as follows. Lower approximation: Upper approximation: Proof. Lower approximation: For any For any Particularly, if Y ∧ x i = {y k } and Y ∨ x j = {y l } 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 Upper approximation:

Proposition 6
The set of Y ∧ x i and Y ∨ x j by removing b from B can be updated respectively as follows. y, b)). Algorithm 3.2 (Incremental algorithm for updating approximations when removing an attribute b) Step 1: Input the relation matrix M n×m ; Step 3: Calculate the lower approximations . // According to Proposition 5 and 6.
Step 5: Output the relation matrix M * n×m ; 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 5 } be the conditional attribute set, X = {x 2 , x 3 , x 6 } be the decision set. Removing an attribute b 2 from B.
Using the result of Example 2. From the step 3 of algorithm 3.2 we have the lower approximations: For any y ∈ Y ∧ From the step 4 of algorithm 3.2 we have the upper approximations:

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.

Incrementally updating approximations when adding an object
The lower and upper approximations of X by adding x ∨ to U can be updated respectively as follows. Lower approximation: When Proof. Lower approximation: Upper approximation: Algorithm 4.1 (Incremental algorithm for updating approximations when adding an object x ∨ to U − X) Step 1: Input the relation matrix M n×m ; Step 2: We get a new relation matrix M * Step 3: Calculate the lower approximations Step 4: Calculate the upper approximations Step 5: Output the relation matrix M * n×(m+1) ; 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 Using the result of Example 3.
From the Step 2 of Algorithm 4.1 we have a new relation matrix: The lower and upper approximations of X = {x 2 , x 3 , x 6 } by adding x 7 to U − X are updated as follows.
From the step 3 of algorithm 4.1 we have the lower approximations: The lower and upper approximations of X ∨ = X ∪ {x ∨ } by adding x ∨ to X can be updated respectively as follows.
Lower approximation: Upper approximation: When x j ∈ X ∨ , we have GR Proof. This proof is similar to that of Proposition 7.
Algorithm 4.2 (Incremental algorithm for updating approximations when adding an object x ∨ to X) Step 1: Input the relation matrix M n×m ; Step 2: We get a new relation matrix Step 3: Calculate the lower approximations // According to Proposition 8.
Step 5: Output the relation matrix M * (n+1)×m ; 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.
Using the result of Example 4.

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: Algorithm 4.3 (Incremental algorithm for updating approximations when removing an object x ∧ from U − X) Step 1: Input the relation matrix M n×m ; Step 3: Calculate the lower approximations // According to the Proposition 9.
Step 4: Calculate the upper approximations // According to the Proposition 9.
Step 5: Output the relation matrix M * n×(m−1) ; 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.
Using the result of Example 5.
The lower and upper approximations of X ∧ = X − {x ∧ } by removing x ∧ from X can be respectively updated as follows.
Lower approximation: Upper approximation: Step 1: Input the relation matrix M n×m ; Step 2: We get a new relation matrix M * (n−1)×m .
Step 3: Calculate the lower approximations // According to the Proposition 10.
Step 4: Calculate the upper approximations // According to the Proposition 10.
Step 5: Output the relation matrix M * (n−1)×m ; 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.
Using the result of Example 6.
From the Step 2 of Algorithm 4.4 we have a new relation matrix M * 3×3 : The lower and upper approximations of X ∧ = {x 2 , x 6 , x 8 } by removing x 3 from X be updated as follows: From the step 3 of algorithm 4.4 we have the lower approximations:

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.

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 ∨ )(x i ) = GR B (X)(x i ) = 0. If x i ∈ X ∨ , we have: Upper approximation: If x j ∈ X ∨ , we have GR B (X ∨ )(x j ) = 1. If x j ∈ U − X ∨ , we have: If GR B (x j , x ∨ ) < GR B (X)(x j ), then GR B (X ∨ )(x j ) = GR B (X)(x j ) and Y ∨ * x j = Y ∨ x j . Algorithm 5.1 (Incremental algorithm for updating approximations when changing the decision attribute value of x ∨ , x ∨ ∈ U − X to x ∨ ∈ X) Step 1: Input the relation matrix M n×m ; GR B (X)(x i ), Y ∧ x i , x i ∈ X; GR B (X)(x j , Y ∨ x j , 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 4: Calculate the upper approximations // According to the Proposition 11.
Step 5: Output the relation matrix M * (n+1)×(m−1) ; 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 1 , x 2 , x 5 , x 6 , x 7 , x 8 } be the universal set, B = {b 1 , b 3 , b 4 , b 5 } be the conditional attribute set, X = {x 2 , x 6 , x 8 } be the decision set. Changing the decision attribute value of x 5 to X from U − X, X ∨ = X ∪ {x 5 }. Table 7.