基于Spark的CVFDT分类算法并行化研究
2018-06-20李玲娟
庄 荣,李玲娟
(南京邮电大学 计算机学院,江苏 南京 210023)
0 引 言
面对实时到达、连续、无限的流数据[1],传统的数据挖掘算法难以满足流数据挖掘的需求,因而流数据的分类挖掘[2]研究一直是热门话题并且具有重大意义。概念适应快速决策树算法(concept-adapting very fast decision tree,CVFDT)[3]是经典的流分类算法之一。CVFDT主要克服了VFDT(very fast decision tree)算法[4]对于数据样本的不断变化而不能更换模型的缺点,并且可以有效地解决概念漂移[5]的问题。与传统的静态大数据处理平台Hadoop[6]不同,Spark[7]扩展了广泛使用的MapReduce[8]模型,提出了基于内存的并行计算框架,通过将中间结果缓存在内存中以减少I/O磁盘操作,从而更高效地支持多次迭代式计算模式。为此,文中研究了基于Spark的CVFDT分类算法并行化,用以提高CVFDT算法对流数据的分类效率。
1 CVFDT算法分析
1.1 CVFDT简介
CVFDT属于一种增量式的分类挖掘方法,即用新到样本修正旧分类器,产生新分类器,以适应新环境。CVFDT在树的所有节点上维持统计信息用于计算基于属性值的信息增益测试,即统计测试,并基于Hoeffding不等式确定叶节点变成分支节点所需的样本数目,对数据流建立分类决策树。
以t为时间戳,xt表示t时刻到达的数据向量,数据流可表示为{…,xt-1,xt,xt+1,…}[9]。CVFDT算法的有关定义如下:


1.2 CVFDT算法流程
在拿到新的数据流样本后,从上到下遍历决策树,并在树的每个分支节点根据属性取值等判断进入不同的分支,最终到达树的叶节点。随着数据流样本的不断增多,信息增益测试为了满足一定条件,其叶节点必须要以较高的置信度确定最佳划分属性,从而变成一个分支节点,这样循环可以不断地决策学习新的叶节点。……
