（应用数学专业论文）bp神经网络在入侵检测系统中的应用及优化.pdf

山东大学硕士学位论文 b p 神经网络在人侵检测系统中的应用及优化 高小伟 ( 山东大学数学与系统科学学院，济南2 5 0 1 0 0 ) 中文摘要 b p 神经网络运用于入侵检测系统有很多优点，但是也存在一些缺点，如执行速度比 较慢的问题等常用的l m b p 算法，虽然收敛速度很快，但是应用于入侵检测系统执行 速度仍然不能满足要求结合k d d 9 9 数据集，选取适当的数据，通过加入一些限制条件， 对l m b p 算法进行了优化通过实际计算，比较算法优化前后的计算结果，验证了优化算 法是有效的优化后的算法比较明显的提高了b p 神经网络应用于入侵检测系统时的执 行速度，具有一定的实用价值 本论文由彼此相关而又独立的四章所组成第一章为序言与预备知识，简要介绍了入 侵检测和本文所需的数学工具，b p 神经网络的基本概念和发展历史及现状在l ，1 节 中介绍了入侵检测的基本概念在1 2 节中介绍了基本的b p 算法1 3 节介绍了基本 的b p 算法的一些改进方法，包括动量方法，可变学习速度算法，共轭梯度法及l e v e n b e r g - m a r q u a r d t 算法其中，重点介绍了l e v e n b e r g - m a r q u a r d t 算法本章是后面各章的基础 第二章2 1 节介绍了本文使用用的k d d 9 9 数据集的基本情况由于这个数据集 包含的属性较多，因此为了倚化问题，需要对这个数据集的属性进行约倚2 2 节介绍 了对k d d 9 9 数据集进行属性约简的一种理论一粗集2 3 节使用粗集的属性约简算法 对k d d 9 9 数据集进行了约简，约简的效果较好说明使用粗糙集进行属性约简是非常有 效的 第三章3 1 节首先介绍了b p 神经网络在入侵检测系统中的应用及已经取得的一 些成果3 2 节将本文需要使用的k d d 9 9 数据集中的数据，根据上一章的结果，做了进 一步的处理，最终选定了实验数据3 3 节讨论了网络参数选择的问题，其中比较难确定 的就是隐含层的数目最后提出了网络泛化能力的问题3 。4 节根据确定的网络参数，使 用m a t l a b 神经网络工具箱中提供的函数对网络进行了训练和测试3 5 节提出了一个优 化算法，通过比较计算结果，可以看到优化后的算法是有效的 山东大学硕士学位论文 第四章对网络的泛化能力进行了讨论4 1 节中介绍了b p 网络过拟合时满足的不 确定关系式： 伽| 1 叫丽赢! 两， ( 1 ) 由此关系式得到了4 ，2 中的一些结果在4 3 - 4 4 节得到了一个计算隐节点的公式： 肌 警e 。( t + 耕 这个公式就是本文计算网络隐节点数的公式从第三章的结果可以看到，用此式确定网络 的隐节点，网络具有较好的泛化能力最后一节提出了该领域需要解决的问题及我们今后 的研究方向 关键词：入侵检测；神经网络；k d d 9 9 数据集；粗集；属性约简；算法优化；泛化能力 些至查兰堡圭兰堡圣鎏 t h ea p p l i c a t i o no fb pn e u r a ln e t w o r ki ni n t r u s i o n d e t e c t i o ns y s t e ma n di t so p t i m i z a t i o n g a ox i a o - w e i s c h o o lo fm a t h e m a t i c sa n ds y s t e ms c i e n c e s ，s h a n d o n gu n i v ，j i n a n2 5 0 1 0 0 a b s t r a c t b pn e u r a ln e t w o r kh a sm a n ym e r i t sf o ri t sa p p l i c a t i o ni ni n t r u s i o nd e t e c t i n gs y s t e m w h i l ea l s oh a v i n gs o m ed e f e c t s s u c h i t 8s l o wr u n n i n gr a t e 1 1 1 ec o m m o n l yu s e dl m b p a l g o r i t h mc a nn o tb ea p p l i e dt ot h ei n t r u s i o nd e t e c t i n gs y s t e mf o ri t sr u n n i n gs p e e d ， e m 9 i r j t ht h eq u i c kc o n s t r i n g e n c yr a t e t h el m b pa l g o r i t h mi so p t i m i z e db yu t i l 磁n g t h ek d d 0 9d a t as e t ，s e l e c t i n gt h es u i t a b l ed a t aa n da d d i n gs o m el i m i t i n gc o n d i t i o n s ， t l ”c o m p u t a t i o nr e s u l t sb e f o r ea n da f t e rt h eo p t i m i z a t i o na r ec o m p a r e d ，w h i c hc o n f i r m t h eo p t i m i z e da l g o r i t h mi se f f e c t i v e t h eo p t i m i z e da l g o r i t h ma p p a r e n t l yi n c r e a s e st h e s p e e do fb pn e u r a ln e t w o r k ，a n dh a sc e r t a i np r a c t i c a ls i g n i f i c a n c e 8 ，w h e ni t i sa p p l i e d i ni n t x t m i o nd e t e c t i r l es y s t e m t h j sp a p e ri 8c o m p o s e do ff o u rc h a p t e r s w h i c ha r ei n d e p e n d e n ta n dc o r r e l a t i v et o o n ea n o t h e r i nc h a p t e r1 ，i e p r o l o g u e ，t h ei n t r u s i o nd e t e c t i n ga n db a s i cc o n c e p to fb p n e u r a ln e t w o r ka n di t sd e v e l o p m e n th i s t o r ya n dt h er e c e n ta p p l i c a t i o n sr r ei n t r o d u c e d c o n c i s e l y i t 8t h eb a s i ct o o ln e e d e di nt h i sp a p e r i ns e c t i o n 1 1 ，t h eb a s i cc o n c e p t o fi n t r u s i o nd e t e c t i n ga r ei n t r o d u c e d i ns e c t i o n 1 2 ，t h eb a s i cb pa l g o r i t h ma r ei n - t r o d u c e d i ns e c t i o n 1 3 ，s o m ei m p r o v e m e n tm e t h o d so fb pa l g o r i t h ma r ei n t r o d u c e d ， w h i c hi n c h d em o m e n t u m ，v a r i a b l el e a r n i n gr a t e ，c o n j u g a t eg r a d i e n ta n dl e v e n c a g e - m a r q u a r d ta l g o r i t h m a m o n gt h e m ，骶i n t r o d u c e dt h el e v e n b e r g - m a r q u a r d ta l g o r i t h m 谢t he m p h a s i s ，t 陆c h a p t e ri sab a s i sf o rt h ef o n o w i n ga l lc h a r p t e r s i ns e c t i o n 2 1o fc h a p t e r2 ，t h eb a s i cs i t u a t i o no fk d d 9 9d a t as e ti si n t m d u c o d t h e r ei s m u c ha t t r i b u t ei nt h i sd a t as e t i no r d e rt os i m p l i f i c a t i o nt h eq u e s t i o n ，讯 n e e d st or e d u c et h ea t t r i b u t ei nt h ed a t as e t i ns e c t i o n 2 2 ，t h er o u g hs e tt h e o r y w h i c hr e d u c et h ea t t r i b u t ei nk d d 9 9d a t as e ti si n t r o d u c e d i ns e c t i o n 2 3 w eu s et h e a t t r i b u t er e d u c t i o na l g o r i t h mb a s e do nr o u 曲s e tt h e o r yr e d u c et h ea t t r i b u t ei nk d d 9 9 d a t as e t ，a n dg e tag o o dr e s u l t t l l i 8i n d i c a t e dt h a t 啦i n gr o u g hs e tr e d u c et h ea t t r i b u t e i se x t r e m e l ye f f e c t i v e i l l 山东大学硕士学位论文 i ns e c t i o n 3 1o fc h a p t e r3 ，8 0 m ea c h i e v e m e n t sa n da p p l i c a t i o no fb pn e u r a ln e t w o r k i ni n t r u s i o nd e t e c t i o ns y s t e ma r ei n t r o d u c e df i r s t l y i ns e c t i o n 3 2 ，a c c o r d i n gt ot h e r e s u l ti np r e v i o u sc h a p t e r w h i c ht h ed a t an e e d st ou s ei nk d d 9 9d a t as e th a sb e e nm a d e f u r t h e rp r o c e s s i n g ，a n dw ef i n a l l yd e t e r m i n e dt h ee x p e r i m e n td a t a i ns e c t i o n 3 3 ，w e d i s c u s s e dt h eq u e s t i o no fn e t w o r kp a r a m e t e rc h o i c e i ti sq u i t ed i 盛c u l tt od e t e r m i n e t h en u m b e ro fh i d d e nl a y e r f i n a l l yw ep r o p o s e dt h eg e n e r a l i z a t i o na b i l i t yq u e s t i o no f b pn e u r a ln e t w o r k i ns e c t i o n 3 4 ，w eu s i n gt h ef u n c t i o ni nm a t l a bn e u r a ln e t w o r k t o o l b o xt r a i n i n ga n dt e s t i n gt h en e t w o r k ，b yu s i n gt h ed e f i n i t en e t w o r kp a r a m e t e r i n s e c t i o n 3 5 ，w eg i v ea no p t i m i z e da l g o r i t h m t h ec o m p u t a t i o nr e s u l t sb e f o r ea n da f t e r t h eo p t i m i z a t i o na r ec o m p a r e d ，w h i c hc o n f i r mt h eo p t i m i z e da l g o r i t h mi se f f e c t i v e i nc h a p t e r4 ，w ei n t r o d u c et h eq u e s t i o no fg e n e r a l i z a t i o na b i l i t yq u e s t i o no fb pn e u r a l n e t w o r k i ns e c t i o n 4 ，1 ，w ei n t r o d u c et h eu n c e r t a i n t yr e l a t i o nw h e nb pn e u r a ln e t w o r k i so v e r f i t t i n g ： p i i 酬瓦毒罱厕 ( 3 ) b yt h ee q u a t i o n ，t h er e s u l ti ns e c t i o n 4 2i so b t a i n e d i ns e c t i o n 4 3 - 4 4 ，t h ee q u a t i o n o fc o m p u t i n gt h en u m b e ro fh i d d e nl a y e ri so b t a i n e d ： 一降 o s 。( + 耕 。， t h i si st h ee q u a t i o nt oc o m p u t et h en u m b e ro fh i d d e nl a y e ri nt h i sp a p e r f r o mt h e r e s u l ti nt h et h i r dc h a p t e r ，w ek n o w ，t h en u m b e ro fn e t w o r kh i d d e nl a y e rd e t e r m i n e db y t h ee q u a t i o nm a k et h en e t w o r kh a sw e l lg e n e r a l i z a t i o na b i l i t y f i n a l l yw ep o i n to u tt h e p r o b l e m sw h i c hw i l lb es o l v e di nt h ef i e l da n dt h ep l a nw ew i l ld oi nt h ef u t u r e k e yw o r d s ：i n t r u s i o nd e t e c t i n g ；n e u r a ln e t w o r k ；k d d 9 9d a t as e t ；a o u g hs e t ；a t t r i b u t e r e d u c t i o n ；a l g o r i t h mo p t i m i z a t i o n ；g e n e r a l i z a t i o na b i l i t y i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行 研究工作所取得的成果除文中已经注明引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写过的科研成果对本论文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明本人完全意识 到本声明的法律责任由本人承担 论文作者签名；蚤! ! ：生 日 期论文作者签名；塑! ! ：竖 日 期 z 1 分1 p 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅；本人授权山东大学可以将本学位论文全部或部分内容编入有 关数据库进行检索，可以采用影印，缩印或其他复制手段保存论文和汇 编本学位论文 ( 保密的论文在解密后应遵守此规定) 论文作者签名；高：) ：垒导师签名：越日期 2 0 口1 ，岁，p 山东大学硕士学位论文 第一章序言一预备知识 1 1 人侵检测简介 入侵检测是对企图入侵、正在入侵或者已经发生的入侵进行识别的过程它通过从计 算机阿络或计算机系统的关键点收集信息并进行分析，从中发现网络或系统中是否有违 反安全策略的行为和被攻击的迹象 目前，大部分的网络环境都采用了标准的t c p i p 协议作为通信协议，因此大部分的 入侵检测系统的数据分析重点也放在了对t c p i p 协议数据包的截获和分析工作 从数据来源看，入侵检测可分为两类：基于主机和基于网络 基于主机的入侵检测通常从主机的审计记录和日志文件中获得所需的主要数据源，早 期的入侵检测系统都是基于主机的基于网络的入侵检测通过监听网络中的数据包来获 得必要的数据来源，并通过协议分析、特征匹配、统计分析等手段发现攻击行为 从数据手段看，入侵检测可分为两类：滥用( m i s u s e ) 和异常( a n o m a l y ) 滥用入侵检测具有较高的监测率和较低的虚警率，它的主要缺点是一般只能检测到 巳知的攻击模型，模式库只有不断地更新才能监测到新的攻击方法而异常检测的优点是 可以检测到未知的入侵行为从现在的实际应用看，大多都是基于滥用的，不过随着入侵 检测技术的发展，基于异常的入侵检测技术和对应的检测模块已经应用于实际 1 2b p 神经网络介绍 误差反向传播人工神经网络模型( 简称b p 网络) 是应用得最多的人工神经网络模型 之一【1 - 4 1 b p 网络的学习过程就是个网络权系数的自适应，自调整过程通过反复训 练后，网络具有对学习样本的记忆，联想的能力常用的b p 模型是一种3 层的网络模型 它由1 个有多个节点的输入层，多个节点的隐层( 中间层) 和多个或1 个输出节点的输出 层组成，相邻各层节点之间单方向互联 1 2 1b p 算法的基本思想 算法的基本思想是：学习过程由信号的正向传播与误差的反向传播两个过程组成正 向传播时输入样本信息从输入层输入，经各隐层逐层处理后，传向输出层苦输出层的实 际输出与期望输出( 教师信号) 不符，则转入误差的反向传播阶段误差反向传播是将输出 误差以某种形式通过隐层向输入层逐层反传，并将误差分摊给各层的所有单元，从而获得 各层单元的误差信号，此误差信号即作为修正各单元权值的依据这种信号正向传播与误 差反向传播的各层权值调整过程，是周而复始地进行的权值不断调整的过程，也就是网 山东大学硕士学位论文 络的学习训练过程此过程一直进行到网络输出的误差减少到可接受的程度，或进行到预 先设定的学习次数为止 1 2 2b p 算法的学习过程 在个多层网络中某一层的输出成为下一层的输入描述此操作的等式为： a m + 1 = p 1 ( w ”“a m + 扩“) ，m = 0 ，1 ，m 一1 ，【1 1 ) 这里，肘是网络的层数第一层的神经元从外部接收输入： a o = p ， ( 1 2 ) 它是等式( 1 1 ) 的起点最后一层神经元的输出是网络的输出： a = a m ( 1 3 ) 多层网络的b p 算法使用均方误差作为性能指数算法的输入是一个网络正确行为 的样本集合： p l ，t 1 ) ， p 2 ，t 2 ， p 。，t q ， ( 1 4 ) 这里p 。是网络的输入，t 是对应的目标输出。每输入一个样本，便将网络输出与目标输 出相比较算法将调整网络参数以使均方误差最小化： f ( x ) = ee 2 = e 【( t 一口) 2 】， 这旦x 是网络权值和偏置值的向量若网络有多个输出，则上式的一般形式为： f ( x ) = e 【e r e 】= e 【( t a ) r ( t a ) 我们用k ( x ) 来近似计算均方误差： 户( x ) = ( t ( 砷一a ( 七) 产( t ( 七) 一a ( 七) ) = 7c k ) e ( k ) ， 这里，均方误差的期望值被第七次迭代时的均方误差所代替 近似均方误差的最速下降算法为： 螂+ 1 ) = 郴) n 磊， + 1 ) = 忡) - 0 器， ( 1 5 ) ( 1 6 ) ( 1 7 ) ( 1 8 ) ( 1 9 ) 山东大学硕士学位论文 对单层线性网络，偏导数可以方便地求得对多层网络，误差不是隐层中的权值的 显式函数，因此这些偏导数并不容易求得，所以下面将用微积分中的链法则来计算( 1 8 ) 和( 1 9 ) 式中的偏导数： 磊= 嚣器， 埘 _ _ _ x l l i l 螂叼一媚 ”7 器= 器筹， 硒2 硒x 两， 1 1 1 1 j 每个等式中的第二项均可容易地算出，因为m 层的网络输入是那一层中的权值和偏置值 的显式函觌 一j 叩= 伽嚣哆1 + 咿， ( 1 1 2 ) 眦 o 笺w j - ：计筹乩 “埘 若定义 够= 器， ( 1 1 4 ) ( p 对m 层的输入的第i 个元素变化的敏感性) ，则式( 1 1 0 ) 和( 1 1 1 ) 可简化为： 罴：s m 一 ( 1 1 5 ) 砥2 町吩一， 训 再a 而f ：印 ( 1 1 6 ) i i 卿。 、。7 t l ，已 + 1 ) = t 吧( 七) 一q s 哆一1 ， 6 p ( 七4 - i ) = 6 p ( 七) 一n 8 p 用矩阵形式表示，则为 矿( 七4 - 1 ) = 胪( 七) 一n s m ( a m 一1 ) t ， b m 4 - 1 ) = b ”( 七) 一。矿 ( 1 1 7 ) ( 1 1 8 ) ( 1 1 9 ) ( 1 2 0 ) 3 山东大学硕士学位论文 这里 一杀憎 ( 1 2 1 ) 现在还需要计算敏感性s ”，这要求再次使用链法则正是这个过程给出了反向传播 这个词，因为它描述了第m 层的敏感性通过第m + 1 层的敏感性来计算的递推关系 推出敏感性的递椎关系需要使用下面的雅可比矩阵： a l l m + 1 a n m 一 下面求这个矩阵的一个表达式考虑矩阵的i ，j 元素： 两o n 于+ 1 ：堡鬻型卅硒o n 3 _ 7丽f 2 两- 一2 叫硒 = 蚶1 掣= 蚶垆( 砒 这里 这里 4 因而雅可比矩阵可写成 产( 哆) = 掣 而o n m + l = 妒+ 1 扩( n m ) ， ，p ( 岬) 0 ，( n m ) ：l ?产甲) i ： f 00 ( 1 2 2 ) ( 1 2 4 ) ( 1 2 5 ) ? 0 、l n 柳 5 i ，l ( 略) 现在可以使用矩阵形式的链法则写出敏感性的递椎关系式， 、li 型善；譬型譬；簪塞；|譬 ，j，。一 山东大学硕士学位论文 s m = 杀= ( 筝) t 丽a f - 川n m ) ( ) t 羔 = 童”( n ”) ( 驴+ 1 ) t s i n + 1 ( 1 2 7 ) 现在我们可以看到反向传播算法得名的原因了敏感性从最后一层通过网络被反向 传播到第一层： s 肘_ 8 肼_ 1 _ _ s 2 _ 8 1 ( 1 2 8 ) 这里值得强调的是，b p 算法使用的是近似最速下降法惟一复杂的是，为了计算梯 度，需要首先反向传播敏感性反向传播的优点是我们可以很有效地实现链法则： 完成b p 算法前还有一点事情要做我们需要递推关系式( 1 2 8 ) 的起始点s m 这在 牡器：半：挈一”风，毒曲， 由于 可以得到 用矩阵形式表示为 器= 筹= 笃铲= 严( 虮 ( 1 3 。) s r = 一2 ( 如一瓯) ，射( n r ) 8 村= 一2 f 肘( n m ) ( t a ) 由以上的分析，总结得到b p 算法如下： 第一步是通过问络将输入向前传播： a 0 4 p ， 扩+ 1 = p 1 ( 妒+ 1 a m + 矿+ 1 ) ，m = 0 ，i ，m 一1 ， a ： ( 1 3 1 ) ( 1 3 2 ) ( 1 3 3 ) ( 1 3 4 ) ( 1 3 5 ) 5 山东大学硕士学位论文 第二步是通过f 叼络将敏感性反向传播： s f = 一2 啻 f ( n m ) ( t a ) ， s m = f m ( 矿) ( 妒+ 1 ) t s m + lm = m 一1 ，2 ，1 最后，使用近似的最速下降法更新权值和偏置值： w ” - i - 1 ) = 妒( 七) 一0 l $ ”( a m 一1 ) t ， b m ( 七+ 1 ) = b m ( k ) 一q s m 1 3b p 算法的改进 ( 1 3 6 ) ( 1 3 7 ) ( 1 3 8 ) ( 1 3 9 ) 反向传播算法是神经网络研究中的重大进展，然而，基本的反向传播算法对大多实际 应用来说都太慢了，这引起了对提高算法收敛速度研究的极大热情由此产生了很多反向 传播算法的变形，这些算法能显著提高速度并使算法实用化 快速算法的研究粗略地分成两类第一类包括那些使用启发式信息的技术，这源于对 标准反向传播算法特定性能的研究这些启发式技术包括可变的学习速度，使用动量和改 变比例变量等【5 _ 8 】 另一类研究集中在标准数值优化技术【g l l 2 】因为训练前向神经网络减小均方误差 只是个数值优化的问题，而数值优化做为一个重要的研究课题已经有三四十年了，因而 从大量已有的数值优化技术中选择快速训练算法是比较合理的下文将介绍两个成功的 应用于多层感知机训练的算法：共扼梯度算法和l e v e n b e r g - m a r q u a r d t 算法( 牛顿法的变 形) 1 3 1 算法的启发式改进 1 动量方法 这种改进是基于实际计算中的观察：如果能平滑轨迹中的振荡将能提高收敛性能这 可以用一个低通滤器来实现它滤波器有助于减少振荡的数目，同时仍然保持平均值一 个常用的一阶滤波器如下： y ( 七) = w ( k 一1 ) + ( 1 一，r ) 埘( k ) ， ( 1 4 0 ) 其中w ( k ) 是滤波器输入，v ( k ) 是滤波器输出，7 是动量系数，满足 0 1 1 ，( 1 4 1 ) 6 山东大学硬士学位论文 当动量滤波器加到式( 1 3 8 ) ，( 1 3 9 ) 后，得到了下述反向传播的动量改进公式： v p + 1 ) = 1 驴 一1 ) 一( 1 1 ) n 8 m ( a m 一1 ) r ，( 1 4 2 ) a b m ( 老- i - 1 ) = t a b * ( 七一1 ) 一( 1 7 ) a 矿 ( 1 4 3 ) 由于使用了动量项，可以在维持算法稳定前提下使用更高的学习速度动量的另一个 特征是当轨迹进入某个一致的方向后，它可以加速收敛 2 可变的学习速度 可变的学习速度反向传播算法的规则如下： 1 ) 如果均方误差( 在整个训练集上) 权值在更新后增加了，且超过了某个设置的百分 数( ( 典型值为1 至5 ) ，则权值更新被取消，学习速度被乘以一个因子p ( o 0 ，可使g 成为正定的，所以矩阵可逆 由此可导出l e v e n b e r g - m a r q u a r d t 算法： + l = 一【j r ( 辄) j ( ) + u k l 一1 j r ( 取) v ( ) ，( 1 5 7 ) 当风为0 时，上式就是牛顿法，只是使用了近似的h e s s i a n 矩阵；当m 较大，上式 就变成了具有较小步长的梯度下降法： 瓠+ l 鲁x k 一壶j t ( ) v ( 轧) 2 一去v f ( x ) ( 1 5 8 ) p kz 弘k 牛顿法能够更快更准确地逼近个最小误差，所以，应尽快地将( 1 5 7 ) 式向牛顿法转 换算法开始时胀取小值，于是在每步成功后，在下一步被除以一个因子o ( o 1 ) ， 只有当发现下一步输出变坏时则m 乘以0 按这种方法，算法的每步运行都会使评估 函数向好的方向发展这个算法提供牛顿法的速度和保证收敛的最速下降法之间的一个 折衷 现在来看如何将l e v e n b e r g - m a r q u a r d t 算法应用于多层网络训练问题多层网络训 练的性能指数是均方误差( 式( 1 6 ) ) 如果每个目标以相同的概率出现，均方误差就正 比于训练集中下述所有q 个目标的平方误差之和： f ( x ) = ( t 。一) t ( t 口一) 9 io n ( 1 5 9 ) 0o m 、。7 = e t e q = ( ) 2 = ( 钆) 2 ， 9 山东大学硕士学位论文 其中e j t 是第q 个输入目标对的误差的第项元素 l m b p 算法步骤： s t e p l 将所有输入提交网络并用式( 1 3 3 ) 和( 1 ，3 4 ) 计算相应的网络输出和误差e q = t 。一a 用式( 1 5 9 ) 计算所有输入的平方误差和f ( z ) s t e p 2 计算雅可比矩阵 s t e p 3 解式( 1 5 7 ) 求得x k s t e p 4 用+ a x k 重复计算平方误差的和如果新的和小于第1 步中计算的和，则 甩p 除以日，并设+ l = x k + a x k ，转第1 步；如果和没有减少，则用p 乘以吼转第3 步 s t e p 5 当梯度的模( ( 1 5 0 ) 式) 小于给定值，或平方误差和减小到某个目标误差时 算法被认为收敛 l m b p 算法收敛的迭代次数较前面讨论的所有算法都少，但是这个算法每次迭代时 的计算量比任何其它的算法都大( 求矩阵的逆) 但是，对于中等数量的网络参数，即使要 做大量的计算，l m b p 算法依然是最快的神经网络训练算法算法的主要缺点是计算过 程存储量大 1 0 山东大学硕士学位论文 第二章选取数据及使用粗糙集进行数据预处理 2 1 试验数据的选取 为了评估各个入侵检测系统的性能，美国麻省理工学院林肯实验室在1 9 9 8 年模拟了 一个军事环境下的局域网，获取了5 百万条用于训练的t c p 连接记录和2 百万条用于测 试的t c p 记录每个连接记录含有4 1 个特征，可分为四类：基本的t c p 特征、容量特 征，基于时间的流量特征和基于主机的流量特征训练数据带有标记( 正常或某种攻击) ， 而且共有3 8 种不同的攻击，其中训练数据中包含2 4 种攻击，测试数据中增加了1 4 种新 的攻击这些攻击可分为四类：拒绝服务攻击( d o s ) 、远程计算机的非授权访问( r 2 l ) ， 非授权访问本地根特权( u 2 r ) 、数据资源窃取( p r o b i n g ) 其中拒绝服务攻击占有较大的 比重本文选用的训练数据是1 9 9 9 d a r 2 a 入侵检测评估数据集【1 3 1 该数据集是在1 9 9 8 入侵检测评估数据集( 1 9 9 8d a r p ai n t r u s i o nd e t e c t i o ne v a l u a t i o nd a t as e t s ) 基础上发 展而成 由于本文用到的数据集是k d d 9 9 ，假如要对其处理的话，就要具备大量的领域知识 所以，本文利用a o u g hs e t 的特性，在不具备大量的领域知识的情况下，也能较好地对其 进行处理，这是一个属性约简的问题从目前来看，使用粗糙集进行属性约简是非常有效 的下文首先介绍粗集及属性约简的基本概念 2 2 粗集及属性约简的基本概念 粗集( r o u g hs e t ) 是由z p a w l a k 在上个世纪8 0 年代初针对g f r e g e 的边界线区域 思想提出来了粗集理论主要兴趣在于它恰好反映了人仃1 用粗集方法处理不分明问题的 常规性，即以不完全信息或知识去处理一些不分明现象的能力，或依据观察、度量到的某 些不精确的结果而进行分类数据的能力1 4 - 1 8 在2 0 世纪8 0 年代末期人们就意识到，信息系统中的信息量积累越来越大，以致造 成信息量爆炸的危险，尤其进入信息时代，这个问题更为突出为此解决信息系统中信息 量膨胀问题不仅是信息系统本身的研究课题，而且也是i n t e r n e t 上的重要研究方向信 息系统约简主要是使信息量减少，它将一些无关或多余的信息丢掉了，而不影响其原有功 能无疑可以设想将约简后的信息重新组合而产生新的决策规则，这类决策规则的前提信 息和结论信息可能不同于约简前的任何一条决策规则，但它们能经推理而得到相同或相 近的结果因此这样的研究成果对数据挖掘以及数据库的进一步应用将产生新的影响 1 1 山东大学硕士学位论文 2 2 1 粗集的基本概念【1 9 - 2 2 】 设x u 是u 上的等价关系，a = ( r ) 是一个近似空间，在a 上，如果x 是一 些尼基本类的并集，则称x 是尼可定义的；否则称x 是r 不可定义的球可定义集 是全集u 上那样一些子集，这些子集在个体全集( ，上是恰好可被定义，而皿不可定义集 是子集x 上不可能恰好被定义的b 可定义集被称做b 一致集或r - 恰当集，而且不 可定义集也被说成是b 不一致集或称r r o u g h 集，简称不一致集或r o u g h 集如果 存在一个等价关系r i n d ( u ) ，其中i n d ( u ) 是u 上给定的所有等价关系的交集，使 得x u 是尼一致的，则集合x 被称做u 中一致集；如果x u 对任意r6i n d ( u ) 都是r r o u g h 的，则x 被称做u 上不一致集或r o u g h 集 设r 是u 上的个等价关系，叫r 表示r 的所有等价类( 或者u 上的分类) 构成的 集合，m r 表示包含元素x u 的r 等价类个知识库就是一个关系系统k = ( 仉r ) ， 其中u 为非空有限集，称为论域，r 是u 上的一个族等价关系 当k = ( 以r ) 为一个知识库，i n d ( k ) 定义为k 中所有等价关系的族，记为 i n d c k ) = i n d ( p ) ：口尸r ) ( 2 1 ) 个决策表是一个信息表知识表达系统s = ，r = c u d 是属性集合， 子集c 和d 分别称为条件属性集和结果属性集，d o 所以对于每个子集x 和 不可区分关系b ，x 的下近似集和上近似集分别可以有b 的基本定义如下： 见( x ) = u y u r ：y x ) ，( 2 2 ) r + ( x ) = u y u a ：y n x 0 ) ( 2 3 ) 下近似和上近似也可以写成下面等价的形式： 见) = 伽u ：m 凡x ) ，( 2 4 ) r ( x ) = z6 u ：陋】 n x o ) ( 2 5 ) 上近似和下近似之间的差将被称做x 的冗- 边界线集，并被表示成 b n r ( x ) = 兄( x ) 一见( x ) ( 2 6 ) 它是那些通过等价关系r 既不能在x 上被分类，也不能在一x 上被分类的元素的集合 粗集理论中还有两个极其重要的概念，这就是约简( r e d u c t ) 和核( c o r e ) 定义1 ：设u 为一个论域，r 是一个等价关系族，r r ，如果i n d ( r ) = i n d c r 一 r ) ，则称r 在r 中是可被约去的知识；如果p = r 一 r ) 是独立的，则p 是r 中一个 约简 定义2 ：设u 为一个论域，r 是一个等价关系族，兄中所有不可约去的关系称为核， 由它构成的集合称为兄的核集，记为c o r e ( r ) 1 2 山东大学硕士学位论文 2 2 2 属性约简