粗糙集理论是波兰学者Pawlak提出的一种数据挖掘模型^[1]，由于它在不精确和不确定性的数据环境下发挥出了重要的作用，目前已被大规模用于机器学习和数据挖掘等^[2-3]领域中。

传统的粗糙集模型通过单个的二元关系对数据进行分割粒化，从而完成对近似目标的粗糙逼近。近年来，为了从多个粒度层次对目标信息进行全方位的挖掘，Qian等^[4]将传统的单个二元关系延伸到多个二元关系，提出了多粒度粗糙集模型，该模型的提出，使得粗糙集理论在分布式数据和多粒化数据的处理上有了一种新的解决方案。在此基础上，学者们对Qian的多粒度粗糙集模型进行了不断地推广和改进，例如将多粒度粗糙集与决策粗糙集结合，提出了多粒度决策粗糙集模型^[5]。将多粒度粗糙集与三支决策模型结合，提出了多粒度三支决策模型^[6]，针对属性和属性值的粒化，Xu^[7]提出了一种新型的改进多粒度粗糙集模型。为了进一步扩大多粒度粗糙集的适用范围，Lin等^[8]将邻域关系融入了多粒度粗糙集模型中，提出了邻域多粒度粗糙集，使得该模型成为了多粒度粗糙集研究分支的热点内容^[9-11]。

当前大数据环境下，数据时刻处于动态变化之中，传统的机器学习和数据挖掘算法针对这一情形面临着极大的挑战。在粗糙集理论中，通过对模型和算法构造增量式学习可以大幅度改善在动态数据下的处理效率，提高粗糙集理论的实际应用性能。增量式学习即保留旧数据的模型和算法结果，然后在此基础上对变化的数据进行计算，使得达到最终新数据的增量式更新。例如，Luo等^[12]利用矩阵方法构造了决策粗糙集模型的增量式更新；Wei等^[13]基于区分矩阵的增量式更新构造了一种属性约简算法；Shu等^[14]研究了邻域粗糙集的增量式学习，并提出一种增量式属性约简；Huang等^[15]利用矩阵的方法重构了多源数据的条件熵模型，并用于增量式属性约简的设计；沈玉峰^[16]基于区分度的矩阵表达提出了一种增量式属性约简算法；Yang等^[17]总结性的提出了一种增量式属性约简的统一框架；Huang等^[18]研究了邻域三支决策模型的增量式更新，并设计出了一种增量式更新算法；杨臻等^[19]利用集合近似的方法针对混合型变精度粗糙集提出了一种动态更新算法；刘丹等^[20]提出了一种双论域模糊概率粗糙集的增量式更新算法。针对多粒度粗糙集模型，学者们也进行了相关的增量式学习的研究，例如Yang等^[21]基于集合近似的方法研究了多粒度粒结构变化时，多粒度粗糙集模型的增量式更新，在其基础上，Hu等^[22]进行进一步地优化和改进，利用矩阵方法去表达多粒度粗糙集，并同样设计出了一种粒结构变化情形下的增量式更新算法，根据这一方法，Hu等^[23]进一步设计出了一种优势多粒度粗糙集的增量式更新算法。同时对于邻域多粒度粗糙集模型，Hu等^[24]也针对粒结构动态变化的情形提出了一种增量式更新算法，并且徐怡等^[25]也提出了类似的改进算法。

然而，针对多粒度粗糙集模型计算的增量式学习研究，目前大多都是考虑粒结构变化的情形，而对象的变化也是信息系统一种较为常见的更新形式，对于多粒度粗糙集而言这一方面的研究目前还比较少。在文献[26]中，两位学者利用矩阵的方法提出了对象变化情形下邻域多粒度粗糙集模型的增量式更新，其主要思想是利用邻域关系矩阵去计算模型的上下近似集，当论域中对象发生变化时，直接增量式更新每个粒度的邻域关系矩阵，同时重新利用矩阵结构去计算新的上下近似结果。这使得文献[26]所提出的增量式方法具有大量的矩阵运算，并且存在着一定的不必要计算，因此仍有一定的优化空间。

为了进一步提高邻域多粒度粗糙集模型的增量式更新效率，本文针对信息系统对象变化的情形，提出一种改进的邻域多粒度粗糙集模型增量式更新方法。矩阵是构造增量式学习的一种重要工具^{[12-13,15-16,20,22,24-26]}，与文献[26]类似，本文也同样采用矩阵的方法去构造模型的增量式学习。文中首先在邻域多粒度粗糙集模型中提出两种近似关系矩阵的概念，然后针对信息系统对象增加和对象减少的情形，在旧信息系统两种近似关系矩阵的基础上进一步地增量式更新出新信息系统的两种近似关系矩阵，最后根据两种近似关系矩阵的增量式更新方法，提出了一种邻域多粒度粗糙集模型的增量式更新算法。本文所提出的增量式更新方法与文献[26]的不同之处在于，本文提出的两种近似关系矩阵表示的是对象在各个粒度下邻域类与近似目标集之间的集合隶属近似关系，文中理论分析表明，通过这两种近似关系矩阵可以直接快速地得到邻域多粒度粗糙集的上下近似集结果，其进行更新的计算方式以及计算的效率均优于文献[26]，最终实验结果也证明了所提出算法的有效性和优越性。

1.   基本理论

本节主要介绍多粒度粗糙集和邻域多粒度粗糙集的相关基本理论，为后文的研究提供基础。

在粗糙集理论中，数据集被表示成信息系统 $S = (U,{A_T})$ 的形式，其中 $ U $ 称为信息系统的论域，是由数据样本组成的集合， ${A_T}$ 称为信息系统的全体属性集，即数据集所有特征的集合。对于论域中的对象 $ \forall x \in U $ 在属性 $\forall a \in {A_T}$ 下的属性值表示为 $ a(x) $ ，若属性值 $ a(x) $ 均为离散值类型，那么该信息系统称之为离散型信息系统，若属性值 $ a(x) $ 均为数值类型，那么该信息系统称之为数值型信息系统。

定义1^[1] 　给定离散型信息系统 $S = (U,{A_T})$ ，属性子集 $A \subseteq {A_T}$ ，那么由属性子集 $ A $ 确定的等价关系定义为 $ {E_A} = \{ (x,y) \in U \times U|\forall a \in A,a(x) = a(y)\} $ 。对于离散型信息系统论域中的对象 $ \forall x \in U $ ，在等价关系 $ {E_A} $ 下确定出的等价类定义为 ${[x]_A} = \{ y \in U|(x,y) \in {E_A}\}$ 。

传统的等价关系仅适用于离散型的信息系统，然而实际应用中存在着数值型的信息系统，因此学者们将等价关系进行推广，提出了邻域关系以及邻域粗糙集模型。

定义2^[8] 　给定数值型信息系统 $S = (U,{A_T})$ ，属性子集 $A \subseteq {A_T}$ ，设邻域半径为 $ \delta $ ，那么由属性子集 $ A $ 确定的邻域关系定义为

式中: 邻域半径 $ \delta $ 是一个非负常数， $ {d_A}{\text{(}}x,y{\text{)}} $ 表示对象 $ x $ 和 $ y $ 在属性子集 $ A $ 下的距离度量，通常 $ {d_A}{\text{(}}x,y{\text{)}} $ 定义为 ${d_A}(x,y) = \left( {\displaystyle\sum\nolimits_{\forall a \in A} {|a(x) - a(y){|^p}} } \right)^{1/p}$ 。这里的 $ p $ 一般取1、2或 $ \infty $ 。对于 $ \forall x \in U $ 在邻域关系 $ N_A^\delta $ 下的邻域类定义为 $ {\delta _A}(x) = \{ y \in U|(x,y) \in N_A^\delta \} $ 。下文中，在不引起混淆的情况下，将 $ N_A^\delta $ 简单表示为 $ {N_A} $ 。

传统的粗糙集模型通过单一粒度视角对近似目标集进行粗糙近似，Qian等^[4]在其基础上推广至多粒度视角下，提出了基于等价关系的多粒度粗糙集模型，同时，Lin等^[8]又将等价关系推广至邻域关系，提出了邻域多粒度粗糙集模型。

定义3^[8] 　给定数值型信息系统 $S = (U,{A_T})$ ，设 $ {A_1},{A_2}, \cdots ,{A_m} $ 是属性集 ${A_T}$ 的一个属性子集族，其中 ${A_i} \subseteq {A_T},1 \leqslant i \leqslant m$ ，邻域半径为 $ \delta $ ，属性子集 $ {A_i} $ 确定的邻域关系为 $ {N_{{A_i}}} $ ，那么对象集 $ X \subseteq U $ 在属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的乐观邻域多粒度下近似集和乐观邻域多粒度上近似集分别定义为

同时对象集 $ X \subseteq U $ 在属性子集族 $ {A_1},{A_2}, \cdots , {A_m} $ 下的悲观邻域多粒度下近似集和悲观邻域多粒度上近似集分别定义为

称 $\left\langle {\underline {\displaystyle\sum_{i = 1}^m {N_i^O} } (X),\overline {\displaystyle\sum_{i = 1}^m {N_i^O} } (X)} \right\rangle$ 为对象集 $ X \subseteq U $ 在属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的乐观邻域多粒度粗糙近似集，称 $\left\langle {\underline {\displaystyle\sum_{i = 1}^m {N_i^P} } (X),\overline {\displaystyle\sum_{i = 1}^m {N_i^P} } (X)} \right\rangle$ 为对象集 $ X \subseteq U $ 在属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的悲观邻域多粒度粗糙近似集。

2.   对象更新时邻域多粒度粗糙集的增量式更新

由于现实中数据集的论域处于不断动态更新之中，即对象的增加或对象的减少，对于邻域多粒度粗糙集模型，如果直接按照模型的定义计算上下近似集，其计算效率不足以满足实际的需求。针对这一问题，本节将设计出一种高效的邻域多粒度粗糙集增量式更新方法。

对于数值型信息系统 $S = (U,{A_T})$ 以及属性集 ${A_T}$ 构造的属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ ，在不引起混淆的情况，用 $ {\varphi ^O}(X) $ ( $ {\varphi ^P}(X) $ )表示近似目标对象集 $ X \subseteq U $ 的乐观(悲观)邻域多粒度下近似集，即 ${\varphi ^O}(X) = \underline {\displaystyle\sum_{i = 1}^m {N_i^O} } (X)$ ( ${\varphi ^P}(X) = \underline {\displaystyle\sum_{i = 1}^m {N_i^P} } (X)$ )，在不区分乐观和悲观的情形下，用 $ \varphi (X) $ 统一表示 $ {\varphi ^O}(X) $ 和 $ {\varphi ^P}(X) $ 。类似地，用 $ {\phi ^O}(X) $ ( $ {\phi ^P}(X) $ )表示近似目标对象集 $ X \subseteq U $ 的乐观(悲观)邻域多粒度上近似集，即 ${\phi ^O}(X) = \overline {\displaystyle\sum_{i = 1}^m {N_i^O} } (X)$ ( ${\phi ^P}(X) = \overline {\displaystyle\sum_{i = 1}^m {N_i^P} } (X)$ )，在不区分乐观和悲观的情形下，用 $ \phi (X) $ 统一表示用 $ {\phi ^O}(X) $ 和 $ {\phi ^P}(X) $ 。

2.1   基于近似关系矩阵形式的邻域多粒度粗糙集

Hu等^[26]通过矩阵的方法定义邻域关系，然后利用邻域关系矩阵与近似目标集的特征向量进行矩阵运算，重构了邻域多粒度粗糙集模型，最后根据邻域关系矩阵的增量式更新进而更新邻域多粒度粗糙集模型，然而Hu等的增量式方法其计算复杂度仍然较高，其性能方面仍有一定的优化空间。本节这里不同于Hu等的方法，将提出邻域多粒度粗糙集一种新的矩阵表达形式，其中定义了邻域多粒度粗糙集的两种近似关系矩阵，本文分别称之为子集近似关系矩阵和交集近似关系矩阵，并利用这两种近似关系矩阵去重构邻域多粒度粗糙集模型。

定义4　给定数值型信息系统 $S = (U,{A_T})$ ， $U = {\text{\{ }}{x_1}{\text{,}}{x_2}{\text{,}} \cdots {\text{,}}{x_n}{\text{\} }}$ ，设 $ {A_1},{A_2}, \cdots ,{A_m} $ 是属性集 ${A_T}$ 的一个属性子集族，其中 ${A_j} \subseteq {A_T},1 \leqslant j \leqslant m$ ，邻域半径为 $ \delta $ ，属性子集 $ {A_j} $ 确定的邻域关系为 $ {N_{{A_j}}} $ ，对象 $ \forall {x_i} \in U $ 在邻域关系 $ {N_{{A_j}}} $ 下的邻域类为 $ {\delta _{{A_j}}}({x_i}) $ 。给定近似目标对象集 $ X \subseteq U $ ，定义该信息系统中 $ X $ 在 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的子集近似关系矩阵 ${\boldsymbol{\varTheta }}(X)$ 和交集近似关系矩阵 ${\boldsymbol{\varOmega }}(X)$ 分别为

其中 $ {\theta _{ij}} = \left\{ \begin{gathered} 1,\;\;\;\;{\delta _{{A_j}}}({x_i}) \subseteq X \\ 0,\;\;\;\;{\delta _{{A_j}}}({x_i}) \not\subset X \\ \end{gathered} \right.\;\;1 \leqslant i \leqslant n,1 \leqslant j \leqslant m $ 。

其中 ${\omega _{ij}} = \left\{ \begin{gathered} 1,\;\;\;\;{\delta _{{A_j}}}({x_i}) \cap X \ne \varnothing \\ 0,\;\;\;\;{\delta _{{A_j}}}({x_i}) \cap X = \varnothing \\ \end{gathered} \right.\;\;1 \leqslant i \leqslant n,{\text{ }}1 \leqslant j \leqslant m$ 。

定义4表明，当数值型信息系统 $S = (U,{A_T})$ 包含了 $ n $ 个对象，并且邻域多粒度粗糙集模型构建了 $ m $ 个属性子集 $ {A_1},{A_2}, \cdots ,{A_m} $ 的属性子集族，那么邻域多粒度近似集 $ X \subseteq U $ 的子集和交集近似关系矩阵具有 $ n $ 行 $ m $ 列，其中矩阵第 $ i $ 行反映了对象 $ {x_i} \in U $ 与近似目标集 $ X $ 在不同粒度下的集合隶属关系。假如当 $ {\delta _{{A_p}}}({x_i}) \subseteq X $ 、 $ {\delta _{{A_q}}}({x_i}) \subseteq X $ 且 $ {\delta _{{A_r}}}({x_i}) \subseteq X $ ，那么对应的子集近似关系矩阵 ${\boldsymbol{\varTheta }}(X)$ 中第 $ i $ 行第 $ p $ 、 $ q $ 和 $ r $ 列上的元素为1，该行其他列的元素为0。同样地，假如当 ${\delta _{{A_s}}}({x_i}) \cap X \ne\varnothing$ 和 ${\delta _{{A_t}}}({x_i}) \cap X \ne \varnothing$ ，那么对应的交集近似关系矩阵 ${\boldsymbol{\varOmega }}(X)$ 中第 $ i $ 行第 $ s $ 和 $ t $ 列上的元素为1，该行其他列的元素为0。因此可以看出，定义4中所定义的近似关系矩阵是对整个邻域多粒度粗糙集中邻域类与近似集之间细节关系的直观展示。下文中，在不引起混淆的情况下，将子集近似关系矩阵和交集近似关系矩阵统称为近似关系矩阵。

近似关系矩阵满足如下性质。

性质1　给定数值型信息系统 $S = (U,{A_T})$ 和属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ ，近似目标对象集 $ X \subseteq U $ 在 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的乐观邻域多粒度下近似集和上近似集分别为 $ {\varphi ^O}(X) $ 和 $ {\phi ^O}(X) $ ，那么有：

1)对于 $ {x_i},{x_j} \in U $ ，若 $ {x_i} \in {\varphi ^O}(X) $ ， $ {x_j} \notin {\varphi ^O}(X) $ ，那么子集近似关系矩阵 ${\boldsymbol{\varTheta }}(X)$ 中第 $ i $ 行至少存在一个元素为1，第 $ j $ 行所有元素均为0。

2)对于 $ {x_i},{x_j} \in U $ ，若 $ {x_i} \in {\phi ^O}(X) $ ， $ {x_j} \notin {\phi ^O}(X) $ ，那么交集近似关系矩阵 ${\boldsymbol{\varOmega }}(X)$ 中第 $ i $ 行所有元素均为1，第 $ j $ 行至少存在一个元素为0。

证明　根据定义3关于乐观邻域多粒度粗糙集的定义以及定义4关于近似关系矩阵的定义：

1)对于乐观邻域多粒度粗糙集下近似集 $ {\varphi ^O}(X) $ 和属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ ，若 $ {x_i} \in {\varphi ^O}(X) $ ，那么 ${\delta _{{A_1}}}({x_i}) \subseteq X \vee {\delta _{{A_2}}}({x_i}) \subseteq X \vee \cdots \vee {\delta _{{A_m}}}({x_i}) \subseteq X$ ，即至少存在一个属性子集 $ {A_t} $ 满足 $ {\delta _{{A_t}}}({x_i}) \subseteq X $ ，所以子集近似关系矩阵 ${\boldsymbol{\varTheta }}(X)$ 中第 $ i $ 行至少存在一个元素为1。对于 $ {x_j} \notin {\varphi ^O}(X) $ ，那么就满足关系 ${\delta _{{A_1}}}({x_j}) \not\subset X \wedge {\delta _{{A_2}}}({x_j}) \not\subset X \wedge \cdots \wedge {\delta _{{A_m}}}({x_j}) \not\subset X$ ，即对象 $ {x_j} $ 均有 $ {\delta _{{A_t}}}({x_j}) \not\subset X(1 \leqslant t \leqslant m) $ ，所以子集近似关系矩阵 ${\boldsymbol{\varTheta }}(X)$ 中第 $ j $ 行所有元素均为0。

2)对于乐观邻域多粒度粗糙集上近似集 $ {\phi ^O}(X) $ 和属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ ，若 $ {x_i} \in {\phi ^O}(X) $ ，则 $ {\delta _{{A_1}}}({x_i}) \cap X \ne \varnothing \wedge \cdots \wedge {\delta _{{A_m}}}({x_i}) \cap X \ne \varnothing $ ，即均有 $ {\delta _{{A_t}}}({x_i}) \cap X \ne \varnothing (1 \leqslant t \leqslant m) $ ，所以交集近似关系矩阵 $ {\boldsymbol{\varOmega }}(X) $ 中第 $ i $ 行所有元素均为1。若 $ {x_j} \notin {\phi ^O}(X) $ ，那么满足关系 $ {\delta _{{A_1}}}({x_j}) \cap X = \varnothing \vee \cdots \vee {\delta _{{A_m}}}({x_j}) \cap X = \varnothing $ ，即存在属性子集 $ {A_t} $ 满足 $ {\delta _{{A_t}}}({x_j}) \cap X = \varnothing (1 \leqslant t \leqslant m) $ ，所以交集近似关系矩阵 ${\boldsymbol{\varOmega }}(X)$ 中第 $ j $ 行至少存在一个元素为0。

证毕。

性质2　给定数值型信息系统 $S = (U,{A_T})$ 和属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ ，近似目标对象集 $ X \subseteq U $ 在 $ {A_1}, {A_2}, \cdots ,{A_m} $ 下的悲观邻域多粒度下近似集和上近似集分别为 $ {\varphi ^P}(X) $ 和 $ {\phi ^P}(X) $ ，那么有：

1)对于 $ {x_i},{x_j} \in U $ ，若 $ {x_i} \in {\varphi ^P}(X) $ ， $ {x_j} \notin {\varphi ^P}(X) $ ，那么子集近似关系矩阵 ${\boldsymbol{\varTheta }}(X)$ 中第 $ i $ 行所有元素均为1，第 $ j $ 行至少存在一个元素为0。

2)对于 $ {x_i},{x_j} \in U $ ，若 $ {x_i} \in {\phi ^P}(X) $ ， $ {x_j} \notin {\phi ^P}(X) $ ，那么交集近似关系矩阵 ${\boldsymbol{\varOmega }}(X)$ 中第 $ i $ 行至少存在一个元素为1，第 $ j $ 行所有元素均为0。

证明　证明过程同性质1。

性质3　给定数值型信息系统 $S = (U,{A_T})$ ，其中 $ U = {\text{\{ }}{x_1}{\text{,}}{x_2}{\text{,}} \cdots {\text{,}}{x_n}{\text{\} }} $ ，给定属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ ，近似目标对象集 $ X \subseteq U $ 在 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的子集近似关系矩阵和交集近似关系矩阵分别为 ${\boldsymbol{\varTheta }}(X)$ 和 ${\boldsymbol{\varOmega }}(X)$ ，那么 $ X $ 在 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的乐观邻域多粒度下近似集 $ {\varphi ^O}(X) $ 和上近似集 $ {\phi ^O}(X) $ 可分别表示为

证明　由性质1可以直接得到证明。

性质4　给定数值型信息系统 $S = (U,{A_T})$ ，其中 $ U = {\text{\{ }}{x_1}{\text{,}}{x_2}{\text{,}} \cdots {\text{,}}{x_n}{\text{\} }} $ ，给定属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ ，近似目标对象集 $ X \subseteq U $ 在 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的子集近似关系矩阵和交集近似关系矩阵分别为 ${\boldsymbol{\varTheta }}(X)$ 和 ${\boldsymbol{\varOmega }}(X)$ ，那么 $ X $ 在 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的悲观邻域多粒度下近似集 $ {\varphi ^P}(X) $ 和上近似集 $ {\phi ^P}(X) $ 可分别表示为

证明　由性质2可以直接得到证明。

性质3和性质4通过两种近似关系矩阵的形式对邻域多粒度粗糙集模型进行了重新表达，因此给定近似目标对象集以及近似目标对象集在多粒度下的近似关系矩阵，那么根据性质3和性质4可以直接得到邻域多粒度粗糙集模型的结果。

性质3和性质4所示的邻域多粒度粗糙集表示方法不同于文献[26]提出的方法，文献[26]为每个邻域关系都建立了邻域关系矩阵，其关系矩阵的建立以单个对象为视角，而定义4中近似关系矩阵的建立以对象的邻域类为视角，对于论域 $ U = {\text{\{ }}{x_1}{\text{,}}{x_2}{\text{,}} \cdots {\text{,}}{x_n}{\text{\} }} $ 和属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ ，文献[26]需要构建 $ m $ 个 $ n \times n $ 的矩阵，并且联合这 $ m $ 个矩阵计算模型的上下近似集结果，而本文仅需构建两个 $ n \times m $ 的矩阵，每个矩阵对应计算出模型上下近似集结果，因此本文方法的计算规模和复杂程度都大幅度小于文献[26]，从而提升了其计算效率。

2.2   对象增加时邻域多粒度粗糙集的增量式更新

本小节中，在2.1节所提出的两种近似关系矩阵的基础上，进一步探究对象增加时邻域多粒度粗糙集的增量式更新方法。

通常信息系统对象的增加和减少都是批量进行的，而直接针对批量变化的对象进行增量式更新研究，其过程比较复杂，本文这里采用其他学者类似的研究方式，每次只研究单个对象变化时模型的增量式更新，然后针对多个对象通过逐步迭代的方式可以实现最终的增量式更新^[19]。

性质3和性质4已经表明，通过近似目标对象集在多粒度环境下的子集近似关系矩阵和交集近似关系矩阵，可以直接得到邻域多粒度粗糙集模型的结果，因此我们可以首先对子集近似关系矩阵和交集近似关系矩阵的增量式更新进行研究，然后依托于这两种近似关系矩阵的增量式更新，那么最终就可以直接实现邻域多粒度粗糙集模型结果的增量式更新。

定理1　给定数值型信息系统 $S = (U,{A_T})$ ， $ U = {\text{\{ }}{x_1}{\text{,}}{x_2}{\text{,}} \cdots {\text{,}}{x_n}{\text{\} }} $ ，设属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ ，邻域半径为 $ \delta $ 。近似目标对象集 $ X \subseteq U $ 在 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的子集近似关系矩阵和交集近似关系矩阵分别为 ${\boldsymbol{\varTheta }}(X) = {({\theta _{ij}})_{n \times m}}$ 和 ${\boldsymbol{\varOmega }}(X) = {({\omega _{ij}})_{n \times m}}$ 。当数值型信息系统论域增加对象 $ {x_{n + 1}} $ ， $ {U^ + } = U \cup \{ {x_{n + 1}}\} $ ，对象 $ {x_{n + 1}} $ 在属性子集 $ {A_i} $ $ (1 \leqslant i \leqslant m) $ 下关于论域 $ {U^ + } $ 的邻域类为 $ {\delta _{{A_i}}}({x_{n + 1}}) $ 。对于两种新的近似目标对象集 $ {X_1} = X $ 和 ${X_2} = X \cup {\text{\{ }}{x_{n + 1}}{\text{\} }}$ ，论域 $ {U^ + } $ 下 $ {X_1} $ 在 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的子集近似关系矩阵和交集近似关系矩阵分别为 ${{\boldsymbol{\varTheta }}^ + }({X_1})$ 和 ${{\boldsymbol{\varOmega }}^ + }({X_1})$ ，论域 $ {U^ + } $ 下 $ {X_2} $ 在 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的子集近似关系矩阵和交集近似关系矩阵分别为 ${{\boldsymbol{\varTheta }}^ + }({X_2})$ 和 ${{\boldsymbol{\varOmega }}^ + }({X_2})$ ，那么它们可增量式计算为

其中

其中

其中

其中

证明　1)对于信息系统新增的对象 $ {x_{n + 1}} $ ，在属性子集 $ {A_j} $ 下的邻域类为 $ {\delta _{{A_j}}}({x_{n + 1}}) $ ，根据邻域关系的对称性，若 $ {x_i} \in {\delta _{{A_j}}}({x_{n + 1}}) $ ，那么必有 $ {x_{n + 1}} \in {\delta _{{A_j}}}({x_i}) $ ，由于 $ {x_{n + 1}} \notin {X_1} $ ，所以 $ {\delta _{{A_j}}}({x_i}) \not\subset {X_1} $ ，即当 $ {x_i} \in {\delta _{{A_j}}}({x_{n + 1}}) $ 时满足 $\theta _{ij}^ + = 0$ ( $1 \leqslant i \leqslant n,{\text{ }}1 \leqslant j \leqslant m$ )，同理若 $ {x_i} \notin {\delta _{{A_j}}}({x_{n + 1}}) $ 则 ${x_{n + 1}} \notin {\delta _{{A_j}}}({x_i})$ ，因此当 $ {x_i} \notin {\delta _{{A_j}}}({x_{n + 1}}) $ 时满足 $ \theta _{ij}^ + = {\theta _{ij}} $ ( $1 \leqslant i \leqslant n, {\text{ }}1 \leqslant j \leqslant m$ )。对于新增的对象 $ {x_{n + 1}} $ ，必满足关系 $ {x_{n + 1}} \in {\delta _{{A_j}}}({x_{n + 1}}) $ ，而 $ {x_{n + 1}} \notin {X_1} $ ，则 $ {\delta _{{A_j}}}({x_{n + 1}}) \not\subset {X_1} $ ，所以有 $ \theta _{(n + 1)j}^ + = 0\; ( 1 \leqslant j \leqslant m )$ 。

2)对于对象 $ \forall {x_i} \in U $ ， $ {\delta _{{A_j}}}({x_i}) $ 表示对象 $ {x_i} $ 在论域 $ U $ 下的邻域类，由于 $ {x_{n + 1}} \notin {X_1} $ ，若 $ {\delta _{{A_j}}}({x_i}) \cap X \ne \varnothing $ ，则 $({\delta _{{A_j}}}({x_i}) \cup \{ {x_{n + 1}}\} ) \cap {X_1} \ne \varnothing$ ，若 ${\delta _{{A_j}}}({x_i}) \cap X = \varnothing$ ，则 $({\delta _{{A_j}}}({x_i}) \cup \{ {x_{n + 1}}\} ) \cap {X_1} = \varnothing$ ，因此满足 $\omega _{ij}^ + = {\omega _{ij}}(1 \leqslant i \leqslant n, {\text{ }}1 \leqslant j \leqslant m)$ 。同时若 ${\delta _{{A_j}}}({x_{n + 1}}) \cap {X_1} \ne \varnothing(1 \leqslant j \leqslant m)$ ，则 $ \omega _{(n + 1)j}^ + = 1 $ ，若 ${\delta _{{A_j}}}({x_{n + 1}}) \cap {X_1} =\varnothing (1 \leqslant j \leqslant m)$ ，则 $ \omega _{(n + 1)j}^ + = 0 $ 。

3)对于对象 $ \forall {x_i} \in U $ ， $ {\delta _{{A_j}}}({x_i}) $ 表示对象 $ {x_i} $ 在论域 $ U $ 下的邻域类，由于 $ {X_2} = X \cup \{ {x_{n + 1}}\} $ ，若 $ {\delta _{{A_j}}}({x_i}) \subseteq X $ ，那么 $ ({\delta _{{A_j}}}({x_i}) \cup \{ {x_{n + 1}}\} ) \subseteq (X \cup \{ {x_{n + 1}}\} ) $ ，即为 $({\delta _{{A_j}}}({x_i}) \cup \{ {x_{n + 1}}\} ) \subseteq {X_2}$ ；若 $ {\delta _{{A_j}}}({x_i}) \not\subset X $ ，那么 $ ({\delta _{{A_j}}}({x_i}) \cup \{ {x_{n + 1}}\} ) \not\subset {X_2} $ ，因此 $\theta _{ij}^ + = {\theta _{ij}}(1 \leqslant i \leqslant n,{\text{ }}1 \leqslant j \leqslant m)$ 。同时，若 ${\delta _{{A_j}}}({x_{n + 1}}) \subseteq {X_2}(1 \leqslant j \leqslant m)$ ，那么 $ \theta _{(n + 1)j}^ + = 1 $ ，若 $ {\delta _{{A_j}}}({x_{n + 1}}) \not\subset {X_2}(1 \leqslant j \leqslant m) $ ，那么 $ \theta _{(n + 1)j}^ + = 0 $ 。

4)对于对象 $ \forall {x_i} \in U $ ， $ {\delta _{{A_j}}}({x_i}) $ 表示对象 $ {x_i} $ 在论域 $ U $ 下的邻域类，若 ${\delta _{{A_j}}}({x_i}) \cap X \ne \varnothing$ ，那么 ${\delta _{{A_j}}}({x_i}) \cap (X \cup \{ {x_{n + 1}}\} ) \ne\varnothing$ ，由于 $ {X_2} = X \cup \{ {x_{n + 1}}\} $ ，所以当 $ {\omega _{ij}} = 1 $ 时有 $\omega _{ij}^ + = 1(1 \leqslant i \leqslant n,{\text{ }}1 \leqslant j \leqslant m)$ 。若 $ {\omega _{ij}} = 0 $ ，则 ${\delta _{{A_j}}}({x_i}) \cap X = \varnothing$ ，如果 $ {x_i} \in {\delta _{{A_j}}}({x_{n + 1}}) $ ，根据邻域关系的对称性，那么对象 $ {x_i} $ 在论域 $ {U^ + } $ 下的邻域类 $ {\delta '_{{A_j}}}({x_i}) $ 包含对象 $ {x_{n + 1}} $ ，因此 ${\delta '_{{A_j}}}({x_i}) \cap {X_2} \ne \varnothing$ ，即 $ {\omega _{ij}} = 0 \wedge {x_i} \in {\delta _{{A_j}}}({x_{n + 1}}) $ 满足 $\omega _{ij}^ + = 1(1 \leqslant i \leqslant n,{\text{ }}1 \leqslant j \leqslant m)$ ，同理当 ${\omega _{ij}} = 0 \wedge {x_i} \notin {\delta _{{A_j}}}({x_{n + 1}})$ 时满足 $\omega _{ij}^ + = 0(1 \leqslant i \leqslant n,{\text{ }}1 \leqslant j \leqslant m)$ 。此外，必有 ${x_{n + 1}} \in {\delta _{{A_j}}}({x_{n + 1}})$ ，因此 ${\delta _{{A_j}}}({x_{n + 1}}) \cap {X_2} \ne \varnothing$ ，所以 $ \omega _{ij}^ + = 1(1 \leqslant j \leqslant m) $ 。

性质3和性质4表明了在邻域多粒度粗糙集模型中，所提出的子集和交集近似关系矩阵在上下近似集的计算中发挥了关键的作用，并且可以直接通过两种近似关系矩阵计算出邻域多粒度粗糙集的上下近似集结果。因此，当信息系统的论域增加单个对象时，定理1通过增量式的方法重新地计算了两种近似关系矩阵，并且该增量式更新方法仅对新增的对象计算了邻域类，极大地提高了计算效率。得到了新信息系统下的子集和交集近似关系矩阵，借助于性质3和性质4便可以直接得到新信息系统下的邻域多粒度粗糙集模型结果。

定理1给出了当信息系统增加单个对象时，两种近似关系矩阵的增量式计算，当信息系统批量地增加多个对象时，那么可以将这多个对象分解成单个对象进行逐个增加，然后逐步采用定理1进行迭代计算，直至完成最终近似关系矩阵的增量式更新。

定理2　给定数值型信息系统 $S = (U,{A_T})$ ， $U = {\text{\{ }}{x_1}{\text{,}}{x_2}{\text{,}} \cdots {\text{,}}{x_n}{\text{\} }}$ ，邻域半径为 $ \delta $ 。近似目标对象集 $ X $ 在属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的子集近似关系矩阵和交集近似关系矩阵分别为 ${\boldsymbol{\varTheta }}(X)$ 和 ${\boldsymbol{\varOmega }}(X)$ 。当数值型信息系统论域增加对象集 $ \{ {x_{n + 1}},{x_{n + 2}}, \cdots ,{x_{n + s}}\} $ 时，新的论域为 $ {U^ + } = U \cup \{ {x_{n + 1}},{x_{n + 2}}, \cdots ,x{}_{n + s}\} $ ，新的近似目标对象集为 $ {X^ + } $ ，那么论域 $ {U^ + } $ 下 $ {X^ + } $ 在属性子集族 $ {A_1}, {A_2}, \cdots ,{A_m} $ 下的子集近似关系矩阵 ${{\boldsymbol{\varTheta }}^ + }({X^ + })$ 和交集近似关系矩阵 ${{\boldsymbol{\varOmega }}^ + }({X^ + })$ 分别增量式更新为

这里的 $ {X^{(i)}}(1 \leqslant i \leqslant s) $ 表示信息系统论域 $ U $ 增加了对象集 $ \{ {x_{n + 1}},{x_{n + 2}}, \cdots ,{x_{n + i}}\} $ 后，近似目标对象集的最新结果，并且 $ X = {X^{(0)}} $ 。 ${{\boldsymbol{\varTheta }}^{(i)}}({X^{(i)}})$ 和 ${{\boldsymbol{\varOmega }}^{(i)}}({X^{(i)}})$ $(1 \leqslant i \leqslant s)$ 分别表示信息系统论域 $ U $ 增加了对象集 $ \{ {x_{n + 1}}, {x_{n + 2}}, \cdots ,{x_{n + i}}\} $ 后近似关系矩阵的更新结果，并且 ${\boldsymbol{\varTheta }}(X) = {{\boldsymbol{\varTheta }}^{(0)}}({X^{(0)}})$ ， ${\boldsymbol{\varOmega }}(X) = {{\boldsymbol{\varOmega }}^{(0)}}({X^{(0)}})$ 。 ${f_1}( \cdot ):{\Re ^{(n + i - 1) \times m}} \to {\Re ^{(n + i) \times m}}$ 为定理1所示的近似关系矩阵 ${{\boldsymbol{\varTheta }}^{(i - 1)}}({X^{(i - 1)}})$ 至 ${{\boldsymbol{\varTheta }}^{(i)}}({X^{(i)}})$ ( ${{\boldsymbol{\varOmega }}^{(i - 1)}}({X^{(i - 1)}})$ 至 ${{\boldsymbol{\varOmega }}^{(i)}}({X^{(i)}})$ )的更新映射关系函数。

基于定理1所示的单个对象更新映射关系 ${f_1}( \cdot )$ ，通过定理2进行迭代计算，我们可以快速高效地完成信息系统增加多个对象时两种近似关系矩阵的增量式更新，利用最新的近似关系矩阵结果，结合性质3和性质4便可以得到最终的邻域多粒度粗糙集的上下近似集，在计算的过程中，仅对增加的对象集 $ \{ {x_{n + 1}},{x_{n + 2}}, \cdots ,{x_{n + s}}\} $ 计算了每个对象的邻域类 $\delta ({x_{n + i}}),{\text{ }}1 \leqslant i \leqslant s$ ，而没有对原先论域 $ U $ 中的对象进行邻域类的重复计算，因此该更新计算方法具有较高的更新计算效率。

2.3   对象减少时邻域多粒度粗糙集的增量式更新

2.2节针对信息系统对象增加的情形提出了邻域多粒度粗糙集模型的增量式更新计算方法，本节采用类似的研究思路，提出信息系统对象减少时邻域多粒度粗糙集的增量式更新计算方法。

定理3　给定数值型信息系统 $S = (U,{A_T})$ ， $U = {\text{\{ }}{x_1}{\text{,}}{x_2}{\text{,}} \cdots {\text{,}}{x_n}{\text{\} }}$ ，设属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ ，邻域半径为 $ \delta $ 。近似目标对象集 $ X \subseteq U $ 在 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的子集近似关系矩阵和交集近似关系矩阵分别为 ${\boldsymbol{\varTheta }}(X) = {({\theta _{ij}})_{n \times m}}$ 和 ${\boldsymbol{\varOmega }}(X) = {({\omega _{ij}})_{n \times m}}$ 。当数值型信息系统论域减少对象 $ {x_t} $ ， $ {x_t} \in U $ ， $ {U^ - } = U - \{ {x_t}\} $ ，对象 $ {x_t} $ 在属性子集 $ {A_i} $ $ (1 \leqslant i \leqslant m) $ 下关于论域 $ U $ 的邻域类为 $ {\delta _{{A_i}}}({x_t}) $ 。对于两种新的近似目标对象集 $ {X_1} = X $ 和 $ {X_2} = X - {\text{\{ }}{x_t}{\text{\} }} $ ，论域 $ {U^ - } $ 下 $ {X_1} $ 在 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的子集近似关系矩阵和交集近似关系矩阵分别为 ${{\boldsymbol{\varTheta }}^ - }({X_1})$ 和 ${{\boldsymbol{\varOmega }}^ - }({X_1})$ ，论域 $ {U^ - } $ 下 $ {X_2} $ 在 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的子集近似关系矩阵和交集近似关系矩阵分别为 ${{\boldsymbol{\varTheta }}^ - }({X_2})$ 和 ${{\boldsymbol{\varOmega }}^ - }({X_2})$ ，那么它们可增量式计算为

式中

其中null表示数值已被删除。

其中

其中

其中

证明　1)根据邻域关系的对称性，对于 $ {x_t} \in U $ ，若 $ {x_i} \in {\delta _{{A_j}}}({x_t}) $ ，那么 $ {x_t} \in {\delta _{{A_j}}}({x_i}) $ ，那么如果 ${\theta _{ij}} = 0 \wedge ({\delta _{{A_j}}}({x_i}) - \{ {x_t}\} ) \not\subset {X_1}$ ，则满足关系 $ \theta _{ij}^ - = 0 $ ( $1 \leqslant i \ne t \leqslant n,{\text{ }}1 \leqslant j \leqslant m$ )。如果 $ {\theta _{ij}} = 0 \wedge ({\delta _{{A_j}}}({x_i}) - \{ {x_t}\} ) \subseteq {X_1} $ ，则 $ \theta _{ij}^ - = 1 $ ( $1 \leqslant i \ne t \leqslant n, {\text{ }}1 \leqslant j \leqslant m$ )。对于 $ {\theta _{ij}} = 1 $ ，那么 $ {\delta _{{A_j}}}({x_i}) \subseteq X $ ，即 $ {x_t} \notin {\delta _{{A_j}}}({x_i}) $ ，所以 $ {\delta _{{A_j}}}({x_i}) - {x_t} = {\delta _{{A_j}}}({x_i}) $ ，则 $ {\delta _{{A_j}}}({x_i}) \subseteq {X_1} $ ，因此 $ {\theta _{ij}} = 1 $ 时 $ \theta _{ij}^ - = 1 $ ( $1 \leqslant i \ne t \leqslant n,{\text{ }}1 \leqslant j \leqslant m$ )。由于 $ {x_t} $ 已被移除，因此 $ \theta _{tj}^ - = {\text{null}} $ ( $ 1 \leqslant j \leqslant m $ )。

2)对于 $ {x_i} \in U $ $ (1 \leqslant i \ne t \leqslant n) $ ，由于 $ {x_t} \notin X $ ， $ X = {X_1} $ ，因此 $ ({\delta _{{A_j}}}({x_i}) - \{ {x_t}\} ) \cap {X_1} = {\delta _{{A_j}}}({x_i}) \cap X $ ， $ 1 \leqslant j \leqslant m $ 。那么有 $\omega _{ij}^ - = {\omega _{ij}},(1 \leqslant i \ne t \leqslant n,{\text{ }}1 \leqslant j \leqslant m)$ ， $\omega _{tj}^ - = {\text{null}},{\text{ }}1 \leqslant j \leqslant m$ 。

3)对于 $ {x_i} \in U $ $ (1 \leqslant i \ne t \leqslant n) $ ，由于 $ {x_t} \in X $ ， $X - \{ {x_t}\} = {X_2}$ ，因此满足关系 $({\delta _{{A_j}}}({x_i}) - \{ {x_t}\} ) \cap (X - \{ {x_t}\} ) = {\delta _{{A_j}}}({x_i}) \cap X$ ， $ 1 \leqslant j \leqslant m $ 。那么有 $\theta _{ij}^ - = {\theta _{ij}},(1 \leqslant i \ne t \leqslant n,{\text{ }}1 \leqslant j \leqslant m)$ ， $\theta _{tj}^ - = {\text{null}},{\text{ }}1 \leqslant j \leqslant m$ 。

4)对于 $ {x_i} \in {\delta _{{A_j}}}({x_t}) $ ， $(1 \leqslant i \ne t \leqslant n,{\text{ }}1 \leqslant j \leqslant m)$ ，则 $ {x_t} \in {\delta _{{A_j}}}({x_i}) $ ，如果 ${\omega _{ij}} = 1 \wedge ({\delta _{{A_j}}}({x_i}) - \{ {x_t}\} ) \cap {X_2} = \varnothing$ ，那么 $ \omega _{ij}^ - = 0 $ ，同理如果 ${\omega _{ij}} = 1 \wedge ({\delta _{{A_j}}}({x_i}) - \{ {x_t}\} ) \cap {X_2} \ne \varnothing$ ，那么 $ \omega _{ij}^ - = 1 $ 。对于 $ {x_i} \notin {\delta _{{A_j}}}({x_t}) $ ，那么 ${\delta _{{A_j}}}({x_i}) - \{ {x_t}\} = {\delta _{{A_j}}}({x_i})$ ，那么满足 $({\delta _{{A_j}}}({x_i}) - {\text{\{ }}{x_t}{\text{\} )}} \cap {X_2} = {\delta _{{A_j}}}({x_i}) \cap {X_2} = {\delta _{{A_j}}}({x_i}) \cap X$ ，因此 $ \omega _{ij}^ - = {\omega _{ij}} $ ，即 $ {x_i} \notin {\delta _{{A_j}}}({x_t}) $ 满足 $ \omega _{ij}^ - = {\omega _{ij}} $ 。

当信息系统的论域减少单个对象时，定理3通过增量式的方法重新计算子集近似关系矩阵和交集近似关系矩阵，其中仅对部分对象计算了其邻域类，极大地提高了计算效率，借助于性质3和性质4便可以直接得到新信息系统下的邻域多粒度粗糙集模型结果，因此同样可以进一步提高邻域多粒度粗糙集上下近似集的更新计算效率。

类似于定理2对单个对象进行迭代的方法，当信息系统批量地减少多个对象时，那么可以将这多个对象分解成单个对象进行逐个减少，然后逐步采用定理3进行迭代计算，直至完成最终近似关系矩阵的增量式更新，具体如定理4所示。

定理4　给定数值型信息系统 $S = (U,{A_T})$ ， $U = \{{x_1}{\text{,}}{x_2}{\text{,}} \cdots {\text{,}}{x_n}\}$ ，邻域半径为 $ \delta $ 。近似目标对象集 $ X $ 在属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的子集近似关系矩阵和交集近似关系矩阵分别为 ${\boldsymbol{\varTheta }}(X)$ 和 ${\boldsymbol{\varOmega }}(X)$ 。当数值型信息系统论域减少对象集 $ \{ {x_{t1}},{x_{t2}}, \cdots ,{x_{ts}}\} $ 时，新的论域为 $ {U^ - } = U - \{ {x_{t1}},{x_{t2}}, \cdots ,x{}_{ts}\} $ ，新的近似目标对象集为 $ {X^ - } $ ，那么论域 $ {U^ - } $ 下 $ {X^ - } $ 在属性子集族 $ {A_1},{A_2}, \cdots , {A_m} $ 下的子集近似关系矩阵 ${{\boldsymbol{\varTheta }}^ - }({X^ - })$ 和交集近似关系矩阵 ${{\boldsymbol{\varOmega }}^ - }({X^ - })$ 分别增量式更新为

式中： $ {X^{(i)}}(1 \leqslant i \leqslant s) $ 表示信息系统论域 $ U $ 减少了对象集 $ \{ {x_{t1}},{x_{t2}}, \cdots ,{x_{ti}}\} $ 后，近似目标对象集的最新结果，并且 $ X = {X^{(0)}} $ ； ${{\boldsymbol{\varTheta }}^{(i)}}({X^{(i)}})$ 和 ${{\boldsymbol{\varOmega }}^{(i)}}({X^{(i)}})$ $ (1 \leqslant i \leqslant s) $ 分别表示信息系统论域 $ U $ 减少了对象集 $ \{ {x_{t1}},{x_{t2}}, \cdots ,{x_{ti}}\} $ 后近似关系矩阵的更新结果，并且 ${\boldsymbol{\varTheta }}(X) = {{\boldsymbol{\varTheta }}^{(0)}}({X^{(0)}})$ ， ${\boldsymbol{\varOmega }}(X) = {{\boldsymbol{\varOmega }}^{(0)}}({X^{(0)}})$ ； ${f_2}( \cdot ):{\Re ^{n \times m}} \to {\Re ^{n \times m}}$ 为定理3所示的近似关系矩阵 ${{\boldsymbol{\varTheta }}^{(i - 1)}}({X^{(i - 1)}})$ 至 ${{\boldsymbol{\varTheta }}^{(i)}}({X^{(i)}})$ ( ${{\boldsymbol{\varOmega }}^{(i - 1)}}({X^{(i - 1)}})$ 至 ${{\boldsymbol{\varOmega }}^{(i)}}({X^{(i)}})$ )的更新映射关系函数。

基于定理3单个对象的更新映射关系 ${f_2}( \cdot )$ ，通过定理4进行迭代计算，我们可以快速高效地完成信息系统减少多个对象时两种近似关系矩阵的增量式更新，利用最新的近似关系矩阵结果，结合性质3和性质4便可以得到最终的邻域多粒度粗糙集的上下近似集，在计算的过程中，仅对减少的对象集 $ \{ {x_{t1}},{x_{t2}}, \cdots ,{x_{ti}}\} $ 计算了每个对象的邻域类 $\delta ({x_{ti}}),{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 1 \leqslant i \leqslant s$ ，而没有对原先论域 $ U $ 中的对象进行邻域类的重复计算，因此该更新计算方法同样具有较高的更新计算效率。

3.   邻域多粒度粗糙集动态更新算法

3.1   非增量式更新算法

针对信息系统对象增加和减少的情形，本小节基于传统的邻域多粒度粗糙集计算方法，提出对应的计算算法，具体算法1和算法2所示，由于该算法不具有增量式更新计算的特性，因此该算法也被称为非增量式更新算法。

算法1　对象增加时邻域多粒度粗糙集非增量式更新算法。

输入　数值型信息系统 $S = (U,{A_T})$ ， $ U = {\text{\{ }}{x_1}{\text{,}} {x_2}{\text{,}} \cdots {\text{,}}{x_n}{\text{\} }} $ ，邻域半径为 $ \delta $ ，属性集 ${A_T}$ 确定的属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ ，近似目标对象集 $ X $ 。信息系统论域增加对象集 $ \{ {x_{n + 1}},{x_{n + 2}}, \cdots ,{x_{n + s}}\} $ ，新的论域 ${U^ + } = U \cup \{ {x_{n + 1}},{x_{n + 2}}, \cdots ,x{}_{n + s}\}$ ，新的近似目标对象集为 $ {X^ + } $ 。

输出　近似目标对象集 $ {X^ + } $ 在属性子集族 $ {A_1}, {A_2}, \cdots ,{A_m} $ 下的乐观(悲观)邻域多粒度下近似集 $ \varphi ({X^ + }) $ 和上近似集 $ \phi ({X^ + }) $ 。

1）初始化近似集 $\varphi ({X^ + }) = \varnothing$ ， $\phi ({X^ + }) = \varnothing$ ，初始化两种近似关系矩阵 ${{\boldsymbol{\varTheta }}^ + }({X^ + }) = {(\theta _{ij}^ + )_{(n + s) \times m}} = {\boldsymbol{0}}$ 和 ${{\boldsymbol{\varOmega }}^ + }({X^ + }) = {(\omega _{ij}^ + )_{(n + s) \times m}} = {\boldsymbol{0}}$ 。/*这里的 ${\boldsymbol{ 0}}$ 代表全0矩阵*/

2）对于 $ {x_i} \in {U^ + } $ $ (1 \leqslant i \leqslant n + s) $ ，计算 $ {x_i} $ 在属性集 $ {A_j} $ $ (1 \leqslant j \leqslant m) $ 下的 $ \delta $ 邻域类 $ {\delta _{{A_j}}}({x_i}) $ 。

3）对于 $ {\delta _{{A_j}}}({x_i}) $ ， $(1 \leqslant i \leqslant n + s,{\text{ }}1 \leqslant j \leqslant m)$ ，若 ${\delta _{{A_j}}}({x_i}) \subseteq {X^ + }$ ，那么 $ \theta _{ij}^ + = 1 $ ，否则 $ \theta _{ij}^ + = 0 $ ，若 $ {\delta _{{A_j}}}({x_i}) \cap {X^ + } \ne \varnothing $ ，那么 $ \omega _{ij}^ + = 1 $ ，否则 $ \omega _{ij}^ + = 0 $ 。

4）根据两种近似关系矩阵 ${{\boldsymbol{\varTheta }}^ + }({X^ + })$ 和 ${{\boldsymbol{\varOmega }}^ + }({X^ + })$ 计算 $ {X^ + } $ 在属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的乐观(悲观)邻域多粒度下近似集 $ \varphi ({X^ + }) $ 和上近似集 $ \phi ({X^ + }) $ 。/*根据性质3和性质4*/

5）返回 $ \varphi ({X^ + }) $ 和 $ \phi ({X^ + }) $ 。

在算法1中，设信息系统条件属性集的属性数量为 $ a $ ，那么整个算法1的计算量主要集中在所有对象邻域类的计算上，因此整个算法1的时间复杂度为 $ O(a \cdot {(n + s)^2}) $ 。

算法2　对象减少时邻域多粒度粗糙集非增量式更新算法。

输入　数值型信息系统 $S = (U,{A_T})$ ， $ U = {\text{\{ }}{x_1}{\text{,}} {x_2}{\text{,}} \cdots {\text{,}}{x_n}{\text{\} }} $ ，邻域半径为 $ \delta $ ，属性集 ${A_T}$ 确定的属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ ，近似目标对象集 $ X $ 。信息系统论域减少对象集 $ \{ {x_{t1}},{x_{t2}}, \cdots ,{x_{ts}}\} $ ，新的论域 $ {U^ - } = U - \{ {x_{t1}}, {x_{t2}}, \cdots ,{x_{ts}}\} $ ，新的近似目标对象集为 $ {X^ - } $ 。

输出　近似目标对象集 $ {X^ - } $ 在属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的乐观(悲观)邻域多粒度下近似集 $ \varphi ({X^ - }) $ 和上近似集 $ \phi ({X^ - }) $ 。

1）初始化近似集 $\varphi ({X^ - }) = \varnothing$ ， $\phi ({X^ - }) = \varnothing$ ，初始化两种近似关系矩阵 ${{\boldsymbol{\varTheta }}^ - }({X^ - }) = {(\theta _{ij}^ - )_{(n - s) \times m}} = {\boldsymbol{0}}$ 和 ${{\boldsymbol{\varOmega }}^ - }({X^ - }) = {(\omega _{ij}^ - )_{(n - s) \times m}} = {\boldsymbol{0}}$ 。/*这里的 ${\boldsymbol{0}}$ 代表全0矩阵*/

2）对于 $ {x_i} \in {U^ - } $ $ (1 \leqslant i \leqslant n - s) $ ，计算 $ {x_i} $ 在属性集 $ {A_j} $ $ (1 \leqslant j \leqslant m) $ 下的 $ \delta $ 邻域类 $ {\delta _{{A_j}}}({x_i}) $ 。

3）对于 $ {\delta _{{A_j}}}({x_i}) $ ， $(1 \leqslant i \leqslant n - s,{\text{ }}1 \leqslant j \leqslant m)$ ，若 ${\delta _{{A_j}}}({x_i}) \subseteq {X^ - }$ ，那么 $ \theta _{ij}^ - = 1 $ ，否则 $ \theta _{ij}^ - = 0 $ ，若 $ {\delta _{{A_j}}}({x_i}) \cap {X^ - } \ne \varnothing $ ，那么 $ \omega _{ij}^ - = 1 $ ，否则 $ \omega _{ij}^ - = 0 $ 。

4）根据两种近似关系矩阵 ${{\boldsymbol{\varTheta }}^ - }({X^ - })$ 和 ${{\boldsymbol{\varOmega }}^ - }({X^ - })$ 计算 $ {X^ - } $ 在属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的乐观(悲观)邻域多粒度下近似集 $ \varphi ({X^ - }) $ 和上近似集 $ \phi ({X^ - }) $ 。/*根据性质3和性质4*/

5）返回 $ \varphi ({X^ - }) $ 和 $ \phi ({X^ - }) $ 。

类似于算法1的时间复杂度分析，整个算法2的时间复杂度为 $ O(a \cdot {(n - s)^2}) $ 。

3.2   增量式更新算法

根据本文2.2节和2.3节所示的邻域多粒度粗糙集增量式更新方法，接下来提出相应的增量式更新算法。

算法3　对象增加时邻域多粒度粗糙集增量式更新算法。

输入　1)数值型信息系统 $S = (U,{A_T})$ ， $U = \{ {x_1}{\text{,}} {x_2}{\text{,}} \cdots {\text{,}}{x_n}\}$ ，邻域半径为 $ \delta $ ，属性集 ${A_T}$ 确定的属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ ，近似目标对象集 $ X $ ， $ X $ 在属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的两种近似关系矩阵分别为 ${\boldsymbol{\varTheta }}(X)$ 和 ${\boldsymbol{\varOmega }}(X)$ 。

2)论域增加的对象集为 $ \{ {x_{n + 1}},{x_{n + 2}}, \cdots ,{x_{n + s}}\} $ ，新的论域表示为 $ {U^ + } = U \cup \{ {x_{n + 1}},{x_{n + 2}}, \cdots ,x{}_{n + s}\} $ ，新的近似目标对象集为 $ {X^ + } $ 。

输出　近似目标对象集 $ {X^ + } $ 在属性子集族 $ {A_1}, {A_2}, \cdots ,{A_m} $ 下的乐观(悲观)邻域多粒度下近似集 $ \varphi ({X^ + }) $ 和上近似集 $ \phi ({X^ + }) $ 。

1）初始化近似集 $ \varphi ({X^ + }) = \varnothing $ ， $ \phi ({X^ + }) = \varnothing $ ，初始化两种近似关系矩阵 ${{\boldsymbol{\varTheta }}^ + }({X^ + }) = {(\theta _{ij}^ + )_{(n + s) \times m}} = {\boldsymbol{0}}$ 和 ${{\boldsymbol{\varOmega }}^ + }({X^ + }) = {(\omega _{ij}^ + )_{(n + s) \times m}} = {\boldsymbol{0}}$ 。/*这里的 ${\boldsymbol{0}}$ 代表全0矩阵*/

2）对于 $ {x_{n + i}} \in \{ {x_{n + 1}},{x_{n + 2}}, \cdots ,{x_{n + s}}\} (1 \leqslant i \leqslant s) $ ，记信息系统 ${S^{(i)}} = ({U^{(i)}} = {U^{(i - 1)}} \cup \{ {x_{n + i}}\} ,{A_T})$ ，其中 $ {U^{(0)}} = U $ ，对应的近似目标集为 $ {X^{(i)}} $ ，其中 $ {X^{(0)}} = X $ 。

3）计算论域 $ {U^{(i)}} $ 下对象 $ {x_{n + i}} $ $ (1 \leqslant i \leqslant s) $ 在属性子集 $ {A_j} $ $ (1 \leqslant j \leqslant m) $ 的邻域类为 $ {\delta _{{A_j}}}({x_{n + i}}) $ 。

4）在近似关系矩阵 ${{\boldsymbol{\varTheta }}^{(i - 1)}}({X^{(i - 1)}})$ 和 ${{\boldsymbol{\varOmega }}^{(i - 1)}}({X^{(i - 1)}})$ 的基础上更新计算论域 $ {U^{(i)}} $ 下 $ {X^{(i)}} $ 关于属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ 的近似关系矩阵 ${{\boldsymbol{\varTheta }}^{(i)}}({X^{(i)}})$ 和 ${{\boldsymbol{\varOmega }}^{(i)}}({X^{(i)}})$ ，其中 ${{\boldsymbol{\varTheta }}^{(0)}}({X^{(0)}}) = {\boldsymbol{\varTheta }}(X)$ 且 ${{\boldsymbol{\varOmega }}^{(0)}}({X^{(0)}}) = {\boldsymbol{\varOmega }}(X)$ 。/*根据定理1*/

5）重复迭代2）~4）。/*定理2*/

6）令近似关系矩阵 ${{\boldsymbol{\varTheta }}^ + }({X^ + }) = {{\boldsymbol{\varTheta }}^{(s)}}({X^{(s)}})$ 、 ${{\boldsymbol{\varOmega }}^ + }({X^ + }) = {{\boldsymbol{\varOmega }}^{(s)}}({X^{(s)}})$ 和 $ {X^ + } = {X^{(s)}} $ ，根据 ${{\boldsymbol{\varTheta }}^ + }({X^ + })$ 和 ${{\boldsymbol{\varOmega }}^ + }({X^ + })$ 计算 $ {X^ + } $ 在属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的乐观(悲观)邻域多粒度下近似集 $ \varphi ({X^ + }) $ 和上近似集 $ \phi ({X^ + }) $ 。/*根据性质3和性质4*/

7）返回 $ \varphi ({X^ + }) $ 和 $ \phi ({X^ + }) $ 。

算法3在执行的过程中，会不断地重复迭代2）~4），其中每次迭代所需的时间复杂度为 $ O(a \cdot n) $ ，直到新增的 $ s $ 个对象全部迭代完成，因此整个算法3的时间复杂度为 $ O(a \cdot s \cdot n) $ 。

算法4　对象减少时邻域多粒度粗糙集增量式更新算法。

输入　1)数值型信息系统 $S = (U,{A_T})$ ， $ U = {\text{\{ }}{x_1}{\text{,}} {x_2}{\text{,}} \cdots {\text{,}}{x_n}{\text{\} }} $ ，邻域半径为 $ \delta $ ，属性集 ${A_T}$ 确定的属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ ，近似目标对象集 $ X $ ， $ X $ 在属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的两种近似关系矩阵分别为 ${\boldsymbol{\varTheta }}(X)$ 和 ${\boldsymbol{\varOmega }}(X)$ 。

2)论域减少的对象集为 $ \{ {x_{t1}},{x_{t2}}, \cdots ,{x_{ts}}\} $ ，新的论域表示为 $ {U^ - } = U - \{ {x_{t1}},{x_{t2}}, \cdots ,{x_{ts}}\} $ ，新的近似目标对象集为 $ {X^ - } $ 。

输出　近似目标对象集 $ {X^ - } $ 在属性子集族 $ {A_1}, {A_2}, \cdots ,{A_m} $ 下的乐观(悲观)邻域多粒度下近似集 $ \varphi ({X^ - }) $ 和上近似集 $ \phi ({X^ - }) $ 。

1）初始化近似集 $ \varphi ({X^ - }) = \varnothing $ ， $ \phi ({X^ - }) = \varnothing $ ，初始化两种近似关系矩阵 ${{\boldsymbol{\varTheta }}^ - }({X^ - }) = {(\theta _{ij}^ - )_{n \times m}} = {\boldsymbol{0}}$ 和 ${{\boldsymbol{\varOmega }}^ - }({X^ - }) = {(\omega _{ij}^ - )_{n \times m}} = {\boldsymbol{0}}$ 。/*这里的 ${\boldsymbol{0 }}$ 代表全0矩阵*/

2）对于 $ {x_{ti}} \in \{ {x_{t1}},{x_{t2}}, \cdots ,{x_{ts}}\} (1 \leqslant i \leqslant s) $ ，记信息系统 ${S^{(i)}} = ({U^{(i)}} = {U^{(i - 1)}} - \{ {x_{ti}}\} ,{A_T})$ ，其中 $ {U^{(0)}} = U $ ，对应的近似目标集为 $ {X^{(i)}} $ ，其中 $ {X^{(0)}} = X $ 。

3）计算论域 $ {U^{(i)}} $ 下对象 $ {x_{ti}} $ $ (1 \leqslant i \leqslant s) $ 在属性子集 $ {A_j} $ $ (1 \leqslant j \leqslant m) $ 的邻域类为 $ {\delta _{{A_j}}}({x_{ti}}) $ 。

4）在近似关系矩阵 ${{\boldsymbol{\varTheta }}^{(i - 1)}}({X^{(i - 1)}})$ 和 ${{\boldsymbol{\varOmega }}^{(i - 1)}}({X^{(i - 1)}})$ 的基础上更新计算论域 $ {U^{(i)}} $ 下 $ {X^{(i)}} $ 关于属性子集族 $ {A_1}, {A_2}, \cdots ,{A_m} $ 的近似关系矩阵 ${{\boldsymbol{\varTheta }}^{(i)}}({X^{(i)}})$ 和 ${{\boldsymbol{\varOmega }}^{(i)}}({X^{(i)}})$ ，其中 ${{\boldsymbol{\varTheta }}^{(0)}}({X^{(0)}}) = {\boldsymbol{\varTheta }}(X)$ 且 ${{\boldsymbol{\varOmega }}^{(0)}}({X^{(0)}}) = {\boldsymbol{\varOmega }}(X)$ 。/*根据定理3*/

5）重复迭代2）~4）。/*定理4*/

6）令近似关系矩阵 ${{\boldsymbol{\varTheta }}^ - }({X^ - }) = {{\boldsymbol{\varTheta }}^{(s)}}({X^{(s)}})$ 、 ${{\boldsymbol{\varOmega }}^ - }({X^ - }) = {{\boldsymbol{\varOmega }}^{(s)}}({X^{(s)}})$ 和 $ {X^ - } = {X^{(s)}} $ ，根据 ${{\boldsymbol{\varTheta }}^ - }({X^ - })$ 和 ${{\boldsymbol{\varOmega }}^ - }({X^ - })$ 计算 $ {X^ - } $ 在属性子集族 $ {A_1},{A_2}, \cdots ,{A_m} $ 下的乐观(悲观)邻域多粒度下近似集 $ \varphi ({X^ - }) $ 和上近似集 $ \phi ({X^ - }) $ 。/*根据性质3和性质4*/

7）返回 $ \varphi ({X^ - }) $ 和 $ \phi ({X^ - }) $ 。

与算法3类似，整个算法4的时间复杂度为 $ O(a \cdot s \cdot n) $ 。

4.   实验分析

4.1   实验设置

为了测试本文所提出的邻域多粒度粗糙集增量式更新算法的有效性，本节将通过实验分析的方式进行验证。本实验分为两部分，第1部分将文中所提出的邻域多粒度粗糙集的增量式更新算法与非增量式更新算法进行比较，由于这两种算法计算的是同一种模型，因此只对它们的算法效率进行比较便可以验证增量式算法的有效性，第2部分是将本文提出的增量式算法与文献[26]提出的邻域多粒度粗糙集增量式更新算法进行实验效率对比，用来验证本文算法的优越性。表1给出了进行实验比较所使用的8个UCI数据集，这些数据集均为数值型的属性值，因此可以直接运用于邻域多粒度粗糙集模型，同时这8个数据集包含了不同的大小规模，可以用来验证算法在不同规模数据集下的增量式更新效果。

由于本文所研究的是邻域多粒度环境下的粗糙集模型，即模型中含有多个邻域关系，因此需要将数据集的条件属性集构造出一组属性子集族。本实验按照原始数据集的属性顺序，对条件属性集进行大致平均划分构造出属性子集族，由于本实验验证的是增量式算法与非增量式算法的算法效率，而邻域多粒度粗糙集的近似集结果并不是本实验关注的重点，因此构造出属性子集族中的属性子集数量可自行约定，对于表1中的数据集Iono构造了7个多粒度属性子集的属性子集族，数据集Wdbc构造了6个多粒度属性子集的属性子集族，数据集Biodeg构造了8个多粒度属性子集的属性子集族，数据集Mess构造了5个多粒度属性子集的属性子集族，数据集Gearbox构造了9个多粒度属性子集的属性子集族，数据集Segment构造了5个多粒度属性子集的属性子集族，数据集Gisette构造了100个多粒度属性子集的属性子集族，数据集Skin构造了2个多粒度属性子集的属性子集族。表2给出了进行实验所使用的软硬件环境。

另一方面，本文所提出的算法是针对动态数据环境下模型的增量式更新，因此需要对表1中的数据集进行动态变化的构造，这里参考其他学者对于该类问题的处理^[12-20]，将数据集的论域进行平均分割成多个部分，然后选择一个部分作为初始数据集，并不断地将剩余的部分数据集进行合并，则构造出了信息系统动态增加更新的情形，相反，从完整的数据集开始，不断地从中依次进行每个部分的删除，因而构造出了信息系统动态减少更新的情形。本实验均按照这种处理方式进行实验，并且将实验数据集分成10个部分。对于邻域多粒度粗糙集模型中的参数邻域半径 $ \delta $ ，在文献[9-11]中，学者们通过大量实验验证了邻域半径 $ \delta = 0.15 $ 时模型的近似效果较佳，因此本文直接采纳其他学者的研究成果，将邻域半径设置为 $ \delta = 0.15 $ 进行实验，模型的近似目标集均由原始数据集的类别集来定义。本文所有实验结果均取自10次实验求取平均值来表示。

4.2   非增量式与增量式算法比较

图1给出了信息系统论域依次增加单个部分数据时，邻域多粒度粗糙集模型增量式更新算法与非增量式更新算法在各个数据集下更新模型的时间比较结果。

图  1  数据增加时增量式与非增量式算法更新用时比较

Fig.  1  Comparison of update time between incremental and non incremental algorithms when data increases

下载: 全尺寸图片

观察图1的每个子图可以发现，随着数据集更新次数的不断增加，即信息系统的论域不断增大，2种算法在更新邻域多粒度粗糙集模型所需的时间都是不断增加的，但是可以很直观地看出非增量式算法的时间增长较为迅速，增量式算法增长的非常平缓，随着更新次数的不断增加，2种算法差距越来越大。例如对于数据集Biodeg，当完成信息系统的第9次更新时，非增量式算法消耗了620 ms，而增量式算法仅消耗了不到100 ms的时间；对于数据集Mess，当完成信息系统的第9次更新时，非增量式算法消耗了超过390 ms的时间，而增量式算法仅消耗了50 ms。产生这一差距的主要原因是由于非增量式算法与增量式算法的计算机制不同导致的，对于非增量式算法，每次基于完整的数据集进行计算，即数据集的规模越大其计算量也越大，消耗的时间也越长，其消耗的时间与当前完整数据集的规模密切相关。而对于增量式算法，通过在旧数据集的计算结果上对新增的数据进行计算，主要的计算量集中在新增的数据上，而对原始数据仅需要花费较少的计算，便可以完成整个新信息系统模型的更新，由于数据集每次新增的数据量比较少且是固定的，因此增量式算法的更新计算时间增长得较为缓慢，整体计算时间处于一个比较低的水平，因此对于信息系统对象增加的情形，本文提出的增量式更新算法具有较高的更新计算效率。

图2给出了信息系统论域依次减少单个部分数据时，邻域多粒度粗糙集模型增量式更新算法与非增量式更新算法在各个数据集下更新模型的时间比较结果。

图  2  数据减少时增量式与非增量式算法更新用时比较

Fig.  2  Comparison of update time between incremental and non incremental algorithms when data decreases

下载: 全尺寸图片

观察图2的每个子图，可以发现当信息系统刚开始更新时，非增量式算法和增量式算法的计算时间就表现出了很大的差距，随着信息系统更新次数的增加，两类算法的计算时间均逐渐减小，并且差距也减小，但是增量式算法的计算时间始终处于一个较低的水平。例如对于数据集Wdbc，第一次动态更新时，非增量式算法的更新时间接近120 ms，而增量式算法仅消耗了20 ms。出现这一差距同样是由于2种算法的计算机制不同导致的，对于非增量式算法，每次基于完整的数据集进行模型的计算，而增量式算法针对变化的数据在原先旧数据集的基础上进行进一步计算，因此增量式算法的效率大幅度高于非增量式算法。另外，观察图2可以发现，在信息系统的第8次和第9次更新时，非增量式算法与增量式算法的更新用时基本接近，甚至非增量式算法的更新用时略低于增量式算法，此时数据集经过不断更新减少，其规模已经很小了，因此对于小规模的数据集，非增量式算法和增量式算法的效率相当，但是对于大规模的数据集，本文增量式算法的效率还是大幅度高于非增量式算法。

综合图1和图2的实验结果，针对信息系统对象的增加和对象的减少，所提出的邻域多粒度粗糙集增量式更新算法都具有更高的更新效率。

4.3   与同类型增量式更新算法比较

为了进一步验证所提出算法的优越性，接下来将本文的增量式算法与文献[26]提出的邻域多粒度粗糙集增量式算法进行实验比较，给定同一邻域半径和同一属性子集族，那么这2种算法的模型计算结果是一致的，因此只需对比2种算法的效率便可以验证它们的性能。

图3和图4分别给出了信息系统依次增加和依次减少单个部分数据时，2种增量式算法的更新时间比较结果。观察图3中各个数据集的实验结果可以发现，本文算法的更新性能较高于文献[26]提出的对比算法，当信息系统刚开始更新时，2种算法的更新所需时间几乎相当，随着更新次数的增加，数据集的规模逐渐增大，2种算法的时间消耗量逐渐表现出了差距，文献[26]算法更新时间的增长速率要略高于本文算法，因此最终的更新用时较高于本文算法。观察图4中各个数据集的实验结果可以发现，随着信息系统论域的逐渐减小，本文算法的更新时间在大部分情形下低于文献[26]的对比算法，例如Iono、Wdbc、Biodeg、Mess、Segment和Gisette数据集的前7次更新。对于信息系统的后两次更新，对比算法的更新时间与本文算法比较接近，此时数据集的规模比较小，对比增量式算法的计算效率与本文算法相差不大。通过整体比较，可以看出本文增量式算法的性能较高于对比增量式算法。

图  3  数据增加时本文增量式算法与对比增量式算法更新用时比较

Fig.  3  Comparison of update time between our incremental algorithm and the compared incremental algorithm when data increases

下载: 全尺寸图片

图  4  数据减少时本文增量式算法与对比增量式算法更新用时比较

Fig.  4  Comparison of update time between our incremental algorithm and the compared incremental algorithm when data decreases

下载: 全尺寸图片

为了测试信息系统不同数据量变化时本文增量式算法与文献[26]对比增量式算法的更新性能，在接下来的实验中，对于信息系统论域增加的情形，首先选择信息系统的1个部分数据作为初始数据集，然后往初始数据集增加1个部分数据作为第1次增量式更新，往初始数据集一次性增加2个部分数据作为第2次增量式更新，往初始数据集一次性增加3个部分数据作为第3次增量式更新，依次类推，直到一次性增加9个部分数据，即每次增加的数据量为信息系统整体数据量的10%、20%、···、90%。类似地，对于信息系统论域减少的情形，每次从整个信息系统开始，一次性移除1个部分数据作为第1次增量式更新，一次性移除2个部分数据作为第2次增量式更新，以此类推，直至移除9个部分数据。按照上述的数据更新，让2种算法进行邻域多粒度粗糙集的增量式更新计算，实验结果如图5、6所示。

图  5  不同数据量增加时邻域多粒度粗糙集更新用时比较

Fig.  5  Comparison of updating time of neighborhood multi-granulation rough sets with different data volume

下载: 全尺寸图片

图  6  不同数据量减少时邻域多粒度粗糙集更新用时比较

Fig.  6  Comparison of updating time of neighborhood multi-granulation rough sets with different data reduction

下载: 全尺寸图片

图5给出了信息系统论域增加不同数据量时2种算法的更新时间比较，图6给出了信息系统论域减少不同数据量时2种算法的更新时间比较。观察图5可以发现，随着数据集更新次数的增加，即每次增加的数据量逐渐增大，本文增量式算法在所有数据集下的更新时间均小于文献[26]的对比增量式算法，并且效率的差距逐渐拉大。观察图6可以发现，随着数据集更新次数的增加，即每次减少的数据量逐渐增大，除数据集Gearbox的更新时间相当外，本文增量式算法在其余数据集的更新时间均小于文献[26]的对比增量式算法，因此综合起来可以看出，对于信息系统不同数据量的变化情形，本文所提出的增量式更新算法具有较高的更新计算效率。

文献[26]所示的邻域多粒度粗糙集增量式更新算法同样是采用矩阵的形式去构造模型的增量式更新，它主要通过矩阵去直接计算邻域多粒度粗糙集的近似集，即通过邻域关系矩阵去表示每个粒度下的邻域关系，然后通过邻域关系矩阵与近似目标集进行矩阵的标准乘运算，来得到最终近似结果的矩阵形式，当信息系统论域发生变化时，通过增量式的方法去更新邻域关系矩阵，然后通过矩阵运算得到最终的更新近似集结果，在这一系列的增量式计算过程中，其中涉及到了较多的矩阵运算，因此其计算复杂度会比较高。而本文提出的增量式更新方法，虽然也同样采用了矩阵的形式，但是本文没有利用矩阵去表示邻域关系，而是去表示邻域粒与近似集之间的关系，屏蔽了邻域类与近似集之间的运算过程，该过程运算量是最大的，对于信息系统变化后，对近似关系矩阵进行更新，可以减少很多计算量，提高了计算效率，因此本文算法的增量式更新效率会更高一些。此外，本文增量式算法与对比增量式算法的实验结果中，出现了一小部分两种算法计算效率相近的情形，可能是由于当时数据集的更新，使得对于本文算法中近似关系矩阵的更新量较大，导致了耗时较长，从而与对比算法的用时比较接近。

4.4   实验总结

综合所有的实验结果和实验分析可以看出，相比较于邻域多粒度粗糙集非增量式更新算法，本文所提出的增量式更新算法具有非常高的更新效率，与文献[26]提出的增量式更新算法相比，本文的增量式更新算法其性能具有很明显的提升，因此证明了本文邻域多粒度粗糙集增量式更新算法具有更高的优越性。

5.   结束语

邻域多粒度粗糙集模型是当前粗糙集理论的重要研究分支，本文针对邻域多粒度粗糙集模型对象变化的情形提出了一种增量式更新算法。文中首先利用矩阵对邻域多粒度粗糙集模型中的近似关系进行表示，定义了近似关系矩阵的概念，理论分析表明，近似关系矩阵是对整个邻域多粒度粗糙集中邻域类与近似集之间细节关系的直观展示，然后针对信息系统对象增加和对象减少的情形，提出了近似关系矩阵的增量式更新，最后利用近似关系矩阵的增量式更新提出了邻域多粒度粗糙集的增量式更新算法，实验验证了本文算法的有效性和优越性。根据本文提出的邻域多粒度粗糙集增量式更新算法，接下来可以针对增量式属性约简进行进一步地研究。