The Research Of Ordinal Decision Trees Efficient Algorithms Based On Rank Entropy

In the induction of ordinal decision tree, for each cut, it is necessary to compute its rankmutual information, the attribute with maximal rank mutual information is selected asexpanded attribute, the computational complexity is very high. Especially it will be abottleneck for inducing ordinal decision tree from large data sets.In order to deal with the problems mentioned above, in this paper, it is studied how toimprove the computational efficiency of ordinal decision tree. The main works consist of thefollowing two aspects:1. The cuts are classified into unstable cuts and stable cuts, a mathematical model isconstructed for describing the rank mutual information, it is proved theoretically that the rankmutual information function will achieve its maximum in unstable cuts, rather than the stablecuts. This result means that the algorithm can only traverses its unstable cuts, it is notnecessary to compute the rank mutual information of stable cuts, and therefore, thecomputational efficiency of inducing ordinal decision trees can be greatly improved.2. In order to solve ordinal classification of massive data, several strategies ofparallelization of ordinal decision tree are investigated. Based on MapReduce, a parallelapproach of ordinal decision tree is presented in this paper, which can reduce the time ofbuilding trees and improve the computational efficiency.Experimental results show that the improved ordinal decision tree based on rank entropycan greatly enhance computational efficiency on artificial and real data sets respectively.