大数据环境下决策树算法并行化研究

主要研究问题
决策数算法(ID3)并行化

为什么重要
大数据环境下像决策树这种传统算法的局限越来约明显，并行化能能够有效减少执行时间

研究现状及存在的问题
1.对于决策树的改进方法都基于传统的串行方法，无法满足大数据环境下数据挖据的需求
2.传统的并行方法主要是基于消息传送例如PVM和MPI，而此方法适合处理计算密集型问题，当处理数据密集型问题时，通讯代价迅速增加系统性能大大降低。
3.传统的并行化方法抽象读较低，需要显式处理一些底层的细节问题，例如调度等，提高了并行程序设计的复杂度。

论文方法和创新点
1.摈弃传统的并行化方法，选择MapReduce并行化决策树算法开销最大的最佳分割点选择部分。
在Map阶段遍历每个属性生成 key = <类标，属性名，属性值> ， value = 1 的 < key, value > 对;
在Reduce阶段，将Map阶段输出的< key, value > 对中key值相同的value相加。从而可以得到计算信息增益时所需的参数
2.引入修正参数改进ID3利用信息增益进行属性选择时倾向于多属性选取的问题。
修正项为： 其中v为该属性的取值个数，取值个数越多，修正参数的值越小

实验证实情况
a）数据选自来自UCI数据集，基于hadoop平台，集群由7台PC组成，1台为Master，6台为Salve节点
b）优劣评价的标准是运行时间
c）通过实验证明，当数据规模增大时，单机处理到一定的程度是会由于内存不足而使得程序无法正常运行，而集群则始终平稳运行，且计算时间增加平稳，每个节点资源消耗波动小。由于MPI方法通信开销大，相同情况下MPI并行化的ID3算法性能低于基于MapReduce的并行化算法