Title of Paper:A parallel C4.5 decision tree algorithm based on MapReduce

Hits:

Date of Publication:2017-04-25

Journal:CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE

Included Journals:SCIE、EI

Volume:29

Issue:8

ISSN No.:1532-0626

Key Words:C4.5; decision trees; MapReduce; parallel computing

Abstract:In the supervised classification, large training data are very common, and decision trees are widely used. However, as some bottlenecks such as memory restrictions, time complexity, or data complexity, many supervised classifiers including classical C4.5 tree cannot directly handle big data. One solution for this problem is to design a highly parallelized learning algorithm. Motivated by this, we propose a parallelized C4.5 decision tree algorithm based on MapReduce (MR-C4.5-Tree) with 2 parallelized methods to build the tree nodes. First, an information entropy-based parallelized attribute selection method (MR-A-S) on several subsets for MR-C4.5-Tree is proposed to confirm the best splitting attribute and the cut points. Then, a data splitting method (MR-D-S) in parallel is presented to partition the training data into subsets. At last, we introduce the MR-C4.5-Tree learning algorithm that grows in a top-down recursive way. Besides, the depth of the constructed decision tree, the number of samples and the maximal class probability in each tree node are used as the termination conditions to avoid the over-partitioning problem. Experimental studies show the feasibility and the good performance of the proposed parallelized MR-C4.5-Tree algorithm.