（应用数学专业论文）机器学习的分类问题中不均衡问题算法研究.pdf

中国农业大学硕士学位论文 摘要 摘要 分类问题中的不均衡问题目前是一个被国内外学者关注的( 相对地) 新问题。本文主要以分 类不均衡问题和类不均衡问题的算法为主要研究内容。试图分别从数据预处理和模式选择这两个 方面来改进和研究不均衡问题相关算法目前解决分类不均衡问题主要基于抽样的技术，有两个 相关研究方向，一个是非充分抽样技术，另一种是充分抽样技术就一般的两分类问题而言，非 充分抽样算法的主要思想是剔除样本点数目较多的那类样本点，使得两类样本点数目均衡之前 算法的主要缺点在于没能有效地利用剔除出来的样本点进行学习本文主要基于半监督学习的思 想来利用这些样本点提高算法的泛化能力充分抽样技术的思想主要是复制样本点数目较少的那 类样本点，之前的研究一直考虑数据结构是一种线性分布的情况下的复制算法本文主要基于最 小闭包球算法提出了一种充分抽样的算法来解决非线性数据结构的数据集中的充分抽样问题本 文最后根据类不均衡问题的特点，从模式选择的角度考虑，提出了一种利用，7 一e c i 螂中参 数l ，的几何意义的算法来解决类不均衡问题 关键词：机器学习，支持向量机。类不均衡问题，充分抽样非充分抽样，卵一恤e c h h 中国农业大学硕士学位论文 a b s t r a c t a b s t r a c t i nt h ec l a s s i f i c a t i o ni m b a l a n c e dq u e s t i o ni saq u e s t i o nw h i c h ( r e l a t i v e l y ) n e w l ye m e r g e s t h i sa r t i c l em a i nc o n s i d e r a t i o nc l a s s i f i c a t i o n i m b a l a n c e d q u e s t i o na n dk i n do fi m b a l a n c e dq u e s t i o na l g o r i t h mr e s e a r c h a t t e m p t sc h o o s e s t h e s et w oa s p e c t sf r o mt h ed a t ap r e p r o c e s sa n dt h ep a t t e r nt oi m p r o v ea n dt h e r e s e a r c hi m b a l a n c e dq u e s t i o nr e l a t e da l g o r i t h a l f o r m e r l y s o l v e dt h e c l a s s i f i e di m b a l a n c e dp r o b l e mm a i n l yb a s e do nt h es a m p l i n gt e c h n o l o g y ，s o m e t w oc o r r e l a t i o n sr e s e a r c hd i r e c t i o n ，ar i g h ta n dw r o n gf u i is a m p l i n gt e c h n i q u e ， a n o t h e rk i n dw a st h ef u l ls a m p li n gt e c h n i q u e ，s p e a k i n go ft h eg e n e r a lt w oc l a s s c l a s s i f i c a t i o n 。t h eu n d e r s a m p l ea l g o r i t h mm a i nt h o u g h tr e j e c t st h es a m p l e n u m b e rm e r et h a tk i n do fs a m p l e ss p o t ，c a u s e dt w ok i n do fs a m p l e sn u m b e rt o b eb a l a n c e d ，b e f o r et h ea l g o r i t h mm a i ns h o r t c o m i n gl a yi nt h es a m p l es p o tw h i c h h a sn o tb e e n a b l ee f f e c t i v e l yt ou s er e j e c t st oc a r r yo nt h es t u d y 。t h i sa r t i c l e m a i n l yu s e st h et h o u g h tw h i c hs e m i s u p e r v i s e dl e a r n i n gt ou s et h e s es a m p l e s p o t s t h eo v e r s a m p l et e c h n i q u et h o u g h tm a i n l yi sd u p l i c a t e st h es a m p l en b e r l e s s t h a tk i n do fs a m p l e ss p o t ，t h eb e f o r er e s e a r c hc o n t i n u o u s l yt e n t a t i v e d a t as t r u c t u r ei si no n ek i n do f1 i n e a rd i s t r i b u t i o ns i t u a t i o nd u p l i c a t i o n ， t h et h i sa r t i c l em a i nu s es l i g h t l ys h u t st h ep a c k a g eo fb a l la l g o r i t h mt o p r o p o s eo n ek i n do fo v e r s a m p l ea l g o r i t h ms o l v e st h en o n l i n e a rd a t as t r u c t u r e d a t as e to v e r s a m p l ep r o b l e nt h i sa r t i c l ef i n a l l yp r o p o s e do n ea l g o r i t h m m a i n l yi si nu s e 叩一o n e c l a 站t h ep a r a m e t e rpg e o m e t r ys i g n i f i c a n c es o l u t i o n c l a s si m b a l a n c e dq u e s t i o n k e y w o r d s ：m c h i n el e a r n i n g , s u p p o r tv e c t o rm m c h i n e c 蛔自m b a l a n c ep r o b l e m , o v e r s a m p l e , u n d e r 姐m p l e , 玎一e d a 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得中国农业大学或其它教育机构的学位或证书 而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示了谢意 研究生签名： 帆劲7 年厶多日 关于论文使用授权的说明 本人完全了解中国农业大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复 制手段保存、汇编学位论文同意中国农业大学可以用不同方式在不同媒体上发表、 传播学位论文的全部或部分内容 ( 保密的学位论文在解密后应遵守此协议) 研究生签 导师签名 时间 时间 日 日 黟歹 0 年年 萝 哆 中国农业大学硕士学位论文 第一章绪论 第一章绪论 1 i 不均衡问题 分类问题中的不均衡问题目前是一个被国内外学者关注的( 相对地) 新问题当机器学习成 熟了，从简单的线性分类问题的研究到各种算法的发展，并且广泛地被使用在现实世界，以及相 关行业的研究随着机器学习。数据挖掘，模式识别的相关研究的深入，越来越多的学者专家， 开始关注一些非标准的，非理想条件下的学习问题分类问题中的不均衡问题正是这样的一种学 习问题 本文主要研究的是分类问题中的不均衡问题在解决不均衡问题的时候。首先很多人对不 均衡问题的认识就不足，在机器学习领域，学习中的不均衡问题主要有类不均衡问题和分类不均 衡问题。正是因为这两类不均衡问题的区别，所以解决不均衡问题的方法也分两类一类是通过 改进训练集，另一类是针对不均衡问题改变模型结构 显然，类不均衡问题是问题本质上的不均衡现象，所以应该通过改变标准的算法模型来达 到特殊的训练目的而分类不均衡问题主要是训练集的问题所以要通过改变数据集的结构来达 到训练器精确的要求本文试图从两方面着手研究不均衡问题 分类不均衡问题 分类不均衡闯题主要是指训练样本点数目的不均衡 类不均衡问题 就二分类问题而言所谓类不均衡问题是指两类样本点的概率分布不均衡 具有不平衡类分布的数据集在许多实际应用中是很常见的例如，一个监管产品生产线的下 线产品的自动检测系统会发现，不合格产品的数量远远低于合格产品的数量类似地，在信用卡 欺诈检测中，合法交易远远多于欺诈交易。在这两个例子中，属于不同类的实例数量都不成比例 不平衡程度随应用不同而不同个在六西格马原则( s i xs i g m ap r i n c i p l e ) 下运行的制造厂在一 百万件出售给顾客的产品中可能发现四件不合格品，而信用卡欺诈的量级可能是百分之一尽管 它们不常出现，但是在这些应用中，稀有类的正确分类比多数类的正确分类更有价值然而，由 于类分布是不平衡的，这就给那些已有的分类算法带来了很多问题 准确率经常被用来比较分类器的性能，然而它可能不适合评价从不平衡数据集得到的模型 例如，如果1 的信用卡交易是欺诈行为，则预测每个交易都合法的模型具有9 9 的准确率，尽 管它检测不到任何欺诈交易另外，用来指导学习算法的度量( 如决策树归纳中的信息增益) 也 需要进行修改，以关注那些稀有类 检测稀有类的实例好比大海捞针因为这些实例很少出现，因此描述稀有类的模型趋向于是 高度特殊化的。例如，在基于规则的分类器中。为稀有类提取的规则通常涉及大量的属性，并 很难简化为更一般的、具有很高覆盖率的规则( 不像那些多数类的规则) 这样的模型也很容易 受训练数据中的噪声的影响因此，许多已有的算法不能很好地检测稀有类的实例 本章将给出一些为处理不平衡类问题而开发的方法。首先，介绍除准确率外的一些可选度量 中国农业大学硕士学位论文 第一章绪论 然后，描述如何使用代价敏感学习和基于抽样的方法来改善稀有类的检测 1 2 可选度量 由于准确率度量将每个类看得同等重要，因此它可能不适合用来分析不平衡数据集，在不平 衡数据集中，稀有类比多数类更有意义对于二元分类，稀有类通常记为正类，而多数类被认为 是负类。表i 1 显示了汇总分类模型正确和不正确预测的实例数目的混淆矩阵 表1 1 类不是同等重要的二类分类问题的混淆矩阵 预测的类 + 实际 + 厶( 砰)l ( f a 9 的类 f 心玲，- ( m 在谈到混淆矩阵列出的计数时，经常用到下面的术语： 真正( t r u ep o s i t i v e ，t p ) 或厶，对应于被分类模型正确预测的正样本数 假负( f a l s en e g a t i v e 。f n ) 或丘对应于被分类模型错误预测为负类的正样本数 假正( f a l s ep o s i t i v e ，f p ) 或l ，对应于被分类模型错误预测为正类的负样本数 真负( t r u en e g a t i v e ，t n ) 或l ，对应于被分类模型正确预测的负样本数。 混淆矩阵中的计数可以表示为百分比的形式 真正率( t r u ep o s i t i v er a t e ，t p r ) 或灵敏度( s s i t i v i t y ) 定义为被模型正确预测的正样本的 比例，即： 1 r i 像- 1 限( t p + f n )( 1 2 1 ) 类似地， 真负率( t r u en e g a t i v er a t e ，t n r ) 或特指度( s p e c i f i c i t y ) 定义为被模型正确预测的负样本 的比例，即： 1 l 限_ ，n l ( 僻f p )( 1 2 2 ) 最后，假正率( f a l s e p o s i t i v e r a t e ，f p r ) 定义为被预测为正类的负样本比例，即： f p r f f i f p ( t n + f p )( 1 2 3 ) 而假负率( f a l s e n e g a t i v e r a t e 。f n r ) 定义为被预测为负类的正样本比例，即： f n r = f n ( t p + f n ) ( 1 2 4 ) 招回率( r e c a l l ) 和精度( p r e c i s i o n ) 是两个广泛使用的度量，用于成功预测一个类比预测其 他类更加重要的应用。下面给出精度( p ) 和召回率( r ) 的形式化定义： r p p2 再丽 2 中国农业大学硕士学位论文 第一章绪论 ，= 一 r p tp+fn 精度确定在分类器断言为正类的那部分记录中实际为正类的记录所占的比例精度越高，分 类器的假正类错误率就越低。召回率度量被分类器正确预测的正样本的比例具有高召回率的分 类器很少将正样本误分为负样本实际上，召回率的值等于真正率 可以构造一个基线模型，它最大化其中一个度量而不管另一个例如，将每一个记录都声明 为正类的模型具有完美的召回率，但它的精度却很差相反，将匹配训练集中任何一个正记录的 检验记录都指派为正类的模型具有很高的精度，但召回率很低。构建一个最大化精度和召回率的 模型是分类算法的一个主要挑战。 之前的学者在处理不均衡问题的研究方向上，主要存在代价敏感学习和基于抽样的方法两 个方向 1 3 代价敏感学习 代价矩阵对将一个类的记录分类到另一个类的惩罚进行编码令c ( i ，力表示预测一个i 类记 录为j 类的代价使用这种记号，“+ ，_ ) 是犯一个假负错误的代价，而c ( 、+ ) 是产生一个假警 告的代价代价矩阵中的一个负项表示对正确分类的奖励。给定一个n 个记录的检验集，模型m 的总代价是： c 【膨) = t p xc ( + ，+ ) + f p xc ( + ) + f n xc ( + _ ) + t n x a - t - ) ( 1 3 1 ) 在o ，l 代价矩阵中，即c ( + ，中c ( ，即而c ( + ，) ；c ( ，+ ) - 1 ，可以证明总代价等价 于误分类的数目 e ( 膨) = o x ( t p + t n ) + i x ( 用+ f v ) = n x e r r ( 1 3 2 ) 其中，e r r 是分类器的误差率 例1 1考虑表l - 2 所示的代价矩阵犯假负错误的代价是犯假警告的一百倍换句话说， 漏检测出任何一个正样本与犯一百个假警告一样糟糕给定具有表5 - 8 所示的混淆 阵的分类模型，每一个模型的总代价是： c , ( m 3 2 1 5 0 x ( 一1 ) + 6 0 l + 4 0 1 0 0 2 3 9 1 0 ( 1 3 3 ) 3 c ( 鸠) = 2 5 0 ( 一1 ) + 5 x l + 4 5 x 1 0 0 = 4 2 5 5 ( 1 3 4 ) 注意，尽管模型 如同时改善了它的真正计数和假正计数，但是仍然较差，因为这些改善 是建立在增加代价更高的假负错误之上而标准的准确率度量更趋向于鸩优于m 中国农业大学磺士学位论文第一章绪论 表l - 2 例1 1 的代价矩阵 预测的类 类= +类；一 实际类= + 1 1 0 0 的类共一lo 表l - 3 两个分类模型的混淆阵 预测的类 如+类，一 模型m 实际共 4 - 1 5 04 0 的类势一6 02 5 0 预测的类 模型鸩 条+类；一 实际类= + 2 5 04 5 的类类= 一52 0 0 代价敏感分类技术在构建模型的过程中考虑代价矩阵，并产生代价最低的模型例如，如果 假负错误代价最高，则学习算法将通过向负类扩展它的决策边界来减少这些错误，这种方法产生 的模型覆盖更多的正类样本，尽管其代价是产生了一些额外的假警告 有许多办法将代价信息加入分类算法中例如，在决策树归纳过程中代价信息可以用来； ( 1 ) 选择用以分裂数据的最好的属性；( 2 ) 决定子树是否需要剪枝；( 3 ) 处理训练记录的权值， 使得学习算法收敛到代价最低的决策树；并且( 4 ) 修改每个叶结点上的决策规则为了解释最 后一种方法，令pg l t ) 表示属于叶结点t 的类i 的训练记录所占的比例如果下面的条件成立， 一个典型的二元分类问题的决策规则将正类指派到结点t ： p ( + i f ) p ( - l f ) ；p ( + i f ) l - - p ( + i f ) 辛2 p ( + i f ) i ( 1 3 5 ) 等p ( + i f ) 0 5 前面的决策规则表明，叶结点的类标号依赖于到达该结点的训练记录的多数类。注意，这个规则 假定对于正样本和负样本，误分的代价都是相同的。这个决策规则等价于4 3 5 节的公式( 4 - 4 8 ) 4 中国农业大学硕士学位论文 第一章绪论 给出的表达式 代价敏感的学习算法不是采用多数表决，而是赋予结点t 类标号i ，如果它最小化如下表达式： c o l f ) = p ( j l t ) c u ，f ) ( 1 3 6 ) ， 在c ( + + ) a c ( ，) 神情况下，叶结点t 被指派为正类，如果： ，( + i f ) c ( + ，- 0 ，( 一i f ) c ( - ，+ ) j p ( + l f ) c ( + ，o ( 1 一，( + i f ) ) c ( _ + ) ( 1 - 3 7 ) 专p “m g 二生一 7 c ( - + ) + c ( + ，- - ) 这个表达式说明，可以把决策规则的阈值从0 5 修改为c ( - ，+ ) ，( c ( + ，- ) + c ( 。+ ) ) ，得 到一个代价敏感的分类器如果c ( ，+ ) c n ) 划阈值将小于0 5 。这个结果是有意义的，因 为一个假负错误比一个假警告代价高降低阈值将向负类扩展决策边界 1 4 抽样技术 抽样是处理不平衡类问题的另一种广泛使用的方法抽样的主要思想是改变实例的分布，从 而使得稀有类在训练数据集中得到很好的表示用于抽样的一些现有的技术包括不充分抽样 ( u n d e r s a m p l i n g ) 、过分抽样( o v e r s m n p l i n g ) 和两种技术的混合为了解释这些技术，考虑一个 包含1 0 0 个正样本和1 0 0 0 个负样本的数据集 在不充分抽样的情况下，取1 0 0 个负样本的一个随机抽样，与所有的正样本一起形成训练集 这种方法的一个潜在的问题是，一些有用的负样本可能没有选出来用于训练，因此导致一个不太 优的模型。克服这个问题的一个可能的方法是多次执行不充分抽样，并归纳类似于组合学习方法 的多分类器也可以使用聚焦的不充分抽样( f o c u s e dt m d e n m p l m g ) ，这时抽样程序精明的确定 应该被捧除的负样本，如那些远离决策边界的样本 充分抽样复制正样本，直到训练集中正样本和负样本一样多 然而，对于噪声数据，充分抽样可能导致模型过分拟合，因为一些噪声样本也可能被复制多 次原则上，过分抽样没有向训练集中添加任何新的信息对正样本的复制仅仅是阻止学习算法 剪掉模型中描述包含很少训练样本的区域的那部分( 即小的不相连的部分) 增加的正样本有可 能增加建立模型的计算时间 混合方法使用二者的组合，对多数类进行不充分抽样，而对稀有类进行过分抽样来获得均匀 的类分布不充分抽样可以采用随机或聚焦的子抽样另一方面，过分抽样可以通过复制已有的 正样本，或在已有的正样本的领域中产生新的正样本来实现在后一种方法中，必须首先确定 每一个已有的正样本的k 最近邻，然后。在连接正样本和一个k - 最近邻的线段上的某个随机点产 生一个新的正样本重复该过程，直到正样本的数目达到要求。不像数据复制方法，新的样本允 许我们向外扩展正类的边界然而，这种方法仍然可能受模型过分拟合的影响 关于不均衡问题的研究工作可以参看c h a w l a 等【4 6 】和w e i s s 4 7 写的综述，许多学者都考虑了 挖掘不均衡问题的抽样方法如k u b a t 和m a t w i n 【4 8 】，j a p k o w i t z 4 9 以及d r u m m o n d 和h o a e 5 0 ， 5 中国农业大学硕士学位论文 第一章绪论 以及其他算法例如j o s h i 等提出的 5 l l s m o t e s 2 ，p n r u l e 5 3 和c r e d o s 【矧，【5 5 】，【5 6 】 1 5 小结 本章主要介绍了关于分类问题中不均衡问题的一些基础概念以及一些相关的学习算法，本 文接下来的章节的安排如下，第二章主要介绍支持向量机理论中的统计学习理论，并求从监督学 习，无监督学习，半监督学习三个方面分别介绍了支持向量机相关算法模型第三章主要介绍我 的研究提出的算法，并阐述其算法思想第四章数值试验部分主要通过一些数据集的数值试验 来现实我们提出的算法和相关算法比较的结果。第五章思考与展望 6 第二章支持向量机 2 1 统计学习理论 顾名思义，统计机器学习应该是以统计学为工具来研究和设计机器学习算法的，但实际上， 人工智能界目前所谈的统计机器学习是具有其特殊含义的。v a p m i k 的著作【l 捌的出现是统计学习 理论得到正式承认的标志目前人们普遍认为的统计学习理论主要是研究从数据到分布的归纳 机理问题，即要求解问题的目标是分布规律意义下的某种最优性，而我们所知道的只有有限样本 集合如何设计以训练数据为目标函数的机器学习算法，从有限的样本得到分布的意义下的最优， 这是统计机器学习研究的主要内容由此可知，统计学习理论主要是解决基于训练数据的目标函 数和基于分布目标函数之问的关系问题。 统计学习理论和统计模式识别【3 】的前提假设和目标是一致的，即都假设已获取的样本具有一 定的统计规律存在，具体体现为要求训练样本集是独立同分布的，且测试样本也来源于此分布。 统计机器学习和统计模式识别的目的都是要根据样本集背后蕴涵的的统计规律，在统计意义下较 好的解决具体的实际问题。统计学习理论与统计模式识别( 特别是b a y s 决策理论) 的主要区别 在于推理的方式的不同统计模式识别是在分布已知或在估计分布的基础上进行推断，实际的推 断方式属于演绎推理统计学习理论是在分布未知并在不估计分布的基础上进行推断，推理的方 式属于归纳推理 一个自然的想法就是利用有限样本估计分布，从而得到样本空间的分布规律，这是经典统计 模式识别理论的基本出发点尽管这种想法在实际应用中有时会产生较好的实际效果。但在统计 学习理论中，一般不以估计分布为出发点因为统计学习理论遵循一个原则，即在解决一个给定 问题时，要设法避免把解决一个更一般的问题作为其中间步骤【l ，2 】 统计学习理论与传统统计学的主要区别在于推理的理论依据不同。传统统计学的推断主要依 据大数定理，这必然会对样本的数目提出一些要求并导致结论的渐近性，而统计学习理论由于基 于p a c 框架( p r o b a b l ya p p r o x i m a t e l yc o r r e c t ) 【4 】给出关于泛化性能的界，从而可以得到误差精 度和样本数目之间的关系，从这一点来说统计学习理论的推断是可以针对有限样本的 s v m ( s u p p o r tv e c t o rm a c h i n e ) 是建立在统计学习理论的基础上的第一个学习算法，目前主要 应用于求解监督学习问题，即分类和回归问题因为s v m 以分类和回归问题的泛化性能为目标， 所以与传统的最小二乘方法和一些数据拟合方法有着明显的的区别泛化性能指的是分布意义下 的总体错误率从这一点我们就可以清楚的看出，统计学习的目的不是对已知样本的描述( 或称 为记忆) ，而是对q p p , i 练样本的预测( 或称泛化) ，支持向量机是从数据到分布进行推理的一个成 功范例。对算法的性能问题，s v m 标志着人们已经从单纯的试验验证向理论分析过渡 2 2 监督学习问题与统计学习算法 2 2 i 监督学习问题 7 设假设空问为日= 矿：r ” z ) ，( ，乃) ，( 屯，咒) ，( 五，只) e r ”x z ，其中毛是训练样 中国农业大学硕士掌位论文 第二章支持向量帆 本，乃是标签，且( 玉，弗) 独立同分布于概率密度函数p ( x , y ) 监督学习问题的目的是，在假设 空间日选取函数厂，使得月= i c ，f ( x ) ) p ( x , y ) d r d y l d 、化，这里c 0 ，( 工) ) ：y x z _ r 是代价函数置u ) = l c ( ) ，f ( x ) ) p ( x , y ) d x d y 是监督学习的泛化性能，而 且。( ，) = ；窆c ( ) ，。，( 毛) ) 称为经验风险显然，泛化性能是关于分布的，而经验风险是关于数 据的，当样本空间为样本集合且每个样本出现的概率相同时，泛化性能也变成了经验风险 值得指出的是以上可以称为监督学习问题的数学定义因此，对于监督学习问题，其评价指 标是唯一和客观的，就是泛化能力如没有特别的目标函数，所设计的算法应该使泛化性能最小 化需要注意的是，在上述定义中，假设空间日是事先指定的，我们的目的是在事先指定的范 围中寻求一个错误率最低的函数至于假设空间如何选取，它属于目前机器学习领域最难解决的 问题之一模式选择问题，在分类定义中并不涉及另外，对一个具体的分类算法，我们应该严 格按照分类的定义去理解它，特别要注意算法的假设空间显然，当假设空间是一次函数集合的 时候，就是通常所说的线性分类或回归问题但对于线性分类器的设计问题，在支持向量机中， 线性可分情形下的最大间隔( m a i m ) 算法和线性不可分情形下的软间隔算法对应的假设空间却 是不一样的 2 2 2s v m 及其理论分析 捌锄一蚪w 删= 怨彩 对于线性可分的二分类闯题，s v m 表现为求解下列优化问题： 吧i 。n 三l l w 8 2 2 _ 一 h j 上咒( 伊五+ 6 ) - l i = l ，2 - - , 1 ( 2 2 2 1 ) 这就是s v m 的最大间隔算法，租略的说，s v m 中的间隔指的是样本点到线性分类器所决定 超平面的最小欧氏距离，当然间隔也可能是基于其他范数的，不同的范数间隔会导致不同形式的 优化问题当间隔是欧氏距离时有时也称为z 间隔 值得注意的是，优化问题( 2 2 2 1 ) 的假设空间并不是所有一次函数的集合，而是经验风险 为零的一次函数集合，这是它和软间隔算法的重要区别。人们不禁要问，基于训练数据的优化问 题式( 2 2 2 1 ) 的解能否使得分布意义下分类的泛化性能最优? 显然，从数学的角度来说，这几 乎是不可能的为此我们需要从两个方面来分析和审视泛化性能最优的问题；第一，所采用的算 法是不是渐进最优的，即当样本数目趋于无穷大时，算法能否使得泛化性能最优；第二，在只有 有限样本的情形下，如何设计相对来说最好的算法，使得泛化性能最优显然，对于只有样本数 目的情形下。由于整体分布未知同时又不采用估计分布的手段，此时必须对泛化性能最优的标准 8 中罾农生大学硕士学位论文第二章支持向量机 有所下降，这就是下面的学习问题提出的p a c 框架 有限样本情形正是在统计学习理论研究的主要内容在统计学习理论中，一般以这样的标准 来衡量学习机器的性能，即从统计的观点来说明最优性的p a c 框架，p a c 框架最早出现于文献【4 】 下面简化的p a c 定义摘自文献【8 】 定义2 2 2 1p a c 框架：对一组概念f ，一个学习机器被认为是p a c 的。是指它具有如下性 质：对任意分布p ，任意f e f 和0 占2 一个不容易忽视的问题是，这个界是不是紧的j s c h a w e - - t a y l o r 等在文献 5 e e 指出不等式 ( 2 2 2 4 ) 的界在l 唱意义下是紧的因此，我们认为最大边缘算法具有统计学习理论依据，主 要是针对p e a 框架和定理2 2 2 2 而言的另一方面，我们也注意到， 占2 这一条件，这说明 精度只石( 力正( 劝s g 和样本数有一定的关系。因此我们认为通常所说的小样本统计学仍然 要根据精度对样本数目有一定的关系，只不过在实际中，所面临的问题是在只有这些有限样本的 情况下，我们怎样才能做得更好另外，我们还注意到，在式( 2 2 2 4 ) 的泛化界中，当样本数 目趋于无穷大时，错误率是趋于零的，这也同时能说明学习算法的渐进最优性，它应该是泛化界 必须具备的条件之一 我们注意到，很多文献都认为优化问题( 2 2 2 1 ) 的理论依据主要体现在如下的泛化界以概 率l 一玎成立： r s r 。+ 对于上式，一般做如下通俗的理解，即为了使得期望风险最小，应同时最小化经验风险和假 设空间的v c 维，从而由此可以得出结构风险最小话原理控制v c 维的项也就是我们通常使用 的正则化项，所以上述不等式在一定程度上说明了使用效果很好的正则化方法是有理论依据的 显然，优化问题式( 2 2 2 1 ) 实际上正是经验风险为零时最小化假设空间v c 维这一思路的具体 体现，并且泛化界式( 2 2 2 5 ) 还能很好的解释支持向量机体系中占据重要地位的软边缘算法 但当我们利用这种简单明确的思路去设计一些新的算法并分析理论依据时，就会发现存在许多问 题，这主要表现在学习算法的目标应该是训练数据相关的，而按照结构风险最小化原理，结构风 险最小化原理中的系列嵌套假设空加应该在数据出现前就定义好，这其实要求假设空间与训练数 据无关，即这时的v c 维与训练数据无关。这就产生了矛盾，使得已有的理论解释无法自圆其说 关于结构风险最小化原理存在的问题，详见文献【1 0 1 前面的泛化界( 2 2 2 - 4 ) 已经说明了线性可分情形下最大边缘算法的统计学习理论依据众 所周知，最大边缘算法的k e r n e l 形式实际上是在特征空间求解最大边缘问题，特征空间的维数通 常很高，甚至是无限维的。由于式( 2 2 2 4 ) 的泛化界涉及到了v c 维，而v c 维和输入空间的 l o 中国农业大学硕士学位论文第二章支持向量机 维数有一定的联系，这使得式( 2 2 2 a ) 无法解s v m 核方法的泛化性能问题。另一方面，应该 注意到式( 2 2 2 4 ) 式中的泛化界只适用于经验风险为零的情形 为此，j s c h a w e - - t a y l o r 等人对边缘核泛化界之间的关系进行了深入的研究”以“l ，得到基于 边缘来控制泛化性能上界的不等式，即 o r b ( f ) 绷脚郴；( 等1 0 9 蠹l o g 等+ l o g 旁4 ( 2 2 2 6 ) lr5 a ro 其中至攀 1 7 ，则称工为假设，的 ，7 - - o u f l i t a - 显然，野一l l i t e r 和线性可分之间有一定的关系，q - - o u t l i t e r 的出现会使经验风险不为零 定义2 4 3 5 ( ，7 非监督问题的最优解与叩- - o u t l i t e r ) 如果 r u o ，r 1 ) = m i l l f l ( f ( x ) ，玎p o ) 如，e i - 1 则称f o 为，7 非监督问题的最优解五在训练集合 五，毛，西) 中的r - - o u t l i t e f 称为叩非监督问 题的o u t l i t e l 注意在定义2 4 3 4 中，函数的，- - o u t l i t a r 与训练样本使没有关系的从统计学习理论的观点 来说。这里的o u t l i t 日也应与训练样本无关之所以如此定义是考虑到在实际问题中。往往需要 从训练样本中发现o m l i t e r 本文之后提到o u t l i t e r 时，都是指函数在训练集合中的o u t l i t e r 定义2 a 3 6 ( 玎非监督问题的边缘) 设，o ) = 伊工+ 6 0 ( o i l 。= 1 定义训练玉关于，的 刁的边缘为m ( f ，玉们= 7 1 - c ( x 。，厂) 定义厂的可的边缘为 m ( f ，5 ，玎) = m i n m ( f ，t 刀) ，i = l 2 ，) 定义2 4 3 7 ( 玎非监督问题的最大边缘解) 令日= 矿：，( 曲= 伊，+ 6 ，国r s , b e r ， 对线性可分问题，若五日，满足 1 9 中国农业大学硕士学位论文 第二章支持向量机 埘c ，s ，7 ) ；n l a x 册( 厂，s ，7 ) ，f 月。) 则称五为玎非监督问题的最大边缘解 2 4 4 玎一伽t c h “问题 对于o n e - - c l a s s 问题，我们一般作如下理解：已知一个样本集合，构建一个能描述样本密度 分布的二值模型，如果一样本处于较大密度区域之内则为正常样本，否则为o u t l i t e r 样本从学 习的观点来看。o n e - - c l a s s 闯题是一种无监督的学习问题目前，基于统计学习理论的算法，如 支持向量机和b o o s t i n g 在处理有监督的学习问题上卓有成效显然，能否设计统计学习算法解决 o n e - - c l a s s 问题是人们非常关心的问题 1 9 9 9 年，t a x 和d u i n 提出了一种s v d d 方法( s u p p o r tv e c t o rd a md e s c r i p t i o n ) 3 0 , 3 i j 用于 o n e - - c l a s s 问题分类器的设计和o u t l i t e r 的检测。其主要思路是寻求一个能把所有训练样本保卫起 来的最小超球，以此最小超球作为o n e - - c l a s s 问题的分类器在实际操作中，他们在覆盖的样本 数和覆盖球的半径之间有所平衡，即允许一定数目的样本点位于该超球之外此时，位于覆盖球 之外的训练样本称为o u t l i t e r 2 0 0 2 年，s c h i i l k o p f 等人统计学习理论的观点深入研究了o n e - - c l a s s 问题，设计出了与 支持向量机完全类似的简明算法，并建立了统计学习理论依据，给出了泛化不等式他们的软算 法( v - s v m ) 沿用了文献 3 2 1 的思路，其中的参数能够从某一方面反映用户的需求，即其中的 平衡系数能够在一定程度上控制o u t l i t e r 的个数特别有趣的是，他们的k e m e l 算法与计算几何 的最小球覆盖算法相吻合 正是由于文献【7 ，3 0 ，3 h 在算法方面具有一定的联系，这些文献在o n e - - c l a s s 问题方面具有 代表性和权威性但当我们用统计学习算法的四条标准对o l l o - - c a n 问题进行审视的时候，就会 发现文献的作者的工作仍然存在一些不足首先，我们在文献【7 ，3 0 ，3 1 中均没有发现o n e - c l a s s 和o u t l i t e r 的确切含义，即文献没有给出分布意义下的性能指标实际上，文献 3 0 ，3 1 l 给出的仅 仅是基于训练数据的算法，并没有把训练样本看成是来源于独立同分布的一组样本，没有从分布 意义上去考虑o m ：- - c l u t s 泛化问题，因而也就没有证据表明他们的算法是一种统计学习算法另 外，文献阴描述的o c - - d a s s 闯题实际上与一个特殊的二分类问题等价，这不免引起人们对e d 无监督性的怀疑。特别是对于线性可分情形，其算法用一个超平面作为o e - - d a s s 闯题的 分类器，这与人们的直观相距甚远而线性问题是整个理论体系的基础，这一点是文献【刀中的 o e - - c h s s 与支持向量机的巨大差异 在现实问愿中，我们往往关心如下问题，即给定一些数据点和一个阈值，希望能找到一个函 数，当样本点与函数的误差小于给定的阈值范围时，认为它们是属于一类的这个阈值的选取必 须认为事先给定，因为它反映的是用户的需求，不同的用户会有不同的需求另一方面，用户有 时无法给出事先指定的有界区域阈值，但对o u t l i t e f 的个数有一定的先验信息或希望限定o u t l i t e r 的个数。我们在文献【1 9 ，3 3 】中尝试从理论层次解决这些问题，目的是建立一个较完整的理论体系 值得提出的是，尽管o n e - - c | a & s 问题已引起了人们的充分注意，但我们今天至今没有发现一个严 谨的数学定义。 中国农业大学硕士学位论文 第二章支持向量机 i 文献 1 9 , 3 3 1 从统计学习算法的四条标准对o n e - - c l a s s 问题进行了研究。首先我们将o n e - - c l a 与o u t l i t e f 问题理解为函数有界区域的估计问题，给出一种新的明确定义认为与一个待求函数 的误差小于一个给定范围r 的点属于一类。而将误差大于这个范围r 的理解为o n t l i t e r 基于 o n d i t e r 数目的多少，可以定义损失函数对待求函数，我们认为它满足在给定的阙值区域内尽量 多的包括训练样本点。在这样的观点下，即可以定义泛化性能此时o n e - - c l a s s 问题是一种特殊 的2 3 3 节定义的玎非监督问题。并且可以认