Hadoop数据挖掘并行算法框架

论文提出了hadoop云平台实现数据挖掘并行算法的编程框架。首先对数据挖掘算法和应用和原理进行了分析，然后介绍了Map/Reduce并行编程流程，从input split，到map（）的（key，value），和reduce对（key，list{value}）的简答计算。详细设计了数据挖掘算法的通用Map/Reduce编程框架，分析了算法关键技术。最后应用在sprint和k-mean算法上，实验结果说明hadoop云平台能实现数据挖掘并行算法，提高加速比。

【关键词】数据挖掘 Map/Reduce 并行计算

数据挖掘是知识发现KDD的关键环节，并且在连续数值、异构数据、计算模型等方面有发展。知识挖掘是在大量数据中发现有效的、新颖的、有用的以及最终可理解知识的非平凡过程，所用到的技术包括统计学、数据库、数值计算、机器学习和算法。数据挖掘技术包括关联发现、分类器、聚类算法和序列模式等，它们的应用分别是：分类算法用在客户分类、目标市场选择、异常分析（信用卡欺诈等）；聚类算法用在市场销售、土地使用、金融领域，互联网WWW，地震防灾、图像处理；关联规则用在购物篮分析、交叉销售、产品目录设计；序列模式应用在客户购买行为模式预测、自然灾害预测、DNA序列分析、工业控制。

分类算法包括两个步骤，首先对训练数据集建立分类规则的训练模型，然后对未知样本数据进行分类。聚类算法则有两个应用：将数据库分成差异明显的不同群组，发现与其他簇差异较高的少量簇，例如发现较高赔偿成本的保险用户。聚类算法将样本集分成簇，使簇中对象相似，而簇间对象距离差异大。关键过程是计算样本数据与所有簇中心点的距离，根据最近距离选择样本所在簇；对新簇计算新的中心点。关联规则算法则是在商业数据中，发现事务集合与对象集合之间的频繁模式，生成关联规则，而且具有支持度和可信度。频繁模式设置min_sup，应用建立树和人工智能的剪枝技术，获得频繁闭项集。尽管数据挖掘在商业领域获得了巨大的资金收益，然而新时期需要处理的是海量数据，使用单机的算法不能适应互联网环境的要求，因此数据挖掘并行算法的研究是势在必行的。

1 Hadoop云平台组成

Hadoop云计算平台是Doug Cutting主导开发的开源项目，使用java语言，具有实用性，受到广泛欢迎。Hadoop包括10个子项目。它的物理存储是分布式文件系统HDFS。HDFS将数据文件分成64M数据块，并且存储在不同数据节点上。HDFS用备份方式防止出现读写错误，因此每个数据块有三个副本，存储在不同机柜。Hadoop可部署在廉价的微型机上，集群系统包括上千个服务器，因此Hadoop的应用程序可处理海量数据，几个GB甚至TB。

Hadoop的编程模型是Map/Reduce。Map/Reduce框架是集中管理，只有一个管理器称为命名节点namenode，有多个工作节点称为数据节点datanode。Namenode接收用户提交的作业，并且用JobDriver初始化一个job。Namenode将并且将用户作业的输入数据划分成split，并且将用户作业划分成不同的map任务，分配给空闲数据节点，称为map节点。Mapper接受split，在setup阶段建立键值对。在map函数运行结束后，产生中间键值对结果，并且向namenode发出中间结果存储信息。Namenode接收到位置信息后，发送到reduce节点。Reducer通过http将所有相关map函数的输出结果复制到本地存储器，进行归并和简单运算，将结果按规格存储在HDFS中。在reduce函数执行前，应产生列表。

2 数据挖掘算法Map/Reduce并行框架

Hadoop云平台设计数据挖掘并行算法包括4层，底层是分布式计算层，用户构建Hadoop系统；第二层是数据挖掘并行算法层，包括数据预处理模块、主算法程序、模式评估模块等；第三层是业务应用层，包括用户业务响应模块和工作流程。最上层是用户界面，包括界面程序、用户管理模块等。数据挖掘算法包括三个阶段：数据预处理、数据挖掘、数据样本类型、簇或者关联规则输出。对每一个阶段都使用Map/Reduce并行框架。

如果对分类算法进行Map/Reduce编程，则在第二阶段map将根据属性表的条件产生新的节点，因此reduce节点增加；而在聚类算法中，reduce节点将计算所有簇的新中心点，因此reduce的数量少。input split在经过数据挖掘程序的执行后，输出样本数据的分类、所有簇、数据库规则。在数据挖掘并行算法中，概率计算、属性表划分、距离计算，和节点的并行分配是关键技术。例如：决策树算法划分数据集使用属性选择度量，有信息增益等三种条件。k-means算法的距离计算有欧式距离等三种数学公式，用以选择样本所在簇；聚类准则函数是迭代停止的条件，有全局误差函数和簇类中心误差值函数两种公式。

3 实验分析

将数据挖掘的map/reduce框架应用在sprint算法和k-means算法上，hadoop云平台有4个节点，则加速比分别增加了2.1倍和1.3倍。因此，hadoop云平台的数据挖掘并行算法是可行的。只是实验设置相对简单，今后应予以改进。

4 总结

Hadoop云平台为海量数据的分布式处理提供了开发环境。数据挖掘算法的各种类型能应用map/reduce编程框架进行并行计算，实现了分布式数据和大量数据实时计算，在当今大数据和物联网迅捷发展的形势下将有良好的应用前景。

参考文献

[1]胡昕.基于Hadoop海量数据挖掘技术分析[J].企业导刊，2014（11）：154，158.

[2]赵伟.基于Hadoop的数据挖掘算法并行化研究[硕士学位论文][D].西南交通大学，2015.

作者简介

徐啸（1993-），男，河南省漯河市人。现为香港浸会大学硕士在读学生。

作者单位

香港浸会大学 中华人民共和国香港特别行政区 999077