张发扬，李玲娟，陈 煜

(南京邮电大学计算机学院，江苏南京 210003)

VFDT算法基于Storm平台的实现方案

张发扬，李玲娟，陈 煜

(南京邮电大学计算机学院，江苏南京 210003)

以提升流数据的分类效率为目标，研究如何在流数据处理平台Storm上实现快速决策树算法-VFDT。设计了VFDT基于Storm的分布式并行化实现方案，将VFDT算法分为建树、分类和评价共三个模块，建树模块负责决策树的初始化和增量建树，分类模块负责对待分类样本进行分类标记，评价模块负责用已标记的样本对VFDT决策树进行评价。通过正确设计Storm拓扑中的Spout/Bolt实现各模块的功能，通过为分类Bolt设定多个Task来实现分类模块的并行化;用内存数据库Redis实现三个模块的有效衔接和决策树的保存;用消息中间件Kafka来提高算法对流数据突增的容忍度。基于该方案的VFDT算法实现与测试结果表明:在Storm集群环境下的VFDT算法分类效率相对于单机环境有显著提高，而且合理设定分类Bolt的Task数可使分类效率进一步提高。

流数据;快速决策树算法;分布式;并行化;Storm

0 引言

20世纪末，为适应网络监控、入侵检测、情报分析、商业交易管理和分析等应用的要求，数据流技术应运而生［1］。数据流中的数据(即流数据)是有序的、连续的且不断变化的，甚至是无限的［2］，不能像传统的静态数据一样将其存储在硬盘或者内存之中，即再次处理这些数据的代价将非常昂贵。

流数据挖掘是指从快速、大量、连续的数据流中挖掘出有价值的信息。数据流具有快速、连续、大量的特点，传统数据挖掘(Data Mining，DM)算法难以对流数据进行有效的挖掘。……