Incremental approaches to update multigranulation approximations for dynamic information systems

Abstract

Multigranulation rough set (MGRS) theory provides an effective manner for the problem solving by making use of multiple equivalence relations. As the information systems always dynamically change over time due to the addition or deletion of multiple objects, how to efficiently update the approximations in multigranulation spaces by making fully utilize the previous results becomes a crucial challenge. Incremental learning provides an efficient manner because of the incorporation of both the current information and previously obtained knowledge. In spite of the success of incremental learning, well-studied findings performed to update approximations in multigranulation spaces have relatively been scarce. To address this issue, in this paper, we propose matrix-based incremental approaches for updating approximations from the perspective of multigranulation when multiple objects vary over time. Based on the matrix characterization of multigranulation approximations, the incremental mechanisms for relevant matrices are systematically investigated while adding or deleting multiple objects. Subsequently, in accordance with the incremental mechanisms, the corresponding incremental algorithms for maintaining multigranulation approximations are developed to reduce the redundant computations. Finally, extensive experiments on eight datasets available from the University of California at Irvine (UCI) are conducted to verify the effectiveness and efficiency of the proposed incremental algorithms in comparison with the existing non-incremental algorithm.

Keywords

Dynamic data approximations multigranulation matrix knowledge discovery

1 Introduction

Rough set theory (RST), proposed by Pawlak [38], provides a soft computing framework for data processing [3, 63]. During the past decades, this theory has been widely used in decision making [1 , 68], machine learning [26 , 53] and rule acquisition [32, 71].

Generally speaking, Pawlak rough set model and most of its extensions are established on the basis of a single granular structure. In these models, the lower and upper approximations, which are basic notations, can be used for rules extraction and related decision making tasks. On one hand, the knowledge hidden in information systems can be described in the form of decision rules by taking advantage of the lower and upper approximations. More precisely, an object belonging to the lower approximation generates a certain rule, whereas an object belonging to the upper approximation forms a probable rule. On the other hand, the lower approximation, which plays a pivotal role in positive region-based attribute reductions [59], can be used to acquire attribute reducts. Due to the requirement of practical applications, information systems may vary over time, e.g., variation of objects, variation of attributes and variation of attribute values. It is noteworthy that the dynamic change of information systems may result in the change of the potential valuable knowledge, e.g., the lower and upper approximations. The non-incremental approach needs to re-calculate the entire data set from scratch and makes it time-consuming for updating new knowledge, owing to the lack of using prior information. Therefore, it is necessary to develop the techniques to update new knowledge effectively from the efficiency perspective. Incremental technique has the ability to perform the computation by means of prior knowledge from the original data assisted with newly arriving data to acquire new knowledge, which avoids reprocessing the whole computation for achieving new knowledge. Recently, numerous findings [6 , 58] concerning incremental updating approximations and attribute reduction in dynamic contexts have been investigated from the efficiency perspective. Furthermore, they are roughly grouped into three categories. (1) Many incremental frameworks have been developed under the variation of objects [4 , 43]. Liu et al. established dynamic knowledge updating approaches in incomplete information systems when the objects vary [31]. Considering the data with fuzzy information, Hu et al. [14] designed an incremental algorithm for computing fuzzy approximations. In addition, Luo et al. [35] explored incremental algorithms for updating probabilistic approximations. (2) Numerous studies regarding updating approximations and attribute reducts have been exploited under the variation of attributes [5 , 52]. Based on characteristic relations, Li et al. [24] developed incremental methods for maintaining approximations when adding or deleting attributes. Incremental algorithms for updating approximations in set-valued ordered systems were investigated by Luo et al. in [34] when adding or deleting attributes. (3) Under the variation of attribute values [23 , 61], a lot of dynamic frameworks have been developed. For example, Chen et al. put forward the incremental algorithms for maintaining decision rules [7] and approximations in incomplete ordered decision systems [8], respectively. Wang et al. [48] proposed an incremental attribute reduction method when feature values evolve over time. These outstanding achievements have provided theoretical guidelines for updating knowledge in dynamic environments.

However, the above-mentioned theoretical frameworks established by a single granulation have some limitations for handling various special data in practical applications, such as, multi-source data, distributive data and multi-agent systems. Therefore, to fill this gap, multigranulation rough set (MGRS) theory, emerged as one of the most distinguished paradigm, has been proposed by Qian et al., where the approximations are established by multiple granular structures [40]. This theory has been utilized to decision making, and attribute reduction [42]. Since then, several state-of-the-art theoretical frameworks in the multigranulation spaces [44–46 , 67] have been developed from theoretical point of view, such as, MGRS under tolerance relations [41], neighborhood-based MGRS models [29], covering-based MGRS and its extensions [2 , 65], fuzzy MGRS [15 , 66], Multi-granulation hesitant fuzzy rough sets [69]. These well-established models not only significantly benefit the theoretical analysis but also show the potential to be applied in various applications. Interestingly, there are also many studies concerning combination of multigranulation rough sets and other theories, such as, Bayesian theory [70], concept lattices [22], three-way group decision [36, 51], as well as three-way concept learning [21]. In the viewpoint of knowledge acquisition, Qian et al. [39] developed an attribute reduction method for acquiring rule in the pessimistic MGRS. Zhan et al. [62] proposed covering-based intuitionistic fuzzy rough sets for multi-attribute decision-making. Ju et al. [18] investigated an effective cost-sensitive rough set framework with multigranulation strategy and established the approximations of cost-sensitive MGRS. In addition, Yao et al. [57] presented a theoretic framework for classification in multigranulation spaces.

Although these theoretical models have promoted the development of MGRS, they are incapable to handle dynamic data sets in multigranulation contexts due to lacking the update mechanisms by utilizing previous knowledge. Accordingly, to acquire new useful knowledge in dynamic multigranulation contexts, one should recalculate the new entire data sets from the very beginning. Nonetheless, this will consume a large number of computational time. Therefore, several incremental mechanisms have been naturally developed to update multigranulation approximations and reducts by considering diverse variations of data sets. For instance, Yang et al. [55] proposed an efficient approach for incrementally computing multigranulation approximations with the increasing of granular structures. Meanwhile, Ju et al. [19] investigated incremental methods for updating approximations and reduction in fuzzy MGRS. In addition, to handle dynamic neighborhood systems, we [13] explored incremental mechanisms to acquire approximations under dynamic granular structures. Furthermore, Yu et al. [60] developed matrix-based methods for updating approximations in neighborhood multigranulation spaces when neighborhood classes decrease or increase over time. Recently, we [11] proposed dynamic algorithms for maintaining dominance-based multigranulation approximations for evolving ordered data.

As discussed above, the well-established dynamic approaches in multigranulation environments were investigated from different perspectives. It is well-known that the change of multi-source data is not only in the sense of evolving granular structures but also in the sense of adding or deleting objects. Taking a comprehensive evaluation system based on multiple experts as an example, the experts often need to evaluate results for all objects of the universe with reference to different evaluation subjects. When new objects that need to be evaluated by different experts arrive, these objects should be added into the original evaluation system. Moreover, some objects in the original evaluation system may be useless and therefore need to be deleted from the system. Accordingly, the approximations and rules hidden in the multigranulation space may vary over time under these circumstances. Therefore, how to update knowledge by making use of previous information so as to enhance the efficiency of acquiring knowledge is a key issue. To address this issue, in this paper, we explore matrix-based incremental mechanisms for updating approximations in MGRS when multiple objects dynamically change. Different from previous work, the main contributions of this study are outlined as follows: (1) Matrix-based incremental frameworks for updating multigranulation approximations are explored when adding or deleting objects. (2) The proposed algorithms can be used to handle dynamic categorical data under the variation of multiple objects from multigranulation perspective. (3) Comparable experiments on UCI datasets are performed to evaluate the performance of the incremental algorithms in terms of computational efficiency.

The remainder of this paper is organized as follows. In Section 2, several fundamental notions of RST and MGRS are reviewed, and a matrix representation of approximations in MGRS is introduced. In Section 3, incremental mechanisms for updating multigranulation approximations are proposed while adding or deleting objects, and numerical examples are employed to illustrate the feasibility of the proposed mechanisms. In Section 4, the corresponding incremental algorithms are developed while adding or deleting multiple objects. Extensive experiments are conducted to validate the efficiency of the proposed incremental updating algorithms in Section 5. The paper ends with a brief summary and some future research topics in Section 6.

2 Preliminaries

In this section, we review the preliminary notions of RST and MGRS [38 –40], and proceed to introduce a matrix representation of multigranulation lower and upper approximations [12].

2.1 Multigranulation rough sets

An information system [38] is defined as IS = (U, A, V, f), where U = {x_i|i ∈ {1, 2, …, n}} is a non-empty finite set of objects, A = {a_k|k ∈ {1, 2, …, m}} is a non-empty finite set of attributes, V = ⋃ _{a_k∈A}V_{a
_k} is the domain of attributes values, V_{a
_k} is the domain of the attribute a_k, and f : U × A → V is a decision function with f (x_i, a_k) ∈ V_{a
_k}, for any a_k ∈ A, and x_i ∈ U.

A binary indiscernibility relation R_B in terms of each non-empty subset B ⊆ A is defined as follows [38]:

$R_{B} = {(x_{i}, y) \in U \times U | f (x_{i}, a_{k}) = f (y, a_{k}), \forall a_{k} \in B} .$

Clearly, R_B is an equivalence relation on the universe U, which forms a partition U/R_B = {[x_i] _B|x_i ∈ U}, where [x_i] _B denotes the equivalence class of x_i with respect to B, i.e., [x_i] _B = {y ∈ U| (x_i, y) ∈ R_B}.

Definition 1. [38] Let IS = (U, A, V, f) be an information system, where U = {x_i|i ∈ {1, 2, …, n}}. Given X ⊆ U, and B ⊆ A. The lower and upper approximations of X with respect to B are defined as $\underline{R_{B}} (X) = {x_{i} \in U | [x_{i}]_{B} \subseteq X};$ (1) $\bar{R_{B}} (X) = {x_{i} \in U | [x_{i}]_{B} \cap X \neq \emptyset} .$ (2)

Based on these approximations, three disjoint regions of X with respect to B ⊆ A, namely, the positive, boundary and negative regions, can be described as: ${POS}_{B} (X) = \underline{R_{B}} (X)$ , ${BND}_{B} (X) = \bar{R_{B}} (X) - \underline{R_{B}} (X)$ and ${NEG}_{B} (X) = U - \bar{R_{B}} (X)$ . Notably, the union of these three regions is the entire universe U.

In the classical rough set model, the approximations were constructed based on a single granulation [38]. To provide a distinguished paradigm for making decisions, Qian el al. [39, 40] proposed a multigranulation rough set model, which consists of the optimistic MGRS and pessimistic MGRS. In what follows, we introduce the basic concepts of approximations in the multigranulation rough set model.

Definition 2. [40] Let IS = (U, A, V, f), where A = {a_k|k ∈ {1, 2, …, m}}, and X ⊆ U. The lower and upper approximations of X in the optimistic MGRS are denoted as $\underline{\sum_{k = 1}^{m} a_{k}^{O}} (X)$ and $\bar{\sum_{k = 1}^{m} a_{k}^{O}} (X)$ , respectively, $\underline{\sum_{k = 1}^{m} a_{k}^{O}} (X) = {x_{i} \in U | \lor_{k = 1}^{m} ([x_{i}]_{a_{k}} \subseteq X)};$ (3) $\bar{\sum_{k = 1}^{m} a_{k}^{O}} (X) = {x_{i} \in U | \land_{k = 1}^{m} ([x_{i}]_{a_{k}} \cap X \neq \emptyset)}$ (4) where “∧” and “∨” refer to the conjunctive and disjunctive operators, respectively.

According to Definition 2, we can see that an object belongs to the lower approximation of the optimistic MGRS if and only if at least one granular structure satisfies with the inclusion condition between equivalence class and the target concept. The upper approximation of the optimistic MGRS can be considered as a set in which objects have non-empty intersection with the target concept in terms of each granular structure.

According to the optimistic multigranulation approximations, the optimistic multigranulation three regions can be formalized as: ${\begin{matrix} {POS}_{\sum_{k = 1}^{m} a_{k}}^{O} (X) = \underline{\sum_{k = 1}^{m} a_{k}^{O}} (X); \\ {BND}_{\sum_{k = 1}^{m} a_{k}}^{O} (X) = \bar{\sum_{k = 1}^{m} a_{k}^{O}} (X) - \underline{\sum_{k = 1}^{m} a_{k}^{O}} (X); \\ {NEG}_{\sum_{k = 1}^{m} a_{k}}^{O} (X) = U - \bar{\sum_{k = 1}^{m} a_{k}^{O}} (X) . \end{matrix}$

Definition 3. [39] Let IS = (U, A, V, f), where A = {a_k|k ∈ {1, 2, …, m}}, and X ⊆ U. The lower and upper approximations of X in the pessimistic MGRS are denoted as $\underline{\sum_{k = 1}^{m} a_{k}^{P}} (X)$ and $\bar{\sum_{k = 1}^{m} a_{k}^{P}} (X)$ , respectively, $\underline{\sum_{k = 1}^{m} a_{k}^{P}} (X) = {x_{i} \in U | \land_{k = 1}^{m} ([x_{i}]_{a_{k}} \subseteq X)};$ (5) $\bar{\sum_{k = 1}^{m} a_{k}^{P}} (X) = {x_{i} \in U | \lor_{k = 1}^{m} ([x_{i}]_{a_{k}} \cap X \neq \emptyset)} .$ (6) where “∧” and “∨” refer to the conjunctive and disjunctive operators, respectively.

According to Definition 3, we can conclude that an object belongs to the lower approximation of the pessimistic MGRS if and only if each granular structure satisfies with the inclusion condition between equivalence class and the target concept. The upper approximation of pessimistic MGRS is regarded as a set in which objects have non-empty intersection with the target concept in terms of at least one granular structure.

Analogously, by making use of the pessimistic multigranulation approximations, the pessimistic multigranulation three regions can be formalized as: ${\begin{matrix} {POS}_{\sum_{k = 1}^{m} a_{k}}^{P} (X) = \underline{\sum_{k = 1}^{m} a_{k}^{P}} (X); \\ {BND}_{\sum_{k = 1}^{m} a_{k}}^{P} (X) = \bar{\sum_{k = 1}^{m} a_{k}^{P}} (X) - \underline{\sum_{k = 1}^{m} a_{k}^{P}} (X); \\ {NEG}_{\sum_{k = 1}^{m} a_{k}}^{P} (X) = U - \bar{\sum_{k = 1}^{m} a_{k}^{P}} (X) . \end{matrix}$

2.2 Matrix representation of rough approximations in multigranulation rough sets

In this subsection, we briefly summarize a matrix representation of rough approximations in MGRS which has been proposed in [12].

Given an information system IS = (U, A, V, f), X ⊆ U and U = {x_i|i ∈ 1, 2, …, n}, the column vector F (X) = [f₁, f₂, …, f_n] ^T (“T " refers to the transpose operation) is defined as [34] $f_{i} = {\begin{matrix} 1, & if x_{i} \in X, \\ 0, & otherwise . \end{matrix} i \in {1, 2, \dots, n} .$ (7)

Clearly, the column vector F (X) is an n × 1 Boolean matrix. In order to represent the equivalence classes of each granular structure from the matrix perspective, the equivalence relation matrix [12] $M_{a_{k}} = (m_{ij}^{a_{k}})_{n \times n}$ with reference to a_k is expressed as $M_{a_{k}} = [\begin{matrix} m_{11}^{a_{k}} & m_{12}^{a_{k}} & m_{13}^{a_{k}} & \dots & m_{1 n}^{a_{k}} \\ m_{21}^{a_{k}} & m_{22}^{a_{k}} & m_{23}^{a_{k}} & \dots & m_{2 n}^{a_{k}} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ m_{n 1}^{a_{k}} & m_{n 2}^{a_{k}} & m_{n 3}^{a_{k}} & \dots & m_{nn}^{a_{k}} \end{matrix}], k \in {1, 2, \dots, m}$ (8) where $m_{ij}^{a_{k}} = {\begin{matrix} 1, & if (x_{i}, x_{j}) \in R_{a_{k}}, \\ 0, & otherwise . \end{matrix} i, j \in {1, 2, \dots, n} .$

According to the equivalence relation matrix with respect to each granular structure, the induced diagonal matrix can be constructed by using the sum of all elements of each row in corresponding equivalence relation matrix.

Definition 4. [12] Let IS = (U, A, V, f), where A = {a_k|k ∈ {1, 2, …, m}}. The equivalence relation matrix of a_k is denoted as $M_{a_{k}} = (m_{ij}^{a_{k}})_{n \times n}$ . Then, the induced diagonal matrix with respect to a_k is defined as

$Λ_{a_{k}} = diag [\frac{1}{μ_{1}^{a_{k}}}, \frac{1}{μ_{2}^{a_{k}}}, \dots, \frac{1}{μ_{n}^{a_{k}}}], k \in {1, 2, \dots, m} .$ (9)

where $μ_{i}^{a_{k}} = \sum_{j = 1}^{n} m_{ij}^{a_{k}}$ , i ∈ {1, 2, …, n}.

According to Definition 4, we can easily derive that the element $μ_{i}^{a_{k}}$ equals to the cardinality of the equivalence class of the object x_i in terms of the granular structure a_k. Furthermore, based on the equivalence relation matrix of a_k and the column vector F (X), the intermediate matrix of a_k can be established.

Definition 5. [12] Let IS = (U, A, V, f), where A = {a_k|k ∈ {1, 2, …, m}}, and X ⊆ U. F (X) = (f_i) _n×1 is the column vector of X. $M_{a_{k}} = (m_{ij}^{a_{k}})_{n \times n}$ is the equivalence relation matrix of a_k. The intermediate matrix of a_k is denoted as M_{a
_k} · F (X). The induced diagonal matrix of a_k is denoted as Λ_{a
_k}. Then, the column matrix H_{a
_k} (X) is defined as $H_{a_{k}} (X) = Λ_{a_{k}} \cdot (M_{a_{k}} \cdot F (X)), k \in {1, 2, \dots, m} .$ (10) where “·” denotes dot product of matrix.

Notably, the column matrix play a significant role in the construction of the cut matrices. Next, we show the definition of two cut matrices by using the column matrix.

Definition 6. [12] Let IS = (U, A, V, f), where A = {a_k|k ∈ {1, 2, …, m}}, 0 ≤ α ≤ β ≤ 1, and X ⊆ U. $H_{a_{k}} (X) = [h_{1}^{a_{k}}, h_{2}^{a_{k}}, \dots, h_{n}^{a_{k}}]^{T}$ is the column matrix of a_k. Then, two cut matrices of a_k are defined as $H_{a_{k}}^{[α, β]} (X) = (h_{i}^{a_{k} ↓})_{n \times 1}$ and $H_{a_{k}}^{(α, β]} (X) = (h_{i}^{a_{k} ↑})_{n \times 1}$ , respectively, where $h_{i}^{a_{k} ↓} = {\begin{matrix} 1, & if α \leq h_{i}^{a_{k}} \leq β, \\ 0, & otherwise . \end{matrix}$ (11) $h_{i}^{a_{k} ↑} = {\begin{matrix} 1, & if α < h_{i}^{a_{k}} \leq β, \\ 0, & otherwise . \end{matrix}$ (12)

According to Definition 6, by using two different parameters α and β, two cut matrices, which are directly used for constructing the column vectors of the lower and upper approximations in MGRS, can be easily obtained. On the basis of the aforementioned properties of matrix operations, the column vectors of the optimistic and pessimistic multigranulation approximations of X can be established in the following theorems.

Theorem 1. [12] Let IS = (U, A, V, f), where A = {a_k|k ∈ {1, 2, …, m}}, and X ⊆ U. $H_{a_{k}} (X) = [h_{1}^{a_{k}}, h_{2}^{a_{k}}, \dots, h_{n}^{a_{k}}]^{T}$ is the column matrix of a_k. $F (\underline{\sum_{k = 1}^{m} a_{k}^{O}} (X))$ and $F (\bar{\sum_{k = 1}^{m} a_{k}^{O}} (X))$ are the column vectors of the optimistic multigranulation lower and upper approximations of X, respectively. Then, we have, $F (\underline{\sum_{k = 1}^{m} a_{k}^{O}} (X)) = \lor_{k = 1}^{m} H_{a_{k}}^{[1, 1]} (X);$ (13) $F (\bar{\sum_{k = 1}^{m} a_{k}^{O}} (X)) = \land_{k = 1}^{m} H_{a_{k}}^{(0, 1]} (X) .$ (14) where “∧” and “∨” refer to the conjunctive and disjunctive operators, respectively.

It can be easily seen from Theorem 1 that the column vectors of the lower and upper approximations of the optimistic MGRS can be obtained when we set the values of the parameters α and β in the cut matrices of each granular structure. Based on Theorem 1, the lower and upper approximations of optimistic MGRS can be further calculated by using the definition of the column vector.

Theorem 2. [12] Let IS = (U, A, V, f), where A = {a_k|k ∈ {1, 2, …, m}}, and X ⊆ U. $H_{a_{k}} (X) = [h_{1}^{a_{k}}, h_{2}^{a_{k}}, \dots, h_{n}^{a_{k}}]^{T}$ is the column matrix of a_k. $F (\underline{\sum_{k = 1}^{m} a_{k}^{P}} (X))$ and $F (\bar{\sum_{k = 1}^{m} a_{k}^{P}} (X))$ are the column vectors of the pessimistic multigranulation lower and upper approximations of X, respectively. Then, we have,

$F (\underline{\sum_{k = 1}^{m} a_{k}^{P}} (X)) = \land_{k = 1}^{m} H_{a_{k}}^{[1, 1]} (X);$ (15) $F (\bar{\sum_{k = 1}^{m} a_{k}^{P}} (X)) = \lor_{k = 1}^{m} H_{a_{k}}^{(0, 1]} (X) .$ (16) where “∧” and “∨” refer to the conjunctive and disjunctive operators, respectively.

It can be easily seen from Theorem 2 that the column vectors of the lower and upper approximations of the pessimistic MGRS can be obtained when we set the values of the parameters α and β in the cut matrices of each granular structure. Based on Theorem 2, the lower and upper approximations of pessimistic MGRS can be further calculated by using the definition of the column vector.

3 Incremental mechanisms for updating multigranulation approximations when multiple objects vary

In dynamic contexts, information systems are always evolving with the changing of the available data, which include the addition or deletion of multiple objects, the variation of the attribute values, and the generalization of attribute sets. In this section, we explore matrix-based incremental mechanisms for updating approximations in MGRS when multiple objects are respectively added into or deleted from information systems.

3.1 Adding multiple objects

Let IS = (U, A, V, f) be an information system, where A = {a_k|k ∈ {1, 2, …, m}}, U = {x_i|i ∈ {1, 2, …, n}} and X ⊆ U. Assume that an objects set U^Δ = {x_n+1, x_n+2, …, x_n+s} is added into U and the granular structures keep unchanged. In what follows, matrix-based incremental mechanisms for updating approximations of a target concept X in MGRS are explored when multiple objects are added into an information system. When adding an object set U^Δ into the original universe U, if the target concept X is changed, then the column vector of X can be updated by the following theorem.

Theorem 3. Given IS = (U, A, V, f), where U = {x_i|i ∈ {1, 2, …, n}} and X ⊆ U. The column vector of X is denoted as F (X) = [f₁, f₂, …, f_n] ^T. When an object set U^Δ = {x_n+1, x_n+2, …, x_n+s} is added into U, the updated column vector of X is denoted as $F^{Δ} (X) = [f_{1}^{↑}, f_{2}^{↑}, \dots, f_{n + s}^{↑}]^{T}$ . Let X = X ∪ X^Δ and X^Δ ⊆ U^Δ. Then, the column vector of X is updated as:

$f_{i}^{↑} = {\begin{matrix} f_{i}, & if i \in {1, 2, \dots, n}, \\ 1, & if x_{i} \in X^{Δ}, i \in {n + 1, n + 2, \dots, n + s}, \\ 0, & if x_{i} \notin X^{Δ}, i \in {n + 1, n + 2, \dots, n + s} . \end{matrix}$ (17)

Proof. Assume that an object set U^Δ = {x_n+1, x_n+2, …, x_n+s} is added into U, the column vector needs to be updated to an (n + s) ×1 column vector. If x_i ∈ X for any i ∈ {1, 2, …, n}, by Eq. (7), we have x_i ∈ X ∪ X^Δ, then $f_{i}^{↑} = f_{i} = 1$ ; otherwise $f_{i}^{↑} = f_{i} = 0$ . Therefore, $f_{i}^{↑} = f_{i}$ always holds for any i ∈ {1, 2, …, n}. In addition, if x_i ∈ X^Δ for any i ∈ {n + 1, n + 2, …, n + s}, then, x_i ∈ X ∪ X^Δ, according to Eq. (8), we have $f_{i}^{↑} = 1$ ; otherwise, $f_{i}^{↑} = 0$ . □

Example 1. The information system IS = (U, A, V, f) outlined in Table 1 is a practical case of car evaluation, where the universe U = {x_i|i ∈ {1, 2, …, 8}} denotes eight cars and A = {a_k|k ∈ {1, 2, 3}} denotes three features which correspond to three granular structures, where a₁ denotes the buying price, a₂ denotes the size of luggage boot, a₃ denotes the estimated safety of a car. Assume the target concept is X = {x₂, x₃, x₄, x₆}. Let an object set U^Δ = {x₉, x₁₀, x₁₁} summarized in Table 2 be added into the original universe U and X^Δ = {x₉}. Then, by Theorem 3, the column vector F^Δ (X) is updated as: F^Δ (X) = [0, 1, 1, 1, 0 , 1, 0, 0, 1, 0, 0] ^T.

Table 1

An information system

U	a ₁	a ₂	a ₃
x ₁	med	small	med
x ₂	low	big	med
x ₃	med	med	low
x ₄	high	med	high
x ₅	low	small	med
x ₆	high	med	high
x ₇	med	big	med
x ₈	med	small	low

Table 2

The added object set U^Δ

U ^Δ	a ₁	a ₂	a ₃
x ₉	high	big	low
x ₁₀	low	med	med
x ₁₁	low	small	high

As previously discussed, the equivalence relation matrix plays a key role in the entire process for updating approximations in MGRS. Therefore, in the following theorem, the updating mechanism for equivalence relation matrix of each granular structure is demonstrated when an object set U^Δ is added into information systems, which can reduce computational time effectively.

Theorem 4. Let IS = (U, A, V, f), where A = {a_k|k ∈ {1, 2, …, m}} and U = {x_i|i ∈ {1, 2, …, n}}. The equivalence relation of a_k is denoted as R_{a
_k}. When an object set U^Δ = {x_n+1, x_n+2, …, x_n+s} is added into U, the updated equivalence relation matrix of a_k is denoted as $M_{a_{k}}^{Δ} = (m_{ij}^{a_{k} ↑})_{(n + s) \times (n + s)}$ , which can be partitioned four parts. Incremental relation matrices are denoted as $P_{a_{k}}^{Δ} = (p_{ij}^{a_{k} ↑})_{n \times s}$ , $Q_{a_{k}}^{Δ} = (q_{ij}^{a_{k} ↑})_{s \times n}$ , and $Z_{a_{k}}^{Δ} = (z_{ij}^{a_{k} ↑})_{s \times s}$ , respectively. Then, we have, $M_{a_{k}}^{Δ} = [\begin{matrix} M_{a_{k}} & P_{a_{k}}^{Δ} \\ Q_{a_{k}}^{Δ} & Z_{a_{k}}^{Δ} \end{matrix}]$ (18) where $P_{a_{k}}^{Δ}$ is the transpose of the relation matrix $Q_{a_{k}}^{Δ}$ , and

${\begin{matrix} p_{ij}^{a_{k} ↑} = {\begin{matrix} 1, & if (x_{i}, x_{n + j}) \in R_{a_{k}}, \\ 0, & otherwise . \end{matrix} & where i \in {1, 2, \dots, n}, j \in {1, 2, \dots, s}, \\ q_{ij}^{a_{k} ↑} = {\begin{matrix} 1, & if (x_{n + i}, x_{j}) \in R_{a_{k}}, \\ 0, & otherwise . \end{matrix} & where i \in {1, 2, \dots, s}, j \in {1, 2, \dots, n}, \\ z_{ij}^{a_{k} ↑} = {\begin{matrix} 1, & if (x_{n + i}, x_{n + j}) \in R_{a_{k}}, \\ 0, & otherwise . \end{matrix} & where i, j \in {1, 2, \dots, s} . \end{matrix}$

Proof. Assume that an object set U^Δ = {x_n+1, x_n+2, …, x_n+s} is added into U, the equivalence relation matrix should be updated to an (n + s) × (n + s) matrix. It is obvious that $m_{ij}^{a_{k} ↑} = m_{ij}^{a_{k}}$ for any i, j ∈ {1, 2, …, n}. For the incremental relation matrix $P_{a_{k}}^{Δ} = (p_{ij}^{a_{k} ↑})_{n \times s}$ , according to Eq. (8), it follows that for any i ∈ {1, 2, …, n} and j ∈ {1, 2, …, s}, if (x_i, x_n+j) ∈ R_{a
_k}, then $p_{ij}^{a_{k} ↑} = 1$ holds; otherwise $p_{ij}^{a_{k} ↑} = 0$ holds. For the incremental relation matrix $Q_{a_{k}}^{Δ} = (q_{ij}^{a_{k} ↑})_{s \times n}$ , according to Eq. (8), it follows that for any i ∈ {1, 2, …, s} and j ∈ {1, 2, …, n}, if it satisfies that (x_n+i, x_j) ∈ R_{a
_k}, then $q_{ij}^{a_{k} ↑} = 1$ holds; otherwise, we have $q_{ij}^{a_{k} ↑} = 0$ . For the incremental relation matrix $Z_{a_{k}}^{Δ} = (z_{ij}^{a_{k} ↑})_{s \times s}$ , according to Eq. (8), if it satisfies that (x_n+i, x_n+j) ∈ R_{a
_k}, for any i ∈ {1, 2, …, s} and j ∈ {1, 2, …, s}, then $z_{ij}^{a_{k} ↑} = 1$ holds; otherwise, we have $z_{ij}^{a_{k} ↑} = 0$ . □

According to Theorem 4, we only need to calculate three incremental relation matrices so as to update the new equivalence relation matrix $M_{a_{k}}^{Δ}$ , k ∈ {1, 2, …, m}. This feasible mechanism can improve the efficiency without forgetting previous knowledge. The following example is to illustrate this mechanism for calculating incremental relation matrices.

Example 2. When adding the object set U^Δ = {x₉, x₁₀, x₁₁} into U, for the granular granular a_k, it can be seen from Eq. (18) that $P_{a_{k}}^{Δ}$ is a 8 × 3 matrix, $Q_{a_{k}}^{Δ}$ is a 3 × 8 matrix, and $Z_{a_{k}}^{Δ}$ is a 3 × 3 matrix, where k ∈ {1, 2, 3}. Accordingly, we can obtain three incremental relation matrices of each granular structure by Theorem 4 as follows:

$P_{a_{1}}^{Δ} = \begin{matrix} [\begin{matrix} 0 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}] \end{matrix}$ , $P_{a_{2}}^{Δ} = \begin{matrix} [\begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}] \end{matrix}$ , $P_{a_{3}}^{Δ} =$ $\begin{matrix} [\begin{matrix} 0 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}] \end{matrix}$ , $Q_{a_{1}}^{Δ} = \begin{matrix} [\begin{matrix} 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \end{matrix}] \end{matrix}$ , $Q_{a_{2}}^{Δ} = \begin{matrix} [\begin{matrix} 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \end{matrix}] \end{matrix}$ , $Q_{a_{3}}^{Δ} = \begin{matrix} [\begin{matrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \end{matrix}] \end{matrix}$ , $Z_{a_{1}}^{Δ} = \begin{matrix} [\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{matrix}] \end{matrix}$ , $Z_{a_{2}}^{Δ} = \begin{matrix} [\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}] \end{matrix}$ , $Z_{a_{3}}^{Δ} = \begin{matrix} [\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}] \end{matrix}$ .

On the basis of the incremental relation matrices, when an object set U^Δ is added into information systems, the incremental mechanism for the induced diagonal matrix of each granular structure can be updated as follows.

Theorem 5. Let IS = (U, A, V, f), where A = {a_k|k ∈ {1, 2, …, m}} and U = {x_i|i ∈ {1, 2, …, n}}. When an object set U^Δ = {x_n+1, x_n+2, …, x_n+s} is added into U, $M_{a_{k}}^{Δ} = (m_{ij}^{a_{k} ↑})_{(n + s) \times (n + s)}$ is the updated equivalence relation matrix of a_k and $Λ_{a_{k}}^{Δ} = diag [1 / μ_{1}^{a_{k} ↑}, 1 / μ_{2}^{a_{k} ↑}, \dots, 1 / μ_{n + s}^{a_{k} ↑}]$ is the updated induced diagonal matrix. $P_{a_{k}}^{Δ} = (p_{ij}^{a_{k} ↑})_{n \times s}$ , $Q_{a_{k}}^{Δ} = (q_{ij}^{a_{k} ↑})_{s \times n}$ , and $Z_{a_{k}}^{Δ} = (z_{ij}^{a_{k} ↑})_{s \times s}$ are incremental relation matrices. Then, the following result holds for the induced diagonal matrix of a_k:

$μ_{i}^{a_{k} ↑} = {\begin{matrix} μ_{i}^{a_{k}} + \sum_{j = 1}^{s} p_{ij}^{a_{k} ↑}, & if i \in {1, 2, \dots, n}, \\ \sum_{j = 1}^{n} q_{i - n, j}^{a_{k} ↑} + \sum_{j = 1}^{s} z_{i - n, j}^{a_{k} ↑}, & if i \in {n + 1, n + 2, \dots, n + s} . \end{matrix}$ (19)

Proof. Assume that an object set U^Δ = {x_n+1, x_n+2, …, x_n+s} is added into U, according to Definition 4, we have $μ_{i}^{a_{k} ↑} = \sum_{j = 1}^{n + s} m_{ij}^{a_{k} ↑} = \sum_{j = 1}^{n} m_{ij}^{a_{k} ↑} + \sum_{j = n + 1}^{n + s} m_{ij}^{a_{k} ↑}$ for any i ∈ {1, 2, …, n}. Because we have $m_{ij}^{a_{k} ↑} = m_{ij}^{a_{k}}$ for any i, j ∈ {1, 2, …, n}, we can obtain that $\sum_{j = 1}^{n} m_{ij}^{a_{k} ↑} = \sum_{j = 1}^{n} m_{ij}^{a_{k}}$ . Moreover, for any i ∈ {1, 2, …, n}, and j ∈ {1, 2, …, s}, we have $p_{ij}^{a_{k} ↑} = m_{i, j + n}^{a_{k} ↑}$ . Then, $\sum_{j = 1}^{s} p_{ij}^{a_{k} ↑} = \sum_{j = n + 1}^{n + s} m_{ij}^{a_{k} ↑}$ holds for any i ∈ {1, 2, …, n}. Therefore, we have $μ_{i}^{a_{k} ↑} = \sum_{j = 1}^{n} m_{ij}^{a_{k} ↑} + \sum_{j = n + 1}^{n + s} m_{ij}^{a_{k} ↑} = \sum_{j = 1}^{n} m_{ij}^{a_{k}} + \sum_{j = 1}^{s} p_{ij}^{a_{k} ↑}$ . According to Definition 4, we have that $μ_{i}^{a_{k} ↑} = μ_{i}^{a_{k}} + \sum_{j = 1}^{s} p_{ij}^{a_{k} ↑}$ . On the other hand, by Definition 4, $μ_{i}^{a_{k} ↑} = \sum_{j = 1}^{n + s} m_{ij}^{a_{k} ↑} = \sum_{j = 1}^{n} m_{ij}^{a_{k} ↑} + \sum_{j = n + 1}^{n + s} m_{ij}^{a_{k} ↑}$ holds for any i ∈ {n + 1, n + 2, …, n + s}. By Theorem 4, $m_{ij}^{a_{k} ↑} = q_{i - n, j}^{a_{k} ↑}$ holds for any j ∈ {1, 2, …, n}, and $m_{ij}^{a_{k} ↑} = z_{i, j - n}^{a_{k} ↑}$ holds for any j ∈ {n + 1, n + 2, …, n + s}. Therefore, we have that $μ_{i}^{a_{k} ↑} = \sum_{j = 1}^{n} q_{i - n, j}^{a_{k} ↑} + \sum_{j = 1}^{s} z_{i - n, j}^{a_{k} ↑}$ for any i ∈ {n + 1, n + 2, …, n + s}.□

According to Theorem 5, we can update the induced diagonal matrix of each granular structure based on previously calculated results and incremental relation matrices, which can reduce some unnecessary calculations. When adding an object set, the following example is to state the incremental mechanism for updating the induced diagonal matrix.

Example 3. (Continuation of Example 2) When adding the object set U^Δ into U, according to Theorem 5, we can calculate the element $μ_{i}^{a_{1} ↑}$ for any i ∈ {1, 2, …, 8} in the updated induced diagonal matrix $Λ_{a_{1}}^{Δ}$ by using previously calculated result $μ_{i}^{a_{1}}$ for any i ∈ {1, 2, …, 8} and the incremental relation matrix $P_{a_{1}}^{Δ}$ as follows:

$\begin{matrix} μ_{1}^{a_{1} ↑} = μ_{1}^{a_{1}} + \sum_{j = 1}^{3} p_{1, j}^{a_{1} ↑} = 4, μ_{2}^{a_{1} ↑} = μ_{2}^{a_{1}} + \sum_{j = 1}^{3} p_{2, j}^{a_{1} ↑} = 4, \\ μ_{3}^{a_{1} ↑} = μ_{3}^{a_{1}} + \sum_{j = 1}^{3} p_{3, j}^{a_{1} ↑} = 4, μ_{4}^{a_{1} ↑} = μ_{4}^{a_{1}} + \sum_{j = 1}^{3} p_{4, j}^{a_{1} ↑} = 3, \\ μ_{5}^{a_{1} ↑} = μ_{5}^{a_{1}} + \sum_{j = 1}^{3} p_{5, j}^{a_{1} ↑} = 4, μ_{6}^{a_{1} ↑} = μ_{6}^{a_{1}} + \sum_{j = 1}^{3} p_{6, j}^{a_{1} ↑} = 3, \\ μ_{7}^{a_{1} ↑} = μ_{7}^{a_{1}} + \sum_{j = 1}^{3} p_{7, j}^{a_{1} ↑} = 4, μ_{8}^{a_{1} ↑} = μ_{8}^{a_{1}} + \sum_{j = 1}^{3} p_{8, j}^{a_{1} ↑} = 4 . \end{matrix}$

Similarly, we calculate the element $μ_{i}^{a_{1} ↑}$ for any i ∈ {9, 10, 11} in $Λ_{a_{1}}^{Δ}$ by utilizing the incremental relation matrices $Q_{a_{1}}^{Δ}$ and $Z_{a_{1}}^{Δ}$ as follows: $μ_{9}^{a_{1} ↑} = \sum_{j = 1}^{8} q_{1, j}^{a_{1} ↑} + \sum_{j = 1}^{3} z_{1, j}^{a_{1} ↑} = 3$ , $μ_{10}^{a_{1} ↑} = \sum_{j = 1}^{8} q_{2, j}^{a_{1} ↑} + \sum_{j = 1}^{3} z_{2, j}^{a_{1} ↑} = 4$ , $μ_{11}^{a_{1} ↑} = \sum_{j = 1}^{8} q_{3, j}^{a_{1} ↑} + \sum_{j = 1}^{3} z_{3, j}^{a_{1} ↑} = 4$ .

Thus, we have $Λ_{a_{1}}^{Δ} = diag [1 / 4, 1 / 4, 1 / 4, 1 / 3, 1 / 4,$ 1/3, 1/4, 1/4, 1/3, 1/4, 1/4]. Analogously, we update the induced diagonal matrices of a₂ and a₃ as follows: $Λ_{a_{2}}^{Δ} = diag [1 / 4, 1 / 3, 1 / 4, 1 / 4, 1 / 4,$ 1/4, 1/3, 1/4, 1/3, 1/4, 1/4], $Λ_{a_{3}}^{Δ} = diag [1 / 5, 1 / 5, 1 / 3, 1 / 3, 1 / 5, 1 / 3, 1 / 5, 1 / 3, 1 / 3,$ 1/5, 1/3].

On the basis of three incremental relation matrices and the updated column vector, when an object set U^Δ is added into information systems, the updating mechanism for the intermediate matrix of each granular structure is demonstrated in the following theorem.

Theorem 6. Let IS = (U, A, V, f), where A = {a_k|k ∈ {1, 2, …, m}} and U = {x_i|i ∈ {1, 2, …, n}}. When an object set U^Δ = {x_n+1, x_n+2, …, x_n+s} is added into U, $M_{a_{k}}^{Δ} = (m_{ij}^{a_{k} ↑})_{(n + s) \times (n + s)}$ is the updated equivalence relation matrix of a_k and $M_{a_{k}}^{Δ} \cdot F^{Δ} (X) = [φ_{1}^{a_{k} ↑}, φ_{2}^{a_{k} ↑}, \dots, φ_{n + s}^{a_{k} ↑}]^{T}$ is the updated intermediate matrix of a_k. $P_{a_{k}}^{Δ} = (p_{ij}^{a_{k} ↑})_{n \times s}$ , $Q_{a_{k}}^{Δ} = (q_{ij}^{a_{k} ↑})_{s \times n}$ , and $Z_{a_{k}}^{Δ} = (z_{ij}^{a_{k} ↑})_{s \times s}$ are incremental relation matrices. Then, the following result holds for the intermediate matrix of a_k: $φ_{i}^{a_{k} ↑} = {\begin{matrix} φ_{i}^{a_{k}} + \sum_{j = n + 1}^{n + s} p_{i, j - n}^{a_{k} ↑} \times f_{j}^{↑}, & if i \in {1, 2, \dots, n}; \\ \sum_{j = 1}^{n} q_{i - n, j}^{a_{k} ↑} \times f_{j}^{↑} + \sum_{j = n + 1}^{n + s} z_{i - n, j - n}^{a_{k} ↑} \times f_{j}^{↑}, & if i \in {n + 1, n + 2, \dots, n + s} . \end{matrix}$ (20) where “×” represents the standard multiplication.

Proof. Assume that an object set U^Δ = {x_n+1, x_n+2, …, x_n+s} is added into U, according to Definition 5, for any k ∈ {1, 2, …, m}, we have $φ_{i}^{a_{k} ↑} = \sum_{j = 1}^{n + s} m_{ij}^{a_{k} ↑} \times f_{j}^{↑} = \sum_{j = 1}^{n} m_{ij}^{a_{k} ↑} \times f_{j}^{↑} + \sum_{j = n + 1}^{n + s} m_{ij}^{a_{k} ↑} \times f_{j}^{↑}$ for any i ∈ {1, 2, …, n}. In addition, $m_{ij}^{a_{k} ↑} = m_{ij}^{a_{k}}$ and $f_{j}^{↑} = f_{j}$ holds for any i, j ∈ {1, 2, …, n}. Thus, according to Definition 5, $\sum_{j = 1}^{n} m_{ij}^{a_{k} ↑} \times f_{j}^{↑} = \sum_{j = 1}^{n} m_{ij}^{a_{k}} \times f_{j} = φ_{i}^{a_{k}}$ holds for any i ∈ {1, 2, …, n}. Furthermore, for any i ∈ {1, 2, …, n} and j ∈ {n + 1, n + 2, …, n + s}, we have that $m_{ij}^{a_{k} ↑} = p_{i, j - n}^{a_{k} ↑}$ . Thus, $\sum_{j = n + 1}^{n + s} m_{ij}^{a_{k} ↑} = \sum_{j = n + 1}^{n + s} p_{i, j - n}^{a_{k} ↑}$ holds for any i ∈ {1, 2, …, n}. Then, we have $φ_{i}^{a_{k} ↑} = \sum_{j = 1}^{n} m_{ij}^{a_{k} ↑} \times f_{j}^{↑} + \sum_{j = n + 1}^{n + s} m_{ij}^{a_{k} ↑} \times f_{j}^{↑} = φ_{i}^{a_{k}} + \sum_{j = n + 1}^{n + s} p_{i, j - n}^{a_{k} ↑} \times f_{j}^{↑}$ . On the other hand, after adding multiple objects, by Definition 5, $φ_{i}^{a_{k} ↑} = \sum_{j = 1}^{n + s} m_{ij}^{a_{k} ↑} \times f_{j}^{↑} = \sum_{j = 1}^{n} m_{ij}^{a_{k} ↑} \times f_{j}^{↑} + \sum_{j = n + 1}^{n + s} m_{ij}^{a_{k} ↑} \times f_{j}^{↑}$ holds for any i ∈ {n + 1, n + 2, …, n + s}. Moreover, by Theorem 4, $m_{ij}^{a_{k} ↑} = q_{i - n, j}^{a_{k} ↑}$ holds for any j ∈ {1, 2, …, n} and $m_{ij}^{a_{k} ↑} = z_{i - n, j - n}^{a_{k} ↑}$ holds for any j ∈ {n + 1, n + 2, …, n + s}. Therefore, we have $φ_{i}^{a_{k} ↑} = \sum_{j = 1}^{n} q_{i - n, j}^{a_{k} ↑} \times f_{j}^{↑} + \sum_{j = n + 1}^{n + s} z_{i - n, j - n}^{a_{k} ↑} \times f_{j}^{↑}$ . □

Example 4. (Continuation of Examples 1 and 2) When adding the object set U^Δ into U, according to Theorem 6, we can update the intermediate matrix of the granular structure a₁ as follows: $\begin{matrix} φ_{1}^{a_{1} ↑} = φ_{1}^{a_{1}} + \sum_{j = 9}^{11} p_{1, j - 8}^{a_{1} ↑} \times f_{j}^{↑} = 1, \\ φ_{2}^{a_{1} ↑} = φ_{2}^{a_{1}} + \sum_{j = 9}^{11} p_{2, j - 8}^{a_{1} ↑} \times f_{j}^{↑} = 1, \\ φ_{3}^{a_{1} ↑} = φ_{3}^{a_{1}} + \sum_{j = 9}^{11} p_{3, j - 8}^{a_{1} ↑} \times f_{j}^{↑} = 1, \\ φ_{4}^{a_{1} ↑} = φ_{4}^{a_{1}} + \sum_{j = 9}^{11} p_{4, j - 8}^{a_{1} ↑} \times f_{j}^{↑} = 3, \\ φ_{5}^{a_{1} ↑} = φ_{5}^{a_{1}} + \sum_{j = 9}^{11} p_{5, j - 8}^{a_{1} ↑} \times f_{j}^{↑} = 1, \\ φ_{6}^{a_{1} ↑} = φ_{6}^{a_{1}} + \sum_{j = 9}^{11} p_{6, j - 8}^{a_{1} ↑} \times f_{j}^{↑} = 3, \\ φ_{7}^{a_{1} ↑} = φ_{7}^{a_{1}} + \sum_{j = 9}^{11} p_{7, j - 8}^{a_{1} ↑} \times f_{j}^{↑} = 1, \\ φ_{8}^{a_{1} ↑} = φ_{8}^{a_{1}} + \sum_{j = 9}^{11} p_{8, j - 8}^{a_{1} ↑} \times f_{j}^{↑} = 1, \end{matrix}$ $\begin{matrix} φ_{9}^{a_{1} ↑} = \sum_{j = 1}^{8} q_{1, j}^{a_{1} ↑} \times f_{j}^{↑} + \sum_{j = 9}^{11} z_{1, j - 8}^{a_{1} ↑} \times f_{j}^{↑} = 3, \\ φ_{10}^{a_{1} ↑} = \sum_{j = 1}^{8} q_{2, j}^{a_{1} ↑} \times f_{j}^{↑} + \sum_{j = 9}^{11} z_{2, j - 8}^{a_{1} ↑} \times f_{j}^{↑} = 1, \\ φ_{11}^{a_{1} ↑} = \sum_{j = 1}^{8} q_{3, j}^{a_{1} ↑} \times f_{j}^{↑} + \sum_{j = 9}^{11} z_{3, j - 8}^{a_{1} ↑} \times f_{j}^{↑} = 1 . \end{matrix}$ Thus, we have $M_{a_{1}}^{Δ} \cdot F^{Δ} (X) = [1, 1, 1, 3, 1, 3, 1, 1, 3, 1, 1]^{T}$ . Analogously, we update the intermediate matrices of a₂ and a₃ as follows: $M_{a_{2}}^{Δ} \cdot F^{Δ} (X) = [0, 2, 3, 3, 0, 3, 2, 0, 2, 3, 0]^{T}$ ; $M_{a_{3}}^{Δ} \cdot F^{Δ} (X) = [1, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2]^{T} .$

As a consequence, according to Definitions 5 and 6, Theorems 1 and 2 which are presented in Section 2.2, we can easily calculate the column vectors of the updated multigranulation approximations when adding the object set U^Δ as follows:

${\begin{matrix} F (\underline{\sum_{k = 1}^{3} a_{k}^{O}} (X)^{'}) = {[0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0]}^{T}; \\ F (\bar{\sum_{k = 1}^{3} a_{k}^{O}} (X)^{'}) = {[0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0]}^{T}; \\ F (\underline{\sum_{k = 1}^{3} a_{k}^{P}} (X)^{'}) = {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]}^{T}; \\ F (\bar{\sum_{k = 1}^{3} a_{k}^{P}} (X)^{'}) = {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]}^{T} . \end{matrix}$

Finally, by Eq. (8), we can calculate the updated multigranulation approximations as follows:

${\begin{matrix} \underline{\sum_{k = 1}^{3} a_{k}^{O}} (X)^{'} = {x_{4}, x_{6}, x_{9}}; \\ \bar{\sum_{k = 1}^{3} a_{k}^{O}} (X)^{'} = {x_{2}, x_{3}, x_{4}, x_{6}, x_{7}, x_{9}, x_{10}}; \\ \underline{\sum_{k = 1}^{3} a_{k}^{P}} (X)^{'} = \emptyset; \\ \bar{\sum_{k = 1}^{3} a_{k}^{P}} (X)^{'} = {x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}, x_{7}, x_{8}, x_{9}, x_{10}, x_{11}} . \end{matrix}$

From the above results, when adding multiple objects, we can conclude that the multigranulation lower and upper approximations of a target concept obtained by means of incremental mechanisms are equivalent to that of the defined matrix-based approach in Section 2.2. Compared with the defined matrix-based approach, the proposed incremental mechanisms can achieve substantially promising results while reducing some redundant computations.

3.2 Deleting multiple objects

Let IS = (U, A, V, f), where A = {a_k|k ∈ {1, 2, …, m}}, U = {x_i|i ∈ {1, 2, …, n}} and X ⊆ U. Assume that an object set U^▿ = {x_n-s+1, x_n-s+2, …, x_n} is deleted from U and the granular structures keep unchange. In the following, matrix-based incremental mechanisms for updating approximations of a target concept X in MGRS are developed when multiple objects are deleted from an information system. When deleting an object set U^▿ from U, if the target concept X is changed, then the column vector of X can be updated by the following theorem.

Theorem 7. Let IS = (U, A, V, f), where A = {a_k|k ∈ {1, 2, …, m}}, U = {x_i|i ∈ {1, 2, …, n}}, X ⊆ U. F (X) = [f₁, f₂, …, f_n] ^T is the column vector of X. When an object set U^▿ = {x_n-s+1, x_n-s+2, …, x_n} is deleted from U, the updated column vector of X is denoted as $F^{▿} (X) = [f_{1}^{↓}, f_{2}^{↓}, \dots, f_{n - s}^{↓}]^{T}$ . Let X = X - X^▿ and X^▿ ⊆ U^▿. Then, the column vector of X is updated as

$f_{i}^{↓} = {\begin{matrix} f_{i}, & if i \in {1, 2, \dots, n - s}, \\ NULL, & if i \in {n - s + 1, n - s + 2, \dots, n} . \end{matrix}$ (21)

Proof. Assume that an object set U^▿ = {x_n-s+1, x_n-s+2, …, x_n} is deleted from U, the column vector should be updated to (n - s) rows and one column. By Eq. (8), if x_i ∈ X - X^▿, then $f_{i}^{↓} = f_{i} = 1$ for any i ∈ {1, 2, …, n - s}; otherwise if x_i ∉ X - X^▿, then $f_{i}^{↓} = f_{i} = 0$ . Therefore, $f_{i}^{↓} = f_{i}$ holds for any i ∈ {1, 2, …, n - s}. Furthermore, for any i ∈ {n - s + 1, n - s + 2, …, n}, if x_i is deleted from IS, it implies that f_i should be deleted from the corresponding column vector F (X).

□

Example 5. Assume that the object set U^▿ = {x₇, x₈} in Table 3 is deleted from the universe U. Let X = {x₂, x₃, x₄, x₆}, and X^▿ =∅, by Theorem 7, we have F^▿ (X) = [0, 1, 1, 1, 0, 1] ^T.

Table 3

The object set U^▿ deleted from U

U ^▿	a ₁	a ₂	a ₃
x ₇	med	big	med
x ₈	med	small	low

Theorem 8. Let IS = (U, A, V, f), where A = {a_k|k ∈ {1, 2, …, m}} and U = {x_i|i ∈ {1, 2, …, n}}. $M_{a_{k}} = (m_{ij}^{a_{k}})_{n \times n}$ is the equivalence relation matrix of a_k. When an object set U^▿ = {x_n-s+1, x_n-s+2, …, x_n} is deleted from U, $M_{a_{k}}^{▿} = (m_{ij}^{a_{k} ↓})_{(n - s) \times (n - s)}$ is the updated equivalence relation matrix of a_k. The deleted relation matrices of a_k are denoted as $P_{a_{k}}^{▿} = (p_{ij}^{a_{k} ↓})_{(n - s) \times s}$ , $Q_{a_{k}}^{▿} = (q_{ij}^{a_{k} ↓})_{s \times (n - s)}$ and $Z_{a_{k}}^{▿} = (z_{ij}^{a_{k} ↓})_{s \times s}$ , respectively. Then, we have, $M_{a_{k}} = [\begin{matrix} M_{a_{k}}^{▿} & P_{a_{k}}^{▿} \\ Q_{a_{k}}^{▿} & Z_{a_{k}}^{▿} \end{matrix}],$ (22) where

${\begin{matrix} m_{ij}^{a_{k} ↓} = m_{ij}^{a_{k}}, & if i, j \in {1, 2, \dots, n - s}, \\ p_{ij}^{a_{k} ↓} = m_{i, j + n - s}^{a_{k}}, & if i \in {1, 2, \dots, n - s}, j \in {1, 2, \dots, s} . \end{matrix}$

Proof. Assume that an object set U^▿ = {x_n-s+1, x_n-s+2, …, x_n} is deleted from U, the equivalence relation matrix should be updated to an (n - s) × (n - s) matrix. By Eq. (8), if (x_i, x_j) ∈ R_{a
_k} for any i, j ∈ {1, 2, …, n - s}, then $m_{ij}^{a_{k}} = 1$ and $m_{ij}^{a_{k} ↓} = 1$ hold, else if (x_i, x_j) ∉ R_{a
_k}, then $m_{ij}^{a_{k}} = 0$ and $m_{ij}^{a_{k} ↓} = 0$ hold. Therefore, we have $m_{ij}^{a_{k} ↓} = m_{ij}^{a_{k}}$ . Analogously, we have $p_{ij}^{a_{k} ↓} = m_{i, j + n - s}^{a_{k}}$ for any i ∈ {1, 2, …, n - s} , j ∈ {1, 2, …, s}. On the other hand, when the object set U^▿ = {x_n-s+1, x_n-s+2, …, x_n} is deleted from IS, the relation matrix M_{a
_k} will reduce s rows and s columns. Therefore, the relation matrices $P_{a_{k}}^{▿}$ , $Q_{a_{k}}^{▿}$ and $Z_{a_{k}}^{▿}$ are deleted from M_{a
_k}, respectively. □

In the light of Theorem 8, we can update relation matrix $M_{a_{k}}^{▿}$ and $P_{a_{k}}^{▿}$ of the k-th granular structure, k ∈ {1, 2, …, m}. The incremental mechanism eliminates the unnecessary efforts in calculating relation matrix during the updating process. The following example is to illustrate the incremental mechanism for updating deleted relation matrix $P_{a_{k}}^{▿}$ , which can further be used for updating the induced diagonal matrix and intermediate matrix.

Example 6. When the object set U^▿ = {x₇, x₈} is deleted from the universe U, it can be concluded from Eq. (22) that the deleted relation matrix $P_{a_{k}}^{▿}$ of a_k, k ∈ {1, 2, 3}, is a 6 × 2 matrix. Then, according to Theorem 8, $P_{a_{k}}^{▿} = (p_{ij}^{a_{k} ↓})_{6 \times 2}$ for any k ∈ {1, 2, …, 3} can be updated as follows:

$P_{a_{1}}^{▿} = \begin{matrix} [\begin{matrix} 1 & 1 \\ 0 & 0 \\ 1 & 1 \\ 0 & 0 \\ 0 & 0 \\ 0 & 0 \end{matrix}] \end{matrix}$ , $P_{a_{2}}^{▿} = \begin{matrix} [\begin{matrix} 0 & 1 \\ 1 & 0 \\ 0 & 0 \\ 0 & 0 \\ 0 & 1 \\ 0 & 0 \end{matrix}] \end{matrix}$ , $P_{a_{3}}^{▿} = \begin{matrix} [\begin{matrix} 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 0 \\ 1 & 0 \\ 0 & 0 \end{matrix}] \end{matrix}$ .

When the objects are deleted from the universe, the size of the equivalence relation matrix of each granular structure is decreased. This will result in the change of the elements in the induced diagonal matrix of each granular structure. In the following, we show the updating mechanism for the induced diagonal matrix of each granular structure when an object set U^▿ is deleted from information systems.

Theorem 9. Let IS = (U, A, V, f), where A = {a_k|k ∈ {1, 2, …, m}} and U = {x_i|i ∈ {1, 2, …, n}}. The induced diagonal matrix Λ_{a
_k} of a_k on U is denoted as $Λ_{a_{k}} = diag [1 / μ_{1}^{a_{k}}, 1 / μ_{2}^{a_{k}}, \dots, 1 / μ_{n}^{a_{k}}]$ . When an object set U^▿ = {x_n-s+1, x_n-s+2, …, x_n} is deleted from U, $M_{a_{k}}^{▿} = (m_{ij}^{a_{k} ↓})_{(n - s) \times (n - s)}$ is the updated equivalence relation matrix of a_k and $Λ_{a_{k}}^{▿} = diag [1 / μ_{1}^{a_{k} ↓}, 1 / μ_{2}^{a_{k} ↓}, \dots, 1 / μ_{n - s}^{a_{k} ↓}]$ is the updated induced diagonal matrix of a_k. $P_{a_{k}}^{▿} = (p_{ij}^{a_{k} ↓})_{(n - s) \times s}$ is the deleted relation matrix. Then, the induced diagonal matrix of a_k is updated as:

$μ_{i}^{a_{k} ↓} = {\begin{matrix} μ_{i}^{a_{k}} - \sum_{j = 1}^{s} p_{ij}^{a_{k} ↓}, & if i \in {1, 2, \dots, n - s}, \\ NULL, & if i \in {n - s + 1, n - s + 2, \dots, n} . \end{matrix}$ (23)

Proof. Assume that an object set U^▿ = {x_n-s+1, x_n-s+2, …, x_n} is deleted from U, according to Definition 4, for any k ∈ {1, 2, …, m}, we have $μ_{i}^{a_{k} ↓}$ $= \sum_{j = 1}^{n - s} m_{ij}^{a_{k} ↓} = \sum_{j = 1}^{n - s} m_{ij}^{a_{k}} = \sum_{j = 1}^{n} m_{ij}^{a_{k}} - \sum_{j = n - s + 1}^{n} m_{ij}^{a_{k}}$ for any i ∈ {1, 2, …, n - s}. According to Definition 4, we have $μ_{i}^{a_{k} ↓} = \sum_{j = 1}^{n} m_{ij}^{a_{k}}$ for any i ∈ {1, 2, …, n}. Thus, we can obtain that $μ_{i}^{a_{k} ↓} = μ_{i}^{a_{k}} - \sum_{j = n - s + 1}^{n} m_{ij}^{a_{k}}$ for any i ∈ {1, 2, …, n - s}. In addition, by Theorem 8, we have that $\sum_{j = n - s + 1}^{n} m_{ij}^{a_{k}}$ $= \sum_{j = n - s + 1}^{n} p_{i, j - n + s}^{a_{k} ↓} = \sum_{j = 1}^{s} p_{ij}^{a_{k} ↓}$ for any i ∈ {1, 2, …, n - s}. Therefore, $μ_{i}^{a_{k} ↓} = μ_{i}^{a_{k}} - \sum_{j = n - s + 1}^{n} m_{ij}^{a_{k}} = μ_{i}^{a_{k}} - \sum_{j = 1}^{s} p_{ij}^{a_{k} ↓}$ holds. On the other hand, for any i ∈ {n - s + 1, n - s + 2, …, n}, when the object x_i is deleted from IS, it is implied that $1 / μ_{i}^{a_{k} ↓}$ should be deleted from the induced diagonal matrix $Λ_{a_{k}}^{▿}$ of a_k. □

According to Theorem 9, the induced diagonal matrix $Λ_{a_{k}}^{▿}$ (k ∈ {1, 2, …, m}) can be updated by using previous knowledge. This mechanisms reduces the computational cost while preserving the same computational results. The following example is to illustrate the updating mechanism for calculating the induced diagonal matrix $Λ_{a_{k}}^{▿}$ when deleting an object set.

Example 7. (Continuation of Example 6) When the object set U^▿ = {x₇, x₈} is deleted from the universe U, according to Theorem 9, we can update the induced diagonal matrix of a₁ as follows: $\begin{matrix} μ_{1}^{a_{1} ↓} = μ_{1}^{a_{1}} - \sum_{j = 1}^{2} p_{1, j}^{a_{1} ↓} = 2, \\ μ_{2}^{a_{1} ↓} = μ_{2}^{a_{1}} - \sum_{j = 1}^{2} p_{2, j}^{a_{1} ↓} = 2, \\ μ_{3}^{a_{1} ↓} = μ_{3}^{a_{1}} - \sum_{j = 1}^{2} p_{3, j}^{a_{1} ↓} = 2, \\ μ_{4}^{a_{1} ↓} = μ_{4}^{a_{1}} - \sum_{j = 1}^{2} p_{4, j}^{a_{1} ↓} = 2, \\ μ_{5}^{a_{1} ↓} = μ_{5}^{a_{1}} - \sum_{j = 1}^{2} p_{5, j}^{a_{1} ↓} = 2, \\ μ_{6}^{a_{1} ↓} = μ_{6}^{a_{1}} - \sum_{j = 1}^{2} p_{6, j}^{a_{1} ↓} = 2 . \end{matrix}$

Thus, we have $Λ_{a_{1}}^{▿} = diag [1 / 2, 1 / 2, 1 / 2, 1 / 2, 1 / 2, 1 / 2]$ . Analogously, we can update the induced diagonal matrices of a₂ and a₃ as: $Λ_{a_{2}}^{▿} = diag [1 / 2, 1, 1 / 3, 1 / 3, 1 / 2, 1 / 3]$ and $Λ_{a_{3}}^{▿} = diag [1 / 3, 1 / 3, 1, 1 / 2, 1 / 3, 1 / 2]$ .

The following theorem demonstrates the updating mechanism for the intermediate matrix $M_{a_{k}}^{▿} \cdot F^{▿} (X)$ (k ∈ {1, 2, …, m}) when an object set U^▿ is deleted from information systems.

Theorem 10. Let IS = (U, A, V, f), where A = {a_k|k ∈ {1, 2, …, m}} and U = {x_i|i ∈ {1, 2, …, n}}. When an object set U^▿ = {x_n-s+1, x_n-s+2, …, x_n} is deleted from U, $M_{a_{k}}^{▿} = (m_{ij}^{a_{k} ↓})_{(n - s) \times (n - s)}$ is the updated equivalence relation matrix of a_k and $M_{a_{k}}^{▿} \cdot F^{▿} (X) = [φ_{1}^{a_{k} ↓}, φ_{2}^{a_{k} ↓}, \dots, φ_{n - s}^{a_{k} ↓}]^{T}$ is the updated intermediate matrix of a_k. $P_{a_{k}}^{▿} = (p_{ij}^{a_{k} ↓})_{(n - s) \times s}$ is the deleted relation matrix. Then, the intermediate matrix of a_k is updated as:

$\begin{matrix} φ_{i}^{a_{k} ↓} = {\begin{matrix} φ_{i}^{a_{k}} - \sum_{j = n - s + 1}^{n} p_{i, j - n + s}^{a_{k} ↓} \times f_{j}, if i \in {1, 2, \dots, n - s}, \\ NULL, if i \in {n - s + 1, n - s + 2, \dots, n} . \end{matrix} \end{matrix}$ (24) where “×” represents the standard multiplication.

Proof. Assume that an object set U^▿ = {x_n-s+1, x_n-s+2, …, x_n} is deleted from U, according to Definition 5, for any k ∈ {1, 2, …, m}, we have $φ_{i}^{a_{k} ↓} = \sum_{j = 1}^{n - s} m_{ij}^{a_{k} ↓} \times f_{j}^{↓}$ for any i ∈ {1, 2, …, n - s}. By Theorem 7, $f_{j}^{↓} = f_{j}$ holds for any j ∈ {1, 2, …, n - s}, and by Theorem 4, $m_{ij}^{a_{k} ↓} = m_{ij}^{a_{k}}$ holds for any i, j ∈ {1, 2, …, n - s}. Then $φ_{i}^{a_{k} ↓} = \sum_{j = 1}^{n - s} m_{ij}^{a_{k} ↓} \times f_{j}^{↓} = \sum_{j = 1}^{n} m_{ij}^{a_{k}} \times f_{j} - \sum_{j = n - s + 1}^{n} m_{ij}^{a_{k}} \times f_{j}$ . According to Definition 5, we have $φ_{i}^{a_{k}} = \sum_{j = 1}^{n} m_{ij}^{a_{k}} \times f_{j}$ for any i ∈ {1, 2, …, n}. Therefore $φ_{i}^{a_{k} ↓} = φ_{i}^{a_{k}} - \sum_{j = n - s + 1}^{n} m_{ij}^{a_{k}} \times f_{j}$ . In addition, by Theorem 4, we have that $\sum_{j = n - s + 1}^{n} m_{ij}^{a_{k}} = \sum_{j = n - s + 1}^{n} p_{i, j - n + s}^{a_{k} ↓}$ for any j ∈ {n - s + 1, n - s + 2, …, n}. Then, we can obtain that $φ_{i}^{a_{k} ↓} = φ_{i}^{a_{k}} - \sum_{j = n - s + 1}^{n} p_{i, j - n + s}^{a_{k} ↓} \times f_{j}$ . On the other hand, for any i ∈ {n - s + 1, n - s + 2, …, n}, when the object x_i is deleted from IS, it is implied that $φ_{i}^{a_{k} ↓}$ should be deleted from the intermediate matrix of a_k. □

It can be seen from Theorem 10 that the intermediate matrix $M_{a_{k}}^{▿} \cdot F^{▿} (X)$ (k ∈ {1, 2, …, m}) can be updated according to previous computational results and deleted relation matrix $P_{a_{k}}^{▿}$ , which can accelerate the calculations. Here, we use an example to state the updating mechanism for calculating the updated intermediate matrix $M_{a_{k}}^{▿} \cdot F^{▿} (X)$ when deleting an object set.

Example 8. (Continuation of Examples 5 and 6) When the object set U^▿ = {x₇, x₈} is deleted from the universe U, according to Theorem 10, we can update the intermediate matrix of a₁ as follows: $\begin{matrix} φ_{1}^{a_{1} ↓} = φ_{1}^{a_{1}} - \sum_{j = 7}^{8} p_{1, j - 6}^{a_{1} ↓} \times f_{j} = 1, \\ φ_{2}^{a_{1} ↓} = φ_{2}^{a_{1}} - \sum_{j = 7}^{8} p_{2, j - 6}^{a_{1} ↓} \times f_{j} = 1, \\ φ_{3}^{a_{1} ↓} = φ_{3}^{a_{1}} - \sum_{j = 7}^{8} p_{3, j - 6}^{a_{1} ↓} \times f_{j} = 1, \\ φ_{4}^{a_{1} ↓} = φ_{4}^{a_{1}} - \sum_{j = 7}^{8} p_{4, j - 6}^{a_{1} ↓} \times f_{j} = 2, \\ φ_{5}^{a_{1} ↓} = φ_{5}^{a_{1}} - \sum_{j = 7}^{8} p_{5, j - 6}^{a_{1} ↓} \times f_{j} = 1, \\ φ_{6}^{a_{1} ↓} = φ_{6}^{a_{1}} - \sum_{j = 7}^{8} p_{6, j - 6}^{a_{1} ↓} \times f_{j} = 2 . \end{matrix}$

Thus, we have $M_{a_{1}}^{▿} \cdot F^{▿} (X) = {[1, 1, 1, 2, 1, 2]}^{T}$ . Analogously, we can update the intermediate matrices of a₂ and a₃ as: $M_{a_{2}}^{▿} \cdot F^{▿} (X) = [0, 1, 3, 3, 0, 3]^{T}$ and $M_{a_{3}}^{▿} \cdot F^{▿} (X) = {[1, 1, 1, 2, 1, 2]}^{T}$ .

Subsequently, according to Definitions 5 and 6, Theorems 1 and 2 in Section 2.2, we can calculate the column vectors of updated multigranulation approximations when deleting the object set U^▿ as follows: ${\begin{matrix} F (\underline{\sum_{k = 1}^{3} a_{k}^{O}} (X)^{'}) = {[0, 1, 1, 1, 0, 1]}^{T}; \\ F (\bar{\sum_{k = 1}^{3} a_{k}^{O}} (X)^{'}) = {[0, 1, 1, 1, 0, 1]}^{T}; \\ F (\underline{\sum_{k = 1}^{3} a_{k}^{P}} (X)^{'}) = {[0, 0, 0, 1, 0, 1]}^{T}; \\ F (\bar{\sum_{k = 1}^{3} a_{k}^{P}} (X)^{'}) = {[1, 1, 1, 1, 1, 1]}^{T} . \end{matrix}$

Finally, by Eq. (8), we can calculate the updated multigranulation approximations as follows: ${\begin{matrix} \underline{\sum_{k = 1}^{3} a_{k}^{O}} (X)^{'} = {x_{2}, x_{3}, x_{4}, x_{6}}; \\ \bar{\sum_{k = 1}^{3} a_{k}^{O}} (X)^{'} = {x_{2}, x_{3}, x_{4}, x_{6}}; \\ \underline{\sum_{k = 1}^{3} a_{k}^{P}} (X)^{'} = {x_{4}, x_{6}}; \\ \bar{\sum_{k = 1}^{3} a_{k}^{P}} (X)^{'} = {x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}} . \end{matrix}$

From the above results, we can conclude that, when deleting multiple objects, the multigranulation lower and upper approximations of the target concept obtained by taking advantage of the incremental mechanisms are equivalent to those of the defined matrix-based approach in Section 2.2. Compared with the defined matrix-based approach, the proposed incremental mechanisms make fully use of previous knowledge to reduce the computational cost of acquiring knowledge.

4 Incremental algorithms for updating approximations in MGRS when adding or deleting multiple objects

The matrix-based static algorithm for computing approximations in multigranulation rough sets (Abbreviated as SACAM) has been proposed in our previous work [12]. Therefore, in this section, based on the proposed incremental mechanisms, we focus on developing the matrix-based incremental algorithms for updating approximations when adding or deleting multiple objects.

4.1 Incremental algorithm for updating approximations in MGRS when adding multiple objects

Algorithm 1, which is abbreviated as IAUAMA, is a matrix-based incremental algorithm for updating approximations in the context of MGRS when an object set U^Δ is added into U. Steps 2-5 update the column vector according to Theorem 3, whose time complexity is O (|U| + |U^Δ|). Steps 6-14 update the relation matrix of a_k, k ∈ {1, 2, …, m} by Theorem 4, whose time complexity is O (m (|U^Δ|² + |U||U^Δ|)). Steps 15-20 update the diagonal matrix and intermediate matrix according to Theorems 5 and 6, whose time complexity is O (m (|U||U^Δ| + |U^Δ|²)). Steps 21-22 compute the column matrix, whose time complexity is O (m (|U| + |U^Δ|)). Steps 23-24 compute the cut matrices of a_k by Definition 6, whose time complexity is O (m (|U| + |U^Δ|)). Steps 25-26 compute the column vectors of multigranulation rough approximations, whose time complexity is O (m (|U| + |U^Δ|)). Step 27 outputs the updated approximations of MGRS, whose time complexity is O (|U| + |U^Δ|). To be brief, the total time complexity of IAUAMA is O (m (|U||U^Δ| + |U^Δ|²)).

Table 4 indicates a comparison of time complexity between SACAM and IAUAMA for updating multigranulation approximations while adding multiple objects. It is easy to see from Table 4 that the computational time complexity of the incremental algorithm IAUAMA is better than that of SACAM when an object set U^Δ is added into U. Therefore, the incremental algorithm IAUAMA is more efficient than static algorithm SACAM when multiple objects are added into information systems.

Table 4
The time complexity of SACAM and IAUAMA

Algorithms Time complexity

SACAM O (m (|U|² + 2|U||U^Δ| + |U^Δ|²))

IAUAMA O (m (|U||U^Δ| + |U^Δ|²))

Algorithms	Time complexity
SACAM	O (m (\|U\|² + 2\|U\|\|U^Δ\| + \|U^Δ\|²))
IAUAMA	O (m (\|U\|\|U^Δ\| + \|U^Δ\|²))

4.2 Incremental algorithm for updating approximations in MGRS when deleting multiple objects

Algorithm 2, which is abbreviated as IAUAMD, is a matrix-based incremental algorithm for updating approximations in multigranulation rough sets when an object set U^▿ is deleted from U. Steps 2-3 update the column vector by Theorem 7, whose time complexity is O (|U^▿|). Steps 4-7 update the relation matrix of a_k k ∈ {1, 2, …, m} by Theorem 8, whose time complexity is O (m|U^▿| (|U| - |U^▿|)). Steps 8-10 update the diagonal matrix and intermediate matrix according to Theorems 9 and 10, whose time complexity is O (m|U^▿| (|U| - |U^▿|)). Steps 11-12 compute the column matrix, whose time complexity is O (m (|U| - |U^▿|)). Steps 13-14 compute the cut matrices of the granular structure a_k by Definition 6, whose time complexity is O (m (|U| - |U^▿|)). Steps 15-16 compute the column vectors of multigranulation rough approximations, whose time complexity is O (m (|U| - |U^▿|)). Step 17 outputs the updated approximations of multigranulation rough sets, whose time complexity is O (|U| - |U^▿|). Hence, the total time complexity of the incremental algorithm IAUAMD is O (m|U^▿| (|U| - |U^▿|)).

Table 5 refers to a comparison of time complexity of updating multigranulation approximations while deleting multiple objects between SACAM and IAUAMD. It can be observed from Table 5 that |U| - |U^▿| is usually greater than |U^▿| when the number of deleted objects is very small. Hence, the time complexity of updating multigranulation approximations by the proposed incremental algorithm IAUAMD is usually better than that of SACAM when an object set U^▿ is deleted from U. Therefore, the incremental algorithm IAUAMD is more efficient than SACAM when multiple objects are deleted from information systems.

Table 5
The time complexity of SACAM and IAUAMD

Algorithms Time complexity

SACAM O (m (|U|² - 2|U||U^▿| + |U^▿|²))

IAUAMD O (m (|U||U^▿| - |U^▿|²))

Algorithms	Time complexity
SACAM	O (m (\|U\|² - 2\|U\|\|U^▿\| + \|U^▿\|²))
IAUAMD	O (m (\|U\|\|U^▿\| - \|U^▿\|²))

5 Experimental evaluations

To evaluate the performance of the proposed incremental algorithms for updating multigranulation approximations, comparative experiments are conducted in the empirical study. Eight data sets downloaded from UCI Repository of Machine Learning Database 1 are used in the experiments. The detailed description of experimental data sets is outlined in Table 6. Furthermore, in order to construct a multigranulation space, each attribute is considered as a granular structure. The algorithms are performed on a personal computer with operation system Windows 7, Intel(R) Core(TM) i3-4010U CPU@1.70GHz and 4GB memory. Moreover, the algorithms are developed in Java and the software being used is Eclipse LUNA. In our experiments, we set α = 1 and β = 1 when updating lower approximation in MGRS, whereas we set α = 0 and β = 1 when updating upper approximation in MGRS.

Table 6
The description of data sets

ID Data sets # Samples # Attributes # Classes

1 Flags 194 30 7

2 Dermatology 366 34 6

3 Balance scale 625 5 5

4 Tic-tac-toe 958 10 2

5 Solar flare 1389 30 3

6 Car evaluation 1728 7 4

7 Mushroom 8124 22 2

8 Nursery 12960 8 5

ID	Data sets	# Samples	# Attributes	# Classes
1	Flags	194	30	7
2	Dermatology	366	34	6
3	Balance scale	625	5	5
4	Tic-tac-toe	958	10	2
5	Solar flare	1389	30	3
6	Car evaluation	1728	7	4
7	Mushroom	8124	22	2
8	Nursery	12960	8	5

5.1 Performance comparison of SACAM and IAUAMA while adding multiple objects

In this subsection, to compare the performance of the static algorithm SACAM and the proposed incremental algorithm IAUAMA versus different adding ratio when adding multiple objects, we select 50% objects of each data set as the original data set, and select 10%, 20%, …, 100% from the remaining 50% objects as the incremental data set. The computational times of SACAM and IAUAMA for updating multigranulation approximations can be obtained when adding multiple objects, respectively. Let R_a be ratio of the size of adding objects and original objects, denoted as adding ratio, changing from 10% to 100% and the size of increase step is 10%. The comparison of computational times between SACAM and IAUAMA versus different adding ratios of the objects is shown in Table 7. In addition, the corresponding trend lines of computational time under different adding ratios are shown in Fig 1, where the square line denotes the computational time of SACAM and the star line stands for the computational time of IAUAMA. In each sub-figure of Fig. 1, the x-coordinate pertains to the adding ratio of adding objects which starts from 10% to 100% of the remaining 50% objects and the y-coordinate concerns the computational times of SACAM and IAUAMA.

Table 7
A comparison of SACAM and IAUAMA versus different adding ratios of the objects

Adding ratio Flags Dermatology Balance scale Tic-tac-toe

SACAM IAUAMA SACAM IAUAMA SACAM IAUAMA SACAM IAUAMA

10% 0.141 0.026 0.302 0.156 0.195 0.056 0.431 0.113

20% 0.148 0.030 0.324 0.213 0.201 0.084 0.496 0.170

30% 0.155 0.034 0.390 0.284 0.233 0.098 0.491 0.210

40% 0.159 0.035 0.428 0.323 0.249 0.112 0.556 0.256

50% 0.170 0.046 0.452 0.316 0.253 0.110 0.564 0.287

60% 0.195 0.061 0.462 0.331 0.301 0.112 0.597 0.407

70% 0.215 0.059 0.471 0.337 0.294 0.158 0.682 0.479

80% 0.222 0.061 0.478 0.394 0.350 0.152 0.702 0.579

90% 0.244 0.070 0.505 0.442 0.349 0.185 0.770 0.617

100% 0.280 0.083 0.560 0.448 0.397 0.193 0.817 0.624

Adding ratio Solar flare Car evaluation Mushroom Nursery

SACAM IAUAMA SACAM IAUAMA SACAM IAUAMA SACAM IAUAMA

10% 0.727 0.417 0.712 0.249 7.891 2.049 7.083 2.229

20% 0.841 0.551 0.867 0.430 9.238 3.065 8.501 3.374

30% 0.941 0.643 0.963 0.560 11.264 4.423 11.262 4.510

40% 1.048 0.789 1.077 0.756 14.015 5.668 14.023 5.959

50% 1.235 0.839 1.213 0.841 16.330 7.319 16.271 7.715

60% 1.349 0.870 1.303 0.940 20.505 9.010 19.223 9.207

70% 1.486 0.929 1.511 1.981 24.109 10.963 21.470 11.175

80% 1.626 0.953 1.725 1.017 27.578 13.225 25.936 13.254

90% 2.205 1.042 1.929 1.202 31.696 15.659 28.109 15.130

100% 2.295 1.251 1.944 1.216 38.109 18.505 32.327 17.902

Adding ratio	Flags		Dermatology		Balance scale		Tic-tac-toe
10%	0.141	0.026	0.302	0.156	0.195	0.056	0.431	0.113
20%	0.148	0.030	0.324	0.213	0.201	0.084	0.496	0.170
30%	0.155	0.034	0.390	0.284	0.233	0.098	0.491	0.210
40%	0.159	0.035	0.428	0.323	0.249	0.112	0.556	0.256
50%	0.170	0.046	0.452	0.316	0.253	0.110	0.564	0.287
60%	0.195	0.061	0.462	0.331	0.301	0.112	0.597	0.407
70%	0.215	0.059	0.471	0.337	0.294	0.158	0.682	0.479
80%	0.222	0.061	0.478	0.394	0.350	0.152	0.702	0.579
90%	0.244	0.070	0.505	0.442	0.349	0.185	0.770	0.617
100%	0.280	0.083	0.560	0.448	0.397	0.193	0.817	0.624
Adding ratio	Solar flare		Car evaluation		Mushroom		Nursery
	SACAM	IAUAMA	SACAM	IAUAMA	SACAM	IAUAMA	SACAM	IAUAMA
10%	0.727	0.417	0.712	0.249	7.891	2.049	7.083	2.229
20%	0.841	0.551	0.867	0.430	9.238	3.065	8.501	3.374
30%	0.941	0.643	0.963	0.560	11.264	4.423	11.262	4.510
40%	1.048	0.789	1.077	0.756	14.015	5.668	14.023	5.959
50%	1.235	0.839	1.213	0.841	16.330	7.319	16.271	7.715
60%	1.349	0.870	1.303	0.940	20.505	9.010	19.223	9.207
70%	1.486	0.929	1.511	1.981	24.109	10.963	21.470	11.175
80%	1.626	0.953	1.725	1.017	27.578	13.225	25.936	13.254
90%	2.205	1.042	1.929	1.202	31.696	15.659	28.109	15.130
100%	2.295	1.251	1.944	1.216	38.109	18.505	32.327	17.902

Fig. 1

Computational times of SACAM and IAUAMA versus different adding ratios of the objects.

From Fig. 1, it can be observed that the computational times of SACAM and IAUAMA increase with the adding ratio of the objects. Furthermore, according to according to the trendlines of SACAM and IAUAMA, it is clear that IAUAMA is always much fast than SACAM when the adding ratio of the objects increases. The reason should be that IAUAMA can be capable of updating relation matrix and intermediate matrix of each granular structure based on the utilization of previous information without re-training from scratch. However, SACAM needs to re-calculate relation matrix and intermediate matrix of each granular structure from the very beginning. In summary, to accelerate the processing of dynamic information systems, the proposed incremental algorithm is to reduce the calculation of relative matrices by means of incremental mechanisms. Therefore, the proposed incremental algorithm IAUAMA is more efficient to update multigranulation approximations while adding multiple objects.

To further demonstrate the advantage of IAUAMA, an incremental speedup [13] is denoted as IncS=T_s/T_i, where T_s is the computational time of the static algorithm and T_i is the computational time of the incremental algorithm. Table 8 indicates the incremental speedup versus different adding ratios of the objects. The last row records the average speedup on eight data sets. It is worth noting that the incremental algorithm IAUAMA achieves 1.742× to 5.350× speedup over the static algorithm SACAM with the adding ratio of 10%. Obviously, from the perspective of speedup, the incremental algorithm IAUAMA performs better than the static algorithm SACAM with the increasing of adding ratio.

Table 8

The incremental speedup versus the adding ratio of the objects

Data sets	Adding ratio
	10%	20%	30%	40%	50%	60%	70%	80%	90%	100%
Flags	5.350	4.950	4.606	4.517	3.685	3.203	3.699	3.632	3.509	3.359
Dermatology	1.933	1.517	1.371	1.324	1.430	1.397	1.400	1.213	1.142	1.249
Balance scale	3.470	2.390	2.390	2.213	2.311	2.695	1.856	2.304	1.886	2.056
Tic-tac-toe	3.817	2.908	2.334	1.174	1.963	1.469	1.424	1.222	1.249	1.310
Solar flare	1.742	1.526	1.465	1.328	1.472	1.550	1.600	1.706	1.944	1.835
Car evaluation	2.863	2.017	1.715	1.425	1.442	1.385	1.574	1.695	1.605	1.599
Mushroom	3.851	3.014	2.547	2.473	2.231	2.276	2.199	2.085	2.024	2.059
Nursery	3.178	2.520	2.497	2.353	2.109	2.088	1.921	1.957	1.858	1.806
Average	3.276	2.605	2.366	2.101	2.080	2.008	1.959	1.977	1.902	1.909

5.2 Performance comparison of SACAM and IAUAMD while deleting multiple objects

In this subsection, to compare the performance of the static algorithm SACAM and the proposed incremental algorithm IAUAMD versus different deleting ratios when deleting multiple objects, we take out the whole data set as the original objects, and select 10%, 20%, …, 90% from the whole data set as the deleting objects. The computational times of SACAM and IAUAMD for updating multigranulation approximations can be obtained when deleting multiple objects, respectively. Let R_d be ratio of the size of deleting objects and original objects, denoted as deleting ratio, changing from 10% to 90% and the size of increase step is 10%. Moreover,the comparison of computational times between SACAM and IAUAMD versus different deleting ratios of the objects is shown in Table 9. The trendlines of computational time in terms of different deleting ratios are shown in Fig. 2. In addition, the square line refers to the computational time of SACAM whereas the star line represents the computational time of IAUAMD. In each sub-figure of Fig. 2, the x-coordinate pertains to the incremental ratio of deleting objects which starts from 10% to 90% of the original objects and the y-coordinate concerns the computational times consumed by SACAM and IAUAMD.

Table 9
A comparison of SACAM and IAUAMD versus different deleting ratios of the objects

Deleting ratio Flags Dermatology Balance scale Tic-tac-toe

SACAM IAUAMD SACAM IAUAMD SACAM IAUAMD SACAM IAUAMD

10% 0.244 0.079 0.477 0.214 0.356 0.141 0.694 0.478

20% 0.199 0.084 0.416 0.209 0.283 0.137 0.579 0.428

30% 0.166 0.077 0.398 0.226 0.242 0.124 0.530 0.386

40% 0.141 0.078 0.315 0.214 0.201 0.103 0.474 0.358

50% 0.130 0.065 0.268 0.169 0.149 0.070 0.408 0.340

60% 0.117 0.063 0.218 0.111 0.135 0.043 0.336 0.332

70% 0.096 0.046 0.149 0.101 0.120 0.044 0.232 0.309

80% 0.075 0.034 0.121 0.089 0.099 0.057 0.140 0.210

90% 0.058 0.023 0.083 0.067 0.067 0.021 0.101 0.145

Deleting ratio Solar flare Car evaluation Mushroom Nursery

SACAM IAUAMD SACAM IAUAMD SACAM IAUAMD SACAM IAUAMD

10% 1.713 0.895 1.395 0.469 27.590 3.458 25.357 3.732

20% 1.375 0.805 1.153 0.519 21.050 3.149 18.569 3.451

30% 1.040 0.708 0.840 0.522 14.332 3.014 12.910 3.248

40% 0.836 0.689 0.709 0.491 9.458 2.910 8.184 2.702

50% 0.592 0.568 0.562 0.487 5.389 2.698 5.218 2.605

60% 0.556 0.532 0.497 0.413 3.987 2.437 3.077 2.429

70% 0.438 0.519 0.380 0.362 2.467 1.929 1.888 1.941

80% 0.267 0.492 0.256 0.276 1.082 1.528 0.871 1.572

90% 0.142 0.355 0.149 0.156 0.366 0.896 0.405 0.831

Deleting ratio	Flags		Dermatology		Balance scale		Tic-tac-toe
10%	0.244	0.079	0.477	0.214	0.356	0.141	0.694	0.478
20%	0.199	0.084	0.416	0.209	0.283	0.137	0.579	0.428
30%	0.166	0.077	0.398	0.226	0.242	0.124	0.530	0.386
40%	0.141	0.078	0.315	0.214	0.201	0.103	0.474	0.358
50%	0.130	0.065	0.268	0.169	0.149	0.070	0.408	0.340
60%	0.117	0.063	0.218	0.111	0.135	0.043	0.336	0.332
70%	0.096	0.046	0.149	0.101	0.120	0.044	0.232	0.309
80%	0.075	0.034	0.121	0.089	0.099	0.057	0.140	0.210
90%	0.058	0.023	0.083	0.067	0.067	0.021	0.101	0.145
Deleting ratio	Solar flare		Car evaluation		Mushroom		Nursery
	SACAM	IAUAMD	SACAM	IAUAMD	SACAM	IAUAMD	SACAM	IAUAMD
10%	1.713	0.895	1.395	0.469	27.590	3.458	25.357	3.732
20%	1.375	0.805	1.153	0.519	21.050	3.149	18.569	3.451
30%	1.040	0.708	0.840	0.522	14.332	3.014	12.910	3.248
40%	0.836	0.689	0.709	0.491	9.458	2.910	8.184	2.702
50%	0.592	0.568	0.562	0.487	5.389	2.698	5.218	2.605
60%	0.556	0.532	0.497	0.413	3.987	2.437	3.077	2.429
70%	0.438	0.519	0.380	0.362	2.467	1.929	1.888	1.941
80%	0.267	0.492	0.256	0.276	1.082	1.528	0.871	1.572
90%	0.142	0.355	0.149	0.156	0.366	0.896	0.405	0.831

Fig. 2

Computational times of SACAM and IAUAMD versus different deleting ratios of the objects.

According to Fig. 2, it can be observed that the computational time of SACAM decreases with the deleting ratio of the objects, while that of IAUAMD is fluctuant for some data sets with the deleting ratio of the objects. Furthermore, IAUAMD usually outperforms SACAM until reaching a threshold value of deleting ratio. The reason should be that when deleting the small scale objects from the original datasets, the computational time of IAUAMD by making use of the previous matrices information to update multigranulation approximations is less that of SACAM by recalculating the entire datasets. However, with the increasing of deleting ratio of objects, the advantage of IAUAMD becomes narrower, such as deleting ratio of 70% for data sets Tic-tac-toe, Solar flare and Nursery, deleting ratio of 80% for data sets Car evaluation and Mushroom. Clearly, the algorithm IAUAMD is influenced by the deleting ratio of objects.

Similarly, we make use of an incremental speedup to demonstrate the advantage of the incremental algorithm IAUAMD. Table 10 presents incremental speedup versus different deleting ratio of the objects. The last row records the average speedup on eight data sets. It is worth noting that the incremental algorithm IAUAMD achieves 1.451× to 7.979× speedup over the static algorithm SACAM with the deleting ratio of 10%. With the increasing deleting ratio of the objects, the speedup becomes smaller and smaller. Furthermore, the speedup is less than 1 for data sets Tic-tac-toe, Solar flare and Nursery when the deleting ratio of objects reaches 70%, for most experimental data sets such as Car evaluation, Mushroom, etc, when the deleting ratio of objects reaches 80%. Therefore, the proposed incremental mechanisms can be capable of learning new knowledge incrementally without the need to retrain the entire updated data set, and the results indicate that IAUAMD can effectively reduce the computational time when the deleting ratio of objects is limited to a small-scale.

Table 10

The incremental speedup versus the deleting ratio of the objects

Data sets	Deleting ratio
	10%	20%	30%	40%	50%	60%	70%	80%	90%
Flags	3.096	2.368	2.156	1.803	1.988	1.872	2.069	2.186	2.526
Dermatology	2.230	1.992	1.761	1.477	1.590	1.964	1.469	1.356	1.234
Balance scale	2.531	2.063	1.950	1.942	2.135	3.178	2.723	1.737	3.233
Tic-tac-toe	1.451	1.353	1.376	1.325	1.199	1.011	0.752	0.669	0.700
Solar flare	1.914	1.708	1.469	1.213	1.042	1.045	0.845	0.541	0.440
Car evaluation	2.973	2.219	1.609	1.445	1.155	1.204	1.048	0.930	0.956
Mushroom	7.979	6.685	4.755	3.250	1.997	1.636	1.279	0.708	0.408
Nursery	6.794	5.381	3.975	3.029	2.003	1.267	0.973	0.554	0.487
Average	3.621	2.971	2.381	1.936	1.639	1.647	1.395	1.085	1.248

6 Conclusions

Multigranulation rough set has the abilities to analyze and address the uncertainties from multigranulation perspective so that it has been broadly utilized for solving many kinds of practical problems in various fields. With the increasing volume of data available, the information systems from various fields dynamically vary over time. Therefore, it is meaningful to develop incremental updating mechanisms that are capable of acquiring valuable knowledge in dynamic circumstances. In order to overcome the limitations of the existing incremental approaches for dealing with dynamic multi-source information systems, in this paper, incremental approaches for updating approximations in multigranulation rough sets were proposed under dynamic information systems. Based on the matrix representation of multigranulation approximations, when adding or deleting multiple objects, the updating mechanisms of the equivalence relation matrix, the intermediate matrix and the induced diagonal matrix were investigated. Furthermore, the incremental algorithms were proposed to update approximations in MGRS. Finally, experimental studies regarding eight UCI data sets indicated that the proposed matrix-based incremental algorithms can reduce computational time of updating multigranulation approximations compared with the non-incremental algorithm. Accordingly, the proposed incremental algorithms provide an effective solution to fuse multi-source uncertain information in a dynamic manner. Due to the changing of objects in dynamic information systems, the incremental attribute reduction needs to be updated in the multigranulation environment. Our future work will focus on developing dynamic attribute reduction algorithms in multigranulation rough sets under the variation of information systems.

Acknowledgments

This work is supported by the Natural Science Foundation of the Jiangsu Higher Education Institutions of China (No. 19KJA550002), the Anhui Provincial Natural Science Foundation (Nos. 2008085MF224, 1808085MF170), the Natural Science Foundation of Educational Commission of Anhui Province (No. KJ2018A0432), the Collaborative Innovation Center of Novel Software Technology and Industrialization, the Six Talent Peak Project of Jiangsu Province of China (No. XYDXX-054), the Soochow Scholar Project and the Priority Academic Program Development of Jiangsu Higher Education Institutions.

Declaration of competing interests

We wish to confirm that there are no known conflicts of interest associated with this publication and there has been no significant financial support for this work that could have influenced its outcome.

Footnotes

References

Alcantud

J.C.R.

, Feng

and Yager

R.R.

, An N-soft set approach to rough sets, IEEE Transactions on Fuzzy Systems, (2020), https://doi.org/10.1109/TFUZZ.2019.2946526.

Alcantud

J.C.R.

and Zhan

J.M.

, Multi-granular soft rough covering sets, Soft Computing 24(13) (2020), 9391–9402.

Cai

M.J.

, Lang

G.M.

, Fujita

, Li

Z.Y.

and Yang

, Incremental approaches to updating reducts under dynamic covering granularity, Knowledge-Based Systems 172 (2019), 130–140.

Chen

D.G.

, Yang

Y.Y.

and Dong

, An incremental algorithm for attribute reduction with variable precision rough sets, Applied Soft Computing 45 (2016), 129–149.

Chen

D.G.

, Dong

L.J.

and Mi

J.S.

, Incremental mechanism of attribute reduction based on discernible relations for dynamically increasing attribute, Soft Computing 24 (2020), 321–332.

Chen

H.M.

, Li

T.R.

, Ruan

, Lin

J.H.

and Hu

C.X.

, A rough-set based incremental approach for updating approximations under dynamic maintenance environments, IEEE Transation on Knowledge and Data Engineering 25(2) (2013), 274–284.

Chen

H.M.

, Li

T.R.

, Luo

, Horng

S.J.

and Wang

G.Y.

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

Chen

H.M.

, Li

T.R.

and Ruan

, Maintenance of approximations in incomplete ordered decision systems while attribute values coarsening or refining, Knowledge-Based Systems 31(7) (2012), 140–161.

Dong

L.J.

and Chen

D.G.

Incremental attribute reduction with rough set for dynamic datasets with simultaneously increasing samples and attributes, International Journal of Machine Learning and Cybernetics (2020), https://doi.org/10.1007/s13042-020-01065-y.

10.

Guo

Y.T.

, Tsang

E.C.C.

, Hu

, Lin

X.X.

, Chen

D.G.

, Xu

W.H.

and Sang

B.B.

, Incremental updating approximations for double-quantitative decision-theoretic rough sets with the variation of objects, Knowledge-Based Systems 189 (2020), 105082.

11.

C.X.

and Zhang

, Dynamic dominance based multigranulation rough sets approaches with evolving ordered data, International Journal of Machine Learning and Cybernetics (2020), https://doi.org/10.1007/s13042-020-01119-1.

12.

C.X.

, Liu

S.X.

and Liu

G.X.

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

13.

C.X.

, Zhang

, Wang

B.J.

, Zhang

and Li

F.Z.

, Incremental updating knowledge in neighborhood multigranulation rough sets under dynamic granular structures, Knowledge-Based Systems 163 (2019), 811–829.

14.

, Li

T.R.

, Luo

, Fujita

and Li

S.Y.

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

15.

Huang

, Guo

C.X.

, Zhuang

Y.L.

, Li

H.X.

and Zhou

X.Z.

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

16.

Huang

Q.Q.

, Li

T.R.

, Huang

Y.Y.

, Yang

and Fujita

, Dynamic dominance rough set approach for processing composite ordered data, Knowledge-Based Systems 187 (2020), 104829.

17.

Huang

Y.Y.

, Li

T.R.

, Luo

, Fujita

and Horng

S.J.

, Dynamic variable precision rough set approach for probabilistic set-valued information systems, Knowledge-Based Systems 122 (2017), 131–147.

18.

H.R.

, Li

H.X.

, Yang

X.B.

, Zhou

X.Z.

and Huang

, Cost-sensitive rough set: A multi-granulation approach, Knowledge-Based Systems 123 (2017), 137–153.

19.

H.R.

, Yang

X.B.

, Song

X.N.

and Qi

Y.S.

, Dynamic updating multigranulation fuzzy rough set: approximations and reducts, International Journal of Machine Learning and Cybernetics 5(6) (2014), 981–990.

20.

Lang

G.M.

, Miao

D.Q.

, Cai

M.J.

and Zhang

Z.F.

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

21.

J.H.

, Huang

C.C.

, Qi

J.J.

, Qian

Y.H.

and Liu

W.Q.

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

22.

J.H.

, Ren

, Mei

C.L.

, Qian

Y.H.

and Yang

X.B.

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

23.

S.Y.

and Li

T.R.

, Incremental update of approximations in dominance-based rough sets approach under the variation of attribute values, Information Sciences 294 (2015), 348–361.

24.

T.R.

, Ruan

, Geert

, Song

and Xu

, A rough sets based characteristic relation approach for dynamic attribute generalization in data mining, Knowledge-Based Systems 20(5) (2007), 485–494.

25.

Liang

M.S.

, Mi

J.S.

and Feng

, Optimal granulation selection for similarity measure-based multigranulation intuitionistic fuzzy decision-theoretic rough sets, Journal of Intelligent and Fuzzy Systems 36 (2019), 2495–2509.

26.

Liang

J.Y.

, Wang

, Dang

C.Y.

and Qian

Y.H.

, A group incremental approach to feature selection applying rough set technique, IEEE Transation on Knowledge and Data Engineering 26(2) (2014), 294–308.

27.

Lin

B.Y.

, Zhang

X.Y.

, Xu

W.H.

and Wu

Y.X.

, Dynamically updating approximations based on multi-threshold tolerance relation in incomplete interval-valued decision information systems, Knowledge and Information Systems 62(3) (2020), 1063–1087.

28.

Lin

G.P.

, Liang

J.Y.

and Qian

Y.H.

, Multigranulation rough sets: From partition to covering, Information Sciences 241(12) (2013), 101–118.

29.

Lin

G.P.

, Qian

Y.H.

and Li

J.J.

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

30.

Liu

, Li

T.R.

and Zhang

J.B.

, Incremental updating approximations in probabilistic rough sets under the variation of attributes, Knowledge-Based Systems 73(81) (2015), 81–96.

31.

Liu

, Li

T.R.

and Zhang

J.B.

, A rough set-based incremental approach for learning knowledge in dynamic incomplete information systems, International Journal of Approximate Reasoning 55(8) (2014), 1764–1786.

32.

Liu

, Yang

and Li

T.R.

, Three way decisions: beyond rough sets and granular computing, International Journal of Machine Learning and Cybernetics 11 (2020), 989–1002.

33.

Luo

, Li

T.R.

, Huang

Y.Y.

and Fujita

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

34.

Luo

, Li

T.R.

and Chen

H.M.

, Dynamic maintenance of approximations in set-valued ordered decision systems under the attribute generalization, Information Sciences 257(2) (2014), 210–228.

35.

Luo

, Li

T.R.

, Chen

H.M.

, Fujita

and Yi

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

36.

W.M.

, Lei

W.J.

and Sun

B.Z.

, Three-way group decisions based on multigranulation hesitant fuzzy decision-theoretic rough set over two universes, Journal of Intelligent and Fuzzy Systems 38 (2020), 2165–2179.

37.

X.L.

, Zhan

J.M.

, Sun

B.Z.

and Alcantud

J.C.R.

, Novel classes of coverings based multigranulation fuzzy rough sets and corresponding applications to multiple attribute group decision-making, Artificial Intelligence Review 53 (2020), 6197–6256.

38.

Pawlak

, Rough sets, International Journal of Computer and Information Sciences 11 (1982), 341–356.

39.

Qian

Y.H.

, Li

S.Y.

, Liang

J.Y.

, Shi

Z.Z.

and Wang

, Pessimistic rough set based decisions: A multigranulation fusion strategy, Information Sciences 264 (2014), 196–210.

40.

Qian

Y.H.

, Liang

J.Y.

, Yao

Y.Y.

and Dang

C.Y.

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

41.

Qian

Y.H.

, Liang

J.Y.

and Dang

C.Y.

, Incomplete multigranulation rough set, IEEE Transactions on Systems Man and Cybernetics-Part A 40(2) (2010), 420–431.

42.

Qian

Y.H.

, Liang

X.Y.

, Lin

G.L.

, Guo

and Liang

J.Y.

, Local multigranulation decision-theoretic rough sets, International Journal of Approximate Reasoning 82 (2017), 119–137.

43.

Shu

W.H.

, Qian

W.B.

and Xie

Y.H.

, Incremental feature selection for dynamic hybrid data using neighborhood rough set, Knowledge-Based Systems 194 (2020), 105516.

44.

Sun

B.Z.

, Ma

W.M.

and Qian

Y.H.

, Multigranulation fuzzy rough set over two universes and its application to decision making, Knowledge-Based Systems 123 (2017), 61–74.

45.

Sun

B.Z.

, Ma

W.M.

, Chen

X.T.

and Zhang

, Multigranulation vague rough set over two universes and its application to group decision making, Soft Computing 23(18) (2019), 8927–8956.

46.

Sun

B.Z.

, Zhou

X.M.

and Lin

N.N.

, Diversified binary relation-based fuzzy multigranulation rough set over two universes and application to multiple attribute group decision making, Information Fusion 55 (2020), 91–104.

47.

Wang

C.Z.

, Shi

Y.P.

, Fan

X.D.

and Shao

M.W.

, Attribute reduction based on-nearest neighborhood rough sets, International Journal of Approximate Reasoning 106 (2019), 18–31.

48.

Wang

, Liang

J.Y.

and Dang

C.Y.

, Attribute reduction for dynamic data sets, Applied Soft Computing 13(1) (2013), 676–689.

49.

Wang

, Li

T.R.

, Luo

, Hu

, Fujita

and Huang

T.Q.

, A novel approach for efficient updating approximations in dynamic ordered information systems, Information Sciences 507 (2020), 197–219.

50.

W.H.

, Wang

Q.R.

and Luo

S.Q.

, Multi-granulation fuzzy rough sets, Journal of Intelligent and Fuzzy Systems 26(3) (2014), 1323–1340.

51.

Xue

Z.A.

, Zhao

L.P.

, Zhang

and Sun

B.X.

, Three-way decisions based on multi-granulation support intuitionistic fuzzy probabilistic rough sets, Journal of Intelligent and Fuzzy Systems 38 (2020), 5013–5031.

52.

Yang

, Li

T.R.

, Liu

, Chen

H.M.

and Luo

, A unified framework of dynamic three-way probabilistic rough sets, Information Sciences 420 (2017), 126–147.

53.

Yang

X.B.

, Liang

S.C.

, Yu

H.L.

, Gao

and Qian

Y.H.

, Pseudo-label neighborhood rough set: Measures and attribute reductions, International Journal of Approximate Reasoning 105 (2019), 112–129.

54.

Yang

X.B.

, Song

X.N.

, Chen

Z.H.

and Chen

J.Y.

, On multigranulation rough sets in incomplete information system, International Journal of Machine Learning and Cybernetics 3(3) (2012), 223–232.

55.

Yang

X.B.

, Qi

, Yu

H.L.

, Song

X.N.

and Yang

J.Y.

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

56.

Yao

Y.Y.

, Three-way granular computing, rough sets, and formal concept analysis, International Journal of Approximate Reasoning 116 (2020), 106–125.

57.

Yao

Y.Y.

and She

Y.H.

, Rough set models in multigranulation spaces, Information Sciences 327 (2016), 40–56.

58.

J.H.

and Xu

W.H.

, Incremental knowledge discovering in interval-valued decision information system with the dynamic data, International Journal of Machine Learning and Cybernetics 8 (2017), 849–864.

59.

J.H.

, Li

Y.Q.

, Chen

M.H.

, Zhang

and Xu

W.H.

, Decision-theoretic rough set in lattice-valued decision information system, Journal of Intelligent and Fuzzy Systems 36 (2019), 3289–3301.

60.

P.Q.

, Wang

H.K.

, Li

J.J.

and Lin

G.P.

, Matrix-based approaches for updating approximations in neighborhood multigranulation rough sets while neighborhood classes decreasing or increasing, Journal of Intelligent and Fuzzy Systems 37 (2019), 2847–2867.

61.

Zeng

A.P.

, Li

T.R.

, Hu

, Chen

H.M.

and Luo

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

62.

Zhan

J.M.

and Sun

B.Z.

, Covering-based intuitionistic fuzzy rough sets and applications in multi-attribute decision-making, Artificial Intelligence Review 53 (2020), 671–701.

63.

Zhan

J.M.

, Jiang

H.B.

and Yao

Y.Y.

, Covering-based variable precision fuzzy rough sets with PROMETHEE-EDAS methods, Information Sciences 538 (2020), 314–336.

64.

Zhan

J.M.

, Zhang

X.H.

and Yao

Y.Y.

, Covering based multigranulation fuzzy rough sets and corresponding applications, Artificial Intelligence Review 53 (2020), 1093–1126.

65.

Zhan

J.M.

and Xu

W.H.

, Two types of coverings based multigranulation rough fuzzy sets and applications to decision making, Artificial Intelligence Review 53 (2020), 167–198.

66.

Zhang

, Li

D.Y.

, Zhai

Y.H.

and Yang

Y.H.

, Multigranulation rough set model in hesitant fuzzy information systems and its application in person job fit, International Journal of Machine Learning and Cybernetics 10 (2019), 717–729.

67.

Zhang

, Li

D.Y.

and Liang

J.Y.

, Multi-granularity three-way decisions with adjustable hesitant fuzzy linguistic multigranulation decision-theoretic rough sets over two universes, Information Sciences 507 (2020), 665–683.

68.

Zhang

, Li

D.Y.

and Liang

J.Y.

, Hesitant fuzzy linguistic rough set over two universes model and its applications, International Journal of Machine Learning and Cybernetics 9(4) (2018), 577–588.

69.

Zhang

H.D.

, Zhan

J.M.

and He

Y.P.

, Multi-granulation hesitant fuzzy rough sets and corresponding applications, Soft Computing 23 (2019), 13085–13103.

70.

Zhang

, Zhang

X.Y.

, Xu

W.H.

and Wu

Y.X.

, Local multigranulation decision-theoretic rough set in ordered information systems, Soft Computing 23(24) (2019), 13247–13261.

71.

Zhang

Y.Y.

, Li

T.R.

, Luo

, Zhang

J.B.

and Chen

H.M.

, Incremental updating of rough approximations in interval-valued information systems under attribute generalization, Information Sciences 373 (2016), 461–475.

Incremental approaches to update multigranulation approximations for dynamic information systems

Abstract

Keywords

1 Introduction

2 Preliminaries

2.1 Multigranulation rough sets

3.1 Adding multiple objects

4.1 Incremental algorithm for updating approximations in MGRS when adding multiple objects

Table 4 The time complexity of SACAM and IAUAMA Algorithms Time complexity SACAM O (m (|U|2 + 2|U||UΔ| + |UΔ|2)) IAUAMA O (m (|U||UΔ| + |UΔ|2))

Table 5 The time complexity of SACAM and IAUAMD Algorithms Time complexity SACAM O (m (|U|2 - 2|U||U▿| + |U▿|2)) IAUAMD O (m (|U||U▿| - |U▿|2))

Table 6 The description of data sets ID Data sets # Samples # Attributes # Classes 1 Flags 194 30 7 2 Dermatology 366 34 6 3 Balance scale 625 5 5 4 Tic-tac-toe 958 10 2 5 Solar flare 1389 30 3 6 Car evaluation 1728 7 4 7 Mushroom 8124 22 2 8 Nursery 12960 8 5

Acknowledgments

Declaration of competing interests

Footnotes

References

Table 4
The time complexity of SACAM and IAUAMA

Algorithms Time complexity

SACAM O (m (|U|² + 2|U||U^Δ| + |U^Δ|²))

IAUAMA O (m (|U||U^Δ| + |U^Δ|²))

Table 5
The time complexity of SACAM and IAUAMD

Algorithms Time complexity

SACAM O (m (|U|² - 2|U||U^▿| + |U^▿|²))

IAUAMD O (m (|U||U^▿| - |U^▿|²))

Table 6
The description of data sets

ID Data sets # Samples # Attributes # Classes

1 Flags 194 30 7

2 Dermatology 366 34 6

3 Balance scale 625 5 5

4 Tic-tac-toe 958 10 2

5 Solar flare 1389 30 3

6 Car evaluation 1728 7 4

7 Mushroom 8124 22 2

8 Nursery 12960 8 5