Matrix-based approaches for updating approximations in neighborhood multigranulation rough sets while neighborhood classes decreasing or increasing

Abstract

With the revolution of computing and biology technology, data sets containing information could be huge and complex that sometimes are difficult to handle. Dynamic computing is an efficient approach to solve some of the problems. Since neighborhood multigranulation rough sets(NMGRS) were proposed, few papers focused on how to calculate approximations in NMGRS and how to update them dynamically. Here we propose approaches for computing approximations in NMGRS and updating them dynamically. First, static approaches for computing approximations in NMGRS are proposed. Second, search region in data set for updating approximations in NMGRS is shrunk. Third, matrix-based approaches for updating approximations in NMGRS while decreasing or increasing neighborhood classes are proposed. Fourth, incremental algorithms for updating approximations in NMGRS while decreasing or increasing neighborhood classes are designed. Finally, the efficiency and validity of the designed algorithms are verified by experiments.

Keywords

Approximation computation multigranulation rough set knowledge acquisition decision making

1 Introduction

Since rough sets was proposed by Pawlak in 1982, it has been widely used in various fields such as pattern recognition [14], machine learning [32], image precessing [23, 24], decision making [11 , 44], data mining and other relevant areas. Many models were proposed to extend its application, for example, covering based rough sets [39], variable precision rough sets [12], probabilistic rough sets [38], fuzzy rough sets [8 , 36], fuzzy variable precision rough sets [45].

Qian et al. proposed multigranulation rough sets [25] (MGRS) based on multiple equivalence relation in 2010, which include optimistic and pessimistic multigranulation rough sets. In recent years, many models have been proposed based on the two decision strategies that “Seeking common ground while reserving differences” and “Seeking common ground with eliminating differences”. For example, by popularizing the binary relation from equivalence relation to neighborhood relation, Lin et al. proposed neighborhood multigranulation rough sets (NMGRS). Lots of studies focus on deriving models by the same decision strategy. Huang et al. proposed intuitionistic fuzzy multigranulation rough sets [9]. Feng et al. proposed variable precision multigranulation decision-theoretic fuzzy rough sets [5]. Li et al. proposed three-way cognitive concept learning via multi-granularity [15]. More over, there are researches about multigranulation rough sets and their relative models, such as multigranulation rough set theory over two universes [31], a comparative study of multigranulation rough sets and concept lattices via rule acquisition [16].

In an information explosion era, approximation computing becomes more and more difficult: the size of data sometimes is too huge to handle, the structure of data is changing to be more complex, and the granular structures often increase or decrease. The issue of computing and updating approximations in MGRS and their derived models attracts much research interest. The studies are often categorized into four classes, namely, how to update approximations while varying attributes [37, 42], how to update approximations while varying attribute values [3, 40], how to update approximations while varying decision attribute values [21, 37], how to update approximations while varying object set [7, 19].

No matter what variation is, there always exist two means to determine the relation between two sets: set operation or matrix product. Therefore, we can classify those studies into two categories. One is based on set operation. Scholars use set operation to determine whether a set is contained in another set or not, or whether their intersection is empty or not (see Chuan Luo [20, 22], Wenhao Shu [29], Guangming Lang [13], Mingjie Cai [2], Wei Wei [34] and etc). When granule size is generally big, set operation is a time consuming way because of its searching strategy: when we compute the intersection of two sets, we must confirm whether every object in a set is in another set or not. In the extreme case, when the two sets are both U(all samples are in a data set), then the time complexity of computing the intersection of them is |U|². The other category is based on matrix. These studies are mostly based on matrix product or other operations. Scholars often change a set into binary matrix, and then design algorithms based on properties of binary matrix (see Jingqian Wang [33], Chengxiang Hu [6], Yanyong Huang [10] and etc). Although the time complexity of determining the relation between two sets via matrix approach is a constant, they often consider all the objects in the universe without filtering.

We attempt to combine the two approaches and derive new methods to overcome their defects. In other words, we concentrate on which part of the universe does not need to be considered while computing and updating approximations in NMGRS. At the same time, we determine the relation between two sets by matrix product.

Lin et al. proposed NMGRS [17] in 2012. NMGRS is a powerful mathematical tool in representing some real life situations and it extends the application of MGRS into a broader area. When we apply NMGRS in real life situations, approximation computing is an essential part. Approximations must be computed before making decision. Positive region must be calculated so that attributes can be selected in some attribute reduction process. Calculating approximations is necessary when applying rough set theory, thus how to compute approximations is an important issue in NMGRS. Granulation and approximation are two important issues in all rough sets models that can not be avoided. In NMGRS theory, different granule sizes have a big influence in its applications. Decreasing or increasing granules changes the approximations directly. Thus choosing an appropriate size of granules makes a great difference in decision making process [27]. Similar phenomenon exists in attribute reduction process because decreasing or increasing granules changes the positive region directly.

Neighborhood classes often decrease or increase. So it is important to update approximations in NMGRS based on approximations we have computed. We design algorithms for updating approximations while decreasing or increasing neighborhood classes. First, searching region while updating approximations in NMGRS need to be shrunk. A shrunk searching region can reduce the executing time of the algorithms. Second, matrix-based approaches need to be proposed to make the algorithms more efficient.

The rest of this paper is organized as follows. Section 2 introduces several basic concepts of NMGRS and matrix-based static algorithms to calculate approximations in NMGRS. In Section 3, dynamic approaches for updating approximations in NMGRS while decreasing or increasing neighborhood classes are proposed. Several algorithms designed using approaches that we proposed are given in Section 4. Experimental evaluations are conducted in Section 5 to verify the efficiency and validity of these algorithms. Finally, some conclusion and future work are given in Section 6.

2 Preliminaries

In this section, we review several basic concepts of NMGRS and propose matrix-based static approaches for computing approximations in NMGRS.

2.1 Neighborhood Multigranulation rough sets

In this subsection, several basic concepts of NMGRS are reviewed.

Definition 1.[17] (PNMGRS) Let NIS = (U, AT, δ) be a neighborhood information system, where A_k ∈ AT for any k∈ { 1, 2, ⋯ , m }, and δ is a nonnegative number. $\forall k \in {1, 2, \dots, m}, A_{k}^{C}, A_{k}^{N} \subseteq A_{k}$ are categorical and numerical attributes, respectively. The neighborhood classes of objects x induced by $A_{k}^{C}$ , $A_{k}^{N}$ and $A_{k}^{C} \cup A_{k}^{N}$ are defined as

$n_{A_{k}^{C}} (x) = {x_{i} \in U | d_{A_{k}^{C}} (x, x_{i}) = 0};$

$n_{A_{k}^{N}} (x) = {x_{i} \in U | d_{A_{k}^{N}} (x, x_{i}) \leq δ};$

$n_{A_{k}^{C} \cup A_{k}^{N}} (x) = {x_{i} \in U | d_{A_{k}^{C}} (x, x_{i}) = 0$ $\land d_{A_{k}^{N}} (x, x_{i}) \leq δ};$

where d is a distance [28] between x and x_i.

Accordingly, we say (U, δ) is a neighborhood approximation space, if there is an attribute subset in the system generating a neighborhood relation on the universe. We consider this system as a neighborhood information system, and denote it as NIS = (U, AT, δ), where U is a nonempty finite set and AT is a group of attribute set.

In this paper we consider distance between two objects as Euclid distance, which is defined as follows.

Definition 2. [1] The Euclidean distance between two points p and q is the length of the line segment connecting them in Cartesian coordinates. If p = (p₁, p₂, ⋯ , p_n) and q = (q₁, q₂, ⋯ , q_n) are two points in Euclidean n-space, then the distance (d) between p and q is given by the Pythagorean formula: $\begin{matrix} d (p, q) = d (q, p) = \\ \sqrt{(q_{1} - p_{1})^{2} + (q_{2} - p_{2})^{2} + \dots + (q_{n} - p_{n})^{2}} . \end{matrix}$

Definition 3. [17] (ONMGRS)Let NIS = (U, AT, δ) be a neighborhood information system, where A_k ∈ AT for any k∈ { 1, 2, ⋯ , m }, and δ is a nonnegative number. For any X ⊆ U, the optimistic neighborhood multigranulation lower and upper approximations of X are denoted by $\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{O}} (X)$ and $\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{O}} (X)$ , respectively, $\begin{matrix} \underline{\sum_{k = 1}^{m} δ_{A_{k}}^{O}} (X) = {x \in U | n_{A_{1}^{C} \cup A_{1}^{N}} (x) \subseteq X \lor n_{A_{2}^{C} \cup A_{2}^{N}} (x) \\ \subseteq X \lor \dots \lor n_{A_{m}^{C} \cup A_{m}^{N}} (x) \subseteq X}, \end{matrix}$ $\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{O}} (X) = \sim \underline{\sum_{k = 1}^{m} δ_{A_{k}}^{O}} (\sim X) .$ where $n_{A_{1}^{C} \cup A_{k}^{N}} (x)$ is the neighborhood class of x in terms of the attribute set A_k and neighborhood radius δ, ∼X is the complement of the set X.

Theorem 1. [17] Let NIS = (U, AT, δ) be a neighborhood information system, where A_k ∈ AT for any k∈ { 1, 2, ⋯ , m }, and δ is a nonnegative number. For any X ⊆ U, the optimistic neighborhood multigranulation upper approximation of X is denoted by $\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{O}} (X)$ . We have $\begin{matrix} \bar{\sum_{k = 1}^{m} δ_{A_{k}}^{O}} (X) = {x \in U | n_{A_{1}^{C} \cup A_{1}^{N}} (x) \cap X \neq \emptyset \land \\ n_{A_{2}^{C} \cup A_{2}^{N}} (x) \cap X \neq \emptyset \land \dots \land n_{A_{m}^{C} \cup A_{m}^{N}} (x) \cap X \neq \emptyset} . \end{matrix}$

Definition 4. [17] Let NIS = (U, AT, δ) be a neighborhood information system, where A_k ∈ AT for any k∈ { 1, 2, ⋯ , m }, and δ is a nonnegative number. For any X ⊆ U, the pessimistic neighborhood multigranulation lower and upper approximations of X are denoted by $\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (X)$ and $\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (X)$ , respectively, $\begin{matrix} \underline{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (X) = {x \in U | n_{A_{1}^{C} \cup A_{1}^{N}} (x) \subseteq X \land n_{A_{2}^{C} \cup A_{2}^{N}} (x) \\ \subseteq X \land \dots \land n_{A_{m}^{C} \cup A_{m}^{N}} (x) \subseteq X}, \end{matrix}$ $\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (X) = \sim \underline{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (\sim X) .$

Theorem 2. [17] Let NIS = (U, AT, δ) be a neighborhood information system, where A_k ∈ AT for any k∈ { 1, 2, ⋯ , m }, and δ is a nonnegative number. For any X ⊆ U, the pessimistic neighborhood multigranulation upper approximation of X is denoted by $\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (X)$ . We have $\begin{matrix} \bar{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (X) = {x \in U | n_{A_{1}^{C} \cup A_{1}^{N}} (x) \cap X \neq \emptyset \lor \\ n_{A_{2}^{C} \cup A_{2}^{N}} (x) \cap X \neq \emptyset \lor \dots \lor n_{A_{m}^{C} \cup A_{m}^{N}} (x) \cap X \neq \emptyset} . \end{matrix}$

2.2 Matrix-based algorithm for computing approximations in NMGRS

Definition 5. [6] Let U ={ x₁, x₂, ⋯ , x_n }, for any X ⊆ U, the matrix representation of X is denoted by V (X) = [v₁ (X) , ⋯ , v_n (X)], where $v_{i} (X) = {\begin{matrix} 1 x_{i} & \in X \\ 0 x_{i} & \notin X \end{matrix} i \in {1, 2, \dots, n}$

Lemma 3. [4] Let U ={ x₁, x₂, ⋯ , x_n }, for any X, Y ⊆ U, if Y ⊆ X, then $V (Y) \cdot V^{T} (\sim X) = 0 .$ where “T” denotes the transpose operation and “·” is matrix product.

Lemma 4. [4] Let U ={ x₁, x₂, ⋯ , x_n }. For any X, Y ⊆ U, if Y∩ X ≠ ∅, then $V (Y) \cdot V^{T} (X) > 0 .$

Example 1. Let NIS = (U, AT, δ) be a neighborhood information system, as shown in Table 1, where U ={ x₁, x₂, x₃, x₄, x₅, x₆ }. $A_{1} = A_{1}^{C} \cup A_{1}^{N}$ , $A_{1}^{C} = {a_{1}}$ and $A_{1}^{N} = {a_{3}}$ , $A_{2} = A_{2}^{C} \cup A_{2}^{N}$ , $A_{2}^{C} = {a_{2}}$ and $A_{2}^{N} = {a_{4}}$ . Let X ={ x₂, x₄, x₅ }, δ = 1. According to Definition 5, we have V (X) = [0, 1, 0, 1, 1, 0] ^T. Suppose Y ={ x₂, x₄ }, Z ={ x₂, x₆ }, then V (Y) = [0, 1, 0, 1, 0, 0], V (Z) = [0, 1, 0, 0, 0, 1]. Obviously, Y ⊆ X, Z∩ X ≠ ∅. V (∼ X) = [1, 0, 1, 0, 0, 1], V (Y) · V^T (∼ X) = [0, 1, 0, 1, 0, 0] · [1, 0, 1, 0, 0, 1] ^T = 0, V (Z) · V^T (X) = [0, 1, 0, 0, 0, 1] · [0, 1, 0, 1, 1, 0] ^T = 1 >0 .

Table 1
A neighborhood information system

U a ₁ a ₂ a ₃ a ₄

x ₁ 1 3 1.5 0.5

x ₂ 2 2 0.5 1

x ₃ 3 1 2 2.5

x ₄ 2 3 1.5 1

x ₅ 1 1 2 0.5

x ₆ 3 2 0.5 2

U	a ₁	a ₂	a ₃	a ₄
x ₁	1	3	1.5	0.5
x ₂	2	2	0.5	1
x ₃	3	1	2	2.5
x ₄	2	3	1.5	1
x ₅	1	1	2	0.5
x ₆	3	2	0.5	2

Definition 6. Let NIS = (U, AT, δ) be a neighborhood information system, where A_k ∈ AT for any k∈ { 1, 2, ⋯ , m }, and δ is a nonnegative number. For any X ⊆ U, the upper approximation character sets of X in NMGRS can be defined as: $\begin{matrix} δ_{A_{k}}^{L} (X) = {x \in U | n_{A_{k}^{C} \cup A_{k}^{N}} (x) \subseteq X}, \\ \forall k = 1, 2, \dots, m . \end{matrix}$

Theorem 5. Let IS = (U, AT, V_AT, f) be an information system, where A_k ∈ AT for any k∈ { 1, 2, ⋯ , m }. For any X ⊆ U, the pessimistic and optimistic lower approximations in NMGRS can be calculated by: $\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (X) = \cap_{k = 1}^{m} δ_{A_{k}}^{L} (X); \underline{\sum_{k = 1}^{m} δ_{A_{k}}^{O}} (X) = \cup_{k = 1}^{m} δ_{A_{k}}^{L} (X) .$

Proof. This theorem can be easily obtained by Definitions 3 and 4.□

Example 2. (Continuation of Example 1) By Theorem 3, since $\begin{matrix} V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{1})) \cdot V^{T} (\sim X) = V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{5})) \cdot \\ V^{T} (\sim X) = [1, 0, 0, 0, 1, 0] \cdot [1, 0, 1, 0, 0, 1]^{T} \\ = 1 \neq 0, \\ V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{2})) \cdot V^{T} (\sim X) = V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{4})) \cdot \\ V^{T} (\sim X) = [0, 1, 0, 1, 0, 0] \cdot [1, 0, 1, 0, 0, 1]^{T} = 0, \\ V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{3}) \cdot V^{T} (\sim X) = [0, 0, 1, 0, 0, 0] \cdot \\ [1, 0, 1, 0, 0, 1]^{T} = 1 \neq 0, \\ V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{6}) \cdot V^{T} (\sim X) = [0, 0, 0, 0, 0, 1] \cdot \\ [1, 0, 1, 0, 0, 1]^{T} = 1 \neq 0; \end{matrix}$

$\begin{matrix} V (n_{A_{2}^{C} \cup A_{2}^{N}} (x_{1})) \cdot V^{T} (\sim X) = V (n_{A_{2}^{C} \cup A_{2}^{N}} (x_{4})) \cdot \\ V (\sim X)^{T} = [1, 0, 0, 1, 0, 0] \cdot [1, 0, 1, 0, 0, 1]^{T} \\ = 1 \neq 0, \\ V (n_{A_{2}^{C} \cup A_{2}^{N}} (x_{2})) \cdot V^{T} (\sim X) = V (n_{A_{2}^{C} \cup A_{2}^{N}} (x_{6})) \cdot \\ V (\sim X)^{T} = [0, 1, 0, 0, 0, 1] \cdot [1, 0, 1, 0, 0, 1]^{T} \\ = 1 \neq 0, \\ V (n_{A_{2}^{C} \cup A_{2}^{N}} (x_{3})) \cdot V^{T} (\sim X) = [0, 0, 1, 0, 0, 0] \cdot \\ [1, 0, 1, 0, 0, 1]^{T} = 1 \neq 0, \\ V (n_{A_{2}^{C} \cup A_{2}^{N}} (x_{5})) \cdot V^{T} (\sim X) = [0, 0, 0, 0, 1, 0] \cdot \\ [1, 0, 1, 0, 0, 1]^{T} = 0, \end{matrix}$ then by Definition 6, $\begin{matrix} V (δ_{A_{1}}^{L} (X)) = V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{2})) \lor V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{4})) \\ = [0, 1, 0, 1, 0, 0], \\ V (δ_{A_{2}}^{L} (X)) = V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{5})) = [0, 1, 0, 0, 1, 0] . \end{matrix}$ By Theorem 5, $\begin{matrix} \underline{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (X) = V (δ_{A_{1}}^{U} (X)) \land V (δ_{A_{2}}^{U} (X)) = [0, 1, 0, \\ 1, 0, 0] \land [0, 1, 0, 0, 1, 0] = [0, 1, 0, 0, 0, 0], \\ \underline{\sum_{k = 1}^{m} δ_{A_{k}}^{O}} (X) = V (δ_{A_{1}}^{U} (X)) \lor V (δ_{A_{2}}^{U} (X)) = [0, 1, 0, \\ 1, 0, 0] \lor [0, 1, 0, 0, 1, 0] = [0, 1, 0, 1, 1, 0] . \end{matrix}$ By Definition 5, $\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (X) = \emptyset, \underline{\sum_{k = 1}^{m} δ_{A_{k}}^{O}} (X) = {x_{2}, x_{4}, x_{5}} .$

Definition 7. Let NIS = (U, AT, δ) be a neighborhood information system, where A_k ∈ AT for any k∈ { 1, 2, ⋯ , m }, and δ is a nonnegative number. For any X ⊆ U, the upper approximation character sets of X in NMGRS can be defined as: $\begin{matrix} δ_{A_{k}}^{U} (X) = {x \in U | n_{A_{k}^{C} \cup A_{k}^{N}} (x) \cap X \neq \emptyset}, \\ \forall k = 1, 2, \dots, m . \end{matrix}$

Theorem 6. Let IS = (U, AT, V_AT, f) be an information system, where A_k ∈ AT for any k∈ { 1, 2, ⋯ , m }. For any X ⊆ U, the optimistic and pessimistic upper approximations can be calculated by: $\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (X) = \cup_{k = 1}^{m} δ_{A_{k}}^{U} (X); \bar{\sum_{k = 1}^{m} δ_{A_{k}}^{O}} (X) = \cap_{k = 1}^{m} δ_{A_{k}}^{U} (X) .$

Proof. This theorem can be easily obtained by Theorems 1 and 2. □

Example 3. (Continuation of Example 1.) From Table 1, by Lemma 4, since $\begin{matrix} V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{1})) \cdot V^{T} (X) = V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{5})) \cdot \\ V^{T} (X) = [1, 0, 0, 0, 1, 0] \cdot [0, 1, 0, 1, 1, 0]^{T} \\ = 1 > 0, \\ V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{2})) \cdot V^{T} (X) = V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{4})) \cdot \\ V^{T} (X) = [0, 1, 0, 1, 0, 0] \cdot [0, 1, 0, 1, 1, 0]^{T} \\ = 1 > 0, \\ V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{3}) \cdot V^{T} (X) = [0, 0, 1, 0, 0, 0] \cdot \\ [0, 1, 0, 1, 1, 0]^{T} = 0, \\ V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{6}) \cdot V^{T} (X) = [0, 0, 0, 0, 0, 1] \cdot \\ [0, 1, 0, 1, 1, 0]^{T} = 0; \end{matrix}$ $\begin{matrix} V (n_{A_{2}^{C} \cup A_{2}^{N}} (x_{1})) \cdot V^{T} (X) = V (n_{A_{1}^{C} \cup A_{2}^{N}} (x_{4})) \cdot \\ V (X) = [1, 0, 0, 1, 0, 0] \cdot [0, 1, 0, 1, 1, 0]^{T} \\ = 1 > 0, \\ V (n_{A_{2}^{C} \cup A_{2}^{N}} (x_{2})) \cdot V^{T} (X) = V (n_{A_{1}^{C} \cup A_{2}^{N}} (x_{6})) \cdot \\ V (X) = [0, 1, 0, 0, 0, 1] \cdot [0, 1, 0, 1, 1, 0]^{T} \\ = 1 > 0, \\ V (n_{A_{2}^{C} \cup A_{2}^{N}} (x_{3})) \cdot V^{T} (X) = [0, 0, 1, 0, 0, 1] \cdot \\ [0, 1, 0, 1, 1, 0]^{T} = 0, \\ V (n_{A_{2}^{C} \cup A_{2}^{N}} (x_{5})) \cdot V^{T} (X) = [0, 0, 0, 0, 1, 0] \cdot \\ [0, 1, 0, 1, 1, 0]^{T} = 1 > 0, \end{matrix}$ then by Definition 7, $\begin{matrix} V (δ_{A_{1}}^{U} (X)) & = V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{1})) \lor V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{2})) \\ = [1, 1, 0, 1, 1, 0], \end{matrix}$

$\begin{matrix} V (δ_{A_{2}}^{U} (X)) & = V (n_{A_{2}^{C} \cup A_{2}^{N}} (x_{1})) \lor V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{2})) \\ \lor V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{5})) = [1, 1, 0, 1, 1, 1] . \end{matrix}$ By Theorem 6, $\begin{matrix} V (\bar{\sum_{k = 1}^{2} δ_{A_{k}}^{P}} (X)) = V (δ_{A_{1}}^{U} (X)) \lor V (δ_{A_{2}}^{U} (X)) = [1, 1, \\ 0, 1, 1, 0] \lor [1, 1, 0, 1, 1, 1] = [1, 1, 0, 1, 1, 1], \\ V (\bar{\sum_{k = 1}^{2} δ_{A_{k}}^{O}} (X)) = V (δ_{A_{1}}^{U} (X)) \land V (δ_{A_{2}}^{U} (X)) = [1, 1, \\ 0, 1, 1, 0] \land [1, 1, 0, 1, 1, 1] = [1, 1, 0, 1, 1, 0] . \end{matrix}$ By Definition 5, $\begin{matrix} \bar{\sum_{k = 1}^{2} δ_{A_{k}}^{P}} (X) = {x_{1}, x_{2}, x_{4}, x_{5}, x_{6}}, \\ \bar{\sum_{k = 1}^{2} δ_{A_{k}}^{O}} (X) = {x_{1}, x_{2}, x_{4}, x_{5}} . \end{matrix}$

Algorithm 1 is a matrix-based algorithm for computing approximations in NMGRS. The total time complexity of the algorithm is O (|AT||X||U|). Steps 2-7 are to calculate $δ_{A_{k}}^{L}$ and $δ_{A_{k}}^{U}$ (k∈ { 1, 2, ⋯ , m }) with time complexity O (|AT||X||U|). Steps 7-17 are to compute the approximations of NMGRS with time complexity O (|AT||U|).

Algorithm 1

Matrix-based algorithm for computing approximations in NMGRS

Require: (1)A neighborhood information system NIS = (U, AT, δ), the granular structures A₁, A₂, ⋯ , A_m.(2)A target concept X ⊆ U (3)neighborhood classes

n_{A_{k}^{C} \cup A_{k}^{N}} (x), \forall x \in U, \forall k \in {1, 2, \dots, m}

Ensure: Approximations in NMGRS.

1: m ← |AT|

2: n ← |U|

3: fork = 1 → mdo

4: fori = 1 → ndo

5: forj = 1 → ndo

6: if

v_{i} (X) = 1 \land V (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{i})) \cdot V^{T} (\sim (X)) = 0

then

v_{i} (δ_{A_{k}}^{L}) = 1

7: end if

8: if

v_{i} (X) = 1 \land v_{i} (n_{A_{1}^{C} \cup A_{1}^{N}} (x_{j})) = 1

v_{j} (δ_{A_{k}}^{U}) = 1

9: end if

10: end for

11: end for

12: end for

13:

V (\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{O}} (X)) \leftarrow V (δ_{A_{1}}^{U})

14:

V (\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (X)) \leftarrow V (δ_{A_{1}}^{U})

15:

V (\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (X)) \leftarrow V (δ_{A_{1}}^{L})

16:

V (\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (X)) \leftarrow V (δ_{A_{1}}^{L})

17: fork = 2 → mdo

18:

V (\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{O}} (X)) \leftarrow V (\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{O}} (X)) \lor V (δ_{A_{k}}^{L})

19:

V (\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{O}} (X)) \leftarrow V (\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{O}} (X)) \land V (δ_{A_{k}}^{U})

20:

V (\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (X)) \leftarrow V (\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (X)) \land V (δ_{A_{k}}^{L})

21:

V (\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (X)) \leftarrow V (\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (X)) \lor V (δ_{A_{k}}^{U})

22: end for

23: Return

\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{O}} (X), \bar{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (X)

\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{O}} (X)

and

\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{P}} (X)

3 Matrix-based dynamic approaches for updating approximations in NMGRS while neighborhood classes are decreasing and increasing

3.1 Matrix-based approaches for updating approximations while neighborhood classes are decreasing

In this subsection, we present matrix-based dynamic approaches for updating approximations in NMGRS while neighborhood classes are decreasing. We denote NIS^t = (U, AT^t, Δ) an neighborhood information system at time t, NIS^t+1 = (U, AT^t+1, δ) an neighborhood information system at time t + 1 where δ and Δ are two nonnegative numbers and δ ≤ Δ. For all $A_{k}^{t} \in {AT}^{t} (k \leq m)$ , there exists $A_{k}^{t + 1} \in {AT}^{t + 1}$ , such that $(A_{k}^{C})^{t} \subseteq (A_{k}^{C})^{t + 1}$ , $(A_{k}^{N})^{t} \subseteq (A_{k}^{N})^{t + 1}$ . Also, for all x ∈ U, we denote neighborhood class of x at time t by $n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x)$ . Denote neighborhood class of x at time t + 1 by $n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x)$ . Denote approximations in PNMGRS by ${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X)$ and ${\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X)$ at time t. Denote approximations in PNMGRS by ${\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{P} (X)$ and ${\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{P} (X)$ at time t + 1. Denote approximations in ONMGRS by ${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X)$ and ${\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X)$ at time t. Denote approximations in ONMGRS by ${\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X)$ and ${\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X)$ at time t + 1.

Theorem 7. Let NIS^t = (U, AT^t, Δ) be an neighborhood information system at time t, NIS^t+1 = (U, AT^t+1, δ) be a neighborhood information system at time t + 1. For any X ⊆ U, the following result holds. $n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \subseteq n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x) .$

Proof.

If $(A_{k}^{C})^{t} \subseteq (A_{k}^{C})^{t + 1}$ , we have $n_{A_{k}^{C}}^{t + 1} (x) \subseteq n_{A_{k}^{C}}^{t} (x) \Rightarrow n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \subseteq n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x)$ ;

If $(A_{k}^{N})^{t} \subseteq (A_{k}^{N})^{t + 1}$ , we have $n_{A_{k}^{N}}^{t + 1} (x) \subseteq n_{A_{k}^{N}}^{t} (x) \Rightarrow n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \subseteq n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x)$ ;

If δ ≤ Δ, we have $n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \subseteq n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x)$ .

□

Theorem 8. Let NIS^t = (U, AT^t, Δ) be a neighborhood information system at time t, NIS^t+1 = (U, AT^t+1, δ) be a neighborhood information system at time t + 1. For any X ⊆ U, the following results hold. $(1) {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X) \subseteq {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X);$ $(2) {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X) \supseteq {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X)$ .

Proof. (1) $\forall x \in {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X), x \in {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)$ $\Rightarrow \exists k \in {1, 2, \dots, m}, n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x) \subseteq X \Rightarrow \exists k \in {1,$ 2, ⋯, m}, $n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \subseteq X \Rightarrow x \in {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X)$ , we have ${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X) \subseteq {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X);$ (2) $\forall x \in {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X), x \in {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X) \Rightarrow \forall k \in {1, 2, \dots, m}, n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \cap X \neq \emptyset \Rightarrow \forall k \in {1, 2, \dots, m}, n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x) \cap X \neq \emptyset \Rightarrow x$ $\in {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)$ , we have ${\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) \subseteq {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X);$ □

Theorem 9. Let NIS^t = (U, AT^t, Δ) be a neighborhood information system at time t, NIS^t+1 = (U, AT^t+1, δ) be a neighborhood information system at time t + 1. For any X ⊆ U, the following results hold. $(1) {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) \subseteq {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{P} (X);$ $(2) {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) \supseteq {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{P} (X) .$

Proof. It is similar to that of Theorem 8. □

Theorems 8 and 9 indicate the relations among lower and upper approximations in NMGRS between time t and time t + 1. However, they are not clear enough for updating approximations in NMGRS. The following theorem provides accurate approaches for updating approximations in NMGRS from time t to t + 1.

Theorem 10. Let NIS^t = (U, AT^t, Δ) be a neighborhood information system at time t, NIS^t+1 = (U, AT^t+1, δ) be a neighborhood information system at time t + 1. For any X ⊆ U, we have

if ${\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X) = {x | \exists k \in {1, 2, \dots,$ $m}, n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \subseteq X, x \in {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) - {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X)}$ , then ${\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X) = {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X) \cup {\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X) .$

if ${\bar{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X) = {x | \exists k \in {1, 2, \dots,$ $m}, n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \cap X = \emptyset, x \in {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) - {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X)}$ , then ${\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X) = {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X) - {\bar{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X) .$

if ${\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{P} (X) = {x | \forall k \in {1, 2, \dots,$ $m}, n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \subseteq X, x \in {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) - {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X)}$ , then ${\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{P} (X) = {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) \cup {\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{P} (X) .$

if ${\bar{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{P} (X) = {x | \forall k \in {1, 2, \dots,$ $m}, n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \cap X = \emptyset, x \in {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) - {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X)}$ , then ${\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{P} (X) = {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) - {\bar{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{P} (X) .$

Proof.

“⇐”: Since we have ${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X) \subseteq {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X),$ and ${\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X) \subseteq {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X),$ we have ${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X) \cup {\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X) \subseteq {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X) .$ “⇒”:If $x \notin {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X) \cup {\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X)$ , since we have $n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1}$ $(x) \subseteq n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x)$ , $n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x) X \Rightarrow n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) X$ , $x \notin {\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X)$ and $x \in U - {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{P} (X) \Rightarrow n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x) \cap X = \emptyset \Rightarrow n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \cap X = \emptyset \Rightarrow x \notin {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X)$ , we have $x \notin {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \cup {\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X) \Rightarrow x \notin {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X)$ , ${\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X) \subseteq {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \cup {\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X) .$ This completes the proof.

“⇒”: $\forall x \in {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X) \Rightarrow n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x)$ $\cap X \neq \emptyset \Rightarrow n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x) \cap X \neq \emptyset \Rightarrow x \in {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)$ , $x \in {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X) \Rightarrow x \notin$ ${\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X)$ , thus we have ${\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X) \subseteq {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) - {\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X) .$ “⇐”: $\forall x \in {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X)$ , if $n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \cap X \neq \emptyset \Rightarrow x \in {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X)$ , if $n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \cap X = \emptyset \Rightarrow x \in {\bar{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X)$ , since we have ${\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) \subseteq {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X)$ , we have ${\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X) - {\bar{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X)$ $\subseteq {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X) .$ This completes the proof.

It is similar to i.

It is similar to ii.□

Example 4. (Continuation of Example 1) Supposed ${AT}^{t} = {A_{1}^{t}, A_{2}^{t}}, A_{1}^{t} = (A_{1}^{C})^{t} \cup (A_{1}^{N})^{t}$ , $(A_{1}^{C})^{t} = {a_{1}}$ and $(A_{1}^{N})^{t} = \emptyset$ , $A_{2}^{t} = (A_{2}^{C})^{t} \cup (A_{2}^{N})^{t}$ , $(A_{2}^{C})^{t} = \emptyset$ and $(A_{2}^{N})^{t} = {a_{3}}$ , ${AT}^{t + 1} = {A_{1}^{t + 1}, A_{2}^{t + 1}}, A_{1}^{t + 1} = (A_{1}^{C})^{t + 1} \cup (A_{1}^{N})^{t + 1}$ , $(A_{1}^{C})^{t + 1} = {a_{1}}$ and $(A_{1}^{N})^{t + 1}$ = {a₄}, $A_{2}^{t + 1} = (A_{2}^{C})^{t + 1} \cup (A_{2}^{N})^{t + 1}$ , $(A_{2}^{C})^{t + 1} = {a_{1}}$ and $(A_{2}^{N})^{t + 1} = {a_{3}}$ . Let X = {x₂, x₃, x₄, x₆} and Δ = 0.5, δ = 0.5.

By Definition 1 we have $\begin{matrix} n_{A_{1}^{C} \cup A_{1}^{N}}^{t} (x_{1}) & = {x_{1}, x_{5}}, n_{A_{1}^{C} \cup A_{1}^{N}}^{t} (x_{2}) \\ = {x_{2}, x_{4}}, n_{A_{1}^{C} \cup A_{1}^{N}}^{t} (x_{3}) = {x_{3}, x_{6}}, \\ n_{A_{1}^{C} \cup A_{1}^{N}}^{t} (x_{4}) & = {x_{2}, x_{4}}, n_{A_{1}^{C} \cup A_{1}^{N}}^{t} (x_{5}) \\ = {x_{1}, x_{5}}, n_{A_{1}^{C} \cup A_{1}^{N}}^{t} (x_{6}) = {x_{3}, x_{6}} . \end{matrix}$ $\begin{matrix} n_{A_{2}^{C} \cup A_{2}^{N}}^{t} (x_{1}) & = {x_{1}, x_{3}, x_{4}, x_{5}}, n_{A_{2}^{C} \cup A_{2}^{N}}^{t} (x_{2}) \\ = {x_{2}, x_{6}}, n_{A_{2}^{C} \cup A_{2}^{N}}^{t} (x_{3}) = {x_{1}, x_{3}, x_{4}, x_{5}}, \end{matrix}$

$\begin{matrix} n_{A_{2}^{C} \cup A_{2}^{N}}^{t} (x_{4}) & = {x_{1}, x_{3}, x_{4}, x_{5}}, n_{A_{2}^{C} \cup A_{2}^{N}}^{t} (x_{5}) \\ = {x_{1}, x_{3}, x_{4}, x_{5}}, n_{A_{2}^{C} \cup A_{2}^{N}}^{t} (x_{6}) = {x_{2}, x_{6}} . \end{matrix}$ $\begin{matrix} n_{A_{1}^{C} \cup A_{1}^{N}}^{t + 1} (x_{1}) & = {x_{1}, x_{5}}, n_{A_{1}^{C} \cup A_{1}^{N}}^{t + 1} (x_{2}) \\ = {x_{2}, x_{4}}, n_{A_{1}^{C} \cup A_{1}^{N}}^{t + 1} (x_{3}) = {x_{3}, x_{6}}, \\ n_{A_{1}^{C} \cup A_{1}^{N}}^{t + 1} (x_{4}) & = {x_{2}, x_{4}}, n_{A_{1}^{C} \cup A_{1}^{N}}^{t + 1} (x_{5}) \\ = {x_{1}, x_{5}}, n_{A_{1}^{C} \cup A_{1}^{N}}^{t + 1} (x_{6}) = {x_{3}, x_{6}} . \end{matrix}$ $\begin{matrix} n_{A_{2}^{C} \cup A_{2}^{N}}^{t + 1} (x_{1}) & = {x_{1}, x_{5}}, n_{A_{2}^{C} \cup A_{2}^{N}}^{t + 1} (x_{2}) \\ = {x_{2}}, n_{A_{2}^{C} \cup A_{2}^{N}}^{t + 1} (x_{3}) = {x_{3}}, \\ n_{A_{2}^{C} \cup A_{2}^{N}}^{t + 1} (x_{4}) & = {x_{4}}, n_{A_{2}^{C} \cup A_{2}^{N}}^{t + 1} (x_{5}) \\ = {x_{1}, x_{5}}, n_{A_{2}^{C} \cup A_{2}^{N}}^{t + 1} (x_{6}) = {x_{6}} . \end{matrix}$

By Definitions 3 and 4 we have $\begin{matrix} {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X) = {x_{2}, x_{3}, x_{4}, x_{6}}, \\ {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) = {x_{2}, x_{6}}, \\ {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X) = {x_{2}, x_{3}, x_{4}, x_{6}}, \\ {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) = U . \\ {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) & - {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) = U - {x_{2}, x_{6}} \\ = {x_{1}, x_{3}, x_{4}, x_{5}} . \end{matrix}$

By Theorem 10 we have $\begin{matrix} {\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X) = {x_{3}, x_{4}}, \\ {\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{P} (X) = {x_{3}, x_{4}}, \\ {\bar{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X) = {x_{1}, x_{5}}, \\ {\bar{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{P} (X) = {x_{1}, x_{5}} . \end{matrix}$ and $\begin{matrix} {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X) = {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X) \cup \\ {\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X) = {x_{2}, x_{3}, x_{4}, x_{6}} \cup {x_{3}, x_{4}} \\ = {x_{2}, x_{3}, x_{4}, x_{6}}, \\ {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X) = {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X) \\ - {\bar{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X) = {x_{2}, x_{3}, x_{4}, x_{6}} - {x_{1}, x_{5}} \\ = {x_{2}, x_{3}, x_{4}, x_{6}}, \\ {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{P} (X) = {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) \cup \\ {\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{P} (X) = {x_{2}, x_{6}} \cup {x_{3}, x_{4}} \\ = {x_{2}, x_{3}, x_{4}, x_{6}}, \\ {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{P} (X) = {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) - {\bar{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{P} (X) \\ = U - {x_{1}, x_{5}} = {x_{2}, x_{3}, x_{4}, x_{6}} . \end{matrix}$

Definition 8. Let NIS^t = (U, AT^t, Δ) be a neighborhood information system at time t, NIS^t+1 = (U, AT^t+1, δ) be a neighborhood information system at time t + 1. For any X ⊆ U, the dynamic lower approximation character sets of X in NMGRS while neighborhood classes decreasing can be defined as: $\begin{matrix} Δ_{A_{k}}^{L} (X) = {x | x \in {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) - {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) \\ \land n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \subseteq X}, \forall k \in {1, 2, \dots, m} . \end{matrix}$

Definition 9. Let IS^t = (U, AT^t, V_{AT
^t}, f^t) be aninformation system at time t, IS^t+1 = (U, AT^t+1,V_{AT
^t+1}, f^t+1) be an information system at time t + 1. For any X ⊆ U, the dynamic upper approximation character sets of X in NMGRS while neighborhood classes decreasing can be defined as: $\begin{matrix} Δ_{A_{k}}^{U} (X) = {x | x \in {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) - {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) \\ \land n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \cap X = \emptyset}, \forall k \in {1, 2, \dots, m} . \end{matrix}$

Theorem 11. Let IS^t = (U, AT^t, V_{AT
^t}, f^t) be aninformation system at time t, IS^t+1 = (U, AT^t+1,V_{AT
^t+1}, f^t+1) be an information system at time t + 1. For any X ⊆ U, the following results hold.

${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) = {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X) \cup (\cup_{k = 1}^{m} Δ_{A_{k}}^{L} (X)),$

${\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) = {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X) - (\cup_{k = 1}^{m} Δ_{A_{k}}^{U} (X)),$

${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X) = {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) \cup (\cap_{k = 1}^{m} Δ_{A_{k}}^{L} (X)),$

${\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X) = {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) - (\cap_{k = 1}^{m} Δ_{A_{k}}^{L} (X)) .$

Proof.

By Theorem 10 and Definition 8 we have ${\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X) = \cup_{k = 1}^{m} Δ_{A_{k}}^{L} (X)$ and ${\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X) = {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X) \cup (\cup_{k = 1}^{m} Δ_{A_{k}}^{L} (X))$ .

By Theorem 10 and Definition 9 we have ${\bar{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X) = \cup_{k = 1}^{m} Δ_{A_{k}}^{U} (X)$ and ${\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X) = {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X) - (\cup_{k = 1}^{m} Δ_{A_{k}}^{L} (X))$ .

It is similar to i.

It is similar to ii.□

Example 5. (Continuation of Example 4) By Definition 8 we have $Δ_{A_{1}}^{L} (X) = {x_{3}, x_{4}}, Δ_{A_{2}}^{L} (X) = {x_{3}, x_{4}}$ .

By Definition 9 we have $Δ_{A_{1}}^{U} (X) = {x_{1}, x_{5}}$ , $Δ_{A_{2}}^{U} (X) = {x_{1}, x_{5}} .$ By Theorem 11 we have

$\begin{matrix} {\underline{\sum_{k = 1}^{2} δ_{A_{k}}^{t + 1}}}^{O} (X) = {\underline{\sum_{k = 1}^{2} Δ_{A_{k}}^{t}}}^{O} (X) \cup (\cup_{k = 1}^{2} Δ_{A_{k}}^{L} (X)) \\ = {x_{2}, x_{3}, x_{4}, x_{6}} \cup {x_{3}, x_{4}} = {x_{2}, x_{3}, x_{4}, x_{6}}, \\ {\underline{\sum_{k = 1}^{2} δ_{A_{k}}^{t + 1}}}^{P} (X) = {\underline{\sum_{k = 1}^{2} Δ_{A_{k}}^{t}}}^{P} (X) \cup (\cap_{k = 1}^{2} Δ_{A_{k}}^{L} (X)) \\ = {x_{2}, x_{6}} \cup {x_{3}, x_{4}} = {x_{2}, x_{3}, x_{4}, x_{6}}, \\ {\bar{\sum_{k = 1}^{2} δ_{A_{k}}^{t + 1}}}^{O} (X) = {\underline{\sum_{k = 1}^{2} Δ_{A_{k}}^{t}}}^{O} (X) - (\cup_{k = 1}^{2} Δ_{A_{k}}^{U} (X)) \\ = {x_{2}, x_{3}, x_{4}, x_{6}} - {x_{1}, x_{5}} = {x_{2}, x_{3}, x_{4}, x_{6}}, \\ {\bar{\sum_{k = 1}^{2} δ_{A_{k}}^{t + 1}}}^{P} (X) = {\underline{\sum_{k = 1}^{2} Δ_{A_{k}}^{t}}}^{O} (X) - (\cap_{k = 1}^{2} Δ_{A_{k}}^{U} (X)) \\ = U - {x_{1}, x_{5}} = {x_{2}, x_{3}, x_{4}, x_{6}} . \end{matrix}$

Corollary 12. Let IS^t = (U, AT^t, V_{AT
^t}, f^t) be an information system at time t, IS^t+1 = (U, AT^t+1, V_{AT
^t+1}, f^t+1) be an information system at time t + 1. For any X ⊆ U, the following results hold.

$V ({\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X)) = V ({\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X)) \lor (\lor_{k = 1}^{m} V (Δ_{A_{k}}^{L} (X)),$

$V ({\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X)) = V ({\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X)) \land \sim (\lor_{k = 1}^{m} V (Δ_{A_{k}}^{U} (X)),$

$V ({\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{P} (X)) = V ({\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X)) \lor (\land_{k = 1}^{m} V (Δ_{A_{k}}^{L} (X)),$

$V ({\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{P} (X)) = V ({\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X)) \land \sim (\land_{k = 1}^{m} V (Δ_{A_{k}}^{L} (X))) .$

Proof. This corollary is the matrix representation of Theorem 11. □

Example 6. (Continuation of Example 5) By Corollary 12 we have $\begin{matrix} V ({\underline{\sum_{k = 1}^{2} δ_{A_{k}}^{t + 1}}}^{O} (X)) = V ({\underline{\sum_{k = 1}^{2} Δ_{A_{k}}^{t}}}^{O} (X)) \lor \\ (\lor_{k = 1}^{2} V (Δ_{A_{k}}^{L} (X))) = [0, 1, 1, 1, 0, 1] \\ \lor [0, 0, 1, 1, 0, 0] = [0, 1, 1, 1, 0, 1], \end{matrix}$

$\begin{matrix} V ({\underline{\sum_{k = 1}^{2} δ_{A_{k}}^{t + 1}}}^{P} (X)) = V ({\underline{\sum_{k = 1}^{2} Δ_{A_{k}}^{t}}}^{P} (X)) \lor \\ (\land_{k = 1}^{2} V (Δ_{A_{k}}^{L} (X))) = [0, 0, 1, 1, 0, 0] \\ \lor [0, 1, 1, 1, 0, 1] = [0, 0, 1, 1, 0, 0], \\ V ({\bar{\sum_{k = 1}^{2} δ_{A_{k}}^{t + 1}}}^{O} (X)) = V ({\underline{\sum_{k = 1}^{2} Δ_{A_{k}}^{t}}}^{O} (X)) \land \sim \\ (\lor_{k = 1}^{2} V (Δ_{A_{k}}^{U} (X))) = [0, 1, 1, 1, 0, 1] \\ \land [0, 1, 1, 1, 0, 1] = [0, 1, 1, 1, 0, 1], \\ V ({\bar{\sum_{k = 1}^{2} δ_{A_{k}}^{t + 1}}}^{P} (X)) = V ({\underline{\sum_{k = 1}^{2} Δ_{A_{k}}^{t}}}^{P} (X)) \land \sim \\ (\land_{k = 1}^{2} V (Δ_{A_{k}}^{U} (X))) = [1, 1, 1, 1, 1, 1] \\ \land [0, 1, 1, 1, 0, 1] = [0, 1, 1, 1, 0, 1] . \end{matrix}$

3.2 Matrix-based approaches for updating approximations while neighborhood classes are increasing

In this subsection, we present matrix-based dynamic approaches for updating approximations in NMGRS while neighborhood classes are increasing. We denote NIS^t = (U, AT^t, δ) a neighborhood information system at time t, NIS^t+1 = (U, AT^t+1, Δ) be a neighborhood information system at time t + 1 where δ and Δ are two nonnegative numbers and δ ≤ Δ. For all $A_{k}^{t} \in {AT}^{t} (k \leq m)$ , there exists $A_{k}^{t + 1} \in {AT}^{t + 1}$ , such that $(A_{k}^{C})^{t + 1} \subseteq (A_{k}^{C})^{t}$ and $(A_{k}^{N})^{t + 1} \subseteq (A_{k}^{N})^{t}$ . Also, for all x ∈ U, we denote neighborhood class of x at time t by $n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x)$ . Denote neighborhood class of x at time t + 1 by $n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x)$ . Denote approximations in PNMGRS by ${\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{P} (X)$ and ${\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{P} (X)$ at time t. Denote approximations in PNMGRS by ${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X)$ and ${\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X)$ at time t + 1. Denote approximations in ONMGRS by ${\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)$ and ${\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)$ at time t. Denote approximation in ONMGRS by ${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X)$ and ${\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X)$ at time t + 1.

Theorem 13. Let NIS^t = (U, AT^t, δ) be a neighborhood information system at time t, NIS^t+1 = (U, AT^t+1, Δ) be a neighborhood information system at time t + 1. For any X ⊆ U, the following result holds. $n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \supseteq n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x)$

Proof.

If $(A_{k}^{C})^{t + 1} \subseteq (A_{k}^{C})^{t}$ , we have $n_{A_{k}^{C}}^{t} (x) \supseteq n_{A_{k}^{C}}^{t + 1} (x) \Rightarrow n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \supseteq n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x)$ ;

If $(A_{k}^{N})^{t + 1} \subseteq (A_{k}^{N})^{t}$ , we have $n_{A_{k}^{N}}^{t} (x) \supseteq n_{A_{k}^{N}}^{t + 1} (x) \Rightarrow n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \supseteq n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x)$ ;

If δ ≤ Δ, we have that $n_{A_{k}^{C}}^{t} (x) \subseteq n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x)$ .□

Theorem 14. Let NIS^t = (U, AT^t, δ) be a neighborhood information system at time t, NIS^t+1 = (U, AT^t+1, Δ) be a neighborhood information system at time t + 1. For any X ⊆ U, the following results hold. $(1) {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \supseteq {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X);$ $(2) {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \subseteq {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) .$

Proof. (1) $\forall x \in {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X), x \in {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) \Rightarrow \exists k \in {1, 2, \dots, m},$ $n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \subseteq X \Rightarrow \exists k \in {1, 2, \dots, m}, n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x) \subseteq X \Rightarrow x \in {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)$ , we have that ${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) \subseteq {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X);$ (2) $\forall x \in {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X), x \in {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \Rightarrow \forall k \in {1, 2, \dots, m},$ $n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x) \cap X \neq \emptyset \Rightarrow \forall k \in {1, 2, \dots, m}, n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \cap X \neq \emptyset \Rightarrow x \in {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X)$ , we have that ${\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \subseteq {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X);$ □

Theorem 15. Let NIS^t = (U, AT^t, δ) be a neighborhood information system at time t, NIS^t+1 = (U, AT^t+1, Δ) be a neighborhood information system at time t + 1. For any X ⊆ U, the following results hold. $(1) {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{P} (X) \supseteq {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X);$ $(2) {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{P} (X) \subseteq {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X) .$

Proof. It is similar to that of Theorem 14. □

Theorems 14 and 15 indicate the relations among lower and upper approximations in NMGRS between time t and time t + 1. However, they are not clear enough for updating approximations in NMGRS. The following theorem provides accurate approaches for updating approximations in NMGRS from time t to t + 1 while neighborhood classes increasing.

Theorem 16. Let NIS^t = (U, AT^t, δ) be a neighborhood information system at time t, NIS^t+1 = (U, AT^t+1, Δ) be a neighborhood information system at time t + 1. For any X ⊆ U, we have

if ${\underline{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X) = {x | \forall k \in {1, 2, \dots,$ $m}, n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) X, x \in {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \cup (U - {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)}$ , then ${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) = {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) - {\underline{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X) .$

if ${\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X) = {x | \forall k \in {1, 2, \dots,$ $m}, n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \cap X \neq \emptyset, x \in {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \cup (U - {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)}$ , then ${\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) = {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \cup {\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X) .$

if ${\underline{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{P} (X) = {x | \exists k \in {1, 2, \dots,$ $m}, n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) X, x \in {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \cup (U - {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)}$ , then ${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X) = {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{P} (X) - {\underline{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{P} (X) .$

if ${\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{P} (X) = {x | \exists k \in {1, 2, \dots,$ $m}, n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \cap X \neq \emptyset, x \in {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \cup (U - {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)}$ , then ${\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X) = {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{P} (X) \cup {\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{P} (X) .$

Proof.

“⇒”: Since we have ${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) \subseteq$ ${\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X),$ and ${\underline{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X) \cap {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) = \emptyset,$ we have ${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O}$ $(X) \subseteq {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) - {\underline{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X) .$ “⇐”: $\forall x \notin {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)$ , $x \notin {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O}$ $(X) \Rightarrow n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x) X \Rightarrow n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) X \Rightarrow$ $x \notin {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) \land x \in {\underline{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X)$ ,we have that ${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) - {\underline{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X) \subseteq {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) .$ This completes the proof.

“⇒”: $\forall x \in {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X)$ , $x \in {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) \Rightarrow \forall k \in {1, 2, \dots, m}, n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \cap X \neq \emptyset \Rightarrow$ $\forall k \in {1, 2, \dots, m}, n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x) \cap X \neq \emptyset \Rightarrow x \in {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \lor x \in {\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X)$ , we have ${\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X) \subseteq {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \cup {\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X) .$ “⇐”: $\forall x \notin {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X), x \notin {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) \Rightarrow \exists k \in {1, 2, \dots, m}, n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \cap X = \emptyset \Rightarrow$ $\exists k \in {1, 2, \dots, m}, n_{A_{k}^{C} \cup A_{k}^{N}}^{t} (x) \cap X = \emptyset \Rightarrow x \notin {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \land x \notin {\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X)$ , thus we have ${\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \cup {\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X) \subseteq {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) .$ This completes the proof.

It is similar to i.

It is similar to ii.□

Example 7. (Continuation of Example 1) Supposed ${AT}^{t} = {A_{1}^{t}, A_{2}^{t}}, A_{1}^{t} = (A_{1}^{C})^{t} \cup (A_{1}^{N})^{t}$ , $(A_{1}^{C})^{t}$ = {a₁, a₂} and $(A_{1}^{N})^{t} = \emptyset$ , $A_{2}^{t} = (A_{2}^{C})^{t} \cup (A_{2}^{N})^{t}$ , $(A_{2}^{C})^{t} = \emptyset$ and $(A_{2}^{N})^{t} = {a_{3}, a_{4}}$ , ${AT}^{t + 1} = {A_{1}^{t + 1}, A_{2}^{t + 1}}, A_{1}^{t + 1} = (A_{1}^{C})^{t + 1} \cup (A_{1}^{N})^{t + 1}$ , $(A_{1}^{C})^{t + 1}$ = {a₂} and $(A_{1}^{N})^{t + 1} = \emptyset$ , $A_{2}^{t + 1} = (A_{2}^{C})^{t + 1} \cup (A_{2}^{N})^{t + 1}$ , $(A_{2}^{C})^{t + 1} = \emptyset$ and $(A_{2}^{N})^{t + 1} = {a_{4}}$ . Let X = {x₂, x₃, x₄, x₆} and δ = 0.5, Δ = 0.5.

By Definition 1 we have $\begin{matrix} n_{A_{1}^{C} \cup A_{1}^{N}}^{t} (x_{1}) = {x_{1}}, n_{A_{1}^{C} \cup A_{1}^{N}}^{t} (x_{2}) = {x_{2}}, \\ n_{A_{1}^{C} \cup A_{1}^{N}}^{t} (x_{3}) = {x_{3}}, \\ n_{A_{1}^{C} \cup A_{1}^{N}}^{t} (x_{4}) = {x_{4}}, n_{A_{1}^{C} \cup A_{1}^{N}}^{t} (x_{5}) = {x_{5}}, \\ n_{A_{1}^{C} \cup A_{1}^{N}}^{t} (x_{6}) = {x_{6}} . \end{matrix}$

$\begin{matrix} n_{A_{2}^{C} \cup A_{2}^{N}}^{t} (x_{1}) = {x_{1}, x_{4}, x_{5}}, n_{A_{2}^{C} \cup A_{2}^{N}}^{t} (x_{2}) = {x_{2}}, \\ n_{A_{2}^{C} \cup A_{2}^{N}}^{t} (x_{3}) = {x_{3}}, n_{A_{2}^{C} \cup A_{2}^{N}}^{t} (x_{4}) = {x_{1}, x_{4}}, \\ n_{A_{2}^{C} \cup A_{2}^{N}}^{t} (x_{5}) = {x_{1}, x_{5}}, n_{A_{2}^{C} \cup A_{2}^{N}}^{t} (x_{6}) = {x_{6}} . \end{matrix}$ $\begin{matrix} n_{A_{1}^{C} \cup A_{1}^{N}}^{t + 1} (x_{1}) = {x_{1}, x_{4}}, n_{A_{1}^{C} \cup A_{1}^{N}}^{t + 1} (x_{2}) = {x_{2}, x_{6}}, \\ n_{A_{1}^{C} \cup A_{1}^{N}}^{t + 1} (x_{3}) = {x_{3}, x_{5}}, n_{A_{1}^{C} \cup A_{1}^{N}}^{t + 1} (x_{4}) = {x_{1}, x_{4}}, \\ n_{A_{1}^{C} \cup A_{1}^{N}}^{t + 1} (x_{5}) = {x_{3}, x_{5}}, n_{A_{1}^{C} \cup A_{1}^{N}}^{t + 1} (x_{6}) = {x_{2}, x_{6}} . \end{matrix}$ $\begin{matrix} n_{A_{2}^{C} \cup A_{2}^{N}}^{t + 1} (x_{1}) = {x_{1}, x_{2}, x_{4}, x_{5}}, n_{A_{2}^{C} \cup A_{2}^{N}}^{t + 1} (x_{2}) \\ = {x_{1}, x_{2}, x_{4}, x_{5}}, n_{A_{2}^{C} \cup A_{2}^{N}}^{t + 1} (x_{3}) = {x_{3}, x_{6}}, \\ n_{A_{2}^{C} \cup A_{2}^{N}}^{t + 1} (x_{4}) = {x_{1}, x_{2}, x_{4}, x_{5}}, n_{A_{2}^{C} \cup A_{2}^{N}}^{t + 1} (x_{5}) \\ = {x_{1}, x_{2}, x_{4}, x_{5}}, n_{A_{2}^{C} \cup A_{2}^{N}}^{t + 1} (x_{6}) = {x_{3}, x_{6}} . \end{matrix}$

By Definitions 3 and 4 we have $\begin{matrix} {\underline{\sum_{k = 1}^{2} δ_{A_{k}}^{t}}}^{O} (X) = {x_{2}, x_{3}, x_{4}, x_{6}}, \\ {\underline{\sum_{k = 1}^{2} δ_{A_{k}}^{t}}}^{P} (X) = {x_{2}, x_{3}, x_{6}}, \\ {\bar{\sum_{k = 1}^{2} δ_{A_{k}}^{t}}}^{O} (X) = {x_{2}, x_{3}, x_{4}, x_{6}}, \\ {\bar{\sum_{k = 1}^{2} δ_{A_{k}}^{t}}}^{P} (X) = U . \end{matrix}$ $\begin{matrix} {\bar{\sum_{k = 1}^{2} δ_{A_{k}}^{t}}}^{O} (X) \cup (U - {\underline{\sum_{k = 1}^{2} δ_{A_{k}}^{t}}}^{O} (X)) \\ = {x_{2}, x_{3}, x_{4}, x_{6}} \cup (U - {x_{2}, x_{3}, x_{4}, x_{6}} = U . \end{matrix}$

By Theorem 10 we have $\begin{matrix} {\underline{Δ \sum_{k = 1}^{2} δ_{A_{k}}}}^{O} (X) = {x_{1}, x_{4}, x_{5}}, \end{matrix}$

$\begin{matrix} {\underline{Δ \sum_{k = 1}^{2} δ_{A_{k}}}}^{P} (X) = {x_{1}, x_{2}, x_{3}, x_{4}, x_{5}}, \\ {\bar{Δ \sum_{k = 1}^{2} δ_{A_{k}}}}^{O} (X) = U, {\bar{Δ \sum_{k = 1}^{2} δ_{A_{k}}}}^{P} (X) = U . \end{matrix}$ and $\begin{matrix} {\underline{\sum_{k = 1}^{2} Δ_{A_{k}}^{t + 1}}}^{O} (X) = {\underline{\sum_{k = 1}^{2} δ_{A_{k}}^{t}}}^{O} (X) - {\underline{Δ \sum_{k = 1}^{2} δ_{A_{k}}}}^{O} (X) \\ = {x_{2}, x_{3}, x_{4}, x_{6}} - {x_{1}, x_{4}, x_{5}} = {x_{2}, x_{3}, x_{6}}, \\ {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) = {\bar{\sum_{k = 1}^{2} δ_{A_{k}}^{t}}}^{O} (X) \cup {\bar{Δ \sum_{k = 1}^{2} δ_{A_{k}}}}^{O} (X) \\ = {x_{2}, x_{3}, x_{4}, x_{6}} \cup U = U, \\ {\underline{\sum_{k = 1}^{2} Δ_{A_{k}}^{t + 1}}}^{P} (X) = {\underline{\sum_{k = 1}^{2} δ_{A_{k}}^{t}}}^{P} (X) - {\underline{Δ \sum_{k = 1}^{2} δ_{A_{k}}}}^{P} (X) \\ = {x_{2}, x_{3}, x_{6}} - {x_{1}, x_{2}, x_{3}, x_{4}, x_{5}} = {x_{6}}, \\ {\bar{\sum_{k = 1}^{2} Δ_{A_{k}}^{t + 1}}}^{P} (X) = {\bar{\sum_{k = 1}^{2} δ_{A_{k}}^{t}}}^{P} (X) \cup {\bar{Δ \sum_{k = 1}^{2} δ_{A_{k}}}}^{P} (X) \\ = U \cup U = U . \end{matrix}$

Definition 10. Let NIS^t = (U, AT^t, Δ) be a neighborhood information system at time t, NIS^t+1 = (U, AT^t+1, δ) be a neighborhood information system at time t + 1. For any X ⊆ U, the dynamic lower approximation character set of X in NMGRS while neighborhood classes increasing can be defined as: $\begin{matrix} δ_{A_{k}}^{L} (X) = {x | x \in {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \cup (U - {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)) \\ \land n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) X}, \forall k \in {1, 2, \dots, m} . \end{matrix}$

Definition 11. Let IS^t = (U, AT^t, V_{AT
^t}, f^t) be an information system at time t, IS^t+1 = (U, AT^t+1, V_{AT
^t+1}, f^t+1) be an information system at time t + 1. For any X ⊆ U, the dynamic upper approximation character set of X in NMGRS while neighborhood classes increasing can be defined as:

$\begin{matrix} δ_{A_{k}}^{U} (X) = {x | x \in {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \cup (U - {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)) \\ \land n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x) \cap X \neq \emptyset}, \forall k \in {1, 2, \dots, m} . \end{matrix}$

Theorem 17. Let NIS^t = (U, AT^t, δ) be a neighborhood information system at time t, NIS^t+1 = (U, AT^t+1, Δ) be a neighborhood information system at time t + 1. For any X ⊆ U, the following results hold.

${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) = {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) - (\cap_{k = 1}^{m} δ_{A_{k}}^{L} (X)),$

${\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) = {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \cup (\cap_{k = 1}^{m} δ_{A_{k}}^{U} (X)),$

${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X) = {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{P} (X) - (\cup_{k = 1}^{m} δ_{A_{k}}^{L} (X)),$

${\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X) = {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{P} (X) \cup (\cup_{k = 1}^{m} δ_{A_{k}}^{L} (X)) .$

Proof.

By Theorem 16 and Definition 10 we have that ${\underline{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X) = \cap_{k = 1}^{m} δ_{A_{k}}^{L} (X)$ and ${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) = {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) - (\cap_{k = 1}^{m} δ_{A_{k}}^{L} (X))$ .

By Theorem 16 and Definition 11 we have that ${\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X) = \cap_{k = 1}^{m} δ_{A_{k}}^{U} (X)$ and ${\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X) = {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \cup (\cap_{k = 1}^{m} δ_{A_{k}}^{U} (X))$ .

It is similar to i.

It is similar to ii.□

Example 8. (Continuation of Example 7) By Definition 10 we have $δ_{A_{1}}^{L} (X) = {x_{1}, x_{3}, x_{4}, x_{5}}, δ_{A_{2}}^{L} (X) = {x_{1}, x_{2}, x_{4}, x_{5}} .$

By Definition 11 we have $δ_{A_{1}}^{U} (X) = U, δ_{A_{2}}^{U} (X) = U .$ By Theorem 17 we have

$\begin{matrix} {\underline{\sum_{k = 1}^{2} Δ_{A_{k}}^{t + 1}}}^{O} (X) = {\underline{\sum_{k = 1}^{2} δ_{A_{k}}^{t}}}^{O} (X) - (\cap_{k = 1}^{2} δ_{A_{k}}^{L} (X)) \\ = {x_{2}, x_{3}, x_{4}, x_{6}} - {x_{1}, x_{4}, x_{5}} = {x_{2}, x_{3}, x_{6}}, \\ {\underline{\sum_{k = 1}^{2} Δ_{A_{k}}^{t + 1}}}^{P} (X) = {\underline{\sum_{k = 1}^{2} δ_{A_{k}}^{t}}}^{P} (X) - (\cup_{k = 1}^{2} δ_{A_{k}}^{L} (X)) \\ = {x_{2}, x_{3}, x_{6}} - {x_{1}, x_{2}, x_{3}, x_{4}, x_{5}} = {x_{6}}, \\ {\bar{\sum_{k = 1}^{2} Δ_{A_{k}}^{t + 1}}}^{O} (X) = {\underline{\sum_{k = 1}^{2} δ_{A_{k}}^{t}}}^{O} (X) \cup (\cap_{k = 1}^{2} δ_{A_{k}}^{U} (X)) \\ = {x_{2}, x_{3}, x_{4}, x_{6}} \cup U = U, \\ {\bar{\sum_{k = 1}^{2} Δ_{A_{k}}^{t + 1}}}^{P} (X) = {\underline{\sum_{k = 1}^{2} δ_{A_{k}}^{t}}}^{O} (X) \cup (\cup_{k = 1}^{2} δ_{A_{k}}^{U} (X)) \\ = U \cup U = U . \end{matrix}$

Corollary 18. Let NIS^t = (U, AT^t, δ) be a neighborhood information system at time t, NIS^t+1 = (U, AT^t+1, Δ) be a neighborhood information system at time t + 1. For any X ⊆ U, the following results hold.

$V ({\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X)) = V ({\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)) \land \sim (\land_{k = 1}^{m} V (δ_{A_{k}}^{L} (X))),$

$V ({\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X)) = V ({\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)) \lor (\land_{k = 1}^{m} V (δ_{A_{k}}^{U} (X))),$

$V ({\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X)) = V ({\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{P} (X)) \land \sim (\lor_{k = 1}^{m} V (δ_{A_{k}}^{L} (X))),$

$V ({\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X)) = V ({\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{P} (X)) \lor (\lor_{k = 1}^{m} V (δ_{A_{k}}^{L} (X))) .$

Proof. This theorem is the matrix representation of Theorem 17. □

Example 9. (Continuation of Example 8) By Corollary 18 we have $\begin{matrix} V ({\underline{\sum_{k = 1}^{2} Δ_{A_{k}}^{t + 1}}}^{O} (X)) = V ({\underline{\sum_{k = 1}^{2} δ_{A_{k}}^{t}}}^{O} (X)) \land \\ \sim (\land_{k = 1}^{2} V (δ_{A_{k}}^{L} (X))) = [0, 1, 1, 1, 0, 1] \\ \land [0, 1, 1, 0, 0, 1] = [0, 1, 1, 0, 0, 1], \end{matrix}$

$\begin{matrix} V ({\underline{\sum_{k = 1}^{2} Δ_{A_{k}}^{t + 1}}}^{P} (X)) = V ({\underline{\sum_{k = 1}^{2} δ_{A_{k}}^{t}}}^{P} (X)) \land \\ \sim (\lor_{k = 1}^{2} V (δ_{A_{k}}^{L} (X))) = [0, 1, 1, 0, 0, 1] \\ \land [0, 0, 0, 0, 0, 1] = [0, 0, 0, 0, 0, 1], \\ V ({\bar{\sum_{k = 1}^{2} Δ_{A_{k}}^{t + 1}}}^{O} (X)) = V ({\underline{\sum_{k = 1}^{2} δ_{A_{k}}^{t}}}^{O} (X)) \\ \lor (\land_{k = 1}^{2} V (δ_{A_{k}}^{U} (X))) = [0, 1, 1, 1, 0, 1] \\ \lor [1, 1, 1, 1, 1, 1] = [1, 1, 1, 1, 1, 1], \\ V ({\bar{\sum_{k = 1}^{2} Δ_{A_{k}}^{t + 1}}}^{P} (X)) = V ({\underline{\sum_{k = 1}^{2} δ_{A_{k}}^{t}}}^{O} (X)) \\ \lor (\lor_{k = 1}^{2} V (δ_{A_{k}}^{U} (X))) = [1, 1, 1, 1, 1, 1] \\ \lor [1, 1, 1, 1, 1, 1] = [1, 1, 1, 1, 1, 1] . \end{matrix}$

4 Matrix-based dynamic algorithms for updating approximations while neighborhood classes increasing or decreasing

Based on Corollary 12, we proposed a matrix-based Algorithm 2 for updating approximations in NMGRS while neighborhood classes are decreasing. The total time complexity of Algorithm 2 is $O (| {AT}^{t} | | {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) - {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) | | U |) .$ Steps 3–12 are to calculate $Δ_{A_{k}}^{L}$ and $Δ_{A_{k}}^{U}$ (k ∈ {1, 2, ⋯ , m}) with time complexity $O (| {AT}^{t} | | {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) - {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) | | U |)$ . Steps 17–22 are to compute $Δ {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X)$ , $Δ {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X)$ , $Δ {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X)$ and $Δ {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X)$ with time complexity O (|AT^t||U|). Steps 24-27 are to update the approximations in NMGRS while neighborhood classes are decreasing with time complexity O (|U|).

Algorithm 2
Matrix-based algorithm for updating approximations in NMGRS while neighborhood classes decreasing

Require: (1)NIS^t = (U, AT^t, Δ). (2)NIS^t+1 = (U, AT^t+1, δ). (3)A target concept X ⊆ U. (4) ${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X)$ ,

${\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X)$ , ${\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X)$ and ${\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X)$ . (5)neighborhood classes $n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x), \forall x \in U, \forall k \in {1, 2, \dots, m}$ .

Ensure: ${\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X)$ , ${\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X)$ , ${\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{P} (X)$ and ${\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{P} (X)$ .

1: m ← |AT^t|

2: n ← |U|

3: fork = 1 → mdo

4: fori = 1 → ndo

5: if $v_{i} ({\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) - {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X)) = 1 \land V (n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x_{i})) \cdot V^{T} (\sim (X)) = 0$ then

6: $v_{i} (Δ_{A_{k}}^{L} (X)) = 1$

7: end if

8: if $v_{i} ({\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) - {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X)) = 1 \land V (n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x_{i})) \cdot V^{T} (X) = 0$ then

9: $v_{i} (Δ_{A_{k}}^{U} (X)) = 1$

10: end if

11: end for

12: end for

13: $V ({\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X)) \leftarrow V (Δ_{A_{1}}^{L} (X))$

14: $V ({\bar{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X)) \leftarrow V (Δ_{A_{1}}^{U} (X))$

15: $V ({\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{P} (X)) \leftarrow V (Δ_{A_{1}}^{L} (X))$

16: $V ({\bar{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{P} (X)) \leftarrow V (Δ_{A_{1}}^{U} (X))$

17: fork = 2 → m

18: $V ({\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X)) \leftarrow V ({\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X)) \lor V (Δ_{A_{k}}^{L} (X))$

19: $V ({\bar{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X)) \leftarrow V ({\bar{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X) \lor V (Δ_{A_{k}}^{U} (X))$

20: $V ({\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{P} (X)) \leftarrow V ({\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{P} (X)) \land V (Δ_{A_{k}}^{L} (X))$

21: $V ({\bar{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{P} (X)) \leftarrow V ({\bar{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{P} (X)) \land V (Δ_{A_{k}}^{U} (X))$

22: end for

23:

24: $V ({\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X)) \leftarrow V ({\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X)) \lor V ({\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X))$

25: $V ({\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X)) \leftarrow V ({\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X)) \land \sim V ({\bar{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{O} (X))$

26: $V ({\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{P} (X)) \leftarrow V ({\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X)) \lor V ({\underline{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{P} (X))$

27: $V ({\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{P} (X)) \leftarrow V ({\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X)) \land \sim V ({\bar{Δ \sum_{k = 1}^{m} Δ_{A_{k}}}}^{P} (X))$

28: Return ${\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X), {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X)$ , ${\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{P} (X)$ and ${\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{P} (X)$ .

Since the time complexity of Algorithm 1 is O (|AT^t||X||U|), and in general, $O (| {AT}^{t} | | {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) - {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) | | U |) \leq O (| {AT}^{t} | | X | | U |)$ does not hold, so Algorithm 3 is proposed to make sure the total time complexity is no more than O (|AT^t||X||U|). In other words, when $| {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) - {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) | > | X |,$ we call Algorithm 1, otherwise, we call Algorithm 2.

Algorithm 3

Ensure total time complexity of updating approximations in NMGRS while decreasing neighborhood classes no more than O (|AT^t||X||U|)

1: Require (1)NIS^t = (U, AT^t, Δ). (2)NIS^t+1 = (U, AT^t+1, δ). (3)A target concept X ⊆ U. (4)

{\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X)

{\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{O} (X)

{\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X)

and

{\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X)

.(4)neighborhood classes

n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x), \forall x \in U, \forall k \in {1, 2, \dots, m}

Ensure:

{\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X)

{\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X)

{\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X)

and

{\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X)

2: if

| {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) - {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) | \leq | X |

Call Algorithm 2

3: end if

4: if

| {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) - {\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t}}}^{P} (X) | > | X |

Call Algorithm 1

5: end if

6: Return

{\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X), {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X)

{\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{P} (X)

and

{\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{P} (X)

Based on Corollary 18, we proposed a matrix-based Algorithm 4 for updating approximations in NMGRS while neighborhood classes are increasing. The total time complexity of Algorithm 2 is $O (| {AT}^{t} | | {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X) \cup (U - {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X)) | | U |)$ . Steps 3-12 are to calculate $δ_{A_{k}}^{L}$ and $δ_{A_{k}}^{U}$ (k∈ { 1, 2, ⋯ , m }) with time complexity $O (| {AT}^{t} | | {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X) \cup (U - {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X)) | | U |)$ . Steps 17-22 are to compute ${\underline{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X)$ , ${\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X), {\underline{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{P} (X)$ and ${\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{P} (X)$ with time complexity O (|AT^t||U|). Steps 24-27 are to update the approximations in NMGRS while neighborhood classes are increasing with time complexity O (|U|).

Algorithm 4

Matrix-based algorithm for updating approximations in NMGRS while neighborhood classes increasing

Require: (1)NIS^t = (U, AT^t, δ)(2)NIS^t+1 = (U, AT^t+1, Δ). (3)A target concept X ⊆ U (4)

{\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)

{\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)

{\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{P} (X)

and

{\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{P} (X)

. (5)neighborhood classes

n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x), \forall x \in U, \forall k \in {1, 2, \dots, m}

Ensure:

{\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X)

{\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X)

{\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X)

and

{\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X)

1: m ← |AT^t|

2: n ← |U|

3: fork = 1 → mdo

4: fori = 1 → ndo

5: if

v_{i} ({\underline{\sum_{k = 1}^{m} A_{k}^{t}}}^{O} (X) \cup (U - {\bar{\sum_{k = 1}^{m} A_{k}^{t}}}^{O} (X))) = 1 \land V (n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x_{i})) \cdot V^{T} (\sim (X)) > 0

then

v_{i} (δ_{A_{k}}^{L} (X)) = 1

7: end if

8: if

v_{i} ({\underline{\sum_{k = 1}^{m} A_{k}^{t}}}^{O} (X) \cup (U - {\bar{\sum_{k = 1}^{m} A_{k}^{t}}}^{O} (X))) = 1 \land V (n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x_{i})) \cdot V^{T} (X) > 0

then

v_{i} (δ_{A_{k}}^{U} (X)) = 1

10: end if

11: end for

12: end for

13:

V ({\underline{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X)) \leftarrow V (δ_{A_{1}}^{L} (X))

14:

V ({\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X)) \leftarrow V (δ_{A_{1}}^{U} (X))

15:

V ({\underline{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{P} (X)) \leftarrow V (δ_{A_{1}}^{L} (X))

16:

V ({\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{P} (X)) \leftarrow V (δ_{A_{1}}^{U} (X))

17: fork = 2 → m

18:

V ({\underline{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X)) \leftarrow V ({\underline{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X)) \land V (δ_{A_{k}}^{L} (X))

19:

V ({\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X)) \leftarrow V ({\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X) \lor V (δ_{A_{k}}^{U} (X))

20:

V ({\underline{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{P} (X)) \leftarrow V ({\underline{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{P} (X)) \lor V (δ_{A_{k}}^{L} (X))

21:

V ({\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{P} (X)) \leftarrow V ({\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{P} (X)) \land V (δ_{A_{k}}^{U} (X))

22: end for

23:

24:

V ({\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X)) \leftarrow V ({\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)) \land \sim V ({\underline{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X))

25:

V ({\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X)) \leftarrow V ({\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)) \lor V ({\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{O} (X))

26:

V ({\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X)) \leftarrow V ({\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{P} (X)) \land \sim V ({\underline{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{P} (X))

27:

V ({\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X)) \leftarrow V ({\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{P} (X)) \lor V ({\bar{Δ \sum_{k = 1}^{m} δ_{A_{k}}}}^{P} (X))

28: Return

{\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X), {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X)

{\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X)

and

{\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X)

Since the time complexity of Algorithm 1is O (|AT^t||X||U|), and in general, O (|AT^t|| ${\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X) \cup (U - {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X)) | | U |) \leq O (| {AT}^{t} | | X | | U |)$ does not hold, Algorithm 5 was proposed to make sure the total time complexity is no more than O (|AT^t||X||U|), in other words, when $| {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X) \cup (U - {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t + 1}}}^{O} (X)) | > | X |,$ we call Algorithm 1, otherwise, we call Algorithm 4.

Algorithm 5

Ensure total time complexity of updating approximations in NMGRS while increasing neighborhood classes no more than O (|AT^t||X||U|)

1: Require (1)NIS^t = (U, AT^t, δ)(2)NIS^t+1 = (U, AT^t+1, Δ)(3)A target concept X ⊆ U (4)

{\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)

{\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)

{\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{P} (X)

and

{\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{P} (X)

.(4)neighborhood classes

n_{A_{k}^{C} \cup A_{k}^{N}}^{t + 1} (x), \forall x \in U, \forall k \in {1, 2, \dots, m}

Ensure:

{\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X)

{\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X)

{\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X)

and

{\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X)

2: if

| {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \cup (U - {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)) | > | X |

then Call Algorithm 2

3: end if

4: if

| {\underline{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X) \cup (U - {\bar{\sum_{k = 1}^{m} δ_{A_{k}}^{t}}}^{O} (X)) | \leq | X |

then Call Algorithm 1

5: end if

6: Return

{\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X), {\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{O} (X)

{\underline{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X)

and

{\bar{\sum_{k = 1}^{m} Δ_{A_{k}}^{t + 1}}}^{P} (X)

5 Experimental evaluations

In this section, several experiments were conducted to evaluate the effectiveness and the efficiency of the algorithms we proposed, namely Algorithm 1(MB), Algorithm 3(DMB) and Algorithm 5(DMB). We chose four algorithms to compare, namely, set operation based static algorithm(SOB) [37], set operation based dynamic algorithm(DSOB) [37], relation matrix based static algorithm(RMB) [6] and relation matrix based dynamic algorithm(DRMB) [6]. Six data sets were chosen from UCI machine learning repository. The details of these data sets are listed in Table 2. All the experiments were carried out on a personal computer with 64-bit windows 10, Inter(R) Core(TM) i7 6700HQ CPU @2.60GHz, and 16GB memory. The program language was Matlab r2015b.

Table 2
Details of data sets

No. Data sets Samples Attributes

1 Cylinder Bands Data Set 541 40

2 Dermatology 366 20

3 Flags 194 30

4 LasVegas Trip Advisor Reviews Data set 504 20

5 Soybean Large 307 36

6 Student 396 33

No.	Data sets	Samples	Attributes
1	Cylinder Bands Data Set	541	40
2	Dermatology	366	20
3	Flags	194	30
4	LasVegas Trip Advisor Reviews Data set	504	20
5	Soybean Large	307	36
6	Student	396	33

5.1 Comparison of computational time using date sets with different size

The computational time are compared among MB,DMB,SOB,DSOB,RMB and DRMB when the size of data sets increases. With neighborhood classes decreasing or increasing. First of all, we randomly chose the categorical and numerical attributes $\hat{a_{C}}$ and $\hat{a_{N}}$ in the data set and randomly divided the rest of the categorical and numerical attributes into three parts randomly to contribute to three granular structures respectively. While neighborhood classes decrease, we added the categorical and numerical attributes $\hat{a_{C}}$ and $\hat{a_{N}}$ into the three granular structures at the same time. While neighborhood classes increase, we combined the categorical and numerical attributes $\hat{a_{C}}$ and $\hat{a_{N}}$ with each granular structure and deleted the categorical and numerical attributes $\hat{a_{C}}$ and $\hat{a_{N}}$ from the three granular structures at the same time. We randomly divided every data set U into ten subsets which is denoted by {U₁, U₂, ⋯ , U₁₀ }. Then U₁ was chosen as the first temporary data set. After that, some samples of the temporary data set were randomly selected to contribute to the target concept X. The size of the target concept X was about 0.95 times the size of each temporary data set. We calculated the four approximations in NMGRS using MB,DMB,SOB,DSOB,RMB and DRMB ten times and compared the averages. Then we made U₁ ∪ U₂ the second temporary data set and repeat the whole process.

When the size of data sets increases gradually, results of the six algorithms while neighborhood classes increasing or decreasing in NMGRS are shown in Figs. 1 and 2. We can see that DMB is the most efficient algorithm when the size of data set increases gradually. From Fig. 1 we can see that DMB is effective and it reduces the computational time.

Fig.1

Comparison of Algorithm 3 when the size of U increase gradually.

Fig.2

Comparison of Algorithm 5 when the size of U increase gradually.

5.2 Comparison of computational time using target concepts with different size

Similarly, instead of construct temporary data sets in Section 5.1, we construct temporary target concepts. The process of constructing and varying the three granular structures is similar to Section 5.1. We randomly divided each data set into ten subsets {X₁, X₂, ⋯ , X₁₀ }. And then X₁ was chosen as the first temporary target concept. Finally, we calculated the four approximations in MGRS by the the four algorithms ten times and compared the averages. Then we made X₁ ∪ X₂ the second temporary target concept and the whole process was repeated.

When the size of target concept increases gradually, results of MB, DMB, SOB, DSOB, RMB and DRMB are shown in Figs. 3 and 4. When the size of target concept increases gradually, RMB is always the most time consuming algorithm among the six algorithms. DMB and MB are more efficient than SOB,DSOB,RMB and DRMB. The computational time of DMB is always less than or equal to MB, so DMB is more efficient than any other algorithms among all the 6 algorithms considered. Sometimes the computational time of DMB is a little more than the MB while neighborhood classed decreasing, which is due to additional computation in DMB and it is within the expected range.

Fig.3

Comparison of Algorithm 3 when the size of X increase gradually.

Fig.4

Comparison of Algorithm 5 when the size of X increase gradually.

6 Conclusion

Data sets in real life applications sometimes are complex and huge. The granular structures often increase and decrease in some data sets. Sometimes it is difficult to handle. Therefore it is important to design algorithms to update approximations in NMGRS while neighborhood classes decreasing or increasing. In this paper, four algorithms have been proposed to ensure that the time complexity of the incremental algorithm is less than or equal to the static algorithm. Experimental results showed that the computational time of the incremental algorithms is no more than the static algorithm in most of the situations considered here.

We have examined the advantage and disadvantage of our proposed methods by experimental evaluation. The theoretical time complexity of DMB is more efficient than the other algorithms. However, the disadvantage of DMB and MB is also obvious: when the average size of granules is too small, the time complexity of matrix production is |U| and the time complexity of set operation is far less than |U|, which makes the algorithms based on the two approaches hard to compare. In the worst situation, DMB is more efficient than SOB and DSOB.

Approximation computation is a basic process of attribute reduction. In the future, we will further investigate attribute reduction algorithms using the approaches we proposed.

Footnotes

Acknowledgement

This work is supported by National Natural Science Foundation of China (No.11871259), National Natural Science Foundation of China (No.61379021), National Youth Science Foundation of China (No.61603173), the Natural Science Foundation of Fujian Province of China(No.2019J01748).

References

Anton

, Elementary linear algebra, Elementary Linear Algebra 50(1944) (1989), 129166.

Cai

and Guangming

, Incremental approaches to updating attribute reducts when refining and coarsening coverings Information Theory, arXiv, 2018.

Chen

, Li

, Luo

, Horng

and Wang

, A rough set-based method for updating decision rules on attribute values coarsening and refining, IEEE Transactions on Knowledge and Data Engineering 26(12) (2014), 2886–2899.

Cheng

, Research on Covering Rough Set Algorithm Based on Matrix, PhD thesis, AnHui univercity, 2017.

Feng

and Mi

, Variable precision multigranulation decision-theoretic fuzzy rough sets, Knowledge Based Systems 91 (2016), 93–101.

, Liu

and Liu

, Matrix-based approaches for dynamic updating approximations in multi-granulation rough sets, Knowledge-Based Systems 122 (2017), 51–63.

, Li

, Luo

, Fujita

and Li

, Incremental fuzzy probabilistic rough sets over two universes, International Journal of Approximate Reasoning 81 (2017), 28–48.

, An

, Yu

and Yu

, Robust fuzzy rough classifiers, Fuzzy Sets & Systems 183(1) (2011), 26–43.

Huang

, Guo

, Zhuang

, Li

and Zhou

, Intuitionistic fuzzy multigranulation rough sets, Information Sciences 277 (2014), 299–320.

10.

Huang

, Li

, Luo

, Fujita

and Horng

S.-J.

, Matrix-based dynamic updating rough fuzzy approximations for data mining, Knowledge-Based Systems 119 (2017), 273–283.

11.

Jiang

, Zhan

and Chen

, Covering based variable precision (i, t)-fuzzy rough sets with applications to multi-attribute decision-making, IEEE Transactions on Fuzzy Systems (2018).

12.

Katzberg

J.D.

and Ziarko

, Variable precision rough sets with a symmetric bounds, In International Workshop on Rough Sets & Knowledge Discovery: Rough Sets, 1993.

13.

Lang

, Miao

, Cai

and Zhang

, Incremental approaches for updating reducts in dynamic covering information systems, Knowledge Based Systems 134 (2017), 85–104.

14.

Leung

, Fischer

M.M.

, Wu

and Mi

, A rough set approach for the discovery of classification rules in interval-valued information systems, International Journal of Approximate Reasoning 47(2) (2008), 233–246.

15.

, Huang

, Qi

, Qian

and Liu

, Three-way cognitive concept learning via multi-granularity, Information Sciences 378 (2017), 244–263.

16.

, Ren

, Mei

, Qian

and Yang

, A comparative study of multigranulation rough sets and concept lattices via rule acquisition, Knowledge Based Systems 91 (2016), 152–164.

17.

Lin

, Qian

and Li

, Nmgrs: Neighborhood-based multigranulation rough sets, International Journal of Approximate Reasoning 53(7) (2012), 1080–1093.

18.

Liu

, Li

and Liang

, Incorporating logistic regression to decision-theoretic rough sets for classifications, International Journal of Approximate Reasoning 55(1) (2014), 197–210.

19.

Luo

, Li

, Chen

, Fujita

and Yi

, Efficient updating of probabilistic approximations with incremental objects, Knowledge Based Systems 109 (2016), 71–83.

20.

Luo

, Li

, Chen

, Fujita

and Yi

, Incremental rough set approach for hierarchical multicriteria classification, Information Sciences 429 (2018), 72–87.

21.

Luo

, Li

, Chen

and Lu

, Fast algorithms for computing rough approximations in set-valued decision systems while updating criteria values, Information Sciences 299 (2015), 221–242.

22.

Luo

, Li

, Huang

and Fujita

, Updating three-way decisions in incomplete multi-scale information systems, Information Sciences 476 (2019), 274–289.

23.

Pawlak

, Rough set, International Journal of Computer & Information Sciences 11(5) (1982).

24.

Pawlak

and Skowron

, Rough sets: Some extensions, Information Sciences 177(1) (2007), 28–40.

25.

Qian

, Liang

, Yao

and Dang

, Mgrs: A multi-granulation rough set, Information Sciences 180(6) (2010), 949–970.

26.

Qian

, Zhang

, Li

, Hu

and Liang

, Set-based granular computing: A lattice model, International Journal of Approximate Reasoning 55(3) (2014), 834–852.

27.

Qian

, Zhang

, Sang

and Liang

, Multigranulation decision-theoretic rough sets, International Journal of Approximate Reasoning 55(1) (2014), 225–237.

28.

Shin

and Cho

, Invariance of neighborhood relation under input space to feature space mapping, Pattern Recognition Letters 26(6) (2005), 707–718.

29.

Shu

, Qian

and Xie

, Incremental approaches for feature selection from dynamic data with the variation of multiple objects, Knowledge Based Systems 163 (2019), 320–331.

30.

Sun

, Gong

and Chen

, Fuzzy rough set theory for the interval-valued fuzzy information systems, Computer Engineering & Applications 178(13) (2011), 2794–2815.

31.

Sun

and Ma

, Multigranulation rough set theory over two universes, Journal of Intelligent and Fuzzy Systems 28(3) (2015), 1251–1269.

32.

Swiniarski

R.W.

and Skowron

, Rough set methods in feature selection and recognition, Pattern Recognition Letters 24(6) (2003), 833–849.

33.

Wang

and Zhang

, Matrix approaches for some issues about minimal and maximal descriptions in covering-based rough sets, International Journal of Approximate Reasoning 104 (2019), 126–143.

34.

Wei

, Song

, Liang

and Wu

, Accelerating incremental attribute reduction algorithm by compacting a decision table, International Journal of Machine Learning and Cybernetics (2018), 1–19.

35.

W.Z.

, Leung

and Shao

M.W.

, Generalized fuzzy rough approximation operators determined by fuzzy implicators, International Journal of Approximate Reasoning 54(9) (2013), 1388–1409.

36.

W.Z.

, Mi

J.S.

and Zhang

W.X.

, Generalized fuzzy rough sets, Information Sciences 151(3) (2003), 263–282.

37.

Yang

, Qi

, Yu

, Song

and Yang

, Updating multigranulation rough approximations with increasing of granular structures, Knowledge Based Systems 64(1) (2014), 59–69.

38.

Yao

, Three-way decisions with probabilistic rough sets, Information Sciences 180(3) (2011), 341–353.

39.

Yao

and Yao

, Covering based rough set approximations, Information Sciences 200(1) (2012), 91–107.

40.

Zeng

, Li

, Hu

, Chen

and Luo

, Dynamical updating fuzzy rough approximations for hybrid data under the variation of attribute values, Information Sciences 378 (2017), 363–388.

41.

Zhan

, Sun

and Alcantud

J.C.R.

, Covering based multigranulation (i, t)-fuzzy rough set models and applications in multi-attribute group decision-making, Information Sciences 476 (2019), 290–318.

42.

Zhang

, Li

, Ruan

and Liu

, Rough sets based matrix approaches with dynamic attribute variation in set-valued information systems, International Journal of Approximate Reasoning 53(4) (2012), 620–635.

43.

Zhang

, Zhan

, Wu

and Alcantud

J.C.R.

, Fuzzy β -covering based (i, t)-fuzzy rough set models and applications to multi-attribute decision-making, Computers & Industrial Engineering 128 (2019), 605–621.

44.

Zhang

, Zhan

and Xu

, Covering-based generalized if rough sets with applications to multi-attribute decision-making, Information Sciences 478 (2019), 275–302.

45.

Zhao

, Tsang

E.C.C.

and Chen

, The model of fuzzy variable precision rough sets, IEEE Transactions on Fuzzy Systems 17(2) (2009), 451–467.

Matrix-based approaches for updating approximations in neighborhood multigranulation rough sets while neighborhood classes decreasing or increasing

Abstract

Keywords

1 Introduction

2 Preliminaries

2.1 Neighborhood Multigranulation rough sets

2.2 Matrix-based algorithm for computing approximations in NMGRS

Table 1 A neighborhood information system U a 1 a 2 a 3 a 4 x 1 1 3 1.5 0.5 x 2 2 2 0.5 1 x 3 3 1 2 2.5 x 4 2 3 1.5 1 x 5 1 1 2 0.5 x 6 3 2 0.5 2

3.1 Matrix-based approaches for updating approximations while neighborhood classes are decreasing

3.2 Matrix-based approaches for updating approximations while neighborhood classes are increasing

4 Matrix-based dynamic algorithms for updating approximations while neighborhood classes increasing or decreasing

Table 2 Details of data sets No. Data sets Samples Attributes 1 Cylinder Bands Data Set 541 40 2 Dermatology 366 20 3 Flags 194 30 4 LasVegas Trip Advisor Reviews Data set 504 20 5 Soybean Large 307 36 6 Student 396 33

Footnotes

Acknowledgement

References

Table 1
A neighborhood information system

U a ₁ a ₂ a ₃ a ₄

x ₁ 1 3 1.5 0.5

x ₂ 2 2 0.5 1

x ₃ 3 1 2 2.5

x ₄ 2 3 1.5 1

x ₅ 1 1 2 0.5

x ₆ 3 2 0.5 2

Table 2
Details of data sets

No. Data sets Samples Attributes

1 Cylinder Bands Data Set 541 40

2 Dermatology 366 20

3 Flags 194 30

4 LasVegas Trip Advisor Reviews Data set 504 20

5 Soybean Large 307 36

6 Student 396 33