大数据分类挖掘算法及其概念漂移应用研究*

陆莉莉，张永潘，谈海宇，季一木

1.南京信息职业技术学院 计算机与软件学院，南京 210023

2.南京邮电大学 计算机学院，南京 210023

大数据分类挖掘算法及其概念漂移应用研究*

陆莉莉1+，张永潘2，谈海宇2，季一木2

1.南京信息职业技术学院 计算机与软件学院，南京 210023

2.南京邮电大学 计算机学院，南京 210023

LU Lili,ZHANG Yongpan,TAN Haiyu,et al.Research on classification algorithm and concept drift based on big data.Journal of Frontiers of Computer Science and Technology,2016,10(12):1683-1692.

随着大数据应用研究的不断深入和分布式机器学习中流计算框架的涌现，针对数据流中概念漂移问题的研究是面向大数据挖掘领域的研究热点之一。现有的针对概念漂移的研究成果主要还是依赖于数据结构和算法优化，通过计算资源有限的独立计算机完成概念漂移的检测。为此，提出一种面向大数据的基于Storm的抵抗概念漂移的分类挖掘算法S-CVFDT（Storm-concept very fast decision tree）及系统。该系统采用并行化窗口和S-CVFDT算法，利用并行化窗口机制检测数据流中的突变型概念漂移，从而自适应地改变并行窗口大小，并通过S-CVFDT算法不断更新渐进性概念漂移时的模型。分析与实验结果表明，该算法可以快速有效地检测到突变型概念漂移，降低系统因为突变型概念漂移造成的资源浪费，且模型建立效率、分类精度得到提高。

大数据；数据挖掘；分类算法；概念漂移

1 引言

随着物联网、社交网络、云计算等技术不断融入人们的生活，以及现有的计算能力、存储空间、网络带宽的高速发展，人类积累的数据在互联网、通信、金融、商业、医疗等诸多领域不断地增长和累积[1]。互联网搜索引擎支持的数十亿次Web搜索每天处理数万TB数据。全球主干通信网每天传输数万TB数据。大型商场遍及世界各地的数以千计的门店每周都要处理数亿交易。医疗行业每天的医疗记录、病人资料和医疗图像每天也都产生大量的数据。数据的爆炸式增长、广泛可用和巨大数量使得真正的大数据时代到来。对于这些数据，人们不仅希望能够从中提取出有价值的信息，更需要发现对决策提供有效支持的更深层次的规律。

大数据挖掘的目的就是为了从海量的实时数据中挖掘出隐含在其中的用户感兴趣的有价值信息，再将挖掘所得到的信息转化成有组织的知识以模型等方式表示出来，最后将分析模型应用到现实生活中，从而提高效率，优化方案。大数据具有规模性（volume）、多样性（variety）、高速性（velocity）和准确性（veracity）4个特点[2]，其前期研究工作主要集中在规模性和多样性上展开。目前广泛存在并应用的数据是像金融、交通等场景下产生的流式数据，流式数据不同于传统的静态数据形态，作为一种新型大数据的数据形态，更多地体现了大数据要求的高速和准确的特点。流式数据需要人们从海量信息中更快地提取有用的信息。因此，基于大数据的实时数据挖掘研究显得尤为重要。流式数据分为稳定数据流和动态数据流，稳定数据流[3]中的数据具有稳定独立同分布的特点，而动态数据流是不独立同分布的，因此会产生概念漂移。

分类是一种通过提取重要数据类模型从而进行数据分析的形式。分类挖掘算法作为一种有监督学习的算法，通过对已知类别的训练集建立模型，从而预测新的数据集的类别，分类方法包括贝叶斯网络、决策树归纳、神经网络等。分类挖掘算法广泛应用在传感器网络、网络入侵检测、电话呼叫日志、银行风险评估等场景中。这些场景下的数据往往随着时间不断产生，而且数据量大，数据模型可能发生变化[2]。如大型商场中顾客的购物倾向会随着时间发生变化，网络安全中对入侵检测也随着用户不同而变化，工业生产中有问题的产品往往是相近的问题，然而共性的问题特征也是不断变化的。社交网络中用户行为将随着位置信息发生改变。

流式数据有数据量大，数据不断产生，并且可能发生概念漂移3个特点。因此基于大数据的分类挖掘算法不仅需要对发生概念漂移的数据具有很高的灵敏度，并且需要对最新的数据尽早做出判断，从而对模型进行自适应的调整。概念漂移是数据挖掘中一个需要重点研究的问题。目前的数据挖掘算法大多数都是针对静态数据的，因此本质上都不具有抵抗流式数据概念漂移的能力。现有的数据挖掘系统不能实时更新数据，并且不能自适应计算模型，或者不能保持原本建立的模型[4]。

文献[3]首次提出“概念漂移”的概念后，国内外的数据挖掘研究人员对概念漂移分别展开了深入研究。其中，文献[5]通过时间序列分析方法，根据概念漂移发生的时间序列分为突变型概念漂移、渐变型概念漂移、重复型概念漂移、增量型概念漂移，并建立了滑动窗口和分类错误率的理论模型。文献[6]提出了数据流分类挖掘算法，对数据的处理需要考虑有限内存、时间序列和单次处理的特点。文献[7]根据环境变化引起的概念漂移将漂移分为虚漂移和实漂移。学术界在数据挖掘的抵抗概念漂移研究中，一方面通过改进单个分类器来解决数据概念漂移的问题，如文献[8]的COBBIT、文献[9]的CD3（concept drift）、文献[10]的CVFDT；另一方面，研究人员通过集成分类器更新分类模型来提高分类精度和泛化能力。如文献[11]提出的通过评估分类器精确度的阈值来不断更新基分类器，从而不断提高整体抵抗概念漂移的SEA（streaming ensemble algorithm）算法，缺点是该系统因为基分类器更新速度较慢，所以不适合突变性概念漂移。文献[12]提出了对SEA改进的对基分类器设置权值的AWE算法。文献[13]提出了一个能提高分类器反应速度的在线学习分类器ACE（adaptive classifiers-ensemble）算法。文献[14-15]提出通过动态调整各基分类器的权值来提高分类性能。文献[16-17]提出根据boosting算法思想，通过带有权值的基分类器多数投票的机制，并动态增加投票精确度高的分类器，删除投票精确度低的分类器来提高分类效果。文献[18]研究了数据流中的样本之间发生概念漂移的最大差值。文献[19]通过利用Peano数据结构模型证明了决策树分类方法适用于动态数据流。文献[20]通过决策树模型检测数据子集，从而实现数据块操作的模型。文献[3]提出基于hoeffding树的决策树分类算法VFDT（very fast decision tree），该算法通过统计每个节点中样本属性的信息增益来选择最佳分裂节点。对于数据流挖掘中概念漂移的研究，主要提出了评估数据集实时性权重和滑动窗口两种策略。如文献[21]提出根据样本的生存时间，利用衰减函数来评估样本的实时性的抵抗概念漂移策略，建模数据项的实时性要求根据其衰减函数来决定。文献[22-24]提出利用可变的窗口尽可能地维持样本，但是需要使用者提供未知的先验参数，如概念漂移的时间尺度。在抵抗概念漂移的系统设计中，广泛得到认可的系统有Last提出的OLIN（on line information network）[25]、Gama等人提出的UFFT（ultra fast forest of trees）[26]、Domingos等人提出的CVFDT[10]。

2 相关研究

2.1 OLIN

文献[25]中Last提出了一种使用IFN（info-fuzzy network）网络的在线分类系统，该系统又称为OLIN，其根据动态数据流上的最新样本建立滑动窗口。系统动态调整训练样本窗口的大小，并且根据概念漂移发生的频率动态更新模型。OLIN系统将训练样本之间的概念漂移统计显著性差异以及最新模型的预测准确率作为动态数据流是否发生概念漂移的标志。OLIN在重构模型过程中启发式动态调整样本数，如果概念未发生漂移，则增加当前模型建立所需的样本。如果检测到发生概念漂移，则减小窗口的大小，从而减少样本。OLIN为每个新的滑动窗口建立一个新的模型。这个方法保证了随着时间的推移，分类精度也能提高。但是OLIN算法有一个主要的缺点：生成新的模型时将产生很高的内存开销，OLIN不考虑新的模型替代原有模型的开销。

2.2 UFFT

Gama等人提出极速算法UFFT[26]。UFFT是基于二叉树森林的有监督的分类学习算法。UFFT是增量式且在恒定时间内处理每个样本，利用分析技术来选择分裂标准处理连续数据流，通过信息增益评估每个可能分裂测试节点的好坏。对于多类的问题，算法为每一对可能相近的类建立一个二叉树，从而构造一个树的森林。UFFT算法在样本训练期间保持一个暂时的内存，保证给定数据流中有限的最新样本固定时间内保存在数据结构中来支持插入和删除。当测试节点一旦建立，叶子节点就变成带有两个子叶子节点的决策节点。通过短期内存中的样本量初始化每个叶子节点的统计信息。UFFT算法在决策树的每个节点上保持一个朴素贝叶斯分类器。通过样本统计值建立的分类器在变成叶子节点时需要根据分裂准则评估其是否符合分裂要求。叶节点变成决策节点后遍历节点的所有样本，将通过朴素贝叶斯分类器进行分类。概念漂移探测方法最基本的思想是控制错误率。如果未发生概念漂移，朴素贝叶斯分类器的错误率会降低。发生概念漂移后，朴素贝叶斯的错误率将上升。当探测到给定节点的分类错误显著上升时，表明现有的分裂节点不再合适。原来节点下的子树将被修剪并重新变为叶子节点并重新初始化。

Table 1 Difference of VFDT and CVFDT表1 VFDT和CVFDT的异同点

2.3CVFDT

Hulten等人提出扩展VFDT的概念漂移自适应快速决策树算法CVFDT[10]，VFDT算法和CVFDT算法的异同点如表1所示。

表1中，m为VFDT中决策树的节点个数；N为CVFDT中决策树和替代子树的节点个数；d为属性个数；V为每个属性值的最大值；C为类的个数。

CVFDT根据滑动窗口中的数据流样本来持续检测旧的决策树的有效性，从而保证建立模型与概念漂移同步。当发现数据流发生概念漂移时，将以细粒度的方式更新它们。特别是每次选择最佳属性时都为每个候选属性保留足够的统计样本时间。当新的样本加入到窗口时，从属性统计值中减去旧的样本数的统计值。每当有Δn个新的样本进入时，CVFDT在原先每个决策点重新决定最佳候选属性。如果候选属性中有一个比原先的决策属性要好，则表明原先的决策不正确或者概念发生漂移。不管是原先的分裂属性不正确，还是概念发生漂移，都会在继续原先属性分裂的同时，新的属性开始寻找分裂属性。在不断的树增长过程中，新的决策属性产生时就相应地产生其替代子树。通过周期性地使用新的样本作为验证集来比较新的决策树和旧的决策树的分类效果。如果新的决策树模型比旧的模型更准确，CVFDT修剪旧树（用新的替代子树替换）。当新的决策树模型在最大数量的检验样本集检验下分类效果仍不如旧的决策树模型，那么建立的新的决策树模型也会被修剪。如果不只一个新的决策树模型，那么将会修剪分类效果最差的那个。CVFDT算法过程包括CVFDTGrow过程、ForgetExample过程、Remove Example过程和CheckSplitValidity过程。

3 基于Storm的S-CVFDT抵抗概念漂移算法

基于Storm的S-CVFDT抵抗概念漂移算法如图1所示，并行化窗口bwin根据数据流中的概念漂移自适应调整窗口大小。当并行化窗口检测数据流未发生概念漂移时，则增大窗口中的样本量，有利于快速建立分类模型。当并行化窗口检测数据流发生概念漂移时，则减小并行化窗口的大小，有利于较快地适应概念漂移。基于Storm的S-CVFDT算法的建树过程在每个决策节点建立替代子树，通过CheckSplit-Validity检测替代子树的准确率，当替代子树的准确率高于旧的子树，则替换之。通过维持一个滑动窗口，不断抛弃旧的样本，添加新的样本，不断更新分类树模型。基于大数据的流数据中主要包含突变式概念漂移和渐变式概念漂移，当数据流具有突变式概念漂移特点时，将需要频繁调用CVFDT算法中的检测替代子树准确率模块，从而增加了内存消耗，降低了分类决策树的建立模型效率。而S-CVFDT算法通过并行化窗口bwin，将能够自适应地根据数据流中的概念漂移，特别是突变型概念漂移来调整窗口的大小，从而有效解决系统针对突变型数据流时频繁更新建树模型，调用决策节点测试模块和资源利用率等问题。

4 基于Storm的抵抗概念漂移系统S-CVFDT

4.1 抵抗数据流概念漂移系统模块设计

面向大数据的数据挖掘算法中，为了使得模型能够抵抗数据流发生的概念漂移，通常需要3个特点：（1）添加新的样本、释放旧的样本的窗口；（2）探测数据流输入端发生概念漂移的方法；（3）对输入的最新样本能够不断更新模型。抵抗数据流概念漂移系统通常包括3个模块：样本窗口模块、探测概念漂移模块和概念漂移评价模块，如图2所示。

①数据流分为子数据流stream1和子数据流stream2，分别添加到并行化窗口bwin1和bwin2中。

②概念漂移探测模块根据概念漂移阈值判断数据流是否发生概念漂移。

③如果发生概念漂移，则建模窗口控制模块减小窗口的大小以抵抗概念漂移。如果未发生概念漂移，则增大窗口大小，提高建模效率。

④根据建模窗口中的样本数据流建立决策树模型。

⑤周期性地比较决策树模型中替代子树和原有属性节点的分类精度，如果替代子树的精度高于原有子树，则替换之。

Fig.1 Parallel window S-CVFDT algorithm to resist concept drift图1 基于Storm的并行化窗口S-CVFDT抵抗概念漂移算法

Fig.2 Frame of data mining for concept drift data stream图2 流数据挖掘抵抗概念漂移框架图

4.2 基于Storm的抵抗概念漂移并行化窗口bwin（bolt-window）

Storm是利用类MapReduce编程模型来处理流数据的分布式流计算框架。Storm主要用来对流数据进行实时分析。比如Twitter使用Storm来查找最新流行的话题和故事，利用对tweet博客查找结果的排序实现在线学习或者对广告实时分析并生成内部日志。Storm相对于HadoopMapReduce的优点是其处理流数据的灵活性。实际上HadoopMapReduce在处理数据流时很复杂而且易错。Storm提供了“至少一次”消息处理机制，且支持水平扩展。Storm因为没有中间队列，所以意味着操作开销更少，更重要的是，Storm平台的“justworks”机制保证了处理数据的容错。Storm最基本的元素包括streams、spout、bolts和拓扑。Storm中的流实际上是元组的无限序列。元组是值的列表，每个值只要可以序列化，就可以赋值为任何类型。Storm是动态匹配类型，也就是说值的类型不需要声明。spout是Storm的数据源，通常从如kestrel/kafka、http服务器日志或者Twitter流APIs这样的外部数据源读取数据。Storm中的bolt是一个或者多个输入流的具体执行者。bolt能执行多个功能，如过滤元组、聚合元组、join多个数据流以及和外部件通信（如缓存或数据库）。Storm在spout和bolt之间利用拉取方式传递元组，bolt从源件（bolt或者spout）拉取元组进行处理。这个特性可以保证当拓扑系统不能实时处理外部事件时，元组的丢失只会发生在spout。Storm中spout、bolt和流组成拓扑的是一个有向无环图。

基于Storm的并行化窗口探测概念漂移模块如图3所示，将数据流分为子数据流stream1和子数据流stream2，分别添加到并行化窗口bwin1和bwin2中。通过检测概念漂移窗口算法的bolt，来检测数据流是否发生概念漂移，并将结果传递到结果bolt中。

4.3 基于Storm的并行化系统S-CVFDT

基于Storm的并行化系统S-CVFDT由并行窗口模块、概念漂移探测模块、S-CVFDT建树模块以及模型评价模块组成，如图4所示。数据流通过spout从外部数据源读入。概念漂移探测模块由并行窗口bolt和漂移探测bolt组成，其中根据并行化窗口算法通过探测bolt将控制信息返回到并行窗口模块中，从而自适应调整并行化窗口的大小。S-CVFDT采用垂直并行设计。垂直并行更适合于具有很多属性的实例，因为它把大部分的时间开销用在每个属性的信息增益的计算上。相比于水平并行，它占用更少的内存，因为它不需要在每一个bolt复制模型。建树模块的第一个bolt负责接收并行化窗口的数据，并将数据流传递到分发bolt；分发bolt将统计信息分发到每一个独立计算bolt，并且计算信息增益；最后将聚集独立bolt的统计信息得到最终的决策树。由于原有的CVFDT算法在样本具有大量属性的情况下，在属性增益的计算中耗费大量计算资源，从而降低建树效率，S-CVFDT算法建树模块部分主要将Storm的分布式和并行化的流数据处理方式应用于系统中，用户通过设置独立bolt的个数处理样本属性，从而调整系统并行度，提高建树效率。

Fig.3 Detection module for concept drift based on Storm by parallel window图3 基于Storm的并行化窗口探测概念漂移模块

Fig.4 Parallel system S-CVFDT for concept drift based on Storm图4 基于Storm的并行化系统S-CVFDT

5 实验仿真与验证

5.1 基于Storm的S-CVFDT分类挖掘系统

基于Storm的流分类挖掘系统，既解决了由于传统的流数据挖掘单机系统不能实现分布式计算信息熵从而提高效率的问题，同时通过并行化窗口的方案有效地抵抗了由于数据流概念漂移导致的模型准确率下降，系统资源消耗过高等问题。

基于Storm的S-CVFDT整体系统框架如图5所示。

Fig.5 S-CVFDT system frame based on Storm图5 基于Storm的S-CVFDT整体系统框架图

（1）对带有标签属性的流式数据样本集进行有监督的学习，实现增量建树，并实时监控概念漂移，形成不断更新的分类决策树模型，以内存数据库Redis作为消息中间件保存不断更新的决策树模型。

（2）从Redis中取出实时决策树模型，并利用数据流中的测试样本集来测试决策树模型的准确率。

（3）从Redis中取出符合准确率要求的决策树模型对未知标签的样本数据流进行预测分析，并输出分类结果。

5.2 S-CVFDT算法系统拓扑设计

基于Storm的抵抗概念漂移流分类挖掘算法并行化拓扑的构建过程如下：

（1）创建基于Storm的由spout和bolt组成的流分类分布式计算拓扑，设置喷发节点spout和计算节点bolt的逻辑关系。

（2）配置拓扑数据源和数据处理节点，设置数据计算节点并发数以及随机的数据分发处理方式。

（3）设置DSourceSpout读取数据源数据，并将数据源的属性信息发送给ReadAttBolt，数据源属性管理模块ReadAttBolt提取数据源中的属性，数据源的属性值信息发送给概念漂移探测模块BwinDetector-Bolt。

（4）BwinDetectorBolt接受DSourceSpout的数据源信息，探测是否发生概念漂移，从而控制窗口window Size，当数据流速率过高时，可以增加并发数来提高探测效率。

（5）S-CVFDTBolt初始化窗口W、各项参数和初始的决策树模型，并将模型及各项参数发送给CheckingSplitNodeBolt。

（6）Att_midBolt接受ReadAttBolt提取数据源中的属性，计算数据流样本中所有属性的个数，并将每个属性打上标签，分发给CheckingSplitNodeBolt。

（7）因为基于数据流的流分类挖掘算法中样本的属性增益将是系统资源消耗的绝大部分，所以通过垂直并行化来计算属性熵增益。CheckingSplitNode-Bolt根据数据源样本的属性个数设置并发数，计算结果保存在Map＜key,value＞中，其中key代表是哪个属性，value代表该属性的信息增益值，将计算结果发送给ChooseMaxBolt。

（8）ChooseMaxBolt对Map中的所有属性对应的value值进行排序，找出最大和次大的＜key，value＞即可确定决策节点进行分裂。

（9）更新决策树，并将最新的决策树模型写入到Redis中。

（10）同时建立测试和分类拓扑，并通过拓扑中的EvaSpout分发测试数据源，DataSpout分发分类数据源，并分别从Redis中取出最新决策树分类模型到classifyBolt中进行评估和分类。

5.3 系统的实现与分析

假设n为决策树和替代子树节点的个数，d为样本属性的个数，v为属性值的最大个数，c为类的个数，则CVFDT算法的复杂度为O(ndvc)。因为CVFDT算法系统除了要存储决策树的数据结构以外，还包括处理样本的存储空间，假设样本的大小为e，窗口的大小为w，所以CVFDT系统实际的空间复杂度为O(ndvc+we)。而因为S-CVFDT算法的窗口是自适应指数调整的，所以其空间复杂度是O(ndvc+elogw)。当数据流数据量很大时，空间复杂度呈指数减小。

概念漂移广泛存在现实数据流中，数据流决策树分类算法CVFDT能够很好地解决概念漂移问题，但是因为其设计处理概念漂移机制时并不考虑概念漂移的类型，只是采用普适的方法，从而效率较低。本文提出的基于分布式计算平台Storm的并行窗口算法设计不仅能够有效检测数据流中的概念漂移，从而自适应改变窗口提高其建立模型的准确率，也通过分布式计算平台强大的计算能力，从而减小属性信息熵的计算时间，提高效率。

在分类算法研究中，分类器的性能评估是重要的一部分。在训练样本上有很高性能的分类器在测试样本中未必能收到同样的结果。本文采用的是在大部分数据挖掘评估中广泛使用的十字交叉验证法。误差率在分类算法的分类器设计中是一个重要的评估指标。分类器对测试样本进行预测，如果正确，则分类成功，否则分类错误。通过建立决策树评价拓扑将测试样本通过evalspout发送数据流到evalbolt进行评估，并输出分类器的误差率。以下选取在流分类挖掘实验中使用较广泛的概念漂移数据流Hyperplane[27]作为算法性能实验的数据源，其通过逐渐改变连续样本的决定边界来实现增量的概念漂移数据流。Hyperplane通过改变每个样本0.01的修正权重值来实现漂移。另外数据集包含5%的噪声，噪声通过人为对样本加上错误的类标签实现。Hyperplane包含10 000个样本和10个维度。如图6所示，当样本数较少时，S-CVFDT算法决策树模型的准确率和CVFDT算法准确率相差不大，但是S-CVFDT算法随着样本的增加，模型建立的准确率不断提高。

Fig.6 Comparison of accuracy between CVFDT algorithm and S-CVFDT algorithm图6 S-CVFDT算法与CVFDT算法准确率比较

由于S-CVFDT具有并行窗口抵抗渐进型概念漂移的机制，当数据流概念发生漂移时，可以发现SCVFDT算法的准确率虽然有所下降，但是能够很快恢复，并且当样本数越大时能保持比CVFDT较高的准确率，如图7所示。

Fig.7 Comparison of accuracy between CVFDT algorithm and S-CVFDT algorithm based on concept drift图7 S-CVFDT算法与CVFDT算法发生概念漂移时准确率比较

CVFDT算法单机情况下：每秒处理的待分类样本数目在10 000～15 000条，而S-CVFDT算法基于分布式平台Storm下每个分类拓扑每秒可处理的待分类样本数目在20 000～30 000条，当分类样本数量倍增时，可以增加分类处理bolt，从而提高分类效率。并且决策树模型不断从Redis中读取更新最具实时性的分类模型，从而保证模型的准确率。

6 结束语

本文基于分布式计算平台Storm提出了一种新的并行化窗口检测和抵抗概念漂移的面向大数据的分类算法S-CVFDT，该算法利用并行化窗口中数据流分布的变化检测突变型概念漂移，并通过垂直并行化改进CVFDT算法，从而实现模型的不断更新和效率优化。实验分析表明，与传统单机检测概念漂移和建立模型相比，S-CVFDT算法具有较优的概念漂移检测能力和分类准确率。而与已有的概念漂移分类算法相比，S-CVFDT算法在分类正确率、抗噪性等方面表现优越。然而，该系统如何引入随机森林决策投票机制，以及如何检测数据流中的噪声和误报，以及分类拓扑并行化是下一步的研究目标和方向。

[1]Bryant R E,Katz R H,Lazowska E D.Big-data computing:creating revolutionary breakthroughs in commerce,science, and society[R/OL].AWhite Paper Prepared for the Computing Community Consortium Committee of the Computing Research Association(2008)[2016-06-17].http://cra.org/ccc/ resources/ccc-led-whitepapers/.

[2]Mitchell T M.Machine learning[M].New York:McGraw-Hill,1997.

[3]Domingos P,Hulten G.Mining high-speed data stream[C]// Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Boston, USA,Aug 20-23,2000.New York:ACM,2000:71-80.

[4]Grossberg S.Nonlinear neural networks:principles,mechanisms and architecture[J].Neural Network,1988,1(1):17-61.

[5]Kuncheva L I.Classifier ensembles for changing environments[C]//LNCS 3077:Proceedings of the 5th Workshop on Multiple Classifier Systems,Cagliari,Italy,Jun 9-11,2004. Berlin,Heidelberg:Springer,2004:1-15.

[6]Gama J.A survey on learning from data streams:current and future trends[J].Progress in Artificial Intelligence,2012,1 (1):45-55.

[7]Widmer G,Kubat M.Effective learning in dynamic environments by explicit context tracking[C]//LNCS 667:Proceedings of the 6th European Conference on Machine Learning, Vienna,Austria,Apr 5-7,1993.Berlin,Heidelberg:Springer,1993:227-243.

[8]Kilander F,Jansson C.COBBIT—a control procedure for COBWEB in the presence of concept drift[C]//Proceedings of the 6th European Conference on Machine Learning,Helsinki,Finland,1993.Berlin,Heidelberg:Springer,1993: 244-261.

[9]Black M,Hickey R J.Maintaining the performance of a learned classifier under concept drift[J].Intelligent Data Analysis,1999,3(6):453-474.

[10]Hulten G,Spencer L,Domingos P.Mining time-changing data streams[C]//Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,San Francisco,USA,Aug 26-29,2001.New York: ACM,2001:97-106.

[11]Street W N,Kim Y S.A streaming ensemble algorithm (SEA)for large-scale classification[C]//Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,San Francisco,USA, Aug 26-29,2001.New York:ACM,2001:377-382.

[12]Wang Haixun,Fan Wei,Yu P S,etal.Mining concept-drifting data streams using ensemble classifiers[C]//Proceedings of the 9th International Conference on Knowledge Discovery and Data Mining,Washington,Aug 24-27,2003.New York: ACM,2003:226-235.

[13]Kyosuke N,Koichiro Y,Takashi O.ACE:adaptive classifiersensemble system for concept-drifting environments[C]// LNCS 3541:Proceedings of the 6th International Workshop on Multiple Classifier Systems,Seaside,USA,Jun 13-15, 2005.Berlin,Heidelberg:Springer,2005:176-185.

[14]Elwell R,Polikar R.Incremental learning of concept drift in nonstationary environments[J].IEEE Transactions on Neural Networks,2011,22(10):1517-1531.

[15]Muhlbaier M D,Polikar R.Multiple classifiers based incremental learning algorithm for learning in nonstationary environments[C]//Proceedings of the 2007 IEEE International Conference on Machine Learning and Cybernetics,Hong Kong,China,Aug 19-22,2007.Piscataway,USA:IEEE, 2007:3618-3623.

[16]Kolter J Z,Maloof M A.Dynamic weighted majority:a new ensemble method for tracking concept drift[C]//Proceedings of the 3rd IEEE International Conference on Data Mining,Melbourne,USA,Dec 19-22,2003.Washington: IEEE Computer Society,2003:123-130.

[17]Kolter J Z,Maloof M A.Using additive expert ensembles to cope with concept drift[C]//Proceedings of the 22nd International Conference on Machine Learning,Bonn,Germany, Aug 7-11,2005.New York:ACM,2005:449-456.

[18]Barve R D,Long P M.On the complexity of learning from drifting distributions[J].Information and Computation,1997, 138(2):170-193.

[19]Ding Qiang,Ding Qin,Perrizo W.Decision tree classification of spatial data streams using peano count trees[C]//Proceedings of the 2002 ACM Symposium on Applied Computing,Madrid,Spain,Mar 2002.New York:ACM,2002: 413-417.

[20]Ganti V,Gehrke J,Ramakrishnan R.Mining data streams under block evolution[J].ACM SIGKDD Explorations Newsletter,2002,3(2):1-10.

[21]Cohen E,Strauss M.Maintaining time-decaying stream aggregates[C]//Proceedings of the 22nd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, San Diego,USA,Jun 9-12,2003.New York:ACM,2003: 223-233.

[22]Gama J,Medas P,Castillo G,et al.Learning with drift detection[C]//LNCS 3171:Advances in Artificial Intelligence, Proceedings of the 17th Brazilian Symposium on Artificial Intelligence,Sao Luis,Brazil,Sep 29-Oct 1,2004.Berlin, Heidelberg:Springer,2004:286-295.

[23]Klinkenberg R,Joachims T.Detecting concept drift with supportvector machines[C]//Proceedings of the 17th International Conference on Machine Learning,Stanford,USA, Jun 29-Jul 2,2000.San Francisco,USA:Morgan Kaufmann Publishers Inc,2000:487-494.

[24]Widmer G,Kubat M.Learning in the presence of concept drift and hidden contexts[J].Machine Learning,1996,23(1): 69-101.

[25]Last M.Online classification of nonstationary data streams [J].Intelligent DataAnalysis,2002,6(2):129-147.

[26]Gama J,Medas P,Rocha R.Forest trees for on-line data[C]// Proceedings of the 2004 ACM Symposium on Applied Computing,Nicosia,Cyprus,Mar 14-17,2004.New York: ACM,2004:632-636.

[27]Lin C H,Chi C Y,Wang Y H,et al.A fast hyperplane-based minimum-volume enclosing simplex algorithm for blind hyperspectral unmixing[J].IEEE Transactions on Signal Processing,2016,64(8):1946-1961.

LU Lili was born in 1978.She received the M.S.degree in computer software and theory from Nanjing University of Posts and Telecommunications in 2008.Now she is a lecturer at Nanjing College of Information Technology.Her research interests include cloud computing and big data,etc.

陆莉莉（1978—），女，江苏南通人，2008年于南京邮电大学计算机软件与理论专业获得硕士学位，现为南京信息职业技术学院讲师，主要研究领域为云计算，大数据等。

ZHANG Yongpan was born in 1994.He is an M.S.candidate at Nanjing University of Posts and Telecommunications.His research interest is data mining in big data.

张永潘（1994—），男，安徽宣城人，南京邮电大学硕士研究生，主要研究领域为大数据挖掘。

TAN Haiyu was born in 1987.He is an M.S.candidate at Nanjing University of Posts and Telecommunications.His research interest is data mining in big data.

谈海宇（1987—），男，江苏盐城人，南京邮电大学硕士研究生，主要研究领域为大数据挖掘。

JI Yimu was born in 1978.He received the Ph.D.degree from Nanjing University of Posts and Telecommunications in 2008.Now he is a professor at Nanjing University of Posts and Telecommunications.His research interests include P2P network optimization,cloud computing security and stream data query in big data,etc.

季一木（1978—），男，安徽无为人，2008年于南京邮电大学通信与信息系统专业获得博士学位，现为南京邮电大学教授，主要研究领域为P2P网络优化，云计算安全，大数据流查询挖掘等。

Research on ClassificationAlgorithm and Concept Drift Based on Big Data*

LU Lili1+,ZHANG Yongpan2,TAN Haiyu2,JI Yimu2
1.Institute of Computer&Software,Nanjing College of Information Technology,Nanjing 210023,China
2.School of Computer Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China
+Corresponding author:E-mail:lull@njcit.cn

With the deepening research of the application on big data and the emergence of more and more distributed computing framework,the research on concept drift in data stream becomes one of the research highlights in data mining for big data.The existing research on concept drift mainly depends on the data structure and algorithm optimization, the calculation mainly depends on the sole computer and limited resources to complete concept drift detection.Thus, this paper proposes a classification mining algorithm and system for big data based on Storm to resist concept drift. The S-CVFDT(Storm-concept very fast decision tree)algorithm system uses the parallel window mechanism to detect mutant concept drift in data stream and adaptively changes the parallel window size so as to update S-CVFDT algorithm model.The experimental analysis and results show that the algorithm can effectively detect mutant concept drift and lower the system resources waste.Not only the modeling is more efficient,but also the classification accuracy is improved.

big data;data mining;classification algorithm;concept drift

10.3778/j.issn.1673-9418.1608039

A

TP393

*The Youth Fund of Natural Science Foundation of Jiangsu Province under Grant No.BK20130876(江苏省自然科学基金青年基金);the Research Foundation of Nanjing College of Information Technology under Grant No.YK20140402(南京信息职业技术学院科研基金).

Received 2016-08,Accepted 2016-10.

CNKI网络优先出版:2016-10-19,http://www.cnki.net/kcms/detail/11.5602.TP.20161019.1458.006.html