Title of Paper:A fast rank mutual information based decision tree and its implementation via Map-Reduce

Hits:

Date of Publication:2018-05-25

Journal:CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE

Included Journals:SCIE、EI

Volume:30

Issue:10

ISSN No.:1532-0626

Key Words:classification; decision trees; dominance rough sets; Map-Reduce; parallel computing

Abstract:To address the time-consuming problem for the confirmation of splitting attributes and splitting points in classic rank mutual information based decision trees, this paper establishes a fast rank mutual information based decision tree (FRMIDT) for classification problems. First, the proposed FRMIDT algorithm improves the velocity by a max-relevance and min-redundancy criterion to remove the redundant attributes in each tree node building. Then, the fuzzy c-means algorithm is employed to confirm the splitting points for further acceleration. Meanwhile, a parallel implementation is developed in the framework of Map-Reduce (MR-FRMIDT) for medium or large-scale data classification. Several comparative studies are conducted on UCI benchmark data sets. In contrast to the classic rank mutual information based decision tree on 12 data sets, the proposed FRMIDT model effectively reduces the computational time on the premise of keeping testing accuracy. Furthermore, the proposed FRMIDT algorithm is comparable through comparing FRMIDT with other traditional decision tree classifiers including BFT, C4.5, LAD, NBT, and SC. Meanwhile, the comparison with 7 different popular splitting measures based monotonic decision trees on several data sets illustrates the effectiveness of FRMIDT in monotonic classification. At last, the experimental analysis on other 6 data sets shows that the proposed MR-FRMIDT is feasible and has a good parallel performance on reducing execution time and avoiding memory restrictions.