学位论文 > 优秀研究生学位论文题录展示

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

作　者: 朱敏
导　师: 万剑怡
学　校: 江西师范大学
专　业: 计算机科学与技术
关键词: 决策树分类 SPRINT 并行编程模型 MapReduce Phoenix架构
分类号: TP311.13
类　型: 硕士论文
年　份: 2011年
下　载: 139次
引　用: 0次
阅　读: 论文下载
 

内容摘要


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

全文目录


摘要  3-4
ABSTRACT  4-7
1 绪论  7-11
  1.1 研究背景和意义  7-8
  1.2 研究现状  8-9
  1.3 本文工作及论文结构  9-11
2 决策树分类方法  11-22
  2.1 决策树方法概述  11-14
    2.1.1 决策树的生成  12-13
    2.1.2 决策树的剪枝  13-14
  2.2 常见的决策树算法  14-19
    2.2.1 ID_3算法  14-15
    2.2.2 C_(4.5)算法  15-16
    2.2.3 SLIQ 算法  16-17
    2.2.4 SPRINT 算法  17-19
  2.3 决策树算法的并行策略  19-22
    2.3.1 数据划分方式  19-20
    2.3.2 程序设计模式  20-22
3 并行编程模型与决策树分类算法的并行实现  22-32
  3.1 PVM 并行编程模型  22
  3.2 MPI 并行编程模型  22-23
  3.3 OpenMP 并行编程模型  23
  3.4 基于骨架的并行编程模型  23-24
  3.5 MapReduce 并行编程模型  24-27
  3.6 并行决策树设分类算法  27-32
    3.6.1 基于PVM 的并行SLIQ 算法  27-29
    3.6.2 基于MPI 的并行SPRINT 算法  29-32
4 MapReduce 实现架构下的并行决策树算法设计  32-47
  4.1 Google 的 MapReduce 架构下并行决策树算法的设计  32-37
    4.1.1 Google 的MapReduce 架构  32-33
    4.1.2 基于 Google 的 MapReduce 架构下的并行 SPRINT 算法设计  33-37
  4.2 Hadoop 架构下的并行决策树算法的设计  37-41
    4.2.1 Apache 的Hadoop 架构  37-38
    4.2.2 Hadoop 架构下并行SPRINT 算法的设计  38-41
  4.3 Phoenix 架构下的并行决策树算法设计  41-46
    4.3.1 Phoenix 架构  41-44
    4.3.2 Phoenix 架构下并行SPRINT 算法的设计  44-46
  4.4 本章小结  46-47
5 实验分析  47-54
  5.1 实验环境搭建  47
  5.2 Phoenix 架构平台上的实现  47-51
    5.2.1 主要数据结构  47-48
    5.2.2 主要函数实现  48-51
  5.3 实验评估指标  51-52
  5.4 实验结果分析  52-54
6 总结与展望  54-55
  6.1 本文总结  54
  6.2 进一步工作  54-55
参考文献  55-59
读研期间发表论文  59-60
致谢  60

相似论文

  1. 基于Map/Reduce框架的分布式日志分析系统的研究及应用,TP311.52
  2. 高速网络环境下的入侵检测系统的研究,TP393.08
  3. 云环境下MapReduce容错技术的研究,TP302.8
  4. 基于粗糙集理论的决策树分类算法与应用研究,TP18
  5. 基于IaaS云计算的Web应用技术研究,TP393.09
  6. 保护隐私的分类挖掘技术研究,TP311.13
  7. 基于MapReduce的聚类算法的并行化研究,TP311.13
  8. MapReduce集群多用户作业调度方法的研究与实现,TP311.13
  9. 决策树分类算法研究及其在地税征管系统中的应用,TP311.13
  10. 基于时空折衷算法的Word文档破解研究,TP391.12
  11. 数据挖掘技术在银行CRM中的应用研究,F830.49
  12. 华东区域土地利用/覆被变化及驱动力模型研究,F301.24
  13. 基于MapReduce的分布式编程框架的设计与实现,TP311.52
  14. 基于数据挖掘技术的印花税“资金账薄”品目欠税分类研究,TP311.13
  15. 基于数据挖掘的高考数据分析,TP311.13
  16. 敏捷开发过程中软件测试技术的分析与应用,TP311.52
  17. 基于CMP集群的并行编程模型的研究与应用,TP338.6
  18. 片上网络多核处理器的性能测试与并行编程研究,TN47
  19. 决策树在入侵检测中的应用研究,TP393.08
  20. 基于MDSP的并行MPEG-4视频编码器的设计与实现,TN919.81

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机软件 > 程序设计、软件工程 > 程序设计 > 数据库理论与系统
© 2012 www.xueweilunwen.com