（计算机应用技术专业论文）基于改进支持向量机的入侵检测算法研究.pdf

中山大学硕士论文基于改进支持向量机的入侵俭测算法研究 基于改进支持向量机的入侵检测算法研究 计算机应用技术 林佳 衣杨副教授 摘要 随着i n t 锄e t 的深入应用，企业及政府中的重要应用系统被入侵的危险越来 越大，信息安全成为日益关注的重要问题。基于静态系统观点的传统安全策略( 例 如防火墙，访问控制，加密等) 无法满足系统安全的需求。入侵检测是一种动态 的监控、预防、抵制系统入侵行为的安全策略。入侵检测通过监视和分析计算机 主机或网络中发生的事件，寻找违反安全机制的入侵行为。 入侵检测通常采用机器学习等“主动 学习策略，通过建立检测模型，检测 主机或网络中可能的攻击行为。支持向量机( s v m ) 基于统计学习的v c 维理论 和结构风险最小化的原理，专门针对有限样本的分类问题，具有分类效果好、全 局最优、算法复杂度与样本维数无关等优点。本文在分析已有的s v m 算法和入 侵检测算法的基础上，完成了基于s v m 的系统调用序列入侵检测算法的研究。 其内容包括： 首先，对机器学习原理和s v m 算法进行研究，分析了c s v m ，o n e c 1 a s s s 和s v d d s v m 算法的原理和特点； 其次，总结了现有的入侵检测模型，定义入侵检测算法的性能评价标准，详 细分析了现有的入侵检测算法的原理和特点； 其三，针对监测特权进程的入侵检测系统，设计了基于系统调用短序列距离 的核函数( s s d 核) ，证明了s s d 核的合法性。在c s v m 和o n e c l a s ss v m 算 法的基础上，设计了基于s s d 核非平衡c s v m 的系统调用序列异常检测算法和 基于s s d 核o n e c l a s ss v m 的系统调用序列异常检测算法。 其四，通过实验验证两种异常检测算法的有效性，并对实验结果进行了分析。 最后，本文展望了基于s v m 的入侵检测的前景和进一步的研究方向。 关键词：入侵检测；异常检测；支持向量机；序列核函数 中山人学硕：卜论文基于改进支持向量机的入侵检测算法研究 r e s e a r c ho ni n t m s i o nd e t e c t i o nb a s e do nh n p r o v e ds u p p o r tv e c t o rm a 出n e c o m p u t e ra p p l i c a t i o nt e c l l i l o l o g y l i nj i a y iy a n ga s s o c i a t ep f o f e s s 0 r a b s t r a c t a 1 0 n gw i t ht h ei n d e p t ha p p l i c a t i o no fi n t e m e t ，i m p o r t a l l ta p p l i c a t i o n s0 n b u s i n e s sa 1 1 dg o v e m m e n ta r ef a c i n gm o r ea n dm o r ei n t r u s i o n s t r a d i t i o n a ls e c u r i t y s t r a t e 百e s ，s u c ha sf i r e w a l l s ， a c c e s sc o n t r o l ，a 1 1 de n c r y p t i o nt e c h i q u e s ，w h i c ha r e b a s e do nt h ev i e wo fs t a t i cs y s t e m s ，a r en o ta b l et om e e tc u r r e n ts e c u n t yn e e d s i n t m s i o nd e t e c t i o n ( i d ) u s e s “a c t i v e ”l e 锄i n gs 仃a t e 百e st oe s t a 【b l i s hd e t e c t i o n m o d e l s ，t h r o u 曲w h j c hp o s s i b l ea t t a c k si nt h eh o s to rn e m o r kc a i lb ed e t e c t e d s u p p o r tv e c t o rm a c h i n e ( s v m ) ，、h i c hi sb a s e do nv cd i m e i l s i o na i l ds 缸1 j c t u m lr i s k m i n i m i z a t i o n ，h a ss u p e r i o rp e r f o 订n a n c e0 ns m a l ls 锄p l ec l a s s i 蜘n g 1 1 1t h i st h e s i s ，w e c o m p l e t et h er e s e a r c ho ni n t m s i o nd e t e c t i o nb a s e do ns y s t 锄c a l ls e q u e n c e s t h e c o n t e n t so ft h i st 1 1 e s i si n c l u d e ： f i r s u y ，w ea n a l y z et 1 1 e 1 e o 叫a n dc h a r a c t 甜s t i c so fd i 脑e n ts s ，i n c l u d i n g c s v m o n e c l a s ss v ma i l ds v d d - s v m s e c o n d l y w es u m m a r i z et 1 1 e e x i s t i n g i dm o d e l s ，d e f i n et l l e p e r f o 衄a n c e e v a l u a t i o nc r i t 甜af o r i da l g o 删m s ，a n ds 1 h n m 撕z er e l a t e da l g o 删瑚si ni d t h i r d l y ，w ed e s i 弘an e wk e m e lb a s e do ns y s t e m - c a l ls h o r ts e q u e n c ed i s t a l l c e s ( s s dk e n l e l ) t om e e tm er e q u e s to fi ds y s t e m sm o n i t o r i n gp r i 讥1 e g e dp r o c e s s w e a l s op r o v et h a tt h ek 锄e li sv a l i d o nt h eb a s i so fc s v ma n do n e - c l a s ss v m ，w e d e s i 口撕oa l g o 订t h m sb a s e do ns s dk e n l e l ：u n b a l a n c e dc - s v mf o rs y s t e r i lc a l l s e q u e n c ea j l o m a l yd e t e c t i o na n do n e c l a s ss f o rs y s t 锄c a l ls e q u e i l c ea n o m a l y d e t e c t i o n f o m h l y ，w ev a l i d a t eo u ra l g o r i t h m so nt 1 1 eb e l l c h n l a r kd a t a s e tu n ms e n d m a i l w ea l s oa i l a l y z em ee x p 甜m e n t a lr e s u l t s a t1 a s t ，w eo u t l o o kt h ep r o s p e c t sf o ri n t m s i o nd e t e c t i o nb a s e do ns v m k e yw o r d s ：i n t m s i o nd e t e c t i o n ；a n o m a l yd e t e c t i o n ；s v m ；s e q u e n c ek e m e l i i 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体己经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：才术f f 圭 r 期：矽。s 戽硐g 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名： 日期： 翻啦 夕9 0 辨明g 日 导师签名： 日期： 一、 、门 飞文移 中山人学颐一l 论文基于改进支持向量机的入侵检测算法研究 1 1 研究背景 第1 章引言 今天，入侵检测技术对于保障网络安全起着越来越重要的作用。1 1 1 t e m e t 包 含广泛的技术体系，包括分布式数据存储系统，加密和认证技术，i p 语音和视 频，远程无线访问和网络服务等，i i l t 锄e t 广泛应用于商业交易、政府政务、个 人消费等社会经济生活的各个方面。1 1 】t e m e t 的复杂性、可访问性和开放性导致 系统安全管理复杂，越来越多的系统遭受入侵的威胁。入侵检测技术作为一种新 的安全防护手段，日益受到人们的关注。 入侵检测( i n t m s i o nd e t e c t i o n ) 是一种动态的监控、预防、抵制系统入侵行 为的安全策略，能够满足动态系统安全的需求。计算机安全通常指保护各种计算 机资源及存放在计算机系统中的重要信息，计算机安全必须保证系统的保密性、 真实性、完整性、可用性、不可否认性、可靠性、正确性等特性 1 ，2 】。传统的安 全观点认为计算机安全可以通过改善安全策略和软件工程方法实现，事实上，传 统的计算机安全策略基于以下假设：安全策略能够被明确和正确地定义，程序能 被正确地实现，系统能被正确地配置。然而，实际生活中的计算机系统不是静态 的系统，计算机系统频繁地被厂商、系统管理员或用户所改变，因此传统安全策 略难以满足动态系统安全的需求。入侵检测基于以下假设：系统是不安全的；通 过监控和分析系统行为，违反安全策略的行为可以被检测到。入侵检测通过建立 检测模型，检测主机或网络中可能的攻击行为，能够适应系统的动态安全需求。 1 2 研究意义 ( 1 ) 目前互联网安全实际状况不容乐观。 目前篡改网站网页，分布式拒绝服务攻击，传播恶意代码等网络攻击活动猖 獗。据国家计算机网络技术应急技术处理协调中心( c n c e i 刑c c ) 的统计 3 】， 2 0 0 7 年上半年的网络仿冒事件和网页恶意代码事件比2 0 0 6 年全年总数增加 中山人学硕： ：论文 基于改进支持向量机的入侵检测算法研究 1 4 6 和1 2 5 ，我国大陆地区被植入木马的主机p 比2 0 0 6 年全年增幅2 l 倍， 被篡改网站的数量比2 0 0 6 年全年增加了1 6 9 。政府类相关网站、以网络服务 为核心的企业、个人用户都是网络入侵者攻击的目标，互联网安全面临着越来越 严重的威胁。 ( 2 ) 传统的安全策略难以满足网络安全的需求。 传统的安全策略具有局限性。传统的安全策略包括防火墙，访问控制和加密 技术等。在网络中，一般采用防火墙作为第一道安全防线。防火墙的主要功能是 访问设备控制，即允许指定的协议、指定的目标或指定的源口地址通过防火墙。 防火墙一般通过分析数据包头来决定如何引导和转发，一般不完全检测数据包的 内容，不能检测或发现嵌入在普通流量中的恶意攻击代码，例如针对w 曲服务 的注入攻击等。此外，传统安全策略无法发现内部网络中的攻击行为。随着攻击 者知识的日益丰富，攻击工具和攻击方式的日趋复杂多样，传统的安全策略已经 无法满足信息安全的需要。网络的防卫必须采用更加纵深的、主动的手段。 ( 3 ) 入侵检测系统是对传统安全策略的补充。 入侵检测系统是防火墙之后的“第二道安全闸门”，它能在不影响网络性能 的情况下对网络或主机进行监听，从而提供对内部攻击、外部攻击和误操作的实 时保护。作为对传统安全策略的有益补充，入侵检测系统能够帮助系统管理员快 速发现攻击行为的发生，扩展了系统管理员的安全管理能力( 包括安全审计、监 控、进攻识别和响应等) ，提高了信息安全基础结构的完整性。 ( 4 )入侵检测系统能够发现新的攻击行为。 入侵检测系统通过建立正常活动的模型，能够检测出任何违反正常模型的行 为，从而能够发现新的攻击行为。传统安全策略事先需要知道攻击的模式，而入 侵检测系统采用自动学习的方法建立检测模型，由于通常情况下入侵者无法获知 合法用户的正常行为模式，入侵者的攻击行为偏离正常模型的可能性很大，因此 能够被入侵检测系统检测到。 ( 5 )入侵检测系统能够发现内部攻击行为。 入侵检测系统能够检测出授权用户的异常活动。传统安全策略通常采用身份 验证的方式保护系统安全，一旦攻击者获得授权用户的帐号密码或者内部员工 进行内部攻击，传统安全策略将失效。入侵检测系统通过正常模型的方式判断入 中山人学硕士论文基于改进支持向量机的入侵检测算法研究 侵是否发生，因此能够检测出授权用户的异常行为。 1 3 入侵检测相关理论及概念 入侵检测系统( i n 仃u s i o nd e t e c t i o ns y s t e m ，i d s ) 是运用入侵检测技术的系 统，能够检测各种恶意的网络交通和计算机活动，入侵检测系统从包括计算机主 机和网络在内的各个区域搜集和分析信息，确认可能的安全破坏。入侵检测系统 由两个基本因素组成，一个是可观察的对象或事件的数据模型，另一个是建立和 分析模型的相应技术。 入侵检测的数据模型主要有网络数据包和主机审计数据。根据数据模型的不 同，入侵检测可分为基于网络的入侵检测和基于主机的入侵检测。 定义1 1 ( 基于网络的入侵检测) 基于网络的入侵检测定义为，通过监视网段中 各种数据包，并对每个数据包或可疑的数据包进行特征分析，判断是否有入侵发 生。 定义1 2 ( 基于主机的入侵检测) 基于主机的入侵检测定义为，通过监视主机的 网络实时连接以及系统审计日志，并对日志信息进行智能分析，判断是否有入侵 发生。 本文主要研究监控特权进程的系统调用序列的入侵检测，基于系统调用序列 的入侵检测属于基于主机的入侵检测。下面给出特权进程和系统调用的定义。 定义1 3 ( 特权进程，p r i v i l e g e dp r o c e s s ) 特权进程是u n i x 主机中的一类特殊进 程，主要运行主机的各种服务。 定义1 4 ( 系统调用，s y s t e l l lc a l l ) 系统调用是u 1 1 i x 类操作系统提供的一系列 良好定义的数量有限的直接访问内核的入口 4 】。 根据建立和分析模型技术的不同，入侵检测可以分为误用检测，异常检测和 混合检测。 定义1 5 ( 误用检测，m i s u s ed e t e c t i o n ) 误用检测定义为，为每个攻击行为建立 攻击标识模型，如果一个的活动符合某种攻击标识则被视为入侵。 定义1 6 ( 异常检测，a b n o m a l yd e t e c t i o n ) 异常检测定义为，通过“学习 建 立系统正常活动的模式，如果一个活动偏离正常模式则被视为入侵。 定义1 7 ( 混合检测，h v b r i dd e t e c t i o n ) 混合检测是误用检测和异常检测的有机 中山人学硕十论文基于改进支持向量机的入侵检测算法研究 结合。 入侵检测系统应该具有无监督的特性。在通常情况下，入侵检测系统的审计 日志数据量大，且没有标记攻击行为是否发生，因此，入侵检测系统要求入侵检 测算法能够进行无监督学习。 定义1 8 ( 无监督学习，u n s u p e r v i s e dl e a n l i n g ) 无监督学习定义为，如果训练 数据没有被标识属于哪一类，学习的任务是理解训练数据产生的过程，并对输入 的测试数据输出估计，则称该学习是无监督的。 1 4 本文的主要工作 本论文研究的主要内容是： ( 1 ) 对机器学习原理和s v m 算法进行研究，分析了c s v m ，o n e c l a s s s v m 和s v d d s v m 算法的原理和特点； ( 2 ) 总结了现有的入侵检测模型，定义入侵检测算法的性能评价标准， 详细分析了现有的入侵检测算法的原理和特点； ( 3 ) 针对监测特权进程的入侵检测系统，设计了基于系统调用短序列距 离的核函数( s h o r ts e q u e n c ed i s t a j l c ek e n l e l ，简称s s d 核) ，证明 了s s d 核的合法性。在c s v m 和o n e c l a s ss v m 算法的基础上， 设计了基于s s d 核非平衡c s v m 的系统调用序列异常检测算法和 基于s s d 核o n e c l a s ss v m 的系统调用序列异常检测算法； ( 4 ) 通过与其他算法的比较，验证两种系统调用序列异常检测算法的有 效性。 设计一个好的异常检测算法，需要考虑以下几个问题： ( 1 ) 算法能够准确地检测到入侵，即对各种入侵行为都有较高的入侵检 测率和较低的误检率。 ( 2 ) 算法能够检测到已知入侵行为的变种或未知的入侵行为。 ( 3 ) 异常检测算法应该是无监督的。 ( 4 ) 异常检测算法应该具有一定的实时性，能够即时发现异常行为。 本文采用u n m 的s e n d m a i l 数据集 5 验证算法的性能。s e n d m a i l 是u n i x “n u x 服务器的邮件收发程序，与l p r ，、r p d 等服务进程相比，s e n d m a i l 的行为模式 4 中山大学硕j ：论文 幕于改进支持向量机的入侵榆测算法研究 更加复杂，更容易被入侵者攻击。 1 s 论文的技术路线 本文主要分成六章，其结构和相关章节的主题如下。 第l 章介绍入侵检测研究的意义、相关理论及概念，阐述本文的研究范围和 组织。 第2 章介绍了机器学习原理和支持向量机相关理论，着重分析了c s v m ， o n e c 1 a s ss v m 和s v d ds v m 算法的原理和特点。 第3 章综述入侵检测的相关理论，分析了现有的入侵检测模型，定义入侵检 测算法的性能评价标准，分析现有的入侵检测算法。 第4 章定义了基于系统调用序列的异常检测问题，在核函数理论的基础上提 出了基于系统调用短序列距离的核函数( s s d 核) ，并给出合法性证明；设计基 于s s d 核非平衡c s 订异常检测算法和基于s s d 核o n e c l a s ss v m 的异常检 测算法。 第5 章对第4 章提出的算法进行实验验证，并对实验结果进行分析。 第6 章总结全文并讨论进一步的研究方向。 5 中山大学硕上论文基于改进支持向量机的入侵检测算法研究 第2 章支持向量机相关理论及算法 入侵检测可以归结为二值分类问题，即区分正常与异常。入侵检测分类可以 使用机器学习的方法。机器学习可以被定义为一个程序或系统在一个特定的任务 或一组任务上经过一定时间学习从而提高学习器性能的能力。s v m 是一种机器 学习算法，可用于分类和回归预测，在实际应用中有相当良好的分类性能。 2 1 机器学习理论 2 1 1 机器学习的问题表示 机器学习的目的是根据给定的训练样本，对某系统输入输出之间的依赖关系 进行估计，使它能够对未知数据做出可能准确的预测。其模型可用图2 1 表示。 其中，系统s 是研究的对象，它在给定输入x 下得到一定的输出j ，l m 是所求 的学习机，输出为y 。 图2 一l 机器学习原理 机器学习问题可以形式化地表示为：已知变量y 与输入z 之间存在一定的未 知依赖关系，即遵循某一未知的联合概率分布瞰) ，机器学习问题就是根据疗 个独立同分布观测样本： o ，戊( 砣扰) ，挑)( 2 - 1 ) 在一组函数 厂( x ，w ) ) 中求一个最优函数m ，w d ) ，对依赖关系进行估计，使期 望风险： 6 中山大学硕卜论文基于改进支持向量机的入侵检测算法研究 r ( w ) = i 三( y ，厂( 石，叻) ( z f ( x ，y ) ( 2 2 ) 最小。其中，( z ，叻) 称作预测函数集，w 为函数的广义参数， 厂( 石，) 可以表 示任何函数集，( y ，厂( x ，w ) ) 表示用似，w ) 对y 进行预测而造成的损失。不同类型 的学习有不同形式的损失函数。有三类基本机器学习问题，分别是模式识别、函 数逼近和概率密度估计。对于模式识别问题，输出y 是类别号，在二值分类情况 下j ，= 0 ，1 ) 或 + 1 ，一1 ) ，这时预测函数称为指示函数，损失函数可以定义为： 三c y ，厂c 石，川，= ；二； 三：驾c 2 3 ， 2 1 2 经验风险最小化 机器学习的目的在于使期望风险最小化，对于公式( 2 2 ) 定义的期望风险最小 化，必须依赖于联合概率分布甩) 的信息，在模式识别问题中就是必须已知类 的先验概率和类的条件概率，但是在实际的机器学习问题中，我们只能利用己知 样本( 2 1 ) 的信息，对期望风险无法直接计算和最小化，因此传统的学习方法中采 用了所谓经验风险最小化( e r m ) 准则，即用样本定义经验风险 r 唧( w ) 2 寺善三( 厂( 托w ) ) ( 2 4 ) 作为对( 2 2 ) 式的估计，设计学习算法使它最小化。如果损失函数形如式( 2 3 ) ，经 验风险就是训练样本的错误率。 当”趋向于无穷大时( 2 4 ) 式趋近( 2 2 ) 式，但在实际问题中样本数目有限，所 以在有限样本下根据e r m 准则得到的学习结果未必能使真实风险也较小。 学习机器对未来输入进行正确预测的能力称作泛化性( g e n e r a l i z a t i o n ) 。在 某此情况下，经验风险最小化会导致推广能力的下降，这就是所谓的过学习问题 ( o v e m t t i n g ) 。 因此，机器学习需要一种能够在小样本情况下建立有效的学习器并保证良好 的泛化性的理论。 7 中山大学硕：l 论文基于改进支持向量机的入侵检测算法研究 2 2 统计学习理论 面： 维。 统计学习理论是研究小样本统计估计和预测的理论，主要内容包括四个方 ( 1 ) 经验风险最小化准则下统计学习一致性的条件； ( 2 ) 在这些条件下关于统计学习方法推广性的界的结论： ( 3 ) 在这些界的基础上建立的小样本归纳推理准则； ( 4 ) 实现新的准则的实际方法。 统计学习理论的重要成果是推广性的界，与此相关的一个核心概念是v c 2 2 1v c 维 为了研究学习过程一致收敛的速度和推广性，统计学习理论定义了一系列有 关函数集学习性能的指标，其中最重要的是v c 维( v a p n i k - c h e r v o n e r 此s d i m e n s i o n ) 。模式识别方法中v c 维的直观定义是：对一个指示函数集，如果存 在j 1 1 个样本能够被函数集中的函数按所有可能的2 6 种形式分开，则称函数集能 够把矗个样本打散。函数集的v c 维就是它能打散的最大样本数目j i l 。若对任意 数目的样本都有函数能将它们打散，则函数集的v c 维是无穷大 6 】。有界实函数 的v c 维可以用一定的阈值将它转化成指示函数来定义。 v c 维反映了函数集的学习能力，v c 维越大则学习器越复杂。目前尚没有 通用的关于任意函数集v c 维计算的理论，只对一些特殊的函数集知道其v c 维。 比如在”维实数空间中线性分类器和线性实函数的v c 维是刀+ 1 而函数 厂( x ，口) = s i n ( 蕊) 的v c 维为无穷大。对于一些比较复杂的学习器，其v c 维除了 与函数集有关外，还受学习算法等的影响，其确定更加困难。对于给定的学习函 数集，如何计算其v c 维是当前统计学理论中有待研究的一个问题。 中山大学硕士论文基十改进支持向量机的入侵检测算法研究 2 2 2 推广性的界 统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之 间的关系，即泛化的界。关于两类分类问题，其结论是：对指示函数集中的所有 函数( 包括使经验风险最小的函数) ，经验风险( 们与实际风险r ( 叻之间以 至少卜7 7 的概率满足如下关系 6 ： 尺( 叻r 唧( 们+ ( 2 - 5 ) 其中乃是函数集的v c 维，”是样本数。 这一结论从理论上说明了学习机器的实际风险是由两部分组成的：一是经验 风险( 训练误差) ，另一部分称为置信范围，它和学习机器的v c 维及训练样本 数有关。可以简单地表示为： 尺( w ) 尺脚( w ) + ( l l ，1 )( 2 6 ) 公式( 2 6 ) 表明，在有限样本下，学习器的v c 维越高( 复杂性越高) 则置信 范围越大，导致真实风险与经验风险之间可能的差别越大，这就是为什么会出现 过学习现象的原因。机器学习过程不但要使经验风险最小，还要使v c 维尽量小 以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的泛化性。 2 2 3 结构风险最小化 从上面的论述可以看出，经验风险最小化原则在有限样本时是不合理的，需 要同时最小化经验风险和置信范围。事实上，在传统方法中，选择学习模型和算 法的过程就是调整置信范围的过程。如果模型比较适合现有的训练样本( 相当于 五肋值适当) ，则可以取得比较好的效果。但因为缺乏理论指导，这种选择只能依 靠先验知识和经验。 统计学习理论提出一种新的策略，即把函数集构造为函数子集序列，使各个 子集按照v c 维的大小( 即j l l 的大小) 排列：在每个子集中寻找最小经验风险， 在子集间折衷考虑经验风险和置信范围，取得实际风险的最小。 这种思想称作结构风险最小化( s t m c t l l r a l 砌s km i n j m i z a t i o n ) 或有序风险 9 中山大学硕二f = 论文基于改进支持向量机的入侵检测算法研究 最小化( s e q u e n t i a lr i s km i n i m i z a t i o n ) 即s r m 准则。统计学习理论还给出了合 理的函数子集结构应满足的条件及在s l w 准则下实际风险收敛的性质。 实现s r m 原则可以有两种思路：一是在每个子集中求最小经验风险，然后 选择使最小经验风险和置信范围之和最小的子集。显然这种方法比较费时，当子 集数目很大甚至是无穷时不可行。第二种思路，即设计函数集的某种结构使每个 子集中都能取得最小的经验风险( 如使训练误差为o ) ，然后只需选择适当的子 集使置信范围最小，则这个子集中使经验风险最小的函数就是最优函数，支持向 量机算法就是这种思想的具体体现。 2 2 4 支持向量机原理 支持向量机( 简称s v m ) 基于结构风险最小化理论，其核心内容是v | a p n i k 在1 9 9 2 到1 9 9 5 年间提出的，目前仍处于不断发展的阶段。 2 2 4 1 最大间隔分类器 s v m 是从线性可分情况下的最优分类平面发展而来的，其基本思想如图2 2 所示。 6 = + l 图2 2 最优分类平面 其中圆点和三角代表两类数据，h 为分类平面，h l ，h 2 分别为过各类中离 分类平面最近的数据且平行于分类平面的平面，h l 与h 2 的距离称为分类间隔。 所谓最优分类平面就是最大化分类间隔的分类平面。在h l ，h 2 上面的点称为支 l o 中山大学硕士论文基于改进支持向量机的入侵检测算法研究 持向量( s u p p o r tv c c t o r ，s v ) 。最优分类问题可以表示为： 设分类平面的方程为： w x + 6 = 0 ( 2 7 ) 对于线性可分样本集( 五，乃) ，f _ 1 ，2 ，尺，m + 1 ，一1 ) ，满足： m ( w 而+ 6 ) 一1 0 ，f = 1 ，2 ， 则分类间隔为赢，最大化分类间隔等价于最j 、化扣2 。 ( 2 - 8 ) s v m 的核心思想是通过最大化分类间隔控制泛化能力。统计学理论指出， 在维空间中，设样本分布在一个半径为尺的超球范围内，则满足条件0 叫l 彳的 正则超平面构成的指示函数集厂( x ，w ，6 ) = s 弘 w 石+ 6 ) 的v c 维满足下面的界 6 ： 办m i n ( 【r 2 彳2 ，忉+ 1( 2 9 ) 因此m 1 2 最小就是使v c 维的上界最小，从而满足s r m 准则。 利用l a 铲a j l g e 优化方法可以把上述最优化分类问题转化为其对偶问题 6 】， 即在约束条件，问题表述为： m a ) 【q ) = 口f 一去口f 口y f ) ，( t z ) ，1f ，= l f s t y f 口，= o f = 1 口f 0 ，江1 ，2 ， ( 2 1 0 ) ( 2 - 1 1 ) ( 2 1 2 ) 为每个样本对应的l a 铲锄g e 乘子。这是一个不等式约束下二次优化问题，存 在唯一解。根据汀条件，解中只有一部分不为o ，对应的向量就是支持向 量。决策函数为： ， 厂( 功= s 盟 ( w 石) 一町= s 印 口；l 乃( 石) + 6 ) ，6 是分类阈值( 2 1 3 ) 如果数据有噪声，则数据一般线性不可分，在这种情况下，可以引入松弛变 中山人学硕：l ：论文基于改进支持向量机的入侵检测算法研究 量毒，它允许在一定程度上违反问隔约束，则问题变为： m i n 知训2 + c 鼻 k j s t y f ( w x f + 6 ) 1 一专净1 ，1 ( 2 1 4 ) ( 2 1 5 ) 磊o 卢1 ，1 ( 2 1 6 ) 对于有噪声数据，最优分类平面是最少错分样本和最大化分类间隔的平衡。 其中c 是一个常数，用于控制对错分样本的惩罚程度。含噪声数据分类的对偶 问题如下： f1f m a 】【q ( 口) = 口，一寺口j 口y f y j ( z f x ，)( 2 1 7 ) 扭if ，= l s t y ，口，= o ( 2 1 8 ) o 口f c ，f = 1 ，2 ，z ( 2 1 9 ) 2 2 4 2 核函数特征空间 对非线性分类问题，通常可以通过非线性变换转化为某个高维特征空间中的 线性分类问题，在变换空间中求最优分类超平面。 如上节所述，通过将最大间隔分类的原问题转化为对偶问题，计算的复杂度 不是取决于空间维数，而是取决于样本数，尤其是样本中的支持向量数。最大间 隔分类的对偶形式只涉及训练样本之间的内积运算( 一x j ) ，则在特征空间中实 际只需进行内积运算。这种内积运算可以用在原空间的特征映射的内积实现，称 为核函数。 定义2 1 ( 核函数，k e r e n lf u l l c t i o n ) 核函数是一个函数k ，对所有x ，z x ，满 足： k ( x ，z ) = ( 痧( x ) ( z ) ) ( 2 2 0 ) 其中是从原空间x 到( 内积) 特征空间f 的映射。 中山大学硕士论文 基于改进支持向量机的入侵柃测算法研究 实际上可以直接定义一个核函数，通过它隐式地定义特征空间。根据泛函的 有关理论，只要函数k 满足m e r c e r 条件 7 】，它就对应于变换空间中的内积。 在最大间隔分类器中引入核函数，则( 2 1 7 ) 可以表示为： 考虑一个训练样本： s = ( ( z i ，y 1 ) ，( 工，y ，) )( 2 2 1 ) 它在核蜘) 隐式定义的特征空问中是线性可分的，假定n 4 = ( 彳，呓，彳) 是下面 二次优化问题的解： m a xq ( 口) = 口f 一寺口f 口y f y k ( 而，石) f = l f ，卢i ， s t y j 口f = o j - l o 口f c ，f = 1 ，2 ，j 则决策规则为s 印( 脚) ，其中： ， 厂( 工) = y ，口? k ( t ，x ) + 6 ( 2 2 2 ) ( 2 2 3 ) ( 2 - 2 4 ) ( 2 - 2 5 ) 等价于核坼力隐式定义的特征空间中的最大间隔超平面，选择6 使得 y ，厂( t ) = 1 成立，其中对任意f 有o o 2 3 c s v m 算法 2 3 1c s v m 算法描述 ( 2 2 6 ) ( 2 2 7 ) ( 2 - 2 8 ) ( 2 - 2 9 ) c s v m 也称为非线性软间隔支持向量机，实现了最大分类间隔分类原理。 c s v m 中的参数c 是惩罚因子，起到控制对错分样本惩罚程度的作用，实现在 错分样本的比例和算法复杂度之间的折中。 对于给定的训练样本集d f = x ，j ，- l ，其中是第f 个输入向量，而尺”， j ， + 1 ，一1 ) ，是输入向量的总数，矽( x ) 是输入向量到特征空间的映射。在c s v m 中，为寻找最优超平面，需要求解下列最优化问题： m l n丢ow | 1 2 + c 圭点 厶 ，= i s t y i ( w 矽( 戈f ) + 6 ) 1 一磊i = l ，l 当0f - 1 ， ( 2 - 3 0 ) ( 2 3 1 ) ( 2 3 2 ) 其中赢为分类间隔，最大化分类间隔等价于最j 、化扣2 。其对偶形式为： 1 4 中山大学硕士论文 基于改进支持向量机的入侵柃测算法研究 m i n 丢q 小静 ， s t j ，= o 扛l o 口l c ，i - 1 ，l q i j = y f y ，k ( x i ，x j ) k ( t ，石) 兰矽( x i ) 。( x j ) ( 2 3 3 ) ( 2 3 4 ) ( 2 3 5 ) ( 2 3 6 ) ( 2 - 3 7 ) 求解上述二次规划问题，为每个样本对应的l a 伊a n g e 乘子，根据l q 汀条件， 解中只有一部分不为o ，对应的向量就是支持向量( s v ) ，s v 的l a 伊a n g e 乘 子为口? ，则常规s v m 的决策函数为： 厂( x ) = j 忉 儿口扛( x 。，x ) + 6 1 x i s r 2 3 2c s v m 算法的几何意义 ( 2 - 3 8 ) 图2 _ 4 c s v m 原理 c s v m 支持向量机的原理如图2 4 所示。从图中可以看出，c s v m 支持向 量机寻求一个将两类数据分开的超平面，使两类数据之间的足巨离而最大并且错 分的代价最小。参数c 用来控制在间隔最大和错分的代价最小之间的折衷程度。 中山人学硕f ：论文基于改进支持向量机的入侵检测算法研究 根据i o 汀条件，有： 口f ( w ( 工f ) + 6 1 + 色) = o( 2 3 9 ) 层缶= ( c 一口，) 蛋= 0 ( 2 - 4 0 ) 当口，= o ，由公式( 2 - 4 0 ) 可知缶= o ，再由( 2 - 3 9 ) 可知w ( x ) + 6 1 ，这时而 位于超平面上或超平面外一侧。 当o 口f c ，由公式( 2 4 0 ) 可知色= o ，再由( 2 3 9 ) 可知w 矽( j f ) + 6 = l ，这时 五位于超平面上，而是超平面上的支持向量，记为s v 。 当口，= c ，由公式( 2 - 4 0 ) 可知茧0 ，再由( 2 - 3 9 ) 可知w ( 功+ 6 = 1 一茧，这时 而位于超平面上或分类间隔内，而是超平面外的支持向量，记为b s v 。图2 5 给 出c s v m 中口值的分布区域。 o 町 c 图2 5c s v m 中口值分布区域 2 4o n e c l a s ss v m 算法 2 4 1o n e c l a s ss v m 算法描述 c o n e c l a s ss v m 属于无监督学习算法，适用于两类样本比例不均衡的分类问 题。o n e c l a s ss v m 假设输入的数据都属于正类，通过映射将属于大类( 正类) 1 6 中山大学硕士论文 基于改进支持向量机的入侵柃测算法研究 的数据转移到远离原点的位置，而将属于小类( 负类) 的数据留在原点为中心的 一个小区域里，用一个尽可能小的超球包含尽可能多的样本，在超球外的样本是 离群点( o u t l i e r ) 。 给定没有分类标记的样本d ，= “l 工。r ”) ：= i ，o n e c l a s ss v m 的初始问题 为： m m 却2 + 吉鼻一p ( 2 - 4 - ) s t ( w 矽( x ，) ) p 一鼻 ( 2 - 4 2 ) 鼻0 ，f 1 ， ( 2 - 4 3 ) y ( 0 ，1 ) 为平衡参数，用来控制多少样本在超球外，y 越小表示超球包含越多的 样本。量是松弛变量。其对偶问题为： m i n 丢仅 ( 2 - 4 4 ) s t o 口f 1 ( ，) ，扣1 ， ( 2 4 5 ) ， = 1 f = l q ，= k ( t ，x ) 三矽( t ) 。( x ，) o n e c l a s ss v m 的决策函数为： ( 2 4 6 ) ( 2 4 7 ) 厂( x ) = s 劬( 口，k ( x ，x ) 一p ) ( 2 4 8 ) 其中p 可以通过下列方式计算，取任何一个满足o 口， 的样本，根据汀 w 条件，其对应的六等于o ，式( 2 - 4 2 ) 变为： ， p = ( w 矽( ) ) = 口，k ( ，工) ( 2 - 4 9 ) ，= l s c h 6 k o p f 等 8 】已证明参数y 是被超平面错分的样本数所占总样本数比例的 上界以及支持向量个数所占样本数比例的下界。 1 7 中山人学顾i ：论文 基于改进支持向量机的入侵检测算法研究 2 4 2o n e c l a s ss v m 算法的几何意义 原点 图2 6o n e c l a s ss 几何原理 o n e c l a s ss v m 的原理如图2 6 所示，o n e c l a s ss v m 寻求一个将样本与原 点分开的超平面，使超平面与样本之间的距离p 州 叫i 最大化且被分到原点一侧样 本的代价最小。参数u 控制被分到原点一侧样本所占样本总数的比例以及位于超 平面上的样本数和被分到原点一侧的样本数之和占样本总数的比例。 o n e c l a s ss v m 要求训练数据为j 下类，但是在实际应用中，训练集有噪声。 o n e c 1 a s ss v m 允许将部分数据排除在超球外，并提供参数y 作为对异常数据的 惩罚。 根据k l 汀条件，有： 口，( w 矽( ) 一p + 六) = o ( 2 5 0 ) 1 屈六= ( 二i 一口，) 毒= o ( 2 5 1 ) 当口，= o ，由公式( 2 - 5 1 ) 可知六= o ，再由( 2 - 5 0 ) 可知w 矽( 工) p ，这时而位于 超平面上或超平面远离原点一侧。 当o 口f ，由公式( 2 5 1 ) 可知点= o ，再由( 2 5 0 ) 可知w 矽( x ) = p ，这时 麓位于超平面上，而是超平面上的支持向量，记为s v 。 当口f ： ，由公式( 2 5 1 ) 可知缶o ，再由( 2 5 0 ) 可知w ( 工) p 一茧，这时 中山大学硕+ 论文 基于改进支持向量机的入侵榆测算 圭研究 而位于超平面上或超平面靠近原点一侧，而是超平面外的支持向量，记为b s v 。 使用记号j j s v 表示s v 的个数， b s v 表示b s v 的个数，那么可以证明下面 两个不等式成立 9 】： 存b s v 订( 2 5 2 ) f j s v + 群b s v 以 ( 2 - 5 3 ) 由此可见，参数确定了边界外支持向量数的上界，从而也决定了排除在边界外的 异常点的比例。图2 7 给出o n e c 1 a s ss v m 口值的分布区域。 图2 7o n e c l a s ss 订口值分布区域 2 5s v d d s v m 算法 2 5 1s v d d s v m 算法描述 给定没有分类标记的样本d ，= x ，h 尺”) ：= l ，s v d d s v m 的初始