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 pruningPEP ）；最 小 错 误 剪 枝 （minimum error pruningMEP）；代价复杂度剪枝 （cost-complexity pruningCCP）；基于错误的剪枝 （error-based pruningEBP）． 在讨论各种后剪枝算法之前先给出一些术语 和符号． “大多数原则”（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
第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,当k25; 算公式不同外，本质上没有区别，行为表现相似，在 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 minimum error）） 倾向于“过剪枝”．PEP 和 EBP 除了计 算公式不同外本质上没有区别行为表现相似在 所比较的算法里它们相对来说有较高的预测精 确度． 2 多标准剪枝方法 决策树剪枝算法通常采用单一标准最常用的 是分类精度但是还有好多标准也是很值得考虑的 如速度、鲁棒性、复杂性、训练时间、分类粒度等．用 户对决策树性能的不同要求决定最终生成什么样 的决策树．Esposito 等研究者［5］试图采用复合标准 进行实验并对什么是最佳标准组合展开讨论． 本文提出了一个多标准的组合评价方法通过 选择每个标准分量的权重用户最终决定自己所要 的决策树而不再是编程者让实践来决定最佳标 准．本文把除精度外（精度可采用任何标准剪枝方 法中的定义）其他常用的标准进行的量化可能并不 完备但本算法是一个开放的算法通过调整决策树 性能描述向量中的分量很容易加入新的分类标准． 2∙1 基本概念 先介绍文中出现的基本概念． Nt：为训练集的总数；Nv：为测试集总数． n（ t ）：到达节点 t 的所有训练集样本数目； v （ t）：到达节点 t 的测试集样本数目． v（ it）：到达节点 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）∈［01］全树的稳定性为： 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·
.430 北京科技大学学报 第29卷 25. 重复步骤2，直到参数不能优化，得到按这个标 (2)以决策树深度为标准.决策树深度代表规 准集剪枝的最优树，如果不满意，可以修改系统参 则的复杂程度，通常决策树中规则的平均长度会在 数，再次剪枝，直到最终满意为止， 2到8之间，更短或更长都不好，所以定义分段 函数： 3实验结果与分析 Simndle=1,当2≤Lnle≤3； 3.1实验结果 Simndle=|9-Lnle|/5,当4≤Lmle≤8； 实验数据来自美国国防部高级计划署、美国空 Simnule=0,当Lrule>8 军研究实验室与麻省理工学院信息技术小组联合推 定义3分类能力：决策树是不是有用的一个 出的标准入侵检测测试数据，这些数据是检测入侵 重要的衡量指标是叶节点的分类识别能力，每个叶 检测系统检测能力与错误率的标准数据集 节点代表的分类越精确说明决策树越好，使用测试 采用DARPA2O00对于Windows NT的测试 集来测量叶节点的后验分类准确率，δ是给定的阈 集，分成外网与内网两个部分，共238MB,使用Nt- 值，叶节点t的分类能力用D(t)表示，如果 poke把TCPDU MP的网络封包进行重放，模拟当时 1-,(t)>ò，D(t)=1;反之D(t)=0. 的网络环境，然后用捕捉器捕获，再送给决策树进行 树的分类能力为： 分类，最后把数据发送给相应的处理模块，封包注重 1 的是处理速度，所以树的简洁性权重比较大，用于 Drs=衣(i)D() 对入侵定性的决策树处理的数据量相对较少，但每 Drm∈[0,1]，数值越大说明分类越明确，出错率 一个判断的意义又比较重大，对精度的要求比较高， 越低 通过权重的调整，可以使一套程序适用于不同的 2.2剪枝过程 场合· 决策树在多个方面会有不同的表现，按用户的 在整个数据集中选取了70000条记录，其中， 需要剪枝成特定目标树的过程实际上是一个多变量 前50000条用于训练，其余的20000条用于测试. 决策过程，本文选用了比较直观又方便的权重 机器配置为：赛扬IV1.7 G Willamette,512MB内 模型. 存，编程工具VC6.0,选择5组参数得到5棵决策 每个树有一个性能描述向量，Teei=(vl,v2, 树，结果见表1. …,”m),向量分量可以是精度、稳定性、复杂度表达 表1调整剪枝参数后所得的决策树的性能对比表 能力等，也可以是本文未定义的其他性能描述参数， Table 1 Performance comparison of decision trees after parameters 把这些分量用一个公式进行合成，得到K: adjustment =之WP权重W要满足以下条件： 误报 序号S(T)D(T)Simnle Simi4 错报时间/ =1 率/%率/% w=1 10.7890.945 0.93 0.4179.23 6.9717.32 1 20.8120.9701.00 0.7507.366.02 14.17 W≥0 30.8700.952 1.00 0.0008.01 6.2319.30 步骤1： 40.8040.9721.00 0.8337.225.9713.48 (1)选择剪枝要使用的评价标准集，如果使用 50.7740.9791.001.0006.895.2212.21 分类能力，请给出阈值6. (②)给出关于准确率，稳定性的阈值 通过表1可以看出，参数调整可以使决策树性 (3)按需要调整复杂性公式的参数，给自己认 能产生较大的变化，用户可根据需要灵活地构建所 为更重要的属性更大的权值 需的决策树， 步骤2： 3.2与相关工作的比较 令Tm为T,计算T的性能参数，T:为T去 目前，已有一些学者将决策树方法应用于入侵 掉第i个叶节点，计算T:的性能参数.如果 检测.文献[6]利用决策树，提出一种基于Agent的 K(T)≥H(K(T),则停止，T为最优：否则，找到 分布式入侵检测系统.文献[7]提出一种基于决策 max(K(T),令T=T 树的、面向不同粒度空间的入侵检测方法，文献[8] 步骤3： 提出了一种模式匹配与决策树相结合的协议分析方
25． （2） 以决策树深度为标准．决策树深度代表规 则的复杂程度通常决策树中规则的平均长度会在 2到8之间更短或更长都不好所以定义分段 函数： Simrule＝1当2≤ L rule≤3； Simrule＝｜9— L rule｜／5当4≤ L rule≤8； Simrule＝0当 L rule＞8． 定义3 分类能力：决策树是不是有用的一个 重要的衡量指标是叶节点的分类识别能力每个叶 节点代表的分类越精确说明决策树越好．使用测试 集来测量叶节点的后验分类准确率δ是给定的阈 值叶 节 点 t 的 分 类 能 力 用 D （ t ） 表 示．如 果 1— rv（ t）＞δD（ t）＝1；反之 D（ t）＝0． 树的分类能力为： DTmax＝ 1 Nv ∑ n t＝1 v （ it） D（ t）． DTmax∈［01］数值越大说明分类越明确出错率 越低． 2∙2 剪枝过程 决策树在多个方面会有不同的表现按用户的 需要剪枝成特定目标树的过程实际上是一个多变量 决策过程．本文选用了比较直观又方便的权重 模型． 每个树有一个性能描述向量Ttree i＝（ vi1vi2 …vin）向量分量可以是精度、稳定性、复杂度表达 能力等也可以是本文未定义的其他性能描述参数 把这 些 分 量 用 一 个 公 式 进 行 合 成得 到 Ki ＝ ∑ n j＝1 Wijvij权重 Wij要满足以下条件： ∑ n j＝1 Wij ＝1 Wij ≥0 步骤1： （1） 选择剪枝要使用的评价标准集如果使用 分类能力请给出阈值 δ． （2） 给出关于准确率稳定性的阈值． （3） 按需要调整复杂性公式的参数给自己认 为更重要的属性更大的权值． 步骤2： 令 T max为 T计算 T 的性能参数Ti 为 T 去 掉第 i 个 叶 节 点计 算 Ti 的 性 能 参 数．如 果 K（ T）≥∀（ K（ Ti））则停止T 为最优；否则找到 max（ K（ Ti））令 T＝ Ti． 步骤3： 重复步骤2直到参数不能优化得到按这个标 准集剪枝的最优树．如果不满意可以修改系统参 数再次剪枝直到最终满意为止． 3 实验结果与分析 3∙1 实验结果 实验数据来自美国国防部高级计划署、美国空 军研究实验室与麻省理工学院信息技术小组联合推 出的标准入侵检测测试数据这些数据是检测入侵 检测系统检测能力与错误率的标准数据集． 采用 DARPA 2000对于 Windows NT 的测试 集分成外网与内网两个部分共238MB使用 Netpoke 把 TCPDU MP 的网络封包进行重放模拟当时 的网络环境然后用捕捉器捕获再送给决策树进行 分类最后把数据发送给相应的处理模块封包注重 的是处理速度所以树的简洁性权重比较大．用于 对入侵定性的决策树处理的数据量相对较少但每 一个判断的意义又比较重大对精度的要求比较高． 通过权重的调整可以使一套程序适用于不同的 场合． 在整个数据集中选取了70000条记录其中 前50000条用于训练其余的20000条用于测试． 机器配置为：赛扬 IV 1∙7G Willamette512MB 内 存编程工具 VC 6∙0选择5组参数得到5棵决策 树结果见表1． 表1 调整剪枝参数后所得的决策树的性能对比表 Table1 Performance comparison of decision trees after parameters adjustment 序号 S（ T） D（ T） Simrule Simleaf 误报 率／％ 错报 率／％ 时间／ s 1 0∙789 0∙945 0∙93 0∙417 9∙23 6∙97 17∙32 2 0∙812 0∙970 1∙00 0∙750 7∙36 6∙02 14∙17 3 0∙870 0∙952 1∙00 0∙000 8∙01 6∙23 19∙30 4 0∙804 0∙972 1∙00 0∙833 7∙22 5∙97 13∙48 5 0∙774 0∙979 1∙00 1∙000 6∙89 5∙22 12∙21 通过表1可以看出参数调整可以使决策树性 能产生较大的变化用户可根据需要灵活地构建所 需的决策树． 3∙2 与相关工作的比较 目前已有一些学者将决策树方法应用于入侵 检测．文献［6］利用决策树提出一种基于 Agent 的 分布式入侵检测系统．文献［7］提出一种基于决策 树的、面向不同粒度空间的入侵检测方法．文献［8］ 提出了一种模式匹配与决策树相结合的协议分析方 ·430· 北 京 科 技 大 学 学 报 第29卷
第4期 李卫东等：一种多标准决策树剪枝方法及其在入侵检测中的应用 .431. 法，并应用于网络入侵检测，文献[9]利用决策树对 Bramer M A.Proceedings of Expert Systems'86.the Sixth An- 传统的基于协议分析的入侵检测方法进行了改进 nual Technical Conference of the British Computer Society Spe- cialist Group on Expert Systems.Brighton:Cambridge University 这些工作基本上都是直接利用传统的决策树对基于 Press,1987:25 模式匹配的入侵检测方法进行改进，虽然在误报率 [4]Breiman L,Friedman J.Olshen R.et al.Classification and Re- 和错报率方面有所改善，但无法根据具体需求产生 gression Trees-Belmont:Wadsworth.1984:1 不同的决策树，与这些工作相比，本文提出的算法 [5]姜欣，徐六通，张雷.C4.5决策树展示算法的设计.计算机工 在灵活性上，以及在多个决策树的同时使用上有一 程与应用，2003,4：96 定的优势 [6]Esposito F,Malerba D.Semeraro G.A comparative analysis of methods for pruning decision trees.IEEE Trans Pattern Anal 4结论 lach Intel,1997,19(5):476 [7]Baik S,Bala J.A decision tree algorithm for distributed data min- 本文提出的剪枝方法，可以使决策树软件更具 ing:towards network intrusion detection//Lagan A.Proceedings 有适应性和鲁棒性，尤其是一个系统中使用多个决 of the 2004 International Conference on Computational Science 策树的情况下可以灵活地调整每一棵树的表现，使 and Its Applications.Berlin:Springer,2004:206 [8]Amor N B.Benferhat S.Elouedi Z,et al.Decision trees and 每一个小部分工作在最佳状态，如何在分布式环境 qualitative possibilistic inference:application to the intrusion de- 下实现本方法，以及如何平衡参数的数量与算法复 tection problem//Nielsen T.Zhang N.Proceedings of 7th Euro- 杂度，是进一步的工作方向· pean Conference on Symbolic and Quantitative Approaches to Rea- soning with Uncertainty.Berlin:Springer.2003:419 参考文献 [9]Abbes T,Bouhoula A.Rusinowitch M.Protocol analysis in in [1]Quinlan J R.Induction of decision tree.Mach Learn.1986,1 trusion detection using decision treeIEEE Proceedings of the In (1):81 ternational Conference on Information lechnology:Coding and [2]Quinlan J R.C4.5:Programs for Machine Learning.San Ma- Computing Las Vegas:Institute of Electrical and Electronics En- teo:Morgan Kaufmann Publishers Inc,1993:302 gineers Computer Society,2004:404 [3]Niblett T,Bratko I.Learning decision rules in noisy domains// A multi-criterion pruning method for decision trees and its application in intrusion detection LI Weidong,SONG Wei),LI Xin2),YANG Bingru2) 1)Information Technology School.Hebei University of Economics and Business,Shijiazhuang 050061.China 2)Information Engineering School.University of Science and Technology Beijing.Beijing 100083.China ABSTRACI To improve the applicability of decision trees,a multi-criterion pruning method was proposed for the application of decision trees in intrusion detection,which enabled decision trees suitable for different condi- tions by parameter adjustment.Several parameters for describing the performance of a decision tree,such as sta- bility,complexity and classification ability,were proposed.To meet the needs of different applications,the de- cision tree was expressed as a vector.Weights of different components of the vector could be adjusted according to the fact,and the required decision tree could be built gradually.Experimental results show that the proposed method can rapidly construct different decision trees according different specific environments,thus one program can be used in different conditions.The approach changes the creator of a decision tree from a programmer to a user,so the program is more suitable and the result is more reasonable. KEY WORDS intrusion detection:decision tree;pruning:stability;complexity:classification ability
法并应用于网络入侵检测．文献［9］利用决策树对 传统的基于协议分析的入侵检测方法进行了改进． 这些工作基本上都是直接利用传统的决策树对基于 模式匹配的入侵检测方法进行改进虽然在误报率 和错报率方面有所改善但无法根据具体需求产生 不同的决策树．与这些工作相比本文提出的算法 在灵活性上以及在多个决策树的同时使用上有一 定的优势． 4 结论 本文提出的剪枝方法可以使决策树软件更具 有适应性和鲁棒性尤其是一个系统中使用多个决 策树的情况下可以灵活地调整每一棵树的表现使 每一个小部分工作在最佳状态．如何在分布式环境 下实现本方法以及如何平衡参数的数量与算法复 杂度是进一步的工作方向． 参 考 文 献 ［1］ Quinlan J R．Induction of decision tree．Mach Learn19861 （1）：81 ［2］ Quinlan J R．C4∙5：Programs for Machine Learning．San Mateo：Morgan Kaufmann Publishers Inc1993：302 ［3］ Niblett TBratko I．Learning decision rules in noisy domains∥ Bramer M A．Proceedings of Expert Systems’86the Sixth Annual Technical Conference of the British Computer Society Specialist Group on Expert Systems．Brighton：Cambridge University Press1987：25 ［4］ Breiman LFriedman JOlshen Ret al．Classification and Regression Trees．Belmont：Wadsworth1984：1 ［5］ 姜欣徐六通张雷．C4∙5决策树展示算法的设计．计算机工 程与应用20034：96 ［6］ Esposito FMalerba DSemeraro G．A comparative analysis of methods for pruning decision trees．IEEE Trans Pattern Anal Mach Intell199719（5）：476 ［7］ Baik SBala J．A decision tree algorithm for distributed data mining：towards network intrusion detection∥Lagan A．Proceedings of the 2004 International Conference on Computational Science and Its Applications．Berlin：Springer2004：206 ［8］ Amor N BBenferhat SElouedi Zet al．Decision trees and qualitative possibilistic inference：application to the intrusion detection problem∥Nielsen TZhang N．Proceedings of 7th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty．Berlin：Springer2003：419 ［9］ Abbes TBouhoula ARusinowitch M．Protocol analysis in intrusion detection using decision tree∥IEEE Proceedings of the International Conference on Information Iechnology：Coding and Computing．Las Vegas：Institute of Electrical and Electronics Engineers Computer Society2004：404 A mult-i criterion pruning method for decision trees and its application in intrusion detection LI Weidong 1）SONG Wei 2）LI Xin 2）Y A NG Bingru 2） 1） Information Technology SchoolHebei University of Economics and BusinessShijiazhuang050061China 2） Information Engineering SchoolUniversity of Science and Technology BeijingBeijing100083China ABSTRACT To improve the applicability of decision treesa mult-i criterion pruning method was proposed for the application of decision trees in intrusion detectionwhich enabled decision trees suitable for different conditions by parameter adjustment．Several parameters for describing the performance of a decision treesuch as stabilitycomplexity and classification abilitywere proposed．To meet the needs of different applicationsthe decision tree was expressed as a vector．Weights of different components of the vector could be adjusted according to the factand the required decision tree could be built gradually．Experimental results show that the proposed method can rapidly construct different decision trees according different specific environmentsthus one program can be used in different conditions．The approach changes the creator of a decision tree from a programmer to a userso the program is more suitable and the result is more reasonable． KEY WORDS intrusion detection；decision tree；pruning；stability；complexity；classification ability 第4期 李卫东等： 一种多标准决策树剪枝方法及其在入侵检测中的应用 ·431·