第16卷第4期 智能系统学报 Vol.16 No.4 2021年7月 CAAI Transactions on Intelligent Systems Jul.2021 D0:10.11992/tis.202010028 网络出版地址：https:/ns.cnki.net/kcms/detail/23.1538.TP.20210409.1403.008.html 基于对象变化的邻域决策粗糙集动态更新算法 孙海霞 (安徽三联学院计算机工程学院，安徽合肥230601) 摘要：针对现实环境下数据集不断动态变化的特性，提出一种邻域决策粗糙集模型的增量式更新算法。采用 由简单到复杂的研究思路，分析了邻域型信息系统论域增加和减少单个对象时，目标近似集与邻域类之间概率 的变化规律，进一步地利用这种规律来构造单个对象变化时邻域决策粗糙集模型上下近似集的增量式更新，在 单个对象变化的基础上，通过逐步迭代的方式设计了对象批量变化时的增量式更新算法。实验分析表明，所提 出的算法具有较高的增量式更新性能，适用于动态数据环境下邻域决策粗糙集模型的动态更新。 关键词：粗糙集：决策粗糙集：邻域：增量式学习：近似集：对象：迭代：动态 中图分类号：TP18 文献标志码：A 文章编号：1673-4785(2021)04-0746-11 中文引用格式：孙海霞.基于对象变化的邻域决策粗糙集动态更新算法J机.智能系统学报，2021,16(4)：746-756. 英文引用格式：SUN Haixia.Dynamic updating algorithm of neighborhood decision-theoretic rough set model based on object change[J].CAAI transactions on intelligent systems,2021,16(4):746-756. Dynamic updating algorithm of neighborhood decision-theoretic rough set model based on object change SUN Haixia (College of Computer Engineering,Anhui Sanlian University,Hefei 230601,China) Abstract:In accordance with the dynamic characteristics of a dataset in a real environment,an incremental updating al- gorithm of the neighborhood decision-theoretic rough set model is proposed after conducting simple to complex re- search.In this paper,the change law of the probability between the target approximation set and the neighborhood class is first analyzed in the context of the domain of the neighborhood information system increasing or decreasing individu- al objects,which is then adopted to construct the incremental updating of the upper and lower approximation sets of the neighborhood decision-theoretic rough set model.On the basis of the change of a single object and given the variety of multiple objects,an incremental updating algorithm is designed through step-by-step iteration.Experimental results show that the proposed algorithm has a high incremental updating performance,thereby making it suitable for the dy- namic updating of the neighborhood decision-theoretic rough set model in a dynamic data environment. Keywords:rough set;decision-theoretic rough set;neighborhood,incremental learning;approximation set,object;itera- tion:dynamic 粗糙集理论是当今知识发现领域的一个研究 早期的决策粗糙集建立在完备离散型的信 热点，决策粗糙集模型是粗糙集理论的重要研 息系统上，在其基础上，学者们进一步地提出了 究分支，由于决策粗糙集在处理噪声数据方面具有 多种扩展的粗糙集模型，例如Lu等m将决策粗 较好的泛化性能，因此目前已广泛应用于机器 糙集推广至不完备信息系统，提出一种改进的不 学习、图像处理和数据挖掘等诸多领域。 完备决策粗糙集模型；Sun等8)在粗糙模糊集下 收稿日期：2020-10-26.网络出版日期：2021-04-09. 提出了相应的决策粗糙集模型；Dou等)基于多 基金项目：安徽省质量工程项目(2020ZYRC063,2020XSKT151): 省教育厅高校自然科学重点项目(KJ2019A0891). 个代价的策略，提出了多代价的决策粗糙集模 通信作者：孙海霞.E-mail:wangbol9855@163.com. 型；在数值型的数据集方面，Li等0将邻域关系
DOI: 10.11992/tis.202010028 网络出版地址: https://kns.cnki.net/kcms/detail/23.1538.TP.20210409.1403.008.html 基于对象变化的邻域决策粗糙集动态更新算法 孙海霞 （安徽三联学院 计算机工程学院，安徽 合肥 230601） 摘 要：针对现实环境下数据集不断动态变化的特性，提出一种邻域决策粗糙集模型的增量式更新算法。采用 由简单到复杂的研究思路，分析了邻域型信息系统论域增加和减少单个对象时，目标近似集与邻域类之间概率 的变化规律，进一步地利用这种规律来构造单个对象变化时邻域决策粗糙集模型上下近似集的增量式更新，在 单个对象变化的基础上，通过逐步迭代的方式设计了对象批量变化时的增量式更新算法。实验分析表明，所提 出的算法具有较高的增量式更新性能，适用于动态数据环境下邻域决策粗糙集模型的动态更新。 关键词：粗糙集；决策粗糙集；邻域；增量式学习；近似集；对象；迭代；动态 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2021)04−0746−11 中文引用格式：孙海霞. 基于对象变化的邻域决策粗糙集动态更新算法 [J]. 智能系统学报, 2021, 16(4): 746–756. 英文引用格式：SUN Haixia. Dynamic updating algorithm of neighborhood decision-theoretic rough set model based on object change[J]. CAAI transactions on intelligent systems, 2021, 16(4): 746–756. Dynamic updating algorithm of neighborhood decision-theoretic rough set model based on object change SUN Haixia (College of Computer Engineering, Anhui Sanlian University, Hefei 230601, China) Abstract: In accordance with the dynamic characteristics of a dataset in a real environment, an incremental updating algorithm of the neighborhood decision-theoretic rough set model is proposed after conducting simple to complex research. In this paper, the change law of the probability between the target approximation set and the neighborhood class is first analyzed in the context of the domain of the neighborhood information system increasing or decreasing individual objects, which is then adopted to construct the incremental updating of the upper and lower approximation sets of the neighborhood decision-theoretic rough set model. On the basis of the change of a single object and given the variety of multiple objects, an incremental updating algorithm is designed through step-by-step iteration. Experimental results show that the proposed algorithm has a high incremental updating performance, thereby making it suitable for the dynamic updating of the neighborhood decision-theoretic rough set model in a dynamic data environment. Keywords: rough set; decision-theoretic rough set; neighborhood; incremental learning; approximation set; object; iteration; dynamic 粗糙集理论是当今知识发现领域的一个研究 热点，决策粗糙集模型[1-2] 是粗糙集理论的重要研 究分支，由于决策粗糙集在处理噪声数据方面具有 较好的泛化性能[2] ，因此目前已广泛应用于机器 学习[3-4] 、图像处理[5] 和数据挖掘[6] 等诸多领域。 早期的决策粗糙集建立在完备离散型的信 息系统上，在其基础上，学者们进一步地提出了 多种扩展的粗糙集模型，例如 Liu 等 [7] 将决策粗 糙集推广至不完备信息系统，提出一种改进的不 完备决策粗糙集模型；Sun 等 [8] 在粗糙模糊集下 提出了相应的决策粗糙集模型；Dou 等 [9] 基于多 个代价的策略，提出了多代价的决策粗糙集模 型；在数值型的数据集方面，Li 等 [10] 将邻域关系 收稿日期：2020−10−26. 网络出版日期：2021−04−09. 基金项目：安徽省质量工程项目 (2020ZYRC063，2020XSKT151)； 省教育厅高校自然科学重点项目 (KJ2019A0891). 通信作者：孙海霞. E-mail：wangbo19855@163.com. 第 16 卷第 4 期 智 能 系 统 学 报 Vol.16 No.4 2021 年 7 月 CAAI Transactions on Intelligent Systems Jul. 2021
第4期 孙海霞：基于对象变化的邻域决策粗糙集动态更新算法 ·747· 融入决策粗糙集模型中，提出了邻域决策粗糙 1邻域决策粗糙集模型 集模型，该模型进一步提升了决策粗糙集的适用 范围。 粗糙集理论中，数据集表示为信息系统 然而现实环境下的数据不总是静止不变的， IS=(U,AT)的形式，其中U为信息系统的对象集， 而是时刻处于动态更新之中，为了提高粗糙集模 称为论域。AT称为信息系统的属性集，若属性集 型在动态数据下的处理效率，学者们对其提出了 AT可分为条件属性集C和决策属性集D,即 多种增量式的模型和算法。在决策粗糙集等 AT=CUD,那么该信息系统又称为决策信息系 统。对于x∈U和Ya∈AT,a(x)表示对象x在属 模型中，学者们同样提出了多种增量式更新算 性a下的属性值。当条件属性集C中的每个属性 法。例如，Zhang等针对属性值动态变化情形 都为数值型属性时，此信息系统又称之为邻域型 提出了相应的增量式更新算法；针对流计算环 信息系统。 境，Xu等提出了对象在线增加和减少时的增 Yao等2】提出的决策粗糙集仅应用于离 量式更新算法；Chen等a利用集合更新的方法设 散型的信息系统，L等将邻域关系引人传统的决 计出了决策粗糙集的增量式更新算法；赵小龙 策粗糙集模型中，提出了邻域决策粗糙集。 等针对数值型信息系统，研究了邻域粒化条件 定义10设邻域型信息系统IS=(U,AT),对 嫡随对象增加和减少时的增量式更新，并进一步 于属性集A二AT确定的邻域关系定义为 地提出了对应的增量式属性约简算法：杨臻等⑧研 Ng={(x,y)∈U×Ul△a(x,y)≤6} 究了混合型信息系统下对象变化时概率的增量式 式中：6称为邻域半径，是一个非负常数；△(x,y) 更新，并进一步地提出了变精度粗糙集模型的增 表示对象x与对象y之间的闵可夫斯基距离，定 量式更新；Luo等9通过矩阵方法构造出了决策 义为 粗糙集的增量式更新算法。然而所提出的这些增 1/ 量式更新算法仅局限于离散数据环境下的决策粗 △A(,y a(x)-a(y) 糙集模型，针对邻域型的决策粗糙集还未有相关 给定邻域信息系统的邻域关系，可以进一步 研究。 得到每个对象在该邻域关系下的邻域类。 论域中对象的增加和减少是信息系统最为常 定义20设邻域型信息系统IS=(U,AT),属 见的一种变化形式，本文将针对这类问题进行邻 性集ACAT确定的邻域关系为N,邻域半径为 域决策粗糙集的增量式更新研究。邻域决策粗糙 6。那么对于x∈U在邻域关系W下的邻域类定 集通过邻域关系来对数值型数据进行信息粒化， 义为 而对其进行增量式计算时必然涉及邻域类的更新 6a(x)={y∈UI(x,y)∈N} 计算，邻域关系不同于传统的等价关系和容差关 可以看出，对象x的邻域类表示与x相近对 系，其增量式计算的复杂程度要更高。在文献[18] 象的集合，其中6体现了相近的程度。基于邻域 中，杨臻等通过单个对象逐步迭代的方式去处理 的思想，Li等0提出了邻域决策粗糙集。 混合型信息系统变精度粗糙集模型的增量式更 在邻域决策粗糙集中，给定状态集2={XX, 新，使得问题的处理方式简便高效。由于决策粗 其中X和X分别表示对象x隶属于X和X的两 糙集与变精度粗糙集有一定的相似性，因此本文 种情形，那么对象x隶属于X的程度可通过概率 将借鉴文献[18]中关于变精度粗糙集模型的增量 PX》=Kn6来表示，则对象x隶属于x的 式更新研究思路与方法，构造出邻域决策粗糙集 6(x)1 程度可表示为PX6(x)=1-PXI6(x)。给定对象 的增量式更新模型。文中首先分别研究论域中增 x划分入X和X时的3种动作T={ap,a,aw,其 加和减少一个对象时，近似集与邻域类之间概率 中ap、as和aw分别表示划分入类别的正区域、边 的变化规律，然后根据这种规律来构造单个对象 界域和负区域。这里令AP(∈{P,B,W)分别表示 变化时模型上下近似集的增量式更新，最后在单 对象x实际属于X时采取ap、as和aw动作时所 个对象变化的基础上，通过逐步迭代的方式设计 产生的决策代价，w(*∈(PB,W)分别表示对象x 了对象批量变化时的增量式更新算法。实验分析 实际属于X时采取ap、as和aw动作时所产生的 表明，所提出的算法具有较高的增量式更新性 决策代价。因此对于对象x进行不同决策动作时 能，适用于动态数据环境下邻域决策粗糙集模型 所产生的的代价为： 的动态更新。 1)Rp=R(apl6(x)=App·P(XI6x)+APw·PXox)
融入决策粗糙集模型中，提出了邻域决策粗糙 集模型，该模型进一步提升了决策粗糙集的适用 范围。 然而现实环境下的数据不总是静止不变的， 而是时刻处于动态更新之中，为了提高粗糙集模 型在动态数据下的处理效率，学者们对其提出了 多种增量式的模型和算法[11-13]。在决策粗糙集等 模型中，学者们同样提出了多种增量式更新算 法。例如，Zhang 等 [14] 针对属性值动态变化情形 提出了相应的增量式更新算法；针对流计算环 境，Xu 等 [15] 提出了对象在线增加和减少时的增 量式更新算法；Chen 等 [16] 利用集合更新的方法设 计出了决策粗糙集的增量式更新算法；赵小龙 等 [17] 针对数值型信息系统，研究了邻域粒化条件 熵随对象增加和减少时的增量式更新，并进一步 地提出了对应的增量式属性约简算法；杨臻等[18] 研 究了混合型信息系统下对象变化时概率的增量式 更新，并进一步地提出了变精度粗糙集模型的增 量式更新；Luo 等 [19] 通过矩阵方法构造出了决策 粗糙集的增量式更新算法。然而所提出的这些增 量式更新算法仅局限于离散数据环境下的决策粗 糙集模型，针对邻域型的决策粗糙集还未有相关 研究。 论域中对象的增加和减少是信息系统最为常 见的一种变化形式，本文将针对这类问题进行邻 域决策粗糙集的增量式更新研究。邻域决策粗糙 集通过邻域关系来对数值型数据进行信息粒化[10] ， 而对其进行增量式计算时必然涉及邻域类的更新 计算，邻域关系不同于传统的等价关系和容差关 系，其增量式计算的复杂程度要更高。在文献 [18] 中，杨臻等通过单个对象逐步迭代的方式去处理 混合型信息系统变精度粗糙集模型的增量式更 新，使得问题的处理方式简便高效。由于决策粗 糙集与变精度粗糙集有一定的相似性，因此本文 将借鉴文献 [18] 中关于变精度粗糙集模型的增量 式更新研究思路与方法，构造出邻域决策粗糙集 的增量式更新模型。文中首先分别研究论域中增 加和减少一个对象时，近似集与邻域类之间概率 的变化规律，然后根据这种规律来构造单个对象 变化时模型上下近似集的增量式更新，最后在单 个对象变化的基础上，通过逐步迭代的方式设计 了对象批量变化时的增量式更新算法。实验分析 表明，所提出的算法具有较高的增量式更新性 能，适用于动态数据环境下邻域决策粗糙集模型 的动态更新。 1 邻域决策粗糙集模型 IS = (U,AT) U AT AT C D AT = C ∪ D ∀x ∈ U ∀a ∈ AT a(x) x a C 粗糙集理论中，数据集表示为信息系统 的形式，其中 为信息系统的对象集， 称为论域。 称为信息系统的属性集，若属性集 可分为条件属性集 和决策属性集 ，即 ，那么该信息系统又称为决策信息系 统。对于 和 ， 表示对象 在属 性 下的属性值。当条件属性集 中的每个属性 都为数值型属性时，此信息系统又称之为邻域型 信息系统。 Yao 等 [ 1 - 2 ] 提出的决策粗糙集仅应用于离 散型的信息系统，Li 等将邻域关系引入传统的决 策粗糙集模型中，提出了邻域决策粗糙集[10]。 IS = (U,AT) A ⊆ AT N δ A 定义 1 [10] 设邻域型信息系统 ，对 于属性集 确定的邻域关系 定义为 N δ A = {(x, y) ∈ U ×U |∆A(x, y) ⩽ δ } δ ∆A(x, y) x y 式中： 称为邻域半径，是一个非负常数； 表示对象 与对象 之间的闵可夫斯基距离，定 义为 ∆A(x, y) = ∑ ∀a∈A |a(x)−a(y)| k 1/k 给定邻域信息系统的邻域关系，可以进一步 得到每个对象在该邻域关系下的邻域类。 IS = (U,AT) A ⊆ AT N δ A δ ∀x ∈ U N δ A 定义 2 [10] 设邻域型信息系统 ，属 性集 确定的邻域关系为 ，邻域半径为 。那么对于 在邻域关系 下的邻域类定 义为 δA(x) = {y ∈ U|(x, y) ∈ N δ A } x x δ 可以看出，对象 的邻域类表示与 相近对 象的集合，其中 体现了相近的程度。基于邻域 的思想，Li 等 [10] 提出了邻域决策粗糙集。 Ω = {X,X c } X X c x X X c x X P(X|δ(x)) = |X ∩δ(x)| |δ(x)| x X c P(X c |δ(x)) = 1− P(X|δ(x)) x X X c Γ = {aP,aB,aN} aP aB aN λ∗P(∗ ∈ {P,B,N}) x X aP aB aN λ∗N(∗ ∈ {P,B,N}) x X c aP aB aN x 在邻域决策粗糙集中，给定状态集 ， 其中 和 分别表示对象 隶属于 和 的两 种情形，那么对象 隶属于 的程度可通过概率 来表示，则对象 隶属于 的 程度可表示为 。给定对象 划分入 和 时的 3 种动作 ，其 中 、 和 分别表示划分入类别的正区域、边 界域和负区域。这里令 分别表示 对象 实际属于 时采取 、 和 动作时所 产生的决策代价， 分别表示对象 实际属于 时采取 、 和 动作时所产生的 决策代价。因此对于对象 进行不同决策动作时 所产生的的代价为： RP = R(aP|δ(x))= λPP · P(X|δ(x))+λPN · P(X c 1) |δ(x)) ; 第 4 期 孙海霞：基于对象变化的邻域决策粗糙集动态更新算法 ·747·
·748· 智能系统学报 第16卷 2)Rg=R(aBl6(x))=ABp-P(X16(x))+ABN-P(X16(x)); 量的，而这些批量的变化可以分解成对象的一个 3)Rw=R(awl6(x)=wP·PX6(x)+ww·P(Xl6(x) 一个依次变化，每次只考虑数据集中一个对象增 基于最小化决策代价的原则，那么有 加或减少时的增量式更新问题，然后逐步对多个 I)RP≤RB且RP≤Rw时，x∈POS(X 对象进行迭代，这样可以简化问题的处理21。 2)RB≤RP且RB≤Rw时，x∈BUNX): 根据这一思想，构造了本文模型的增量式更新 3)Rw≤RP且Rw≤Ra时，x∈NEG(X)o 方法。 通常决策代价满足关系pp≤dsPdar- 在论域U+下的邻域类。对于XYsU,若 ,则 ABN ANN APN-ABN X,Y*sU且X+=XU{x},Y=Y。那么满足： 1)当PX6(x)>a时，那么x∈POS(X): 1)x∈6g(x)-{xh,有 2)当B≤PX6x)≤a时，那么x∈BUN(X): PX*l6g(x)≥PX16(x): 3)当P(X6x)a) 定理2设邻域型信息系统IS=(U,AT),邻域 Na”(X={x∈UPX6Ax)≥B\ 半径为6。对于X,YsU关于属性集ASAT的邻 式中：0≤Ba) 型和算法不再有效，针对该问题，本节将提出一 2)N(Y)=(W(Y)- 种论域变化时邻域决策粗糙集模型的增量式更新 {x∈Na(Y)n6(x*)IP(Y*6g(x)≤aU 方法。 {x∈{x*IP(Y*16g(x)> 定义3已经表明，当信息系统的决策代价已 证明I)对于x∈N(X),要么x∈(x)- 经确定时，则邻域决策粗糙集中的阈值α和B也 {x,要么x∈U-g(x)。对于Yx∈Nam(X)且满 就确定，因此对于邻域决策粗糙集的研究只需考 足x∈g(x)-{x),那么由定理1可以得到 虑概率P(X6(x)与阈值a和B的关系即可。 PX16g(x)≥P(X6(x)>a,则有x∈m(X)。 数据集论域中对象的增加和减少往往都是批 对于x∈Na(X)且满足x∈U+-6g(x),那么
RB = R(aB|δ(x))= λBP · P(X|δ(x))+λBN · P(X c 2) |δ(x)) ; RN = R(aN|δ(x))= λNP · P(X|δ(x))+λNN · P(X c 3) |δ(x)) 基于最小化决策代价的原则，那么有 1) RP ⩽ RB 且 RP ⩽ RN 时，x ∈ POS(X) ; 2) RB ⩽ RP 且 RB ⩽ RN 时，x ∈ BUN(X) ; 3) RN ⩽ RP 且 RN ⩽ RB 时，x ∈ NEG(X)。 λPP ⩽ λBP λBP −λPP λPN −λBN 进一步地，若 ，则 1) 当 P(X|δ(x)) > α 时，那么 x ∈ POS(X) ； 2) 当 β ⩽ P(X|δ(x)) ⩽ α 时，那么 x ∈ BUN(X) ； 3) 当 P(X|δ(x)) α} N (α,β) A (X) = {x ∈ U|P(X|δA(x)) ⩾ β} 0 ⩽ β α} 2)N (α,β) A (Y + ) = (N (α,β) A (Y)− {x ∈ N (α,β) A (Y)∩δ U + A (x + )|P(Y + |δ U + A (x)) ⩽ α})∪ {x ∈ {x + }|P(Y + |δ U + A (x)) > α} ∀x ∈ N (α,β) A (X) x ∈ δ U + A (x + )− {x + } x ∈ U + −δ U + A (x + ) ∀x ∈ N (α,β) A (X) x ∈ δ U + A (x + )− {x + } P(X + |δ U + A (x)) ⩾ P(X|δ U A (x)) > α x ∈ N (α,β) A (X + ) 证明 1) 对于 ，要么 ，要么 。对于 且满 足 ，那么由定 理 1 可以得到 ，则有 。 ∀x ∈ N (α,β) A (X) x ∈ U + −δ U + A (x + 对于 且满足 ) ，那么 ·748· 智 能 系 统 学 报 第 16 卷
第4期 孙海霞：基于对象变化的邻域决策粗糙集动态更新算法 ·749· 由定理1可以得到 示的下近似集增量式更新具有较高的计算效率。 P(X*1 (x))=P(X16(x))>a 类似于定理2的研究方法，接下来可以进一 同样有x∈Nm(X)。所以对于Yx∈N(X) 步得到上近似集的增量式更新。 都有x∈V(X),即Va(X)SN(X)。 定理3设邻域型信息系统IS=(U,AT),邻域 对于Hx∈U-Na(),若x∈U-6(x),由定 半径为6。对于XYSU关于属性集ASAT的邻 理1可得PX6(x)=P(X6(x)≤a。那么此时 域决策粗糙上近似分别为N(X)和N(Y。当 xEN(X+)。 信息系统论域U增加对象x*,新的邻域型信息系 若x∈6(x)-{x,根据定理1可得 统表示为IS*=(U=UU{x*h,AT)。若X,YSU P(X6W(x)≥P(X6(x) 且X=XU},Y=Y,那么X,Y+关于属性集 而P(X6以(x)≤a,因此P(X69(x)与a的大 A二AT的邻域决策粗糙上近似增量式更新为 小无法确定，只有当P(X6(x》>a时 1)N”(X)=N(XU x∈N(X+)。也就是说，只需对x∈(x)-Wa(X) 中的对象进行具体的计算便可以完成最终的下近 {xe6)-N(XPX*6》≥B卧 似更新，因此 2N”(Y=(N(Y- N(X)=N(X)U xEN()o(P(Y()a] {x∈{x*HPY6g(x)≥B\ 即1)成立。 证明证明过程同定理2。 2)对于Yx∈U-N(),都有P(YI6(x》≤ 定理3类似于定理2，更新上近似集时也只需 a。那么根据定理1，当x∈(x)-{x}时，有 要针对部分对象集进行计算便可完成，例如从 P(Y6g(x)a。根据 加一个对象时，邻域决策粗糙上下近似的增量式 定理1，当xe(x)-{x时，有 更新问题，当信息系统通过增加多个对象，可以 P(Y+l6g(x)a。 根据定理2和定理3逐步进行迭代，直至完成最 因此PY6(x)与α的大小无法确定。 终的更新。 当x∈U-g(x)时，有 2.2论域中对象减少时模型的增量式更新 P(Y(x))=P(Y164(x))>a 类似于第2.1节中研究方法，本节将进一步 即x∈Nm(Y),则需要对x∈(x)-{x*}中 提出论域中对象减少时模型的增量式更新，首先 的对象计算P(Yg(x)可得到新的下近似结 分析对象减少时概率的变化关系。 果，即 定理48I设邻域型信息系统IS=(U,AT),邻 N(Y+)=(W(Y)- 域半径为6且属性集ASAT。当信息系统论域U {x∈Na(Y)ng(x*)P(Y*l6g(x)≤aU 移除对象x,x∈U,新的邻域型信息系统表示为 {x∈{x*IP(Y*16g(x》>a IS=(U=U-{xh,AT)。令以(x)表示对象Yx∈U 定理2证明完毕。 在论域U下的邻域类，令(x)表示对象Hx∈U 定理2表明，当信息系统增加一个对象后，新 在论域U下的邻域类。对于XYsU,若 的邻域决策粗糙下近似集变化呈现一定的规律， X,Y-≤U-且X=X-{x},Y-=Y。那么满足 例如从N(X)更新至N(X),其近似集是增大 1)Yx∈6(x)-{x1,有 的，并且增加的对象集只来源于对象集(x)- P(X16g(x)≤PX(x) (X),因此只需对这里面的对象进行概率 P(Y16(x)>P(Y16(x) P(Xl6(x)计算，便可得到最终的更新结果，这样 2)x∈U-6(x),有 大幅度减小了计算量。同样地对于()更新 P(X-1 (x))=P(X18(x)) 至Y(Y),只需对Yam(Y)ng(r)中的对象进 P(Y-1(x))=P(Y14(x)) 行相关计算便可以完成最终更新，所以定理2所 定理4给出信息系统论域U移除一个对象
由定理 1 可以得到 P(X + |δ U + A (x)) = P(X|δ U A (x)) > α x ∈ N (α,β) A (X + ) ∀x ∈ N (α,β) A (X) x ∈ N (α,β) A (X + ) N (α,β) A (X) ⊆ N (α,β) A (X + ) 同样有 。所以对于 都有 ，即 。 ∀x ∈ U −N (α,β) A (X) x ∈ U + −δ U + A (x + ) P(X + |δ U + A (x)) = P(X|δ U A (x)) ⩽ α x α x ∈ N (α,β) A (X + ) x ∈ δ U + A (x + )−N (α,β) A (X) 而 ，因此 与 的大 小无法确定，只有当 时 。也就是说，只需对 中的对象进行具体的计算便可以完成最终的下近 似更新，因此 N (α,β) A (X + ) = N (α,β) A (X)∪ {x ∈ δ U + A (x + )−N (α,β) A (X)|P(X + |δ U + A (x)) > α} 即 1) 成立。 ∀x ∈ U −N (α,β) A (Y) P(Y|δ U A (x)) ⩽ α x ∈ δ U + A (x + )− {x + } 2 ) 对 于 ，都有 。那么根据定理 1，当 时，有 P(Y + |δ U + A (x)) α x ∈ δ U + A (x + )− {x + } 对于 ，都有 。根据 定理 1，当 时，有 P(Y + |δ U + A (x)) α。 P(Y + |δ U + A 因此 (x)) 与 α 的大小无法确定。 x ∈ U + −δ U + A (x + 当 ) 时，有 P(Y + |δ U + A (x)) = P(Y|δ U A (x)) > α x ∈ N (α,β) A (Y + ) x ∈ δ U + A (x + )− {x + } P(Y + |δ U + A (x)) 即 ，则需要对 中 的对象计算 可得到新的下近似结 果，即 N (α,β) A (Y + ) = (N (α,β) A (Y)− {x ∈ N (α,β) A (Y)∩δ U + A (x + )|P(Y + |δ U + A (x)) ⩽ α})∪ {x ∈ {x + }|P(Y + |δ U + A (x)) > α} 定理 2 证明完毕。 N (α,β) A (X) N (α,β) A (X + ) δ U + A (x + )− N (α,β) A (X) P(X + |δ U + A (x)) N (α,β) A (Y) N (α,β) A (Y + ) N (α,β) A (Y)∩δ U + A (x + ) 定理 2 表明，当信息系统增加一个对象后，新 的邻域决策粗糙下近似集变化呈现一定的规律， 例如从 更新至 ，其近似集是增大 的，并且增加的对象集只来源于对象集 ，因此只需对这里面的对象进行概率 计算，便可得到最终的更新结果，这样 大幅度减小了计算量。同样地对于 更新 至 ，只需对 中的对象进 行相关计算便可以完成最终更新，所以定理 2 所 示的下近似集增量式更新具有较高的计算效率。 类似于定理 2 的研究方法，接下来可以进一 步得到上近似集的增量式更新。 IS = (U,AT) δ X,Y ⊆ U A ⊆ AT N (α,β) A (X) N (α,β) A (Y) U x + IS+ = (U + = U ∪ {x + },AT) X + ,Y + ⊆ U + X + = X ∪ {x + } Y + = Y X + ,Y + A ⊆ AT 定理 3 设邻域型信息系统 ，邻域 半径为 。对于 关于属性集 的邻 域决策粗糙上近似分别为 和 。当 信息系统论域 增加对象 ，新的邻域型信息系 统表示为 。 若 且 ， ，那么 关于属性集 的邻域决策粗糙上近似增量式更新为 1)N (α,β) A (X + ) = N (α,β) A (X)∪ {x ∈ δ U + A (x + )−N (α,β) A (X)|P(X + |δ U + A (x)) ⩾ β} 2)N (α,β) A (Y + ) = (N (α,β) A (Y)− {x ∈ N (α,β) A (Y)∩δ U + A (x + )|P(Y + |δ U + A (x)) P(Y|δ U A (x)) ∀x ∈ U −δ U A (x − 2) ),有 P(X − |δ U − A (x)) = P(X|δ U A (x)) P(Y − |δ U − A (x)) = P(Y|δ U A (x)) 定理 4 给出信息系统论域 U 移除一个对象 第 4 期 孙海霞：基于对象变化的邻域决策粗糙集动态更新算法 ·749·
·750· 智能系统学报 第16卷 后，近似集在不同对象下的概率变化关系，有了 若对象x∈U-(x),那么由定理4可得到 这种变化作为基础，接下来可以很容易得到邻域 P(Y-16 (x))=P(Yl64(x))a) 同样地对于Y(Y)更新至N(Y),也只需对一 证明1)对于Yx∈N(X),要么x∈(x), 小部分对象进行相关计算便可以完成最终更新。 要么xeU-(xr)。若对象满足x∈以(xr)-{x, 所以定理5所示的下近似集增量式更新方法具有 那么由定理4可以得到 较高的计算效率。类似于定理5的研究方法，接 P(X16(x)≤PX6(x) 下来可以进一步得到上近似集的增量式更新。 由于P(X6(x)>a,则无法直接确定PX-6(x) 定理6设邻域型信息系统IS=(U,AT),邻域 与a的关系。即x∈a(X)且x∈6(x)-{x, 半径为6。对于XYSU关于属性集ASAT的邻 需要计算PX6g(x)的值。 域决策粗糙上近似分别为N(X和N”(Y).当 若对象满足x∈U-(x),那么由定理4可以 信息系统论域U移除一个对象x,x∈U,新的邻 得到P(X6g(x)=PX6(x)>a,因此x∈Na() 域型信息系统表示为S=(U=U-{x,AT)。若 且x∈U-(x)都有x∈(X) X,Y∈U且X=X-{x1,Y=Y,那么X、Y关于 对于Yx∈U-N(X),若对象满足x∈6(x)- 属性集A二AT的邻域决策粗糙上近似增量式更 {x1,那么由定理4可以得到 新为 P(X16(x)≤P(X6(x)≤a. 1N)=NX)-xEN 因此Yx∈U-Na(X)且x∈(x)-x}都有 (6(x)-x川P(X-6(x)P(Y164(x))>a 与之间的大小关系不能直接确定，因此定理 若对象满足x∈U-(x),那么由定理4可以 6中的1)得到证明。 得到 2)根据定理5的证明结果，对于VxeN(Y) P(Y-1(x))=P(Y1(x))>a 都有xeN(Y)。对于xEU-N(Y)且 因此x∈(Y)都有x∈N(Y-)。 xEU-以)时，都有xEN(Y),只有当 对于Yx∈U-(Y),若对象满足x∈(x)- rxeU-N()且xe6x)-{1时，不能直接确 {x},那么由定理4可以得到 定P(Y(x)与a之间的大小关系，因此定理 P(Y16g(x)>P(Y16(x),P(Y16以(x)≤a 6中的2)得到证明。 此时不能直接确定P(Yg(x)与α之间的 定理6与定理5类似，只需要在原先上近似 关系。 集NX)和N(的结果上，进一步对)
后，近似集在不同对象下的概率变化关系，有了 这种变化作为基础，接下来可以很容易得到邻域 决策粗糙集上下近似的增量式更新。 IS = (U,AT) δ X,Y ⊆ U A ⊆ AT N (α,β) A (X) N (α,β) A (Y) U x − x − ∈ U IS− = (U − = U − {x − },AT) X − ,Y − ⊆ U − X − = X − {x − } Y − = Y X − ,Y − A ⊆ AT 定理 5 设邻域型信息系统 ，邻域 半径为 。对于 关于属性集 的邻 域决策粗糙下近似分别为 和 。当 信息系统论域 移除对象 且 ，新的邻域 型信息系统表示为 。 若 且 , ，那么 关于 属性集 的邻域决策粗糙下近似增量式更 新为 1)N (α,β) A (X − ) = N (α,β) A (X)− {x ∈ N (α,β) A (X)∩ (δ U A (x − )− {x − })|P(X − |δ U − A (x)) ⩽ α} 2)N (α,β) A (Y − ) = N (α,β) A (Y)∪ {x ∈ δ U A (x − )− {x − } −N (α,β) A (Y)|P(Y − |δ U − A (x) > α} ∀x ∈ N (α,β) A (X) x ∈ δ U A (x − ) x ∈ U −δ U A (x − ) x ∈ δ U A (x − )− {x − } 证明 1) 对于 ，要么 ， 要么 。若对象满足 ， 那么由定理 4 可以得到 P(X − |δ U − A (x)) ⩽ P(X|δ U A (x)) P(X|δ U A (x)) > α P(X − |δ U − A (x)) α ∀x ∈ N (α,β) A (X) x ∈ δ U A (x − )− {x − } P(X − |δ U − A (x)) 由于 ，则无法直接确定 与 的关系。即 且 ， 需要计算 的值。 x ∈ U −δ U A (x − ) P(X − |δ U − A (x)) = P(X|δ U A (x)) > α ∀x ∈ N (α,β) A (X) x ∈ U −δ U A (x − ) x ∈ N (α,β) A (X − ) 若对象满足 ，那么由定理 4 可以 得到 ，因此 且 都有 。 ∀x ∈ U −N (α,β) A (X) x ∈ δ U A (x − )− {x − } 对于 ，若对象满足 ，那么由定理 4 可以得到 P(X − |δ U − A (x)) ⩽ P(X|δ U A (x)) ⩽ α. ∀x ∈ U −N (α,β) A (X) x ∈ δ U A (x − )− {x − } x P(Y|δ U A (x)) > α x ∈ U −δ U A (x − 若对象满足 ) ，那么由定理 4 可以 得到 P(Y − |δ U − A (x)) = P(Y|δ U A (x)) > α ∀x ∈ N (α,β) A (Y) x ∈ N (α,β) A (Y − 因此 都有 )。 ∀x ∈ U −N (α,β) A (Y) x ∈ δ U A (x − )− {x − } 对于 ，若对象满足 ，那么由定理 4 可以得到 P(Y − |δ U − A (x)) > P(Y|δ U A (x)),P(Y|δ U A (x)) ⩽ α P(Y − |δ U − A 此时不能直接确定 (x)) 与 α 之间的 关系。 x ∈ U −δ U A (x − 若对象 ) ，那么由定理 4 可得到 P(Y − |δ U − A (x)) = P(Y|δ U A (x)) ⩽ α x < N (α,β) A (Y − 即 )。 (U −N (α,β) A (Y))∩ (δ U A (x − )− {x − }) x ∈ δ U A (x − )− {x − } −N (α,β) A (Y) 因此只需要计算对象集 中的对象便可以完成近似集的增量 式更新，即计算 ， 因 此 2) 成立。 定理 5 证明完毕。 x − N (α,β) A (X) N (α,β) A (X − ) P(X − |δ U − A (x)) N (α,β) A (Y) N (α,β) A (Y − ) 定理 5 表明，当邻域型信息系统移除一个对 象 后，新的邻域决策粗糙下近似集变化也呈现 一定的规律，例如从 更新至 ，其 近似集是减小的，并且减少的对象只来源于一小 部分对象集，因此只需对这里面的对象进行概率 的计算，便可得到最终的更新结果。 同样地对于 更新至 ，也只需对一 小部分对象进行相关计算便可以完成最终更新。 所以定理 5 所示的下近似集增量式更新方法具有 较高的计算效率。类似于定理 5 的研究方法，接 下来可以进一步得到上近似集的增量式更新。 IS = (U,AT) δ X,Y ⊆ U A ⊆ AT N (α,β) A (X) N (α,β) A (Y) U x − x − ∈ U IS− = (U − = U − {x − },AT) X − ,Y − ⊆ U − X − = X − {x − } Y − = Y X − Y − A ⊆ AT 定理 6 设邻域型信息系统 ，邻域 半径为 。对于 关于属性集 的邻 域决策粗糙上近似分别为 和 .当 信息系统论域 移除一个对象 ， ，新的邻 域型信息系统表示为 。若 且 , ，那么 、 关于 属性集 的邻域决策粗糙上近似增量式更 新为 1)N (α,β) A (X − ) =N (α,β) A (X)− {x ∈ N (α,β) A (X)∩ (δ U A (x − )− {x − })|P(X − |δ U − A (x)) < β} 2)N (α,β) A (Y − ) = N (α,β) A (Y)∪ {x ∈ δ U A (x − )− {x − } −N (α,β) A (Y)|P(Y − |δ U − A (x) ⩾ β} ∀x ∈ U −N (α,β) A (X) x < N (α,β) A (X − ) ∀x ∈ N (α,β) A (X) x ∈ U −δ U A (x − ) x ∈ N (α,β) A (X − ) ∀x ∈ N (α,β) A (X) x ∈ δ U A (x − )− {x − } P(X − |δ U − A (x)) α 证 明 1 ) 根据定 理 5 的证明结果，对于 都满足 。而对于 且 都有 ，只 有当 且 时， 与 之间的大小关系不能直接确定，因此定理 6 中的 1) 得到证明。 ∀x ∈ N (α,β) A (Y) x ∈ N (α,β) A (Y − ) ∀x ∈ U −N (α,β) A (Y) x ∈ U −δ U A (x − ) x < N (α,β) A (Y − ) ∀x ∈ U −N (α,β) A (Y) x ∈ δ U A (x − )− {x − } P(Y − |δ U − A (x)) α 2) 根据定理 5 的证明结果，对于 都 有 。对于 且 时，都有 ，只有当 且 时，不能直接确 定 与 之间的大小关系，因此定理 6 中的 2) 得到证明。 N (α,β) A (X) N (α,β) A (Y) δ U A (x − ) 定理 6 与定理 5 类似，只需要在原先上近似 集 和 的结果上，进一步对 ·750· 智 能 系 统 学 报 第 16 卷
第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·
·752· 智能系统学报 第16卷 均进行归一化处理，并且统一设定邻域半径 献[10]提出的算法。 6=0.15,阈值=0.75，B=0.55。 在图1所示的实验结果中，增量式算法的更 表1实验数据集 新用时大幅度低于非增量式算法，并且随着数据 Table 1 Experimental data set 集更新次数的增多，两类算法的差距不断增大。 序号 数据集 对象 属性 类别 这主要是由于非增量式更新算法在进行模型的更 iono 351 34 新时，每次均基于完整的论域进行计算，产生的 2 pima 768 6 3 时间会越来越多。对于增量式更新算法，随着数 wdbc 569 以 2 据集论域的增大，更新所需的时间较少且增长的 biodeg 1055 4t 2 速率较为缓慢，这主要是由于增量式更新算法采 5 segment 2310 19 7 用增量式的方法进行更新计算，每次均在前一次 6 musk 6598 166 2 更新的结果上进行进一步更新，这样避免了原有 7 census income 48842 14 3 对象的重复计算，大幅度提高更新效率，因此增 量式算法更加高效。 music 106574 518 图2展示的是各个数据集论域减少时，增量 图1为各个数据集论域增加时增量式更新算 式更新算法（算法2）与非增量式更新算法计算 法（算法1）与非增量式更新算法计算邻域决策粗 邻域决策粗糙集的时间比较结果，非增量式更新 糙集的时间比较结果，非增量式更新算法采用文 算法同样采用文献[I0]提出的算法。 0.06 0.14 ©非增量式算法 ◆非增量式算法 0.05 。增量式算法 0.12 。增量式算法 0.10 0.03 0.08 0.06 0.02 0.04 0.01 0.02 3 5 6 3 6 增量更新次数 增量更新次数 (a)iono (b)pima 0.10 。非增量式算法 0.30 非增量式算法 0.08 。增量式算法 0.25 。增量式算法 0.06 0.15 0.04 0.10 0.02 0.05 45 6 7 3 d 78 增量更新次数 增量更新次数 (c)wdbc (d)biodeg 0.6 2.0 。非增量式算法 。非增量式算法 0.5 。增量式算法 日增量式算法 1.5 0.4 0.3 1.0 0.2 0.5 3 6 78 3 6 增量更新次数 增量更新次数 (e)segment (f)musk
δ = 0.15 α = 0.75 β = 0.55 均进行归一化处理，并且统一设定邻域半径 ，阈值 ， 。 表 1 实验数据集 Table 1 Experimental data set 序号 数据集 对象 属性 类别 1 iono 351 34 2 2 pima 768 8 3 3 wdbc 569 31 2 4 biodeg 1055 41 2 5 segment 2310 19 7 6 musk 6598 166 2 7 census income 48842 14 3 8 music 106574 518 4 图 1 为各个数据集论域增加时增量式更新算 法 (算法 1) 与非增量式更新算法计算邻域决策粗 糙集的时间比较结果，非增量式更新算法采用文 献 [10] 提出的算法。 在图 1 所示的实验结果中，增量式算法的更 新用时大幅度低于非增量式算法，并且随着数据 集更新次数的增多，两类算法的差距不断增大。 这主要是由于非增量式更新算法在进行模型的更 新时，每次均基于完整的论域进行计算，产生的 时间会越来越多。对于增量式更新算法，随着数 据集论域的增大，更新所需的时间较少且增长的 速率较为缓慢，这主要是由于增量式更新算法采 用增量式的方法进行更新计算，每次均在前一次 更新的结果上进行进一步更新，这样避免了原有 对象的重复计算，大幅度提高更新效率，因此增 量式算法更加高效。 图 2 展示的是各个数据集论域减少时，增量 式更新算法 (算法 2) 与非增量式更新算法计算 邻域决策粗糙集的时间比较结果，非增量式更新 算法同样采用文献 [10] 提出的算法。 非增量式算法 增量式算法 0.06 0.05 0.04 0.03 0.02 0.01 0 更新用时/s 1 2 3 4 5 6 7 8 增量更新次数 (a) iono 非增量式算法 增量式算法 更新用时/s 1 2 3 4 5 6 7 8 增量更新次数 0.14 0.12 0.10 0.08 0.06 0.04 0.02 0 (b) pima 非增量式算法 增量式算法 更新用时/s 1 2 3 4 5 6 7 8 增量更新次数 0.10 0.08 0.06 0.04 0.02 0 (c) wdbc 非增量式算法 增量式算法 1 2 3 4 5 6 7 8 增量更新次数 更新用时/s 0.30 0.25 0.20 0.15 0.10 0.05 0 (d) biodeg 非增量式算法 增量式算法 0.6 0.5 0.4 0.3 0.2 0.1 0 更新用时/s 1 2 3 4 5 6 7 8 增量更新次数 (e) segment 非增量式算法 增量式算法 2.0 1.5 1.0 0.5 0 更新用时/s 1 2 3 4 5 6 7 8 增量更新次数 (f) musk ·752· 智 能 系 统 学 报 第 16 卷
第4期 孙海霞：基于对象变化的邻域决策粗糙集动态更新算法 ·753· 120 。-非增量式算法 g非增量式算法 20 ·增量式算法 100 :增量式算法 80 60 0 20 0 3 456 3 45678 增量更新次数 增量更新次数 (g)census income (h)music 图1论域增加时两类算法的更新用时比较 Fig.1 Comparison of update time of two algorithms when universe is added 在图2所示的实验结果中，可以发现增量 量式算法。对于增量式更新算法，随着数据集论 式更新算法的更新用时同样大幅度低于非增量 域的减小，其整体更新用时始终处于一个较低的 式更新算法，对于非增量式更新算法，随着数据 水平，并且随着更新次数增加，更新用时也是逐 集论域的逐渐减少，其更新模型的用时也是逐 渐减小的。这主要是由于增量式更新算法采用增 渐减小，这主要是由于非增量式更新算法在进 量式的方法进行更新计算，在前一次更新结果的 行更新时，对完整论域进行计算，因此随着论域 基础上计算后一次结果，由于论域逐渐减少，则 的减少，非增量式算法的计算量也大幅度减小， 更新时间会更加的少，从而效率远高于非增量式 产生的时间会越来越少，但是整体还是高于增 算法。 0.07 。非增量式算法 0.14 。非增量式算法 0.06 母增量式算法 0.12 。增量式算法 0.05 0.10 0.04 0.08 0.03 0.06 0.02 0.04 0.01 0.02 0 0 2 6 3 4 56 78 增量更新次数 增量更新次数 (a)iono (b)pima 0.12 。非增量式算法 0.30 e非增量式算法 0.10 ·增量式算法 0.25 ·增量式算法 0.20 0.06 0.15 0.04 0.02 0.05 0 2 3 4 5 6 3 4 567 增量更新次数 增量更新次数 (c)wdbc (d)biodeg 1.04 4.0 。非增量式算法 3.51 。非增量式算法 0.8 母增量式算法 3.0 增量式算法 0.6 2.5 20 0.4 1.5 0.2 1.0 0.5 0 456 3 4 56 增量更新次数 增量更新次数 (e)segment (f)musk
在图 2 所示的实验结果中，可以发现增量 式更新算法的更新用时同样大幅度低于非增量 式更新算法，对于非增量式更新算法，随着数据 集论域的逐渐减少，其更新模型的用时也是逐 渐减小，这主要是由于非增量式更新算法在进 行更新时，对完整论域进行计算，因此随着论域 的减少，非增量式算法的计算量也大幅度减小， 产生的时间会越来越少，但是整体还是高于增 量式算法。对于增量式更新算法，随着数据集论 域的减小，其整体更新用时始终处于一个较低的 水平，并且随着更新次数增加，更新用时也是逐 渐减小的。这主要是由于增量式更新算法采用增 量式的方法进行更新计算，在前一次更新结果的 基础上计算后一次结果，由于论域逐渐减少，则 更新时间会更加的少，从而效率远高于非增量式 算法。 非增量式算法 增量式算法 25 20 15 10 5 0 更新用时/s 1 2 3 4 5 6 7 8 增量更新次数 (g) census income 非增量式算法 增量式算法 120 100 80 60 40 20 0 更新用时/s 1 2 3 4 5 6 7 8 增量更新次数 (h) music 图 1 论域增加时两类算法的更新用时比较 Fig. 1 Comparison of update time of two algorithms when universe is added 非增量式算法 0.06 增量式算法 0.07 0.05 0.04 0.03 0.02 0.01 0 更新用时/s 1 2 3 4 5 6 7 8 增量更新次数 (a) iono 非增量式算法 0.12 增量式算法 0.14 0.10 0.08 0.06 0.04 0.02 0 更新用时/s 1 2 3 4 5 6 7 8 增量更新次数 (b) pima 非增量式算法 0.10 增量式算法 0.12 0.08 0.06 0.04 0.02 0 更新用时/s 1 2 3 4 5 6 7 8 增量更新次数 (c) wdbc 非增量式算法 0.25 增量式算法 0.30 0.20 0.15 0.10 0.05 0 更新用时/s 1 2 3 4 5 6 7 8 增量更新次数 (d) biodeg 非增量式算法 增量式算法 1.0 0.8 0.6 0.4 0.2 0 更新用时/s 1 2 3 4 5 6 7 8 增量更新次数 (e) segment 非增量式算法 增量式算法 4.0 3.5 3.0 2.5 2.0 1.5 1.0 0.5 0 更新用时/s 1 2 3 4 5 6 7 8 增量更新次数 (f) musk 第 4 期 孙海霞：基于对象变化的邻域决策粗糙集动态更新算法 ·753·
·754· 智能系统学报 第16卷 120 。非增量式算法 。非增量式算法 20 。增量式算法 100 。增量式算法 80 % 20 0 456 3 4 56 增量更新次数 增量更新次数 (g)census income (h)music 图2论域减少时两类算法的更新用时比较 Fig.2 Comparison of update time of two algorithms when universe is reduced 综合图1和图2的实验结果，可以看出本文 径6下增量式更新用时比较结果，其中包含了论 所提出的增量式更新算法的更新效率均大幅度高 域增加和论域减少的两种情形，这里设定邻域半 于传统的非增量式算法，并且所提出的算法随数 径6在0.1,0.28]内以0.02为间隔分别进行取值。 据集论域变化的影响较小，这说明了本文所提出 通过图3~6的结果可以看出，随着邻域半径 的增量式更新算法具有很高的优越性。 的逐渐增大，增量式更新算法的更新用时是逐渐 另一方面，在本文所提出的邻域决策粗糙集 增大的，这主要是由于本文所提出的增量更新算 增量式更新算法中，有3个重要的参数，分别为邻 法，计算新论域下的模型时，需要计算变化对象 域半径6，和一对阈值(a,B)。由于阈值(@，)可以 的邻域类，并基于这些邻域类进行更新计算，而 通过不同的评价方式进行确定，因此阈值（α，）可 邻域半径的增大无疑会增加邻域类中对象的数 认定为是固定的值，那么接下来将直接探究邻域 量，因此计算量会增加，从而展现出了图3~6 半径6对所提算法更新效率的影响。 的结果，但是对比图1和图2，这种增量式算法的 图3~6所示的是部分数据集在不用邻域半 用时仍然大幅度小于非增量式算法。 0.018 0.020 0.016 0.03 0.025 0.014 0.012 0.02 0.020 0.010 0.010 0.005 0.008 0.01 0.015 0302 0.006 0.010 10 0.004 0.18 邻域半径 002￥68 0.30 0.002 0.26 2 1 10 .1 增量更新次数 00之46 0.005 邻域半径 .14 增量更新次数 (a)论域增加 (b)论域减少 图3数据集pima在不同邻域半径下算法更新用时比较 Fig.3 Comparison of algorithm updating time of pima data set under different neighborhood radius 10.024 0.014 0.025 0.020 0.03 0.012 0.020 0.018 0.010 0.02 0.016 0.010 0.008 0.014 0.01 0.006 0.012 0.010 0.004 0.008 10 0.18 0.14 6 8 0.002 0.006 邻域半 00 增量更新次数 4 0.18 0.14 邻域半 002 468 增量更新次数 (a)论域增加 ()论域减少 图4数据集wdbc在不同邻域半径下算法更新用时比较 Fig.4 Comparison of algorithm updating time of wdbe data set under different neighborhood radius
综合图 1 和图 2 的实验结果，可以看出本文 所提出的增量式更新算法的更新效率均大幅度高 于传统的非增量式算法，并且所提出的算法随数 据集论域变化的影响较小，这说明了本文所提出 的增量式更新算法具有很高的优越性。 δ (α, β) (α, β) (α, β) δ 另一方面，在本文所提出的邻域决策粗糙集 增量式更新算法中，有 3 个重要的参数，分别为邻 域半径 ，和一对阈值 。由于阈值 可以 通过不同的评价方式进行确定，因此阈值 可 认定为是固定的值，那么接下来将直接探究邻域 半径 对所提算法更新效率的影响。 图 3～6 所示的是部分数据集在不用邻域半 δ δ 径 下增量式更新用时比较结果，其中包含了论 域增加和论域减少的两种情形，这里设定邻域半 径 在 [0.1,0.28] 内以 0.02 为间隔分别进行取值。 通过图 3~6 的结果可以看出，随着邻域半径 的逐渐增大，增量式更新算法的更新用时是逐渐 增大的，这主要是由于本文所提出的增量更新算 法，计算新论域下的模型时，需要计算变化对象 的邻域类，并基于这些邻域类进行更新计算，而 邻域半径的增大无疑会增加邻域类中对象的数 量，因此计算量会增加，从而展现出了图 3~6 的结果，但是对比图 1 和图 2，这种增量式算法的 用时仍然大幅度小于非增量式算法。 (a) 论域增加 0.020 0.015 0.010 0.005 0 0 2 4 6 8 0.30 10 0.26 0.22 0.18 0.14 0.10 更新用时/s 更新用时/s 邻域半径 δ 增量更新次数 0 0 2 4 6 8 0.30 10 0.26 0.22 0.18 0.14 0.10 邻域半径 δ 增量更新次数 0.018 0.016 0.014 0.012 0.010 0.008 0.006 0.004 0.002 0.03 0.02 0.01 (b) 论域减少 0.025 0.020 0.015 0.010 0.005 图 3 数据集 pima 在不同邻域半径下算法更新用时比较 Fig. 3 Comparison of algorithm updating time of pima data set under different neighborhood radius (a) 论域增加 0.020 0.015 0.010 0.005 0 0 2 4 6 8 0.30 10 0.26 0.22 0.18 0.14 0.10 更新用时/s 更新用时/s 邻域半径 δ 增量更新次数 0 0 2 4 6 8 0.30 10 0.26 0.22 0.18 0.14 0.10 邻域半径 δ 增量更新次数 0.014 0.012 0.010 0.008 0.006 0.004 0.002 0.03 0.02 0.01 (b) 论域减少 0.024 0.025 0.020 0.018 0.016 0.014 0.012 0.010 0.008 0.006 图 4 数据集 wdbc 在不同邻域半径下算法更新用时比较 Fig. 4 Comparison of algorithm updating time of wdbc data set under different neighborhood radius 非增量式算法 增量式算法 25 20 15 10 5 0 更新用时/s 1 2 3 4 5 6 7 8 增量更新次数 (g) census income 非增量式算法 增量式算法 120 100 80 60 40 20 0 更新用时/s 1 2 3 4 5 6 7 8 增量更新次数 (h) music 图 2 论域减少时两类算法的更新用时比较 Fig. 2 Comparison of update time of two algorithms when universe is reduced ·754· 智 能 系 统 学 报 第 16 卷
第4期 孙海霞：基于对象变化的邻域决策粗糙集动态更新算法 ·755· 0.06 0.09 0.08 0.10 0.08 0.06 0.05 0.07 0.04 0.04 0.06 0.06 0.02 0.03 0.05 0.02 0.02 0.30 0.30 0.04 002468 0 0.01 0 0.03 邻域半径 .14 增量更新次数 000246 增量更新次数 (a)论域增加 (b)论域减少 图5数据集biodeg在不同邻域半径下算法更新用时比较 Fig.5 Comparison of algorithm updating time of biodeg data set under different neighborhood radius 0.6 0.07 0.8 0.8 0.5 0.06 0.6 0.6 0.4 0.4 0.4 0.05 0.2 0.3 0.2 0.04 0.2 0.03 10 0.1 0.30 0. 10 8 0.02 邻域半径6 01002468 增量更新次数 00246 0.14 邻域半径 增量更新次数 (a)论域增加 (b)论域减少 图6数据集musk在不同邻域半径下算法更新用时比较 Fig.6 Comparison of algorithm updating time of musk data set under different neighborhood radius 5结束语 [3]陈家俊，徐华丽，魏赟.多重代价多粒度决策粗糙集模型 研究.计算机科学与探索，2018.12(5：839-850 邻域决策粗糙集是传统决策粗糙集的重要拓 CHEN Jiajun,XU Huali,WEI Yun.Multi-cost based 展，针对现实环境下数据集的动态性，本文提出 multi-granulation decision-theoretic rough set model[J]. 一种论域动态变化时的邻域决策粗糙集增量式更 Journal of frontiers of computer science and technology, 新算法。本文首先研究了论域中单个对象变化 2018,12(5):839-850 时，模型的增量式更新问题，然后以单个对象变 [4]JIA Xiuyi,LI Weiwei,SHANG Lin.A multiphase cost- 化为基础，通过迭代方式完成对象批量变化时的 sensitive learning method based on the multiclass three- 增量式更新问题，实验分析表明，所提出的增量 way decision-theoretic rough set model[J].Information sci- 式算法在更新动态数据时，其效率大幅度高于非 ences,.2019,485:248-262 增量式算法，且增量式算法的更新时间受论域对 [5]张婷，张红云，王真.基于三支决策粗糙集的迭代量化的 象变化的影响较小，因此说明了所提出的增量式 图像检索算法[J].南京大学学报（自然科学版），2018 54(4):714724 更新算法具有很高的优越性，从而也进一步推动 ZHANG Ting,ZHANG Hongyun,WANG Zhen.image re- 了决策粗糙集在实际环境下的应用。在本文研究 trieval:Iterative quantization based on saliency detection 成果的基础上，接下来可以进一步在邻域决策粗 and three-way decision based rough sets[J].Journal of 糙集的增量式属性约简问题上进行探索。 Nanjing University(natural sciences edition),2018,54(4): 参考文献： 714724 [6]ZHAO Xuerong,HU Baoging.Three-way decisions with [1]YAO Yiyu.Three-way decisions with probabilistic rough decision-theoretic rough sets in multiset-valued informa sets[J].Information sciences,2010,180(3):341-353 tion tables[J].Information sciences,2020,507:684-699 [2]YAO Yiyu.The superiority of three-way decisions in prob- [7]LIU Dun,LIANG Decui,WANG Changchun.A novel abilistic rough set models[J].Information sciences,2011, three-way decision model based on incomplete informa- 181(6):1080-1096 tion system[J].Knowledge-based systems,2016,91:
(a) 论域增加 0.08 0.06 0.04 0.02 0 0 2 4 6 8 10 0.30 0.26 0.22 0.18 0.14 0.10 更新用时/s 更新用时/s 邻域半径 δ 增量更新次数 0 2 4 6 8 0.30 10 0.26 0.22 0.18 0.14 0.10 邻域半径 δ 增量更新次数 0.06 0.05 0.04 0.03 0.02 0.01 0.10 0.08 0.06 0.04 0.02 (b) 论域减少 0.09 0.08 0.07 0.06 0.05 0.04 0.03 图 5 数据集 biodeg 在不同邻域半径下算法更新用时比较 Fig. 5 Comparison of algorithm updating time of biodeg data set under different neighborhood radius (a) 论域增加 0.8 0.6 0.4 0.2 0 0 2 4 6 8 10 0.30 0.26 0.22 0.18 0.14 0.10 更新用时/s 更新用时/s 邻域半径 δ 增量更新次数 0 2 4 6 8 0.30 10 0.26 0.22 0.18 0.14 0.10 邻域半径 δ 增量更新次数 0.6 0.5 0.4 0.3 0.2 0.1 0.8 0.6 0.4 0.2 0 (b) 论域减少 0.07 0.06 0.05 0.04 0.03 0.02 图 6 数据集 musk 在不同邻域半径下算法更新用时比较 Fig. 6 Comparison of algorithm updating time of musk data set under different neighborhood radius 5 结束语 邻域决策粗糙集是传统决策粗糙集的重要拓 展，针对现实环境下数据集的动态性，本文提出 一种论域动态变化时的邻域决策粗糙集增量式更 新算法。本文首先研究了论域中单个对象变化 时，模型的增量式更新问题，然后以单个对象变 化为基础，通过迭代方式完成对象批量变化时的 增量式更新问题，实验分析表明，所提出的增量 式算法在更新动态数据时，其效率大幅度高于非 增量式算法，且增量式算法的更新时间受论域对 象变化的影响较小，因此说明了所提出的增量式 更新算法具有很高的优越性，从而也进一步推动 了决策粗糙集在实际环境下的应用。在本文研究 成果的基础上，接下来可以进一步在邻域决策粗 糙集的增量式属性约简问题上进行探索。 参考文献： YAO Yiyu. Three-way decisions with probabilistic rough sets[J]. Information sciences, 2010, 180(3): 341–353. [1] YAO Yiyu. The superiority of three-way decisions in probabilistic rough set models[J]. Information sciences, 2011, 181(6): 1080–1096. [2] 陈家俊, 徐华丽, 魏赟. 多重代价多粒度决策粗糙集模型 研究 [J]. 计算机科学与探索, 2018, 12(5): 839–850. CHEN Jiajun, XU Huali, WEI Yun. Multi-cost based multi-granulation decision-theoretic rough set model[J]. Journal of frontiers of computer science and technology, 2018, 12(5): 839–850. [3] JIA Xiuyi, LI Weiwei, SHANG Lin. A multiphase costsensitive learning method based on the multiclass threeway decision-theoretic rough set model[J]. Information sciences, 2019, 485: 248–262. [4] 张婷, 张红云, 王真. 基于三支决策粗糙集的迭代量化的 图像检索算法 [J]. 南京大学学报(自然科学版), 2018, 54(4): 714–724. ZHANG Ting, ZHANG Hongyun, WANG Zhen. image retrieval: Iterative quantization based on saliency detection and three-way decision based rough sets[J]. Journal of Nanjing University (natural sciences edition), 2018, 54(4): 714–724. [5] ZHAO Xuerong, HU Baoqing. Three-way decisions with decision-theoretic rough sets in multiset-valued information tables[J]. Information sciences, 2020, 507: 684–699. [6] LIU Dun, LIANG Decui, WANG Changchun. A novel three-way decision model based on incomplete information system[J]. Knowledge-based systems, 2016, 91: [7] 第 4 期 孙海霞：基于对象变化的邻域决策粗糙集动态更新算法 ·755·