基于MapReduce的并行决策树分类算法研究与实现

论文摘要

分类是数据挖掘和机器学习等领域中一个非常重要的研究课题,在众多领域中都得到了广泛的应用。当前已经提出的分类方法主要有贝叶斯分类、决策树、神经网络、支持向量机等,其中决策树方法以其构造速度快、生成模式简单、精度高等优点而广受欢迎。目前影响较大的决策树算法主要有ID3、SLIQ、SPRINT等。由于决策树分类模型精准程度直接依赖于训练数据集的大小,在处理海量数据时就会遇到时间复杂度过高的瓶颈,使其很难得到推广。因此,决策树分类算法的并行化开发就显得非常必要。本论文基于MapReduce并行编程模型对决策树分类算法的并行化进行了系统的研究。论文首先研究了各种串行决策树分类算法的主要思想,同时对现有的并行编程模型进行了全面的研究、分析和比较,发现MapReduce模型是一种适用于大规模数据并行计算的并行编程模型。在对决策树分类算法的并行性开发时,主要通过将训练数据集在各处理机上进行划分、并行地确定结点的最佳分裂属性以及并行地分割属性列表到各个子结点来实现。论文分别研究了三种MapReduce实现架构下并行决策树分类算法的设计,并在Phoenix共享内存架构上对SPRINT算法进行了具体的并行实现。通过实验分析和比较,结果表明本文研究的方法和实现不仅比基于MPI并行编程模型的同类决策树算法的实现编程更容易,而且在计算节点较多的情况下能得到更优的性能,获得更大加速比。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 研究背景和意义
• 1.2 研究现状
• 1.3 本文工作及论文结构
• 2 决策树分类方法
• 2.1 决策树方法概述
• 2.1.1 决策树的生成
• 2.1.2 决策树的剪枝
• 2.2 常见的决策树算法
• 3算法'>2.2.1 ID₃算法
• 4.5算法'>2.2.2 C_4.5算法
• 2.2.3 SLIQ 算法
• 2.2.4 SPRINT 算法
• 2.3 决策树算法的并行策略
• 2.3.1 数据划分方式
• 2.3.2 程序设计模式
• 3 并行编程模型与决策树分类算法的并行实现
• 3.1 PVM 并行编程模型
• 3.2 MPI 并行编程模型
• 3.3 OpenMP 并行编程模型
• 3.4 基于骨架的并行编程模型
• 3.5 MapReduce 并行编程模型
• 3.6 并行决策树设分类算法
• 3.6.1 基于PVM 的并行SLIQ 算法
• 3.6.2 基于MPI 的并行SPRINT 算法
• 4 MapReduce 实现架构下的并行决策树算法设计
• 4.1 Google 的 MapReduce 架构下并行决策树算法的设计
• 4.1.1 Google 的MapReduce 架构
• 4.1.2 基于 Google 的 MapReduce 架构下的并行 SPRINT 算法设计
• 4.2 Hadoop 架构下的并行决策树算法的设计
• 4.2.1 Apache 的Hadoop 架构
• 4.2.2 Hadoop 架构下并行SPRINT 算法的设计
• 4.3 Phoenix 架构下的并行决策树算法设计
• 4.3.1 Phoenix 架构
• 4.3.2 Phoenix 架构下并行SPRINT 算法的设计
• 4.4 本章小结
• 5 实验分析
• 5.1 实验环境搭建
• 5.2 Phoenix 架构平台上的实现
• 5.2.1 主要数据结构
• 5.2.2 主要函数实现
• 5.3 实验评估指标
• 5.4 实验结果分析
• 6 总结与展望
• 6.1 本文总结
• 6.2 进一步工作
• 参考文献
• 读研期间发表论文
• 致谢