（应用数学专业论文）弹性函数构造与智能入侵检测方法研究.pdf

里堕型竺垫查奎堂婴塞竺堕兰垡笙苎 摘要 密码技术中弹性函数的存在性与构造问题和入侵检测技术中基于机器学习的智能化 改进是目前信息安全领域中的研究热点。本文的工作围绕弹性函数的构造和智能入侵检测 方法的研究两方面而展开。 弹性函数是密码函数中最重要的安全性指标之一。它是相关免疫函数概念的自然延 伸，但弹性函数的结构和性质却远比相关免疫函数复杂。本文研究了有限域上弹性函数的 性质与构造方法，利用有限域的基本性质和弹性函数的构造特性，构造出当 拧m ，l 研茎g 一1 ，q 3 时，只上( g ，州+ 拧，”，研) 弹性函数的一般结构；并在此基础上证明了 当狞 g 一1 时，( 吼m + 刀，一，m ) 弹性函数的存在。 智能入侵检测方法能使系统具有更强的适应性和自学习性，是目前入侵检测研究的一 个重要方向。为了使入侵检测系统对新的入侵行为有更好的识别能力和识别效率，本文在 研究了各种基于无监督学习的入侵检测特征提取方法的基础上，提出了基于增量核主成份 分析( i k p c a ) 的入侵检测特征提取方法，并对该方法进行了收敛性分析，同时结合仿真 试验对其正确性进行了验证：另外，本文通过研究独立成份分析和神经网络，提出了基于 快速独立成份分析和神经网络的入侵检测方法( f a s t i c a n ni d s ) ，并通过对k 肋c u p 9 9 的1 0 9 6 数据集的检测比较了核主成份分析( k p c a ) 、增量核主成份分析( i k p c a ) 和快速独 立成份分析( f a s t i c a ) 在入侵检测特征提取方面的优缺点。 关键词：有限域，弹性函数，入侵检测，增量核主成份分析，独立成份分析，特征提取， 核主成份分析 第1 页 望堕型兰茎查奎堂竺至尘堕堂垡笙苎 第一章绪论 1 1 密码技术与入侵检测技术的基本概念 1 1 1 密码技术的基本概念 密码技术m 是信息安全的一门学科。它包括两个分支，即密码编码学和密码分析学。 密码编码学的主要目的是寻求保证信息保密性和可认证性的方法，密码分析学是研究加密 消息的破译和消息的伪造。 采用密码技术可以隐蔽和保护需要保密的信息，使未授权者不能提供信息也不能窜改 信息。被隐藏的信息称作明文，隐蔽后的信息称作密文。将明文变换成密文的过程称作加 密，其逆过程，即由密文恢复出原明文的过程称作解密。对明文进行加密和对密文进行解 密时各自采用的一组规则分别称作加密算法和解密算法。加密和解密算法的操作通常都在 一组密钥的控制下进行的，分别称作加密密钥和解密密钥。 根据密钥的特点，密码体制可分为对称和非对称密码体制，也可称作私钥和公钥密码 体制。在私钥密码体制嘲中，加解密钥是一样的，它的安全性基础是密码函数的伪随机性， 包括三个方面：( 1 ) 静态信息泄露的缓慢性和均匀性。具体有以下的安全性度量的指标： 非线性、弹性、混淆性和扩散性。 ( 2 ) 动态信息泄露的缓慢和均匀性。具体有以下的安 全性度量指标：差分分布与高阶差分分布均匀性、自相关性和互相关性。( 3 ) 前述两个 方面各自安全性指标的稳定性。私钥密码体制又可按照加密方式分为序列密码和分组密 码：序列密码例体制的主要原理足采用移位寄存器序列及编钟序列两种方式将明文消息按 字符逐位地加密，不同的安全部门和安全对象所采用的序列密码的生成机制是不同的，而 且所采用的移位寄存器的级数也没有统一的标准：分组密码体制的主要原理是将明文消息 分组，逐组地加密。在公钥密码体制口1 中，加解密密钥不同，且难以互相推出，它的原理 是计算的单向可行性，比如离散指数和离散对数，数字背包的装载和卸载，大整数的组成 与素分解等。 密码分析过程是指通过分析从截获的密文推断出原来的明文甚至密钥的过程。根据密 码分析者破译时己具备的前提条件，通常人们将攻击类型分为下述四种： ( 1 ) 唯密文攻击：密码分析者有一个或多个密文。 ( 2 )己知明文攻击：密码分析者有一些明文以及相应的密文。 ( 3 ) 选择明文攻击：密码分析者有机会使用密码机，因此可选择一些明文，并产生 密文。 ( 4 ) 选择密文攻击：密码分析者有机会使用密码机。因此可选择一些密文，并产生 第l 页 里堕型堂垫查查兰笪茎生堕兰垡丝苎 明文。 上述每种攻击的目的是决定所使用的密钥，这四种攻击类型的强度按序递增。一种密 码攻击的复杂度可分为两部分，即数据复杂度和处理复杂度。数据复杂度是实施该攻击所 需输入的数据量；而处理复杂度是处理这些数据所需的计算量。这两部分的主要部分通常 被用来刻画该攻击的复杂度。对一个密码系统的攻击可分为主动攻击和被动攻击。主动攻 击是指非法入侵者主动向系统窜扰，采用删除、更改、增添、重放、伪造等手段向系统注 入假消息。 1 i 2 入侵检测技术的基本概念 入侵检测是指通过对计算机网络或计算机系统中的若干关键点收集信息并对其进行 分析，从中发现网络或系统中是否有违反安全策略的行为和被攻击的迹象。实施入侵检测 的系统称为入侵检测系统( i d s ) 。衡量入侵检测系统的两个最基本指标为检测率和误报率， 两者分别从正、反两方面表明检测系统的检测准确性。对于目前已有入侵检测的分类【4 1 有 多种方法，比较通用的方法有两种：从分析引擎所采用的技术上来说，可分为误用检测和 异常检测：按照数据源的不同，可分为主机型和网络型入侵检测。 ( 1 ) 误用入侵检测 误用入侵检测例是指运用已知攻击方法，根据已定义好的入侵模式，通过匹配这些入 侵模式是否出现来检测。误用入侵检测中常用的技术有基于专家系统的攻击检测技术，基 于特征检测的攻击检测技术等。 ( 2 ) 异常入侵检测 在异常入侵检测峥1 中，观察到的不是已知的入侵行为，而是所研究的通信过程中的异 常现象，它通过比较系统当前的活动与正常活动模型之间的差异来判断系统是否受到攻 击。异常检测中的主要方法有统计分析技术、神经网络方法以及数据挖掘的异常检测技术。 ( 3 ) 主机型入侵检测 主机型入侵检测“1 技术是以系统日志，应用程序日志，系统审计记录等作为数据源， 当然也可以通过其他手段( 如监督系统调用) 从所在的主机收集信息进行分析。由于主机 型入侵检测系统过分依赖系统的日志和审计记录等数据源，因此系统的可移植性不强。 ( 4 ) 网络型入侵检测 网络型入侵检测”1 通过监听所有本网段内的数据包米检测整个网段是否受到攻击，一 般网络型入侵检测系统担负着保护整个网段的任务。网络型入侵检测的优点主要是：一个 网段上只需安装一个或几个这样的系统，便可以监测整个网段的情况，同时由于采用旁路 技术，它对该网段中其它计算机的影响较低。但由于现在网络的日趋复杂和高速网络的普 及，需检测的数据量越来越多，因此对网络入侵检测的误报率和实时性提出了更高的要求， 这种结构正受到越来越大的挑战。一个典型的例子便是交换式以太网。 第2 页 国防科学技术人学研究生院学位论文 发展方向集中在如下几个方面：智能化入侵检测系统、入侵检测的标准化和与其他网络安 全技术的联动。 1 3 论文的组织和安排 本文的研究工作围绕弹性函数的构造和智能入侵检测方法的研究两方面而展开，主要 包括以下几个方面： l _ 提出了伪置换函数的概念，并结合退化弹性函数的良好性质，构造出当 一研，l 啪g l ，q 3 时，c 上( g ，州+ 刀，疗，所) 弹性函数的一般结构；另外，在此基础上， 充分利用有限域基本原理，通过构造一类特殊的伪置换函数，证明了当聍 印一1 时， ( 吼坍+ n ，月，肌) 弹性函数的存在。 2 提出了基于增量核主成份分析( i k p c a ) 的入侵检测特征提取方法，并对该方法进 行了收敛性分析，同时结合仿真试验对该方法的正确性进行了验证。 3 提出了基于快速独立成份分析和神经网络的入侵检测方法( f a s t i c a n ni d s ) ， 并通过对k d d c u p 9 9 的1 0 数据集的检测比较了核主成份分析( k p c a ) 、增量核主成份分析 ( i k p c a ) 和快速独立成份分析( f a s t i c a ) 在入侵检测特征提取方面的优缺点。 本文的安排如下： 第二章介绍了有限域的基本理论和弹性函数的基本结构。构造出了有限域上新的弹性 函数，并证明了当h g 一1 ，g 3 时，c 上( g ，册+ ”，n ，肌) 弹性函数的存在。 第三章介绍了基于无监督学习的入侵检测特征提取方法的基本原理，包括机器学习的 基本知识、主成份分析( p c a ) 算法和核主成份分析( k p c a ) 算法。提出了基于增量核 主成份分析( i k p c a ) 的入侵检测特征提取方法，并分别通过理论和试验验证了该方法的 正确性。 第四章介绍了独立成份分析和神经网络的基本理论。提出了基于快速独立成份分析和 神经网络的入侵检测方法( f a s t i c a n ni d s ) ，并通过试验比较了核主成份分析( k p c a ) 、 增量核主成份分析( i k p c a ) 和快速独立成份分析( f a s t i c a ) 在入侵检测特征提取方面的 优缺点。 第4 页 国防科学技术大学研究生院学位论文 仅当m 是某个素数的幂，即存在某个整数雕和素数p ，使得m = ，p 称为有限域的特征。 下面给出与弹性函数构造相关的有限域的一些基本性质： 定理2 1 【”1 假设，是有g 个元素的有限域，则v f ，d g = 口。 定理2 2 对每一个有限域c ，其乘法群巧是g 一1 阶的循环群。 定理2 3 n 9 1 设c 是一个有限域，c 是一个有限扩域，则c 为的一个单扩张，且任 一的本原元都是e 在上的定义元。 定理2 4 对任意的有限域和正整数一，存在n 次不可约多项式。 2 1 2 有限域上的弹性函数及其基本性质 我们首先介绍一下与有限域上弹性函数相关的基本概念： 定义2 4 【2 0 2 i l 设有( 狞，神均衡函数( 均衡函数，即当自变量的值均匀分布时，函数值 也均匀分布) f ：g f ( 2 ) 。斗g f ( 2 ) ”，其中l 埘一取定下标集u ，矗，囊 c a z ，磅称f 为 慨m ，u ，止，工) ) 弹性函数，如果对任意口= ( q ，啦，q ) e g f ( 2 ) ，任意6 g f ( 2 ) ”，则有 i x i x = q i ，x 2 ，矗) g f ( 2 ) ”，( x ，：，x ) = 口，f ( 工) = 6 ) f = 2 。 称f 为帆r ) 弹性函数，如果对任意u ，止，z ) c 1 z ，田，f 都是( h ，阳， ，：，工) ) 弹性 函数。称，的弹性阶为f ，如果f 是( 片，册，) 弹性函数，但不是( 玎，m ，f ) 弹性函数。 定义2 5 【2 1 设有两个函数f ：g e ( 2 ) ”一g f ( 2 ) ”，g ：g e ( 2 ) ”斗g f ( 2 ) ”。设自变量 x g f ( 2 ) 1 均匀分布。则称f 和g 是r 阶对偶分布的，若对任意u ，止，0 c 1 ，乙，磅，任意 d = ( q ，口2 ，口。) g f ( 2 ) ，任意6 g f ( 2 ) ”，有 p ( f ( 工) = 6 l ( h ，x ) = 盯) = 2 一尸( g ( x ) = 6 l ( x j l ，x ：，x ) = 口) 定义2 6 【2 1 设有四个函数f ：g ，( 2 ) ”1 斗g f ( 2 ) ”；- ，= 1 4 。设自变量x 凹( 2 ) ”均匀 分布。称( e ，e ，e ，) 是r 阶互补分布的，若对任意u ，止，z c 扎三，哪，任意 口= ( 口1 ，n 2 ，q ) g f ( 2 ) ，任意6 叩( 2 ) ”，有 p ( 巧= 6 | ( x j 。，x ，x ) = ) + p ( 五= 6 1 0 ，x 止，一，x ) = d ) + p ( e = 6 i ( x ，并止，一，z ) = 口) + p ( 日= 6 i ( x 工，x ) = 口) = 2 2 。 在给出了基本概念之后，我们简要介绍一下有关弹性函数的基本性质： 定理2 5 2 1 记( ”，卅) 均衡函数f ( x ) = ( e ( 功，疋( d ，( 工) ) 。则f 是f 阶弹性函数的充 要条件是对任意c = ( c 。，c ：，c 。) g f ( 2 ) ”，c o ，羔。c ，( 工) 是均衡r 阶相关免疫函数。 定理2 6 2 1 ：g f ( 2 ) ”1 斗6 f ( 2 ) “为+ 1 ，脚，“一1 ) 弹性函数的充要条件是： 第6 页 国防科学技术大学研究生院学位论文 ( 五，x 2 ，矗，毛+ 1 ) = f ( ，工2 ，) + + j ( ，o l ，x 2 ，垓) + g ( 一，叠r ，z 。) 其中，和g 都是( 即，坍，f ) 弹性函数，且f 和g 是f + 1 阶对偶分布的。 定理2 7 2 1h ：g f ( 2 ) ”2 专g f ( 2 ) 是 + 2 ，脚，f + 2 ) 弹性函数，当且仅当 日 x i ，吒，x 。“，吒+ 2 ) = ( 工i ，x 。) + x 。+ l ( e ( x l ，x 。) + ( z i ，矗) ) + 了。+ 2 ( 巧( x l ，x 。) + e ( x l ，x 。) ) + x 。+ l x 。+ 2 ( 曩 1 ，x 。) + r ( 工l ，x 。) + e ( x l ，工。) + ( 工l ，z 。) ) 其中： ( 1 ) 只，_ ，= l 4 ，都是( ”，m ，f ) 弹性函数。 ( 2 ) e 与e ，曩与e ，只与，e 与e ，都是f + 1 阶对偶分布的。 ( 3 ) ( e ，e ，e ，) 都是r + 2 阶互补分布的。 2 2 弹性函数在密码设计中的应用 布尔函数的相关免疫性阻1 和非线性度都是衡量序列密码体制安全性的重要指标。如果 选用的布尔函数不具有相关免疫性，则相应的密码体制可由相关的攻击法破译；如果选用 非线性度较低的布尔函数，则相应的密码体制也易受到最佳仿射逼近法的攻击。因为平衡 布尔函数比不平衡的布尔函数具有更好的性质，且应用上更经得起攻击，故我们希望所选 用的布尔函数是平衡的且具有较高的相关免疫性和非线性度。弹性函数的概念是由c h o re t a 1 和b e 加c t tc ta 1 第一次引入的，它是平衡的相关免疫函数，是相关免疫函数的自然延伸， 主要应用于容错分布计算，量子密钥分布和流密码的随机生成序列中。 2 3 弹性函数的存在性与构造 我们首先定义疗元甬数，为下面的映射： f ：g f ( g ) ”_ g f ( g ) 记为f ( 石) ，其中x 卯( g ) ”，f ( z ) g f ( g ) “，g 为某个素数的幂，l 用”。取任 意 ，j ，) c 1 ，2 ，h ) ，令( x ，。，x ) = ( i ，d ，) ，其中( 口l ，口，) l ? f ( g ) 。若f ( x l ，x 。) 在6 f ( g ) “中概率分布为均匀的，则称f 为( g ，疗，m ，f ) 弹性函数。若f 为( g ，n ，m ，) 弹性函数， 但不是( 吼”，研，f + 1 ) 弹性函数，则，的弹性系数为，。 在此我们给出有关弹性函数存在性与构造的一些现有结论。 1 ) c h e n 2 3 】提出一些在原有函数基础上构造出新弹性函数的方法。基本思想是， 第7 页 国防科学技术大学研究生院学位论文 ，+ g 为( 2 ，h l + 也，坍，j l + f 2 + 1 ) 弹性函数当且仅当f ，g 分别是( 2 ，强，肌，f 】) 和( 2 ，n 2 ，所，2 ) 弹 性函数。 定理2 8 设e ：g f ( 2 ) g f ( 2 ) ”是( 门，珊，f ，) 弹性函数，_ ，= 1 ，。设爿= 嘞) 。是 g f ( 2 ) 上r s 阶矩阵，r 口疵( 爿) = j 。设 胪。盛。( 善乃q ) 其中口，表示矩阵彳的第_ ，列。即p 为由7 生成的线性分组码的最小距离。则存在 “，：，丘 c ( 1 ，2 ，) ，记丁= ，。，g o 。，y ：， ) = ( e ) ，e c y ：) ，f o ，) m ；其中 乃g f ( 2 ) ”使得g 是( 珂，s m ，r + p 一1 ) 弹性函数。 j = i 2 ) s i e g e n l h a l e r 【2 4 】和x a o 2 5 】证明了( 2 ，村，l ，f ) 弹性函数具有代数次数d 当f = 一1 时，有r + d = 珂；当f 2 时，仍然存在非线性和弹性之间权衡关系。 5 ) h u 【2 9 】给出了( g ，历+ 1 ，研，1 ) 弹性函数的构造；证明了( 孽，掰+ ，m ，f ) 弹性函数的存 在，当q 卅 l ，g r 2 且g 3 。 定理2 1 0 1 2 9 1 如果 ( 1 ) f ( x ，工。) 为6 f ( g ) ”上的置换函数且尸( o ，o ，o ) = ( 毡o ，0 ) 。 ( 2 ) 蜀，9 2 ，岛为退化的( q ，2 ，l ，1 ) 弹性函数。 ( 3 ) 石， ， 为凹( 叮) 上的置换函数，且 ( 0 ) = ( o ) = = ( o ) 。 ( 4 ) 一为g f ( q ) ”中的常值。 则函数日( 一，x 。，x ) = ，( ( x l ，z ( 算) ) ，岛( ，工( x ) ) ) + 爿为( g ，n + 1 ， ，1 ) 弹性函数。 定理2 1 l 假设g 为某个素数的幂。则对任意的埘，当g 肌 1 ，g f 2 且口 3 时， ( 叮，脚+ f ，辨，f ) 弹性函数存在。 第8 页 国防科学技术大学研究生院学位论文 4 一j口一】 ( 厶，厶) = 口。，毋，屯，g ，) j = 1= l = ( ，x 。) 4 口一1卜l 8 h j e j q k i e j = 1，t l q ig l 口。，e ”d 。，e 9 j = lj = l ( 2 1 ) 显然， ，厶) 为置换函数当且仅当矩阵可逆。根据定义2 7 ， ( z ， ) 为g f ( g ) “ _ g f ( g ) 上的伪置换函数当且仅当矩阵爿可逆，其中 ， ) c l ，2 ，b ，口。g f ( g ) 。 ( 2 ) 根据定理2 1 2 ，可知函数日为( 乳，2 + 七，七，野) 弹性函数。其中，槐，魂，b ，f 均为 定理2 1 2 中的结构。 例2 1 在有限域g f ( 3 ) 中，按照定理2 1 3 构造函数 冒“，) = f ( 囊( ，霸，鼍) ) ，恕，9 2 ( 矗，鼍) ) ，魂( 墨，2 崩阮，鼍) + 2 9 2 ( ，墨) ) ) ， 其中 蜀心，) = 2 h + 墨，岛瓯，恐) = + 恐。( 9 1 ( ，鼍) ，9 2 ，屯) ，2 9 i ( h ，砖) + 2 9 2 ( h ，如) ) 在 g 目3 ) 中的真值表为： 容易看出( g 。( x 4 ， ) ，g ：( x 。，x ，) ，2 9 ，( h ，马) + 2 9 ：( - ，x ，) ) 确为g f ( 3 ) 中的伪置换函数。所以由 定理2 1 2 知，胃为( 3 ，5 ，3 ，2 ) 弹性函数。这说明当i g 时，通过定理2 1 3 构造出 ( g ，h + 女，t ，月) 弹性函数的可能性是存在的。 最后，我们构造了另一类有用的( g ，门，| 】 ，”一七) 弹性函数( g 一1 ，2 七甩) 。 定理2 1 4 令q 为某个素数的幂，且口3 ：e 为有限域g f ( q ) 上的本原根 g ，( 工l i ，。) = e 工l + + p ”x 。 g ，= l ，g 一1 ) 。对任意 ，2 七珂和任意的 i ，”， ) ， 1 矗一，则( g ，g ，。) 为( g ，玎，七，刀一t ) 弹性函数。 证明：显然，每个函数占，均为( 吼斥，1 ， 一1 ) 弹性函数任取七，2 尼孽一1 ，和七个指数 j j t j * i j i = 尼孽一1，和七个指数 ，_，。)，则有： 国防科学技术大学研究生院学位论文 ( g ，g a ) = ( 曹j | 莲j喜1。，孽i 二j ；目l： i 螽曩? i 自：萋j 一：i 未 一塑! 一i 荤 掣蠢薹。仞；“圩萎- 叁璀弱鉴般捌，氆惠攫嚣巍f 鹾j j l | 魏喜t i 蠢。霪；j 晦季；嘉甲i 董i “帆豁蕈萋i i 醇坚明争利； i 事髯盟影l = ! 辩。争m 亨造协嘤硅灌癌唰奏乒；0 受接鹭f ；i f 。 k 皆葡币；越 其中妒( f ) ，= 1 ，2 ，为女维向量( 七可 能特别大) 。不失一般性，可以假设e 妒( r ) ) = o ，4 = ( f ) 声7 ( ，) ) 为未知或无法估计的尼七协 方差矩阵。 令x 为矩阵一的特征向量，五为相应的特征值。所以，触：出。 替换4 为样本协方差矩阵，并用x m 在第f 步逼近x ，从而得到触在第f 步的估计值 v ( f ) = 五(毋( f ) ，即： 国防科学技术大学研究生院学位论文 第三章基于无监督学习的入侵检测特征提取方法 3 1 机器学习概论 机器学习( m a c l l i n el e a h l i n g ) 是研究计算机怎样模拟或实现人类的学习行为，以获 取新的知识或技能，重新组织已有的知识结构使之不断改善自身性能的一门科学。近几年 来，随着计算机网络，特别是因特网的发展，网络中的信息急剧增长，面向网络的信息服 务和数据挖掘成了当今一个热门的研究方向。而机器学习技术则可在智能的网络信息服务 和网络数据挖掘中扮演重要的角色。 人类的成长就是不断地学习、向外界吸取经验和获取知识，所以说学习是人类智能的 主要标志和获取知识的基本手段。关于学习口”的定义：如果一个计算机程序针对某类任务 r 的用p 衡量的性能根据经验e 来自我完善，那么我们称这个计算机程序在从经验e 中学 习，针对某类任务正它的性能用p 来衡量。 迪特里奇( d i e t t e r i c h ) 提出了一个简单的机器学习模型( 图3 1 ) 。在此模型【”1 中， 环境向系统的学习部件提供某些信息，学习部件利用这些信息修改知识库，以增进系统执 行部件的效能；执行部件根据知识库完成任务，同时把获得的信息反馈给学习部件。在具 体的应用中，环境、知识库和执行部件决定了具体的工作内容，学习部件所需解决的问题 完全由其余三个部分确定。 图3 1 机器学习模型 机器学习有各种方法，为了系统地了解机器学习，有必要对其进行分类。按照综合分 类方式将机器学习方法区分为以下五类： ( 1 ) 经验性归纳学习( e m p m c a l i n d u c t i v el e a n l i n g ) 。经验性归纳学习采用一些数据密集 的经验方法对例子进行归纳学习。它相当于基于学习策略分类中的归纳学习，但扣除联接 第1 3 页 国防科学技术大学研究生院学位论文 学习、遗传算法、加强学习的部分。 ( 2 ) 分析学习( a n a l ”i cl e a n l i n g ) 。分析学习方法使用先验知识和演绎推理来扩大训 练样例提供的信息。分析学习的目标是改善系统的性能，而不是新的概念描述。分析学习 包括应用解释学习、演绎学习、多级结构组块以及宏操作学习等技术。 ( 3 ) 类比学习。类眈学习把训练样例存储起来，每当学习器遇到一个新的查询实例， 它分析这个新实例与以前存储的实例的关系，并据此把一个目标函数值赋给新实例。 ( 4 ) 遗传算法( g e n e t i ca l g o m h m ) 。遗传算法是一种受生物进化启发的学习方法。它 不再是从一般到特殊或从简单到复杂她搜索假设，而是通过变异和重组当前己知的最好假 设来生成后续假设。 ( 5 ) 加强学习( i n f o r c e m e ml e a r i l i n g ) 。加强学习就是智能系统从环境到行为映射的 学习，以使奖励信号函数值最大。 3 2 入侵检测中的特征提取方法 3 2 1 主成份分析算法 主成分分析( p r i n c i p a lc 鲫p o n e n ta n a l y s i s ) 是将分散在一组变量上的信息集中 到某几个综合指标( 主成分) 上的探索性统计分析方法。具体地讲，就是设法将原来指标重 新组合成一组新的互相无关的几个综合指标来代替原来指标，同时根据实际需要从中可取 几个较少的综合指标尽可能多的反映原来的指标信息。以下是主成分分析的定义： 设置，五，x ，为某实际问题所涉及的p 个随机变量。记其协方差矩阵为： = ( o ) ，。，= e ( 工一e ( r ”+ ( v e ( 爿) ) 】 ( 3 1 ) 它是一个彪 非负定矩阵， 设，= ( ，儿，。，0 ) ( j _ 1 ，2 ，p ) 为j 口个常数向量，考虑如下线 性组合，易知有 脚( i ) = 肋( z ，2 x ) = ，f - l ，2 ，p ( 3 2 ) c b v ( e ，) = c b v ( f ，巧x ) = ，j 0 ，f = 1 ，2 ，p ( 3 3 ) 如果我们希望用i 代替原来p 个变量。x ：，x 。，就要求k 尽可能的反映原来p 变 量的信息。这里的信息用的方差来度量，即要脚( x ) = ，? 达到最大。在约束条件 f ，。= 1 之下，求 使玩，( k ) 达到最大，由此所确定的随机变量五= 一肖称为x 。，五， 的第一主成份，依次类推可求第二，第三等主成分。 主成分的总方差为： 2 。 白，( i ) = 墨。丑= f ，( p2 j d ) = 驴( 即7 ) = 驴( ) = 2 ，k 矿( x ，) ( 3 4 ) 即主成分分析是把p 个原始变量z 。，x ：，的总方差分解为p 个不相关变量k ，k ，匕 的方差值和乌p 钉( i ) ，而砌，( z ) = ，因此， 昌丑描述了第 个主成分提取的信息 第1 4 页 一一 里堕型兰垫查奎兰旦塞生堕堂垡笙苎 ( a ) 若i - 聃初始化第j 个特征向量为：v 。( 玎) = 破( ”) ( b ) 否则， 四( 耐= 圆翰必矽) 加 _c刀，=寺叶c疗一，+量竺=!雩；：铲 。，。4 ， 胛 n v 1 ”一l l ，11 、 咖州旷刃( 力揣恭揣 3 3 2 聃a 收敛性证明 本节主要证明算法3 1 的收敛性，即当，2 充分大时，有v ，( 一) 斗 ，( ”) p ，( 胛) 成立。其中 ( 田为样本协方差矩阵b ( 刀) = ：。妒( ，) 矿( _ ，) 7 行的第f 个特征值，q ( ，2 ) 为相应的特征向 量。在收敛性证明过程中，我们首先在定理3 3 中，证明第一个主特征向量的收敛性，然 后在定理3 5 中，利用类似定理3 3 的证明方法，证明前l j 个主特征向量的收敛性。证明假 设：一= 占 声( 曲7 ( 甩) ) 可逆，即其最小的特征值不为o 。本节最后，我们将在定理3 ，6 中 描述最优化特征提取的过程和依据。 引理3 1v ，( n ) 有界。 姗声7 ( i ) 证明：令b ( 疗) = 丛一，其中五( 口( 丹) ) 为b ( n ) 的最大特征值。 考虑以下两种情形： 情形1 ：若i i h ( n 一1 ) l i 小于五。( b ( 动，则v 】( 功有界。 情形2 ：若i lv ，一1 ) 忙l 。( b ( 砌( 对某些胛) ，则： 加川2 刮v l ( 川2 + ( 字) 2 ( 业篙瑞业+ v l - 1 ) “川) 刀 | | v i ，l l i l f 一 一而音而吼川“川) ) + 垫竽出篇焉p 吖旷1 ) v 舸_ 1 ) ) 绷川川2 + 导( 等篇瑞业吖”1 ) v 阳卅” ( 3 1 5 ) 胛 v 1 一l 川 因为： v j ( 聆一1 ) b ( 聆) q ( 盯一1 ) = ( e 詹v i ( 一1 ) ) 7 b f m ( e b v l ( 竹一1 ) ) ( 3 1 6 ) 其中为曰( ”) 的特征向量，、。、为对角矩阵，其对角元素为b ( ”) 的特征值。令 j ，= v ，一1 ) 肋) ，其中、跏1 为对角矩阵，其对角元素为b ( 疗) 的特征值的平方根。得 到： j jyi 五。( 曰( 片) ) j | 岛v ，( ”一1 ) | j ( 3 1 7 ) 考虑： v i ( 力一1 ) 占( 胆) v l ( 一1 ) 九。( b ( 聆) ) v j ( n 一1 ) v 1 ( 玎一1 ) v j ( 疗一1 ) b 2 ( 彬v 1 ( n 1 ) 刀。( b ( ”) ) v j ( 玎一1 ) v l ( 竹一1 ) 和 i iv 。仰一1 ) 8 k ( b ( 胛) ) ( 对某些胛) ( 3 1 8 ) 第1 7 页 国防科学技术大学研究生院学位论文 得到：业掣掣禁掌生。i ( 川川沪1 ) ( 3 1 9 ) 印一圳2 一 所以，j | v 。( 丹) 删1v 1 0 1 ) 结合情形1 ，2 ，知v 。( n ) 有界。 定理3 1 令为式( 3 2 0 ) 的局部渐近稳定解， 啪) _ r ( 尚柚v - ( j 2 0 ) 其邻域为d ( v l 。) 。若有紧集p c d ( v 。) 使得式( 3 1 4 ) 的解满足尸 v 1 ( 肝) q = 1 ，则v l ( 船) 逼近于- 证髓：示用k l i s h n e r 觚dc i a r k 【4 5 】中的定理2 3 1 进行证明。【4 5 】中的假设a 2 2 1 ， a 2 2 2 ，a 2 2 3 和a 2 2 4 显然满足。结合引理3 1 ，定理2 3 1 的所有假设均成立。所 以定理3 1 成立。 展开v ，o ) 为矩阵口( r ) 的特征向量的表示形式： h ( ，) = q ( ，) p ，( f ) 其中g ，o ) 为b ( f ) 的特征向量，且i ip ) i 亭l ；五，0 ) 为相应的特征值。令 嘲= 如( f ) ，鲰 ，e o ) = 0 ，( f ) ，o ”，得到引理3 2 ： 引理3 2 击( f ) ：r ( ；! 垒l 一) 口( f ) ( f 充分大) ；其中曰( f ) 为对角矩阵，对角元素为 、f a 细 b ( r ) 的特征值。 硼双厕引( 焉) v l ( f ) 躺恕 。r o ) p ) d ( f ) + 口) ：r ( 掣! ! 垒：一，) 。( f ) 、f 舀；o ) 雠) = 盟半掣 ( 3 _ 2 1 ) ( 3 2 2 ) 当f 充分时，b ( f ) = q ( f ) ( r ) ，其中矿( ，) 为单位矩阵且s 。( f ) 一o 。因为p ( f ) 为矩阵 b ( f ) 的特征向量，故： 8 ( ，) = 占20 ) w ( f ) 其中| i ，p ) | f = 1 且s 2 ( ，) 斗o ，所以有： p u ) = u ( 占( ， 综上所述，且当f 充分大时，忽略o ( s ( ，) ) ，得到： 日沁，( ；丝坠棚呻) 、日) ( 3 2 3 ) ( 3 2 4 ) ( 3 2 5 ) 第1 8 页 国防科学技术大学研究生院学位论文 2 # 卜黼鬻越 篓菱薹! 昭鞋篓霉t 薹墓蕾翥权鎏攀囊霪婺声： 囊纛鬻辫；墓薹；麓孺耋绷， 季s t i 席测j ；i ，i ，嘴型遘案嚣| 萋骁嚣鬻篓i 嚣囊麟震萋t ；i i 蠹；爵l 蠹錾- 羹羹鬟i 藩* ；* 黼蔫鬻囊 羹爱缫蕊薹蒸餐垂鼷骢鬻瓣海鞠憔黼 f i i ? ! ，u i 薹萋；2 嚣掣i 掣驯犁鼻： 雾l t 鬟掌：毳一m ：? 豢羹i 嚣；毒蓑i ( w l x ) ) 一e g ( w 1 x ) ) w 3 令= w + 川w + | j 4 如果不收敛，则返回到2 。 注意到，收敛即意味着新旧w 值的点积几乎为l 。 f a s t i c a 算法的推广形式如下： 首先注意到，w 7 x 的负平均信息熵的最大估计值通过最优化e g ( w 7x ) ) 得到。根据 k u l l l l t u c k e r 条件( l u c n b e r g e r ，1 9 6 9 ) ，在限制条件耳矿功2 刊w i l 2 = l 的前提下，最优化 职g ( 矿曲) 可由如下公式得到： e ( j 曙( w 7 工) 一缈= 0 ( 4 2 ) 上述公式可由牛顿方法解得。令上式左边等于f ，我们可得到j a c o b i a n 矩阵如下： j f ( w ) = e 材7g ( w 7 x ) ) 一历 ( 4 3 ) 为了简化上述矩阵的求逆，我们估计上式的第一项。因为数据呈球状分布，所以合理的估 计为：e 船7 9 + (w 7 x ) ) ze 7 e 豫+ ( w 7 工) i = e 僖1 ( w 7 x ) i 。此时，j a c o b i a n 矩阵变成了对 角化形式，能易于求逆。最终，我们得到下述估计牛顿跌代过程： w + = w 一 e 昭(w 7 x ) ) 一i 吼f ) e 9 1 ( w 7 x ) ) 一) ( 4 4 ) 实际上，f a s t l ca 的期望值通常被它们的估计值所替代。理想状况下，所有可得的数 据都应被用来估计计算，但这样会增大计算量。所以通常状况下，只选用了一部分样本数 里堕型堂垫查查堂婴窒竺堕堂垡笙茎 特真 o 1 2 3 5o 1 4 5 8o 1 0 6 】0 1 8 3 80 1 3 0 7o ，1 1 9 3n 1 6 6 20 1 3 6 9o ，1 8 4 9n 1 3 4 0 征 实 01 4 7 9o 1 8 8 0 o 1 3 9 l 0 1 4 6 801 4 0 3 o 1 6 8 5 0 1 5 1 90 1 0 4 8 o ，1 2 5 1 01 3 3 0 0 1 0 7 7o 1 6 7 8o 1 2 9 90 1 4 4 90 1 4 4 l0 1 2 7 2o 1 2 7 3o 1 3 6 401 4 8 00 1 0 8 2 向值 n 1 2 5 00 1 6 9 40 1 3 1 0o 0 9 6 60 1 6 1 90 1 1 2 00 1 6 0 80 1 5 3 90 1 1 9 80 1 9 3 2 量 0 0 9 8 l0 1 8 8 4o 1 0 5 701 3 1 201 5 1 0n 0 9 8 301 3 0 9o 1 6 1 3o 1 2 3 201 3 0 0 第误 o 0 1 4 i- 0 0 3 j 4- o 0 6 3 2o 0 0 4 4o 0 0 7 l0 o o l io o 1 0 8n 0 1 4 8n o 8一o 0 5 1 5 0 0 3 9 70 0 1 5 8o 0 4 4 6- 0 0 2 8 30 0 1 4 7- o 0 7 5 7o 0 0 2 50 0 2 4 9o0 1 8 8o o i l o o 0 3 6 7n 0 0 1 4- o0 0 1 5一o 0 4 5 5_ 0 肚1 8 90 0 5 8 4o 0 1 9 2- o0 1 9 5- o 叭3 80 0 0 9 4 个 o m l 5 - 0 0 2 7 400 0 7 0o ( ) 0 1 1o 0 5 7 80 0 1 7 1o0 0 7 5o 0 5 2 700 2 9 l0 0 0 8 7 主 差 00 2 1 9 0 0 4 1 2 o 0 0 6 8 - 00 1 3 00 0 2 6 0 o ，0 2 1 2- o 0 1 0 4 0 0 1 2 4 o 0 5 8 20 0 0 5 2 特 真 0 1 6 7 20 1 5 5 6o0 8 4 70 2 “60 1 9 2 000 3 1 1- 0 0 3j 6o 0 2 7 8- o 0 1 5 80 0 0 3 5 0 2 6 7 00 1 2 2 9- 0 1 2 3 00 2 6 7 1 0 1 1 2 401 4 3 4 - 0 2 2 9 lo 1 6 4 2 0 2 7 9 5 o 1 3 6 9 征 实 0 1 6 7 7 o 0 6 6 70 0 9 7 8 - o 1 1 4 7 0 0 2 4 80 1 0 9 8 o 2 8 8 4 0 0 3 4 5- o1 3 4 0 o 0 0 2 8 向 值 o 0 3 7 50 1 5 1 6- o 0 1 9 6- 0 0 2 5 4o 1 0 7 20 0 4 5 6一o 0 2 8 30 0 0 4 3- 0 0 4 5 6- o 0 4 l l 量 o1 9 0 2- 0 1 6 6 6o1 2 6 30 2 0 0 6 01 2 4 7 0 1 9 2 8o1 2 2 50 0 1 3 4o 2 0 9 20 0 5 2 7 第误 00 0 5 3 0 0 5 9 l o 0 1 4 9- 0 0 j 3 90 0 5 4 2o 0 0 2 50 0 1 9 2 0 0 6 0 4 o 0 0 5 6 00 3 5 l 0 ，0 9 2 70 0 6 “o 0 3 4 l0 0 7 6 9- o 0 4 l oo 0 1 6 7- 00 5 4 6- 00 6 7 7o 0 5 2 4_ 0 0 1 5 8 = - 0 0 4 3 0- o 0 0 4 60 o l l 20 们9 3n 0 0 4 2- o 0 6 4 4n 0 4 5 50 0 1 7 10 0 1 7 4- 0 0 2 9 6 个 - 0 0 1 3 00 0 4 7 70 0 2 1 0o 0 5 7 6o 0 0 9 l0 0 1 3 30 0 1 7 1o 0 1 0 90 0 3 1 6o 0 0 8 2 主 差 - 0 0 4 3 8o 0 3 0 70 0 0 8 40 0 4 9 4- o 0 0 8 2o ，0 0 9 00 0 0 9 30 0 3 1 4- o ，0 7 3 60 0 7 1 4 特 真 0 0 0 8 8n 1 8 7 3 - 0 2 9 1 20 0 2 1 3o 0 9 3 70 ，0 l o l0 2 0 7 2o 1 3 7 00 0 5 6 9_ 0 1 9 6 8 0 1 1 6 70 0 0 3 80 1 4 5 20 1 5 5 4- o 0 5 5 5- o - 3 5 3 4o o o l 20 _ 0 3 4 20 0 7 3 1_ o 0 1 5 l 征 实 一0 0 8 6 4- o0 4 4 l0 0 3 7 70 1 5 0 80 1 0 4 5一o 2 0 0 901 0 2 90 0 7 8 80 0 2 0 9o0 8 2 6 向 值 0 0 1 6 801 7 4 lo 1 9 5 90 0 7 5 2- 0 3 1 3 9，o 0 3 0 lo 0 8 1 6o2 5 1 20 2 4 1 90 5 9 量 - o 0 8 7 70 1 8 3 6o ，0 8 4 8- 0 0 8 6 0o 1 0 6 5_ o 15 7 l0 0 8 3 60 1 6 6 0一o 1 6 1 5- 0 0 9 7 5 表3 1 前三个主特征向量的真实值与估计误差 第一个主特征值第二个主特征值第三个主特征值 估计值 1 2 7 7 2 8 17 0 5 5 65 9 1 3 1 真实值 1 2 7 7 2 7 47 1 3 6 55 8 7 6 5 表3 2 前三个主特征值的估计值与真实值 试验结果表明：i k p c a 具有良好的收敛性。我们又另外选取了5 0 0 0 个样本点进行试 验，发现k p c a 在此时对核空间主成份元素的求解变得十分缓慢，而i k p c a 却能相对较 快地估计出该主成份元素，这说明k p c a 的实际应用范围仅局限于样本点数较少的情况， 而i k p c a 恰好弥补了k p c a 的这个