基于多目标最优化的最小代价决策树构建与实现

Construction and Implementution of Minimum Cost Decision Tree Based on Multi-Objective Optimization

提出一种基于多目标最优化的代价敏感决策树构建方法。将误分类代价、测试代价、等待时间代价和信息增益率作为四个优化目标,利用线性加权和法把多目标最优化问题转化成单目标最优化问题,作为分裂属性选择的准则。然后提出了构建最小代价决策树的具体策略和测试决策树的一个混合测试方法。最后,用该算法和其它两个算法在两个真实的数据集中进行构建、测试,实验结果表明,该方法获得的决策树具有更小的代价,效率更高,泛化能力更强。该方法在医疗诊断中表现尤为突出。

A multi-objective optimization based on the cost sensitive decision tree building method is proposed.The misclassification cost,test cost,waiting time cost and information gain rate as four optimization goal,the method of linear weighting is used to transfer the multi-objective optimization problem into single objective optimization problem,as the splitting attribute selection criterion.And then the concrete strategy of building the minimum cost decision tree and a hybrid testing decision tree method are put forward.Finally,the algorithm and two other algorithms in two real datasets are used to build decision trees and test the trees,and experimental results show that the decision tree obtained by this method has a smaller cost,more efficient and stronger generalization ability.The method is especially useful in medical diagnostic.