·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 卷