第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≤dsP<wP, 2.1论域中对象增加时模型的增量式更新 dww≤dN<w,那么可以得到 在邻域决策粗糙集中，研究增量式更新的关 1)当P(X6(x)≥a且P(X6(x)≥y时，x∈POS(X): 键是上下近似区域的更新问题，由于阈值α和B 2)当PX16(x)≤a且P(X6x)≥B时，x∈BUN(X)方 已经确定，因此主要涉及到对象与对象集之间的 3)当PX6(x)≤B且P(X6x)≤y时，x∈NEG(X: 概率计算，首先探讨论域对象增加时概率的增量 这里的a、B和y计算分别为 式更新。 APN-ABN 定理1设邻域型信息系统IS=(U,AT),邻 a=dpw-Aav)+QLp-p】 域半径为6且属性集ASAT。当信息系统论域U ABN ANN B=Caw-w)+Lwp-igP） 增加对象x*,新的邻域型信息系统表示为 IS*=(U=UU{x*h,AT)。令以(x)表示对象Yx∈U APN-ANN y=Cdw-Aw)+p-p） 在论域U下的邻域类，令(x)表示对象Yx∈U 进一步地，若p-ar>dar- 在论域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)<B时，x∈NEG(X). P(Yl6(x)<P(Y69(x). 因此基于上述决策判别条件，我们可以进一 2)Yx∈U-69(x),有 步得到邻域决策粗糙集的上下近似集的定义。 PX*16(x)=PX16(x): 定义30设邻域型信息系统IS=(U,AT),邻 P(Y*6(x)=PY6(x). 域半径为6，属性集ASAT确定的邻域关系为 定理1给出信息系统论域U增加一个对象 N,为了简便，这里简单表示为NA。那么对象集 后，论域对象在近似集下的概率变化关系，有了 XsU关于邻域关系Na的(a,B)邻域决策粗糙下 这种变化作为基础，接下来可以很容易得到邻域 近似和上近似分别定义为 决策粗糙集上下近似的增量式更新。 N((X)=IxE UIP(Xl6A(x))>a) 定理2设邻域型信息系统IS=(U,AT),邻域 Na”(X={x∈UPX6Ax)≥B\ 半径为6。对于X,YsU关于属性集ASAT的邻 式中：0≤B<a≤1，P(X6a(x)表示对象x的邻域关 域决策粗糙下近似分别为Na(X)和Na(Y)。当 于X的概率，定义为 信息系统论域U增加对象x*,新的邻域型信息系 PX6》=lEn为 统表示为IS*=(U+=UU{x*,AT)。若X,Y*sU 16() 且X*=XUx,Y*=Y,那么X,Y+关于属性集 ASAT的邻域决策粗糙下近似增量式更新为 2邻域决策粗糙集模型的增量式更新 1)N(X)=NB(X)U 由于现实环境下数据集的动态性，传统的模 (x E6(x)-N(X)IP(X'1(x))>a) 型和算法不再有效，针对该问题，本节将提出一 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 < λNP λNN ⩽ λBN < λPN 通常决策代价满足关系 ， ，那么可以得到 1) 当 P(X|δ(x)) ⩾ α且 P(X|δ(x)) ⩾ γ 时，x ∈ POS(X) ； 2)当 P(X|δ(x)) ⩽ α且 P(X|δ(x)) ⩾ β 时，x ∈ BUN(X) ； 3)当 P(X|δ(x)) ⩽ β 且 P(X|δ(x)) ⩽ γ 时，x ∈ NEG(X) ； 这里的 α、β 和 γ 计算分别为 α = λPN −λBN (λPN −λBN)+(λBP −λPP) β = λBN −λNN (λBN −λNN)+(λNP −λBP) γ = λPN −λNN (λPN −λNN)+(λNP −λPP) λNP −λBP λBN −λNN > λBP −λPP λPN −λBN 进一步地，若 ，则 1) 当 P(X|δ(x)) > α 时，那么 x ∈ POS(X) ； 2) 当 β ⩽ P(X|δ(x)) ⩽ α 时，那么 x ∈ BUN(X) ； 3) 当 P(X|δ(x)) < β 时，x ∈ NEG(X)。 因此基于上述决策判别条件，我们可以进一 步得到邻域决策粗糙集的上下近似集的定义。 IS = (U,AT) δ A ⊆ AT N δ A NA X ⊆ U NA (α, β) 定义 3 [10] 设邻域型信息系统 ，邻 域半径为 ，属性集 确定的邻域关系为 ，为了简便，这里简单表示为 。那么对象集 关于邻域关系 的 邻域决策粗糙下 近似和上近似分别定义为 N (α,β) A (X) = {x ∈ U|P(X|δA(x)) > α} N (α,β) A (X) = {x ∈ U|P(X|δA(x)) ⩾ β} 0 ⩽ β < α ⩽ 1 P(X|δA(x)) x X 式中： , 表示对象 的邻域关 于 的概率，定义为 P(X|δA(x)) = |δA(x)∩ X| |δA(x)| 2 邻域决策粗糙集模型的增量式更新 由于现实环境下数据集的动态性，传统的模 型和算法不再有效，针对该问题，本节将提出一 种论域变化时邻域决策粗糙集模型的增量式更新 方法。 α β P(X|δ(x)) α β 定义 3 已经表明，当信息系统的决策代价已 经确定时，则邻域决策粗糙集中的阈值 和 也 就确定，因此对于邻域决策粗糙集的研究只需考 虑概率 与阈值 和 的关系即可。 数据集论域中对象的增加和减少往往都是批 量的，而这些批量的变化可以分解成对象的一个 一个依次变化，每次只考虑数据集中一个对象增 加或减少时的增量式更新问题，然后逐步对多个 对象进行迭代，这样可以简化问题的处理[12, 17-18]。 根据这一思想，构造了本文模型的增量式更新 方法。 2.1 论域中对象增加时模型的增量式更新 α β 在邻域决策粗糙集中，研究增量式更新的关 键是上下近似区域的更新问题，由于阈值 和 已经确定，因此主要涉及到对象与对象集之间的 概率计算，首先探讨论域对象增加时概率的增量 式更新。 IS = (U,AT) δ A ⊆ AT U x + IS+ = (U + = U ∪ {x + },AT) δ U A (x) ∀x ∈ U + U δ U + A (x) ∀x ∈ U + U + X,Y ⊆ U X + ,Y + ⊆ U + X + = X ∪ {x + } Y + = Y 定理 1 [18] 设邻域型信息系统 ，邻 域半径为 且属性集 。当信息系统论域 增加对象 ，新的邻域型信息系统表示为 。令 表示对象 在论域 下的邻域类，令 表示对象 在论域 下的邻域类。对于 ， 若 且 ， 。那么满足： ∀x ∈ δ U + A (x + )− {x + 1) } ，有 P(X + |δ U + A (x)) ⩾ P(X|δ 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)). 定理 1 给出信息系统论域 U 增加一个对象 后，论域对象在近似集下的概率变化关系，有了 这种变化作为基础，接下来可以很容易得到邻域 决策粗糙集上下近似的增量式更新。 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 定理 2 设邻域型信息系统 ，邻域 半径为 。对于 关于属性集 的邻 域决策粗糙下近似分别为 和 。当 信息系统论域 增加对象 ，新的邻域型信息系 统表示为 。 若 且 ， ，那么 关于属性集 的邻域决策粗糙下近似增量式更新为 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)) ⩽ α})∪ {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()<BDU Ix E64(x)-N (X)IP(X-1(x))>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)<P(YI6(x)≤a N(X)更新至NX),只需计算6(x)-N(N 当x∈U-(x)时，有 内的对象，从N()更新至N(Y),只需计算 P(Y6g(x)=P(YI6(x)≤a N”()n6(r)中的对象，因此定理3同样具有 因此Yx∈U-N(Y)都满足P(Y6(x)≤a, 很高的更新计算效率。 即x生N(Y)。 定理2和定理3分别给出当邻域信息系统增 对于Yx∈Y(Y),都有P(Y6()>a。根据 加一个对象时，邻域决策粗糙上下近似的增量式 定理1，当xe(x)-{x时，有 更新问题，当信息系统通过增加多个对象，可以 P(Y+l6g(x)<P(Y6g(),P(Y6()>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 < N (α,β) A (X + ) 对于 ，若 ，由定 理 1 可得 。那么此时 。 x ∈ δ U + A (x + )− {x + 若 } ，根据定理 1 可得 P(X + |δ U + A (x)) ⩾ 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 + )−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)) < P(Y|δ U A (x)) ⩽ α x ∈ U + −δ U + A (x + 当 ) 时，有 P(Y + |δ U + A (x)) = P(Y|δ U A (x)) ⩽ α ∀x ∈ U −N (α,β) A (Y) P(Y + |δ U + A (x)) ⩽ α x < N (α,β) A (Y + ) 因此 都满足 ， 即 。 ∀x ∈ N (α,β) A (Y) P(Y|δ U A (x)) > α x ∈ δ U + A (x + )− {x + } 对于 ，都有 。根据 定理 1，当 时，有 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 + 当 ) 时，有 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)) < β})∪ {x ∈ {x + }|P(Y + |δ U + A (x)) ⩾ β} 证明 证明过程同定理 2。 N (α,β) A (X) N (α,β) A (X + ) δ U + A (x + )−N (α,β) A (X) N (α,β) A (Y) N (α,β) A (Y + ) N (α,β) A (Y)∩δ U + A (x + ) 定理 3 类似于定理 2，更新上近似集时也只需 要针对部分对象集进行计算便可完成，例如从 更新至 ，只需计算 内的对象，从 更新至 ，只需计算 中的对象，因此定理 3 同样具有 很高的更新计算效率。 定理 2 和定理 3 分别给出当邻域信息系统增 加一个对象时，邻域决策粗糙上下近似的增量式 更新问题，当信息系统通过增加多个对象，可以 根据定理 2 和定理 3 逐步进行迭代，直至完成最 终的更新。 2.2 论域中对象减少时模型的增量式更新 类似于第 2.1 节中研究方法，本节将进一步 提出论域中对象减少时模型的增量式更新，首先 分析对象减少时概率的变化关系。 IS = (U,AT) δ A ⊆ AT U x − x − ∈ U IS− = (U − = U − {x − },AT) δ U A (x) ∀x ∈ U U δ U − A (x) ∀x ∈ U U − X,Y ⊆ U X − ,Y − ⊆ U − X − = X − {x − } Y − = Y 定理 4 [18] 设邻域型信息系统 ，邻 域半径为 且属性集 。当信息系统论域 移除对象 ， ，新的邻域型信息系统表示为 。令 表示对象 在论域 下的邻域类，令 表示对象 在论域 下的邻域类。对于 , 若 且 ， 。那么满足 ∀x ∈ δ U A (x − )− {x − 1) },有 P(X − |δ U − A (x)) ⩽ P(X|δ 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 决策粗糙集上下近似的增量式更新。 即x年N(Y-)。 定理5设邻域型信息系统IS=(U,AT),邻域 因此只需要计算对象集(U-Wa(Y)n 半径为6。对于X,YsU关于属性集AsAT的邻 (⊙(x)-{x)中的对象便可以完成近似集的增量 域决策粗糙下近似分别为Nm(X)和Na(Y)。当 式更新，即计算x∈(x)-{x}-N(Y),因此 信息系统论域U移除对象x且x∈U,新的邻域 2)成立。 型信息系统表示为IS=(U=U-{x,AT)。若 定理5证明完毕。 X,Y≤U且X=X-{x,Y=Y,那么X,Y关于 定理5表明，当邻域型信息系统移除一个对 属性集ASAT的邻域决策粗糙下近似增量式更 象x后，新的邻域决策粗糙下近似集变化也呈现 新为 一定的规律，例如从Y(X)更新至N(X),其 1)N(X-)=N(X)-IxE N(X) 近似集是减小的，并且减少的对象只来源于一小 (6(x)-{rlP(X6(x)≤a 部分对象集，因此只需对这里面的对象进行概率 2)N(Y-)=N(YU P(Xl6(x》的计算，便可得到最终的更新结果。 IxE60(x)-x)-N (Y)P(Y-180 (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)<\ xN(X-). 若对象满足x∈U-洲(x),那么由定理4可以得 2)N(Y-)=N(Y)U 到PX6g(x)=P(X6(x)≤。因此Yx∈U-Na(X) xe6)-1-N"YPY6m)≥B 且x∈U-(x)都有x生Y(X)。综合起来 证明1)根据定理5的证明结果，对于 Yx∈U-Na()都满足xW(X-),则(I)成立。 xeU-N(X)都满足xEN(X)。而对于 2)对于Yx∈W(),若对象满足x∈(x)- xeN(X且xU-x)都有x∈N(X),只 (x1,那么由定理4可以得到 有当Yx∈N(X)且x∈6x)-{x)时，PX6(x) P(Y-1 (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 < N (α,β) A (X − ) 因此 且 都有 . x ∈ U −δ U A (x − ) P(X − |δ U − A (x)) = P(X|δ U A (x)) ⩽ α ∀x ∈ U −N (α,β) A (X) x ∈ U −δ U A (x − ) x < N (α,β) A (X − ) ∀x ∈ U −N (α,β) A (X) x < N (α,β) A (X − ) 若对象满足 ，那么由定理 4 可以得 到 。因此 且 都 有 。综合起来 都满足 ，则 (1) 成立。 ∀x ∈ N (α,β) A (Y) x ∈ δ U A (x − )− {x − } 2) 对于 ，若对象满足 ，那么由定理 4 可以得到 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) 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 卷