一种改进的MEP决策树剪枝算法

An improved pruning algorithm for MEP decision tree

决策树剪枝是将已生成的决策树进行简化的过程,包括预剪枝和后剪枝。为了提高后剪枝算法MEP的剪枝精度,防止因MEP影响因子选取不当造成决策树修剪过度而丢失特征信息的问题,提出一种改进的MEP算法即IMEP方法。首先引入k-折交叉验证(k-Fold Cross-Validation)方法用于选取最优的影响因子m,然后将m带入到MEP算法,再对原始决策树进行剪枝,可以得到最精确的决策树,并保持决策树的影响特征。其次,通过k次交叉验证,可以避免产生过拟合问题,和单独测试集方法相比,经过k次交叉验证后,已经减弱了随机性,防止出现“欠学习”问题。经过验证IMEP方法不仅提高了MEP的精度,能更精准简化决策树,并且保持决策树的影响特征。相比于PEP算法,在数据集较小时有更好的适用性,表现更加稳定。

Decision tree pruning is to simplify the generated decision tree both in the pre-pruning and post-pruning.In order to improve the pruning accuracy of post-pruning algorithm MEP and prevent the problems of excessive pruning of decision tree and loss of feature information caused by improper selection of influence factors of MEP,an improved MEP algorithm called IMEP algorithm is proposed.First,the k-Fold Cross-Validation method is introduced to select the optimal impact factor m,and the factor m is introduced into MEP algorithm.By pruning the original decision tree,the most precise decision tree can be obtained and the impact characteristics of the decision tree can be maintained.Secondly,the problem of over-fitting can be avoided by k-times cross-validation.Compared with the single test set,after k-times cross-validation,the randomness has been weakened and the problem of under-learning has been prevented.After verification,IMEP algorithm not only improves the accuracy of MEP,but also simplifies the decision tree more precisely,and maintains the influence characteristics of the decision tree.Compared with PEP algorithm,it has better applicability and more stable performance when the data set is small.