基于Storm平台的流挖掘算法及抵抗概念漂移系统的设计与实现

陆元福++彭天慈++季开洋++谈海宇

摘要：随着云计算、物联网等技术的兴起，流数据作为一种新型的大数据形态广泛存在于各个邻域。该文提出面向大数据的基于分布式计算平台Storm的流分类挖掘算法及系统，采用并行化窗口和CVFDT算法，利用分布式平台来检测数据流中是否发生概念漂移，从而自适应的改变建模样本数据的流入，提高流数据模型的准确率和效率。

关键字：大数据；数据挖掘；分类算法；概念漂移

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）09-0011-03

Design and Implementation of Flow Mining Algorithm and Resistance Concept Drift System Based on Storm Platform

LU Yuan-fu， PENG Tian-ci， Ji Kai-yang， TAN Hai-yu

（College of Computer Science， Nanjing University of Posts and Telecommunications， Nanjing 210046， China）

Abstract：With the rise of cloud computing and Internet of things（LOT） technology，stream data widely exist in all fields as a new mega data form.This article propose a stream-classifying algorithm and system oriented to big data，which is based on DCP （Distributed Computing Platform）.Parallelize windows and CVFDT algorithm are both adopted.We use a DCP to test whether the mutation concept drift happened in data stream，so as to change the inflow of modeling sample data adaptively.The accuracy and efficiency of stream data model will be improved at last.

Key words： big data； data mining； classifying algorithm； concept drift

1 背景

随着云计算、互联网+等技术的快速发展，生产制造控制、无线通信网络、电子商务交易、金融信息监控等领域形成了高速、海量、动态的数据流，而有效的对数据流进行处理并从中挖掘有价值的信息就显得尤为重要。

在流数据分类挖掘中，概念漂移是指流数据特性的改变使得目标分类模型随着时间的变化而变化。针对流数据挖掘过程中的概念漂移问题，Hulten等人提出了概念自适应快速决策（Concept-adaptingVeryFastDecisionTree，CVFDT）算法[1]。CVFDT 算法是一种扩展了VFDT算法用以解决概念漂移问题的高效算法，通过在原有的算法基础上改进添加滑动窗口使得建立决策树模型的数据流能够不断实现更新，从而保证在概念漂移的数据流中模型建立的准确率。

本文主要讨论研究了基于分布式实时计算系统STORM平台的去概念漂移算法及系统的设计与实现，在流挖掘过程中，利用分布式平台的特点采用并行化窗口方案来检测数据流中是否发生概念漂移，并行化窗口bin-win根据数据流中的概念漂移自适应调整窗口大小，从而自适应的改变建模样本数据的流入，提高了流数据的准确性和高效性。

2 算法分析与实现

2.1 CVFDT算法

2.1.1 CVFDT算法的原理

概念自适应快速决策树（CVFDT）[2]是一种扩展了VFDT算法用以解决概念漂移问题的高效算法，具有类似VFDT的HT树生成过程，在保持了VFD的速度和精度的前提下，能够处理样本产生过程中所出现的概念漂移问题[3]。CVFDT对样本维持一个滑动窗口，并能够动态改变窗口的大小。CVFDT算法过程包括CVFDTGrow过程、ForgetExample过程、RemoveExample过程和CheckSplitValidity过程。算法主要思想是先根据当前的数据构建临时决策树，然后并不断地获取新的数据去优化已建立的决策树。若在某个时候出现了概念漂移，则算法会在出现漂移的节点上建立一个新的替代子树。当替代子树的分类效果优于当前的决策子树时，就直接取而代之。

2.1.2 CVFDT算法抵抗概念漂移问题

概念漂移表示目标变量的统计特性随着时间的推移以不可预见的方式变化的现象[4]。在流数据分类挖掘中，也指流数据特性的改变使得目标分类模型随着时间的变化而变化。CVFDT周期性的扫描HT生成树的内部节点来检验原先的分裂节点是否依然是最优的分裂属性节点。当该节点发生了概念漂移，最优分裂属性节点已不再是原先的Xa。CVFDT算法会重新寻找最佳测试属性，新的属性不直接取代原有的测试属性，而是成为一个替代子树的根节点，并且依据该根节点建立替代子树。如果后继滑动窗口的样本在替代子树上有较高的分类精度，则替代子树便取代原先的决策树，以维持滑动窗口的样本和更新后的决策树的一致性。

2.2 基于STORM平台的CVFDT算法实现

2.2.1 CVFDT并行化窗口抵抗概念漂移算法设计

本小节讨论以STORM作为分布式实时计算平台，结合CVFDT流挖掘算法，解决数据流的概念漂移问题，从而提高模型建立的准确性。基于storm分布式平台的并行化窗口抵抗概念漂移方案，通过并行化窗口bin-win对数据流实时检测实现概念漂移抵抗[5-6]，窗口调整流程图如图1所示。

从流程图中，可以看到并行化窗口根据数据流中的概念漂移自适应调整窗口大小，当窗口检测数据流未发生概念漂移时，则增大窗口中的样本量，反之，则减小并行化窗口的大小，有利于较快的适应概念漂移。

其中，检测是否发生概念漂移模块，通过对HT树中的非叶子节点的替代子树调用CheckSplitValidity函数，计算属性增益，从而判断是否发生概念漂移，流程图如图2 所示。

2.2.2 CVFDT算法实现与分析

在现实生活中，大部分数据都是非平稳分布的，数据流根据时间的推移不断发生变化，即发生了概念漂移[7]。CVFDT算法通过并行化窗口检测数据流是否发生概念漂移，窗口太大不能快速有效的抵抗数据流中的概念漂移，窗口太小影响模型建立的时间和模型一段时间内的稳定性，如图3所示在建立决策树模型时检测到概念漂移，则减小窗口的大小。当数据流稳定时，则增大窗口的大小，从而有效建立准确的决策树模型。

3 系统实现

3.1 系统总体架构

CVFDT算法在STORM平台上的实现方式有两种，一种是垂直并行化实现，一种是结合随机森林的实现，该抵抗概念漂移系统的设计主要基于垂直并行化的实现方式。系统包括三大模块：并行化窗口模块、抵抗概念漂移模块、决策树建立更新模块。系统整体框架如图4所示。

3.2 系统界面

抵抗概念漂移流分类挖掘系统参数设置界面如图5所示，用户输入训练样本、更新样本、测试样本以及样本所在文件的具体地址。点击确定之后传输相应参数，CVFDT算法执行结束之后，弹出该算法挖掘结果显示窗口，姐main如图6所示，结果展示界面输出当前决策树以及其评价结果，以及未分类样本的标记结果[8]。

4结束语

本文以分布式实时计算STORM平台，设计并实现CVFDT算法，解决在流数据挖掘过程中出现的概念漂移现象，保证了流数据分类挖掘模型的准确性和高效性。CVFDT算法对样本数据维持一个滑动窗口，在新样本到达的时候更新节点上的统计信息，并在样本滑出窗口的时候肩上其对应的统计信息。STORM平台保证算法能够提前预测数据流中的概念漂移，并实时更改窗口的大小，提高决策模型的准确性。

本文设计实现的算法与系统仅仅只是数据挖掘的一个方面，随着大数据时代的到来，数据流会越来越大，并且会不断变化，这就影响到了决策模型的建立与改善，因此，如何设计准确的算法和平台来彻底解决流数据的概念漂移仍然需要进一步的研究。

参考文献：

[1] Hulten G， Spencer L， and Domingos P. Mining time-changing data streams[C]//Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Francisco， California， USA， 2001： 97-106.

[2] Ganti V， Johannes Gehrke， Raghu Ramakrishnan. Mining Data Streams under Block Evolution. [J].SIGKDD Explorations， 2002， 3（2）.

[3]Street W N， Kim Y S. A streaming ensemble algorithm （SEA） for large-scale classification[C]//Proceedings of the seventh International Conference on Knowledge Discovery and Data Mining. San Francisco， USA， 2001： 377-382.

[4] Mitchell T M. Machine learning[M]. New York City： McGraw-Hill， 1997.

[5] 杨雅双. 关联规则的并行挖掘算法研究[D]. 西安：西安科技大学，2010.

[6] 唐耀红. 数据流环境中关联规则挖掘技术的研究[D]. 北京：北京交通大学，2012.

[7] Gama J. A survey on learning from data streams： current and future trends[J]. Progress in Artificial Intelligence， 2011，1（1）： 45-55.

[8] 李明， 王晓鹏. Strom《源码分析》[M]. 北京： 人民邮电出版社， 2014.