A fast rank mutual information based decision tree and its implementation via Map‐Reduce. (8th January 2018)

• Record Type: Journal Article
• Authors: Mu, Yashuang; Wang, Lidong; Liu, Xiaodong
• Is Part Of: Concurrency and computation. Volume 30:Number 10(2018)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2018-01-08
• Subjects: classification -- decision trees -- dominance rough sets -- Map‐Reduce -- parallel computing; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.4387
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: 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.