改进贝叶斯分类算法在入侵检测中的研究_图文

1、收稿日期:2006-04-14基金项目:国防科工委国防基础科研项目(S0500B003作者简介:张 铮(1982-,男,江苏人,硕士研究生,主要研究方向为计算机网络、网络安全;李 俊,教授,硕士生导师,主要研究方向为计算机网络、网络安全、数据库。改进贝叶斯分类算法在入侵检测中的研究张 铮,高志森,李 俊(南京航空航天大学信息科学与技术学院,江苏南京210016摘 要:把朴素贝叶斯分类算法引入到入侵检测中,可以简单方便地区别出入侵事件。但是由于该算法在学习中存在一定的不足和缺陷,主要是属性值之间要求相互条件独立和训练集数据不完备这两个缺陷,导致了它的检测效果并不是很理想。文中针对该算法这两个最主

2、要的缺陷,提出增量学习概念,引入损失幅度参数,改进和完善朴素贝叶斯分类算法。并对改进后的新学习策略进行了分析和研究,给出了其基本实现思想和算法描述,并指出它实现的可能性。关键词:贝叶斯分类;增量学习;损失幅度参数;类别标签中图分类号:T P393 08 文献标识码:A 文章编号:1673-629X(200701-0174-03Research of Improved Bayesian Classification Arithmeticin Intrusion DetectionZHANG Zheng,GAO Zhi sen,LI Jun(Co llege of Info.Sci.&T

3、ech.,N anjing U niversit y of A ero nautics and Astronautics,Nanjing 210016,ChinaAbstract:Native Bayesian Classificati on Arithmeti c distinguishes intrusion inci dents from all incidents con ven i ently in i ntrusion detection.But this arithm eti c has some lack and limitation,two important factors

4、 of which are conditi on indepen dency among property val ues and non -maturity training-data collection,s o its intrusion effect is not good.T hen in all usion to these two important factors,a concept of incre mental learning and a loss extent parameter are put forward in this paper,and Native Baye

5、sian Classification Arithmetic is also perfected.Furthermore,the paper analyses the new learning strategy,and introduces th e basic realizing thought about new arithmetic and a descrip tion about it,and points out its reali z i ng possibility.Key words:Bayesian classi fication;i ncremental learning;

6、loss extent param eter;classification l abel0 引 言在入侵检测系统中,为了提高系统的性能,包括降低误报率和漏报率,缩短反应时间等,学者们引入了许多方法,如专家系统、神经网络、遗传算法和数据挖掘中的聚类、分类等各种算法1。其中,朴素贝叶斯分类算法由于简单实用、计算高效,在入侵检测中可以建立良好的用户模型,并具有坚实的数学理论基础和丰富的概率表达能力2,所以被广泛地应用到入侵检测系统中3。但是由于该算法比较简单,所以它不可避免地有一些限制和不足。文中首先介绍朴素贝叶斯分类算法,分析了它存在的主要限制和不足,提出增量学习策略来弥补它的不足之处。对算法实现

7、过程进行了细致描述。并通过算法分析来说明该策略的可行性。另外它也起到了弱化限制条件的作用。该策略全面提高了朴素贝叶斯分类算法性能。1 朴素贝叶斯分类算法每个数据样本用n 维向量X =X 1,X 2, ,X n 表示,X 1,X 2, ,X n 是n 个属性A 1,A 2, ,A n 的具体取值4。在入侵检测系统中,是从审计记录或网络数据流中提取的参数,包括登录频度、会话时间、CPU 和I/O 的利用量等等5。先假定有m 个类别C =C 1,C 2, ,C m ,在入侵检测系统中一般令m =2,即C 1=异常,C 2=正常。现给定一个未知的数据样本x (即没有类别标签,通过当前已有类别标签的样本

8、集,预测出x 属于具有最高后验概率(条件x 下的类4,6,7。即, x =x 1,x 2, ,x n ,c i !(1im ,当且仅当类型支持概率6:P (c i |x>P (c j |x ,1j m ,j #i其中,P (c i |x =P (c i P (x |c i P (x =P (c i nj =1P (x j |c i P (x 。2 增量学习策略2.1 朴素贝叶斯分类算法的缺陷朴素贝叶斯分类算法有一个基本限制:在给定特征条第17卷 第1期2007年1月计算机技术与发展COM PUT ER TECHNOLOGY AND DEVELOPM ENTVo l.17 N o.1Jan

9、. 2007件下的属性值之间必须相互条件独立2,3。在不考虑这个基本限制的条件下,朴素贝叶斯分类算法还是存在一个比较明显的缺陷。样本集S 分为已有类别标签的训练集D 和没有类别标签的测试集T 。朴素贝叶斯分类算法就是根据先验概率(从训练集D 中得到来预测后验概率,得出测试集T 中的实例类别标签7。如果训练集D 没有良好的数据完备性,那么预测的测试集T 中实例类别标签就可能不准确。在正常情况下,有限大小的训练集D 不可能具有完备的数据,所以需要不断地更新训练集D,使其趋于完备。2.2 增量学习概念在原始条件下,训练集D 保持不变。增量学习就是预测测试集T 中没有类别标签的实例并更新训练集D 。把

10、刚得知类别标签的实例加入到训练集D 中,再用新的训练集D 来预测未知实例。这一过程往复下去,直到测试集T 为空。令未知类别标签的实例x t=x t 1,x t 2,x t n %T ,通过预测学习得到它的类别标签c t ,即 x t =x t 1,x t 2, ,x t n ,c t !,并且有 t=max P (!c |x t =P(c t |x t (!c%C ,设 为类型支持概率。增量学习是要把x t 加入到训练集D 中,D &=D + x t ,c t !。由于x t 的类别标签是由原训练集D 学习预测得来,有一定的不确定性,所以在D &中,新元素x t 会影响原D 中

11、元素的类型支持概率 值。这种影响可以概括为三类:假设原D 中一个元素为 x d =x d 1,x d2, ,x d n ,c d !, d =P (c d |x d ,当x t加入后,在D &中,元素保持不变,为x d ,c d !,类型支持概率变为 d , d = d - d。(1 d>0,说明新加入的x t 强化了原实例x d 的类别,x d的敏感度变小;(2 d=0,说明新加入的x t 对原实例x d 没有影响,x d 的敏感度不变;(3 d <0,说明新加入的x t 弱化了原实例x d 的类别,x d的敏感度变大。新元素x t 与原D 中的元素吻合性好,即x t 比

12、较完备,那么应该 d =0或者 d没有较大变化;相应地,x t 与原D 中的元素如果吻合性不好,那么 d 就会相当大。这就要求有选择地更新训练集D,只能把 d没有较大变化的新实例加入到训练集D 中。所以需要好的学习策略。2.3 增量学习策略对于原训练集D 中的每一个元素,它们的类型支持概率 值在新元素加入到D 中后的变化值有大有小。笔者就把这些变化值相对化,引入分类损失系数 ,来统计它们的相对变化幅度。对于上文原D 中的元素 x d ,c d !, d =2| d|/ d2| d|/ d,这里,当 d =0时, d =1,即表示没有变化;当 d =( d 时, d =2,表示变化了1倍;等等。

13、符合变化幅度表示。 对原训练集D 中所有的元素来说,损失估计值SUM loss =,学习策略就是要在测试集T 找到使得原训练集D 中所有实例的损失估计值SUM lo ss = 为最小时的新实例,即使类型支持概率 值变化幅度最小的新实例,把它加入到D 中,逐步减少测试集T 的实例数目,直到T = 为止。3 算法描述在入侵检测系统中,训练集D 来源于国外知名大学实验室的正规训练数据,测试集T 来源于网络数据流和事后审计数据。在程序执行过程中,训练集D 是不断扩大的;测试集T 被学习完并为空后可以不断更新,也可以结束执行程序。在图1中,flag1、flag2作为全局静态变量,保存在数据库中初始值都为

14、1;类型支持概率值 也保存在数据库中。另外,不等式A 为:min(SUM lo ss >SUM loss ;损失估计值B:SU M loss =;赋值语句C:min (SU M lo ss =SUM loss 。图1 算法流程图4 算法实现分析在文中所述的增量学习算法中,需要为训练集D 中每一个实例保存它的类型支持概率 值,用来与后来的 值结合起来计算损失估计值,这就比原来的朴素贝叶斯分类算法额外开销S (n 级的空间。每次向训练集D 中加入175第1期 张 铮等:改进贝叶斯分类算法在入侵检测中的研究新实例时,需要重新计算原训练集D 中每个元素的新类型支持概率 值,有了额外的时间开销,时

15、间开销为N (mi =1(n +i(m -i 级。在空间和时间的额外开销方面,都在可接受范围,所以该算法是可行的。在增量学习算法中,反复用训练数据检验,这使得样本实例属性值之间的条件相关性不断弱化,减小其负面影响。因而,在朴素贝叶斯分类算法的基本限制和明显缺陷方面,增量学习算法都对其有不错的完善。5 结束语如何改善朴素贝叶斯分类算法,提高其在入侵检测系统中的性能,仍然是目前一个比较重要的课题。除了文中所述的方法外,还有很多诸如贝叶斯分类算法与决策树结合3、贝叶斯分类算法与信念网络结合1等等的方法。但各种方法不是降低实例属性值之间的条件依赖程度,就是提高用先验知识来预测后验数据的准确率。增量学习

16、策略是一种相对简便实用的弥补方法,而怎样选择新实例加入到训练集D 中,更好地完备训练集D 来改善文中算法,仍然值得做深入的研究工作。参考文献:1 Lee Wenke,Stolfo S J,Mok K W.A Data M ining Frameworkfor Building Intrusion Detection Model s C/Proceedings of the 1999IEEE Symposium on Security and Privacy.Los Alamos,C A:IEEE Computer Society Press,1999:120-132.2 Firedman N,

17、Geiger D.Bayesian network classifier J.M achine Learning,1997,29:103-130.3 张王番.多种策略改进朴素贝叶斯分类器J.微机发展,2005,15(4:35-374 Han Jiaw ei,Kamber M.数据挖掘概念与技术M .范 明,孟小峰,等译.北京:机械工业出版社,2005.5 张 琨,徐永红,王 珩,等.用于入侵检测的贝叶斯网络J.小型微型计算机系统,2003,24(5:913-915.6 Yager R R.An extension of the naive Bayesian classifierJ.Inform

18、ation Sciences,2006,176:577-588.7 宫秀军,刘少辉,史忠植.一种增量贝叶斯分类模型J.计算机学报,2002,25(6:645-650.(上接第171页该系统针对不同的领域配以不同的应用软件,可应用于远程网络数据库的访问权限及身份的确认、银行储蓄防冒领及通存通兑的加密方法、保险行业中投保人的身份确认、期货证券提款人的身份确认、医疗卫生系统中医疗保险人的身份确认等领域。可以说,指纹识别技术实现了身份鉴定领域的世纪革命,解决了困扰身份识别多年的问题。4 结束语随着硬件技术的提高和互联网的广泛应用,指纹身份认证系统的开发和应用将得到进一步的拓宽,指纹身份认证的普及应用指日可待。参考文献:1 戴平阳.指纹识别技术研究进展J.厦门大学学报:自然科学版,2002,41(6:750-755.2 卢朝阳,张岗山,刘 琳.指纹识别系统性能评价方法J.西安电子科技大学学报:自然科学版,2002,29(6:804-808.3 于秀霞.指纹识别技术及其应用J.长春大学学报,2005,15(2:30-32.4 李海雄,刘国清.活体指纹识别系统及其应用J.计算技术与自动化,2003,22(4:68-70.5 刘 旭,田 捷.自动指纹识别算法在嵌入式系统上的实现J.计算机工程与应用,2002(21: