（计算机软件与理论专业论文）单类分类器研究及其在击键认证系统中的应用实现.pdf

南京航空航天大学硕士学位论文 摘要 单类分类器是不同于传统模式识别的一种机器学习方法，传统模式识别方法一般 需要多个类别的样本( 至少两个) ，而在有些场合中，几乎无法获取多类的样本，或 者获取其样本所需花费的代价非常高，比如：机器故障中我们不可能为了去获得故障 样本而让机器特意产生故障：又有些场合的类别样本个数严重不平衡，比如医学上的 疾病特征与非疾病特征的比例是严重不平衡的。对于这些问题，都比较适宜采用单类 分类方法。本文在分析探讨了三种单类分类方法之后，并侧重对c a m p b e l l 与b e n n e t t 的基于线性规划的新颖性检测方法进行了推广，提出了一个相应的加权方法，并在真 实数据集上对这些方法进行比较，该加权方法可以获得更好的分类性能。最后，将单 类分类方法应用于计算机的击键登录认证，并且集成到w i n d o w sn t 系统的登录认证 系统，使击键认证趋向实用化。 关键词：模式识别；生物认证；单类分类器：击键特征：支持向量机；核方法；安全 控制 兰耋坌耋墅堕壅墨基垄童塑坠堡墨竺! 塑壁旦兰翌 a b s t r a c t o n ec l a s sc l a s s i f i c a t i o ni sam a c h i n el e a r n i n ga p p r o a c hd i f f e r e n tf r o mt h et r a d i t i o n a l p a a e mr e c o g n i t i o na p p r o a c hw h e r et w oo rm o r ec l a s ss a m p l e sa r er e q u i r e d h o w e v e ri n s o m er e a l l i f ec a s e s ，w ec a nh a r d l y , e v e nn o t ，g e tt h es a m p l e so fs o m ec l a s s e s ，o rh a v et o p a yc o s t l yp r i c e t oo b t a i nt h es o n e e d e d s a m p l e s ，s u c h a si nt h ec a s eo fm a c h i n e r y m a l f u n c t i o n a n dw h i l ei no t h e rc a s e s ，t h es i z e so fs a m p l e sa m o n gc l a s s e sa r ei m b a l a n c e ， s u c ha sm e d i c a ld i a g n o s i s a l lt h e s ep r o b l e m sa r es u i t a b l ef o ro n ec l a s sc l a s s i f i c a t i o n a p p r o a c h i nt h i sa r t i c l e ，a f t e ra n a l y z i n gt h r e et y p i c a la p p r o a c h e so f o n e c l a s sc l a s s i f i e r s ， w ef o c u sm u c ho nag e n e r a l i z a t i o no fc a m p b e l la n db e n n e t t sl i n e a r p r o g r a m m i n g b a s e d o n e c l a s sc l a s s i f i c a t i o n a p p r o a c h t o n o v e l t yd e t e c t i o n ，a n d e x t e n di tt oa w e i g h t e d f o r m u l a t i o n ，t h e np e r f o r ms o m ee x p e r i m e n t so nt h er e a ld a t a s e t s t h er e s u l t ss h o w t h a tt h e n e wa p p r o a c hg e t sb e t t e rp e r f o r m a n c ec o m p a r e dt ot h eo r i g i n a lc o u n t e r p a r t a tl a s t ，w e i n t e g r a t et h eo n ec l a s sc l a s s i f i c a t i o na p p r o a c ht o t h ew i n d o w sn t l o g o na u t h e n t i c a t i o n s y s t e m t or e a l i z ea p r a c t i c a l l y u s e f u l k e y s t r o k e a u t h e n t i c a t i o n s y s t e m w i t h h i 曲 p e r f o r m a n c e k e y w o r d s ：p a r e r nr e c o g n i t i o n ；b i o m e t r i ca u t h e n t i c a t i o n ；o n ec l a s sc l a s s i f i e r ；k e y s t r o k e f e a t u r e ；s u p p o r tv e c t o rm a c h i n e ；k e r n e lm e t h o d ；s e c u r i t y c o n t r o l i i 南京航空航天大学硕士学位论文 1 1 什么是单类分类器 第一章前言 单类分类是一种较为特殊的模式分类问题【5 7 】。在单类分类问题中，我们需要做 出的判断是某个模式属于或者不属于单个类别。我们把这个较为特殊的类别以及区分 该类别的模式类分别叫做正常类和异常类【5 - 8 】。 正常类 5 】：该类别的模式样本一般被认为是具有某个分布，而且用于训练单类分 类器的样本也全部来自该类别。训练样本集不一定需要严格满足正常类的样本分布， 但是训练样本集至少可以反映出正常类的区域分布。 异常类 5 】：该类别的样本分布未知，也有可能是该类别的样本很难获取或者是 要付出较高的代价才可以获取到。单类分类器不对该类别中的样本进行训练，只是在 判断时鉴别出新样本是否属于正常类( 不属于正常类即意味着属于异常类) 。 如果把正常类看成一个集合，那么异常类就恰好是正常类的补集。由于训练样本 仅仅束取自正常类，因此这种分类器被称作为单类分类器【5 】。 比如我们要对苹果和梨子进行分类 5 】，那么我们就遇到了一个两类分类问题，该 问题可以用多种常用模式识别方法解决。接着如果我们需要处理其前提问题，就是判 断一种水果是否属于苹果和梨子组成的集合，这就产生了一个单类分类问题。在这个 新问题中，我们需要判断的是种水果究竟是属于还是不属于苹果和梨子这个类别。 该问题与前面的两类问题的区别在于：在训练阶段，我们可以获得很多的苹果和梨子 样本，但是不管我们怎么获取其他水果的样本，都是不足以表达异常类的分布( 我们 不可能把世界上所有除开梨子和苹果的水果都罗列出来) ，或者说异常类根本就不存 在某种分布。这就形成了一个单类分类问题，而对于两类分类问题，苹果和梨子的训 练样本我们可以提供很多。 本文中的击键认证就是适合单类分类处理的问题，对于个人来说，其击键模式是 容易获取的；而我们根本无法获取他人击键模式所形成的异常类中的样本来满足异常 类的分布情况。 1 2 生物认证与击键认证的现状 生物特征认证技术是通过计算机利用人体固有的生理特征或行为特征来进行个 人身份的鉴定。人的生理特征与生俱来，多为先天性的；行为特征则是习惯使然，多 位后天性的。生理和行为特征统称为生物特征，常用的生物特征包括人脸、虹膜、指 纹、掌纹、声音、笔迹、步态、颅骨、击键行为等。 单类分类器研究及其在击键认证系统中的应用实现 根据i b g ( 国际生物集团) 的统计，到2 0 0 5 年年底，全球生物特征认证技术市 场规模将达到2 2 亿美元 2 】。同时，市场每年将以超过8 0 的速度快速增长。随着生 物认证技术的成熟、应用面的扩大以及时间的推移，这个数字有望达到数千亿美元。 其主要应用领域包括：机场旅客控制、政府部门、门禁和考勤、法律执行、消费者管 理系统、金融管理服务系统、计算机登录管理、医疗保健系统等。 图1 12 0 0 2 2 0 0 7 年全球生物市场增长预测f i b g ) 国内生物认证识别技术的应用主要集中在比较分散、自发性的企业级应用上，在 2 0 0 2 年总体约为2 5 亿元人民币的终端系统中，超过4 0 的产品都用于低端考勤、门 禁系统。在行业应用方面，a f i s ( a u t o m a t i cf i n g e r p r i n ti d e n t i f i c a t i o ns y s t e m ，自动指 纹识别系统) 超过了4 0 。其他应用零散分布在金融、社保、政府等领域。 i b g 的市场报告显示在2 0 0 2 年各种技术市场份额中，指纹识别技术占据了近5 2 的份额。而本文所采用的击键特征只占了o 3 的份额。虽然在目前来说，这个份额 是非常少的，但是在电子商务领域，由于密码的检验不再仅仅限于单纯的密码，还包 括了用户的击键行为，因而其可靠性大大的提高。对于网络上用户的认证以及计算机 的登录认证管理都是非常有用的。 利用键入特性进行身份认证的优点是非常明显的，因为无论如何用户通常总是要 通过键盘进行输入，所以用户注册和身份确认的过程并不会干扰到他们正常的工作。 并且输入设备是已经存在的键盘，这项技术的开销非常低，只须在系统中嵌入相应的 软件即可。所以将口令与键入特性结合起来进行身份验真的技术得到国外很多学者的 重视，他们为此做了大量研究工作，并且出现了与之相关的商业产品，如美国n e t n a n n y 公司的b i o p a s s w a r d 3 1 。 塑塞堕窒堕鲞盔堂堡主堂些堕墨 图1 22 0 0 3 年各种识别技术相对市场份额( 不包括a f i s 系统) 采用用户的击键行为对用户进行认证，可以保证在用户的密码失窃之后，仍然有 一定的防护作用。最重要的是，可以提高用户在电子商务行为中的可靠性，用户失窃 的信用卡等也可以获得更多的保护措施。人们在很早就开始了击键行为的研究，1 8 9 5 年，通过对发报员的观察表明，每一个发报员发送相同的一段报文都有其唯一的击键 模式，后来接线员经常通过简单地监听点击的声音，就能辨认出发报员是谁 4 】。这 些都告诉我们，击键特征是可以作为人的一种可靠的行为特征来辅助认证的。 1 3 本文的主要研究内容 本文的主要研究内容： 1 本文在分析探讨了三种单类分类方法之后，并侧重对c a m p b e l l 与b e n n e t t 的基于线性规划的新颖性检测方法进行了推广，提出了一个相应的加权方 法，并在真实数据集上对这些方法进行比较，该加权方法可以获得更好的 分类性能。 2 本文将单类分类器模型应用到击键认证上，并且将其与w i n d o w $ n t 登录 认证系统集成起来，将击键认证实用化。 在第二章讲述目前主要的单类分类器，并且对他们做比较实验。第三章提出一种 加权方法，阻及该方法与其他方法的比较。第四章讲述如何在w i n d o w sn t 系统中集 成击键认证系统，我们提供了训练程序以及认证程序，并且在各方面进行了效果测试。 第五章我们对m a t l a b 的应用程序接口做一个简单的了解，并且比较多种不同方法的 区别。最后，我们在第六章对将来要继续的工作做一个简单的说明。 3 单类分类器研究及其在击键认证系统中的应用实现 第二章常用单类分类器 2 1 单类分类器的适用范围 单类分类器由于其特殊性，一般可以用于解决如下问题： 1 类别样本数目不平衡问题：比如两个训练类别中的样本数目比例高至9 ：1 ： 2 异常类样本获取代价高问题：比如某些故障诊断，要获取故障样本所付出的 代价太高，我们不可能为了获取故障样本而特意让机器出现故障； 3 异常类样本数目几乎无穷问题：比如既不是苹果也不是梨子的水果多得数不 清，根本就不清楚该拿哪些水果样本来训练。 由于单类分类器只训练正常类的训练数据，因此在解决方法上不同于传统的两类 ( 或者多类) 分类问题。在单类分类问题的错误率监测上，存在着两个标准：j 下常类 错误率与异常类错误率。这两个错误率是相关的，正常类错误率高的往往导致异常类 错误率低，反之亦然。因此，在最后评价一个单类分类器的性能，我们应从这两个方 面综合考虑。 单类分类方法同样可以用于野值与新颖性的检测，在这种场合，野值与新颖值被 看作成异常类数据。 这一章将介绍一些常用的单类分类方法，而且这些方法中几乎都用到了核函数与 支持向量，我们先介绍这个内容，接着介绍支持向量数据描述方法( s u p p o r tv e c t o r d a t a d e s c r i p t i o n ) 【5 ，单类支持向量分类器方法u s v c ( u s u p p o r t v e c t o r c l a s s i f i e r ) 【6 以及采用线性规划的新颖性检测方法 7 】。 2 2 支持向量机与核函数 支持向量机( s v m ：s u p p o r tv e c t o rm a c h i n e ) 是统计学习理论( s l t ：s t a t i s t i c a l l e a r n i n gt h e o r y ) 【8 中提出的一种新的模式识别方法，他们从9 0 年代以来受到很大 的重视，主要是由于它们对小样本情况下模式识别中的一些根本性问题进行了系统的 理论研究。传统统计模式识别方法都是在样本数目足够多的前提下进行研究的，而支 持向量机能够较好的解决小样本学习问题，并且通过核函数映射到高维特征空间，可 以在不增加运算成本的情况下较好地解决线性不可分问题。以往很多困扰机器学习方 法的问题，比如模型选择与过学习问题、非线性和维数灾难问题、局部极小点问题等， 在很大程度上都可以通过支持向量机加以解决。 塑室堕皇堕墨盔堂堕主堂堡堡苎 一 图2 1 最优分类面示意图 s v m 是从线性判别函数【8 】引出，其基本思想可以概括为：首先通过非线性变换 将输入空间变化到一个高维空间，然后在这个新空间( 高维空间) 中求取最优线性分 类面，而这种非线性变换是通过定义适当的内积函数实现的。 对于线性可分情形是通过在两类样本间构造一个最优分类面( o p t i m a l h y p e r p l a n e ) 。考虑图2 1 所示的二维线性可分情况，图中实心点和空心点分别表示两 类的训练样本，h 为把两类没有错误地分开的分类线，h i 、h 2 分别为过各类样本中 离分类线最近的点且平行于分类线的直线，h l 和h 2 之间的距离叫做两类的分类空隙 或分类间隔( m a r g i n ) 。最优分类线就是要求分类线不但能将两类无错误地分开，而且 要使两类的分类空隙最大，推广到高维空间，最优分类线就成为最优分类面。 设线性可分样本集为0 。儿l i = 1 ，”，x r “，y “1 ，一1 是类别标号。d 维空间 中线性判别函数的一般形式为： g b ) = w x + 6 ， ( 2 1 ) 分类面方程为： w x + b = 0 ，( 2 2 ) 将判别函数进行归一化，使两类所有样本都满足k g 】1 ，即使离分类面最近的 样本的k 0 】= 1 ，这样分类间隔就等于2 州w 因此使间隔最大等价于使m l ( 或州1 2 ) 最小；而要求分类线对所有样本正确分类，就是要求它满足： y 。【( w x ，) + 6 卜1 0 ，i = 1 , 2 ，珂， ( 2 3 ) 因此，满足上述条件且使m l2 最小的分类面就是最优分类面。过两类样本中离分 类面最近的点，且平行于最优分类面的超平面h l 、h 2 上的训练样本，也就是式( 2 3 ) 中使等号成立的那些样本，它们叫做支持向量( s u p p o r tv e c t o r ) 。因为它们支撑了最优 分类面，如图2 1 中用圆圈标出的点所示。 5 单类分类器研究及其在击键认证系统中的应用实现 求最优分类面的问题可以表示成如下的约束优化问题，即在条件( 2 3 ) 的约束下 求函数 。( w ) = 扣j 2 = j 1 ( w w ) ， t 的最小值。为此，可以定义如下的l a g r a n g e 函数： 中( m 6 ，口) = 三一w ) 一喜q 扣爪w q ) + 6 】一 ， cz s 其中口， 0 为l a g r a n g e 系数，问题转化为对w 和b 求l a g r a n g e 函数的极小值。 把式( 2 - 5 ) 分别对w 和b 求偏微分并令它们等于0 ，就可以把原问题转化为如下这 种较简单的对偶问题：在约束条件 邶，= 0 ， ( 2 - 6 a ) 之下对a 求解下列函数的最大值 若口为最优解，则 口20 ，i = 1 ，一，n q 如) = a ，一寺叩玛b i - l i , l = 1 w + = 口。y ，z ， ( 2 8 ) 一 ，= l 即最优分类面的权系数向量是训练样本向量的线性组合。 这是一个不等式约束下二次函数极值问题，存在唯一解。且根据k u h n t u c k e r 条 件，这个优化问题的解须满足 口。0 。 x 。+ 6 ) 一1 ) = 0 ，i = 1 ，一，” 因此，对多数样本口。将为零，取值不为零的口，对应于式( 2 3 ) 等号成立的样本即支持 向量，它们通常只是全体样本中的很少一部分。 求解上述问题后得到的最优分类函数是 几) = s g l l ( w z ) + 6 = s g l l o q * y ，x ，x ) + 6 ， ( 2 _ 9 ) ，、i h l lj = ij 由于非支持向量对应的口，均为0 ，因此式中的求和实际上只对支持向量进行。而 南京航空航天大学硕士学位论文 b 为分类器的域值，可以由任意一个支持向量用式( 2 - 3 ) 求得( 因为支持向量满足其中 的等式) ，或通过两类中任意一对支持向量取均值求得。 在线性不可分的情况下，就是某些训练样本不能满足式( 2 3 ) 的条件，因此可以在 条件中增加一个松弛项亭，0 ，变成： y 。【( w x ，) + 6 卜1 + 毒，0 ， 2 1 0 ) 对于足够小的盯 0 ，只要使 c 瞎) = 董。， ( 2 _ i i ) 最小就可以使错分样本数最小。对应线性可分情况下的使分类间隔最大，在线性不可 分情况下可引入约束 2 c 女， ( 2 1 2 1 在约束条件( 2 1 0 ) 和( 2 1 2 ) 下对式( 2 1 1 ) 求极小，就得到了线性不可分情况下的最优分 类面，称作广义最优分类面。为计算方便，这里取叮= l 。 广义最优分类面问题可以进一步演化为在条件( 2 1 0 ) 的约束下求下列函数的极小 值： 由( w ，手) = 毒( w w ) + c f 皇， ( 2 - 1 3 ) 1，n、 其中c 为某个指定的常数，它实际上起着控制错分样本惩罚程度的作用，实现在错分 样本的比例与算法复杂度之间的折衷。 用与求解最优分类面时同样的方法求解这一优化问题，同样得到一个二次函数极 值问题，其结果与可分情况下得到的式( 2 6 ) 式( 2 9 ) 几乎完全相同，只是条件( 2 6 b 1 变为 0 口。c ，i = 1 ，”，( 2 - 14 ) 上面讨论的最优和广义线性分类函数，其最终的分类判别函数( 2 9 ) 中只包含待分 类样本中的支持向量内积运算g - 一) ，同样它的求解过程式( 2 6 ) 式( 2 _ 8 ) 中也只涉 及训练样本之间的内积运算0 t ) ，可见要解决一个特征空间的最优线性分类问题， 只需要知道这个空间中的内积运算即可。 如果用内积丘b ，工) 代替最优分类面中的点积，相当于把原特征空间变换到了某一 新的特征空间，此时式( 2 7 ) 的优化函数变为： 单类分类器研究及其在击键认证系统中的应用实现 q 缸) ：芝“一丢窆口。口，只y ，k b 。x ，) ， cz t s ) 而相应的判别函数式( 2 9 ) 也应变为 ，g ) = s g n a 。y ，足b ，x ) + b ， ( 2 _ 1 6 ) 算法的其他条件不变。这就是支持向量机。 根据h i l b e r t - s c h r a i d t 原理，只要一种运算满足m e r c e r 条件，它就可以作为这里 的核函数使用。m e r c e r 条件为：对于任意的对称函数k ( x ，x ) ，它是某个特征空间中 的内积运算的充分必要条件是，对于任意的妒( x ) 0 且陆2 0 0 ) 出锄，有 f l x ( xx 如g 如0 池 0 。常用的的核函数有多项式核函数上g ，y ) = ( 1 + z y ) “， g a u s s i a n 舳f 核函数m 小e x - 卜譬l 和s i g m o i a 核函数 k ( x ，y ) - - t a n h 【6 g - ) ，) 一c 】。 从支持向量机的基本思想可以看出，s v m 对线性情况和非线性情况的处理方式 是一致的，而且在性能上，由于核函数仅仅是一个内积函数，不会增加太大的运算代 价。传统的模式识别方法，对于非线性问题和维数灾难问题，都显得力量不足。 2 3 支持向量数据描述方法( s v d d ) 支持向量数据描述方法( s v d d ：s u p p o m v e c t o rd a t a d e s c r i p t i o n ) 是由d a v i d t a x 等人提出的一种单类分类方法【5 】。s v d d 的基本思想是：首先通过核函数将输入空 间映射到一个高维空间，在这个高维空间构造一个包含所有训练样本点的球体：在球 面上的样本点即为s v d d 所求得的支持向量( 因为这些样本点就可以支持这个球体 的形成) 。同s v m 的原理相仿，支持向量所对应的系数大于0 ，而所有的其他样本点 对应的系数等于0 。而且支持向量的个数是稀疏的，因此计算量得到相应的减少。 假设模型f ( x ；w ) 表示一类紧密的有界数据集，因此我们可以借助一个超球体去包 含并描述它。这个球体可以用中心a 和半径r 表示，而且使训练集x ”的所有样本都 落在此球体内。这就表示经验风险等于0 ，因此，类比于s v m 8 ，定义个结构误 差： f p w ，( r ，d ) = r 2 ， ( 2 1 7 ) 在如下的约束下对它最小化： 南京航空航天大学硕士学位论文 忙一a l l 2 r2 ，vi，(2-18 ) 由于训练样本中一般含有噪声或野值( 也叫新颖值) ，因此上述优化结果对噪声 或野值敏感，缺少鲁棒性。为提高结果的鲁棒性，仿照s v m 为每个样本引入松弛变 量专0 ，v i ，以控制野值对解的影响。意即对于远离球心的样本点实施惩罚，因此， 最小化问题变为如下形式： 占。( r ，a ，告) = r2 + c 掌。，( 2 - 1 9 ) 其约束条件为： j | z ，- a l l 2s r 2 + 皇，专o ，v i ，( 2 2 0 ) 参数c 类似于s v m 中的控制变量。 为求解上述约束下的最小化问题。x , j - ( 2 - 1 9 ) 、( 2 - 2 0 ) 定义如下的l a g r a n g e 函数： l ( r ，口，眚，口，y ) = r2 + c ， 一口， r2 + 孝，一( x ，工，一2 d ，石，+ 口口) ) 一y 孝，2 2 1 r ， 这里l a g r a n g e 乘子口。o ，一0 ，葺z ，表示z 。和x ，的内积。对于每一个样本点石，都 定义了一个相应的口。，。l 相对于r ，口，掌来说是做最小化，而相对于a ，y 则是最大化。 求其偏微分并令它们等于0 ，得到约束为： a ，= 1 ， ( 2 2 2 ) 口= 即， ( 2 2 3 c a 一一= o ，v ，( 2 - 24 ) 最后一个约束( 2 2 4 ) n - j 化简为如下的约束： 0 口，c ，v ，( 2 25 ) 将上述公式( 2 2 2 ，2 - 2 3 ，2 - 2 4 ) 代入( 2 - 2 1 ) ，经代数运算后，获得原有问题的最后表 示l ： l = a ，( x ，x t ) 一口，口j ( t x ，) ， ( 2 2 6 ) 约束为( 2 2 2 ) ，( 2 - 2 s ) 。 对上述问题相对口求最大，可以用标准的二次规划算法来解决。这样就可以求得 a 的最优值，对于非0 的a ，其对应的样本点是支持向量，位于球面上；而口；：o 则 表示对应的样本点位于球体内。在这里并没有显式表出a 和r ，它们可以用a 隐含表 9 单类分类器研究及其在击键认证系统中的应用实现 出。 假设z 为测试样本，那么当如下公式满足，即判z 是正常类，否则为异常类。相 当于z 落在该超球体内部。 | | z 一f | 2 = ( ：z ) 一2 口。( z z ，) + 口，口( x ，x j ) 玉r 2 ，( 2 2 7 ) 其中，r 是任意一个支持向量x k 到球心a 的距离： r 2 = ( x z 女) 一2 口，( x ，j t ) + a ，口，( x ，x ) ，( 2 2 8 ) 将( 2 - 2 8 ) 代入( 2 2 7 ) 可得： 兀。( = ；a ，r ) = ，( j | ：一口l i 2 r 2 ) ：，f ( ；：) 一2 z 口，( ；。，) + 口，口，( ，。，) 尺z1 2 2 9 f ， 这里指示函数i 定义为： i f a i s t r u e o t h e r w i s e 当输入空间的样本点不满足球状分布时( 比如香蕉状分布) ，可以通过类似于s v m 的核技巧把输入空间先映射到高维空间，然后在映射后的高维空间内求解。也就是将 上述公式中的内积形式都变换成核函数形式： x f x j 矽( x ) 庐( z j ) = k ( x ，x j ) ， ( 2 3 1 其中为非线性映射，对于某些核函数可以显式的求出矽，而绝大多数则难以表出。 选择个适当的核函数也是比较重要的，如果选取的核函数能够将输入空间正好 映射成高维空间的一个球体分布，那么所求得的分类器也会比较吻合实际的分布情 况。关于核函数的选取也可以参考【5 】。 引入核函数后，原来的公式变成了如下形式： = 口，k ( x ，x ) 一口aj k ( x ，xj ) ， ( 2 3 2 ) i i ， 约束不变，而决策函数变为： j ，( z ；a ，尺) = ，( 8 庐( z ) 一庐( 口) | | 2 r2 ) 厂、。( 2 3 3 ) = 1 1 足( 即) 一2 口，x ( z ，t ) + d ，a ，k ( x ，) r 21 2 4 单类支持向量分类器v - s v c s c h 6 l k o p f 提出了另一种y s 阳支持向量分类方法【6 ，主要目的是为进一步推广 南京航空航天大学硕士学位论文 s v m ，。冥基本思想是：首先将输入空间通过核函数映射到两维空侧，在高维空【剧将 它们与原点尽可能地分开。对于测试样本x ，f i x ) 表明了它在高维空间位于超平面的 哪边。f ( x ) 为1 的认为是e 常类，1 认为是异常类。 要将数据集从原点尽可能的分开，我们解决如下的= 次规划问题： 。，襞嚣。扣国1 1 2 + 击；孝，一p ，( 2 - 3 4 ) j t ( 0 9 ( z ，) ) p 一善。，毒，0 ，( 2 - 3 5 ) 这里的参数v ( 0 , 1 的意义将在后面讨论。 由于非0 松弛变量善，是对目标函数的惩罚，我们认为如果6 0 和p 能够解决这个问题 那么决策函数： f ( x ) = s g n ( ( c o ( x ) ) 一p ) ，( 2 - 36 ) 对训练样本集中的绝大部分样本x i 都为正，而蚓i 仍然保持最小。它们之间的折衷参 数就由v ( 0 ，i 控制。 为了求解上述公式，引入l a g r a n g e 乘子： 上( 怎p ，口，) 2 扣珊l l2 + 吉莩善，一p 一军a l ( ( 庐( t ) ) 一卢+ 射一；卢点，( 2 - 3 7 ) 对，孝，p 求偏导并令其等于0 ，得出： = q ( ) ， ( 2 3 8 ) 铲土v 一口 击，；铲，( 2 - 3 9 ) 公式( 2 - 3 8 ) 中求出的所有b ：f 【珏口， o ) 就是支持向量。将映射毋变换为核函数 后，决策函数就是如下形式： m ) _ s 弘阵啦( x ，, x ) - p ， 限删 l 将( 2 3 8 ) 减去( 2 3 9 ) 并代e k ( 2 3 7 ) ，可以得到如下的二次问题： 单类分类器研究及其在击键认证系统中的应用实现 哑n 吉叩，k ( x ，, x j ) 。j ， “o 钮s 去，；铲， 在最优化后，可以看到原来的不等式约束( 2 3 5 ) 变成了口，都非0 时的等式 约束。由于支持向量是位于超平面上，我们由此可以从某个支持向量x 及其对应的口 求出p ： p = ( 甜庐( x ，) ) = a ，女( x ，一) ， ( 2 4 2 ) 注意到当y 逼近0 时，l a g r a n g e 乘子的上界趋向于无穷大，约束( 2 - 4 1 ) 中的第 2 个不等式就变得没有意义。从( 2 3 4 ) 中可以看出，由于误差惩罚项变得无穷大， 问题就类似于相应的“硬边界”算法。 同样，也可以把高维空间的样本点约束到一个球内，这与t a x 和d u i n 的方法 5 有相似之处。此时，把绝大部分的样本点约束到一个球内： 。哩粤一r 2 + 专专 尺e 婀， e 州，c e fw s t i f ( t ) 一c 1 2 r 2 + 专，毒- 0f o ri e ，( 2 4 3 ) y ( o ，1 ) 这可以推出如下二次问题： 叫n q q k ( x t , x j ) 一q 七( 一) ， ， ( 2 4 4 ) “0 i 1 ，q = 1 w 以及球心可以表示为： c = 口。地) ，( 2 - 4 5 ) 决策函数为如下形式： 厂、 厂( x ) = s g n lr2 一口，口，k ( x ，z ，) + 2 a 。t ( x 。，z ) 一k ( z ，：) i ( 2 46 ) u 同样的，r 2 可以从某个支持向量x 及其对应的口求出。 由于核函数k ( x ，y ) 仅仅依赖于x y ，因此k ( x ，x ) 是一个常量。因此，这就意味着二 次目标函数中的线性项是常量，所以问题( 2 - 4 4 ) 与( 2 4 1 ) 是等价的。这就是说， 对于常量k ( x ，x ) ，所有的样本都映射到高维空间的一个球体内。因此，寻找体积最小 南京航空航天大学硕士学位论文 的球体实际上相当于寻找包裹数据的球表面的一个切片。而这个切片可以很直接的通 过一个穿过球体的超平面求得。这个超平面就是离原点最远的一个最优分类面。这也 就是为什么两者可以等价的原因。 2 5 采用线性规划算法的新颖性检测方法 由于上述两种方法的求解都需要用至r j - - 次规划，其复杂度较高；c o l i nc a m p b e l l 等提出了一种采用线性规划算法的新颖性检测方法【7 】，问题求解的复杂度变成了线 性规划算法。该方法与v s v c 有一定的相似之处，其基本思想也是在高维空间寻找 一个最优分类面。 假设输入空间的样本为x i ( i _ 1 m ) ，映射函数为x 寸( x ，) ，那么在高维空间， 我们可以得到权向量的形式为w = a ，声( x ，) 。因此定义w - 庐( x 。) + b = 0 为高维空间 的分类面。同样可以知道，分类面的一边为正，另一边为负。由此决策函数可以定义 如下： 厂、 s g n ( w ( ：) + 6 ) = s g n i d ( j ，) ( z ) + bf ， ( 2 4 7 ) l ， 同样的，映射的内积形式可以替换成核函数： s g n ，k ( x ，：) + 6i，(2-4 8 ) j 该方法有硬边界与软边界之分。对于硬边界方法，要保证所有的训练样本点都在 超平面的一侧。而软边界方法，则允许有个别样本点位于超平面的另一侧( 这些样本 点可以称为野值或新颖值) 。 对于硬边界方法，目的是在输入空间找到一个包裹所有训练样本点的表面，所有 在这个边界之外的样本都被认为是异常类别。这个表面可以定义成某种非线性函数形 式：f ( z ) 2 0 。而在高维空间对应的就是超平面，( z ) = 。a ，k ( z ，x ，) + 6 ，这个超平面与 训练样本点的映射紧紧的靠在一起，并且对于所有的训练样本点，其值都大于或等于 0 。通过最小化输出函数f ( z ) 的均值，来实现超平面与样本点映射紧凑这个目标。因 此，其可以表示为如下形式： _，。、 矽( a ，6 ) = i a ，k ( x ，) + b ， ( 2 49 ) 2 ，= ， 约束为： 单类分类器研究及其在击键认证系统中的应用实现 口j k ( x ) + b 0 ，( 2 - 5 0 ，= i 口，= 1 ；口0 ， 【2 一s 1 ) 如果在实际训练样本数据中包含了噪音和野值，这可以通过软边界方法最小化如 下函数来解决： w ( 口，b ) = i 口，k ( ，j ，) + bl + s ，t ( 2 5 2 ) = l j = i l = 1 约束为： 口j k ( x ，zj ) + b 一，；0 ，( 2 - 5 3 ，= i 以及约束( 2 5 1 ) 。 参数丑用来控制误差程度( 越大意味着忽略的野值越少，五- - - 9 c 。相当于硬边界 方法) 。 这个问题可以很容易的通过线性规划的单纯型或者内点算法求解。 南京航空航天大学硕士学位论文 第三章加权单类分类器 第二章中所讲的单类分类方法，对所有的训练样本都是一致对待的，即把所有样 本对分类器的贡献看成是一样的。比如s v d d 方法，所构造的高维空间的超球体， 离球心越远的样本对分类器的贡献越大。对于其他的几种方法，都有类似的样本对分 类器的贡献不同这一问题。 因此我们可以对每个样本点取不同的权值用于训练，表示该样本点的贡献大小。 在上述方法的基础上，我们对c o l i nc a m p b e l l 的新颖性检测方法研究了一种加权形式， 采用不同的加权函数对两者的区别进行实验上的性能比较。 3 1 采用线性规划算法的加权方法 加权方法的主要思想就是考虑训练样本对整个训练过程贡献的不同，比如：离核 球体中心近的样本我们认为其贡献大。在每个样本上乘以一个权函数来实现加权过 程。 公式( 2 - 4 9 ) 的加权形式为： 口，u ( x f ) k ( z ，x ，) + b 0 j - 【 c t ，= 1 ；o r 0 ， 一 ，= 1 其中( x ) 是所采用的权函数，权函数可以为多种形式，比如 或者 一叫 4 x ) = e 2 。2 3 3 3 4 3 5 ) 等 l 一 3 、 6+ ) k ) ， 口 。川 ，。l 。 nm 毗 本 = ) x (卢 单类分类器研究及其在击键认证系统中的应用实现 其中聊= 去喜t ，即m 为训练样本的均值。同样的，m 可以为中值或者是中值与均 值的混合值。 3 2 训练样本的均值权 l - 当m 2 i 备一时，在权函数中的参数仃可以通过如下方式求得： c r 2 砷摺誓一刊1 2 ( o 删) ， ( 3 _ s ) 把权函数( x ) 核化： l i x m l l 2 竺；i c x ，一喜一c x 。，8 2 2 声似) 烈一詈善( 功( ) + 砉荟再( t ) ( z ，) 1 月 1 月nl j 一，j 圳，一詈善卿，x 小吉善毫z ， 在加权形式的线性规划方法中，需要额外提供的一个参数就是0 r 1 ，这个参 数用来控制通过训练样本得出的方差的大小。 加权思想就是认为每个训练样本对训练过程的贡献是不一样的，这里我们可以看 到如果采用以砷2 i 厦1 作为权函数，就表达了离中心越近的训练向量，其贡 献械女的照樵。 3 3 训练样本的中值权 m 除了取训练样本的均值外，也可以取其为训练样本的中值。由于m 核化之后 无法直接求得中值，可以把求中值转化为求如下的一个最小值对应的训练样本： 南京航空航天大学硕士学位论文 叩慨蕾) 一( 圳 。乏护( 一) 地) + 7 ( 吒) 地) 一2 矿7 ( t ) 妣) 川- 8 ) = 芝肛瓦可磊瓦i f 丽 1 i x - m l l 2 核化后变为： i 陋( x ) 一庐( m ) 1 1 2 = 7 ( x ) 妒( 工) + 庐7 ( 历) ( 研) 一2 妒7 ( x ) 妒( m ) ，( 3 9 3 4 均值与中值的混合 除了采用单一的一种权值外，还可以采用均值与中值两者的混合值，作为权函数 中的参数m 。 3 5 比较实验 厅2 m 2 ：j l n m e “+ 莉脚一加石+ z万+ z 为了比较这几种单类分类方法，我们在3 个数据集上对它们进行比较。由于s v d d 与有比较类似( 在有些情况下，两者是等价的) ，因此我们主要比较了s v d d ，采用 线性规划算法的新颖性检测方法以及加权方法。 3 5 1 实验数据集介绍 血压观测数据集b i o m e dd a t a s e t 3 2 ： 这个数据集包含了1 9 4 个血压观察样本，有2 个类别，每个样本有4 个特征( 去 掉了1 5 个特征值不全的观察样本) 。1 9 4 个样本中，有1 2 7 个正常样本和6 7 个异常 样本。 乳腺癌数据集w i s c o n s i nd i a g n o s t i cb r e a s tc a n c e l 3 3 ： 该数据集为两类，3 5 7 个良性样本和2 1 2 个恶性样本，每个样本3 0 个特征。 甲状腺数据集t h y r o i dg l a n d 3 3 】 单类分类器研究及其在击键认证系统中的应用实现 该数据集共有3 类数据，1 5 0 个正常样本，3 5 个亢奋样本，3 0 个忧郁病患者样本。 每个样本有5 个特征。 3 5 2 总体实验比较 下面我们用实验来比较加权方法与原有的线性规划方法。在实验中我们采用中值 加权，采用的核函数为g a u s s i a n 核： 足( x ，x ，) ：p 一卜j 厅“2 为了比较两种方法对异常数据的分类能力，采用了医学数据集b i o m e d d a t a s e t 3 2 。 我们从正常数据集中随机抽取了7 0 个正常样本用于训练，剩下的5 7 个正常样本和 6 7 个异常样本用于测试。 对于加权方法中的参数玎，我们选择了r = 0 9 。 所有的曲线图其纵坐标为正确分类率，横坐标为核函数参数盯的大小。 图3 1 加权方法与非加权方法对正常数据正确分类率的比较图 南京航空航天大学硕士学位论文 图3 2 加权方法与非加权方法对异常数据正确分类率的比较图 在图3 2 中，我们可以看到，加权方法权对异常类的分类性能比非加权方法稍微 差一点，不过两者的正确率仍让都比较高。从总体效果来看，加权方法有更好的分类 性能 不管采用哪种方法，都会受到核函数参数的限制，因此如何找到一个合适的参数 对于具体应用来说就是一个相当重要的问题。将来的研究可以在如何寻找一个合适的 参数上着手进行深入。这个核参数的寻找需要通过不断的迭代直到找到一个合适的位 置为止。在这个位置上，可以根据需要满足一定的正常数据错分率和异常数据错判率 的比率。 而对于加权方法来说，它要比原有的线性规划方法多一个参数，不过这个参数可 以通过经验值得出，因为从加权思想的直观意义上看，是比较能够容易的确定这个参 数的。 3 5 3 三个数据集的实验比较 下表列出了对3 个数据集做实验比较的情况。 b i o m e dd a t a s e t ：训练样本数为7 0 个。 w i s c o n s i nd i a g n o s t i cb r e a s tc a n c e l ：训练样本数为1 5 0 个。 t h y r o i dg l a n d ：训练样本数为7 0 个。对于两类异常数据合并为一类进行测试。 单类分类器研究及其在击键认证系统中的应用实现 以下数据中所取的的参数r = 0 9 。 盯1 00l lo1 2ol3 o1 4o1 501 6o1 701 8