开放科学（资源服务）标志码（OSID）：

0 概述

经典的粗糙集^[1]在没有任何先验知识的情况下，通过上下近似集表示某个确定的概念，能够处理具有不确定性、不一致性等特点的数据集。粗糙集理论广泛应用于数据挖掘^[2]、推荐系统^[3]、工业控制系统^[4-5]等领域。

信息系统可能伴有部分缺失值或集值。研究人员提出了容差关系^[6]、非对称相似关系^[7]、限制性容差关系^[8]、最大相容类^[9]等二元关系代替不可区分关系，使得泛化的粗糙集模型能够处理集值信息系统。文献[10-11]提出拟单层覆盖粗糙集界于一般覆盖与划分之间，是一个特殊的邻域系统。近似质量是衡量一个模型的标准，文献[12]将拟单层覆盖粗糙集应用于集值信息系统中，并在真实数据集上进行实验，证明了该模型在近似质量和计算效率方面均优于容差关系、非对称相似关系、限制性容差关系以及最大相容类，但是该模型无法应用于动态集值信息系统。

随着时间的推移，信息系统也会持续不断地发生变化。求解近似集的效率将直接影响规则提取和属性约简的效率。当信息系统发生改变时，快速获取更新系统中的近似集成为亟待解决的难题。

增量学习是指充分利用已知的信息并且避免从头开始计算，从而达到提升计算效率的目的。将增量学习灵活运用于动态信息系统中近似集的求解可以显著提升其计算效率。信息系统结构的动态变化方式有属性集的变化^[13-15]、属性值的变化^[16-17]以及对象集的变化。关于对象集发生变化的情况，文献[18]基于模糊优势邻域粗糙集提出动态区间值有序数据的增量特征选择方法。根据云平台下的并行模型MapReduce，文献[19]提出经典粗糙集的并行增量算法，用于更新大规模数据的近似集。当对象批量发生变化时，文献[20]提出一种邻域决策粗糙集模型的增量式更新算法。针对混合型信息系统，文献[21]提出基于邻域决策粗糙集矩阵方法的增量式更新算法。文献[22]提出邻域多粒度粗糙集模型的矩阵化方法并设计了相应的增量更新方法，用于更新正域、负域及其边界域。文献[23]研究了优势粗糙集模型中动态有序数据的增量属性约简方法。

本文提出拟单层覆盖粗糙集中近似集的增量更新算法。当一个对象集添加至原始系统时或一个对象集从原始系统移除时，通过分析拟单层覆盖集中信息单元的变化情况，根据信息单元的变化对各近似集可靠单元和争议单元的相关可靠单元集的影响，设计相应的更新算法。在此基础上，通过计算更新系统中各近似集的最终结果，从而提高近似集的计算效率。

1 基本概念

集值信息系统$ S=\left(U, A, V, f\right) $是一个四元组。其中：$ U $是一个非空有限的对象集，称为论域；$ A $是有限的属性集；$ V $为属性的值域且$ V=\bigcup _{a\in A}{V}_{a} $；$ f:U\times A\to {2}^{{V}_{A}} $是从$ U\times A $到$ V $的集值映射。

定义1    令$ S=\left(U, A, V, f\right) $为集值信息系统，其中$ A=\left({a}_{1}, {a}_{2}, \cdots , {a}_{n}\right) $。对象$ x\in U $的信息解释是一个集值向量。表达式$ \overrightarrow{\mathit{\boldsymbol{x}}}= < f(x, {a}_{1}), f(x, {a}_{2}), \cdots , f(x, {a}_{n}) > $，其中$ f(x, {a}_{i}) $是集合。

定义2    令$ S=\left(U, A, V, f\right) $为集值信息系统。$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{x}= $$ (y\in U|\overrightarrow{\mathit{\boldsymbol{x}}}=\overrightarrow{\mathit{\boldsymbol{y}}}) $是$ S $上的一个信息单元，且$ x\in \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{x} $，$ \overrightarrow{\mathit{\boldsymbol{x}}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{x}} $。如果$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{x}} $中的任意值均为单值，则该信息单元被称为可靠单元。如果$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{x}} $中存在集值，则该信息单元被称为争议单元。$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c} $的相关可靠单元集记为$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}\right) $，其中$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}\right)=(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}\in \mathrm{R}\mathrm{C}|\forall {a}_{i}\in A, x\in \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{x}, $ $ y\in \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{y}, $$ f(x, {a}_{i})\subseteq f(y, {a}_{i}))\mathrm{。} $

可靠单元和争议单元分别记为$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r} $和$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c} $，并且所有可靠元和争议元的集合分别记为$ \mathrm{R}\mathrm{C} $和$ \mathrm{C}\mathrm{C} $。

定理1    令$ S=\left(U, A, V, f\right) $为集值信息系统。$ \mathrm{R}\mathrm{C} $和$ \mathrm{C}\mathrm{C} $分别包含$ S $中所有的可靠单元和争议单元。对应任意$ X\subseteq U $，$ S $上$ X $的DA0和DE0近似集如下：

$ \begin{array}{l}{\underset{\_}{C}}_{\mathrm{D}\mathrm{E}0}\left(X\right)=(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}\in \mathrm{R}\mathrm{C}|\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}\in {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}\left(X\right))\bigcup \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}\in \mathrm{C}\mathrm{C}|\mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}\right)\bigcap {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}\left(X\right)\ne \mathrm{\varnothing })\\ {\stackrel{-}{C}}_{\mathrm{D}\mathrm{A}0}\left(X\right)=(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}\in \mathrm{R}\mathrm{C}|\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}\in {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}\left(X\right))\bigcup \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}\in \mathrm{C}\mathrm{C}|\mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}\right)\subseteq {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}\left(X\right))\\ {\stackrel{-}{C}}_{\mathrm{D}\mathrm{E}0}\left(X\right)=(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}\in \mathrm{R}\mathrm{C}|\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}\in {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}\left(X\right))\bigcup \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}\in \mathrm{C}\mathrm{C}|\mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}\right)\bigcap {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}\left(X\right)\ne \mathrm{\varnothing })\end{array} $

其中：$ {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}\left(X\right)=(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}\in \mathrm{R}\mathrm{C}|\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}\subseteq X) $；$ {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}\left(X\right)=(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}\in $ $ \mathrm{R}\mathrm{C}| $$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}\bigcap X\ne \mathrm{\varnothing }) $。

2 近似集的增量更新

当论域发生变化时，拟单层覆盖粗糙集中的近似集也会发生变化。传统的静态方法将从头开始计算近似集，会浪费大量的时间。本文提出当对象集变化时拟单层覆盖粗糙集的增量更新方法，充分利用已知的计算结果，达到提高计算效率的目的。

2.1 对象增加时近似集动态更新

令$ {S}^{{t}_{0}}=({U}^{{t}_{0}}, A, V, f) $为原始集值信息系统，$ {S}^{\mathrm{\Delta }}=(\mathrm{\Delta }U, A, V, f) $为新增集值信息系统，其中$ {U}^{{t}_{0}} $为原始对象集，$ \mathrm{\Delta }U $为新增对象集。假设系统$ {S}^{{t}_{0}} $和$ {S}^{\mathrm{\Delta }} $中的信息单元分别记为$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{0}} $和$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }} $，系统$ {S}^{{t}_{0}} $中争议单元的相关可靠单元集记为$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}\right) $。当一个对象集$ \mathrm{\Delta }U $被添加到系统$ {S}^{{t}_{0}} $中，形成更新后的集值信息系统$ {S}^{{t}_{1}}=({U}^{{t}_{0}}\bigcup \mathrm{\Delta }U, A, V, f) $，分别记系统$ {S}^{{t}_{1}} $的信息单元及其相关可靠单元集为$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{1}} $和$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}}\right) $。同时，$ X $可能增加$ \mathrm{\Delta }X $至$ {X}^{\text{'}} $，其中$ \mathrm{\Delta }X\subseteq \mathrm{\Delta }U $。因此，在对象集增加过程中，系统$ {S}^{{t}_{0}} $的近似集将由$ {\underset{\_}{C}}_{\mathrm{D}\mathrm{A}0}^{{t}_{0}}\left(X\right) $、$ {\underset{\_}{C}}_{\mathrm{D}\mathrm{E}0}^{{t}_{0}}\left(X\right) $、$ {\stackrel{-}{C}}_{\mathrm{D}\mathrm{A}0}^{{t}_{0}}\left(X\right) $和$ {\stackrel{-}{C}}_{\mathrm{D}\mathrm{E}0}^{{t}_{0}}\left(X\right) $变化为$ {\underset{\_}{C}}_{\mathrm{D}\mathrm{A}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $、$ {\underset{\_}{C}}_{\mathrm{D}\mathrm{E}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $、$ {\stackrel{-}{C}}_{\mathrm{D}\mathrm{A}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $和$ {\stackrel{-}{C}}_{\mathrm{D}\mathrm{E}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $。

定理2    令$ {S}^{{t}_{0}}=({U}^{{t}_{0}}, A, V, f) $为原始集值信息系统，$ {S}^{\mathrm{\Delta }}=(\mathrm{\Delta }U, A, V, f) $为新增集值信息系统，其中$ {U}^{{t}_{0}} $为原始对象集，$ \mathrm{\Delta }U $为新增对象集。对于任意一个$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }} $，如果存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{0}} $，$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }} $并且$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $，则在更新系统$ {S}^{{t}_{1}} $中必然存在$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $且$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\bigcup \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $。如果存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{0}} $，并且任意$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }} $使得$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}}\ne $ $ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}} $成立，则更新系统$ {S}^{{t}_{1}} $中必然存在$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $且$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}} $。如果存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }} $，并且不存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{0}} $使得$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $成立，则$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $。

证明    当$ {S}^{{t}_{0}} $和$ {S}^{\mathrm{\Delta }} $中均存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{0}} $，$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}\in $$ \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }} $使得$ \exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{1}} $，$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}} $，$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}}= $ $ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}} $成立。根据定义2中$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{x} $的定义，$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\bigcup $ $ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $；当仅$ {S}^{{t}_{0}} $中存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{0}} $使得$ \exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in $ $ \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{1}} $，$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}} $成立，则$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}} $；同理第3种情况可证得。

定理3    令$ {S}^{{t}_{0}}=({U}^{{t}_{0}}, A, V, f) $为原始集值信息系统，$ {S}^{\mathrm{\Delta }}=(\mathrm{\Delta }U, A, V, f) $为新增集值信息系统，其中$ {S}^{{t}_{0}} $和$ {S}^{\mathrm{\Delta }} $中的信息单元为$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}} $和$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $。对于$ \forall X $，当$ {S}^{\mathrm{\Delta }} $中的所有对象被添加至$ {S}^{{t}_{0}} $中时，假设$ X $增加$ \mathrm{\Delta }X $至$ {X}^{\text{'}} $，主要有6种情况：1）如果$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{0}}\left(X\right) $，且$ \exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $使得$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $和$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}\subseteq \mathrm{\Delta }X $成立，则$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\bigcup \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}= $ $ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $；2）如果$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{0}}\left(X\right) $，且$ \nexists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $使得$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $成立，则$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $；3）如果$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }} $，$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}\subseteq \mathrm{\Delta }X $，且$ \nexists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $使得$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $成立，则$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $；4）如果$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in $ $ {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{0}}\left(X\right) $，且$ \exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $使得$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $，则$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\bigcup \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}= $ $ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $；5）如果$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{0}}\left(X\right) $，且$ \nexists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $使得$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $成立，则$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $；6）如果$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }} $，$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}\bigcap \mathrm{\Delta }X\ne \mathrm{\varnothing } $，且$ \nexists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $使得$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $成立，则$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $。

证明    关于$ {S}^{{t}_{1}} $中$ {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $的计算，本文对前3种情况进行讨论。因为第1种情况满足定理2中的第1种情况且$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{0}}\left(X\right) $，所以$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\bigcup \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $，$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\subseteq X $。由于$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}\subseteq \mathrm{\Delta }X, {X}^{\text{'}}=X\bigcup \mathrm{\Delta }X $，因此$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\subseteq {X}^{\text{'}} $，$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in $ $ {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $。同理，第2种和第3种情况可证。

关于$ {S}^{{t}_{1}} $中$ {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $的计算，本文对后3种情况进行讨论。如果$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{0}}\left(X\right) $，则$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\bigcap X\ne \mathrm{\varnothing } $。因为$ \exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $使得$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $成立，所以$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\bigcup $$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $且$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\bigcap {X}^{\text{'}}\ne \mathrm{\varnothing } $。因此$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in $ $ {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $。同理，第5种和第6种情况可证。

由定理1可知，如果$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}\in {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}\left(X\right) $，则$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}\in $ $ {\underset{\_}{C}}_{\mathrm{D}\mathrm{A}0\left(\mathrm{D}\mathrm{E}0\right)}\left(X\right) $；如果$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}\in {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}\left(X\right) $，则$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}\in $ $ {\stackrel{-}{C}}_{\mathrm{D}\mathrm{A}0\left(\mathrm{D}\mathrm{E}0\right)}\left(X\right) $。因此，定理2解决了可靠单元的更新问题。当集值信息系统中的对象增加时，由于可靠单元的增加，因此更新后的系统$ {S}^{{t}_{1}} $中的$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}}\right) $可由原始系统$ {S}^{{t}_{0}} $中的$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}\right) $更新得到。根据定理2，本文通过原始系统和新增系统中的信息单元更新获取更新系统的信息单元及其信息解释。

定理4    令$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}\right) $为原始系统$ {S}^{{t}_{0}} $中争议单元的相关可靠单元集，且$ \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }} $分为$ \mathrm{R}{\mathrm{C}}^{\mathrm{\Delta }} $和$ \mathrm{C}{\mathrm{C}}^{\mathrm{\Delta }} $，其中$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{\mathrm{\Delta }}\in \mathrm{R}{\mathrm{C}}^{\mathrm{\Delta }} $和$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{\mathrm{\Delta }}\in \mathrm{C}{\mathrm{C}}^{\mathrm{\Delta }} $为系统内$ {S}^{\mathrm{\Delta }} $中的可靠单元集和争议单元集。如果$ \exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}\in \mathrm{C}{\mathrm{C}}^{{t}_{0}} $且$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}}= $ $ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}}} $，则$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}}\right)=(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{1}}\in \mathrm{R}{\mathrm{C}}^{{t}_{1}}|\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{0}}\in \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}\right), \exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{1}}\in \mathrm{R}{\mathrm{C}}^{{t}_{1}}, $$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{0}}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{1}}})\bigcup (\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{1}}\in \mathrm{R}{\mathrm{C}}^{{t}_{1}}|\exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{\mathrm{\Delta }}, $$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{1}}}\wedge $$ \nexists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{0}}, \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{0}}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{\mathrm{\Delta }}}\wedge \forall {a}_{i}\in A, x\in \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{\mathrm{\Delta }}, y\in \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}}, $$ f(x, {a}_{i})\subseteq f(y, {a}_{i})) $；如果$ \nexists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}\in \mathrm{C}{\mathrm{C}}^{{t}_{0}} $且$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}}} $，则$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}}\right)=(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{1}}\in \mathrm{R}{\mathrm{C}}^{{t}_{1}}|\forall {a}_{i}\in A, {a}_{i}\in A, x\in \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{1}}, y\in $$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}}, f(x, {a}_{i})\subseteq f(y, {a}_{i})) $。

证明    当$ \exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}\in \mathrm{C}{\mathrm{C}}^{{t}_{0}} $且$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}}} $时，已知$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}\right) $，即原始系统$ {S}^{{t}_{0}} $中符合$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}\right) $定义的可靠单元已经得到。本文仅需计算新增系统中符合$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}\right) $定义的可靠单元。由定理2可知，如果$ \exists $ $ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{\mathrm{\Delta }} $，$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{1}}} $且$ \nexists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{0}} $使得$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{0}}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{\mathrm{\Delta }}} $成立，则$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{1}}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{\mathrm{\Delta }} $。因此，$ \forall {a}_{i}\in A, x\in \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{\mathrm{\Delta }}, y\in \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}} $，$ f(x, {a}_{i})\subseteq $ $ f(y, {a}_{i}) $等价于$ \forall {a}_{i}\in A, x\in \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{1}}, $ $ y\in \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}}, $$ f(x, {a}_{i})\subseteq f(y, {a}_{i}) $。根据$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}\right) $的定义可知，$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{1}}\in \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}}\right) $。当$ \nexists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}\in $ $ \mathrm{C}{\mathrm{C}}^{{t}_{0}} $，$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}}} $时，根据定义计算即可。

2.2 对象移除时近似集动态更新

令$ {S}^{{t}_{0}}=({U}^{{t}_{0}}, A, V, f) $​为原始集值信息系统，$ {S}^{\mathrm{\Delta }}=(\mathrm{\Delta }U, A, V, f) $为被移除的集值信息系统，其中$ {U}^{{t}_{0}} $为原始对象集，$ \mathrm{\Delta }U $为被移除的对象集。假设系统$ {S}^{{t}_{0}} $和$ {S}^{\mathrm{\Delta }} $中的信息单元分别记为$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{0}} $和$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }} $，$ {S}^{{t}_{0}} $中争议单元的相关可靠单元集记为$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}\right) $。当一个对象集$ \mathrm{\Delta }U $从$ {S}^{{t}_{0}} $中移除时，更新后的集值信息系统$ {S}^{{t}_{1}}=({U}^{{t}_{0}}-\mathrm{\Delta }U, A, V, f) $将会形成，记$ {S}^{{t}_{1}} $的信息单元及其相关可靠单元集分别为$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{1}} $和$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}}\right) $。同时，$ X $将被移除$ \mathrm{\Delta }X $至$ {X}^{\text{'}} $，其中$ \mathrm{\Delta }X\subseteq \mathrm{\Delta }U $。因此，在对象集移除过程中，$ {S}^{{t}_{0}} $中的近似集将由$ {\underset{\_}{C}}_{\mathrm{D}\mathrm{A}0}^{{t}_{0}}\left(X\right) $，$ {\underset{\_}{C}}_{\mathrm{D}\mathrm{E}0}^{{t}_{0}}\left(X\right) $，$ {\stackrel{-}{C}}_{\mathrm{D}\mathrm{A}0}^{{t}_{0}}\left(X\right) $和$ {\stackrel{-}{C}}_{\mathrm{D}\mathrm{E}0}^{{t}_{0}}\left(X\right) $变化为$ {\underset{\_}{C}}_{\mathrm{D}\mathrm{A}0}^{{t}_{1}}\left({X}^{\text{'}}\right), {\underset{\_}{C}}_{\mathrm{D}\mathrm{E}0}^{{t}_{1}}\left({X}^{\text{'}}\right), {\stackrel{-}{C}}_{\mathrm{D}\mathrm{A}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $和$ {\stackrel{-}{C}}_{\mathrm{D}\mathrm{E}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $。

定理5    令$ {S}^{{t}_{0}}=({U}^{{t}_{0}}, A, V, f) $为原始集值信息系统，$ {S}^{\mathrm{\Delta }}=(\mathrm{\Delta }U, A, V, f) $为被移除的集值信息系统，其中$ {U}^{{t}_{0}} $为原始对象集，$ \mathrm{\Delta }U $为被移除的对象集。对于任意一个$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }} $，存在3种情况：1）如果存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{0}} $，$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $并且$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}} $，则在更新后的系统$ {S}^{{t}_{1}} $中必然不存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{1}} $，使得$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $成立；2）如果存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{0}}, $ $ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $并且$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}⊊\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}} $，则在更新后的系统$ {S}^{{t}_{1}} $中存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}-\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{1}} $，使得$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}= $ $ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $成立；3）如果存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{0}} $但$ \nexists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}\in $ $ \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }} $，$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $，则在更新后的系统$ {S}^{{t}_{1}} $中存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{1}} $，使得$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $成立。

证明    由于$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $是被移除的信息单元，因此任意$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $一定存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{0}} $满足$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $。如果$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}} $，则说明该信息单元中的所有对象均被移除。因此该信息单元不存在$ {S}^{{t}_{1}} $的$ \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{1}} $中。如果$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}⊊\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}} $，则说明该信息单元中的部分对象均被移除。因此$ \exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{1}} $满足$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}-\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $且$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $。第3种情况说明$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}} $中的对象未发生改变，因此$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{1}} $且$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $。

定理6    令$ {S}^{{t}_{0}}=({U}^{{t}_{0}}, A, V, f) $为原始集值信息系统，$ {S}^{\mathrm{\Delta }}=(\mathrm{\Delta }U, A, V, f) $为被移除的集值信息系统，其中$ {S}^{{t}_{0}} $和$ {S}^{\mathrm{\Delta }} $中的信息单元为$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}} $和$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $。对于$ \forall X $，当$ {S}^{\mathrm{\Delta }} $中的所有对象从$ {S}^{{t}_{0}} $中移除时，假设$ X $移除$ \mathrm{\Delta }X $至$ {X}^{\text{'}} $，存在以下5种情况：1）如果$ \exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $使得$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $且$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}} $成立，则$ \nexists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in $ $ \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{1}} $使得$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $和$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $成立；2）如果$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{0}}\left(X\right) $且$ \exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $满足$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $和$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}⊊\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}} $，则$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}-\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}= $ $ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in $ $ {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $；3）如果$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{0}}\left(X\right) $但$ \nexists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }} $，$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $，则$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in $ $ {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $；4）如果$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in $ $ {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{0}}\left(X\right) $且$ \exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $满足$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $和$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}⊊\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}} $，则$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}- $ $ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $；如果$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\bigcap {X}^{\text{'}}\ne \mathrm{\varnothing } $，则$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{}^{{t}_{1}}\in {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $；5）如果$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{0}}\left(X\right) $但$ \nexists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }} $，$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}= $ $ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $且$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\bigcap {X}^{\text{'}}\ne \mathrm{\varnothing } $，则$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $。

证明    由定理5可知，如果$ \exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $使得$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $且$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}} $成立，则$ {S}^{{t}_{1}} $中必然不存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in $ $ \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{1}} $。因此，第1种情况可证得。如果$ \exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $使得$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}= $$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $和$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}⊊\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}} $成立，则$ \exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{1}} $，$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}-\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $且$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}}= $ $ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}} $。因为$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{0}}\left(X\right) $，所以$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\subseteq X $。由于$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\bigcap \mathrm{\Delta }X=\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $，因此$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}-\mathrm{\Delta }X $ $ =\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}-\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }} $$ \subseteq X-\mathrm{\Delta }X $，即$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\subseteq {X}^{\text{'}} $。因此$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{1}}\in {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $。同理，第3种情况可证。第4种和第5种情况根据定理1中$ {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}^{}\left(X\right) $的定义即可证得。

定理7    令$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}\right) $为原始系统$ {S}^{{t}_{0}} $中争议单元的相关可靠单元集。如果$ \exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}\in \mathrm{C}{\mathrm{C}}^{{t}_{0}} $，$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{\mathrm{c}}^{{\mathrm{t}}_{1}}} $，则$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}}\right)=\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{1}}\right|\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{0}}\in \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}\right), \exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{1}}\in \mathrm{R}{\mathrm{C}}^{{t}_{1}}, \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{0}}}= $ $ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{1}}}) $。

证明    由定理5可知，一些信息单元可能被移除，所以可靠单元也有可能被移除。如果$ \exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}}\in \mathrm{C}{\mathrm{C}}^{{t}_{1}} $，$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}}} $，则$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}} $移除$ \mathrm{\Delta }X $后得到$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}} $不为空。同时，如果$ \exists \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{0}}\in \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}\right) $且存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{1}}\in \mathrm{R}{\mathrm{C}}^{{t}_{1}}, \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{0}}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{1}}} $，则$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{0}} $移除$ \mathrm{\Delta }X $后得到$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{1}} $不为空。根据$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}\right) $的定义可知，$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{r}^{{t}_{1}}\in \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}}\right) $。

3 本文算法

本文设计增量更新算法，算法1为静态算法，算法2和算法3分别为对象集增加时和减少时的增量更新算法。

3.1 静态算法

在定义2和定理1的理论基础上，本文设计相应的静态算法。

算法1    计算拟单层覆盖粗糙集中近似集的静态算法

输入    集值信息系统$ S=\left(U, A, V, f\right) $和目标概念$ X $

输出    $ {\underset{\_}{C}}_{\mathrm{D}\mathrm{A}0}\left(X\right), {\underset{\_}{C}}_{\mathrm{D}\mathrm{E}0}\left(X\right), {\stackrel{-}{C}}_{\mathrm{D}\mathrm{A}0}\left(X\right) $和$ {\stackrel{-}{C}}_{\mathrm{D}\mathrm{E}0}\left(X\right) $

1.根据定义2构造信息单元并分为可靠单元和争议单元；

2.根据定理1，通过判断可靠单元与$ \mathrm{X} $之间的关系计算$ {\underset{\_}{\mathrm{C}}}_{\mathrm{G}\mathrm{C}0}\left(\mathrm{X}\right) $和$ {\stackrel{-}{\mathrm{C}}}_{\mathrm{G}\mathrm{C}0}\left(\mathrm{X}\right) $；

3.根据$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{\mathrm{c}}\right) $的定义计算争议单元的相关可靠单元集；

4.根据定理1，计算$ {\underset{\_}{\mathrm{C}}}_{\mathrm{D}\mathrm{A}0}\left(\mathrm{X}\right) $，$ {\underset{\_}{\mathrm{C}}}_{\mathrm{D}\mathrm{E}0}\left(\mathrm{X}\right) $，$ {\stackrel{-}{\mathrm{C}}}_{\mathrm{D}\mathrm{A}0}\left(\mathrm{X}\right) $和$ {\stackrel{-}{C}}_{\mathrm{D}\mathrm{E}0}\left(\mathrm{X}\right) $。

算法1主要分为4个步骤：1）构造信息单元的时间复杂度为$ O\left(\left|U\right|\right) $，其中$ \left|U\right| $为集值信息系统中包含对象的数目；2）计算$ {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}\left(X\right) $和$ {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}\left(X\right) $的时间复杂度为$ O\left(\left|\mathrm{R}\mathrm{C}\right|\right) $，其中$ \left|\mathrm{R}\mathrm{C}\right| $为可靠单元的数目；3）计算$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}\right) $的时间复杂度为$ O\left(\left|\mathrm{C}\mathrm{C}\right|\times \left|\mathrm{R}\mathrm{C}\right|\right) $，其中$ \left|\mathrm{C}\mathrm{C}\right| $为争议单元的数目；4）计算$ {\underset{\_}{C}}_{\mathrm{D}\mathrm{A}0}\left(X\right) $、$ {\underset{\_}{C}}_{\mathrm{D}\mathrm{E}0}\left(X\right) $、$ {\stackrel{-}{C}}_{\mathrm{D}\mathrm{A}0}\left(X\right) $和$ {\stackrel{-}{C}}_{\mathrm{D}\mathrm{E}0}\left(X\right) $的时间复杂度为$ O\left(\left|\mathrm{C}\mathrm{E}\mathrm{L}\mathrm{L}\right|\right) $，其中$ \left|\mathrm{C}\mathrm{E}\mathrm{L}\mathrm{L}\right| $为信息单元的数目，即可靠单元与争议单元数目之和。由于信息单元是互不相交的对象集，因此其大小与整体对象个数相比可以忽略。算法1的整体时间复杂度为$ O\left(\right|U|+|\mathrm{R}\mathrm{C}|+|\mathrm{C}\mathrm{C}|\times |\mathrm{R}\mathrm{C}|+|\mathrm{C}\mathrm{E}\mathrm{L}\mathrm{L}\left|\right)\approx $ $ O\left(\right|U|+|\mathrm{C}\mathrm{C}|\times |\mathrm{R}\mathrm{C}\left|\right) $。

3.2 对象集添加时近似集的增量更新算法

当原始系统中添加一个对象集时，根据2.1节提出的方法设计相应的增量更新算法。

算法2    添加一个对象集时动态更新拟单层覆盖粗糙集中近似集的增量算法

输入    原始集值信息系统$ {S}^{{t}_{0}}=({U}^{{t}_{0}}, A, V, f) $中的信息单元$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{0}} $，$ {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{0}} $，$ {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{0}} $以及$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}\right) $，其中$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}} $ $ \in \mathrm{C}{\mathrm{C}}^{{t}_{0}} $，新增集值信息系统$ {S}^{\mathrm{\Delta }}=(\mathrm{\Delta }U, A, V, f) $，被添加的概念$ \mathrm{\Delta }X $以及更新后的概念$ {X}^{\text{'}} $

输出    $ {\underset{\_}{C}}_{\mathrm{D}\mathrm{A}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $，$ {\underset{\_}{C}}_{\mathrm{D}\mathrm{E}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $，$ {\stackrel{-}{C}}_{\mathrm{D}\mathrm{A}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $和$ {\stackrel{-}{C}}_{\mathrm{D}\mathrm{E}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $

1.使用算法1中构造信息单元的方法计算$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }} $；

2.根据定理2，通过$ {\mathrm{S}}^{{\mathrm{t}}_{0}} $和$ {\mathrm{S}}^{\mathrm{\Delta }} $中的信息单元形成更新系统中的信息单元，针对更新系统中的可靠单元，通过定理3判断其是否属于$ {\underset{\_}{\mathrm{C}}}_{\mathrm{G}\mathrm{C}0}^{{\mathrm{t}}_{1}}\left({\mathrm{X}}^{\mathrm{\text{'}}}\right) $和$ {\stackrel{-}{\mathrm{C}}}_{\mathrm{G}\mathrm{C}0}^{{\mathrm{t}}_{1}}\left({\mathrm{X}}^{\mathrm{\text{'}}}\right) $；

3.根据定理4，通过判断原始系统中是否存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{\mathrm{c}}^{{\mathrm{t}}_{0}} $，使得更新系统中存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{\mathrm{c}}^{{\mathrm{t}}_{1}} $与其信息解释相等，采取不同的方式计算$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{\mathrm{c}}^{{\mathrm{t}}_{1}}\right) $；

4.根据定理1，计算$ {\underset{\_}{\mathrm{C}}}_{\mathrm{D}\mathrm{A}0}^{{\mathrm{t}}_{1}}\left({\mathrm{X}}^{\mathrm{\text{'}}}\right) $，$ {\underset{\_}{\mathrm{C}}}_{\mathrm{D}\mathrm{E}0}^{{\mathrm{t}}_{1}}\left({\mathrm{X}}^{\mathrm{\text{'}}}\right) $，$ {\stackrel{-}{\mathrm{C}}}_{\mathrm{D}\mathrm{A}0}^{{\mathrm{t}}_{1}}\left({\mathrm{X}}^{\mathrm{\text{'}}}\right) $和$ {\stackrel{-}{\mathrm{C}}}_{\mathrm{D}\mathrm{E}0}^{{\mathrm{t}}_{1}}\left({\mathrm{X}}^{\mathrm{\text{'}}}\right) $。

算法2主要分为4个步骤：1）构造新增系统中信息单元的时间复杂度为$ O\left(\right|\mathrm{\Delta }U\left|\right) $；2）形成更新系统中的信息单元并计算$ {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $和$ {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $，仅需遍历$ \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }} $，其时间复杂度为$ O\left(\right|\mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }}\left|\right) $；3）如果原始系统中存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}} $，使得更新系统中存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}} $与其信息解释相等，则遍历$ \mathrm{R}{\mathrm{C}}^{\mathrm{\Delta }} $，其时间复杂度为$ O\left(\right|\mathrm{C}{\mathrm{C}}^{{t}_{0}}|\times |\mathrm{R}{\mathrm{C}}^{\mathrm{\Delta }}\left|\right) $，否则需要遍历$ \mathrm{R}{\mathrm{C}}^{{t}_{1}} $，其时间复杂度为$ O\left(\right|\mathrm{C}{\mathrm{C}}^{\mathrm{\Delta }}|\times |\mathrm{R}{\mathrm{C}}^{{t}_{1}}\left|\right) $；4）时间复杂度为$ O\left(\right|\mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{1}}\left|\right) $。由于算法2的整体时间复杂度为$ O\left(\right|\mathrm{\Delta }U|+|\mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }}|+|\mathrm{C}{\mathrm{C}}^{{t}_{0}}|\times |\mathrm{R}{\mathrm{C}}^{\mathrm{\Delta }}|+|\mathrm{C}{\mathrm{C}}^{\mathrm{\Delta }}|\times |\mathrm{R}{\mathrm{C}}^{{t}_{1}}\left|\right)\approx O\left(\right|\mathrm{\Delta }U|+ $ $ \left|\mathrm{C}{\mathrm{C}}^{{t}_{0}}\right|\times \left|\mathrm{R}{\mathrm{C}}^{\mathrm{\Delta }}\right|+\left|\mathrm{C}{\mathrm{C}}^{\mathrm{\Delta }}\right|\times \left|\mathrm{R}{\mathrm{C}}^{{t}_{1}}\right|) < O(\left|\mathrm{\Delta }U\right|+ $$ \left(\right|\mathrm{C}{\mathrm{C}}^{{t}_{0}}|+|\mathrm{C}{\mathrm{C}}^{\mathrm{\Delta }}\left|\right)\times $$ \left|\mathrm{R}{\mathrm{C}}^{{t}_{1}}\right|)=O(\left|{U}^{{t}_{1}}\right|+\left|\mathrm{C}{\mathrm{C}}^{{t}_{1}}\right|\times \left|\mathrm{R}{\mathrm{C}}^{{t}_{1}}\right|) $，因此算法2的时间复杂度低于算法1的时间复杂度。

3.3 对象集移除时近似集的增量更新算法

当原始系统中移除一个对象集时，根据2.2节提出的方法设计相应的增量更新算法。

算法3    移除一个对象集时动态更新拟单层覆盖粗糙集中近似集的增量算法

输入    原始集值信息系统$ {S}^{{t}_{0}}=({U}^{{t}_{0}}, A, V, f) $中的信息单元$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{{t}_{0}}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{0}} $，$ {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{0}} $，$ {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{0}} $以及$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}}\right) $，其中$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{0}} $ $ \in \mathrm{C}{\mathrm{C}}^{{t}_{0}} $，被移除的集值信息系统$ {S}^{\mathrm{\Delta }}=(\mathrm{\Delta }U, A, V, f) $，被移除的概念$ \mathrm{\Delta }X $以及更新后的概念$ {X}^{\text{'}} $

输出    $ {\underset{\_}{C}}_{\mathrm{D}\mathrm{A}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $，$ {\underset{\_}{C}}_{\mathrm{D}\mathrm{E}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $，$ {\stackrel{-}{C}}_{\mathrm{D}\mathrm{A}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $和$ {\stackrel{-}{C}}_{\mathrm{D}\mathrm{E}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $

1.使用算法1中构造信息单元的方法计算$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}^{\mathrm{\Delta }}\in \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }} $；

2.根据定理5，计算更新系统中的信息单元，针对更新系统中的可靠单元，进一步通过定理6判断其是否属于$ {\underset{\_}{\mathrm{C}}}_{\mathrm{G}\mathrm{C}0}^{{\mathrm{t}}_{1}}\left({\mathrm{X}}^{\mathrm{\text{'}}}\right) $和$ {\stackrel{-}{\mathrm{C}}}_{\mathrm{G}\mathrm{C}0}^{{\mathrm{t}}_{1}}\left({\mathrm{X}}^{\mathrm{\text{'}}}\right) $；

3.如果原始系统中存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{\mathrm{c}}^{{\mathrm{t}}_{0}} $，使得更新系统中存在$ \mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{\mathrm{c}}^{{\mathrm{t}}_{1}} $且$ \overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{\mathrm{c}}^{{\mathrm{t}}_{0}}}=\overrightarrow{\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{\mathrm{c}}^{{\mathrm{t}}_{1}}} $，则根据定理7的方法计算$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}}\right) $；

4.根据定理1，计算$ {\underset{\_}{\mathrm{C}}}_{\mathrm{D}\mathrm{A}0}^{{\mathrm{t}}_{1}}\left({\mathrm{X}}^{\mathrm{\text{'}}}\right) $，$ {\underset{\_}{\mathrm{C}}}_{\mathrm{D}\mathrm{E}0}^{{\mathrm{t}}_{1}}\left({\mathrm{X}}^{\mathrm{\text{'}}}\right) $，$ {\stackrel{-}{\mathrm{C}}}_{\mathrm{D}\mathrm{A}0}^{{\mathrm{t}}_{1}}\left({\mathrm{X}}^{\mathrm{\text{'}}}\right) $和$ {\stackrel{-}{\mathrm{C}}}_{\mathrm{D}\mathrm{E}0}^{{\mathrm{t}}_{1}}\left({\mathrm{X}}^{\mathrm{\text{'}}}\right) $。

在算法3中步骤1的时间复杂度为$ O\left(\right|\mathrm{\Delta }U\left|\right) $。步骤2计算更新系统中的信息单元和$ {\underset{\_}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $，$ {\stackrel{-}{C}}_{\mathrm{G}\mathrm{C}0}^{{t}_{1}}\left({X}^{\text{'}}\right) $需遍历$ \mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }} $，因此其时间复杂度为$ O\left(\right|\mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }}\left|\right) $。根据定理7，算法3计算$ \mathrm{R}\mathrm{S}\left(\mathrm{C}\mathrm{e}\mathrm{l}{\mathrm{l}}_{c}^{{t}_{1}}\right) $的时间复杂度为$ O\left(\right|\mathrm{C}{\mathrm{C}}^{{t}_{1}}\left|\right) $。算法3的步骤4时间复杂度为$ O\left(\right|\mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{1}}\left|\right) $。由于算法3的时间复杂度为$ O\left(\right|\mathrm{\Delta }U|+|\mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }}|+|\mathrm{C}{\mathrm{C}}^{{t}_{1}}|+|\mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{1}}\left|\right) $且小于$ O\left(\right|{U}^{{t}_{1}}|+ $ $ \left|\mathrm{C}{\mathrm{C}}^{{t}_{1}}\right|\times \left|\mathrm{R}{\mathrm{C}}^{{t}_{1}}\right|) $，因此算法3的时间复杂度低于算法1的时间复杂度。

本文通过对比静态算法和两个增量算法的时间复杂度可知，无论对象集被添加还是被移除，增量算法的时间复杂度总低于静态算法的时间复杂度。

4 实验结果与分析

本文通过在真实数据集上的一系列实验验证增量算法的有效性。在计算结果保持一致的前提下，本文计算拟单层覆盖粗糙集中近似集所消耗的时间，对比静态算法和增量算法的效率。

本文实验分为对象添加和对象移除两种情况。这两种情况下的对比实验均在UCI数据集上进行。数据集的具体描述如表 1所示。

本文对数据集进行预处理形成对应的集值信息系统，分别计算每个属性的最小值、最大值、平均数和中位数，将其从小到大排列产生3个间隔。如果该列的某个属性值位于第1个间隔，则该属性值对应于单值记录。如果其位于第3个间隔，则该属性值对应于与前者不同的单值记录，否则该值对应于前两者组成的集值记录。

实验环境的操作系统为Windows 10，CPU为Intel^® Core^TM i7-9750H，内存为16 GB。本文使用Java编程语言在IDEA平台上实现静态和增量算法，其中Java虚拟机版本为JVM 1.8。

当对象集发生变化时，本文在保持原始数据集包含对象数不变的前提下，依次增加发生变化（被添加到原始系统或从原始系统中移除）的对象数，对比静态算法和增量算法的计算时间，以验证增量理论和对应算法的有效性。

对于一个对象集被添加至原始集值信息系统的情况，本文对数据集进行如下处理：1）取出前50%的对象作为原始数据；2）将后50%的对象平均划分为10份；3）依次将10%，20%，…，100%添加至原始数据。针对算法1和算法2，本文使用以上产生的10组添加对象数不同的数据进行实验。在不同的数据集上，当对象增加时算法1和算法2计算时间的对比如图 1所示。

从图 1可以看出，随着添加至原始数据集中对象数目的增加，算法1和算法2的计算时间都呈增加趋势，但算法1对应曲线的斜率更大，并且计算时间比算法2多。因此，算法1的效率低于算法2。当数据集中包含对象增加时，信息单元（可靠单元和争议单元）的数目也会随之增加。根据算法1和算法2的时间复杂度可知，2个算法随着对象集的增加所需的计算时间也会增加，即图 1的结果也与时间复杂度的分析保持一致。

当对象添加率为10%、50%和100%时，静态算法1和增量算法2计算近似集所需运行时间的比值如表 2所示。从表 2可以看出，随着对象添加率的增加，算法1和算法运行时间的比值越来越小。在Sensorless数据集上，当对象添加率达到100%时，算法1的执行时间为4.155 s，而算法2仅需0.224 s，前者仍是后者的18倍。

对于一个对象集从原始集值信息系统中移除的情况，本文对数据集进行如下处理：1）将完整的数据集作为原始数据；2）将后50%的对象平均划分为10份；3）依次将10%，20%，…，100%从原始数据中移除。针对算法1和算法3，本文使用以上产生的10组移除对象数中不同的数据进行实验。在不同的数据集上，当对象移除率增加时算法1和算法3的计算时间对比如图 2所示。从图 2可以看出，随着移除对象的增加，算法1呈下降趋势，而算法3呈上升趋势，但是算法3的曲线总在算法1对应曲线的下方。因此，当论域中部分对象集移除时算法3的效率更高。

当对象移除率为10%、50%和100%时，静态算法1和增量算法3计算所需运行时间的比值如表 3所示。

从表 3可以看出，当对象移除率增加时，静态算法1和增量算法3计算所需运行时间的比值越来越小。在Sensorless数据集上，当对象移除率达到100%时，算法1的执行时间为2.489 s，而算法3仅需0.221 s，前者是后者的11.26倍。

在不同数据集上，对象移除率为10%和100%时$ \left|\mathrm{\Delta }U\right|+\left|\mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }}\right|+\left|\mathrm{C}{\mathrm{C}}^{{t}_{1}}\right|+\left|\mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{1}}\right| $如表 4所示。当在集值信息系统中移除一个对象集$ \mathrm{\Delta }U $时，由于更新后系统中对象数$ \left|{U}^{{t}_{1}}\right| $和信息单元（可靠单元$ \mathrm{R}{\mathrm{C}}^{{t}_{1}} $和争议单元$ \mathrm{C}{\mathrm{C}}^{{t}_{1}} $）的数目也随之减少，因此算法1的计算时间减少。当被移除对象集$ \mathrm{\Delta }U $增大时，$ \left|\mathrm{\Delta }U\right|+\left|\mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{\mathrm{\Delta }}\right| $变大，$ \left|\mathrm{C}{\mathrm{C}}^{{t}_{1}}\right|+\left|\mathrm{C}\mathrm{E}\mathrm{L}{\mathrm{L}}^{{t}_{1}}\right| $变小，但前者的增量大于后者的减量，因此在此过程中前者与后者总和是变大的。因此算法3呈上升趋势，并且图 2的结果与时间复杂度的分析保持一致。

5 结束语

因集值信息系统中的对象集随时间的推移而增加或移除，导致拟单层覆盖粗糙集中的近似集发生变化。本文结合增量学习与拟单层覆盖粗糙集，提出近似集的增量更新算法。通过设计信息单元、可靠单元和争议单元的更新方法，以达到提高计算效率的目的。构建与更新算法相对应的增量算法，并分析其时间复杂度。在UCI数据集上进行实验，结果表明，当对象集发生变化时，本文算法相较于静态算法的近似集计算效率高。下一步将拟单层覆盖粗糙集增量更新算法与大数据框架相结合，并对本文增量更新算法的并行化问题进行研究，使其能够实时处理海量数据。