基于蚁群优化的改进决策树算法研究张忠坤，周亚建**（北京邮电大学信息安全中心，北京100876）510152025303540摘要：本文提出了一种新的基于蚁群优化的改进决策树算法(ACODT,AntColonyOptimizationDecisionTree)，该算法充分利用了蚁群算法的信息素反馈和启发搜索特征来改进决策树的生成过程。选取15个UCI数据集进行实验并与C4.5和CART算法进行比较。实验结果表明，改进算法适用于连续属性和离散属性，能够有效提高决策树预测精度，降低决策树规模，增强可理解性。关键词：决策树；蚁群算法；信息素；启发信息；中图分类号：TP301.6ImprovingdecisiontreesbasedonanantcolonyalgorithmZHANGZhongkun,ZHOUYajian(InformationSecurityCenter,BeijingUniversityofPostsandCommunications,Beijing100876,China)Abstract:Inthispaperweproposeanewdecisiontreealgorithmbasedonanantcolonyalgorithm,whichmakesfulluseofthepheromonefeedbackandheuristicinformationintheantcolonyalgorithm.Theproposedalgorithmiscomparedagainsttwowell-knowndecisiontreealgorithm,C4.5andCART,in15datasets.Theexperimentalresultsshowthattheproposeddecisiontreealgorithmissuitableforbohcontinuousattributesanddiscreteattributes.Itcaneffectivelyimprovethegenerateddecisiontree'spredictionaccuracy,reduceitssizeandenhanceitsintelligibility.Keywords:decisiontree;antcolonyalgorithm;pheromone;heuristicinformation;0引言决策树算法是机器学习领域具有代表性的算法之一，具有分类速度快、精度高、生成过程简单以及产生的规则易于理解等优点，已经被成功地应用到计算机辅助医疗诊断、数据挖掘、风险评估等领域。但是，决策树算法也存在着对噪声敏感、在测试属性选择时倾向于选择取值较多的属性等缺陷。蚁群算法是一种模拟真实蚁群的觅食行为而形成的仿生算法，具有分布计算、信息正反馈和启发式搜索等特征，易于与其它方法结合，形成优化算法[1][2]。因此，许多研究人员尝试利用蚁群算法来对决策树算法进行优化，并提出了许多有效的决策树改进算法，主要有分类回归树算法(CART,ClassificationAndRegressionTree)和二叉决策树算法(ACDT,AntColonyDecisionTree)。这两种改进方法在一定程度上提高了决策树算法的预测精度，但是它们只是利用了蚁群算法的一部分特征，没有充分挖掘蚁群算法的优势。本文提出了一种基于蚁群优化的改进决策树算法，充分利用了蚁群算法的信息素反馈和启发搜索特征，将蚁群算法的优势引入到决策树中。仿真结果表明，改进算法能够提高决策树预测精度，降低决策树规模，并且增强了决策树的可理解性。作者简介：张忠坤（1988-），男，硕士研究生通信联系人：周亚建（1971-），男，副教授.zhouyajian@126.com-1-1相关研究目前利用蚁群算法来改进决策树的方法主要有两种，分别是分类回归树算法和二叉决策树算法。分类回归树算法[3]是由Izrailev和Agrafiotis提出的一种基于蚁群建立分类回归决策树的455055方法。在该方法中，蚂蚁表示递归树，信息素矩阵利用二叉参考树表示，二叉参考树与已生成树形成的拓扑结构保持一致。树的决策结点由二叉条件确定，信息素通过选择属性和属性值来创建决策结点。该方法的缺点主要有两个：一是只适用于连续属性；二是没有充分利用蚁群算法中的启发信息。二叉决策树算法[4]是由Boryczka和Kozak提出的。在该方法中，决策树结点通过二叉条件确定，因此决策结点将会有两条输出边。信息素值表示“父结点”和“子结点”之间的关联程度。该方法的缺点主要有两个：一是不适用于连续属性；二是每个结点只有两个分枝，生成的决策树规模比较大，不易于理解。2改进决策树算法改进算法的伪代码如图1所示。输入：训练集输出：决策树模型1.初始化信息素2.计算启发信息3.Treegb=Ø4.m=05.whilem<maximumiterationsandnotconvergence()dotreeib=Ø;forn1tocolonysizedotreen=CreateTree(Examples,Attributes,-);Prune(treen);ifAccuracy(treen)>Accuracy(treeib)thentreeib=treen;endifendforUpdatePheromones(treeib);ifAccuracy(treeib)>Accuracy(tr...