基于三支决策粗糙集的概念漂移研究

张 任，王 晖

(浙江师范大学 数理与信息工程学院，浙江 金华 321004)

基于三支决策粗糙集的概念漂移研究

张 任，王 晖

(浙江师范大学 数理与信息工程学院，浙江 金华 321004)

随着大数据时代的到来，数据挖掘已经成为研究热点，概念漂移作为数据挖掘领域所面临的挑战之一，也越来越受到人们的关注。针对传统基于经典粗糙集的概念漂移探测研究不关注边界域上的概念漂移现象、不具有容错性的问题，提出了基于三支决策粗糙集的概念漂移的探测算法，该算法将概念漂移的探测拓展到了三支决策粗糙集领域，将正域概念漂移探测的意义推广到了边界域上，认为边界域上的概念漂移现象也是值得研究的且具有实际意义的。利用三支决策粗糙集能够有效模拟人类智能的不确定性和非精确性的特点，增加了该概念漂移算法的容错性。最后，通过实验验证了该算法的可行性。

概念漂移;三支决策粗糙集;数据挖掘;容错性

0 引言

现实生活中的数据总是按照时间的顺序连续不断地到达，如声波和信号。连续不断有序到达的数据就是数据流。由于干扰及噪声的存在，从数据流中挖掘出有用的数据显得十分重要。数据挖掘是机器学习的主要应用之一，目前机器学习所面临的主要挑战包括概念漂移。概念漂移[1-3]指的是数据及其分布随时间的推移而变化的现象。

滑动窗口技术[4]作为探测概念漂移的常用技术之一，包括固定大小的滑动窗口和可变大小的滑动窗口。其运用的分类技术主要有单一分类器和集成分类器[5-6]，后者以其分类速度快、分类准确率高等优势，在概念漂移探测领域取得了广泛了应用。

粗糙集[7-8]是一种不需要借助外部知识，只需要通过对数据的分析、研究就能发掘数据的潜在的知识和规律的数学工具。目前已有一些利用粗糙集理论对概念漂移进行研究的介绍：文献[9]利用粗糙集的上近似以及下近似来探测概念漂移，并运用粗糙率来度量概念漂移的程度；文献[10]的研究建立在F-粗糙集理论之上，并提出了概念漂移探测的一些指标；文献[11]通过分析并指出了运用数据内部特性——属性重要度来探测概念漂移的效果优于利用分类准确率的方法；文献[12]运用F-模糊粗糙集理论及其方法对模糊数据流上的模糊概念漂移进行探测。这些概念漂移的探测没有关注到边界域上的概念漂移情况，且不具有容错性。

三支决策作为决策粗糙集的重要思想之一，有效模拟了人类智能的模糊性和不精准性，并重新探讨了经典粗糙集的语义，将可能正确的划入正域，即接受；可能不正确的划入负域，即拒绝；介于两者之间的划入边界域，表示需要进一步观察，即延迟决策，并认为延迟决策是一种可执行决策。三支决策粗糙集[13-14]通过风险值得到的两个阈值α、β对论域进行划分从而得到具有某种容错能力的三个区域，即正域、负域和边界域，形成了具有容错性的概率三支决策过程，增加了容错性，该思想已经被应用在医学诊断、数据集选择以及智能学习等领域[15-16]。

对于边界域的研究是三支决策粗糙集领域的一个热点，边界域代表着不确定性，对边界域上的概念漂移情况进行研究，就是研究实际概念的不确定性，这更加切合概念漂移探测的实质，也更加符合人类的思维模式。

本文主要研究基于三支决策粗糙集的概念漂移探测，将传统的基于经典粗糙集的概念漂移探测拓展到了三支决策粗糙集领域，将正域概念漂移探测的意义推广到了边界域上。首先提出了基于三支决策粗糙集探测概念，在重点关注边界域上的概念漂移的同时，也提出了分别在正域、负域上概念漂移的度量指标及其相关算法；定义了从整体上综合了正域、负域和边界域上的概念漂移程度的概念漂移确及其算法；通过实验验证了文中所提方法的可行性。基于三支决策粗糙集的概念漂移探测符合人类日常处理决策问题时的思维过程，具有广泛的代表性。

1 基础知识

三支决策是决策粗糙集的核心思想之一，它将传统的正域、负域两支决策语义拓展为正域、负域和边界域的三支决策语义，认为边界域决策也是一类可行的决策，这与人类智能在处理决策问题的方法是一致的，也是人们在处理决策问题过程中常用的一种策略。例如现实中医生对疾病进行诊断，有时并不能立即断定是否患某种疾病，需要更进一步的观察再作出判断。现对三支决策粗糙集理论及其相关知识介绍如下。

定义1 假设U是一个有限的非空子集，R是定义在U上的一种等价关系，记apr=(U,R)，为近似空间，U在等价关系R下的划分记为U/R={[x]R|x∈U}，[x]R是包含x的等价类。∀X⊆U，其下、上近似集定义为：

上、下近似集将论域分为三个部分，即正域POS(X)、边界域BND(X)和负域NEG(X)，其定义分别为：

由正域中元素导出的规则表示确定属于X的规则，由负域中元素导出的规则表示确定不属于X的规则，而由边界域导出的规则表示可能属于X的规则。这体现了三支决策的基本思想，但Pawlak粗糙集并没有考虑到规则的容错性。

定义2 假设S=(U,A,V,f)是一个信息表，R是定义在U上的等价关系，∀x∈U，X⊆U，记

Pr(X|[x]R)=|[x]R∩X|/|[x]R|

其中，|·|表示集合中元素的基数；Pr(X|[x]R)表示分类条件概率。

定义3 假设S=(U,A,V,f)是一个信息表，∀X⊆U，0≤β<α≤1，则(α,β)-下近似集、(α、β)-上近似集可分别定义为：

同样地，(α,β)-上、下近似集将论域分为三个部分，即(α,β)-正域POS(α,β)(X)、(α,β)-边界域BND(α,β)(X)和(α,β)-负域NEG(α,β)(X)，其定义分别为：

POS(α,β)(X)={x∈U|Pr(X|[x]R)≥α}

BND(α,β)(X)={x∈U|β

NEG(α,β)(X)={x∈U|Pr(X|[x]R)≤β}

当α=1，β=0时，该模型转化成Pawlak粗糙集模型；当α=β=0.5时，上述模型转化成0.5-概率粗糙集模型。然而，Pawlak粗糙集模型和0.5-概率粗糙集模型只是两种特殊情况下的三支决策模型，大多概率粗糙集在参数α和β的选取上都缺乏对实际语义的思考。Yao等的决策粗糙集理论是将Bayes决策过程引入概率粗糙集模型，为概率粗糙集模型给出了语义上的一种解释。

在决策粗糙集理论的(α,β)-三支决策过程中，条件概率Pr(X|[x]R)可完全从信息系统计算得出，是通过机器学习得到的，是客观的；阈值α和β是通过行动损失参数计算得出的，而行动损失的大小可由行为学实验或专家的意见给出，是通过人类经验得到的，是主观的。利用α和β去验证条件概率Pr(X|[x]R)的正确性，利用条件概率Pr(X|[x]R)去指导α和β设置的合理性，两者相辅相成，互为补充。因而，三支决策粗糙集体现了一种主观和客观相结合，人机合一的思想。

定义4 假设S=(U,C∪d,V,f)是一个决策表，α∈[0,1]为条件概率阈值,a∈C为单个属性，则属性a的α-正域全局重要度定义为：

三支决策作为决策粗糙集的重要思想之一，有效地模拟了人类智能的模糊性和不精准性，对于边界域的研究是三支决策粗糙集领域的一个热点，边界域代表着不确定性，对概念在边界域上的漂移进行研究，就是研究实际概念的不确定性，这更加切合概念漂移探测的实质，也更加符合人类的思维模式。

2 基于三支决策粗糙集的概念漂移

基于以上基础知识及背景，本文将概念漂移的探测拓展到三支决策粗糙集领域。首先，对基于边界域和负域的属性重要度定义如下。

2.1 基于边界域和负域的属性重要度

传统的关于属性重要度的研究只集中在正域上，几乎没有研究是基于边界域和基于负域的属性重要度。基于边界域的属性重要度可以刻画出属性在边界域上的变化情况，这为更好地研究延迟决策提供了依据，其相应的定义如下。

定义5(基于边界域的属性重要度) 已知S={U,C∪d,f,V}一决策表,0≤β<α≤1,α、β为概率阈值,a∈C为单个属性,则决策属性集D(这里简记为d)相对于条件属性a的(α,β)-边界域全局重要度定义为：

定义6 (基于负域的属性重要度) 已知S={U,C∪d,f,V}一决策表,0≤β<α≤1,β为概率阈值,a∈C为单个属性,则决策属性d相对于条件属性a的(α,β)-负域全局重要度定义为：

定理1 决策属性d对同一条件属性a下的基于正域的属性重要度、基于负域的属性重要度以及基于负域的属性重要度之和为定值1。

证明：由定义4～6可知γp(d)、γB(d)、γN(d)具体意义，在此不在赘述。

γp(d)+γB(d)+γN(d)=

定理1证毕。

定理2 基于边界域的属性重要度和基于负域属性重要度至少有一个在约简时不随着属性个数的减少而变增大。

证明：由文献[13-14] 可知基于正域的属性重要度不具有单调性，并且由定理1可知三个属性重要度之间存在线性关系，故若基于边界域的属性重要度和基于负域的属性重要度都存在着单调性，则基于正域的属性重要度也必然存在单调性，故定理2成立。

2.2 基于三支决策粗糙集的概念漂移探测

基于三支决策粗糙集的概念漂移探测增加了探测算法的容错性。因为三支决策粗糙集认为具有较高正确可能性的就可以进入正域，而不满足较低划分阈值的就可以进入负域，介于两者之间的就会进入边界域。而传统的粗糙集要求完全正确或完全属于的才可以进入正域，完全错误或完全不属于的就进入负域，介于两者之间的进入边界域，所以不具有噪声容忍机制。例如文献[11]利用基于正域的属性重要度去探测概念漂移，当存在噪声的时候，正域的划分将受到影响，从而导致基于正域的属性重要度的值发生改变，若以此为依据来判断是否存在概念漂移现象，则可能产生误判。

本节主要研究基于三支决策粗糙集探测概念漂移，分别给出了基于边界域、负域、正域的属性重要性向量、基于三支决策的正域、边界域和负域全局属性重要度的概念漂移确指标定义，以及相关基于三支决策的概念漂移的探测算法(注：滑动窗口视为数据流决策系统的决策子表，两者可等同看待)。

定义7(基于三支决策的边界域全局属性重要度矩阵) 已知Si={Ui,C∪D,f,V}(i=1,2,…，n)是数据流决策系统DS=(U,A,d)的滑动窗口，F是若干个滑动窗口的集合，则属性A关于F基于三支决策的边界域全局属性重要度矩阵TB(A,F)可以定义为：

定义8(基于三支决策的正域全局属性重要度矩阵)已知Si={Ui,C∪D,f,V}(i=1,2,…，n)是数据流决策系统DS=(U,A,d)的决策子表(滑动窗口)，F是若干个滑动窗口的集合，则属性A关于F基于三支决策的正域全局属性重要度矩阵TP(A,F)可以定义为：

定义9(基于三支决策的负域全局属性重要度矩阵) 已知Si={Ui,C∪D,f,V}(i=1,2,…，n)是数据流决策系统DS=(U,A,d)的滑动窗口，F是若干个滑动窗口的集合，则属性A关于F基于三支决策的负域全局属性重要度矩阵TN(A,F)可以定义为：

2.2.1 独立的概念漂移探测

传统的概念漂移研究仅仅关注概念在正域上的漂移情况，而同一个概念在不同的情况下不仅在正域上发生了变化，它在边界域、负域上也可能会发生变化。三支决策的优势就是在于它注重决策的容错性，并认为边界域上的决策也是一种可行性决策，从而更加符合人类日常的思考。在考虑属性的概念漂移时，不仅要考虑概念在正域上的漂移情况，同样要考虑属性在负域和边界域的概念漂移情况。下面运用属性重要性的变化情况对概念漂移进行度量，研究概念在正域、负域以及边界域上的变化情况，并着重讨论概念在边界域上的漂移情况。它们的定义如下。

定义10(基于三支决策的边界域全局属性重要度概念漂移量) 在基于三支决策的边界域全局属性重要度矩阵TB(A,F)中，单个属性a∈A在边界域上的属性重要度的概念漂移量定义为：

其中j为属性a∈A在TB(A,F)中所对应的列。DTk、DTl为F中的两个滑动窗口。

概念在边界域上的漂移量的提出，为探测边界域上的概念漂移情况提供了指标，从而更加切合探测概念漂移的实质，即对概念发生变化的不确定性进行度量，也更加符合人类的思维模式。例如：从数学上，通过边界域来描述集合的不确定性，就能更精确地度量知识的不确定性。

同样可以得到基于正域及负域的概念漂移量。

定义11(基于三支决策的正域全局属性重要度概念漂移量) 在基于三支决策的正域全局属性重要度矩阵TP(A,F)中，单个属性a∈A在正域上的属性重要度的概念漂移量定义为：

其中j为属性a∈A在TP(A,F)中所对应的列。

定义12(基于三支决策的负域全局属性重要度概念漂移量) 在基于三支决策的负域全局属性重要度矩阵TN(A,F)中，单个属性a∈A在负域上的属性重要度的概念漂移量定义为：

其中j为属性a∈A在TN(A,F)中所对应的列。

性质1 基于三支决策粗糙集的概念漂移探测具有容错性。

定理3 基于三枝决策的属性重要性的概念漂移量DRCDp(DTk,DTl)、DRCDB(DTk,DTl)DRCDN(DTk,DTl)满足对称、非负、三角不等式。

证明：因证明过程类似，这里只证明DRCDP(DTk,DTl)满足对称、非负、三角不等式。

已知DRCDP(DTk,DTl)=|γkj-γlj|,DRCDP(DTl,DTk)=|γlj-γkj|,但|γkj-γlj|=|γlj-γkj|，故可知DRCDP(DTk,DTl)满足对称性;又知DRCDN(DTk,DTl)=|γkj-γlj|，则知DRCDP(DTk,DTl)满足非负性、三角不等式。

定理4 基于三枝决策正域全局属性重要性的概念漂移量DRCDp(DTk,DTl)非零时，则DRCDN(DTk,DTl)、DRCDB(DTk,DTl)中至多有一个为零。

证明：假设当DRCDp(DTk,DTl)非零时，则DRCDN(DTk,DTl)、DRCDB(DTk,DTl)全部为零。由正域、负域和边界域的定义及属性的重要度定义可知,在同一决策表中相同的属性a中存在γP(d)+γB(d)+γN(d)=1，故在滑动窗口DTk、DTl中对于属性a分别有γPk(d)+γBk(d)+γNk(d)=1，γPl(d)+γBl(d)+γNl(d)=1成立。若DRCDN(DTk,DTl)、DRCDB(DTk,DTl)都为零则可以知道|γBk-γBl|=|γNk-γNl|=0，即γBk=γBl，γNk=γNl，则γPk=γPl，那就可知DRCDP=|γPk-γPl|=0，与DRCDp(DTk,DTl)非零相矛盾，故原命题得证。

2.2.2 独立的概念漂移探测算法

现在给出具体利用三支决策粗糙集探测概念独立的概念漂移算法，为算法中表达清楚明白，下面首先给出概念漂移与阈值关系的定义，只有概念漂移量大于相应的阈值时，才认为存在概念漂移。

定义13(基于三支决策的边界域全局属性重要度概念漂移确) 设TB(A,F)是若干个滑动窗口Si(i=1,2,3,…，n)的基于三支决策的边界域全局属性重要度矩阵，ε为一个给定的阈值，DRCDBND(DTk,DTl)为基于三支决策的边界域全局属性重要度概念漂移量，则基于三支决策的边界域全局属性重要度概念漂移确QBND∈{0,1}：

(1)当DRCDBND(DTk,DTl)≥ε时，QBND=1；

(2)当DRCDBND(DTk-DTl)<ε时，QBND=0。

基于三支决策的边界域全局属性重要度概念漂移探测算法如下。

算法1 基于三支决策的边界域全局属性重要度概念漂移探测算法

输入：若干个滑动窗口Si={Ui,d,f,V}(i=1,2,…，n)，阈值α,β∈[0,1]；

输出：若干个滑动窗口Si={Ui,d,f,V}(i=1,2,…，n)有没有发生边界域概念漂移；

第1步：根据阈值α,β求出每个滑动窗口Si={Ui,d,f,V}(i=1,2,...n)的边界域属性重要度；

第2步：求出每个属性在每个滑动窗口中的基于三支决策的边界域的全局属性重要度，并分别生成基于三支决策的边界域全局属性重要度矩阵TB(A,F)；

第3步：分别在这个矩阵中计算相邻两行之间对应元素之差，即基于边界域的概念漂移量DRCDBND(DTi,DTi-1)；

第4步：计算基于三支决策的边界域全局属性重要度概念漂移确，即QBND；

输出若干个滑动窗口Si={U,C∪D,f,V}(i=1,2,…，n)没有发生边界域概念漂移，结束程序。

定义14(基于三支决策的正域全局属性重要度概念漂移确) 设TP(A,F)是若干个滑动窗口Si(i=1,2,3,…，n)的基于三支决策的正域全局属性重要度矩阵，δ为一个给定的阈值，DRCDPOS(DTk,DTl)为基于三支决策的正域全局属性重要度概念漂移量，则基于三支决策的正域全局属性重要度概念漂移确QPOS∈{0,1}：

(1)当DRCDPOSij(DTi-DTi-1)≥δ时，QPOS=1；

(2)当DRCDPOSij(DTi-DTi-1)<δ时，QPOS=0。

基于三支决策的正域全局属性重要度概念漂移探测算法如下。

算法2 基于三支决策的正域全局属性重要度概念漂移探测算法

输入：若干个滑动窗口Si={Ui,d,f,V}(i=1,2,…，n)，阈值α,β∈[0,1]；

输出：若干个滑动窗口Si={Ui,d,f,V}(i=1,2,…，n)有没有发生正域概念漂移；

第1步： 根据阈值α,β求出每个滑动窗口Si={Ui,d,f,V}(i=1,2,…，n)的正域属性重要度。

第2步：求出每个属性在每个滑动窗口中的基于三支决策的正域的全局属性重要度，并分别生成基于三支决策的正域全局属性重要度矩阵TP(A,F)；

第3步：分别在这个矩阵中计算相邻两行之间对应元素之差，即基于正域的概念漂移量DRCDPOS(DTi,DTi-1)(1≤i≤n)；

第4步：计算基于三支决策的正域全局属性重要度概念漂移确，即QPOS；

输出若干个滑动窗口Si={U,C∪D,f,V}(i=1,2,…，n)没有发生正域概念漂移，结束程序。

相应地，也可以得到属性在负域上的概念漂移算法(算法3)，但篇幅原因，在此就不详细叙述，记φ、QNES∈{0,1}为与基于负域的概念漂移量相对应得阈值和概念漂移确。

算法3(略)。

例1 设F={DT1,DT2}，如表1、表2所示，其论域U1={e1,e2,e3,e4,e5}，U2={e4,e5,e6,e7,e8},条件属性集C={Headache,Muscle-pain,Temperature}，决策条件属性d={Flu}。

表1 流感诊断决策表DT1

表2 决策子系统DT2

通过计算可得F的基于正域、边界域、负域的属性重要性矩阵TP(A,F)、TB(A,F)与TN(A,F)分别为：

DT1与DT2之间的概念漂移为：

如果ε、δ、φ均取0.3，那么相对于单个属性a在正域、负域上具有概念漂移，在边界域上就不具有概念漂移；相对于单个属性b在边界域、负域上具有概念漂移具有概念漂移，在正阈上就不具有概念漂移；相对于单个属性c在正域、负域上具有概念漂移，在边界域上不具有概念漂移。

2.2.3 整体概念漂移探测

下面探讨整体上来探讨概念漂移的程度。以上的研究只是在独立的研究属性在正阈、负域、边界域是否存在概念漂移，没有将正域、负域、边界域上的概念漂移综合起来研究属性的概念漂移，不仅要单一地研究属性的概念漂移，而且要整体上结合正域、负域、边界域上的概念漂移来研究属性的概念漂移，这样更符合人们认识客观世界的思维逻辑，从局部和整体上去认识事物。基于三支决策的整体概念漂移探测算法如下。

算法4 基于三支决策的整体概念漂移探测算法

输入：若干个滑动窗口Si={Ui,d,f,V}(i=1,2,…，n)，阈值α,β∈[0,1]；

输出：若干个滑动窗口Si={Ui,d,f,V}(i=1,2,…，n)有没有发生整体概念漂移；

第1步:调用算法1、算法2、算法3分别计算基于三支决策的正域、边界域、 负域全局属性重要度概念漂移确，即QPOS、QBND、QNEG；

第2步:计算QPOS+QBND+QNEG，若结果为3执行第3步，若结果为0执行第4步，若结果为1执行第4步，若结果为2执行第3步；

第3步：Si={U,C∪D,f,V}(i=1,2,…，n)发生了概念漂移，结束程序；

第4步：输出若干个滑动窗口Si={U,C∪D,f,V}(i=1,2,…，n)没有发生概念漂移，结束程序。

该整体概念漂移探测算法以正域、边界域、负域各自表示的实际语义为依据，主要分为以下两种情况：

(1)当正域、负域、边界域至少两者发生概念漂移时，则称之单个属性发生全概念漂移；

(2)当正域、负域、边界域至多一个发生概念漂移时，则称为属性不发生全概念漂移。

3 实验

在本节中将通过实验来验证算法和定义的可行性和有效性。实验数据选择UCI数据集的mushroom数据，滑动窗口大小为100，相邻滑动窗口间有10%的重复率，阈值大小从0.01到1，间隔为0.01。

(1)独立的属性概念漂移探测

图1和图2分别显示在所有滑动窗口下基于边界域和正域的概念漂移情况。

图1 基于边界域的概念漂移总数与阈值ε之间的关系

图1中DRCDBND(DTi,DTi+1)≥ε，表示在边界域上存在一次概念漂移，通过图1分析可知，概念在边界域的确存在概念漂移的情况，并且不同的阈值会有相应的概念漂移情况产生，当阈值大于0.36以后边界域上几乎没有概念漂移的情况。

图2 基于正域的概念漂移总数与阈值δ之间的关系

图2中，当DRCDPOS(DTi,DTi+1)≥δ时，表示存在一次概念漂移，实验结果显示阈值大于0.36以后边界域上几乎没有概念漂移的情况，并且图中曲线变化相比文献[11]要平缓，原因是本文所依据的三支决策粗糙集决策规则的容错性使得基于正域的属性重要度的变化更加明显，所定义的基于正域的属性重要性的概念漂移量的变化范围更广，即可以容忍一定噪声的影响，同样基于边界域上的概念漂移探测也是具有容错性的。基于正域的概念漂移探测的阈值，通过图1分析，可以选择[0.05,0.25],而在文献[11]阈值选取0.01～0.1，若轻微的噪声的影响使得它所定义的度量概念漂移的指标值为0.01，则会判断出属性存在概念漂移。

基于负域的概念漂移与阈值φ之间的关系，同边界域、正域相类似，在此就不再赘述。

(2)综合意义下的概念漂移探测

下面来探讨整体上来探讨概念漂移的程度。以上的研究只是在独立的研究属性在正域、负域、边界域是否存在概念漂移，没有将正阈、负域、边界域综合起来研究属性的概念漂移，不仅要单一地研究属性的概念漂移，而且要整体、综合研究概念漂移，图3是根据概念漂移确来研究的综合上探测概念漂移的情况。

图3 单个属性在滑动窗口下的整体概念漂移情况

在本次实验中，实验数据有9个属性，论域被划分为7个滑动窗口，因对每个属性的实验结果相类似，下面选取第4个属性来说明概念在整体意义上的概念漂移情况。

在第1、3、4相邻的滑动窗口下，属性在整体上存在概念漂移的情况，特别在第3个相邻的滑动窗口间，整体意义上的概念漂移情况更明显。2中不存在单独及整体上的概念漂移，5、6中在边界域、负域上也存在整体意义的概念漂移。

由此可以更加清晰地判断概念漂移的程度，若在整个滑动窗口中如3情况出现的次数过多，那么在后续基于三支决策的聚类和其他三支决策应用中就要对这个属性特别注意，防止由于概念漂移而影响实际的结果。

4 结论

针对传统基于经典粗糙集的概念漂移探测研究不关注边界域上的概念漂移现象和不具有容错性的问题，本文提出了基于三支决策粗糙集的概念漂移的探测算法。实验结果表明该算法比传统的概念漂移算法更具容错性。但是，在处理具有大量属性的概念在边界域上的漂移探测问题上，仍然有可能存在时间复杂度过高的问题。将并行计算的思想结合到基于三支决策的概念漂移探测中，在探测之前对冗余属性进行删除，从而降低处理算法的时间复杂度，这将是下一步的研究方向。

[1]KUNCHEVALI.Classifierensemblesforchangingenvironments[C].ProceedingsoftheFifthWorkshoponMultipleClassifierSystems.Cagliari,Italy, 2004: 1-15.

[2] 王涛, 李舟军, 颜跃进, 等. 数据流挖掘分类技术综述[J]. 计算机研究与发展, 2007, 44(11): 1809-1815.

[3]HOENSTR,POLIKARR,CHAWLANV.Learningfromstreamingdatawithconceptdriftandimbalance:anoverview[J].ProgressinArtificialIntelligence, 2011: 1-13.

[4]BABCOCKB,BABUS,DATERM,etal.Modelsandissuesindatastreamsystems[C].Proceedingsofthe19thACM

SIGACT-SIGMOD-SIGARTSymposiumonPrinciplesDatabaseSystems,Madison,USA, 1802.

[5] 孙岳,毛国君,刘旭，等.基于多分类器的数据流中的概念漂移挖掘[J].自动化学报,2008, 34(1): 93-96.

[6]WangHaixun,FanWei,YUPS,etal.Miningconcept-driftingdatastreamsusingensembleclassifiers[C].Proceedingsofthe9thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining,Washington,USA, 2003:226-235.

[7]PAWLAKZ.Roughsets-theoreticalaspectofreasoningaboutdata[M].KluwerAcademicPublishers,Dordrecht, 1991.

[8] 王国胤, 姚一豫, 于洪. 粗糙集理论与应用研究综述[J]. 计算机学报, 2009,32(7): 1229-1246.

[9]CaoFuyuan,HUANGJZ.Aconcept-drftingdetectionalgorithmforcategoricalevolvingdata[C].LectureNotesinComputerScience, 2013: 485-496.

[10] 邓大勇, 裴明华, 黄厚宽.F-粗糙集方法对概念漂移的度量[J].浙江师范大学学报(自然科学版), 2013, 36(3): 303-308.

[11] 邓大勇,徐小玉. 黄厚宽.基于并行约简的概念漂移探测[J].计算机研究与发展, 2015,58(5):582-587.

[12] 张任.基于模糊并行约简的模糊概念漂移探测[J]. 微型机与应用，2016,35(12):55-58.

[13] 刘盾，姚一豫，李天瑞.三支决策粗糙集[J].计算机科学，2011，38(1)：245-250.

[14]YaoYiyu.Probabilisticroughsetapproximations[J].InternationalJournalofApproximateReasoning,2008,49:255-271.

[15]LiuDun,LiHuaxiong,ZhouXxianzhong.Twodecades’researchondecision-theoreticroughsets[C].Proceedingof9thIEEEInternationalConferenceonCognitiveInformatics,2010.

[16] 李华雄，刘盾，周献中.决策粗糙集模型研究综述[J]. 重庆邮电大学学报(自然科学版)，2010，22(5)：624-630.

An implementation of Cloud-based video image recognition system

ZhangRen,WangHui

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,Jinhua321004,China)

Asthetimeforbigdataiscoming,thedatamininghasbeenahottopic.Theconceptdriftingisoneofchallengeswhichthedataminingfaces,andmoreandmorepeoplefocusonit.Amingattheproblemsthattheresearchontheconceptdriftingbasedontheclassicalroughsettheorydoesn’thavefault-toleranceandpaysnoattentiontotheconceptdriftingonboundaryregion,thispaperproposesdetectionalgorithmofconceptdriftingbasedonthree-waydecisionroughset,whichextendsthedetectionoftheconceptdriftingtothefieldofthree-waydecisionroughsetanddetectionofconceptdriftingonpositiveregiontotheoneonboundaryregion,andregardsthedecisiononboundaryregionasafeasibleandvaluableone.Thefault-toleranceisaddedtothealgorithmbyusingthecharacteristicthatthethree-waydecisionroughsetcanimitatetheindeterminacyandinaccuracyofhumanintelligence.Finallythefeasibilityofthealgorithmisvalidatedthroughtheexperiment.

theconceptdrifting;three-waydecisionroughset;datamining;fault-tolerance

TP

ADOI： 10.19358/j.issn.1674- 7720.2016.22.015

张任，王晖. 基于三支决策粗糙集的概念漂移研究[J].微型机与应用，2016,35(22)：54-60.

2016-06-16)

张任(1989-)，男，硕士研究生，主要研究方向：人工智能、数据挖掘。