（计算机软件与理论专业论文）非平衡类的异常检测研究.pdf

l r n a n j i n gu n i v e r s i t yo f a e r o n a u t i c sa n d a s t r o n a u t i c s t h eg r a d u a t es c h 0 0 1 c o l l e g eo f i n f o r m a t i o ns c i e n c ea n dt e c h n o l o g y a n o m a l y d e t e c t i o nr e s e a r c h f o ri m b a l a n c e dc l a s s e s a 砀e s i si n c o m p u t e rs o f t w a r ea n dt h e o r y b y z h a n gq i n g - q i n g a d v i s e d b y p r o f c h e ns o n g c a n s u b m i t t e di np a r t i a lf u l f i l l m e n t o ft h er e q u i r e m e n t s f o r t h ed e g r e eo f m a s t e ro fe n g i n e e r i n g j a n ，2 0 1 0 嬲f 燃必 y 18 2 9 芝l 芝。 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进 行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容外， 本学位论文的研究成果不包含任何他人享有著作权的内容。对本论文所 涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标 明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允许 论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名： ! 醴盔盔 日 期：垒：生：l ：瞧 j j 南京航空航天大学硕士学位论文 摘要 异常检测可视为非平衡分类问题，因此可借助解决该问题的方法来实现异常检测。近年来， 对非平衡分类问题的研究在模式识别领域受到了广泛关注，并已取得了显著进展，相关成果已 用于垃圾邮件过滤、网络入侵检测、文本检索等各个领域。 支持向量机( s v m ) 作为一种性能优异的分类器，已在众多模式识别问题中获得了印象深 刻的效果，并也可用于非平衡分类问题。但由于其本身对非平衡类的脆弱性，直接用它难以奏 效。非平衡支持向量机( a s v m ) 则相对有效地克服了这一不足。其有效性归因于它融合了单 类支持向量机对非平衡类的鲁棒性和s v m 大间隔的优势，即同时使类间间隔和单类间隔最大 化。但这一有效性也部分掩盖了a s v m 的不足，即忽视了每类数据内在结构的利用。受到结构 化s v m ( s s v m ) 的启发，我们发展出了结构化非平衡支持向量机( s t a s v m ) 。它不仅保留了 a s v m 的优点，同时通过在a s v m 目标函数中嵌入类内结构信息，达到了结合更多先验知识， 提升分类性能的目的。实验验证了s t a s v m 确实具有比a s v m 更优的分类性能。 尽管a s v m 和s t a s v m 在非平衡分类问题上获得了相对好的分类性能，但其时间效率较 低。增量算法能有效地提高时间效率，但高效地解决非平衡分类问题的增量算法仍相对缺乏。 我们从降低类间不平衡率出发，将一种简单的增量学习算法拓展应用于当前的类不平衡问题上， 并在部分u c i 数据集上取得了满意的实验效果。进一步通过结合主动学习策略，我们提出了基 于主动学习的增量型非平衡支持向量机( 队s ) ，其在保证与a s v m 相当分类效果的前提下， 大大减少了算法的训练时间。 关键词：类不平衡问题，支持向量机，非平衡支持向量机，结构信息，主动学习， 增量学习 非平衡类的异常检测研究 a b s t r a c t a n o m a l yd e t e c t i o nc a nb es o l v e da sc l a s si m b a l a n c e dp r o b l e m sw h i c hh a v e a t t r a c tm u c h a t t e n t i o nf r o mp a t t e mr e c o g n i t i o na n dm a c h i n el e a r n i n ga r e a s r e c e n t l y , i nc l a s si m b a l a n c e dp r o b l e m s ， r e s e a r c h e r sh a v em a d es o m es i g n i f i c a n tp r o g r e s s ，a n da p p l i e dt h ep r o g r e s si ns u c ha r e a sa ss p a m f i l t e r i n g ，n e t w o r ki n t r u s i o nd e t e c t i o n ，t e x tm i n i n ga n ds oo n s u p p o r tv e c t o rm a c h i n e s ( s v m ) i sa ne x c e l l e n tc l a s s i f i e r , w h i c hh a sg a i n e ds o m ei m p r e s s i v e e f f e c t si ns u c ha r e a sa sp a t t e r nr e c o g n i t i o na n dm a c h i n el e a r n i n g s v mh a sa l s ob e e na p p l i e di nc l a s s i m b a l a n c e dp r o b l e m s h o w e v e r , b e c a u s eo fi t sv u l n e r a b i l i t ya sw e l la st h es p e c i a l i t yo fc l a s s i m b a l a n c e dp r o b l e m s ，s v mc a nn o ts o l v et h e s e sp r o b l e m sv e r yw e l l a s y m m e t r i cs u p p o r tv e c t o r m a c h i n e ( a s v m ) w h i c hi n c o r p o r a t e st h ei d e a so fs v ma n do n e - c l a s ss v m ( o c s v m ) c a n s o l v e c l a s si m b a l a n c e dp r o b l e m sr e l a t i v e l yw e l l h o w e v e r , a s v mi g n o r e st h ei m p o r t a n c eo fw i t h i n - c l a s s s t r u c t u r ei n f o r m a t i o n i n s p i r e db ya s v m ，w ed e v e l o pas t r u c t u r e da s y m m e t r i cs u p p o r tv e c t o r m a c h i n e ( s t a s v m ) t om a x i m i z et h ec l a s s - m a r g i na sw e l la st h em 啦b e t w e e nt h eo r i g i na n do n eo f t h ec l a s s e s m e a n w h i l e ，s t a s v md i r e c t l ye m b e d st h ew i t h i n - c l a s ss t r u c t u r ei n f o r m a t i o ni n t ot h e a s v ma n dm a x i m i z e st h ew i t h i n - c l a s st i g h t n e s st or a i s ei t sp e r f o r m a n c e b yt h i sm e t h o d ，s t a s v m n o to n l yf o c u s e so nt h eb e t w e e n - c l a s ss c a t t e r , b u ta l s ot a k e st h ew i t h i n - c l a s ss c a t t e ri n f o r m a t i o ni n t o a c c o u n t e x p e r i m e n tr e s u l t ss h o wt h a tb yi n c o r p o r a t i n gm o r ep r i o rk n o w l e d g ef r o md a t a ，s t a s v m h a sab e t t e rg e n e r a t i o nt h a na s v m a s v ma n ds t a s v mh a v eg a i n e dg o o dp e r f o r m a n c e si nc l a s si m b a l a n c e dp r o b l e m s h o w e v e r , t h e yb o t ht a k em u c ht r a i n i n gt i m e i n c r e m e n t a ll e a r n i n ga l g o r i t h m sc a ni m p r o v et h et i m ee f f i c i e n c y s i g n i f i c a n t l y h o w e v e r , i n c r e m e n t a la l g o r i t h m sf o ri m b a l a n c e dc l a s s i f i c a t i o na r es t i l lr e l a t i v e l yr a r e i n t h i sp a p e r , b a s e do nt h er e d u c t i o no ft h ei m b a l a n c er a t i o ，w ea p p l yas i m p l ei n c r e m e n t a ll e a r n i n g a l g o r i t h mc a l l e da sm i n o v e rt oi m b a l a n c e dc l a s s i f i c a t i o np r o b l e ma n da c h i e v eg o o dp e r f o r m a n c e si n s o m eu c id a t a b a s e s b e s i d e s ，b yi n t r o d u c i n gt h ea c t i v el e a r n i n gs t r a t e g yt o0 1 1 1 a l g o r i t h m , w ef u r t h e r p r o p o s ea ni n c r e m e n t a la s y m m e t r i cs u p p o r tv e c t o rm a c h i n e sb a s e do na c t i v el e a r n i n g ( a s v m ) ， w h i c hs i g n i f i c a n t l yr e d u c e st h et i m ec o n s u m i n gw h i l es t i l lk e e p st h ec o m p a r a b l ep e r f o r m a n c et ot h e m i n o v e ra l g o r i t h m k e yw o r d s ：c l a s si m b a l a n c e dp r o b l e m s ，s u p p o r tv e c t o rm a c h i n e s ，a s y m m e t r i cs u p p o r tv e c t o r m a c h i n e ，s t r u c t u r e di n f o r m a t i o n ，a c t i v el e a r n i n g ，i n c r e m e n t a ll e a r n i n g 南京航空航天大学硕士学位论文 目录 第一章绪论1 1 1 异常检测简介1 1 2 异常检测的难点。l 1 3 本文的主要工作2 1 4 本文的内容安排3 第二章异常检测相关技术。4 2 1 异常检测研究概述。4 2 2 基于单类问题的分类方法4 2 2 1 支持向量机( s ) 为基础的方法4 2 2 2 统计为基础的方法7 2 3 基于非平衡问题的分类方法。8 2 3 1 重采样为基础的方法8 2 3 2 支持向量机为基础的方法9 2 4 其他方法1 0 2 5 本章小结1 1 第三章结构化非平衡支持向量机1 2 3 1 非平衡分类问题概述1 2 3 2 非平衡支持向量机( a s 垤) 介绍1 2 3 2 1 支持向量机( s ) 1 3 3 2 2 单类支持向量机( o c s 、m i ) 。1 4 3 2 3 非平衡支持向量机( a s 、伸讧) 1 6 3 3 结构化非平衡支持向量机( s 认s 订) 。1 7 3 3 1w a r d 层次聚类1 9 3 3 2s t a s v m 的设j 汁2 l 3 4 实验2 3 3 4 1 实验设置与结果。2 3 3 4 2 实验分析2 6 3 5 本章小结2 6 第四章基于主动学习的增量型非平衡支持向量机2 7 非平衡类的异常检测研究 4 1 增量型非平衡分类器概述2 7 4 2 增量型学习算法2 8 4 2 1 增量型分类算法简介2 8 4 2 2 增量感知器2 8 4 2 3 增量支持向量机2 9 4 3 主动学习。3 0 4 3 1 主动学习简介。3 0 4 3 2 主动学习分类一3 0 4 4 基于主动学习的增量型支持向量机( 队s 讧) 3 1 4 4 1i 9 机3 1 4 4 2m i n o v e r 算法3 2 4 4 3 “5 9 技巧”3 4 4 4 4i a s 订流程3 4 4 5 实验3 5 4 5 1 实验设置与结果。3 5 4 5 2 实验分析3 7 4 6 本章小结3 8 第五章总结与展望3 9 5 1 已有工作总结3 9 5 2 未来工作展望4 0 参考文献4 2 致谢4 6 硕士研究生期间参与的科研项目及发表的论文4 7 南京航空航天大学硕士学位论文 图表清单 图2 1o c s v m 和s v d d 在高斯核下的最优超平面6 图3 1s 得到的最优分类面。1 3 图3 2o c s v m 得到的最优分类平面1 5 图3 3a s 垤融合s 订和o c s v m 示意图1 6 图3 4s v m 和s l m m 在人工数据集上得到的分类平面1 8 图3 5 人工数据集上s t a s v m 和a s v m 的分类效果1 9 图4 1 批处理感知器的算法流程2 9 图4 2 增量感知器的算法流程。2 9 图4 3 间隔内样本间的不平衡率远小于整个样本集间的不平衡率3 l 图4 4 迭代步数对a u c 实验结果的影响3 6 表3 1 实验中使用的数据集和样本规模。2 4 表3 2s t a s v m 和a s v m 在u c i 数据集上的a u c 实验结果2 5 表3 3s t a s v m 和a s v m 在u c i 数据集上的实验稳定性2 5 表4 1 实验中使用的数据集、正负类样本规模以及训练样本规模。3 6 表4 2 三种算法a u c 实验的结果3 7 表4 3 三种算法在u c i 数据集上的训练时间。3 7 v 非平衡类的异常检测研究 注释表清单 s v m ( s u p p o r tv e c t o rm a c h i n e s ) ： o c s v m ( o n e c l a s ss u p p o r tv e c t o rm a c h i n e ) ： s v d d ( s u p p o r tv e c t o rd o m a i nd e s c r i p t i o n ) ： a s v m ( a s y m m e t r i cs u p p o r tv e c t o rm a c h i n e ) ： s t a s v m ( s t r u c t u r e da s y m m e t r i cs v m ) - s s v m ( s t r u c t u r e ds u p p o r tv e c t o rm a c h i n e ) - s l m m ( s t r u c t u r e dl a r g em a r g i nm a c h i n e ) ： k e r n e lt r i c k ： n f l ： l d a ( l i n e a rd i s c r i m i n a n ta n a l y s i s ) ： p c a ( p r i n c i p a lc o m p o n e n ta n a l y s i s ) s v d ( s i n g u l a rv a l u ed e c o m p o s i t i o n ) ： s m o ( s e q u e n t i a lm i n i m a lo p t i m i z a t i o n ) ： k - m e a n s ： a c t i v el e a r n i n g ： o n l i n el e a r n i n g ： i n c r e m e n t a ll e a r n i n g ： p e r c e p t r o n ： 5 9 t r i c k ： l a g r a n g em u l t i p l i e r ： s c m p m ( s i n g l ec l a s sm i n i m a xp r o b a b i l i t ym a c h i n e ) - 不含标号的训练样本集合 训练样本标号集合 包含标号的样本集合 样本维数 分类超平面法向量 松弛变量 原空间向h i l b e r t 空间的隐映射 核函数 支持向量机 单类支持向量机 支持向量数据描述 非平衡支持向量机 结构化非平衡支持向量机 结构化支持向量机 结构化大间隔机 核技巧 没有免费午餐定理 线性判别分析 主成分分析 奇异值分解 顺序最小化 k 均值聚类 主动学习 联机学习 增量学习 感知器算法 5 9 技巧 拉格朗日乘子法 单类最小化最大概率机 h乙出w孝矽后 南京航空航天大学硕士学位论文 瑚v m ： s u p e r v i s e dl e a r n i n g ： u n s u p e r v i s e dl e a r n i n g ： s e m i - s u p e r v i s e dl e a r n i n g ： m l e o v l a x i m u ml i k e l i h o o de s t i m a t e s ) ： f p r ( f a l s ep o s i t i v er a t e ) ： t p r o r u ep o s i t i v er a t e ) ： 基于主动学习的增量支持向量机 监督学习 无监督学习 半监督学习 最大似然估计 误警率 正确警报率 南京航空航天大学硕士学位论文 第一章绪论弟一早珀1 ：匕 1 1 异常检测简介 异常检测 2 2 0 1 是指从数据中发现为数不多的异常模式，而这些异常模式在训练样本中通常 很少出现，甚至没有出现过。这些行为异常的模式通常被称作异常点( a n o m a l y ) 、野值点( o u t l i e r ) 或新颖点( n o v e l t y ) 等。所以，异常检测也被称作新颖性检测( n o v e l t yd e t e c t i o n ) 【2 】或野值检 测( o u t l i e rd e t e c t i o n ) 【l 】等。 对于异常检测的研究最早可追溯到十九世纪末【1 9 1 ，当时的统计学领域已开始关注该问题。 现在，异常检测已成为模式识别和机器学习等诸多领域的研究主题，众多学者已提出并设计了 若干实现异常检测的方法和算法，并取得了一些有效的进展。 在模式识别领域，异常检测研究通常可被视作两类不同的问题来解决，一类为单类分类问 题而另一类为( 两类) 非平衡分类问题。所谓单类分类，是指在训练样本中只有一类样本，而另 一类样本则由于采样局限而无法获得。所谓非平衡分类问题，又称类不平衡问题，是指训练样 本中存在两类样本，但其中目标类和非目标类数据规模极度不平衡。 目前，异常检测己应用到众多领域。按识别目的分，异常检测应用主要分为两类：第一类 是“识别异常”：这类应用以故障诊断f 2 9 1 ，网络入侵检测口1 1 【4 2 】【4 3 1 ，邮件过、滤【3 5 3 6 1 ，医疗诊蝌3 3 1 等为代表，目的是从领域内的大量正常数据模式中识别异常的数据模式。第二类是“挖掘兴趣”。 这类应用以文本检索瞵一鲫一，生物信息掣3 9 1 等为代表，目的是从大量无关联数据中挖掘出我 们需要的关联或“感兴趣”数据。 1 2 异常检测的难点 虽然异常检测研究已取得了一些进展，但其仍存在诸多不足，从模式识别和机器学习的角 度分析，至少来自如下两方面： 第一，异常检测仍不够精确，即识别精度不高。特别在故障诊断、医疗诊断等精度要求非 常高的应用领域，识别精度的不足可能带来严重后果。 第二，实时性不足，即算法效率不高。异常检测的众多应用如邮件过滤，入侵检测等，需 要较高的实时性，甚至在实时高效的前提下才进一步要求较高的精度。 如上所述，异常检测在精度和效率两方面仍有待提高，但提高的难点主要归咎于以下三点 原因： 首先：先验信息匮乏或利用不足。一方面，异常数据的极度缺失，导致了分类器设计中可 用的先验信息不足，从而严重影响了分类精度。另一方面，正常类数据虽然规模较大，但其包 非平衡类的异常检测研究 含的正常类信息得不到充分利用，也影响了分类精度的提高。 其次：应用领域数据规模不断增大引起的海量数据处理问题。网络环境带来的海量数据要 求分类器有着更高的处理效率，与此同时，海量数据使得原本模式识别领域的一大类批算法 ( b a t c ha l g o r i t h m s ) 由于效率问题不能使用，学者们必须针对海量数据提出更快的增量 ( i n c r e m e n t a l ) 或联机( o n l i n e ) 算法( 增量算法和联机算法将在第四章中具体介绍) 。 最后：根据“没有免费午餐定理”( n of r e el u n c h ) 【3 】没有一个普适的分类器能解决所有 异常检测问题。这也必然要求我们依据不同的应用领域设计不同的分类算法，这实质性地增加 了异常检测的难度。 1 3 本文的主要工作 本文立足于非平衡分类的观点展开研究，目的是提出并设计出性能相对更优的非平衡分类 算法，达到更有效地处理非平衡分类问题和部分解决异常检测问题的目的。本文主要从提高分 类器的精度和时间效率两方面着手，并完成了以下工作： l 、针对异常信息匮乏和正常类信息利用不足的问题，我们充分利用了类内结构和类间分布 信息，提出了一个较现有非平衡分类器性能更优的分类算法。本小组，4 5 1 先前已设计了数个性 能优异的分类器，较好地解决了部分分类问题( 包括多类分类和单类分类) 。他们的主要出发点 是在最大间隔思想的基础上，进一步融合各类数据的类内结构信息。但这些算法并不能有效地 解决非平衡分类问题。受之前工作的启发，我们设计了一个非平衡分类器，其融合了支持向量 机( s u p p o r tv e c t o rm a c h i n e s ，s ) 和单类支持向量机( o n ec l a s ss u p p o r tv e c t o rm a c h i n e ， o c s v m ) 最大间隔的优势，克服了s v m 原有对非平衡问题的脆弱性，并通过最大化类内紧性 的手段，结合更多的类内结构信息，更有效地解决了类不平衡问题。最后，我们在通用的部分 u c i 数据集上验证了该算法的分类性能。 + 2 、针对数据量增大引起的批处理算法效率低下的问题，我们设计了一个增量型分类器，高 效地解决了部分非平衡分类问题。很多异常检测应用需要较高的分类效率，而批算法通常很难 达到这样的目的。我们设计了一个适用于非平衡问题的增量学习算法，目的是在不影响分类精 度的前提下，有效地提高算法效率。我们基于这样一个事实：信息量最丰富样本的规模通常处 于相对平衡状态，同时它们又是对分类器设计贡献最大的样本，因此充分利用这些信息量最丰 富的样本不仅可以缓解类间的不平衡性，而且有利于利用更多的先验知识。基于以上想法，我 们将一种简单的增量学习算法拓展应用到了非平衡分类问题之中，取得了不错的分类效果。进 一步我们又结合了主动学习技巧，提出了一种基于主动学习的增量型算法，其在不明显影响分 类精度的前提下大大提高了算法的时间效率。 2 南京航空航天大学硕士学位论文 1 4 本文的内容安排 本文共分五章，各章主要内容安排如下： 第二章主要回顾了异常检测的主要研究方法，我们将其归为两大类，分别是单类分类为基 础的方法和非平衡分类为基础的方法。主要介绍了两大类方法中有代表性的分类算法，对这些 算法进行了深入的分析和总结。通过总结找到了非平衡分类研究领域的不足与盲点，为后续章 节的研究打下理论基础。 第三章首先回顾了经典的支持向量机( s 讧) 和单类支持向量机( o c s ) 算法。进一 步深刻分析了非平衡支持向量机算法( a s 讧) 。受到a s v m 和本小组先前工作的启发，我们 进一步提出了结构化非平衡支持向量机( s 认s 订) 。通过实验验证，我们的s t a s v m 算法在分 类性能上优于a s v m 分类器。 第四章首先介绍了增量型算法与主动学习技巧的基本知识，再此基础上，我们从非平衡分 类问题的本质出发，集成了m i n o v e r t 5 3 1 算法和“5 9 技巧”【5 l ，提出了基于主动学习的增量型非 平衡支持向量机( i a s v m ) 。实验表明，i a s v m 分类器在分类性能与a s v m 相当的基础上， 有效地提高了算法的时间效率。 第五章总结了已完成的工作并对后续工作进行了展望。 本文的工作得到了国家自然科学基金( 6 0 7 7 3 0 6 1 ) 和江苏省自然科学基金( b k 2 0 0 8 3 8 1 ) 的资助。 3 非平衡类的异常检测研究 第二章异常检测相关技术 2 1 异常检测研究概述 异常检测方法主要分为两类：第一类方法是训练样本中没有异常样本，只有正常样本，将 异常检测问题视为单类分类问题；第二类方法是考虑异常样本，训练过程中同时采用正常和异 常样本，但样本规模极不平衡，故称该类方法为类不平衡分类问题，或称为非平衡问题。 单类分类问题是一类经典而有效的方法，其中最主要的两种是支持向量机( s v m ) 为基础 的方法和统计为基础的方法。近年来，包括信息论等一些新领域的知识也渐渐引入到了异常检 测研究中，进而发展出了一批新方法。 非平衡分类闯题是近几年比较流行的方法5 1 【6 】，其主要利用重采样手段消除类间的不平衡 性，从而降低正常类和异常类间的不平衡性，后利用经典分类算法实现分类。但由于重采样技 术存在其局限性，近年来，学者们将最大间隔思想用到了非平衡分类问题之中，并结合各类数 据间的不平衡性，设计出了众多基于最大间隔思想的类不平衡分类器，达到了很好的分类效果。 下面具体介绍单类分类和非平衡分类中的一些经典算法，我们主要从以下方面对各类方法 进行详细介绍：方法的出发点，方法的缺陷，方法的改进等。通过总结与对比，我们找到了非 平衡分类研究领域的盲点，并据此提出了两个高效的异常检测分类器。 2 2 基于单类问题的分类方法 相比于基于非平衡问题的分类方法，单类分类方法已比较成熟，学者们已提出并设计出了 一批经典算法【9 一。一2 1 4 1 ，其中以统计学习理论为基础的方法和以支持向量机为基础的方法最为 典型。近几年，学者们又利用其它领域的知识，如信息论等，发展出了众多解决单类分类问题 的新方法，下面做详细介绍。 2 2 1 支持向量机( s v m ) 为基础的方法 支持向量机是模式识别【3 】领域最经典最流行的分类方法之一。所谓分类，是指通过已有的 有标号或无标号的训练样本学习出一个分类模型，使之能在测试样本上获得较优的推广性能。 若训练样本均为有标号样本，我们称之为监督学习( s u p e r v i s e dl e a r n i n g ) ：若训练样本均为无标 号样本，即称之为无监督学习( u n s u p e r v i s e dl e a r n i n g ) ：若训练样本中同时有无标号和有标号样 本，即称之为半监督学习( s e m i s u p e r v i s e dl e a r n i n g ) 。单类分类问题通常是监督学习问题，其假 设所有的训练样本都来自正常类，它主要分为两个过程，训练过程通过已有的训练样本学习出 分类器，并通过该分类器确定正常区域，测试过程判断剩余的测试样本是否在分类器所决定的 4 南京航空航天大学硕士学位论文 正常区域内，若在正常区域内，就判断为正常样本，否则，即视为异常样本。 支持向量机( s v m ) 【7 】通过寻求各类样本到分类面间的最大间隔，达到了降低v c 维的目 的【8 】，得到了较优的分类推广性能，是当下最流行的分类器之一。它通过核技巧( k e r n e lt r i c k ) 将低维数据投影到高维空间且不引起维数灾难【3 】，同时又将低维空间中的线性不可分问题转化 为高维空间中的线性可分问题。 以支持向量机为基础的方法充分利用了最大间隔思想。这类方法通过训练找到一个包含大 多数样本的决策区域，落在该区域内的点表示正常样本，而区域外的点表示异常样本，这其中 以单类支持向量机( o n ec l a s ss u p p o r tv e c t o rm a c h i n e ，o c s v i v l ) 9 1 和支持向量数据描述最为经 典( s u p p o r tv e c t o rd o m a i nd e s c r i p t i o n 。s v d d ) 0 0 。 o c s v m 人为地规定原点为唯一的异常样本，训练过程期望寻求一个超平面( 高维空间中 的平面) 能分开原点与其余正常样本，同时使得原点距分类平面的距离最大。测试过程中，如 果测试样本位于正常样本所在的半平面区域内则将该样本视为正常样本，否则视为异常。由于 完全分开原点与正常样本的条件有时过于苛刻，o c s v m 引入松弛变量对该条件进行松弛，从 而解决了部分线性不可分问题。o c s v i v i 同样使用了核技巧，其不仅避免了维数灾难，同时解 决了低维空间下的线性不可分问题，图2 1 ( a ) 示出了o c s v m 的在高斯核下的分类面。我们 将在第三章中详细介绍单类支持向量机。 支持向量数据描述( s v d d ) f l o 】同样是一种经典的基于s v m 的方法，它分成两个过程，训 练过程寻求一个包含所有训练数据的半径最小的超球( 高维空间中的球体) ，通常称作最小闭球， 测试过程判断测试样本是否在学习得到的超球内部，如果是则表明是正常样本，否则就判断为 异常样本。与s v m 、o c s v m 类似，s v d d 同样引入了松弛变量，对所有样本完全落入超球内 部的条件进行了松弛。通过核映射，s v d d 可以找到一个特征空间中的最小闭球，如图2 1 ( b ) 是高斯核下s v d d 得到的分类面。 需要指出的是，虽然单类支持向量机和支持向量数据描述的表示形式不同，出发点也不完 全一样，但s c h 6 1 k o p f 已证明，两者在高斯核下是等价的【引。 o c s v m 和s v d d 已在实践中得到了较优的分类性能，但两者同样也存在了很多问题，学 者们针对这些问题提出了众多改进算法，主要分为以下儿类： 5 非平衡类的异常检测研究 ( a ) o c s v m 取高斯核时的 最优超平面 ( b ) s v d d 取高斯核时的最 小超球 图2 1o c s v m 和s v d d 在高斯核下的最优超平面 l 、结构信息： o c s v m 和s v d d 都存在一个明显不足，即均未考虑数据的类内结构信息。前者只找到一 个离原点最远的超平面，并没有考虑数据的类内结构；而后者总是用超球去包围数据，也没有 照顾到数据结构，比如当数据原本服从椭球分布时，显然用球包围并不紧致。 l a n c k r i e t 1 2 】提出的单类最小化最大概率机( s i n g l ec l a s sm i n i m a xp r o b a b i l i t ym a c h i n e ， s c m p m ) 引入了概率约束，目的是期望在最坏情况下也有一定比例的数据落入正常区域，它 寻求在马氏距离( m a h a l a n o b i sd i s t a n c e ) 下原点到与之最近点的距离最大时所对应的超平面， 这一方法使优化过程更简单，但同时失去了原始o c s v m 的稀疏性。同样，t s a n 9 1 1 3 】用马氏距 离取代了o c s v m 原始的欧氏距离，充分利用了数据的分布信息，得到一个结合结构信息的超 平面。 针对s v d d ，主要的改进思想是结合数据类内结构，用超椭球取代s v d d 中的超球。最小 体积包围椭球( m i n i m u mv o l u m ee n c l o s i n ge l l i p s o i d ，m v e e ) 1 4 】就是这样一种思想，它将样本 包围在一个单位椭球中，但m v e e 并不能核化，故其适用范围存在局限。最小体积覆盖椭球 ( m i n i m u mv o l u m ec o v e r i n ge l l i p s o i d ，m v c e ) 【1 5 】克服了i v l v e e 的缺陷，它并没有约束覆盖椭 球为单位椭球，作者通过迭代方式寻找最优的超椭球，通过主成分分析( p r i n c i p a lc o m p o n e n t a n a l y s i s ，p c a ) 将原始问题进行了核化。然而，当原始分布并不是服从一个椭球分布，而是服 从多个椭球分布时，m v c e 又变得不再合适，w a n g 1 6 1 根据该情形提出了结构化单类分类器 ( s t r u c t u r e do n ec l a s sc l a s s i f i c a t i o n ，1 d c c ) ，它将每个簇都用一个最小体积超椭球包围。 2 、鲁棒性 s v m 有一个很明显的缺点，即鲁棒性不强，其主要归咎于s v m 使用铰链损失( h i n g e 1 0 s s ) 。 铰链损失根据每个样本点到超平面的距离给出相应惩罚，故噪声点通常会得到很大惩罚而严重 6 南京航空航天大学硕士学位论文 影响了分类面的构造。s o n g 等人【18 】对h i n g e - l o s s 的缺陷进行了改进，考虑了样本点和类中心的 距离，对于那些距离类中心很远的样本点不予惩罚，即将它们视为噪声，这样有效减小了噪声 对分类平面的影响。o c s v m 也使用了h i n g e 1 0 s s ，所以也存在同样问题，一些对s v m 鲁棒性 的改进同样可用到单类问题中。x u 1 7 1 提出了一种鲁棒的支持向量机的同时，将这种方法直接用 到了异常检测中。它给予每个点的h i n g e 1 0 s s 一个权值，同时规定噪声点在所有样本点中的比 例，那些对分类平面影响较小的点，就视为噪声点。另外，在o c s v m 的基础上，y a r l k o v 2 7 通过混合因子分析加入了局部信息。利用混合因子分析可减小野值点对超平面影响这一优势， 引入局部信息，增强了o c s 鲁棒性。 3 、用户需求 鉴于单类分类问题的广泛应用，单类算法的设计通常需考虑用户和应用需要。比如医疗检 测，实际情况要求我们不允许出现漏检，也就是当疾病出现时，必须及时发现，以免造成重大 医疗事故而危及患者生命。而对于另外一些应用，如垃圾邮件检测，误警可能会导致一些重要 邮件的丢失，故邮件过滤不允许过滤正常邮件。这些实际情况在以上部分算法中并未考虑。最 近，w u 6 】等人考虑了用户和应用需求，在分类器的设计中引入了用户需求。该方法在o c s v m 基础上考虑了类间间隔最大化，通过参数设置可适应用户对误警率的需求，并已被用到了邮件 检测中。 2 2 2 统计为基础的方法 统计为基础的方法是一类古老而又重要