第5期 徐健锋，等：概率粗糙集三支决策在线快速计算算法研究 ·745· ③假设p3:R”C NEG8(DAPr(DR)≥a 式中： 成立，由定义2得Pr(D1R)≤B。因为Pr(D+R≥ b1:ROC POS(D)AB<Pr(DuDIR)<a a,即R+CPOS(D),则接受域更新为POSa b2:RC BND(DAB<Pr(DR)<a (D=POS(D)UR+。 b3:RCBND(D)APr(DR)<B 2)对于3ND(D+ (NEG(D)URD,m ①假设b1:RCBND(D)Pr(DR+)≥a成 3)NEG((D)=NEG(B(D)URD,n2 立，由定义2得B<Pr(DR)<。因为Pr(DR+)≥ NEG(B(D()-RUR, ns a,即CPOS(D),则边界域更新为BNDa 式中： (D=BNDa(D)-R。 m:R∈POS(D)APr(D+IR+≤B ②假设b2:RCBND(D9)B<P(D1R+)< n:RC BND(DP)APr(D+”IR+)≤B a成立，由定义2得B<Pr(D9R<a,因为B<Pr(DI R<a,即DCBND(D),则边界域更新为 ns:RCNEG (D) 证明证明过程与推论1类似，此处略。证毕。 BND(D)=BND(D()-RURD 推论3给定1时刻信息系统S={U9,CUD ③假设b:R”CNEG/(D)B<Pr(D+1R+")< 和1+1时刻信息系统IS)={U+),C+UD, a成立，由定义2得Pr(DR)<B,因为B<Pr(D 若定理3描述的变化模式成立，三支决策区域更 R+<a,即R”C BND(D,则边界域更新为 新为： BNDa(Dgt)=BNDa(DUR。 POS:RCPOS(D)=POS(D)=POS(D): 3)对于NEG@8(D+ BND:REBND(D)=BND(D)=BND(D): ①假设m1:R”C NEG(D)APr(D件R≥a NEG:RCNEG(D')→NEGa(D)=NEG8(D)。 成立，由定义2得r(DIR)≥a,因为P(D+IR+)≥a, 证明根据定理3，条件概率Pr(D+C,+) 即R+CPOS(DP,则拒绝域更新为NEGe(D+)= 保持不变，由定义2可知此时三支决策区域亦是 NEG(@(D-R。 保持不变的。证毕。 ②假设m2:R CBNDA(D)B<Pr(DR+)< 2.3三支决策在线快速计算算法 a成立，由定义2得B<Pr(DR)<,因为B<Pr(D+ 根据2.1节中的定理1~3推导出的概率粗糙 R+)<a,即R+”CBND(D),则拒绝域更新为 集的条件概率变化趋势，以及2.2节中的三支决 NEG(D牛)=NEGa(D9)-R+。 策区域的快速计算3种情形展开讨论。 ③假设m3:R”NEGa(D)APr(D+R+)≤B 本节设计了三支决策在线快速计算算法(on- 成立，由定义2得r(DIR)<B.因为Pr(DR+)≤B, line computing algorithm),并从算法时间复杂度角 即RCNEG(D,则拒绝域更新为NEGa(D件)= 度与基于三支决策理论的经典计算算法作对比， NEGm(D)-RURm。 从理论上分析在线快速计算算法的优势。 证毕。 算法1三支决策在线快速计算算法 推论2给定1时刻信息系统S0={U0,C0UD叫 输入1时刻信息系统ISo={Uo,CoUD,条 和1+1时刻信息系统S)={U,C+UD, 件等价类和决策等价类R、D9i=1,2,…,m:j= 若定理2描述的变化模式成立，则三支决策区域 1,2,…,n,条件概率Pr(D91Ri=1,2,…,m:j=1,2,…, 更新为 (POS(D)-RUR,P ),三支决策接受域、拒绝域和边界域POS(D) 1)POS(D)=POS(D)-R,P2 BNDa(D及NEG(a(D9),新增决策对象及被移 出对象x,三支决策阈值(a,)。 POSa(D)-R”,ps 输出1+1时刻三支决策区域POS(D)、 式中： BND(Dgt"及NEGm(D)。 Pi:RPOS(D)APr(DDR)a 1)通过及x的等价类从属关系，更新+1时 p2 RPOS (D)AB<Pr(DDIRD)<a 刻的条件等价类和决策等价类R和D: P3:R9∈POS(D)APr(DIR+)≤B 2)根据定理1~3评估1+1时刻条件概率 BND(D)URD,b Pr(DR的变化趋势； 2)BND(D)= BND(D)-RURD),b2 3)根据推论1~3更新什1时刻三支决策区域 BNDa(D)-R”,bs POS(D+)、BNDa(D+、NEGa(D+");p3 : R (t) i ⊆ NEG(α,β)(D (t) j )∧Pr(D (t+1) j |R (t+1) i ) ⩾ α Pr(D (t) j |R (t) i ) ⩽ β Pr(D (t+1) j |R (t+1) i ) ⩾ α R (t+1) i ⊆ POS(α,β)(D (t+1) j ) POS(α,β) (D (t+1) j ) = POS(α,β)(D (t) j )∪R (t+1) i ③假设 成立，由定义2得 。因为 ，即 ，则接受域更新为 。 BND(α,β)(D (t+1) j 2) 对于 ) b1 : R (t) i ⊆BND(α,β)(D (t) j )∧Pr(D (t+1) j |R (t+1) i )⩾α β<Pr(D (t) j |R (t) i ) < α Pr(D (t+1) j |R (t+1) i )⩾ α R (t+1) i ⊆ POS(α,β)(D (t) j ) BND(α,β) (D (t+1) j ) = BND(α,β)(D (t) j )−R (t) i ①假设 成 立，由定义2得 。因为 ，即 ，则边界域更新为 。 b2 : R (t) i ⊆BND(α,β)(D (t) j )∧β<Pr(D (t+1) j |R (t+1) i )< α β < Pr(D (t) j |R (t) i ) < α β < Pr(D (t+1) j | R (t+1) i ) < α R (t+1) i ⊆ BND(α,β)(D (t) j ) BND(α,β)(D (t+1) j ) = BND(α,β)(D (t) j )−R (t) i ∪R (t+1) i ②假设 成立，由定义2得 ，因为 ，即 ，则边界域更新为 。 b3 : R (t) i ⊆NEG(α,β)(D (t) j )∧β<Pr(D (t+1) j |R (t+1) i ) < α Pr(D (t) j |R (t) i ) < β β < Pr(D (t+1) j | R (t+1) i ) < α R (t+1) i ⊆ BND(α,β)(D (t) j ) BND(α,β)(D (t+1) j ) =BND(α,β)(D (t) j )∪R (t+1) i ③假设 成立，由定义 2 得 ，因为 ，即 ，则边界域更新为 。 NEG(α,β)(D (t+1) j 3) 对于 ) n1 : R (t) i ⊆ NEG(α,β)(D (t) j )∧Pr(D (t+1) j |R (t+1) i ) ⩾ α Pr(D (t) j |R (t) i )⩾α Pr(D (t+1) j |R (t+1) i )⩾α R (t+1) i ⊆POS(α,β)(D (t) j ) NEG(α,β)(D (t+1) j )= NEG(α,β)(D (t) j )−R (t) i ①假设 成立，由定义2得 ，因为 ， 即 ，则拒绝域更新为 。 n2 : R (t) i ⊆BND(α,β)(D (t) j )∧β<Pr(D (t+1) j |R (t+1) i ) < α β<Pr(D (t) j |R (t) i )<α β < Pr(D (t+1) j | R (t+1) i ) < α R (t+1) i ⊆ BND(α,β)(D (t+1) j ) NEG(α,β)(D (t+1) j ) = NEG(α,β)(D (t) j )−R (t+1) i ②假设 成立，由定义 2 得 ，因为 ，即 ，则拒绝域更新为 。 n3 : R (t) i ⊆ NEG(α,β)(D (t) j )∧Pr(D (t+1) j |R (t+1) i ) ⩽ β Pr(D (t) j |R (t) i )< β Pr(D (t+1) j |R (t+1) i )⩽β R (t+1) i ⊆NEG(α,β)(D (t+1) j ) NEG(α,β)(D (t+1) j )= NEG(α,β)(D (t) j )−R (t) i ∪R (t+1) i ③假设 成立，由定义2得 ，因为 ， 即 ，则拒绝域更新为 。 证毕。 IS(t) = { U (t) ,C (t) ∪ D (t) } IS(t+1) = { U (t+1) ,C (t+1) ∪ D (t+1)} 推论2 给定 t时刻信息系统 和 t + 1 时刻信息系统 ， 若定理 2 描述的变化模式成立，则三支决策区域 更新为 1) POS(α,β)(D (t+1) j ) =    POS(α,β)(D (t) j )−R (t) i ∪R (t+1) i , p1 POS(α,β)(D (t) j )−R (t) i , p2 POS(α,β)(D (t) j )−R (t) i , p3 p1 : R (t) i ⊆ POS(α,β)(D (t) j )∧Pr(D (t+1) j |R (t+1) i ) ⩾ α p2 : R (t) i ⊆ POS(α,β)(D (t) j )∧β < Pr(D (t+1) j |R (t+1) i ) < α p3 : R (t) i ⊆ POS(α,β)(D (t) j )∧Pr(D (t+1) j |R (t+1) i ) ⩽ β 式中： 2) BND(α,β)(D (t+1) j ) =    BND(α,β)(D (t) j )∪R (t+1) i , b1 BND(α,β)(D (t) j )−R (t) i ∪R (t+1) i , b2 BND(α,β)(D (t) j )−R (t) i , b3 b1 : R (t) i ⊆ POS(α,β)(D (t) j )∧β < Pr(D (t+1) j |R (t+1) i ) < α b2 : R (t) i ⊆ BND(α,β)(D (t) j )∧β < Pr(D (t+1) j |R (t+1) i ) < α b3 : R (t) i ⊆ BND(α,β)(D (t) j )∧Pr(D (t+1) j |R (t+1) i ) ⩽ β 式中： 3) NEG(α,β)(D (t+1) j ) =    NEG(α,β)(D (t) j )∪R (t+1) i , n1 NEG(α,β)(D (t) j )∪R (t+1) i , n2 NEG(α,β)(D (t) j )−R (t) i ∪R (t+1) i , n3 n1 : R (t) i ⊆ POS(α,β)(D (t) j )∧Pr(D (t+1) j |R (t+1) i ) ⩽ β n2 : R (t) i ⊆ BND(α,β)(D (t) j )∧Pr(D (t+1) j |R (t+1) i ) ⩽ β n3 : R (t) i ⊆ NEG(α,β)(D (t) j ) 式中： 证明 证明过程与推论 1 类似，此处略。证毕。 IS(t) = { U (t) ,C (t) ∪ D (t) } IS(t+1) = { U (t+1) ,C (t+1) ∪ D (t+1)} 推论3 给定t时刻信息系统 和 t + 1 时刻信息系统 ， 若定理 3 描述的变化模式成立，三支决策区域更 新为： POS : R (t) i ⊆POS(α,β)(D (t) j )⇒POS(α,β)(D (t+1) j )=POS(α,β)(D (t) j ); BND : R (t) i ⊆BND(α,β)(D (t) j )⇒BND(α,β)(D (t+1) j )=BND(α,β)(D (t) j ); NEG : R (t) i ⊆NEG(α,β)(D (t) j )⇒NEG(α,β)(D (t+1) j )=NEG(α,β)(D (t) j )。 Pr(Dj (t+1)   Ci (t+1) 证明 根据定理 3，条件概率 ) 保持不变，由定义 2 可知此时三支决策区域亦是 保持不变的。证毕。 2.3 三支决策在线快速计算算法 根据 2.1 节中的定理 1~3 推导出的概率粗糙 集的条件概率变化趋势，以及 2.2 节中的三支决 策区域的快速计算 3 种情形展开讨论。 本节设计了三支决策在线快速计算算法 (on￾line computing algorithm)，并从算法时间复杂度角 度与基于三支决策理论的经典计算算法作对比， 从理论上分析在线快速计算算法的优势。 算法 1 三支决策在线快速计算算法 IS(t) = { U (t) ,C (t) ∪ D (t) } R (t) i D (t) j (i = 1,2,··· ,m; j = 1,2,··· ,n) Pr(D (t) j |R (t) i )(i=1,2,··· ,m; j=1,2,··· , n) POS(α,β)(D (t) j ) BND(α,β)(D (t) j ) NEG(α,β)(D (t) j ) x x 输入 t 时刻信息系统 ，条 件等价类和决策等价类 、 ，条件概率 ，三支决策接受域、拒绝域和边界域 、 及 ，新增决策对象 及被移 出对象 ，三支决策阈值 (α，β)。 POS(α,β)(D (t+1) j ) BND(α,β)(D (t+1) j ) NEG(α,β)(D (t+1) j ) 输出 t+1 时刻三支决策区域 、 及 。 x x R (t+1) i D (t+1) j 1) 通过 及 的等价类从属关系，更新 t+1 时 刻的条件等价类和决策等价类 和 ; Pr(D (t+1) j |R (t+1) i ) 2) 根据定 理 1~3 评 估 t+1 时刻条件概率 的变化趋势; POS(α,β)(D (t+1) j ) BND(α,β)(D (t+1) j ) NEG(α,β)(D (t+1) j ) 3) 根据推论 1~3 更新 t+1 时刻三支决策区域 、 、 ; 第 5 期 徐健锋，等：概率粗糙集三支决策在线快速计算算法研究 ·745·