第13卷第5期 智能系统学报 Vol.13 No.5 2018年10月 CAAI Transactions on Intelligent Systems Oct.2018 D0:10.11992/tis.201706047 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180419.1332.008.html 概率粗糙集三支决策在线快速计算算法研究 徐健锋2，何宇凡，汤涛，赵志宾2 (1.南昌大学软件工程系，江西南昌330029：2.同济大学计算机科学与技术系，上海201804) 摘要：随着大数据和物联网技术的不断发展，动态在线计算已经成为了一种常见的计算模式，在动态在线计 算中进行不确定问题的推理和求解是一项具有挑战性的新议题。概率粗糙集三支决策理论是一种处理不确定 性知识挖掘的有效工具，根据在线计算模式中数据同步增减的动态特点，提出了一种概率粗糙集三支决策的在 线计算方法。首先，以内存滑动窗口模式对在线动态计算的数据变化特点进行理论建模：然后，根据上述模型 中在线计算的数据变化模式，推导出不同类型数据变化模式下的三支决策条件概率及三支区域的变化规律：最 后，提出了一种新型在线快速计算算法，其获取的三支决策规则与经典概率三支决策算法是等效的。通过与经 典三支决策计算算法的多组对比实验，验证了提出的在线快速计算算法的高效性与稳定性。 关键词：三支决策；粗糙集；条件概率；在线计算；不确定；动态计算；粒计算 中图分类号：TP181文献标志码：A文章编号：1673-4785(2018)05-0741-10 中文引用格式：徐健锋，何宇凡，汤涛，等.概率粗糙集三支决策在线快速计算算法研究.智能系统学报，2018,13(5)： 741-750. 英文引用格式：XU Jianfeng,.HE Yufan,TANG Tao,etal.Research on a fast online computing algorithm based on three--way de cisions with probabilistic rough sets Jl.CAAI transactions on intelligent systems,2018,13(5):741-750. Research on a fast online computing algorithm based on three-way decisions with probabilistic rough sets XU Jianfeng,HE Yufan',TANG Tao',ZHAO Zhibin'2 (1.Department of Software Engineering.Nanchang University,Nanchang 330029,China;2.Department of Computer Science and Technology,Tongji University,Shanghai 201804,China) Abstract:With the continuous development of big data and IoT(Internet of Things),dynamic online computation has become a common computing pattern;however the field of dynamic online computation faces challenges in deducing and solving uncertainty problems.A three-way decision theory with probabilistic rough set method is an efficient tool for mining uncertain knowledge;thus a dynamic online computing approach of three-way decision theory with probabil- istic rough set is proposed in this paper,in accordance with the features of data dynamic synchronization.First,a data model is established to describe the inherent features of dynamic online computation via memory sliding window mode. In terms of the variational features of dynamic online computation of the above model,a three-way decision conditional probability and the change rule of three-way area are deduced as diverse variational patterns of data.Finally,a novel al- gorithm of online rapid computation is proposed.The obtained three-way decision rule is identical with the three-way decision algorithm of classic probability.By comparison with the classic three-way decision algorithm through multiple experiments,the proposed online rapid computation algorithm is confirmed to have high efficiency and stability Keywords:three-way decisions;rough sets;conditional probability;online computing;uncertain;dynamic calculation; granular computing 随着大数据与互联网加时代的到来，动态流 收稿日期：2017-06-12.网络出版日期：2018-04-19. 基金项目：国家自然科学基金项目(61763031,61673301)：上海 数据成为了一种主流的数据类型，当前已经被广 市自然科学基金项目(14ZR1442600):江西省研究生 创新专项资金项目(YC2016-S053). 泛地应用于金融股票交易、天气和环境监测、计 通信作者：徐健锋.E-mail:jianfeng_x@ncu.edu.cn. 算机网络监控等众多领域口。在上述应用中，在
DOI: 10.11992/tis.201706047 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180419.1332.008.html 概率粗糙集三支决策在线快速计算算法研究 徐健锋1,2，何宇凡1 ，汤涛1 ，赵志宾1,2 （1. 南昌大学 软件工程系，江西 南昌 330029; 2. 同济大学 计算机科学与技术系，上海 201804） 摘 要：随着大数据和物联网技术的不断发展，动态在线计算已经成为了一种常见的计算模式，在动态在线计 算中进行不确定问题的推理和求解是一项具有挑战性的新议题。概率粗糙集三支决策理论是一种处理不确定 性知识挖掘的有效工具，根据在线计算模式中数据同步增减的动态特点，提出了一种概率粗糙集三支决策的在 线计算方法。首先，以内存滑动窗口模式对在线动态计算的数据变化特点进行理论建模；然后，根据上述模型 中在线计算的数据变化模式，推导出不同类型数据变化模式下的三支决策条件概率及三支区域的变化规律；最 后，提出了一种新型在线快速计算算法，其获取的三支决策规则与经典概率三支决策算法是等效的。通过与经 典三支决策计算算法的多组对比实验，验证了提出的在线快速计算算法的高效性与稳定性。 关键词：三支决策；粗糙集；条件概率；在线计算；不确定；动态计算；粒计算 中图分类号：TP181 文献标志码：A 文章编号：1673−4785(2018)05−0741−10 中文引用格式：徐健锋, 何宇凡, 汤涛, 等. 概率粗糙集三支决策在线快速计算算法研究[J]. 智能系统学报, 2018, 13(5): 741–750. 英文引用格式：XU Jianfeng, HE Yufan, TANG Tao, et al. Research on a fast online computing algorithm based on three-way decisions with probabilistic rough sets[J]. CAAI transactions on intelligent systems, 2018, 13(5): 741–750. Research on a fast online computing algorithm based on three-way decisions with probabilistic rough sets XU Jianfeng1,2 ，HE Yufan1 ，TANG Tao1 ，ZHAO Zhibin1,2 (1. Department of Software Engineering, Nanchang University, Nanchang 330029, China; 2. Department of Computer Science and Technology, Tongji University, Shanghai 201804, China) Abstract: With the continuous development of big data and IoT (Internet of Things), dynamic online computation has become a common computing pattern; however the field of dynamic online computation faces challenges in deducing and solving uncertainty problems. A three-way decision theory with probabilistic rough set method is an efficient tool for mining uncertain knowledge; thus a dynamic online computing approach of three-way decision theory with probabilistic rough set is proposed in this paper, in accordance with the features of data dynamic synchronization. First, a data model is established to describe the inherent features of dynamic online computation via memory sliding window mode. In terms of the variational features of dynamic online computation of the above model, a three-way decision conditional probability and the change rule of three-way area are deduced as diverse variational patterns of data. Finally, a novel algorithm of online rapid computation is proposed. The obtained three-way decision rule is identical with the three-way decision algorithm of classic probability. By comparison with the classic three-way decision algorithm through multiple experiments, the proposed online rapid computation algorithm is confirmed to have high efficiency and stability. Keywords: three-way decisions; rough sets; conditional probability; online computing; uncertain; dynamic calculation; granular computing 随着大数据与互联网加时代的到来，动态流 数据成为了一种主流的数据类型，当前已经被广 泛地应用于金融股票交易、天气和环境监测、计 算机网络监控等众多领域[1]。在上述应用中，在 收稿日期：2017−06−12. 网络出版日期：2018−04−19. 基金项目：国家自然科学基金项目 (61763031，61673301)；上海 市自然科学基金项目 (14ZR1442600)；江西省研究生 创新专项资金项目 (YC2016-S053). 通信作者：徐健锋. E-mail：jianfeng_x@ncu.edu.cn. 第 13 卷第 5 期 智 能 系 统 学 报 Vol.13 No.5 2018 年 10 月 CAAI Transactions on Intelligent Systems Oct. 2018
·742· 智能系统学报 第13卷 线计算是动态流数据的主要计算形式，其主要 在线计算为背景的动态三支决策研究较少。 特点是实时数据快速地加载入内存，而CPU需要 本文以上述三支决策动态计算研究为基础， 对内存中的实时数据实施快速计算，并且实时反 系统性地研究了在线计算中动态数据变化形式及 馈计算结果。而传统的离线计算方式需要外部 动态决策的变化规律，提出一种有别于传统经典 存储器积淀数据后再进行科学计算，对于数据实 计算的三支决策在线快速计算学习方法，并进行 时性和流动性的要求相对较低，因此传统计算方 实验验证。 法不能完全适应在线计算的新要求。研究更加高 效的在线计算方法已经成为了当前大数据领域的 1相关工作 一项重要课题。 1.1概率粗糙集三支决策模型 近年来，以SPARKISH为代表的内存计算平台 概率粗糙集是构造三支决策的基础原型，首 的推出与发展，较快推动了动态在线计算的发 先我们回顾一下概率粗糙集三支决策的相关基本 展。不确定性问题是机器学习领域的经典难题， 理论0。 如何在在线计算过程中进行不确定性问题的动 信息系统IS是一个四元组，IS=(U,A,Vf),其 态推理及求解也逐渐成为一项具有挑战性的新 中U代表论域中对象x的集合；A=RUD代表属性 议题。 集合，R为条件属性集合(UIR={R,R2,Rm}为R 三支决策理论是基于粒计算粗糙集理论提 属性确定的不可区分关系形成的等价类集合)， 出和发展起来的一种处理不确定、不完整信息决 D为决策属性集合(UID={D,D2,D}为D属性 策的新方法。其初始目的是为粗糙集理论中的 确定的不可区分关系形成的等价类集合)：V代表 3个分类区域，即正域、负域和边界域，提供合理 A中各属性的取值范围；f代表从对象到属性取值 的决策语义解释。近年来随着该理论的深入研究 的信息函数，即f:U×A→V。 与发展，三支决策被认为是在信息不足或者获取 定义1在信息系统IS中，设D,为论域U的 足够信息的代价较高背景下的合理选择。该理论 子集，即DSU,给定一个等价类[xsU属于D,的 与人类的认知习惯相似，具有认知方面的优势， 近年来，三支决策理论在垃圾邮件过滤、文本挖掘 条件概率可定义为Pr(D,=D,n因 I[xll 图像识别、属性约简0、聚类等应用领域2 注：表示集合的基数。 也都取得了广泛的成果。 定义2设D为论域U的子集，即DSU,给 目前主要代表性的理论成果包括：基于代价 定一对阈值(a,),并且满足0≤B<a≤1，则(a,B) 敏感度量的决策粗糙集三支决策1、模糊集三支 正域、负域和边界域可以定义为 决策16、区间集三支决策Ⅵ、概率粗糙集三支决 POSa.(D）={x∈UIPr(DHx]）≥a 策】、博弈粗糙集三支决策]、信息熵三支决 NEG.(D,)={x∈UIPr(D,x)≤\ BND(.(D )=(xE UlB<Pr(Dil[x])<a) 策o、GNI系数三支决策2四等。 通过定义2中的(a)-正域、负域和边界域， 同时针对动态数据环境下的动态计算也是另 可分别生成相应的接受、拒绝和延迟决策规则。 一项主要研究内容。文献[22]首次提出一种离线 1.2三支决策在线快速计算模型 动态计算方法，其对更新后的数据对象进行重新 滑动窗口技术2：2别可以有效处理动态流数据 计算，算法执行效率不高。为了提高动态计算的 下的数据挖掘与知识更新问题。在线计算的动态 效率，许多学者研究了粗糙集及三支决策的离线 特点是，随着新数据不断进入，同时由于内存空 增量学习方法。其主要成果有：Liu等P提出了一 间的限制，旧数据也被不断被删除，内存中包含 种基于矩阵的动态不完备信息系统的增量方法： 的计算数据既增又减。由此，三支决策在线计算 Li等通过分析动态数据库中新数据的不断更新， 的数据变化模式可以用滑动窗口的方式进行描述。 提出了基于粗糙集理论的增量学习方法；Zhang等凹 给定1时刻的决策信息系统表：IS= 等给出了邻域粗糙集模型下多对象增加删除时近 {U9,C9UD,其中U1C”={R",R29,R”,…,Rm 似集快速更新的方法；Luo等2考虑到信息系统 U/D0={D”,D2,D”,…,Dn。将决策表空间 中数据对象动态插入，讨论介绍了概率粗糙集模 看作内存空间，即当前决策表中为内存中实时计 型中条件概率的动态估计策略，进而给出了概率 算的数据。当+1时刻有新的数据对象动态进出 三支近似的增量更新算法。然而研究表明，上述 决策表时，内存空间发生数据动态变化，其变化 动态学习研究都是以离线计算为研究背景，而以 机制如下
线计算[2-3]是动态流数据的主要计算形式，其主要 特点是实时数据快速地加载入内存，而 CPU 需要 对内存中的实时数据实施快速计算，并且实时反 馈计算结果。而传统的离线计算[4]方式需要外部 存储器积淀数据后再进行科学计算，对于数据实 时性和流动性的要求相对较低，因此传统计算方 法不能完全适应在线计算的新要求。研究更加高 效的在线计算方法已经成为了当前大数据领域的 一项重要课题。 近年来，以 SPARK[5]为代表的内存计算平台 的推出与发展，较快推动了动态在线计算的发 展。不确定性问题是机器学习领域的经典难题， 如何在在线计算过程中进行不确定性问题的动 态推理及求解也逐渐成为一项具有挑战性的新 议题。 三支决策理论[6]是基于粒计算粗糙集理论提 出和发展起来的一种处理不确定、不完整信息决 策的新方法。其初始目的是为粗糙集理论中的 3 个分类区域，即正域、负域和边界域，提供合理 的决策语义解释。近年来随着该理论的深入研究 与发展，三支决策被认为是在信息不足或者获取 足够信息的代价较高背景下的合理选择。该理论 与人类的认知习惯相似，具有认知方面的优势， 近年来，三支决策理论在垃圾邮件过滤[7] 、文本挖掘[8] 、 图像识别[9] 、属性约简[10] 、聚类[11]等应用领域[12-14] 也都取得了广泛的成果。 目前主要代表性的理论成果包括：基于代价 敏感度量的决策粗糙集三支决策[15] 、模糊集三支 决策[16] 、区间集三支决策[17] 、概率粗糙集三支决 策 [ 1 8 ] 、博弈粗糙集三支决策[ 1 9 ] 、信息熵三支决 策 [20] 、GINI 系数三支决策[21]等。 同时针对动态数据环境下的动态计算也是另 一项主要研究内容。文献[22]首次提出一种离线 动态计算方法，其对更新后的数据对象进行重新 计算，算法执行效率不高。为了提高动态计算的 效率，许多学者研究了粗糙集及三支决策的离线 增量学习方法。其主要成果有：Liu 等 [23]提出了一 种基于矩阵的动态不完备信息系统的增量方法； Li 等 [24]通过分析动态数据库中新数据的不断更新， 提出了基于粗糙集理论的增量学习方法；Zhang 等 [25] 等给出了邻域粗糙集模型下多对象增加删除时近 似集快速更新的方法；Luo 等 [26]考虑到信息系统 中数据对象动态插入，讨论介绍了概率粗糙集模 型中条件概率的动态估计策略，进而给出了概率 三支近似的增量更新算法。然而研究表明，上述 动态学习研究都是以离线计算为研究背景，而以 在线计算为背景的动态三支决策研究较少。 本文以上述三支决策动态计算研究为基础， 系统性地研究了在线计算中动态数据变化形式及 动态决策的变化规律，提出一种有别于传统经典 计算的三支决策在线快速计算学习方法，并进行 实验验证。 1 相关工作 1.1 概率粗糙集三支决策模型 概率粗糙集是构造三支决策的基础原型，首 先我们回顾一下概率粗糙集三支决策的相关基本 理论[20]。 IS IS = (U,A,V, f) U x A = R∪ D U/R = {R1,R2 · ··,Rm} U/D = {D1,D2 · ··,Dn} f f : U × A → V 信息系统 是一个四元组， ，其 中 代表论域中对象 的集合； 代表属性 集合，R 为条件属性集合 ( 为 R 属性确定的不可区分关系形成的等价类集合)， D 为决策属性集合 ( 为 D 属性 确定的不可区分关系形成的等价类集合)；V 代表 A 中各属性的取值范围； 代表从对象到属性取值 的信息函数，即 。 IS Dj Dj ⊆ U [x] ⊆ U Dj Pr(Dj |[x]) = |Dj ∩[x]| |[x]| 定义 1 在信息系统 中，设 为论域 U 的 子集，即 ，给定一个等价类 属于 的 条件概率可定义为 。 注： | · | 表示集合的基数。 Dj Dj ⊆ U 0 ⩽ β < α ⩽ 1 定义 2 设 为论域 U 的子集，即 ，给 定一对阈值 (α，β)，并且满足 ，则 (α，β)- 正域、负域和边界域可以定义为 POS(α,•)(Dj) = {x ∈ U|Pr(Dj |[x]) ⩾ α} NEG(•, β)(Dj) = {x ∈ U|Pr(Dj |[x]) ⩽ β} BND(α, β)(Dj) = {x ∈ U|β < Pr(Dj |[x]) < α} 通过定义 2 中的 (α，β)-正域、负域和边界域， 可分别生成相应的接受、拒绝和延迟决策规则。 1.2 三支决策在线快速计算模型 滑动窗口技术[27-28]可以有效处理动态流数据 下的数据挖掘与知识更新问题。在线计算的动态 特点是，随着新数据不断进入，同时由于内存空 间的限制，旧数据也被不断被删除，内存中包含 的计算数据既增又减。由此，三支决策在线计算 的数据变化模式可以用滑动窗口的方式进行描述。 IS(t) = { U (t) ,C (t) ∪ D (t) } U (t) /C (t) = { R1 (t) ,R2 (t) ,R3 (t) ,··· ,Rm (t) } U (t) /D (t) = { D1 (t) ,D2 (t) ,D3 (t) ,··· ,Dn (t) } 给 定 t 时刻的决策信息系统表： ，其中 ， 。将决策表空间 看作内存空间，即当前决策表中为内存中实时计 算的数据。当 t+1 时刻有新的数据对象动态进出 决策表时，内存空间发生数据动态变化，其变化 机制如下。 ·742· 智 能 系 统 学 报 第 13 卷
第5期 徐健锋，等：概率粗糙集三支决策在线快速计算算法研究 ·743· 设1时刻内存滑动窗口如图l(a)所示，其中 2三支决策在线快速计算方法 粗实线框（即x,x+1,…,k+数据对象）为当前t时 刻内存滑动窗口空间，长度为k虚线框（即x,2,…, 上述模型实现了动态流数据在线计算的动态 x数据对象)为历史遗弃数据；细实线框（即 变化机制。在经典计算中，对于信息系统的每一 k+2,+k3,…数据对象)为待移入内存数据。如 次数据更新，采用等价类的重新划分与计算，开 销较大。基于内存滑动窗口的三支决策动态变化 图1(b)所示，+1时刻单个对象4k+2(图中上三角 情况需要借鉴增量学习的思想，对于移入移出数 标识)移入内存滑动窗口中，同时前一时刻最陈 据进行同步处理，从而能够加快三支决策在线计 旧的决策对象x-(图中下三角标识)被移出，内存 算状态下条件概率与三支区域的更新速度，保证 滑动窗口发生更新。 了动态三支决策更新的实时性与高效性。 2.1条件概率快速估计方法 (a)1时刻内存滑动窗口 如何利用已有的决策知识，实现条件概率的 动态估计是基于三支决策知识更新的基础。 又 由定义2可知，计算概率粗糙集三支决策的 △ 原理是：首先计算每条决策规则的条件概率，然 二 动态数据流方向三 后将每条决策规则的条件概率与三支决策阈值 (b)+1时刻内存滑动窗口 《、B进行比较，然后才能确定每个条件等价类属 图1在线计算内存数据变化机制模型 于哪个三支决策区域。可见，每条决策规则的条件 Fig.1 Sliding windows online computing model on 概率计算，是概率粗糙集三支决策的关键步骤。 memory data 定理1给定1时刻信息系统IS={U,C0UD, 基于三支决策理论以及上述在线内存数据变 什1时刻信息系统更新为IS+={U+,C+UD, 化模型，可以获取如下动态单对象三支决策在线 在此期间，基于内存滑动窗口机制，移入单数据 内存计算变化模型。 对象x,同时移出单数据对象x,当动态数据对象 给定+1时刻决策表IS),当有新数据对象 符合以下变化模式时，条件概率呈增大趋势，即 集移入，同时必然有旧数据对象集{移出，则 Pr(D+R,)>Pr(D,0RO)。 更新后的决策信息系统中条件等价类和决策类可 变化模式1：(CER+”AT生D+)(xERx年D) 能分别发生如下变化： 变化模式2：(GER+”AT∈DA(XERAxEDO) R4)= ((xeRAxD) /R-{,(,9eR+",(x,闭生R,1≤i≤m 变化模式3：(ERDAIED)A{(x∈AIE D) (xROAxED) R9U,(x,ER+,(x,eR+,1≤i≤m 证明若移入对象及移出对象x满足变化模 R9U{-{,(x,)∈R”,(x,eR+,1≤i≤m 式1，则有R+=R-x,D+”=D9。根据定义1及给定 R”,(x)生R,(x)ERw,1≤i≤m 1+1时刻决策表IS+的数据变化公式(1)和(2)， (1) D4”= 可推断出t+1时刻条件概率Pr(DR)更新为 D9-,(x,eD+,(x,xED,1≤j≤n D DRD D)n(R”-xW Pr(D,+R,+)= D0U,(x,)∈D,(x,xED,1≤j≤n IR+D R”-{x D,U-{,x,刀eD+",(x,)eD”,1≤j≤n D)(R" D9,(x,ED”,(x,)生D”,1≤j≤n =Pr(D,R,) R1-1 1R7 (2) 其余变化模式的证明过程与变化模式1类 可见，决策信息系统在动态环境中，伴随着数 似，在此省略。 据对象在内存窗口的移入移出变化，必然会导致 定理2给定1时刻信息系统S0={U0,CwUD, 相关条件分类与决策分类发生相应变化，其条件 什1时刻信息系统更新为IS+)={U+,C+UD, 概率及三支区域必然也会发生变化。本文首先系 在此期间，基于动态流数据滑动窗口机制，移入 统地讨论在线数据的动态变化情况下条件概率及 单数据对象x,同时移出单数据对象x,当流数据 三支区域的变化，并以此为基础提出三支决策在 对象符合以下变化模式时，条件概率呈减小趋 线快速计算算法。 势，即Pr(D,R,+)<Pr(D,R)
xi , xi+1,··· , xi+k+1 x1, x2,··· , xi−1 xi+k+2, xi+k+3,··· xi+k+2 xi−1 设 t 时刻内存滑动窗口如图 1(a) 所示，其中 粗实线框 (即 数据对象) 为当前 t 时 刻内存滑动窗口空间，长度为 k；虚线框 (即 数据对象 ) 为历史遗弃数据；细实线 框 (即 数据对象) 为待移入内存数据。如 图 1(b) 所示，t+1 时刻单个对象 (图中上三角 标识) 移入内存滑动窗口中，同时前一时刻最陈 旧的决策对象 (图中下三角标识) 被移出，内存 滑动窗口发生更新。 x1 x2 ... xi−1 xi xi+1 xi+2 ... xi+k xi+k+1 xi+k+2 xi+k+3 ... (a) t 时刻内存滑动窗口 x1 x2 ... xi−1 xi xi+1 xi+2 ... xi+k xi+k+1 xi+k+2 xi+k+3 ... (b) t+1 时刻内存滑动窗口 动态数据流方向 图 1 在线计算内存数据变化机制模型 Fig. 1 Sliding windows online computing model on memory data 基于三支决策理论以及上述在线内存数据变 化模型，可以获取如下动态单对象三支决策在线 内存计算变化模型。 IS(t+1) {x} {x} 给定 t+1 时刻决策表 ，当有新数据对象 集 移入，同时必然有旧数据对象集 移出，则 更新后的决策信息系统中条件等价类和决策类可 能分别发生如下变化： R (t+1) i = R (t) i − {x}, (x, x) ∈ R (t+1) i , (x, x) < R (t+1) i , 1 ⩽ i ⩽ m R (t) i ∪ {x}, (x, x) < R (t+1) i , (x, x) ∈ R (t+1) i , 1 ⩽ i ⩽ m R (t) i ∪ {x} − {x}, (x, x) ∈ R (t+1) i , (x, x) ∈ R (t+1) i , 1 ⩽ i ⩽ m R (t) i , (x, x) < R (t+1) i , (x, x) < R (t+1) i , 1 ⩽ i ⩽ m (1) D (t+1) j = D (t) j − {x}, (x, x) ∈ D (t+1) j , (x, x) < D (t+1) j , 1 ⩽ j ⩽ n Dj (t) ∪ {x}, (x, x) ∈ D (t+1) j , (x, x) < D (t+1) j , 1 ⩽ j ⩽ n Dj (t) ∪ {x¯} − {x}, (x, x) ∈ D (t+1) j , (x, x) ∈ D (t+1) j , 1 ⩽ j ⩽ n Dj (t) , (x, x) < D (t+1) j , (x, x) < D (t+1) j , 1 ⩽ j ⩽ n (2) 可见，决策信息系统在动态环境中，伴随着数 据对象在内存窗口的移入移出变化，必然会导致 相关条件分类与决策分类发生相应变化，其条件 概率及三支区域必然也会发生变化。本文首先系 统地讨论在线数据的动态变化情况下条件概率及 三支区域的变化，并以此为基础提出三支决策在 线快速计算算法。 2 三支决策在线快速计算方法 上述模型实现了动态流数据在线计算的动态 变化机制。在经典计算中，对于信息系统的每一 次数据更新，采用等价类的重新划分与计算，开 销较大。基于内存滑动窗口的三支决策动态变化 情况需要借鉴增量学习的思想，对于移入移出数 据进行同步处理，从而能够加快三支决策在线计 算状态下条件概率与三支区域的更新速度，保证 了动态三支决策更新的实时性与高效性。 2.1 条件概率快速估计方法 如何利用已有的决策知识，实现条件概率的 动态估计是基于三支决策知识更新的基础。 由定义 2 可知，计算概率粗糙集三支决策的 原理是：首先计算每条决策规则的条件概率，然 后将每条决策规则的条件概率与三支决策阈值 α、β 进行比较，然后才能确定每个条件等价类属 于哪个三支决策区域。可见，每条决策规则的条件 概率计算，是概率粗糙集三支决策的关键步骤。 IS(t) = { U (t) ,C (t) ∪ D (t) } IS(t+1) = { U (t+1) ,C (t+1) ∪ D (t+1)} x x Pr(Dj (t+1) Ri (t+1) ) > Pr(Dj (t) Ri (t) ) 定理 1 给定 t 时刻信息系统 ， t+1 时刻信息系统更新为 ， 在此期间，基于内存滑动窗口机制，移入单数据 对象 ，同时移出单数据对象 ，当动态数据对象 符合以下变化模式时，条件概率呈增大趋势，即 。 (x<R (t+1) i ∧x<D (t+1) j )∧(x∈R (t) i ∧x < D (t) j 变化模式 1： ) (x<R (t+1) i ∧x∈D (t+1) j )∧(x∈R (t) i ∧x<D (t) j 变化模式 2： ) (x ∈ R (t+1) i ∧x∈D (t+1) j )∧ (x<R (t) i ∧x<D (t) j ) (x∈R (t) i ∧x<D (t) j ) (x<R (t) i ∧x∈D (t) j ) 变化模式3： x x R (t+1) i = R (t) i −{x},D (t+1) j = D (t) j IS(t+1) t+1 Pr(Dj (t+1) Ri (t+1) ) 证明 若移入对象 及移出对象 满足变化模 式1，则有 。根据定义1及给定 t + 1 时刻决策表 的数据变化公式 (1) 和 (2)， 可推断出 时刻条件概率 更新为 Pr(Dj (t+1) Ri (t+1) ) = Dj (t+1) ∩Ri (t+1) |Ri (t+1)| = (D (t) j )∩(R (t) i − x}) R (t) i − {x} = (D (t) j )∩(R (t) i ) |R (t) i | −1 > D (t) j ∩R (t) i |R (t) i | = Pr(Dj (t) Ri (t) ) 其余变化模式的证明过程与变化模式 1 类 似，在此省略。 IS(t) = { U (t) ,C (t) ∪ D (t) } IS(t+1) = { U (t+1) ,C (t+1) ∪ D (t+1)} x x Pr(Dj (t+1) Ri (t+1) ) < Pr(Dj (t) Ri (t) ) 定理 2 给定t时刻信息系统 ， t+1 时刻信息系统更新为 ， 在此期间，基于动态流数据滑动窗口机制，移入 单数据对象 ，同时移出单数据对象 ，当流数据 对象符合以下变化模式时，条件概率呈减小趋 势，即 。 第 5 期 徐健锋，等：概率粗糙集三支决策在线快速计算算法研究 ·743·
·744· 智能系统学报 第13卷 变化模式4：(G使R+ATED+)A(x∈R”AxED 线计算，进而使得三支决策区域的在线更新成为 变化模式5：(eRIMATED)(x∈R°AxED) 可能。 区ER”AxED) 2.2三支决策区域在线更新方法 变化模式6：(ER+AFED件)A{x使RPAIED) 三支决策的在线快速计算，即充分利用1时 x∈RAx∈D) 刻信息系统的获取的三支决策知识以及+1时刻 证明若移入对象及移出对象x遵循变化模 变化数据的动态变化信息，快速且准确地计算三 式4，则有R+=R”-{x,D+”=D-{s。根据定 支决策的区域变化。其计算的原理是根据2.1节 义1及给定t+1时刻决策表IS+)的数据变化公 定理1~3获得的各个决策规则的条件概率变化趋 式(1)、(2)，可推断出t+1时刻条件概率Pr(D,+1 势及特定条件概率取值，推导出三支决策区域在 R,4)更新为 +1时刻的变化规律。 DDRD 推论1给定1时刻信息系统S={U0,CUD) P(D+R+)= IR (1 和1什1时刻信息系统IS+)={U,C+UD+,若 kD-n(R-{ 定理1描述的变化模式成立，三支决策区域更新 R- 如下： POS(.(D)-R9URt”,p1 DP0R-1 DPoR =Pr(D,0R0) 1)POS(D)=POS(D)UR P2 1R91-1 IROI POS(D)UR Ps 其余变化模式的证明过程与变化模式4类 其中 似，在此省略。 定理3给定1时刻信息系统S0={U,C0UD, P:RPOS(D) 什1时刻信息系统更新为IS+)={U),C+DUD, P2:R9 C BND(D)APr(D件R+)≥a 在此期间，基于动态流数据滑动窗口机制，移入 P3:R CNEG(D)APr(DDR)>a 单数据对象无，同时移出单数据对象x,当流数据 (BNDm(D()-R,b 对象符合变化模式5~8时，条件概率保持不变，即 2)BND(D)=BNDm(D()-R4URD),b2 Pr(D,DR,(D)=Pr(D R,). BND((D)URD),b3 变化模式5：G在R”AED件)A{ (xeROAxED) 其中 ER”Ax∈D) 区RAxD) b:R C BND(D()A Pr(DD RD)a 变化模式6：（仅RATED)A xER"Ax∈D b2:RCBND(D)AB<Pr(DR)<a 变化模式7：(TERMATED件)A(XERDAX生D) b3 RCNEG(D)AB<Pr(DR)<a 变化模式8：(ERMDATED)A(xER”Ax∈D) (NEG((D)-R,n 证明若移入对象及移出对象x遵循变化模 3)NEG(D)=NEG(D)-R n 式5：C使R”A元生DA(区使R9Ax使D),则有 NEG(D)-RURD,ns RW=RAD=D9。根据定义1及给定1+1 其中 时刻决策表S+的数据变化公式(1)和公式(2)， m:R”CNEG(DAPr(DtR)≥a 可推断出t+1时刻条件概率Pr(D+R+”)更新为 n2 R C BND(D)AB<Pr(DDRD)<a Pr(DR)=IDR n3:RCNEG(D)A Pr(DR)B R+] 证明1)对于POSa(D (DR =Pr(D,(R,) IR ①假设p1:RCPOS(D)成立，由定义2得 其余变化模式的证明过程与变化模式5类 Pr(DR)>a。由定理1可知Pr(DR)> 似，在此省略。通过定理13可知，随着决策系统 P(DR)>a,即DC POS(D,则接受域更 中数据对象同步移入移出的更新，原有决策规则 新为POSa(D+)=POS(D)-R”UR+。 的条件概率的变化趋势可以通过局部更新数据 ②假设p2:RC BNDA(D)APr(D+R+≥a 的计算进行快速估计。这样既避免了原有数据对 成立，由定义2得B<PDR)<a。因为 象的重复学习，又利用同步更新大大提高了条件 Pr(DR+≥a,即RDPOS(D+),则接受域 概率的计算效率，实现了三支决策条件概率的在 更新为POS(D+=POSa(D)UR+
(x<R (t+1) i ∧x<D (t+1) j )∧(x∈R (t) i ∧x∈D (t) j 变化模式 4： ) (x<R (t+1) i ∧x∈D (t+1) j )∧(x∈R (t) i ∧x∈D (t) j 变化模式 5： ) (x∈R (t+1) i ∧x<D (t+1) j )∧ (x<R (t) i ∧x<D (t) j ) (x<R (t) i ∧x∈D (t) j ) (x∈R (t) i ∧x∈D (t) j ) 变化模式 6： x x R (t+1) i = R (t) i − {x},D (t+1) j = D (t) j − {x} t+1 IS(t+1) t+1 Pr(Dj (t+1)| Ri (t+1)) 证明 若移入对象 及移出对象 遵循变化模 式 4，则有 。根据定 义 1 及给定 时刻决策表 的数据变化公 式 (1)、(2)，可推断出 时刻条件概率 更新为 Pr(Dj (t+1) Ri (t+1) ) = Dj (t+1) ∩Ri (t+1) |Ri (t+1)| = (D (t) j − { x } )∩(R (t) i − { x } ) R (t) i − { x } = D (t) j ∩R (t) i −1 |R (t) i | −1 < D (t) j ∩R (t) i |R (t) i | = Pr(Dj (t) Ri (t) ) 其余变化模式的证明过程与变化模式 4 类 似，在此省略。 IS(t) = { U (t) ,C (t) ∪ D (t) } IS(t+1) = { U (t+1) ,C (t+1) ∪ D (t+1)} x x Pr(Dj (t+1) Ri (t+1) ) = Pr(Dj (t) Ri (t) ) 定理3 给定t时刻信息系统 ， t+1 时刻信息系统更新为 ， 在此期间，基于动态流数据滑动窗口机制，移入 单数据对象 ，同时移出单数据对象 ，当流数据 对象符合变化模式 5~8 时，条件概率保持不变，即 。 (x<R (t+1) i ∧x<D (t+1) j )∧ (x<R (t) i ∧x<D (t) j ) (x<R (t) i ∧x∈D (t) j ) 变化模式 5： (x<R (t+1) i ∧x∈D (t+1) j )∧ (x<R (t) i ∧x<D (t) j ) (x<R (t) i ∧x∈D (t) j ) 变化模式 6： (x∈R (t+1) i ∧x<D (t+1) j )∧(x∈R (t) i ∧x<D (t) j 变化模式 7： ) (x∈R (t+1) i ∧x∈D (t+1) j )∧(x∈R (t) i ∧x∈D (t) j 变化模式 8： ) x x (x < R (t+1) i ∧ x < D (t+1) j )∧(x < R (t) i ∧ x < D (t) j ) R (t+1) i = R (t) i ∧ D (t+1) j = D (t) j t+1 IS(t+1) t+1 Pr(Dj (t+1) Ri (t+1) ) 证明 若移入对象 及移出对象 遵循变化模 式 5 ： ，则有 。根据定 义 1 及给定 时刻决策表 的数据变化公式 (1) 和公式 (2)， 可推断出 时刻条件概率 更新为 Pr(Dj (t+1) Ri (t+1) ) = |Dj (t+1) ∩Ri (t+1)| |Ri (t+1)| = |(D (t) j ∩R (t) i )| |R (t) i | = Pr(Dj (t) Ri (t) ) 其余变化模式的证明过程与变化模式 5 类 似，在此省略。通过定理 1~3 可知，随着决策系统 中数据对象同步移入移出的更新，原有决策规则 的条件概率的变化趋势可以通过局部更新数据 的计算进行快速估计。这样既避免了原有数据对 象的重复学习，又利用同步更新大大提高了条件 概率的计算效率，实现了三支决策条件概率的在 线计算，进而使得三支决策区域的在线更新成为 可能。 2.2 三支决策区域在线更新方法 三支决策的在线快速计算，即充分利用 t 时 刻信息系统的获取的三支决策知识以及 t+1 时刻 变化数据的动态变化信息，快速且准确地计算三 支决策的区域变化。其计算的原理是根据 2.1 节 定理 1~3 获得的各个决策规则的条件概率变化趋 势及特定条件概率取值，推导出三支决策区域在 t+1 时刻的变化规律。 IS(t) = { U (t) ,C (t) ∪ D (t) } IS(t+1) = { U (t+1) ,C (t+1) ∪ D (t+1)} 推论1 给定t 时刻信息系统 和 t+1 时刻信息系统 ，若 定理 1 描述的变化模式成立，三支决策区域更新 如下： 1) POS(α,β)(D (t+1) j ) = POS(α,β)(D (t) j )−R (t) i ∪R (t+1) i , p1 POS(α,β)(D (t) j )∪R (t+1) i , p2 POS(α,β)(D (t) j )∪R (t+1) i , p3 p1 : R (t) i ⊆ POS(α,β)(D (t) j ) p2 : R (t) i ⊆ BND(α,β)(D (t) j )∧Pr(D (t+1) j |R (t+1) i ) ⩾ α p3 : R (t) i ⊆ NEG(α,β)(D (t) j )∧Pr(D (t+1) j |R (t+1) i ) ⩾ α 其中 2) BND(α,β)(D (t+1) j ) = BND(α,β)(D (t) j )−R (t) i , b1 BND(α,β)(D (t) j )−R (t) i ∪R (t+1) i , b2 BND(α,β)(D (t) j )∪R (t+1) i , b3 b1 : R (t) i ⊆ BND(α,β)(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 ⊆ NEG(α,β)(D (t) j )∧β < Pr(D (t+1) j |R (t+1) i ) < α 其中 3) NEG(α,β)(D (t+1) j ) = NEG(α,β)(D (t) j )−R (t) 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 ⊆ NEG(α,β)(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 )∧Pr(D (t+1) j |R (t+1) i ) ⩽ β 其中 POS(α,β)(D (t+1) j 证明 1) 对于 ) p1 : R (t) i ⊆ POS(α,β)(D (t) j ) Pr(D (t) j |R (t) i ) > α Pr(D (t+1) j |R (t+1) i ) > Pr(D (t) j |R (t) i ) > α R (t+1) i ⊆ POS(α,β)(D (t+1) j ) POS(α,β)(D (t+1) j ) =POS(α,β)(D (t) j )−R (t) i ∪R (t+1) i ①假设 成立，由定义 2 得 。由定 理 1 可 知 ，即 ，则接受域更 新为 。 p2 : 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+1) j ) POS(α,β)(D (t+1) j ) =POS(α,β)(D (t) j )∪R (t+1) i ②假设 成立，由定 义 2 得 。因为 ，即 ，则接受域 更新为 。 ·744· 智 能 系 统 学 报 第 13 卷
第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 种情形展开讨论。 本节设计了三支决策在线快速计算算法 (online 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·