一种基于Hadoop架构的并行挖掘算法研究
曾俊
摘 要： 基于Hadoop架构，提出一种并行的决策树挖掘算法实现大数据集间的知识挖掘。通过MapReduce并行编程模式实现Hadoop架构下SPRINT并行挖掘算法的频繁项集，解决了大数据集挖掘效率低下，时间消耗量大的问题。SPRINT算法通过对原始数据集进行划分，并将分块数据发给不同Map进程并行计算，使系统存储和计算资源得到有效利用，运用MapReduce各计算节点将挖掘结果数据汇聚，减少中间结果数据量，使并行挖掘时间显著减少。SPRINT算法并行化实验表明，Hadoop架构下的SPRINT并行挖掘算法具有良好的可扩展性和集群加速比。
关键词： 挖掘算法； Hadoop架构； SPRINT； 并行化； 决策树； MapReduce
中图分类号： TN911.1?34； TP311 文献标识码： A 文章编号： 1004?373X（2018）01?0117?03
Abstract： A parallel decision tree mining algorithm based on Hadoop is proposed to realize the knowledge mining between large data sets. The frequent item sets of SPRINT parallel mining algorithm under the Hadoop architecture is realized with the MapReduce parallel programming mode to solve the problems of low efficiency and large time consumption for large data sets mining. The original data set is divided with SPRINT algorithm， and its block data is sent to different Map process for parallel computing， which can utilize the system storage and computing resources availably. The MapReduce is used to aggregate the mining results of each computing node， reduce the data quantity of the intermediate results， and decrease the parallel mining time significantly. The SPRINT parallel algorithm was verified with experiments. The experimental results show that the SPRINT parallel mining algorithm under Hadoop architecture has strong scalability and perfect speedup ratio.
Keywords： mining algorithm； Hadoop architecture； SPRINT； parallelization； decision tree； MapReduce
0 引 言
數据挖掘是通过对数据的分析，在大量数据集中进行有价值信息寻找的技术。文献[1]提出一种决策树挖掘算法（SDT），SDT算法对未知数据集、已知数据集进行同时挖掘，并建立决策树，从而快速对未知数据集进行理解，进而对未知数据集的特性进行关注。但SDT算法以传统串行思想为基础，只能对小规模数据进行处理，对于规模大的数据，挖掘效率比较低下，在进行决策树的构造时，时间会较长，同时还会因内存限制，造成无法运行[2]。Hadoop从基础构架的角度来说属于分布式，能够在未知的条件下对分布式的应用程序进行并行性的开发，文件系统（HDFS）通过流式数据访问模式，可进行超大文件的存储[3]。本文基于Hadoop架构，提出一种并行的决策树挖掘算法来实现大数据集间的知识挖掘。
1 决策树挖掘算法SPRINT算法
SPRINT算法采用的属性选择度量为Gini指标，对于SPRINT而言，在数据集[D]中，条数据记录分为[D1，][D2，]分别对应包含的数据记录为[m1]条，[m2]条，Gini指标计算公式：
[GinisplitD=m1m2GiniD1+m1m2GiniD2] （1）
1.1 并行化方案设计
1.1.1 决策树节点的并行
在由拓扑结构组成的决策树中，通过各树节点的不断分裂，就生成了树，从实际的角度上来说就是将数据集进行分裂。图1为树节点并行化，在图1a）中，传统SPRINT算法在分裂时将某个树节点上的属性列表看作整体，决策树会在节点分裂时产生，主要是由不断递归来完成的。在MapReduce的框架计算结构当中，Map具有强大的映射处理功能，能够借助于PatITioer完成函数的定义，将不同进行不同Reducer的对映射，之后进行进一步的处理。由于这样的原因，相应的Reducer上会反应决策树当中的节点属性，最后进行并行处理，见图1b）。在生成树中，每层算法均一样，只要执行一次循环，属性列表的节点和分裂构造就可实现。
1.1.2 属性选择度量的并行
SPRINT算法中，在进行节点的属性度量中Gini主要进行一个可并行化的过程。图2为节点属性度的计算并行。在树节点并行机制上，进行属性列表的Gini指标计算的建立，在相同树节点中，不同的节点在相应的决策树上都有其属性。由于上面的原因，想要保证并行化的树节点标记，在寻址阶段应当满足上面提到的Patitioner规则。相同的属性和树节点在进行标记时，才能够实现Reducer的处理和实施。
1.1.3 Gini指标排序的并行
在SPRINT的一个算法当中，数据如果属于一个连续性的属性列表，在进行Gini指标的计算时需要寻找分裂点，因此，该连续值属性列表需要进行排序。在数据集完全拆分成属性列表后，SPRINT算法会进行连续值属性列表的排序，当数据集规模非常庞大时，整个算法受设计的排序算法影响较大，可通过MapReduce框架的天然排序特性得到解决。
2 基于Mapreduce框架的SPRINT算法具体实现
2.1 决策树根节点的创建与分裂
两个任务要在第一个阶段来完成，基本的属性列表都是要形成的，属性列表是由拆分之后的数据集组成的，之后出现了决策树的根节点；另一方面根据根节点分裂的情况，之后每个Job的作业控制由MRApp Master负责。
2.1.1 Job1阶段
在Job1阶段，Map过程负责拆分数据集，生成属性列表，用来表征全部数据集的信息。Input Format组件实现MapReduce框架的读取操作，在Input Format中，通过Record Reader由Input Split的多个键值对，由Map（）函数对其进行处理，从HDFS上进行数据集中样本对象的读取，并进行Map操作。在SPRINT算法中，Reducer通过映射之后对已经排序过的属性列表进行处理。
2.1.2 Job2阶段
Job2阶段是判断、汇总、执行Job1的处理结果，Job1的输出就是Job2的Map过程的输入，由于根节点只有一个，因此全部属性列表在一个Reduce上进行分发。在进行输入时，包括每一个属性的分裂点以及Gini的值，Gini对应的属性值为节点分裂最小的属性值。
2.2 决策树主要阶段的生成
2.2.1 Job3阶段
Job3阶段的任务目的和Job1类似，分裂出的子节点可作为下一轮分裂树节点的“根节点”。在这里，实现属性表的映射是Map的任务。在Hadoop MapReduce框架中，通过借助一定的组件，Map能够从HDFS上面读取一定的数据信息。在第一个阶段中Patitioner进行时，Map根据情况的不同分发不同的数据，因此能够完成并行的机制。
2.2.2 Job4阶段
该阶段和Job2的目的有一定的相似性，能够分割最佳的树节点属性，差别是Job4阶段分裂的树节点较多。Job4作业的Map过程是收集依附于某个树节点的全部属性列表数据。相对于第一阶段Job2的Reduce来说，Job4作业的Reduce在选择最佳分割属性前，要判断该节点是否有叶节点生成，也就是对其是否达到循环终止条件进行判断。若达到终止条件，则不再分裂树节点的所有属性列表；反之，算法继续执行。
2.3 决策树结构的完成
决策树是将上面得到的数据按照一定规则分配好后，将树的基本构造完成。三个阶段的试验方法完成之后，能够将SPRINT串行算法运行在云计算平台Hadoop上，进而完成在大量的数据中挖掘和提取数据的工作。
3 SPRINT算法并行化实验
3.1 SPRINT准确率验证
实验对比分析SPRINT算法的MapReduce模型和串行模型，对SPRINT算法的分类准确率进行测试。实验数据样本来源于UCI，在UCI中选取3个数据集，分类进行测试，具体如表1所示。其中35%样本作为测试数据，65%样本作为训练数据。Hadoop平台共有3个计算节点数目。
图3为SPRINT算法的3个数据集的准确率比较，由图3知，表1当中三个样本集的并行和串行模型準确率都是非常接近的，能够看到此算法对最后的准确率影响是比较小的。
3.2 集群并行化的可扩展性和加速比
实验通过不同规模的集群计算节点、不同大小的数据集，对SPRINT算法并行的可扩展性效果和集群加速比进行验证。实验数据来源于UCI，根据3.1实验数据集Adult的样本，随机生成规模不同的实验样本，具体见表2。图4，图5为可扩展比实验结果。
从图4和图5可以看出，SPRINT算法具有比较好的集群和可扩展性，能够提升大规模数据计算的速度；可扩展性和集群加速比随着集群节点的增加均有一定程度的下降，原因是由于并行化程度和对应的数据集大小均已达到最大化，不能随着集群的运算节点的增加而增长。
4 结 语
本文基于Hadoop架构，提出一种并行的决策树挖掘算法实现大数据集间的知识挖掘。通过MapReduce并行编程模式实现Hadoop架构下SPRINT并行挖掘算法的频繁项集，解决了大数据集挖掘效率低下，时间消耗量大的问题。SPRINT算法通过对原始数据集进行划分，并将分块数据发给不同Map进程并行计算，使系统存储和计算资源得到有效利用，运用MapReduce，各计算节点将挖掘结果数据汇聚，减少中间结果数据量，使并行挖掘时间显著减少。SPRINT算法并行化实验表明，Hadoop架构下的SPRINT并行挖掘算法具有良好的可扩展性和集群加速比。
参考文献
[1] DONG Guozhu， HAN Qian. Mining shared decision trees between datasets [R]. USA： Wright State University， 2010.
[2] 周建华.一种基于Hadoop架构的网络舆情热点话题挖掘方法[J].河北北方学院学报（自然科学版），2014，30（6）：19?24.ZHOU Jianhua. A mining method for hot topics of network public opinion based on Hadoop architecture [J]. Journal of Hebei North University （natural science edition）， 2014， 30（6）： 19?24.
[3] 張振友，孙燕，丁铁凡，等.一种新型的基于Hadoop框架的分布式并行FP?Growth算法[J].河北工业科技，2016，33（2）：169?178.
ZHANG Zhenyou， SUN Yan， DING Tiefan， et al. A new distributed parallel FP?Growth algorithm based on Hadoop framework [J]. Hebei industrial science and technology， 2016， 33（2）： 169?178.
[4] 施亮，钱雪忠.基于Hadoop的并行FP?Growth算法的研究与实现[J].微电子学与计算机，2015，32（4）：150?154.
SHI Liang， QIAN Xuezhong. Research and implementation of FP?Growth algorithm based on parallel Hadoop [J]. Microelectronics & computer， 2015， 32（4）： 150?154.
[5] HAN jiawei， KAMBER M.数据挖掘：概念与技术[M].范明，孟小峰，译.北京：机械工业出版社，2008.
HAN Jiawei， KAMBER M. Data mining： concepts and techniques [M]. Translated by FAN Ming， MENG Xiaofeng. Beijing： Mechanical Industry Press， 2008.
[6] ZAKI M J. Fast vertical mining using diffsets [R]. New York， USA： Rensselaer Polytechnic Institute， 2001.
[7] Apache. Apache Hadoop [EB/OL]. [2012?12?03]. http：//hadoop.apache.org/.
[8] MAITREYA S， JHAB C K. MapReduce： simplified data analysis of big data [J]. Procedia computer science， 2015， 57： 563?571.
[9] 李国杰，程学旗.大数据的研究现状与科学思考[J].中国科学院院刊，2012，27（6）：647?651.
LI Guojie， CHENG Xueqi. Big data research status and scientific thinking [J]. Chinese Science Research Institute Journal， 2012， 27（6）： 647?651.
[10] NESI Paolo， PANTALEO Gianni， SANESI Gianmarco. A Hadoop based platform for natural language processing of Web pages and documents [J]. Journal of visual languages and computing， 2015， 31： 130?138.
[11] WHITE T. Hadoop权威指南[M].华东师范大学数据科学与工程学院，译.北京：清华大学出版社，2010.
WHITE T. Hadoop authoritative guide [M]. Translated by the School of Data Science and Engineering， East China Normal University. Beijing： Tsinghua University Press， 2010.
摘 要： 基于Hadoop架构，提出一种并行的决策树挖掘算法实现大数据集间的知识挖掘。通过MapReduce并行编程模式实现Hadoop架构下SPRINT并行挖掘算法的频繁项集，解决了大数据集挖掘效率低下，时间消耗量大的问题。SPRINT算法通过对原始数据集进行划分，并将分块数据发给不同Map进程并行计算，使系统存储和计算资源得到有效利用，运用MapReduce各计算节点将挖掘结果数据汇聚，减少中间结果数据量，使并行挖掘时间显著减少。SPRINT算法并行化实验表明，Hadoop架构下的SPRINT并行挖掘算法具有良好的可扩展性和集群加速比。
关键词： 挖掘算法； Hadoop架构； SPRINT； 并行化； 决策树； MapReduce
中图分类号： TN911.1?34； TP311 文献标识码： A 文章编号： 1004?373X（2018）01?0117?03
Abstract： A parallel decision tree mining algorithm based on Hadoop is proposed to realize the knowledge mining between large data sets. The frequent item sets of SPRINT parallel mining algorithm under the Hadoop architecture is realized with the MapReduce parallel programming mode to solve the problems of low efficiency and large time consumption for large data sets mining. The original data set is divided with SPRINT algorithm， and its block data is sent to different Map process for parallel computing， which can utilize the system storage and computing resources availably. The MapReduce is used to aggregate the mining results of each computing node， reduce the data quantity of the intermediate results， and decrease the parallel mining time significantly. The SPRINT parallel algorithm was verified with experiments. The experimental results show that the SPRINT parallel mining algorithm under Hadoop architecture has strong scalability and perfect speedup ratio.
Keywords： mining algorithm； Hadoop architecture； SPRINT； parallelization； decision tree； MapReduce
0 引 言
數据挖掘是通过对数据的分析，在大量数据集中进行有价值信息寻找的技术。文献[1]提出一种决策树挖掘算法（SDT），SDT算法对未知数据集、已知数据集进行同时挖掘，并建立决策树，从而快速对未知数据集进行理解，进而对未知数据集的特性进行关注。但SDT算法以传统串行思想为基础，只能对小规模数据进行处理，对于规模大的数据，挖掘效率比较低下，在进行决策树的构造时，时间会较长，同时还会因内存限制，造成无法运行[2]。Hadoop从基础构架的角度来说属于分布式，能够在未知的条件下对分布式的应用程序进行并行性的开发，文件系统（HDFS）通过流式数据访问模式，可进行超大文件的存储[3]。本文基于Hadoop架构，提出一种并行的决策树挖掘算法来实现大数据集间的知识挖掘。
1 决策树挖掘算法SPRINT算法
SPRINT算法采用的属性选择度量为Gini指标，对于SPRINT而言，在数据集[D]中，条数据记录分为[D1，][D2，]分别对应包含的数据记录为[m1]条，[m2]条，Gini指标计算公式：
[GinisplitD=m1m2GiniD1+m1m2GiniD2] （1）
1.1 并行化方案设计
1.1.1 决策树节点的并行
在由拓扑结构组成的决策树中，通过各树节点的不断分裂，就生成了树，从实际的角度上来说就是将数据集进行分裂。图1为树节点并行化，在图1a）中，传统SPRINT算法在分裂时将某个树节点上的属性列表看作整体，决策树会在节点分裂时产生，主要是由不断递归来完成的。在MapReduce的框架计算结构当中，Map具有强大的映射处理功能，能够借助于PatITioer完成函数的定义，将不同
1.1.2 属性选择度量的并行
SPRINT算法中，在进行节点的属性度量中Gini主要进行一个可并行化的过程。图2为节点属性度的计算并行。在树节点并行机制上，进行属性列表的Gini指标计算的建立，在相同树节点中，不同的节点在相应的决策树上都有其属性。由于上面的原因，想要保证并行化的树节点标记，在寻址阶段应当满足上面提到的Patitioner规则。相同的属性和树节点在进行标记时，才能够实现Reducer的处理和实施。
1.1.3 Gini指标排序的并行
在SPRINT的一个算法当中，数据如果属于一个连续性的属性列表，在进行Gini指标的计算时需要寻找分裂点，因此，该连续值属性列表需要进行排序。在数据集完全拆分成属性列表后，SPRINT算法会进行连续值属性列表的排序，当数据集规模非常庞大时，整个算法受设计的排序算法影响较大，可通过MapReduce框架的天然排序特性得到解决。
2 基于Mapreduce框架的SPRINT算法具体实现
2.1 决策树根节点的创建与分裂
两个任务要在第一个阶段来完成，基本的属性列表都是要形成的，属性列表是由拆分之后的数据集组成的，之后出现了决策树的根节点；另一方面根据根节点分裂的情况，之后每个Job的作业控制由MRApp Master负责。
2.1.1 Job1阶段
在Job1阶段，Map过程负责拆分数据集，生成属性列表，用来表征全部数据集的信息。Input Format组件实现MapReduce框架的读取操作，在Input Format中，通过Record Reader由Input Split的多个
2.1.2 Job2阶段
Job2阶段是判断、汇总、执行Job1的处理结果，Job1的输出就是Job2的Map过程的输入，由于根节点只有一个，因此全部属性列表在一个Reduce上进行分发。在进行输入时，包括每一个属性的分裂点以及Gini的值，Gini对应的属性值为节点分裂最小的属性值。
2.2 决策树主要阶段的生成
2.2.1 Job3阶段
Job3阶段的任务目的和Job1类似，分裂出的子节点可作为下一轮分裂树节点的“根节点”。在这里，实现属性表的映射是Map的任务。在Hadoop MapReduce框架中，通过借助一定的组件，Map能够从HDFS上面读取一定的数据信息。在第一个阶段中Patitioner进行时，Map根据情况的不同分发不同的数据，因此能够完成并行的机制。
2.2.2 Job4阶段
该阶段和Job2的目的有一定的相似性，能够分割最佳的树节点属性，差别是Job4阶段分裂的树节点较多。Job4作业的Map过程是收集依附于某个树节点的全部属性列表数据。相对于第一阶段Job2的Reduce来说，Job4作业的Reduce在选择最佳分割属性前，要判断该节点是否有叶节点生成，也就是对其是否达到循环终止条件进行判断。若达到终止条件，则不再分裂树节点的所有属性列表；反之，算法继续执行。
2.3 决策树结构的完成
决策树是将上面得到的数据按照一定规则分配好后，将树的基本构造完成。三个阶段的试验方法完成之后，能够将SPRINT串行算法运行在云计算平台Hadoop上，进而完成在大量的数据中挖掘和提取数据的工作。
3 SPRINT算法并行化实验
3.1 SPRINT准确率验证
实验对比分析SPRINT算法的MapReduce模型和串行模型，对SPRINT算法的分类准确率进行测试。实验数据样本来源于UCI，在UCI中选取3个数据集，分类进行测试，具体如表1所示。其中35%样本作为测试数据，65%样本作为训练数据。Hadoop平台共有3个计算节点数目。
图3为SPRINT算法的3个数据集的准确率比较，由图3知，表1当中三个样本集的并行和串行模型準确率都是非常接近的，能够看到此算法对最后的准确率影响是比较小的。
3.2 集群并行化的可扩展性和加速比
实验通过不同规模的集群计算节点、不同大小的数据集，对SPRINT算法并行的可扩展性效果和集群加速比进行验证。实验数据来源于UCI，根据3.1实验数据集Adult的样本，随机生成规模不同的实验样本，具体见表2。图4，图5为可扩展比实验结果。
从图4和图5可以看出，SPRINT算法具有比较好的集群和可扩展性，能够提升大规模数据计算的速度；可扩展性和集群加速比随着集群节点的增加均有一定程度的下降，原因是由于并行化程度和对应的数据集大小均已达到最大化，不能随着集群的运算节点的增加而增长。
4 结 语
本文基于Hadoop架构，提出一种并行的决策树挖掘算法实现大数据集间的知识挖掘。通过MapReduce并行编程模式实现Hadoop架构下SPRINT并行挖掘算法的频繁项集，解决了大数据集挖掘效率低下，时间消耗量大的问题。SPRINT算法通过对原始数据集进行划分，并将分块数据发给不同Map进程并行计算，使系统存储和计算资源得到有效利用，运用MapReduce，各计算节点将挖掘结果数据汇聚，减少中间结果数据量，使并行挖掘时间显著减少。SPRINT算法并行化实验表明，Hadoop架构下的SPRINT并行挖掘算法具有良好的可扩展性和集群加速比。
参考文献
[1] DONG Guozhu， HAN Qian. Mining shared decision trees between datasets [R]. USA： Wright State University， 2010.
[2] 周建华.一种基于Hadoop架构的网络舆情热点话题挖掘方法[J].河北北方学院学报（自然科学版），2014，30（6）：19?24.ZHOU Jianhua. A mining method for hot topics of network public opinion based on Hadoop architecture [J]. Journal of Hebei North University （natural science edition）， 2014， 30（6）： 19?24.
[3] 張振友，孙燕，丁铁凡，等.一种新型的基于Hadoop框架的分布式并行FP?Growth算法[J].河北工业科技，2016，33（2）：169?178.
ZHANG Zhenyou， SUN Yan， DING Tiefan， et al. A new distributed parallel FP?Growth algorithm based on Hadoop framework [J]. Hebei industrial science and technology， 2016， 33（2）： 169?178.
[4] 施亮，钱雪忠.基于Hadoop的并行FP?Growth算法的研究与实现[J].微电子学与计算机，2015，32（4）：150?154.
SHI Liang， QIAN Xuezhong. Research and implementation of FP?Growth algorithm based on parallel Hadoop [J]. Microelectronics & computer， 2015， 32（4）： 150?154.
[5] HAN jiawei， KAMBER M.数据挖掘：概念与技术[M].范明，孟小峰，译.北京：机械工业出版社，2008.
HAN Jiawei， KAMBER M. Data mining： concepts and techniques [M]. Translated by FAN Ming， MENG Xiaofeng. Beijing： Mechanical Industry Press， 2008.
[6] ZAKI M J. Fast vertical mining using diffsets [R]. New York， USA： Rensselaer Polytechnic Institute， 2001.
[7] Apache. Apache Hadoop [EB/OL]. [2012?12?03]. http：//hadoop.apache.org/.
[8] MAITREYA S， JHAB C K. MapReduce： simplified data analysis of big data [J]. Procedia computer science， 2015， 57： 563?571.
[9] 李国杰，程学旗.大数据的研究现状与科学思考[J].中国科学院院刊，2012，27（6）：647?651.
LI Guojie， CHENG Xueqi. Big data research status and scientific thinking [J]. Chinese Science Research Institute Journal， 2012， 27（6）： 647?651.
[10] NESI Paolo， PANTALEO Gianni， SANESI Gianmarco. A Hadoop based platform for natural language processing of Web pages and documents [J]. Journal of visual languages and computing， 2015， 31： 130?138.
[11] WHITE T. Hadoop权威指南[M].华东师范大学数据科学与工程学院，译.北京：清华大学出版社，2010.
WHITE T. Hadoop authoritative guide [M]. Translated by the School of Data Science and Engineering， East China Normal University. Beijing： Tsinghua University Press， 2010.
