D0I:10.13374/1.issnl00103.2007.04.013 第29卷第4期 北京科技大学学报 Vol.29 No.4 2007年4月 Journal of University of Science and Technology Beijing Apr.2007 一种多标准决策树剪枝方法及其在入侵检测中的应用 李卫东)宋威)李欣)杨炳儒) 1)河北经贸大学信息技术学院，石家庄0500612)北京科技大学信息工程学院，北京100083 摘要为提高决策树的适用性，以决策树在入侵检测中的应用为背景提出一种多标准的剪枝方法，使决策树程序能在参数 调整后适应不同的应用·给出了用于描述决策树不同性能的一些参量，如稳定性、复杂度、分类能力等，用户可以根据具体情 况对向量各分量的权重进行调整，逐步得到满足要求的决策树，实验结果表明，该算法能够根据入侵检测系统的具体需要，快 速地构建相应的决策树，从而程序可被用于不同情况·该方法把由程序员决定决策树变成了由用户决定决策树，程序更通用， 结果更合理 关键词入侵检测：决策树：剪枝：稳定性：复杂度；分类能力 分类号TP18 入侵检测是现代计算机网络安全的一个重要方 应用更重视它预测与分类的精确性与稳定性，在规 面，由于网络带宽的不断增加、网络内容的迅速扩 则推理中更多考虑规则的简洁性与适用性，在入侵 充、入侵方式的快速发展等原因，系统处理速度成为 检测中更注重处理速度，本文在开发入侵检测系统 最大的瓶颈，最好的办法就是把网络封包快速分成 时使用了两层决策树：第一层用于对网络封包进行 若干小类，然后用相应的子系统进行处理或丢弃，决 快速分类，第二层对某些入侵进行定性分析，所以 策树就是一种非常合适的分类工具， 笔者研究开发了一种可以根据多个标准进行剪枝的 决策树算法ID3(inductive dichotomiser3)凹最 算法，只要调整部分参数，决策树就能在多种要求组 早是由Quinlan提出的一种归纳分类模型的算法， 合下找到最佳平衡点，从而适用于多种情况 是数据挖掘中的一种重要分类算法，有十分广泛的 商业应用，决策树学习策略也广泛应用于模式识别 1主要的后剪枝方法 和机器学习等领域，用来解决与分类相关的问题 目前主要的后剪枝方法有四种：悲观错误剪枝 生成算法与剪枝算法是决策树研究中的核心 (pessimistic error pruning,PEP);最小错误剪枝 问题 (minimum error pruning,MEP);代价复杂度剪枝 生成过程即建立决策树的过程，是不断地把训 (cost -complexity pruning,CCP);基于错误的剪枝 练数据集进行划分的过程，每层划分对应一个属性， (error-based pruning,EBP). 此属性应使划分后的分组“差异”最大，决策树生成 在讨论各种后剪枝算法之前，先给出一些术语 算法的不同主要体现在对“差异”的衡量方式上，例 和符号. 如ID3采用信息熵增益衡量差异，C4.5[则采用增 “大多数原则"(majority class criterion):剪枝过 益比衡量差异。 程中，将一些子树删除而用叶节点代替，这个叶节点 剪枝过程是让决策树更一般化，以适应新样本 所标识的类别用这棵子树中大多数训练样本所属的 的过程，常见的剪枝策略有预剪枝(pre pruning)技 类别来标识，所标识的类称为majority class,可以叫 术和后剪枝(post pruning)技术.预剪枝技术主要是 做节点主类 通过建立某些规则限制决策树的充分生长，后剪枝 Tmax:由决策树生成算法生成的未剪枝的完 技术则是待决策树充分生长完毕后再进行剪枝，后 全决策树 剪枝应用比较多 Tt:以内部节点t为根的一棵子树 不同应用对决策树的要求有不同的侧重，商业 (l)悲观错误剪枝PEP.Quinlan提出的PEP 收稿日期：2005-12-12修回日期：2006-04-19 剪枝算法从上至下遍历每一个内部节点，通过比较 基金项目：国家科技成果重点推广计划项目(N。.2003EC000001) 剪枝前、后的错分样本数来判断是否剪枝，它在ID3 作者简介：李卫东(1973一)，男，讲师，博士；杨炳儒(1943-)，男， 教授，博士生导师 系统中获得实现，PEP既采用训练集来生成决策树一种多标准决策树剪枝方法及其在入侵检测中的应用 李卫东1） 宋 威2） 李 欣2） 杨炳儒2） 1） 河北经贸大学信息技术学院‚石家庄050061 2） 北京科技大学信息工程学院‚北京100083 摘 要 为提高决策树的适用性‚以决策树在入侵检测中的应用为背景提出一种多标准的剪枝方法‚使决策树程序能在参数 调整后适应不同的应用．给出了用于描述决策树不同性能的一些参量‚如稳定性、复杂度、分类能力等‚用户可以根据具体情 况对向量各分量的权重进行调整‚逐步得到满足要求的决策树．实验结果表明‚该算法能够根据入侵检测系统的具体需要‚快 速地构建相应的决策树‚从而程序可被用于不同情况．该方法把由程序员决定决策树变成了由用户决定决策树‚程序更通用‚ 结果更合理． 关键词 入侵检测；决策树；剪枝；稳定性；复杂度；分类能力 分类号 TP18 收稿日期：20051212 修回日期：20060419 基金项目：国家科技成果重点推广计划项目（No．2003EC000001） 作者简介：李卫东（1973—）‚男‚讲师‚博士；杨炳儒（1943—）‚男‚ 教授‚博士生导师 入侵检测是现代计算机网络安全的一个重要方 面．由于网络带宽的不断增加、网络内容的迅速扩 充、入侵方式的快速发展等原因‚系统处理速度成为 最大的瓶颈．最好的办法就是把网络封包快速分成 若干小类‚然后用相应的子系统进行处理或丢弃‚决 策树就是一种非常合适的分类工具． 决策树算法 ID3（inductive dichotomiser3） ［1］最 早是由 Quinlan 提出的一种归纳分类模型的算法‚ 是数据挖掘中的一种重要分类算法‚有十分广泛的 商业应用‚决策树学习策略也广泛应用于模式识别 和机器学习等领域‚用来解决与分类相关的问题． 生成算法与剪枝算法是决策树研究中的核心 问题． 生成过程即建立决策树的过程‚是不断地把训 练数据集进行划分的过程‚每层划分对应一个属性‚ 此属性应使划分后的分组“差异”最大．决策树生成 算法的不同主要体现在对“差异”的衡量方式上‚例 如 ID3采用信息熵增益衡量差异‚C4∙5［2］则采用增 益比衡量差异． 剪枝过程是让决策树更一般化‚以适应新样本 的过程．常见的剪枝策略有预剪枝（pre-pruning）技 术和后剪枝（post-pruning）技术．预剪枝技术主要是 通过建立某些规则限制决策树的充分生长‚后剪枝 技术则是待决策树充分生长完毕后再进行剪枝‚后 剪枝应用比较多． 不同应用对决策树的要求有不同的侧重‚商业 应用更重视它预测与分类的精确性与稳定性‚在规 则推理中更多考虑规则的简洁性与适用性‚在入侵 检测中更注重处理速度．本文在开发入侵检测系统 时使用了两层决策树：第一层用于对网络封包进行 快速分类‚第二层对某些入侵进行定性分析．所以 笔者研究开发了一种可以根据多个标准进行剪枝的 算法‚只要调整部分参数‚决策树就能在多种要求组 合下找到最佳平衡点‚从而适用于多种情况． 1 主要的后剪枝方法 目前主要的后剪枝方法有四种：悲观错误剪枝 （pessimistic error pruning‚PEP ）；最 小 错 误 剪 枝 （minimum error pruning‚MEP）；代价复杂度剪枝 （cost-complexity pruning‚CCP）；基于错误的剪枝 （error-based pruning‚EBP）． 在讨论各种后剪枝算法之前‚先给出一些术语 和符号． “大多数原则”（majority class criterion）：剪枝过 程中‚将一些子树删除而用叶节点代替‚这个叶节点 所标识的类别用这棵子树中大多数训练样本所属的 类别来标识‚所标识的类称为 majority class‚可以叫 做节点主类． Tmax：由决策树生成算法生成的未剪枝的完 全决策树． Tt：以内部节点 t 为根的一棵子树． （1） 悲观错误剪枝 PEP．Quinlan 提出的 PEP 剪枝算法从上至下遍历每一个内部节点‚通过比较 剪枝前、后的错分样本数来判断是否剪枝‚它在 ID3 系统中获得实现．PEP 既采用训练集来生成决策树 第29卷 第4期 2007年 4月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．29No．4 Apr．2007 DOI:10．13374／j．issn1001－053x．2007．04．013