A Research On Decision Tree Learning From The View Of Optimization

Decision trees are a classic class of machine learning methods,and also the base learners for ensemble learning such as random forests and gradient boosting trees,they have been successfully used in many fields such as pattern recognition,data mining,bioinformatics and so on.How to design the splitting criterion and effectively search the splits is the key issue of decision tree learning.Based on the idea of optimizing the objective function in statistical learning,this thesis studies the design of splitting criteria and split search,and has achieved the following innovative results:A new splitting criterion based on ranking loss is proposed: Pairwise Gain.Traditional splitting criteria are mainly designed from some perspectives such as information theory or statistics.From the view of optimizing loss functions,this thesis presents a unified framework for splitting criteria,which are essentially equivalent to optimizing different point-wise loss functions.Under this framework,this thesis derives a new splitting criterion,named Pairwise Gain,which is motivated by the optimization of the lower bound of total pairwise loss(eg.ranking loss).Theoretical and experimental results verify that the proposed criterion is so robust to random label noise that decision trees and random forests under noise get better performance.A new oblique decision tree based on continuous optimization to search split is proposed: Weighted Oblique Decision Tree.The traditional construction algorithms of decision trees calculate scores for all heuristic candidate splits based on a certain splitting criterion.This thesis proposes a weighted oblique decision tree,named WODT,which needs only random initialization and continuous optimization to find valid splits.The experimental results show that the proposed method WODT has better predictionaccuracy than the previous decision trees,and has more compact tree structures,and the construction speed is faster than previous oblique decision trees.