第4期 孙海霞：基于对象变化的邻域决策粗糙集动态更新算法 ·751· 中的对象计算概率便可完成最终的更新，因此上 IS@=(U,AT),X记为Xo,近似集N(X)和 近似集的增量式更新同样具有很高的计算效率。 N(分别记为N(X,)和N”(X)。 定理5和定理6分别给出当邻域型信息系统 2)对于x∈△U(1≤i≤)，将x从邻域型信息 移除一个对象时上下近似集的增量式更新问题， 系统IS-=(U-),AT)中移除，新的信息系统表示 当信息系统同时移除多个对象时，可以根据定理 为IS0=(U%,AT),其中U0=U-)-{x,此时新的 5和定理6逐步进行迭代，直至完成最终的更新。 近似对象集为X。 3邻域决策粗糙集更新算法 3)计算对象的邻域类6以(x),然后根据定 理5和定理6在aX-)和(X-)的基础 根据本文所提出的增量式更新方法，接下来 上增量式计算a(X)和N”(XO)。 将进一步提出对应的邻域决策粗糙集增量式更新 4)重复迭代计算步骤2)3) 算法，具体如算法1和算法2所示。 5)令 算法1论域增加时邻域决策粗糙集的增量 Na(X)=Nam(X)方 式更新算法 x)=x0. 输入1)邻域型信息系统IS=(U,AT),邻域 返回(X)和N(X)。 半径为6，阈值(@，)。近似对象集X关于属性子 在算法1所示的增量式计算过程中，每次在 集AcAT的近似集YPX和(X。 更新前信息系统的上下近似基础上进一步计算新 2)信息系统增加对象集△U+={,对，…，x, 的上下近似集，并且定理2和定理3已经表明，只 新的邻域型信息系统为IS*=(U=UU△U+,AT), 需要计算新增对象的邻域类，便可以完成最终的 新的近似对象集为X。 更新，而不必去计算其他对象的邻域类，这样大 输出新的近似集Na(X)和N(X)。 大减少了重复的计算量，提高了更新的效率，因 1)将初始时的信息系统IS=(U,AT)记为 此整个算法1和算法2的时间复杂度可表示为 IS=(U0,AT),X记为Xo,近似集N(X)和 OA·l1·△U。 NX分别记为(X)和N(x)。 2)对于∈△U(1≤i≤)，将x对加人邻域型 4实验分析 信息系统IS-)=(U-”,AT)中，新的信息系统表示 为了验证所提出增量式更新算法的有效性， 为IS0=(U,AT),其中U而=U-U{x1,此时新的 将通过实验比较的方式进行验证。本实验主要将 近似对象集为X。 文中所提出的增量式更新算法与传统的非增量更 3)计算对象x的邻域类6(x),然后根据定 新算法对同一组数据集进行动态更新计算，通过 理2和定理3在N(X-)和(X-)的基础 比较他们的动态更新效率来验证算法的有效性， 上增量式计算(XO)和N(XO)。 其中表1所示的是实验中所使用的数据集，这些 4)重复迭代计算步骤2)~3)。 数据集均来源于UCI数据集库，其中数据集的各 5)令 个属性均为数值类型。整个实验所运行的硬件环 Ne(X)=N(X)方 境为Intel Core G45603.5GHz处理器和DDR4 NX)=NX). 8GB内存。 返回X)和(X*)。 表1所示的均为静态的数据集，为了模拟数 算法2论域减少时邻域决策粗糙集的增量 据集动态变化的情形，本实验采用其他学者常用 式更新算法 的处理方法21，即让数据集按照论域平均分 输入1)邻域型信息系统IS=(U,AT),邻域 成多个对象集，然后通过将这些对象集逐渐进行 半径为6，阈值(a,B)。近似对象集X关于属性子 合并，达到了数据集论域动态增加的效果，将原 集ASAT的近似集N(X和N(X)。 始论域逐渐对这些对象集进行移除，便达到了数 2)信息系统减少对象集△U={x,5,…,x, 据集论域动态的减少。本实验将论域平均分成 新的邻域型信息系统为IS=(U~=U-△U,AT), 9个部分，这样可以构造出数据集的8次动态更 新的近似对象集为X。 新。实验中将数据集的决策类作为邻域决策粗糙 输出新的近似集Y(X)和N(X)。 集的近似对象集，即计算数据集每个决策类的上 1)将初始时的信息系统IS=(U,AT)记为 下近似增量式更新。实验中每个数据集的属性值中的对象计算概率便可完成最终的更新，因此上 近似集的增量式更新同样具有很高的计算效率。 定理 5 和定理 6 分别给出当邻域型信息系统 移除一个对象时上下近似集的增量式更新问题， 当信息系统同时移除多个对象时，可以根据定理 5 和定理 6 逐步进行迭代，直至完成最终的更新。 3 邻域决策粗糙集更新算法 根据本文所提出的增量式更新方法，接下来 将进一步提出对应的邻域决策粗糙集增量式更新 算法，具体如算法 1 和算法 2 所示。 算法 1 论域增加时邻域决策粗糙集的增量 式更新算法 IS = (U,AT) δ (α, β) X A ⊆ AT N (α,β) A (X) N (α,β) A (X) 输入 1) 邻域型信息系统 ，邻域 半径为 ，阈值 。近似对象集 关于属性子 集 的近似集 和 。 ∆U + = {x + 1 , x + 2 ,··· , x + s } IS+ = (U + = U ∪∆U + ,AT) X + 2) 信息系统增加对象集 ， 新的邻域型信息系统为 ， 新的近似对象集为 。 N (α,β) A (X + ) N (α,β) A (X + 输出 新的近似集 和 )。 IS = (U,AT) IS(0) = (U (0) ,AT) X X (0) N (α,β) A (X) N (α,β) A (X) N (α,β) A (X (0)) N (α,β) A (X (0)) 1 ) 将初始时的信息系统 记 为 ， 记 为 ，近似集 和 分别记为 和 。 x + i ∈ ∆U + (1 ⩽ i ⩽ s) x + i IS(i−1) = (U (i−1) ,AT) IS(i) = (U (i) ,AT) U (i) = U (i−1) ∪ {x + i } X (i) 2) 对于 ，将 加入邻域型 信息系统 中，新的信息系统表示 为 ，其中 ，此时新的 近似对象集为 。 x + i δ U (i) A (x + i ) N (α,β) A (X (i−1)) N (α,β) A (X (i−1)) N (α,β) A (X (i) ) N (α,β) A (X (i) ) 3) 计算对象 的邻域类 ，然后根据定 理 2 和定理 3 在 和 的基础 上增量式计算 和 。 4) 重复迭代计算步骤 2）~3）。 5) 令 N (α,β) A (X + ) = N (α,β) A (X (s) ); N (α,β) A (X + ) = N (α,β) A (X (s) ). N (α,β) A (X + ) N (α,β) A (X + 返回 和 )。 算法 2 论域减少时邻域决策粗糙集的增量 式更新算法 IS = (U,AT) δ (α, β) X A ⊆ AT N (α,β) A (X) N (α,β) A (X) 输入 1) 邻域型信息系统 ，邻域 半径为 ，阈值 。近似对象集 关于属性子 集 的近似集 和 。 ∆U − = {x − 1 , x − 2 ,··· , x − t } IS− = (U − = U −∆U − ,AT) X − 2) 信息系统减少对象集 ， 新的邻域型信息系统为 ， 新的近似对象集为 。 N (α,β) A (X − ) N (α,β) A (X − 输出 新的近似集 和 )。 1 ) 将初始时的信息系统 IS = (U,AT) 记 为 IS(0) = (U (0) ,AT) X X (0) N (α,β) A (X) N (α,β) A (X) N (α,β) A (X (0)) N (α,β) A (X (0)) ， 记 为 ，近似集 和 分别记为 和 。 x − i ∈ ∆U − (1 ⩽ i ⩽ t) x − i IS(i−1) = (U (i−1) ,AT) IS(i) = (U (i) ,AT) U (i) = U (i−1) − {x − i } X (i) 2) 对于 ，将 从邻域型信息 系统 中移除，新的信息系统表示 为 ，其中 ，此时新的 近似对象集为 。 x − i δ U (i) A (x − i ) N (α,β) A (X (i−1)) N (α,β) A (X (i−1)) N (α,β) A (X (i) ) N (α,β) A (X (i) ) 3) 计算对象 的邻域类 ，然后根据定 理 5 和定理 6 在 和 的基础 上增量式计算 和 。 4) 重复迭代计算步骤 2)~3) 5) 令 N (α,β) A (X − ) = N (α,β) A (X (t) ); N (α,β) A (X − ) = N (α,β) A (X (t) ). N (α,β) A (X − ) N (α,β) A (X − 返回 和 )。 O(|A| · |U| · |∆U|) 在算法 1 所示的增量式计算过程中，每次在 更新前信息系统的上下近似基础上进一步计算新 的上下近似集，并且定理 2 和定理 3 已经表明，只 需要计算新增对象的邻域类，便可以完成最终的 更新，而不必去计算其他对象的邻域类，这样大 大减少了重复的计算量，提高了更新的效率，因 此整个算法 1 和算法 2 的时间复杂度可表示为 。 4 实验分析 为了验证所提出增量式更新算法的有效性， 将通过实验比较的方式进行验证。本实验主要将 文中所提出的增量式更新算法与传统的非增量更 新算法对同一组数据集进行动态更新计算，通过 比较他们的动态更新效率来验证算法的有效性， 其中表 1 所示的是实验中所使用的数据集，这些 数据集均来源于 UCI 数据集库，其中数据集的各 个属性均为数值类型。整个实验所运行的硬件环 境为 Intel Core G4560 3.5 GHz 处理器和 DDR4 8 GB 内存。 表 1 所示的均为静态的数据集，为了模拟数 据集动态变化的情形，本实验采用其他学者常用 的处理方法[11-12, 17-18] ，即让数据集按照论域平均分 成多个对象集，然后通过将这些对象集逐渐进行 合并，达到了数据集论域动态增加的效果，将原 始论域逐渐对这些对象集进行移除，便达到了数 据集论域动态的减少。本实验将论域平均分成 9 个部分，这样可以构造出数据集的 8 次动态更 新。实验中将数据集的决策类作为邻域决策粗糙 集的近似对象集，即计算数据集每个决策类的上 下近似增量式更新。实验中每个数据集的属性值 第 4 期 孙海霞：基于对象变化的邻域决策粗糙集动态更新算法 ·751·