基于hadoop的决策树分类算法的并行化分析

《基于hadoop的决策树分类算法的并行化分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据四川师范大学硕士学位论文4．3．4加速比⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯444．4本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯455CART算法在Hadoop上的并行化及实现⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．475．1经典CART算法简介⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯475．2CART算法的并行化⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．485．3实验⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯555．3．1实验数据⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯55

2、5．3．2运行时间⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯565．3．3可扩展性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯575．3．4加速比⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．585．4本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯596总结与展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯6l6．1本文工作总结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯616．2未来研究展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯62参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

3、．63致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯66ⅥII万方数据1引言1引言随着计算机、网络等相关技术的发展，数据挖掘技术的应用渗透到了各行各业，其中决策树分类算法又在数据挖掘技术中占有重要地位。然而传统的决策树分类算法为内存驻留算法，能处理的数据集规模小且效率低，在大数据背景下，已经显得完全无能为力。但是，云技术的出现，基于云计算的决策树分类算法使决策树处理大数据成为可能。本文分析决策树自身特点，结合MapReduce并行计算框架，提出了基于Hadoop平台的决策树分类算法的并行化方案，并在平台上对其进行了实现，

4、解决了传统决策树算法不能处理大规模数据集的问题并且使其具有较好的性能。1．1课题研究背景及意义1．大数据时代的到来，解决“数据丰富，知识贫乏”问题的需要“大数据【lj，’、“云技术[21”是IT界最近讨论的比较热的两个名词，吸引了众多IT公司的参与，如Google、IBM、Amazon、YahOO、Intel等。同时，高校、科研机构、IT爱好者也对它们给予的高度的关注。在Web2．0之前，对于互联网，所有的参与者只能被动的接受信息，而随着Web2。0时代的到来，参与者拥有了实际的参与权。Web2．0时代的到来，与人们的生活、学习、工作、娱乐等相关的所有信息都可以通

5、过互联网这个大环境进行传播，互联网上的所有人都成为信息的生产者和传播者，同时涌现了QQ、博客、微信、人人网等众多的社交工具和网站，为信息的产生和传播奠定了基础。随着参与到互联网活动中的人越来越多，互联网上的信息呈指数级趋势增长，而这些信息存在高重复、部分信息不真实或信息缺失等种种问题，大量信息不可用，这就是所说的“数据爆炸”和“数据丰富，知识贫乏【3】’’现象，因此，如何存储和管理这些数据并从中提取出潜在有用的信息成为了大数据环境下亟待解决的任务之一。2．传统的决策树算法优点多，但不能直接用于处理大规模的数据集随着互联网上的信息呈指数级的增长，我们仍希望决策树分类

6、算法能处理不断增长的数据集。其原因是传统的决策树分类算法具有结构简单、准确率高等优点，但它必须通过挖掘大量的数据才能得到有效的知识。尤其是在生物医学领域进行的相关研究，通常需要处理的都是大规模、超大规模的数据[41。但是传统的决策算法在处理海量数据时，效率低，甚至对海量数据无法进行处理【51，只有对决策树分类算法进行并行化才是解决此问题的唯一办法。万方数据四川师范大学硕士学位论文3．在众多的决策树并行算法中，基于云计算的并行决策树算法是处理数据密集型应用最有效的方法按数据共享和同步方式，可将决策树并行算法分为基于共享内存、消息通信和云计算三类【6，7j。基于共享内

7、存的并行决策树分类算法，它仅适用于单机多核的高性能计算机以及分布式共享存储的多处理机，对机器的性能要求高且可扩展性差。而基于消息通信的并行决策树分类算法，一般都是用MPI实现的，可移植性好、易扩展，但它仅适用于处理计算密集性应用，而不适合处理数据密集性的应用：其次，基于MPI的并行算法，无法处理结点失效的情况，容错性差。为处理数据性密集性应用，Google提出了云计算的概念，用于对大数据进行存储和处理，相比于传统并行计算的数据向计算迁移，Google的云计算实现了“计算向存储迁移”【8J的机制；其次，云计算平台拥有一套完善的解决结点失效的方案，具有高效的任务分配、

8、调度机制，