A parallel C4.5 decision tree algorithm based on MapReduce

摘要

In the supervised classification, large training data are very common,and decision trees arewidelyrnused. However, as some bottlenecks such as memory restrictions, time complexity, or data complexity,rnmany supervised classifiers including classical C4.5 tree cannot directly handle big data.rnOne solution for this problem is to design a highly parallelized learning algorithm. Motivated byrnthis,we propose a parallelized C4.5 decision tree algorithm based on MapReduce (MR-C4.5-Tree)rnwith 2 parallelized methods to build the tree nodes. First, an information entropy-based parallelizedrnattribute selection method (MR-A-S) on several subsets for MR-C4.5-Tree is proposed tornconfirm the best splitting attribute and the cut points. Then, a data splitting method (MR-D-S)rnin parallel is presented to partition the training data into subsets. At last, we introduce thernMR-C4.5-Tree learning algorithm that grows ina top-down recursiveway.Besides, thedepth of thernconstructed decision tree, the number of samples and the maximal class probability in each treernnode are used as the termination conditions to avoid the over-partitioning problem. Experimentalrnstudies show the feasibility and the good performance of the proposed parallelized MR-C4.5-Treernalgorithm.