Efficient Construction of Decision Trees by the Dual Information Distance Method

摘要

TheconstructionofefficientdecisionandclassificationtreesisafundamentaltaskinBigDataanalyticswhichisknowntobeNP-hard.Accordingly,manygreedyheuristicsweresuggestedfortheconstructionofdecision-trees,butwerefoundtoresultinlocal-optimumsolutions.Inthisworkwepresentthedualinformationdistance(DID)methodforefficientconstructionofdecisiontreesthatiscomputationallyattractive,yetrelativelyrobusttonoise.TheDIDheuristicselectsfeaturesbyconsideringboththeirimmediatecontributiontotheclassification,aswellastheirfuturepotentialeffects.Itrepresentstheconstructionofclassificationtreesbyfindingtheshortestpathsoveragraphofpartitionsthataredefinedbytheselectedfeatures.TheDIDmethodtakesintoaccountboththeorthogonalitybetweentheselectedpartitions,aswellasthereductionofuncertaintyontheclasspartitiongiventheselectedattributes.WeshowthattheDIDmethodoftenoutperformspopularclassifiers,intermsofaveragedepthandclassificationaccuracy.