【机器学习】概率粗糙集三支决策在线快速计算算法研究

第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 de￾cisions 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 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 随着大数据与互联网加时代的到来，动态流 数据成为了一种主流的数据类型，当前已经被广 泛地应用于金融股票交易、天气和环境监测、计 算机网络监控等众多领域[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) Pr(Dj (t)   Ri (t) ) 定理 1 给定 t 时刻信息系统 ， t+1 时刻信息系统更新为 ， 在此期间，基于内存滑动窗口机制，移入单数据 对象 ，同时移出单数据对象 ，当动态数据对象 符合以下变化模式时，条件概率呈增大趋势，即 。 (x    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)ABa。由定理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 α 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 种情形展开讨论。 本节设计了三支决策在线快速计算算法 (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·

·746· 智能系统学报 第13卷 4)更新1+1时刻每个等价类的条件概率值 假设原1时刻信息系统为IS”,新增对象集为 Pr(DR+及条件、决策等价类R+)、D+,返回I)o ,上述两种算法的时间复杂度分别为： 在线快速计算中，若给定内存部分信息系统 经典计算算法： IS,包含m个条件等价类和n个决策等价类，其中 OIU/A·A+DD+O2 U/AI-IDD m=IUo1A(UosU),n=DL,等价类的计算时间复 在线快速计算： 杂度为O(UA4+DD。步骤2)评估条件概率 O(IU/AI-IAI+IDD+O(IRI+IR,D 变化趋势，其时间复杂度为O1),这时可以忽略不 从时间复杂度分析可知，在线快速计算的效 计的。步骤3)为更新三支区域，即区域内的对象 率明显优于经典计算算法。从算法执行过程亦可 可能发生转移，区域未发生变化是最好的情况， 看出，由于经典计算算法对于决策对象的每一次 在这种情况下两种算法的时间复杂度均可视为 更新，都进行等价类划分和条件概率的重新计 01):最坏的情况，此算法中需要转移对象两次， 算，其开销甚是庞大：而在线计算利用内存滑动 以R和R表示移人对象x和被移出对象x的条件 窗口模型，同步处理移入移出数据，对当前实时 和决策等价类，则区域更新的时间复杂度为 变化的数据进行局部计算，实现条件概率及三支 OR+RD。步骤4)中，在R和D已知的情况 区域的快速估计与更新，其运算效率明显高于经 下，重新计算条件概率的时间复杂度几乎是可以 典计算算法。 忽略不计的。综上，在线快速计算的时间复杂度 综上，从理论分析可知在线快速计算的运行 为O0Uo/AA+D+OR+RD。 效率明显优于经典计算算法。接下来，我们将从 为了说明上述在线三支决策算法的特点与优 势，本文将根据文献[22]中提出的基于概率粗糙 实验的角度评估两算法的实际表现。 集三支决策理论的经典计算思想，设计三支决策 3实验与结果 经典计算算法(classical computing algorithm)。 算法2基于三支决策的经典计算算法 2.3节通过理论证明了三支决策在线快速计 输入1时刻下信息系统IS={U,CUD, 算算法的时间复杂度优于经典计算算法。本章将 条件等价类和决策等价类R”、Di=1,2,…,m:j=1, 通过与三支决策经典计算算法的对比实验来验证 2,…,n,条件概率Pr(DR)i=1,2,…,m;j=1,2,…, 三支决策在线快速计算算法的时间消耗优势。 n),三支决策接受域、拒绝域和边界域POS(D)、 本实验环境为：双核、4GB内存的PC,运行 BNDa(D、NEGa(D"),新增决策对象x及被移 Microsoft Windows7操作系统，算法程序使用 出对象x,三支决策阈值(a,)。 Java编程，Java开发包为JDKl.6版本。 输出什1时刻的三支决策区域及决策规则 3.1数据集 POSa(D+)、BNDa(D牛)和NEG(8()D件。 为了验证在线快速计算的性能，我们从 /体根据移入对象x、移出对象x进行三支决策 UCI数据库中选择了8个较大数据集，分别为 更新计算*/ Skin-NoSkin、Shuttle、IRIS、Zoo、Haberman、Breast- 1)通过x和x的等价类从属关系，更新什1时 cancer、Letter、Magic.,所有的数据均为数值型或类 刻的条件等价类和决策等价类R和D, 别型，表1为数据集的基本信息。 2)根据定义1重新计算1+1时刻条件概率 表1数据集基本信息 Pr(DIR值； Table 1 The basic information of the eight datasets 3)根据定义2重新计算什1时刻三支决策接 序号 数据集 样本数 特征数 概念计数 受域、拒绝域和边界域POSm(D+、BNDa(D+), 1 Skin NoSkin 64486 2 NEG(D+。 Shuttle 58000 9 经典计算算法中，若给定内存部分信息系统 IRIS IS,包含m个条件等价类和n个决策等价类，其中 60750 3 m=IUo1A(Uo≤U),n=ID,等价类的计算时间复 Z00 60600 17 7 杂度为O(UA·4+DD;重新计算条件概率的时 5 Haberman 55080 3 2 间复杂度为O(U/A·DD;根据条件概率大小与阈 6 Breast-cancer 60860 10 4 值的比较，更新三支区域的时间复杂度亦为 7 Letter 20000 16 12 O(U/A·DD。因此，经典计算算法的时间复杂度 8 为OIUo/A·4+1DD+O(2IU9/ADD. Magic 19020 10 2

Pr(D (t+1) j |R (t+1) i ) R (t+1) D (t+1) 4) 更新 t+1 时刻每个等价类的条件概率值 及条件、决策等价类 、 ，返回 1)。 m = |U (t) /A|(U (t) ⊆ U) n = |D| O(|U (t) /A| · |A|+|D|) O(1) O(1)|Ri | |Rj | x x O(|Ri |+|Rj |) |Ri | |Dj | O(|U (t) /A| · |A|+|D|)+O(|Ri |+|Rj |) 在线快速计算中，若给定内存部分信息系统 IS，包含 m 个条件等价类和 n 个决策等价类，其中 ， ，等价类的计算时间复 杂度为 。步骤 2) 评估条件概率 变化趋势，其时间复杂度为 ，这时可以忽略不 计的。步骤 3) 为更新三支区域，即区域内的对象 可能发生转移，区域未发生变化是最好的情况， 在这种情况下两种算法的时间复杂度均可视为 ；最坏的情况，此算法中需要转移对象两次， 以 和 表示移入对象 和被移出对象 的条件 和决策等价类，则区域更新的时间复杂度为 。步骤 4) 中，在 和 已知的情况 下，重新计算条件概率的时间复杂度几乎是可以 忽略不计的。综上，在线快速计算的时间复杂度 为 。 为了说明上述在线三支决策算法的特点与优 势，本文将根据文献[22]中提出的基于概率粗糙 集三支决策理论的经典计算思想，设计三支决策 经典计算算法 (classical computing algorithm)。 算法 2 基于三支决策的经典计算算法 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,··· , POS(α,β)(D (t) j ) BND(α,β)(D (t) j ) NEG(α,β)(D (t) j ) x x 输入 t 时刻下信息系统 ， 条件等价类和决策等价类 、 ，条件概率 n)，三支决策接受域、拒绝域和边界域 、 、 ，新增决策对象 及被移 出对象 ，三支决策阈值 (α，β)。 POS(α,β)(D (t+1) j ) BND(α,β)(D (t+1) j ) NEG(α,β)(D (t+1) j ) 输出 t+1 时刻的三支决策区域及决策规则 、 和 。 /* 根据移入对象 x、移出对象 x进行三支决策 更新计算*/ x x R (t+1) i D (t+1) j 1) 通过 和 的等价类从属关系，更新 t+1 时 刻的条件等价类和决策等价类 和 ; Pr(D (t+1) j |R (t+1) i ) 2) 根据定义 1 重新计算 t+1 时刻条件概率 值; POS(α,β)(D (t+1) j ) BND(α,β)(D (t+1) j ) NEG(α,β)(D (t+1) j ) 3) 根据定义 2 重新计算 t+1 时刻三支决策接 受域、拒绝域和边界域 、 ， 。 m = |U (t) /A|(U (t) ⊆ U) n = |D| O(|U (t) /A| · |A|+|D|) O(|U (t) /A| · |D|) O(|U (t) /A| · |D|) O(|U (t) /A| · |A|+|D|)+O(2|U (t) /A| · |D|) 经典计算算法中，若给定内存部分信息系统 IS，包含 m 个条件等价类和 n 个决策等价类，其中 ， ，等价类的计算时间复 杂度为 ；重新计算条件概率的时 间复杂度为 ；根据条件概率大小与阈 值的比较，更新三支区域的时间复杂度亦为 。因此，经典计算算法的时间复杂度 为 。 IS(t) {x} 假设原 t 时刻信息系统为 ，新增对象集为 ，上述两种算法的时间复杂度分别为： 经典计算算法： O(|U (t) /A| · |A|+|D|)+O(2|U (t) /A| · |D|) 在线快速计算： O(|U (t) /A| · |A|+|D|)+O(|Ri |+|Rj |) 从时间复杂度分析可知，在线快速计算的效 率明显优于经典计算算法。从算法执行过程亦可 看出，由于经典计算算法对于决策对象的每一次 更新，都进行等价类划分和条件概率的重新计 算，其开销甚是庞大；而在线计算利用内存滑动 窗口模型，同步处理移入移出数据，对当前实时 变化的数据进行局部计算，实现条件概率及三支 区域的快速估计与更新，其运算效率明显高于经 典计算算法。 综上，从理论分析可知在线快速计算的运行 效率明显优于经典计算算法。接下来，我们将从 实验的角度评估两算法的实际表现。 3 实验与结果 2.3 节通过理论证明了三支决策在线快速计 算算法的时间复杂度优于经典计算算法。本章将 通过与三支决策经典计算算法的对比实验来验证 三支决策在线快速计算算法的时间消耗优势。 本实验环境为：双核、4 GB 内存的 PC，运行 Microsoft Windows 7 操作系统，算法程序使用 Java 编程，Java 开发包为 JDK1.6 版本。 3.1 数据集 为了验证在线快速计算的性能，我们 从 UCI 数据库中选择了 8 个较大数据集，分别为 Skin-NoSkin、Shuttle、IRIS、Zoo、Haberman、Breast￾cancer、Letter、Magic，所有的数据均为数值型或类 别型，表 1 为数据集的基本信息。 表 1 数据集基本信息 Table 1 The basic information of the eight datasets 序号 数据集 样本数 特征数 概念计数 1 Skin_NoSkin 64 486 3 2 2 Shuttle 58 000 9 5 3 IRIS 60 750 8 3 4 Zoo 60 600 17 7 5 Haberman 55 080 3 2 6 Breast-cancer 60 860 10 4 7 Letter 20 000 16 12 8 Magic 19 020 10 2 ·746· 智 能 系 统 学 报 第 13 卷

第5期 徐健锋，等：概率粗糙集三支决策在线快速计算算法研究 ·747· 3.2 实验和结果 在线快速计算、经典计算算法的性能时，逐渐增 为排除偶然因素的影响，所有实验都进行了 加上述8个数据集在内存中存储数据的比例。当 10次，最终结果是10次实验的平均值。我们任 进入决策信息系统的在线计算数据总量累计达到 意设定的三支决策阈值（α，B)为(0.75,0.3）。 总数据量的10%~100%时，分别测试不同情况下， 1)算法执行时间对比实验 两种算法在三支决策区域更新中的平均执行时 假设存储空间保持为100条记录，我们比较 间。实验结果如图2所示。 15x10 12*10 经典计算 一经典计算 +在线计算 10 士一在线计算 6 ● ■ 0 ◆ 102030405060708090100 102030405060708090100 流数据规模% 流数据规模% (a)Skin NoSkin (b)Shuttle 14*10 14*10 。经典计算 12 。一经典计算 在线计算 。在线计算 10 8 6 6 2 0 102030.405060708090100 102030405060708090100 流数据规模% 流数据规模% (c)IRIS (d)Zoo 10*10 2*10 一经典计算 一经典计算 8 。在线计算 10 ·在线计算 6 6 4 ■ 0 102030405060708090100 102030405060708090100 流数据规模% 流数据规模% (e)Haberman (f)Breast-cancer 30*10 ×10 5 。一经典计算 。一经典计算 25 ·在线计算 +在线计算 20 3 ◆ o 2 ■ 5 0 本本★★李 0 102030405060708090100 102030405060708090100 流数据规模% 流数据规模% (g)Letter (h)Magic 图2在线快速计算与经典计算算法的平均时间消耗对比 Fig.2 Average elapsed times between online computing algorithm and classical computing algorithm 由图2显然可以看出，在每个数据集下，随着 与经典计算算法的平均执行时间亦逐渐增大，但 进人内存中动态数据比例的增大，在线快速计算 经典计算算法的增幅明显更大。可见，在线快速

3.2 实验和结果 (α, β) 为排除偶然因素的影响，所有实验都进行了 10 次，最终结果是 10 次实验的平均值。我们任 意设定的三支决策阈值 为 (0.75，0.3)。 1) 算法执行时间对比实验 假设存储空间保持为 100 条记录，我们比较 在线快速计算、经典计算算法的性能时，逐渐增 加上述 8 个数据集在内存中存储数据的比例。当 进入决策信息系统的在线计算数据总量累计达到 总数据量的 10%~100% 时，分别测试不同情况下， 两种算法在三支决策区域更新中的平均执行时 间。实验结果如图 2 所示。 由图 2 显然可以看出，在每个数据集下，随着 进入内存中动态数据比例的增大，在线快速计算 与经典计算算法的平均执行时间亦逐渐增大，但 经典计算算法的增幅明显更大。可见，在线快速 0 5 10 15 10 20 30 40 50 60 70 80 90 100 计算时间/s 流数据规模/% (a) Skin_NoSkin 经典计算 在线计算 10 20 30 40 50 60 70 80 90 100 计算时间/s 流数据规模/% (h) Magic 经典计算 在线计算 0 1 2 3 4 5 10 20 30 40 50 60 70 80 90 100 计算时间/s 流数据规模/% (g) Letter 经典计算 在线计算 0 5 10 15 20 25 30 0 2 4 6 8 12 10 20 30 40 50 60 70 80 90 100 计算时间/s 流数据规模/% (f) Breast-cancer 经典计算 10 在线计算 0 2 4 6 8 10 10 20 30 40 50 60 70 80 90 100 计算时间/s 流数据规模/% (e) Haberman 经典计算 在线计算 0 2 4 6 8 10 14 10 20 30 40 50 60 70 80 90 100 计算时间/s 流数据规模/% (d) Zoo 经典计算 在线计算 12 0 2 4 6 8 10 14 10 20 30 40 50 60 70 80 90 100 计算时间/s 流数据规模/% (c) IRIS 经典计算 在线计算 12 0 2 4 6 8 10 12 10 20 30 40 50 60 70 80 90 100 计算时间/s 流数据规模/% (b) Shuttle 经典计算 在线计算 ×104 ×104 ×104 ×104 ×103 ×104 图 2 在线快速计算与经典计算算法的平均时间消耗对比 Fig. 2 Average elapsed times between online computing algorithm and classical computing algorithm 第 5 期 徐健锋，等：概率粗糙集三支决策在线快速计算算法研究 ·747·

·748· 智能系统学报 第13卷 计算的平均执行时间相对更少。 均执行时间并对比其稳定性。结果见表2，单位 此外，为了更加精确地展现在线快速计算的 为s。可以观察到，对于同一数据集，对比经典 优势及其稳定性，我们将在占数据总量50%的 计算算法，在线快速计算可以大大节约算法执行 情况下，从1时刻到+5时刻，测试两类算法的平 时间。 表2t~什5时刻算法执行时间 Table 2 Experimental results examined from time tto +5 on UCI datasets ms 数据集 算法 +1 1+2 1什3 1+4 +5 平均值±标淮差 经典计算 2.280 1.860 1.890 1.770 1.740 1.800 1.890±0.007 Skin NoSkin 在线计算 0.055 0.043 0.040 0.039 0.039 0.038 0.042±0.006 经典计算 2.220 2.040 1.890 1.860 1.980 1.860 1.980±0.005 Shuttle 在线计算 0.063 0.046 0.045 0.043 0.041 0.039 0.046±0.009 经典计算 2.370 2.280 2.070 1.860 1.980 1.860 1.980±0.005 IRIS 在线计算 0.058 0.048 0.040 0.041 0.040 0.040 0.044±0.007 经典计算 2.340 1.920 2.100 1.800 1.770 1.800 1.950±0.008 Z00 在线计算 0.050 0.040 0.037 0.039 0.037 0.036 0.040±0.005 经典计算 1.950 1.620 1.500 1.500 1.440 1.500 1.590±0.006 Haberman 在线计算 0.043 0.034 0.038 0.031 0.030 0.029 0.034±0.005 经典计算 1.890 1.710 1.710 1.650 1.680 1.740 1.740±0.003 Breast-cancer 在线计算 0.044 0.036 0.034 0.033 0.031 0.032 0.035±0.005 经典计算 2.200 0.740 1.500 1.420 1.400 1.440 1.620±0.015 Letter 在线计算 0.079 0.074 0.058 0.052 0.051 0.049 0.061±0.013 经典计算 2.200 1.860 1.560 1.440 1.320 1.340 1.620±0.017 Magic 在线计算 0.071 0.059 0.053 0.041 0.039 0.043 0.053±0.012 同时，在不同数据集上，在线快速计算执行时 每次都需要执行时间复杂度为O(2IU/ADD的步 间的均值和方差比经典计算算法更小，显示了其 骤，其时间消耗极大，且与内存中的数据量及复 具有更好的效率及稳定性。 杂程度密切相关；而在线快速计算由于只需要对 2)不同内存容量算法执行时间对比 当前实时变化的数据对象进行局部计算，避免了 由于在线计算方法以内存计算为依托，内存 历史数据的重复学习，最多只需执行时间复杂度 空间的容量对于三支决策在线快速计算的执行效 为OU/A·DD的步骤，大大节省了此更新过程的 果是否有影响，是一个值得研究的问题。因此我 开销。 们选择以上8个UCI数据集中规模较大且复杂程 综上可知，在不同内存空间下，在线快速计算 度较高的Breast-.cancer数据集，构造和实验1相 的效率均远高于经典计算算法，且这一优势随着 似的对比实验，但是将内存容量分别为设定为 内存空间的增加更加明显。 100、500、1000、2000条记录，当上述数据集实施 3)不同阈值在线快速计算执行时间对比 两种算法实验的数据总量累计达到总数据量的 由于三支决策是一种典型的概率粗糙集参数 10%、40%、70%和100%时，分别记录这两种算法 化模型，实验结果可能会受参数设置的影响。设 此时的平均执行时间。 置内存空间为100b,并选取了5对阈值，分别测 由图3可以观察到，在相同实验数据累积量 出在线快速计算在8个数据集下执行完毕平均所 下，随着内存空间的增加，经典计算算法的平均 需时间，从而验证在线快速计算的性能与选取阈 执行时间几乎呈指数级速度增长，而在线快速计 值的关系。图4显示了算法平均执行时间随不同 算的时间消耗较为平稳。 阈值对的变化趋势，不难看出，算法的执行时间 由算法的时间复杂度可知，随着决策系统的 随着阈值的改变有轻微的波动，总体来说比较 每一次更新，经典计算算法需要进行所有数据等 稳定。由此也进一步验证了在线快速计算的时间 价类的重新划分及条件概率的重新计算，此过程 复杂度主要取决于动态数据的规模及其复杂程度

计算的平均执行时间相对更少。 此外，为了更加精确地展现在线快速计算的 优势及其稳定性，我们将在占数据总量 50% 的 情况下，从 t 时刻到 t+5 时刻，测试两类算法的平 均执行时间并对比其稳定性。结果见表 2，单位 为 ms。可以观察到，对于同一数据集，对比经典 计算算法，在线快速计算可以大大节约算法执行 时间。 同时，在不同数据集上，在线快速计算执行时 间的均值和方差比经典计算算法更小，显示了其 具有更好的效率及稳定性。 2) 不同内存容量算法执行时间对比 由于在线计算方法以内存计算为依托，内存 空间的容量对于三支决策在线快速计算的执行效 果是否有影响，是一个值得研究的问题。因此我 们选择以上 8 个 UCI 数据集中规模较大且复杂程 度较高的 Breast-cancer 数据集，构造和实验 1 相 似的对比实验，但是将内存容量分别为设定为 100、500、1 000、2 000 条记录，当上述数据集实施 两种算法实验的数据总量累计达到总数据量的 10%、40%、70% 和 100% 时，分别记录这两种算法 此时的平均执行时间。 由图 3 可以观察到，在相同实验数据累积量 下，随着内存空间的增加，经典计算算法的平均 执行时间几乎呈指数级速度增长，而在线快速计 算的时间消耗较为平稳。 由算法的时间复杂度可知，随着决策系统的 每一次更新，经典计算算法需要进行所有数据等 价类的重新划分及条件概率的重新计算，此过程 O(2|U (t) /A| · |D|) O(U(t) /A| · |D|) 每次都需要执行时间复杂度为 的步 骤，其时间消耗极大，且与内存中的数据量及复 杂程度密切相关；而在线快速计算由于只需要对 当前实时变化的数据对象进行局部计算，避免了 历史数据的重复学习，最多只需执行时间复杂度 为 的步骤，大大节省了此更新过程的 开销。 综上可知，在不同内存空间下，在线快速计算 的效率均远高于经典计算算法，且这一优势随着 内存空间的增加更加明显。 3) 不同阈值在线快速计算执行时间对比 由于三支决策是一种典型的概率粗糙集参数 化模型，实验结果可能会受参数设置的影响。设 置内存空间为 100 b，并选取了 5 对阈值，分别测 出在线快速计算在 8 个数据集下执行完毕平均所 需时间，从而验证在线快速计算的性能与选取阈 值的关系。图 4 显示了算法平均执行时间随不同 阈值对的变化趋势，不难看出，算法的执行时间 随着阈值的改变有轻微的波动，总体来说比较 稳定。由此也进一步验证了在线快速计算的时间 复杂度主要取决于动态数据的规模及其复杂程度。 表 2 t～t+5 时刻算法执行时间 Table 2 Experimental results examined from time t to t+5 on UCI datasets ms 数据集 算法 t t+1 t+2 t+3 t+4 t+5 平均值±标准差 Skin_NoSkin 经典计算 2.280 1.860 1.890 1.770 1.740 1.800 1.890±0.007 在线计算 0.055 0.043 0.040 0.039 0.039 0.038 0.042±0.006 Shuttle 经典计算 2.220 2.040 1.890 1.860 1.980 1.860 1.980±0.005 在线计算 0.063 0.046 0.045 0.043 0.041 0.039 0.046±0.009 IRIS 经典计算 2.370 2.280 2.070 1.860 1.980 1.860 1.980±0.005 在线计算 0.058 0.048 0.040 0.041 0.040 0.040 0.044±0.007 Zoo 经典计算 2.340 1.920 2.100 1.800 1.770 1.800 1.950±0.008 在线计算 0.050 0.040 0.037 0.039 0.037 0.036 0.040±0.005 Haberman 经典计算 1.950 1.620 1.500 1.500 1.440 1.500 1.590±0.006 在线计算 0.043 0.034 0.038 0.031 0.030 0.029 0.034±0.005 Breast-cancer 经典计算 1.890 1.710 1.710 1.650 1.680 1.740 1.740±0.003 在线计算 0.044 0.036 0.034 0.033 0.031 0.032 0.035±0.005 Letter 经典计算 2.200 0.740 1.500 1.420 1.400 1.440 1.620±0.015 在线计算 0.079 0.074 0.058 0.052 0.051 0.049 0.061±0.013 Magic 经典计算 2.200 1.860 1.560 1.440 1.320 1.340 1.620±0.017 在线计算 0.071 0.059 0.053 0.041 0.039 0.043 0.053±0.012 ·748· 智 能 系 统 学 报 第 13 卷

第5期 徐健锋，等：概率粗糙集三支决策在线快速计算算法研究 ·749· 30*10m ×105 ■一经典计算 6「。经典计算 2 女一在线计算 ·一在线计算 10 2 1 5 10 10 20*10 内存中数据量 内存中数据量 (a)流数据总量的10% (b)流数据总量的40% 20 ×10 ×10 ■一经典计算 30 ■一经典计算 士一在线计算 士一在线计算 o ×10 5 10 20 10 20*10 内存中数据量 内存中数据量 (c)流数据总量的70% (d流数据总量的100% 图3在线快速计算与经典计算算法在不同内存容量下的平均执行时间 Fig.3 Average elapsed times between online computing algorithm and classical computing algorithm on different memory sizes ◆Skin NoSkin -Shuttle 30*103 -∠00 -w-Haberman 计算比经典计算算法效率更高，稳定性更好。本 Letter -Magic ·IRIS --Breast-cancer 研究表明，概率粗糙集三支决策领域采用在线计 25 算方法进行快速计算是可行的。我们将在未来的 20 工作中，继续探讨概率粗糙集三支决策的多对象 动态在线快速计算以及其在实际在线计算场景中 本10 的应用。 参考文献： (0.60.4)(0.7,0.3)(0.80.2)(0.9,0.1)(10) [1]FONG S.WONG R.VASILAKOS A V.Accelerated PSO 阀值对 swarm search feature selection for data stream mining big 图4不同阈值对在线快速计算平均执行时间 data[J].IEEE transactions on services computing,2016, Fig.4 Average elapsed times on online computing al- 91:33-45 gorithm with different threshold pairs [2]ZHANG Hong,LI Bo,JIANG Hongbo,et al.A frame- work for truthful online auctions in cloud computing with 4结束语 heterogeneous user demands[C]//Proceedings of 2013 IEEE INFOCOM.Turin,Italy,2013:1510-1518 动态在线计算是一种常见的数据计算方法， [3]ESKANDARI S,JAVIDI MM.Online streaming feature 本文提出一种内存滑动窗口机制对在线计算的数 selection using rough sets[J].International journal of ap- 据变化模式进行统一建模，并根据上述模型，推 proximate reasoning,2016,69:35-57. 导出不同类型数据变化模式下的三支决策条件概 [4]CHAZELLE B,ROSENBERG B.The complexity of com- 率及三支区域的变化规律。最后本研究提出一种 puting partial sums off-line[J].International journal of 新型的动态在线快速计算算法，该算法能够获得 computational geometry and applications,1991,1(1): 与经典三支决策算法相同的决策结果。由于本算 33-45. 法只需要对当前的变化数据进行局部实时计算， [5]DENG Jie,QU Zhiguo,ZHU Yongxu,et al.Towards effi- cient and scalable data mining using spark[C]//Proceed- 有效避免了历史数据的重复学习，大大提高了三 ings of 2014 International Conference on Information and 支决策更新效率。为验证本文所提出的在线快速 Communications Technologies.Nanjing,China,2014:1-6. 计算的优势，与经典计算算法在8个UCI公共数 [6]YAO Yiyu.Three-way decisions and cognitive computing 据集上进行实验对比。实验结果表明，在线快速 [J].Cognitive computation,2016,8(4):543-554

4 结束语 动态在线计算是一种常见的数据计算方法， 本文提出一种内存滑动窗口机制对在线计算的数 据变化模式进行统一建模，并根据上述模型，推 导出不同类型数据变化模式下的三支决策条件概 率及三支区域的变化规律。最后本研究提出一种 新型的动态在线快速计算算法，该算法能够获得 与经典三支决策算法相同的决策结果。由于本算 法只需要对当前的变化数据进行局部实时计算， 有效避免了历史数据的重复学习，大大提高了三 支决策更新效率。为验证本文所提出的在线快速 计算的优势，与经典计算算法在 8 个 UCI 公共数 据集上进行实验对比。实验结果表明，在线快速 计算比经典计算算法效率更高，稳定性更好。本 研究表明，概率粗糙集三支决策领域采用在线计 算方法进行快速计算是可行的。我们将在未来的 工作中，继续探讨概率粗糙集三支决策的多对象 动态在线快速计算以及其在实际在线计算场景中 的应用。 参考文献： FONG S, WONG R, VASILAKOS A V. Accelerated PSO swarm search feature selection for data stream mining big data[J]. IEEE transactions on services computing, 2016, 9(1): 33–45. [1] ZHANG Hong, LI Bo, JIANG Hongbo, et al. A frame￾work for truthful online auctions in cloud computing with heterogeneous user demands[C]//Proceedings of 2013 IEEE INFOCOM. Turin, Italy, 2013: 1510–1518. [2] ESKANDARI S, JAVIDI M M. Online streaming feature selection using rough sets[J]. International journal of ap￾proximate reasoning, 2016, 69: 35–57. [3] CHAZELLE B, ROSENBERG B. The complexity of com￾puting partial sums off-line[J]. International journal of computational geometry and applications, 1991, 1(1): 33–45. [4] DENG Jie, QU Zhiguo, ZHU Yongxu, et al. Towards effi￾cient and scalable data mining using spark[C]//Proceed￾ings of 2014 International Conference on Information and Communications Technologies. Nanjing, China, 2014: 1–6. [5] YAO Yiyu. Three-way decisions and cognitive computing [J]. Cognitive computation, 2016, 8(4): 543–554. [6] 计算时间/s 内存中数据量 (a) 流数据总量的 10% 经典计算 在线计算 0 5 10 15 20 25 30 1 5 10 20 0 5 10 15 20 25 30 计算时间/s 内存中数据量 (d) 流数据总量的 100% 经典计算 在线计算 1 5 10 20 计算时间/s 内存中数据量 (c) 流数据总量的 70% 经典计算 在线计算 1 5 10 20 0 5 10 15 20 计算时间/s 内存中数据量 (b) 流数据总量的 40% 经典计算 在线计算 1 5 10 20 0 1 2 3 4 5 6 ×105 ×104 ×102 ×102 ×102 ×102 ×105 ×105 图 3 在线快速计算与经典计算算法在不同内存容量下的平均执行时间 Fig. 3 Average elapsed times between online computing algorithm and classical computing algorithm on different memory sizes 0 5 10 15 20 25 30 (0.6,0.4) (0.7,0.3) (0.8,0.2) (0.9,0.1) (1,0) 计算时间/s 阈值对 Skin_NoSkin Shuttle IRIS Zoo Haberman Breast-cancer Letter Magic ×102 图 4 不同阈值对在线快速计算平均执行时间 Fig. 4 Average elapsed times on online computing al￾gorithm with different threshold pairs 第 5 期 徐健锋，等：概率粗糙集三支决策在线快速计算算法研究 ·749·

·750· 智能系统学报 第13卷 [7]ZHOU Bing,YAO Yiyu,LUO Jigang.Cost-sensitive three-way classifications[J].International journal of ap- three-way email spam filtering[J].Journal of intelligent in- proximate reasoning,2017,81:103-114. formation systems,2014,42(1):19-45. [22]GRECO S,MATARAZZO B,ROMAN S.Rough sets [8]KHAN MT,AZAM N.KHALID S,et al.A three-way ap- theory for multicriteria decision analysis[J].European proach for learning rules in automatic knowledge-based journal of operational research,2001,129(1):1-47 topic models[J].International journal of approximate reas- [23]LIU Dun,LI Tianrui,ZHANG Junbo.Incremental updat- 0ning,2017,82:210-226, ing approximations in probabilistic rough sets under the [9]LI Huaxiong,ZHANG Libo,ZHOU Xianzhong,et al. variation of attributes[J].Knowledge-based systems, Cost-sensitive sequential three-way decision modeling us- 2015,73:81-96. ing a deep neural network[J].International journal of ap- [24]LI Shaoyong,LI Tianrui,LIU Dun.Incremental updating proximate reasoning,2017,85:68-78. approximations in dominance-based rough sets approach [10]QIAN Jin,DANG Chuangyin,YUE Xiaodong.et al.At- under the variation of the attribute set[J].Knowledge- tribute reduction for sequential three-way decisions under based systems,2013,40:17-26. dynamic granulation[J].International journal of approx- [25]ZHANG Junbo,LI Tianrui,RUAN Da,et al.Neighbor- imate reasoning,2017,85:196-216. hood rough sets for dynamic data mining[J].International [11]YU Hong,ZHANG Cong,WANG Guoyin.A tree-based journal of intelligent systems,2012,27(4):317-342. incremental overlapping clustering method using the [26]LUO Chuan,LI Tianrui,CHEN Hongmei.Dynamic three-way decision theory[J].Knowledge-based systems, maintenance of three-way decision rules[C]//Proceedings 2016,91:189-203. of the 9th International Conference on Rough Sets and [12]LUO Chuan,LI Tianrui,CHEN Hongmei,et al.Efficient Knowledge Technology.Shanghai,China,2014:801- updating of probabilistic approximations with increment- 811. al objects[J].Knowledge-based systems,2016,109 [27]PAPANDREOU G,KOKKINOS I,SAVALLE P A 71-83. Modeling local and global deformations in Deep Learn- [13]NAUMAN M.AZAM N.YAO Jingtao.A three-way de- ing:epitomic convolution,Multiple Instance Learning, cision making approach to malware analysis using prob- and sliding window detection[C]//Proceedings of 2015 abilistic rough sets[M].New York,NY,USA:Elsevier, IEEE Conference on Computer Vision and Pattern Recog- 2016. nition.Boston,MA,USA,2015:390-399. [14]CHEN Yufei,YUE Xiaodong,FUJITA H,et al.Three- [28]YUN U,LEE G.Sliding window based weighted eras- way decision support for diagnosis on focal liver able stream pattern mining for stream data applications[J]. lesions[J].Knowledge-based systems,2017,127:85-99. Future generation computer systems,2016,59:1-20. [15]CHEN Hongmei,LI Tianrui,LUO Chuan,et al.A de- 作者简介： cision-theoretic rough set approach for dynamic data min- 徐健锋，男，1973年生，副教授， ing[J].IEEE transactions on fuzzy systems,2015,23(6) 博土研究生，计算机学会会员，主要研 1958-1970. 究方向为数据挖掘、粗糙集、机器学 [16]LIANG Decui,XU Zeshui,LIU Dun.Three-way de- 习。主持国家自然基金项目1项，参 cisions based on decision-theoretic rough sets with dual 与国家自然科学基金项目2项。 hesitant fuzzy information[J.Information sciences,2017, 396:127-143 [17]ZHANG Hongying,YANG Shuyun,MA Jianmin.Rank- ing interval sets based on inclusion measures and applica- 何宇凡，男.1994年生，硕士研究 tions to three-way decisions[J].Knowledge-based sys- 生，主要研究方向为三支决策、粗糙 tems.2016,91:62-70. 集、粒计算、机器学习。 [18]ZHAO Xuerong,HU Baoqing.Fuzzy probabilistic rough sets and their corresponding three-way decisions[J]. Knowledge-based systems,2016,91:126-142. [19]AZAM N,ZHANG Yan,YAO Jingtao.Evaluation func- tions and decision conditions of three-way decisions with 汤涛，男，1993年生，硕士研究 game-theoretic rough sets[J].European journal of opera- 生，主要研究方向为粗糙集、粒计算、 tional research,2017,261(2):704-714. 机器学习。 [20]DENG Xiaofei,YAO Yiyu.A multifaceted analysis of probabilistic three-way decisions[J].Fundamenta inform- aticae,.2014,132(3):291-313. [21]ZHANG Yan,YAO Jingtao.Gini objective functions for

ZHOU Bing, YAO Yiyu, LUO Jigang. Cost-sensitive three-way email spam filtering[J]. Journal of intelligent in￾formation systems, 2014, 42(1): 19–45. [7] KHAN M T, AZAM N, KHALID S, et al. A three-way ap￾proach for learning rules in automatic knowledge-based topic models[J]. International journal of approximate reas￾oning, 2017, 82: 210–226. [8] LI Huaxiong, ZHANG Libo, ZHOU Xianzhong, et al. Cost-sensitive sequential three-way decision modeling us￾ing a deep neural network[J]. International journal of ap￾proximate reasoning, 2017, 85: 68–78. [9] QIAN Jin, DANG Chuangyin, YUE Xiaodong, et al. At￾tribute reduction for sequential three-way decisions under dynamic granulation[J]. International journal of approx￾imate reasoning, 2017, 85: 196–216. [10] YU Hong, ZHANG Cong, WANG Guoyin. A tree-based incremental overlapping clustering method using the three-way decision theory[J]. Knowledge-based systems, 2016, 91: 189–203. [11] LUO Chuan, LI Tianrui, CHEN Hongmei, et al. Efficient updating of probabilistic approximations with increment￾al objects[J]. Knowledge-based systems, 2016, 109: 71–83. [12] NAUMAN M, AZAM N, YAO Jingtao. A three-way de￾cision making approach to malware analysis using prob￾abilistic rough sets[M]. New York, NY, USA: Elsevier, 2016. [13] CHEN Yufei, YUE Xiaodong, FUJITA H, et al. Three￾way decision support for diagnosis on focal liver lesions[J]. Knowledge-based systems, 2017, 127: 85–99. [14] CHEN Hongmei, LI Tianrui, LUO Chuan, et al. A de￾cision-theoretic rough set approach for dynamic data min￾ing[J]. IEEE transactions on fuzzy systems, 2015, 23(6): 1958–1970. [15] LIANG Decui, XU Zeshui, LIU Dun. Three-way de￾cisions based on decision-theoretic rough sets with dual hesitant fuzzy information[J]. Information sciences, 2017, 396: 127–143. [16] ZHANG Hongying, YANG Shuyun, MA Jianmin. Rank￾ing interval sets based on inclusion measures and applica￾tions to three-way decisions[J]. Knowledge-based sys￾tems, 2016, 91: 62–70. [17] ZHAO Xuerong, HU Baoqing. Fuzzy probabilistic rough sets and their corresponding three-way decisions[J]. Knowledge-based systems, 2016, 91: 126–142. [18] AZAM N, ZHANG Yan, YAO Jingtao. Evaluation func￾tions and decision conditions of three-way decisions with game-theoretic rough sets[J]. European journal of opera￾tional research, 2017, 261(2): 704–714. [19] DENG Xiaofei, YAO Yiyu. A multifaceted analysis of probabilistic three-way decisions[J]. Fundamenta inform￾aticae, 2014, 132(3): 291–313. [20] [21] ZHANG Yan, YAO Jingtao. Gini objective functions for three-way classifications[J]. International journal of ap￾proximate reasoning, 2017, 81: 103–114. GRECO S, MATARAZZO B, ROMAN S. Rough sets theory for multicriteria decision analysis[J]. European journal of operational research, 2001, 129(1): 1–47. [22] LIU Dun, LI Tianrui, ZHANG Junbo. Incremental updat￾ing approximations in probabilistic rough sets under the variation of attributes[J]. Knowledge-based systems, 2015, 73: 81–96. [23] LI Shaoyong, LI Tianrui, LIU Dun. Incremental updating approximations in dominance-based rough sets approach under the variation of the attribute set[J]. Knowledge￾based systems, 2013, 40: 17–26. [24] ZHANG Junbo, LI Tianrui, RUAN Da, et al. Neighbor￾hood rough sets for dynamic data mining[J]. International journal of intelligent systems, 2012, 27(4): 317–342. [25] LUO Chuan, LI Tianrui, CHEN Hongmei. Dynamic maintenance of three-way decision rules[C]//Proceedings of the 9th International Conference on Rough Sets and Knowledge Technology. Shanghai, China, 2014: 801– 811. [26] PAPANDREOU G, KOKKINOS I, SAVALLE P A. Modeling local and global deformations in Deep Learn￾ing: epitomic convolution, Multiple Instance Learning, and sliding window detection[C]//Proceedings of 2015 IEEE Conference on Computer Vision and Pattern Recog￾nition. Boston, MA, USA, 2015: 390–399. [27] YUN U, LEE G. Sliding window based weighted eras￾able stream pattern mining for stream data applications[J]. Future generation computer systems, 2016, 59: 1–20. [28] 作者简介： 徐健锋，男，1973 年生，副教授， 博士研究生，计算机学会会员，主要研 究方向为数据挖掘、粗糙集、机器学 习。主持国家自然基金项目 1 项，参 与国家自然科学基金项目 2 项。 何宇凡，男，1994 年生， 硕士研究 生，主要研究方向为三支决策、粗糙 集、粒计算、机器学习。 汤涛，男，1993 年生，硕士研究 生，主要研究方向为粗糙集、粒计算、 机器学习。 ·750· 智 能 系 统 学 报 第 13 卷