《基于改进决策树算法的入侵检测方法》由会员分享，可在线阅读，更多相关《基于改进决策树算法的入侵检测方法（9页珍藏版）》请在金锄头文库上搜索。
1、基于改进决策树算法的入侵检测方法 姜潇蔚 王勇 桂林电子科技大学计算机与信息安全学院 桂林电子科技大学广西云计算与复杂系统高校重点实验室 桂林电子科技大学广西云计算与大数据协同创新中心 摘 要： 针对异常检测技术中 C4.5 算法属性选择偏向具有更多数值属性的问题, 提出基于改进决策树算法的入侵检测方法。通过添加平衡因子及融合数学极限思想, 利用属性的数量确定平衡因子, 同时利用洛必达法则对计算进行简化, 重新设计信息增益率计算方法, 优化了属性选择机制, 改善了原算法中的属性选择偏向多数值属性的现象。实验结果表明, 基于改进决策树算法对流量识别具有良好的识别效果。关键词： 入侵检测; 流量识
2、别; 决策树; 平衡因子; 作者简介：王勇 (1964-) , 男, 四川南充人, 教授, 博士, 研究方向为云计算、计算机网络技术及应用、信息安全等。E-mail:收稿日期：2017-04-15基金：国家自然科学基金 (61662018, 61661015, 61163058) An intrusion detection method based on improved decision tree algorithmJIANG Xiaowei WANG Yong School of Computer and Information Security, Guilin University o
3、f Electronic Technology; Abstract： C4.5 attribute selection has more numerical attributes in anomaly detection technology, so an intrusion detection method based on improved decision tree algorithm is proposed.By adding the balance factor and the idea of fusing the mathematical limit, the equilibriu
4、m factor is determined by the number of attributes.The calculation method is simplified by Lobida rule.The information gain rate method is used to optimize the attribute selection mechanism and improve the attribute selection bias in the original algorithm.The experimental results show that the impr
5、oved decision tree algorithm has a good recognition effect on traffic identification.Keyword： intrusion detection; traffic identification; decision tree; balance factor; Received： 2017-04-15入侵检测1是通过收集和分析网络行为、安全日志、审计数据、其他网络的信息及计算机关键节点的信息, 检查是否有违反网络安全2的行为。入侵检测主要包括基于主机的入侵检测和基于网络的入侵检测。决策树算法属于机器学习3算法的一种。
6、决策树是通过一种树形结构对数据进行分类的分类方法, 其中每个非叶子节点表示不同的属性进行的数据分割规则, 而每生长出一个树枝代表所产生的输出, 不同的叶子节点表示不同类别。近年来, 数据挖掘4技术飞速发展, 给入侵检测带来了新的启示。因此, 可利用数据挖掘中机器学习算法进行入侵检测。此方法通过决策树算法, 进行一种有监督5的入侵检测。入侵检测算法分为误用检测、异常检测和人工智能检测。Khan 等6提出基于无量纲 P2P 网络的支持向量机 (SVM) 的协作分类方法 (TRed SVM) , 以可容忍的通信增加为代价改进整体分类性能, 使其优于基准的模型传播方法。Pajouh等7提出一种基于机器
7、学习的 2 层分类模型的方法, 2 层模型由于最优的维度和特征, 从而缩短了计算时间, 且对复杂的攻击类型具有良好的检测率。Ardiansya 等8结合神经网络和决策树, 使用决策树提取规则, 提高了算法精度。Li 等9提出一种因果决策树 (CDT) , 其节点具有因果解释, 且 CDT 算法是可扩展的, 识别方法可在保持较高精度的同时显著提升其执行效率, 达到提升入侵检测性能的目的。C4.5 算法是一种改进的 ID3 算法10-11, 属于一种贪心算法12。C4.5 算法在给定的 n 个数据对象集合内, 根据信息增益率13的高低, 将信息增益率最高作为划分规则, 每次划分都遵循信息增益率规则
8、, 生成决策树。从入侵检测的角度分析, 找到一个合适的分类算法, 有助于快速且准确对数据进行划分。为此, 将平衡因子思想和数学极限思想引入 C4.5 算法, 提出基于改进决策树算法的入侵检测方法, 解决决策树算法在进行属性选择14时容易偏向多值属性的问题, 提高算法精度并生成规模较小的树。1 决策树算法1.1 决策树算法属性选择决策树利用自顶向下的方式, 在获取划分规则的条件下, 从根节点开始构造树直到生成整棵树。每次的划分旨在让数据更加有序, 每个叶子节点存放的类别表示决策的结果。常用的计算方法包括以下几种:1) 基尼不纯度。将数据集划分为若干子集后随机选取子集, 利用基尼不纯度衡量其被应用
9、于其他部分的概率。基尼不纯度越小纯度越高, 表示集合的有序程度越高, 分类效果越好。当基尼不纯度为 0 时, 表示集合的类别一致。基尼不纯度计算式为其中:m 为类标签的个数;f i为标签 i 在一个节点出现的频率。2) 信息熵。信息熵在信息论中是一种用于描述信源的不确定度, 也可用来描述某种特定信息的出现概率。信息熵计算式为其中:X 为信息源;m 为整个集合的子集个数;p i为标签 i 出现的频率。3) 方差。方差用来度量一个随机变量与均值之间的偏离程度, 方差越大, 表示数据间的差异越大, 该特征的代表性也就越强。方差计算式为其中:= Ni= 1yi;yi 为第 i 个特征的值;N 为样本的
10、数目。1.2 BL4DT 算法设计ID3 算法是基于信息增益的一种决策树算法。ID3 算法具有如下优点:1) 搜索范围可变化性, 可自行设定搜索的范围。2) 目标函数在搜索范围内一定有解。但 ID3 算法也存在一些缺点:1) 只适用于处理离散的属性, 对于连续的属性, 需先进行离散化处理才能继续下一步操作。2) 当样本数量不同时, 信息增益会偏向具有较多数值的特征, 但具有更多数值的特征未必是最优的属性。3) 易忽略属性之间的相关性。4) 信息熵的计算频繁, 且有大量对数操作。由于 ID3 最大的局限性在于建树的过程, 依据信息熵理论计算信息增益, 选取的最佳属性是一种多值属性, 却不一定是最
11、优的属性。从而使其分类结果有局部最优的缺点, 无法达到全局最优的效果。C4.5 算法是一种基于信息增益率的决策树算法, 虽然在一定程度上解决了 ID3算法的局部最优问题, 但当属性 X 有且仅有一个值时, 分裂信息 Sp趋于 0, 其倒数趋于无穷大, 导致信息增益率逼近于 0, 分类无效, 且仍存在属性选择偏向多值属性的问题。改进的 C4.5 (balanced and limited C4.5 decision tree, 简称 BL4DT) 算法引入平衡因子, 减轻了 C4.5 算法的多值偏向现象。对于分类的问题, 给定 S 作为数据集, 目标函数具有 m 个不同的特征属性, 且服从分布
12、P= (p1, p2, , pm) , 数据集 S 的熵为其中 S 的取值范围为假设 S=A1, A2, , Am为包含 m 个属性的训练样本集合, 为训练样本数, 所有的训练样本都被划分成 n 个不同的类 Ci (i=1, 2, , n) , 每类对应的样本数为|C i|, 则 S 的属性 Ai的信息增益为即其中:V (A i) 为 Ai的取值范围;S v为 Ai=v 的样本子集, S v=sS|A (s) =v。由 C4.5 算法的分裂信息得到 BL4DT 算法的信息增益率为针对 C4.5 算法的信息增益率的缺陷, 当 A 的信息增益率最高并且数值最多时, 添加平衡因子, 改善传统 C4.
13、5 算法仍存在的多值偏向造成的效果不佳问题。平衡因子:数据集 N 被分成 m 个不同的特征属性, 对于属性 A 有 n 个不同的值, 其平衡因子为其中:x ij为属性 A 在第 i 类中属于 Cj的个数;E ij为属性与类无关联时 xij的期望值。式 (9) 分母上通过加一个常数 C 使得分母不为 0, C 通常取 1。BL4DT 算法具有 m 个值的属性 A 信息增益为假设将 S 划分成 n 个部分, 如S 1, S2, , Sn, S 中属性 A 取值为 Ai时, S 中有 pi个正例与 ni个反例, S i的信息是 I (pi, ni) , 则用于计算信息增益率属性 A 的信息熵为根据极
14、限公式, 当 x0 时, ln (1+x) x, 式 (12) 可简化为同理, 则将带有最大信息增益率的属性作为判别标准, 使得叶子节点的集合纯度升高, 进而分类效果明显。决策树的建树过程如图 1、2 所示。图 1 决策树的建树过程 Fig.1 Process of creating decision tree 下载原图图 2 决策树的构建流程 Fig.2 Flow chart of creating decision tree 下载原图BL4DT 算法步骤如下:1) 输入样本集 D、属性集合 A 以及训练样本 S, 创建节点 T;2) 若训练样本 S 为空, 建树失败, 返回节点 T;3)
15、若候选属性集合 A 为空, 则返回 T 作为单节点树, 并将样本集 D 出现最多的类赋给 T;4) 若训练样本 S 在同一类, 则返回 T 作为叶子节点, 并将 D 的类赋给 T;5) 选择 A 中信息增益率最高的属性 Ai;6) 标记节点 T 为属性 Ai;7) 对于每个 Ai中的已知值 c, 从节点 T 生长出 Ai=c 的分支;8) 设 Sc为 D 中 Ai=c 的训练样本集合;9) 若 Sc为空, 则生成叶子节点, 用训练样本中出现最多的类赋值给它, 否则, 加上一个返回的节点。2 实验过程2.1 现有研究条件和基础实验使用 KDD CUP99 10%数据集, 数据分布如表 1 所示。
16、KDD CUP99 数据集对于提供的每个 TCP/IP 连接, 除了一系列基本属性外, 还利用领域知识对属性进行了一些扩展。每个攻击记录都有 42 个特征组成, 8 个为离散型的变量, 其余为数字变量。KDD CUP99 提供的 10%数据集包括 DOS、PROBE、U2R、R2L 四大攻击类型, 共分为 24 小类。四大攻击类型分布差别很大, 其中 DOS 攻击所占比例最大, 另外 3 种入侵记录仅占样本总数的 1%左右, U2R 和 R2L 攻击所占比例非常小。表 1 数据分布 Tab.1 Data distribution 下载原表 2.2 实验结果本实验主要验证 BL4DT 算法分类准确率和树的总节点数, 采用相同数据集进行测试, 与 C4.5 方法对比。检测结果如表 2 所示。R2L 和 U2R 由于数据规模相对较小, 不对攻击类型进行细分, 只分为 Normal 和非 Normal
