（运筹学与控制论专业论文）不均衡数据集的支持向量机模型研究.pdf

摘要 摘要 近年来支持向量机理论取得了长足的发展，并广泛应用到模式识别、回归分析、 信号处理、函数估计等诸多领域，但仍有待进一步的研究和改善。 传统的支持向量机当处理重要性或样本数量不均衡的训练集时其性能，分类精 度将会显著下降；训练支持向量机可以归结为求解一个二次规划问题，而求解二次 规划的算法的计算复杂度和空间复杂度是随着样本数量的增加显著增加，一些经典 的求解二次规划的方法对于学习大规模的训练样本往往会失效。针对这些问题，在 二分类方面，本文做了三方面的研究工作。第一，支持向量机参数的选择是决定其 性能的关键，本文从惩罚参数、核参数的作用和最优性条件给出了支持向量机参数 选择的定性分析；第二，本文给出了两种分类惩罚的支持向量机模型，使之能更好 的处理不均衡的样本集；第三，本文提出采用有效集法，针对所要求解二次规划的 特点，提出了一种基于有效集法的动态存储的支持向量机算法。该算法很大程度上 降低了对计算机内存的需求；提高了求解速度，并保证了分类精度，进一步加快了 学习的速度。并且用数值实验对上述三方面工作进行了验证。 关键词：支持向量机；有效集法；动态存储；惩罚因子； 北京t 业大学理学硕十学位论文 a bs t r a c t s u p p o r tv e c t o rm a c h i l l et e c h 血q u eh a sar 印i dd e v e l o p m e n t ，a 1 1 di th 鹊b e e n 印p l i e d i i l t om a n y d so ff i e l d s y e tm e r ei ss t i l lm u c ht ob es t u d i e d 锄di i n p r o v e d t h ec l a s s i f i c a t i o na c c u r a c yo fm e 仃a d i t i o n a ls v mw i l lb es i 鲥f i c 锄n yr e d u c e d 访h e n d e a l i n gw i mu n b a l a n c e dd a t as e t t r 血i n gs v mc a nb e 仃a n s f 0 胁e dn os o l 诎培a q u a d r a t i cp r o b l 锄( q p ) t h ec o 1 p u t i n gc o n l p l e x i t ya 1 1 ds p a c ec o m p l e x 时o fm eq p i 1 1 c r e a u s e ss i 鲥f i c a n t l yw i mm ei 1 1 c r e a s eo fs 锄p l en u m b e r s o m eo fm ec 1 2 l s s i cm e t l l o d s o fq pa r eo r e ni r a l i d a t e df o rm es t u d yo f1 a r g e s c a l et r a i 血gs a i 】叩l e s i n1 i g h to ft 1 1 e s e p r o b l 锄s ，血t w oc l a s sc l a s s i f i c a t i o n ，“sp a p e rh a sb e e nd o n ei 1 1 t 1 1 r e ea r e a so fr e s e a r c h f i r s t ，s v mp a r 锄e t e rs e l e c t i o ni sm ek e yt o d e t e 力 i l i n ei t sp e r f o m a j l c e ，w e 西v em e p e n a l t yp 2 u r 锄e t e r 、t 1 1 ep a r 锄e t e ro fk e n l e l 缸n c t i o nq u a l i t a t i v ea 1 1 a l y s i s 丘o mm e r 0 1 eo f 也ep a r 锄e t e r s 撕l dt h ek k t c o n d i t i o n ；s e c o n d l y ，t 1 1 i sp a p e rp mf o 刑a r dt w ok i l l d so f t w o c a t e g o 巧p u m s l l i i l e n ts u p p o r tv e c t o rm a c _ h i n em o d e l ，s o 1 a ti tc a l lb e t t e rd e a lw i 也m e u n b a l a n c e dd a t as e t s ；t h i r d ，a c c o r d i n gt om ef l e a n l r eo fm eq p ，t h j sp 印e rp r o p o s e sa 1 1 咖r o v e ds v mm e 廿1 0 db a s e do na c t i v es e tm e t h o dw i md y n a m i cs t o r a g eo fk e m e l 如n “o n t h ea l g o r i t h m sr e d u c e sd e i l l a l l d sf o rm ec o m p u t e rm e m o r yg r e a u y ，i 1 1 c r e a l s e dm e s p e e d ，a i l de n s u r em ec l a s s i f i c a t i o na c c u r a c y ，舢n e rs p e e du pt h e 仃a i l 血gp r o c e s s n u i n e r i c a le x p e 血e n t sv e r i f i e dn l ea b o v e - m e n t i o n e dm r e ea s p e c t so fm e 、阳r kw eh a v e d o n e 1 ( e yw o r d s ：s u p p o r t v t o rm a c h i i l e ；a c t i v es e tm e 血o d ；d y n a i l l i cs t o r a g e ；p e n a l t yf a c t o r ； 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构的学位 或证书而使用过的材料。与我同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权保 留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：丑晶导师签名：茸毅 隰州萨彳乙 第l 章绪论 第1 章绪论 1 1 引言 随着社会的发展，人类社会进入了一个信息时代。面对海量的数据，如何进行 分析处理，成为信息技术领域的主要问题。机器学习技术有了广泛的发展。支持向 量机( s u p p o hv 色c t o rm a c i l i n e ，简称s v m ) 是在统计学习理论基础之上发展起来的一 种全新的机器学习算法。s v m 基于统计学习理论的结构风险最小化原则，它将最大 化分类间隔的思想和基于核的方法结合在一起，表现出很好的泛化能力，近年s v m 成 为人们研究的热点。 1 2 研究课题背景与研究意义 支持向量机是一类新型机器学习方法，是数据挖掘中的一项新技术，是借助于最 优化方法解决机器学习问题的新工具。它最初于2 0 世纪9 0 年代由v a p n i k 提出，近年 在其理论研究和算法研究实现方面取得了突破性的进展，开始称为克服“维数灾难 和“过学习”等传统困难的有力手段。 s v m 基于统计学习理论的结构风险最小化原则。与传统统计学相比，统计学习理 论( s t a t i s t i c a ll e a r n i n gt h e o r y 或s l t ) 是一种专门研究小样本情况下机器学习规 律的理论。v a p n i k 等人从六、七十年代开始致力于此方面研究，到九十年代中期， 随着其理论的不断发展和成熟，统计学习理论开始受到越来越广泛的重视。统计学 习理论是建立在一套较坚实的理论基础之上的，为解决有限样本学习问题提供了一 个统一的框架。它能将很多现有方法纳入其中，有望帮助解决许多原来难以解决的 问题( 比如神经网络结构选择问题、局部极小点问题等) 。一些学者认为，s l t 和s v m 正 在成为继神经网络研究之后新的研究热点，并将有力地推动机器学习理论和技术的 发展。 支持向量机算法用非线性映射把数据映射到一个高维特征空间，在高维特征空 间中进行线性分类，将原问题转化为一个二次规划问题，与传统的分类算法相比， s v m 在运算速度、结果精度等方面都有着明显的优越性。因此，目前支持向量机已广 泛应用于人脸检测、人脸识别、手写数字识别、文本自动分类等各个方面。由于支 持向量机的广泛应用，因此对其研究具有理论与实际意义。 1 北京t 业大学理学硕十学位论文 1 3 支持向量机的算法研究概况 尽管s v m 学习机在许多实际问题的应用中得到了验证，但是该方法的具体实现 算法在计算上存在着一些问题，包括训练算法速度慢、算法复杂而难以实现以及测试 阶段运算量大等等为了克服这些困难，许多学者将很大的精力投入到寻找快速有效 的s v m 训练方法，并取得了很多成果支持向量机的算法主要有下面几类算法，二 次规划算法、选块算法、分解算法、增量算法、多变量更新算法。 ( 1 ) 二次规划算法，s v m 可以归结为一个二次规划问题，二次规划是一种常见的 优化问题，有一套比较成熟的理论。通常解法有罚函数法和单纯形法内点算法。 ( 2 ) 选块算法。当训练样本增加时，二次规划算法面临维数灾，或者由于内存限 制无法用计算机正常处理。为此，研究者提出了处理大规模训练集的s v m 选块训练 算法。 ( 3 ) 分解算法。q s u n a 1 】等人证明了c h u n k i n g 算法的收敛性，并提出了新的s v m 算法，固定工作集算法。q s u n a 的工作集选择算法不是最优的，但是他的工作可以说 是开创性的，为后来的研究奠定了基础。j o a c m m s 2 提出一种解决大型s v m 学习的 算法，称为s v 1 1 i 曲t 该算法实际上是q s u n a 方法的推广。p l a t t 提出了s m o ( s e q u e n t i a l m i m m a lo p t i m i z a t i o n 序贯最小优化) 算法。该算法可以说是q s 吼a 分解算法的一个特 例，工作集中只有2 个样本。对p 1 a t t 的s v m 算法，k e e m l is s 等通过对s v m 算法的 分析在 3 】中提出了重大改进，即在判别最优条件时用两个阈值代替一个阈值，从而 使算法更加合理，更快。 ( 3 ) 增量算法。训练方式是在训练样本单个输入的情况下训练，其训练样本总的 个数是未知的。最典型的应用是系统的在线辨识。 ( 4 ) 多变量更新算法。分解算法虽然取得了成功，大大减少了s v m 学习算 法的计算复杂性，但是这种算法的具体实施比较困难，具有相当的经验启发成分，尤其 是工作集的选择和迭代策略的确定为了克服这个难题很多学者提出了多变量迭代 更新算法，它不像分解算法一次迭代只更新工作集的学习系数一样，而是更新全部训 练集的学习系数 1 4 支持向量机的其他方面的发展 由于支持向量机坚实的理论基础和在很多领域表现出良好的推广性能，因 2 第1 苹绪论 此，国际上正在广泛开展对支持向量机的研究。目前对支持向量机分类研究主要有 以下几方面：改进的支持向量机问题；核函数的构造、改进以及相应参数的调整； 利用支持向量机解决多分类问题：以及如何把核函数的内积思想引入到其他方面， 比如p c a ( 主成分分析) 中。 1 4 1 改进的支持向量机问题 人们通过各种方法使标准的支持向量机中的最优化问题变形，产生出能解决某 一类问题或在某方面有优势的算法，其中比较典型的有以下几种： ( 1 ) f u s s y s v m ，冯瑞等人研究了模糊集支持向量机。提出了用模糊支持向量 分类器对输入数据进行预处理，并以得到的模糊隶属度作为分类依据。文献【8 中提 出了模糊支持向量机方法，在应用中取得了一定的效果。 ( 2 ) y s ：标准的支持向量机需要选取合适的参数c ，定性地讲c 的值有着 明确的含义，选取值越大，意味着更强调最小化训练错误，但定量地讲本身没有确 切的含义，所以c 的取值在实际应用中比较困难，因此在文献【1 2 】中提出了y s v m 方法，用参数7 代替c ，且7 有直观的上的意义。 ( 3 ) p s v m ：文献 1 0 中提出一种方法，改变了要求解的凸二次规划的约束条 件，即将标准s 蹦中的二次规划问题中的不等式约束改为等式约束，简化了凸二次 规划的求解。 ( 4 ) 加权s v m ：在实际应用中，当两类训练样本的数目相差悬殊时，取相同 的c 可能会影响分类效果，因此根据每类样本的数目对两类样本采取不同的惩罚系 数c ( 对样本点较少的采取较大的惩罚系数) ，可以在一定程度上解决由于样本不均而 带来的问题。文献 1 3 中提出一种加权支持向量机，对于不同类给予不同的惩罚系数， 从而弥补了标准支持向量机中样本数目相差悬殊而影响分类效果的问题。 1 5 支持向量机研究目前存在的问题 虽然支持向量机已经成功的应用在很多领域，但是作为一种新技术，仍然存在 一些目前尚未解决的问题。比如在以下几个方面： 1 ) 核函数的选择，以及核函数参数的选择问题。对于不同的问题，选择不同的 核函数和不同的参数，对于分类结果有很大影响，如何针对实际问题选择恰 3 北京t 业大学理学硕十学位论文 当的核函数。 2 )目前讨论多种类分类方法基本上是基于两类问题的分类方法，研究成果较 少。 3 ) 对于大规模的训练数据，二次规划问题的求解在计算时间和存储空间上都碰 ， 到了挑战，以至无法求解。， 4 )标准的支持向量机对于不均衡数据集的不适应性影响着支持向量机的性 能。 5 ) 标准的支持向量机对于样本集较敏感。样本集的扰动或不均衡性往往使得的 机器的性能产生较大的改变，机器的稳定性研究也是未来的一个方向。 1 6 本文的研究内容与组织结构 第一章简要介绍了支持向量机研究的背景和意义，以及其发展现状和存在的问 题。第二章主要介绍了支持向量机的基本理论，包括其理论基础和基本思想。 第三、四、五章是本文的核心部分。第三章分别从惩罚参数、核参数的意义， 盯条件，几何意义对支持向量机参数进行了定性分析。 第四章针对不均衡样本集的问题提出了两种分类惩罚的支持向量机模型。即核 函数体现的，和约束体现惩罚的模型。 第五章基于有效集算法给出了不均衡支持向量机模型求解的一种有效算法，并 进行了数值试验。 4 第2 幸支持向量机的基本理论 第2 章支持向量机的基本理论 2 1 支持向量机分类机 2 1 1 问题的提出 考虑( 两类) 分类问题，设训练样本集为： 丁= ( ，y 1 ) ，( x ，y ，) ( x y ) ) 其中石f x = 月“，y y = 一1 ，1 ) ，f = 1 ，。 分类问题的任务是，再给一个新的z ，如何判断y 的取值，换句话说就是如何把 x 所在的以维空间分为两部分，一部分空间中的x 对应的) ，为一1 ，另一部分空间中的 x 对应的y 值为l 。如寻找尺”的一个函数g ( x ) = o ，构造决策函数y = s 朗( g ( 工) ) ，称 这种方法为一般划分；也可以寻找一个超平面( w ，功+ 6 = o ，构造决策函数 y = s g i l ( ( w ，石) + 6 ) ，称这种方法为线性划分。 2 1 2 最大间隔的原则 考虑二维空间的分类问题，如图( 2 1 ) 1 2 l 。 ，、 o 、 、 图2 1 二分类几何解释示意图 f 培2 1g e o m e 仃ye x p l a n a t i o i l so f b i n a 拶c l a s s i 丘c a t i o n 从图( 2 1 ) 可以看出，显然有许多直线能将两类点正确分开，接下来产生了一个 北京工业大学理学硕士学位论文 问题：哪一条直线更好一些? 设f ，为一条能够将两类点正确划分的直线，当直线，。的 法方向w 已经确定时，沿着两个方向平移，直到分别碰到两类点，这样就得到另 外两条直线，：，毛，可见在乞，乞之间的任何一条直线都能够将两类点正确划分，不过， 显然，：，中间的直线，最好。这样问题就转化为怎么确定划分直线的法方向w 。我们 称z ：，毛之间的距离称为与法方向w 相对应的间隔，应当选取使得间隔最大的那个法 方向。 当法方向形给定以后，不妨设，：，z ，分别为( 影工) + i = 岛和( 仍x ) + f = 尼：，调整 方，可以把两条直线分别表示为( 影工) + 占= 一尼和( 影功+ 石= 尼，显然，：，z ，中间的直 线，：( 茹x ) + 占= o 作为划分直线。令w = 导，6 = 等，表示2 1 2 ，的两式可以等价表示为 kk ( 协x ) + 6 = 一1 和( w x ) + 6 = 1 可以计算得到，：，之间的距离为 2二 因此用极大化间隔的思想得到下面的最优化问题 。 珊帅2 s j y f ( ( w 工f ) + 6 ) 1 ，f = 1 ，z ( 2 1 ) 2 1 3 最大间隔的原则的解释 文献 1 2 】给出了最大间隔的原则的解释。 ( a ) 一方面，考虑输入工受到扰动。一般来讲，当输入z 与某个x ，的距离很近时， x 和对应输出的y 和y ，应该相同，我们自然希望我们的决策函数具有这种特性。下 面我们说明间隔越大越能够满足这个性质。设某个划分的间隔为p ，并设x = 薯+ 缸， 其中0 纠l ，- ，显然只要， p ，我们便有y = y ，由此可见，p 越大，就可以允许输 入有更大扰动。如图2 2 所示： 6 第2 章支持向量机的基本理论 ， 图2 2 最大间隔的几何解释 f i g 2 - 2g e o m 酏哕e ) 【p l a n a t i o n so fm a x 证1 i z i n gm a 晒n a l i t y ( b ) 考虑所得决策函数厂( x ) = s 印( ( w 石) + 6 ) 的扰动。一个好的决策函数应该在它 。 、 受到一个不太大的扰动之后，仍然能够正确的划分训练集。最大间隔的原则产生的 决策函数能够承受尽可能大扰动。一种最简单的对决策函数的扰动是超平面的平行 移动，设训练集对某个划分的间隔为p ，显然当划分超平面平移不超过p 时，仍然 能够正确划分，可见用最大间隔原则得到的划分超平面能承受很大干扰。 2 1 4 支持向量分类机 支持向量机两分类问题主要包括三种类型：线性硬间隔分类机、线性软间隔 分类机和非线性硬间隔分类机。设已知训练集丁= ( 而，y 。) ，( 一，j ，m 其中 t r ”，y f 一1 ，1 ) f = 1 ， ( 1 ) 线性可分情况，是指存在一个超平面，可以将两类样本正确划分，在二维空 间示意图如下： 7 北京工业大学理学硕上学位论文 ， 图2 3 线性可分离的示意图 f i g 2 3m es i t l l a t i o no fl i n e a rs 印a r a t i o n 根据2 1 2 中最大化间隔的原则，构造出相应的最优化问题： 纺抓f 2 s j 少f ( ( w x f ) + 6 ) 1 ，i = 1 ， ( 2 - 2 ) 一般通过求解最优化问题( 2 2 ) 的对偶问题来求解，其对偶问题如下： 哮去善蔷y r y ，口r 口，( t 。，) 一蔷口， f s j y f = o 扭l 口f o 扛1 ， ( 2 3 ) 这种方法构造的支持向量机称为线性硬间隔分类机。 ( 2 ) 线性不可分离的一种情况，即不存在超平面，能够把两类点完全正确划分， 但可以近似的分开( 存在错分的，但不严重) ，在二维空间示意图如下： 图2 4 线性不可分离示意图 f i g 2 - 4m es i t u a t i o no fn o n - 1 血e a rs 印a r a t i o n 第2 荦支持向量机的基本理论 凶为，不存在超平面能两类点分开，所以( 1 ) 中的方法行不通，所以我们采取“软 化 间隔的要求，即允许有不满足约束条件y 烈w x ) + 6 ) 1 的点存在，即允许一些 错分的点存在。我们称这样的分类机为：线性软间隔分类机。引入松弛变量 六o ，f = 1 ， 得到软化的约束条件。 y f ( ( w x ) + 6 ) 之1 一鼻，f = l ， 显然，当参充分大时，样本点总可以满足上面的约束条件。但是显然设法避免取 太大的值，为此我们在目标函数里对它进行惩罚，并由此得到下面的最优化问题： 谚帅2 + c 喜鼻 ( 2 - 4 ) j ，y f ( ( w z f ) + 6 ) 1 一点，f = 1 ， 鼻o f = 1 ， 其对偶规划为： i 旁 圭蔷蔷y 册q 口，( tq ，) 一蔷口， ( 3 ) 线性不可分离的另一种情况，二维示意图如下： 图2 5 线性不可分离示意图 f i g 2 5t h es i t u a t i o no fn o n - 1 i n e a rs 印a r a t i o n 9 $ 2 ， = 0 = c q o ，d 为任意整数。 ( b ) g a u s s 径向基核函数k ( x ，x ，) ：e x p ( 一竖二垩) ( c ) 刀维 傅立叶核函数 k ( 石，工) = 兀k 。( t ，石；) 其中 北京工业大学理学硕士学位论文 x=(z。，x：，z，石。)x7=(石：，工：，x；，工：)k。(口，6)=互石f二芝； g 是满足o g 0 ，c 1 1 7 ( 3 - 1 1 ) ) ) ) ) ) 、， 国 柳 q 妨 妨 忉 0 0 0 仔 0 p 北京丁业大学理学硕士学位论文 ( 2 ) 对于支持向量的数据点来说，分两种情况，一种是边界支持向量数据点，此时 口i = c 。 口f = c ：o c 一一白= o j 啦眺( 芝哆k “，t ) + 功一1 + 缶 = o 】 = l q = c ( 3 1 2 ) j 乃( 芝q k ( ，巧) + 功一1 + 毒= o ( 3 _ 1 3 ) 二：置：三- 工”工i ) + 6 ) 一1 + 善f = 。 j y ，。，。工， y l ( y f 口j k ( 工f ，工，) + 6 ) 一1 + 善f = oi f = l j ，f 厂( 工f ) 0 ( 3 - 1 4 ) ( 3 - 1 5 ) ( 3 1 6 ) ( 3 ) 最后，考虑非边界支持向量数据点，此时o 口， c 根据互补松弛条件，有以 下关系成立： 口f y f ( y f a f k ( ，x j ) + 6 ) 一1 + 六 = o o 口f c j y f 厂( 石f ) 1 ( 3 - 1 7 ) 第3 币文持向量机模型的参数选择 o 1 o cjy f g ( x f ) = 1( 3 2 0 ) 口f = cjy f g ( 五) 1 其中非零的口，为支持向量考虑函数g ( x ) = j i l 可知g ( 石) = o 为分类面，g ( x ) = 1 为 分类间隔的边界，其上的样本即为支持向量 定理：3 1 对样本集进行训练得到s v 1 分类器，口为l a g r a n g e 乘子口= 0 对应的样本分 布在分类间隔之外，0 a 1 0 口f cj lg ( t ) l - 1 口f = cj ig ( ) i 1 1 9 ( 3 2 1 ) ( 3 2 2 ) ( 3 - 2 3 ) 北京t 业大学理学硕上学位论文 图3 1s v m 优化问题最有性条件示意图 f i g 3 1t h ei c a k tc o n d i t i o no fs v m 图3 1 是对简化的最优性条件的几何解释，图中和o 分别代表两种类别的样本， 白色样本对应的为零，即非支持向量( y ，厂( t ) 1 ) ，这些向量在分类面的构造中 ，- 不起作用，这些点位于虚线两侧，分别在各自正确的类别一侧；位于虚线上的黑色 样本点是非约束支持向量( y ，厂( ) = 1 ) ，对应的为o 臼， 0 即绝大多数的支持向量穿过分类间隔，属于 错分样本，并称之为间隔错误( m 晒ne 玎o r s ) ，而此时的间隔错误约等分类错误。即 在忽略正确分类的支持向量的情况下，两类各自的错误率可分别表示成 且+ ，尻一，- 其中b + ，置分别为正类和负类的边界支持向量的数量。则在( 4 1 2 ) 式的目标函数中 毋c + ( 儿= 1 ) 2 7 北京工业大学理学硕士学位论文 t _ 1 口i 占一c 一 ( y f = 一1 ) 一j 一、7i 则两类错误率的比值为 设定 b 。c j b c b 。ln 一：b 一| n 一 1 ( c + + ) ：1 ( c 一一) c 一| n 一：c ln + c n c n 一是负类( 多类) 样本数，+ 是正类( 少类) 样本数。 我们将会得到两类各自的分类错误率相近的s 。 然而这种模型增加了问题求解的复杂度，约束的个数有原来的1 个变为2 肘1 个 随着样本个数的增加，问题的复杂度显著增加，本文第五章给出了一个基于有效集法 的支持向量机求解方法。 4 5 本章小结 本章针对传统支持向量机对于样本不均衡数据集的缺点提出了两种分类惩罚的 支持向量机模型，分类惩罚体现在在对偶问题的核函数和约束中，数值实验表明核 函数惩罚模型，分类惩罚效果不明显，对惩罚参数的改变不敏感，而约束惩罚的模 型处理效果比较好。 改进的支持向量机模型的提出解决了传统支持向量机处理不均衡数据集的弊 端，然而模型中有出现了新的参数，这些参数的确定同样会影响支持向量机的性能， 同时改进的支持向量机模型的求解会更复杂。 第五章，我们给出了一种基于有效集法的处理约束体现的分类惩罚支持向量机模 型的有效解法。 2 8 第5 章基于有效集法的改进支持向量机算法 第五章基于有效集法的改进支持向量机算法 s v m 的主要任务是构造并求解一个凸二次规划，传统的支持向量机算法，需要计 算和存储全部样本构造的核函数矩阵。我们知道核函数矩阵大小和训练样本数目的 平方相关，一般来讲当训练样本数目超过4 0 0 0 时，存储核函数矩阵需要多达1 2 8 m 内存。所以当训练样本的规模较大时，就会占用较多的计算机内存，而且求解时间 也会急剧增加，这给求解凸二次规划带来了困难，甚至不能求解。同时本文第四章 中提出的处理不均衡数据集的支持向量机模型中有更多的参数，增加了问题求解的 时间，空间复杂度，本章给出了一种基于有效集法的支持向量机算法，通过动态存 储核矩阵，在一定程度上解决上述问题。基于有效集法的支持向量机算法减少了问 题求解时间空间代价，减少了问题求解的规模，数值试验表明该算法加快了支持向 量机学习的速度，提高了支持向量机处理不均衡数据集时的学习测试精度。 5 1 应用有效集法求解s v m 中的凸二次规划 5 1 1 有效集法求解凸二次规划算法简介 有效集法的基本思想是通过求解有限个等式约束的凸二次规划问题来得到般 约束的凸二次规划问题的最优解。不妨设要求解的二次规划形式如下： ， m ) = 圭x + ，x s a ；x 一包= o a i x 一包o f e f ， 算法( 5 1 ) 如下： ( 1 ) 取初始可行点x n ，即x 1 满足 a i x 1 一6 f = o f e a ；x 忆包o ， f j 确定x ( 1 1 处的有效约束指标集 ，( x 1 ) = f | a ；x n 一包= o ，f ) 北京【业大学理掌坝t 学位论文 置七= 1 ( 2 ) 求解等式约束二次规划问题 面n去d r g d + 夥( x ) r d d 。、7 s j a j d = o ， f eu ，( x ) 得到d ( 。) ( 3 ) 若d = o ，则计算相应的乘子，若4 o ，v f ( x 。) ，则停止计算；否 则求 硝= r n i n 名if ，( x ) ) ， 置，x “1 = x ， ，( x + 1 ) = ，( x 七) 一 g ) ，后二后+ 1 ，转( 2 ) ( 4 ) 若d 0 ，计算 证曲降l 扣地川( x ( 勺) ：丝二型： a ：一 取口 = m i n 俄，1 ) ，置 ， 如果口t = a t ，则置 否则置 置七= 七+ 1 ，转( 2 ) x ( 七+ 1 ) = x ( ”+ 口七d ( n ( x m ) = ，( x 2 ) + 妇) ( x m ) = ，( x 七) 5 1 2 有效集法收敛性定理 设点列x ( 是由算法5 1 1 产生。若算法不是有限终止，则必出现退化的情形。 若算法不出现退化情形，则算法必有限次迭代后终止于二次规划问题的k u h n t u c k e r 点。 5 2 分类惩罚的支持向量模型 通过以上分析可知惩罚因子f 主要是对错分样本进行惩罚。f 的选择与不同类样 第5 章基于有效集法的改进支持向量机算法 本的数量，样本的重要性有很大关系对于数量不均衡和重要性不均衡的数据集，我 们提出对正类和负类样本给予不同惩罚的方法，给出如下支持向量机对偶形式： m i n ! 口r 赢一e r 口m m一口爿口一e 口 口 2 s t y 2 。口= o o 口f c + z z ( 5 1 ) o 口f c f f z 表示正类样本集合f 表示负类样本集合 标准支持向量机模型通常把求解的问题转换为 y o y + y 一 、n匡 = o 转换为含一个约束的最优化问题，而分类惩罚的支持向量机模型( 5 - 1 ) 中含2 力+ 1 个约束条件，这样随着样本数量的增加，问题规模较大，给求解带来很大困难。下 面我们给出基于有效集法求解二次规划的方法。 5 2 1 基于有效集法的支持向量机算法 s 的主要任务是构造并求解二个凸二次规划，传统的支持向量机算法，需要计 算和存储全部样本构造的核函数矩阵。我们知道核函数矩阵大小和训练样本数目的 平方相关，一般来讲当训练样本数目超过4 0 0 0 时，存储核函数矩阵需要多达1 2 8 m 内存。所以当训练样本的规模较大时，就会占用较多的计算机内存，而且求解时间 也会急剧增加，这给求解凸二次规划带来了困难，甚至不能求解。本文针对改进支 持向量机模型约束的特点提出了采用有效集法求解凸二次规划，动态改变核矩阵，较 少存储空间，加快了求解的速度，在一定程度上解决上述问题。 根据凸二次规划( 5 1 ) 的不等式约束的特点：每一个不等式约束中只涉及一个变 量口，( f ，) 而且是边界约束，所以在每步迭代一部分变量取得等式约束，即零或c 值，这样就减小了求解子二次规划的规模。且每步迭代只有一个变量进入或退出等 式约束集，根据这个特点，我们可以动态的改变核矩阵，可以很大程度的减小等式 约束二次规划的规模，下面给出具体算法的过程。 北京t 业大学理学硕上学位论文 设第七次迭代的可行点为口，确定有效约束集的下标集合 ( 口) = 矗i 口p = o ；口r = c + f z ；口r = c f ，) 我们按口( 的值将其分为四个集合 。集口；= o ：+ 集口；= c + ：一集口；) = c 一口( 其余分量为n 集 因此对应规划可转化为求解下面等式约束的二次规划 1 n u n d 2 d o d + d d h 弭ha h + h 。 h 一。h h n hn 一 + h h + - h a h 。qh h h 山h 。h 日o 日+ h j 一 d o d + d d 上式h 。分别对应的是以上四个集合数据间的核函数矩阵向量y 、d 也可进行如上 划分 一i i 、i厂三 ，。知 = o ( 5 2 ) 易知d o = d + = d 一= o = o 。= c + 口，) = c j 。为单位矩阵 因此可得( 5 1 ) 等价规划 毋扣d + + c + + 风一c 一十口牡e h j y j 7 d = o 因此我们给出有效集法的算法描述： 5 2 2 算法描述 。 ( 1 ) 取初始可行点口( n ，即口( 1 满足 y r 口( 1 ) = 0 o 口f ( 1 ) c +y f = 1 0 口f ( 1 ) c y f = 一1 确定口1 处的有效约束指标集 ，( 口1 ) = pi 一口；1 = o ，口；1 = c + ，口j 1 ) = c 一) 置七= 1 1 ( 5 3 ) o+一 口 口 口 口 ，删 o + 一，以乩日 d d d d vii000ioi几 脚 o + - ，纸以乩日 第5 章幕于有效集法的改进支持向量饥算法 ( 2 ) 按( 5 2 ) 中，调整d ，相应地调整日、口、e 7 和y ，然后化简得到小规模的二次 规划( 5 - 3 ) ( 3 ) 求解等式约束的二次规划 母三d o + 矿+ f + 驸一爵h s f y 1d = o( 5 3 ) 得出最优解d 譬 ， ( 4 ) 对应求出d ，若d = o ，则计算求出相应的乘子厶七1 ，丑n ，以n ，g 为分量全 是1 的向量 九= 一( p 一日o + c + 一日。一c 一一o 口n y o 九) = p 一日+ + c + 一日+ 一c + 一日+ _ 口| 一y + 如 九= e h c + 一h c + 一h n n 0 硝一y 一九n 若刃0 ，v f ，( 口) ，则停止计算；否则求 露= 觚n 。if ，( 口七) ) ，置口七十1 = 口n ，j r ( 口“1 ) = ，( 口七) 一铆，按( 5 2 ) 式，调 整d ，相应地调整日、口、p r 和y ，然后化简得到小规模的二次规划( 5 3 ) ，后= 七+ 1 转( 3 ) ( 5 ) 若d ( i ) o ，计算 以= m i i l等d f ( z 等d f ( ， o 取孱= m i n 反，1 ) ，置口“1 = 口+ 反d 。 如果履= 反，则置， m ) = ， ) + p ) p 为反对应的下标否则置，( 口) = ，( 口2 ) 按( 5 1 ) 式，调整d ，相应地调整日、口、p r 和y ，然后化简得到小规模的二次规划 ( 5 3 ) ，置七= 七十1 ，转( 3 ) 3 3 生 一 北京工业大学理学硕十学位论文 有效集法并不是求解二次规划的最优算法，然而我们发现此算法却是求解4 i 均 衡数据集支持向量机模型的有效算法，在此模型中约束较多，核函数较大，传统的 方法需要存贮和计算全部的核矩阵和约束，然而在用有效集法在每次迭代时可以除 去一部分为零的等式约束及变量对应的核矩阵，减小了所求解二次规划的规模，不用 计算全部的核函数矩阵，而是采用核函数分块动态存取的方法，降低了存储空间，提 高了算法的效率，即时问空间复杂度都显著减小。 5 2 3 数值实验 由于数据指标的量纲和取值范围的不同，所得数据分量的取值有时会相差很大， 这样在实际应用中，往往分量较大的因素对分类结果影响较大，分量小的对分类结 果影响较小，但实际中并不是如此。为了避免这种情况的发生，在实际应用中一般 要对数据进行规范化。本文所有给出的数值试验，都用统计标准化的方法对数据进 行了预处理。 统计标准化公式为： 铲高一1 ，2 ， 乩 p 其中，z 和p 为训练样本数目和维数，弓和v a r o ) 为第- ，个变量的平均值和标准差。 实验环境：w i n d o wx p 系统，p 4 ，m a t l a b 6 5 本数值实验的程序是作者在m a t l a b 6 5 下开发的我们给出此算法对数量不均衡 的b a l a n c e s c a l e 数据集和分布特殊的信用数据集训练学习的效果并同标准s 讧算 法的进行比较 ( 实验一) b a l a n c e s c a l e 数据 b a l a n c e s c a l e 数据是心理测验的数据，共有2 类，分别为l “偏左 ，r “偏右。 其中l 类数据2 8 8 个，r 类数据2 8 8 个，我们选取了2 8 8 个l 类数据，1 0 0r 类数据 做训练，随机选6 0 个做测试，样本数据没有缺损实验具体结果见下表 参数设定：高斯核，s i g m a = o 6 两类样本的惩罚参数的选择遵循：罟= 等 第5 章基于有效集法的改进支持向量机算法 表5 一lb a l a n c e s c a l e 数据实验效果比较 方法训练时间参数c正确率支持向量个数 标准s 4 9 5 s4 0 0 9 7 3 7 3 5 l2 5 0 改进的s 5 6 sl 0 0 9 62 2 r7 0 0 参数设定：高斯核，s i 鲫a = o 8两类样本的惩罚参数的选择遵循：= 二二一 ，1 十1r 十 c n 一 表5 2b a l a n c e s c a l e 数据实验效果比较 方法训练时间参数c正确率支持向量个数 标准s 鼯 5 3 6 s4 0 09 6 7 4 l l2 5 0 改进的s 、，m6 2 s9 9 2 8 r7 0 0 ( 实验二) 信用数据 本实验数据来自于德国银行的个人贷款数据库，共1 0 5 0 条记录，每个记录2 4 个指标，信用为g o o d 记录5 0 0 条，b a d 记录5 5 0 条由于正负类样本大量分布于分 类间隔中，而且我们认为将信用为b a d 的误判为g o o d 的和将g o o d 误判为b a d 的具 有错分代价是不同。传统的s v m 方法对此数据集训练学习效果不好，在这里我们 给与b a d 类较大的错分惩罚即减小其错分率我们给出改进后算法的实验结果 随机抽取4 0 0 个作为训练样本，1 5 0 个作为测试数据 高斯核，s i g m a = 3 两类样本的惩罚参数的选择遵循：对b a d 类加大惩罚 表5 3c r e d i t 数据实验效果比较 方法 训练时间 参数c正确率 支持向量个数 标准s v m2 1 0 0 s2 0 0 08 0 6 2 8 1 g o o d2 0 0 0 改进的s 1 3 l s9 6 4 2 2 5 b a d3 0 0 0 高斯核，s i g m a = 1 5 两类样本的惩罚参数的选择遵循：对b a d 类加大惩罚 3 5 北京t 业大学理学硕十学位论文 表5 4c r e d i t 数据实验效果比较 方法训练时间参数c正确率支持向量个数 标准s 2 0 5 0 s3 0 0 08 2 6 2 6 5 g o o d2 0 0 0 改进的s v m1 2 7 s9 8 5 2 1 3 b a d3 5 0 0 5 3 本章小结 本章通过对有效集法的特点以及分类惩罚的支持向量机对应二次规划的 特点进行分析，提出了一种基于有效集法的求解分类惩罚的支持向量机算法 通过算法我们可以看出该算法解决了传统方法中，二次规划求解过程中核矩 阵较大，求解时间长的很多弊端。数值实验表明本算法在时间、存储空间、 预测精度上均优于标准的s v m 算法。 3 6 参考文献 结论 目前，支持向量机理论得到了广泛研究与应用，但在具体实际应用中，于 大规模的训练样本，由存储和计算量的要求，一般的算法往往会失效。 支持向量机参数的选择的是否合适严重影响支持向量机的性能，标准的支 持向量机对于不均衡数据集的不适应性影响着支持向量机的性能。本文从这些 问题入手首先给出了支持向量机参数的定性分析，第四章针对不均衡支持向量 机的问题我们提出了两种分类惩罚的支持向量机模型，即核函数体现的分类惩 罚和约束体现的分类惩罚，使之能更好的处理样本数量不均衡的样本集；针对 约束体现的不均衡支持向量机模型，针对所要求解二次规划约束的特点