Abstract: In view of that the traditional decision tree algorithm that cannot solve the mass data mining and the multi-value bias problem of ID3 algorithm, the paper designed and realized a parallel decision tree classification algorithm based on the MapReduce framework. This algorithm adopted attribute similarity as the choice standard to avoid the multi-value bias problem of ID3 algorithm, and used the MapReduce model to solve the mass data mining problems. According to the experiments on the Hadoop cluster set up by ordinary PCs, the decision tree algorithm based on MapReduce can deal with massive data classification. What's more, the algorithm has good expansibility while ensuring the classification accuracy and can get close to linear speedup rate.

Key words: MapReduce, attribute similarity, Hadoop, decision tree, ID3 algorithm

摘要： 针对传统决策树算法不能解决海量数据挖掘以及ID3算法的多值偏向问题,设计和实现了一种基于MapReduce架构的并行决策树分类算法。该算法采用属性相似度作为测试属性的选择标准来避免ID3算法的多值偏向问题,采用MapReduce模型来解决海量数据挖掘问题。在用普通PC搭建的Hadoop集群的实验结果表明:基于MapReduce的决策树算法可以处理大规模数据的分类问题,具有较好的可扩展性,在保证分类正确率的情况下能获得接近线性的加速比。

关键词: MapReduce, 属性相似度, Hadoop, 决策树, ID3算法