第4期 李卫东等：一种多标准决策树剪枝方法及其在入侵检测中的应用 429 又用它来进行剪枝，不需要独立的剪枝集，剪掉以t 为根节点的子树而代之为一个叶节点，该叶节点所 2多标准剪枝方法 标识的类别由“大多数原则”确定 决策树剪枝算法通常采用单一标准，最常用的 PEP剪枝算法中当某个子树Tt满足剪枝条件 是分类精度，但是还有好多标准也是很值得考虑的， 时将不再对其后裔进行剪枝判断，因此PEP方法 如速度、鲁棒性、复杂性、训练时间、分类粒度等，用 收敛速度较快，但最坏情况下仍然每个节点都要遍 户对决策树性能的不同要求，决定最终生成什么样 历，为线性复杂度 的决策树.Esposito等研究者[试图采用复合标准 (2)最小错误剪枝MEP,Niblett和Bratko]于 进行实验，并对什么是最佳标准组合展开讨论 l986年提出的MEP利用Laplace概率估计来提高 本文提出了一个多标准的组合评价方法，通过 ID3算法在噪声域中的性能.所使用的独立数据集 选择每个标准分量的权重，用户最终决定自己所要 仅用来简化对未知样本的错分率估计，实际上无论 的决策树，而不再是编程者，让实践来决定最佳标 早期版本还是改进版本均只利用了训练集的信息进 准，本文把除精度外（精度可采用任何标准剪枝方 行剪枝 法中的定义)其他常用的标准进行的量化，可能并不 MEP算法自底向上遍历完全决策树并计算子 完备，但本算法是一个开放的算法，通过调整决策树 树的静态错误和动态错误，当满足静态错误小于动 性能描述向量中的分量，很容易加入新的分类标准 态错误时剪枝，并用一个叶节点来代替，该叶节点所 2.1基本概念 标识的类别由“大多数原则”来确定 先介绍文中出现的基本概念， N:为训练集的总数；N,:为测试集总数 在MEP剪枝算法中，可以通过参数的调整来 决定剪枝程度的大小 n(t):到达节点t的所有训练集样本数目； v(t):到达节点t的测试集样本数目 (3)代价一复杂度剪枝CCP.CCP剪枝算法在 Breimen3]等人开发的CART系统中得到实现.它 v(i,t):到达节点t且属于节点主类i的测试 集样本数目， 为子树Tt定义了代价(cost)和复杂度(complexity), e(t):到达节点t但不属于节点t所标识的类 以及一个可由用户设置的衡量代价与复杂度之间关 别的训练集样本数目；e(t):到达节点t但不属于 系的参数a,CCP剪枝的结果是得到一棵错分样本 节点t所标识的类别的测试集样本数目. 数和规模相折中的决策树， r(t):训练集错分样本率，其值为e(t)/n(t): (4)基于错误剪枝EBP,C4.5系统采用EBP ,(t):测试集错分样本率，其值为e(t)/v(t) 做剪枝算法I,可以认为是PEP的改进，它对期望 定义1稳定性：对叶节点t,稳定性S(t)= 错误率的估计比PEP更悲观。剪枝过程中，EBP无 mini(1-r(t)/(1-,(t),(1-,(t)/ 需专用的剪枝集，训练集用于生成决策树同时也用 (1一r(t){,S(t)∈[0,1]全树的稳定性为： 来剪枝 EBP较PEP更倾向于悲观剪枝，但与其他被测 sn-t空w)s(0 方法相比仍具有较高的精确度，EBP剪枝算法通过 定义2复杂度：决策树的复杂度也是经常要 CF值来控制剪枝的强度，CF设定的越高，当前错误 考虑的一个重要因素，通常可以由树叶的数量或规 率越易被接受，即若CF=1,则不需要进行剪枝；采 则的深度来形成表达函数，下面给出两组经验 用较小的CF值叶节点上出现的错误率要高于CF 公式. 值较大情况下的错误率， ()以叶节点为标准.决策树的叶节点数量代 大多数情况下剪枝并不会使预测精度降低，只 表总体分成的类别数量，过多可能会造成树的深度 有个别邻域可能较难控制；而对于所生成的剪枝树 加大，分类算法失效等现象.但是根据经验，叶节点 的复杂程度来说，MEP、CCP和EBP容易产生“欠 在4到10之间比较适用，少于2或多于25的决策 剪枝”，而使用规则1SE(1 standard error of mini- 树就不太实用，所以给出以下公式： mum error))倾向于“过剪枝”.PEP和EBP除了计 Simleaf(k)=0,当k<2或k>25; 算公式不同外，本质上没有区别，行为表现相似，在 Simeleaf(k)=k/4,当2≤k<4; 所比较的算法里它们相对来说有较高的预测精 Simieaf(k)=1,当4≤k≤10： 确度 Simleaf(k)=(25-k)/(25-10),当10<k≤又用它来进行剪枝‚不需要独立的剪枝集．剪掉以 t 为根节点的子树而代之为一个叶节点‚该叶节点所 标识的类别由“大多数原则”确定． PEP 剪枝算法中当某个子树 Tt 满足剪枝条件 时将不再对其后裔进行剪枝判断‚因此 PEP 方法 收敛速度较快‚但最坏情况下仍然每个节点都要遍 历‚为线性复杂度． （2） 最小错误剪枝 MEP．Niblett 和Bratko ［2］于 1986年提出的 MEP 利用 Laplace 概率估计来提高 ID3算法在噪声域中的性能．所使用的独立数据集 仅用来简化对未知样本的错分率估计‚实际上无论 早期版本还是改进版本均只利用了训练集的信息进 行剪枝． MEP 算法自底向上遍历完全决策树并计算子 树的静态错误和动态错误‚当满足静态错误小于动 态错误时剪枝‚并用一个叶节点来代替‚该叶节点所 标识的类别由“大多数原则”来确定． 在 MEP 剪枝算法中‚可以通过参数的调整来 决定剪枝程度的大小． （3） 代价—复杂度剪枝 CCP．CCP 剪枝算法在 Breimen ［3］等人开发的 CART 系统中得到实现．它 为子树 Tt 定义了代价（cost）和复杂度（complexity）‚ 以及一个可由用户设置的衡量代价与复杂度之间关 系的参数 α．CCP 剪枝的结果是得到一棵错分样本 数和规模相折中的决策树． （4） 基于错误剪枝 EBP．C4∙5系统采用 EBP 做剪枝算法［4］‚可以认为是 PEP 的改进‚它对期望 错误率的估计比 PEP 更悲观．剪枝过程中‚EBP 无 需专用的剪枝集‚训练集用于生成决策树同时也用 来剪枝． EBP 较 PEP 更倾向于悲观剪枝‚但与其他被测 方法相比仍具有较高的精确度．EBP 剪枝算法通过 CF 值来控制剪枝的强度‚CF 设定的越高‚当前错误 率越易被接受．即若 CF＝1‚则不需要进行剪枝；采 用较小的 CF 值叶节点上出现的错误率要高于 CF 值较大情况下的错误率． 大多数情况下剪枝并不会使预测精度降低‚只 有个别邻域可能较难控制；而对于所生成的剪枝树 的复杂程度来说‚MEP、CCP 和 EBP 容易产生“欠 剪枝”‚而使用规则1—SE （1standard error of mini￾mum error）） 倾向于“过剪枝”．PEP 和 EBP 除了计 算公式不同外‚本质上没有区别‚行为表现相似‚在 所比较的算法里它们相对来说有较高的预测精 确度． 2 多标准剪枝方法 决策树剪枝算法通常采用单一标准‚最常用的 是分类精度‚但是还有好多标准也是很值得考虑的‚ 如速度、鲁棒性、复杂性、训练时间、分类粒度等．用 户对决策树性能的不同要求‚决定最终生成什么样 的决策树．Esposito 等研究者［5］试图采用复合标准 进行实验‚并对什么是最佳标准组合展开讨论． 本文提出了一个多标准的组合评价方法‚通过 选择每个标准分量的权重‚用户最终决定自己所要 的决策树‚而不再是编程者‚让实践来决定最佳标 准．本文把除精度外（精度可采用任何标准剪枝方 法中的定义）其他常用的标准进行的量化‚可能并不 完备‚但本算法是一个开放的算法‚通过调整决策树 性能描述向量中的分量‚很容易加入新的分类标准． 2∙1 基本概念 先介绍文中出现的基本概念． Nt：为训练集的总数；Nv：为测试集总数． n（ t ）：到达节点 t 的所有训练集样本数目； v （ t）：到达节点 t 的测试集样本数目． v（ i‚t）：到达节点 t 且属于节点主类 i 的测试 集样本数目． e（ t）：到达节点 t 但不属于节点 t 所标识的类 别的训练集样本数目；ev （ t）：到达节点 t 但不属于 节点 t 所标识的类别的测试集样本数目． r（ t）：训练集错分样本率‚其值为 e（ t）／n（ t）； rv（ t）：测试集错分样本率‚其值为 ev（ t）／v （ t）． 定义1 稳定性：对叶节点 t‚稳定性 S （ t）＝ min｛（1— r （ t ））／（1— rv（ t））‚（1— rv （ t ））／ （1— r（ t））｝‚S（ t）∈［0‚1］全树的稳定性为： STmax＝ 1 Nt ∑ n t＝1 n（ t） S（ t）． 定义2 复杂度：决策树的复杂度也是经常要 考虑的一个重要因素‚通常可以由树叶的数量或规 则的深度来形成表达函数．下面给出两组经验 公式． （1） 以叶节点为标准．决策树的叶节点数量代 表总体分成的类别数量‚过多可能会造成树的深度 加大‚分类算法失效等现象．但是根据经验‚叶节点 在4到10之间比较适用‚少于2或多于25的决策 树就不太实用‚所以给出以下公式： Simleaf（ k）＝0‚当 k＜2或 k＞25； Simeleaf（ k）＝k／4‚当2≤k＜4； Simleaf（ k）＝1‚当4≤k≤10； Simleaf（ k）＝（25— k）／（25—10）‚当10＜ k≤ 第4期 李卫东等： 一种多标准决策树剪枝方法及其在入侵检测中的应用 ·429·