（基础数学专业论文）支持向量机反问题及其解法.pdf

摘要 皇薯量尊皇皇_ i i 皇目曼皇皇量皇置宣篁皇_ 摘要 支持向量机是一种新的学习机器，其以统计学习理论为基础，现已被广泛的应用于 模式识别、回归及信号处理等领域，并且取得了良好的学习效果。本文以支持向量机理 论为基础，提出了支持向量机反问题，即是如何将一个事例集分为两部分，才能使这两 部分之间的间隔最大。间隔就是支持向量到分割超平面的距离。但是，对于一个事例集 合，将其划分为两类，并使这两类间的间隔最大，并不是一件容易的事。在本文中我们 使用遗传算法来解决此问题。本文给出了设计原理，计算与实现方法。并通过实例验证 了这种算法的可行性与有效性。这种基于支持向量机反问题的划分方法可以成为决策树 的一种新的启发式算法，使得决策树有较强的强泛化能力。 关键词统计学习理论；支持向量机；超平面；遗传算法 a b s t r a c t j ! _ - _ _ 目_ _ 目_ _ _ - _ 目_ _ l _ _ _ ! 自_ j _ l - | 目_ e _ l _ i l l - _ 自g 目e e l _ - _ _ $ 目_ l _ 目目_ | a b s t r a e t s u p p o r tv e c t o rm a c h i n e ( s v m ) i sn o v e lt y p el e a r n i n gm a c h i n e ，b a s e do ns t a t i s t i c a l l e a r n i n gt h e o r y , w h i c ht a s k si n v o l v i n gc l a s s i f i c a t i o n ，r e g r e s s i o no rn o v e l t yd e t e c t i o n t h i s p a p e ri n v e s t i g a t e s a l li n v e r s ep r o b l e mo fs u p p o r tv e c t o rm a c h i n e s ( s v m o t h ei n v e r s e p r o b l e mi sh o w t os p l i tag i v e nd a t a s e ti n t ot w oc l u s t e r ss u c ht h a tt h em a r g i nb e t w e e nt h et w o c l u s t e r sa t t a i n sm a x i m u m h e r et h em a r g i ni sd e f i n e da c c o r d i n gt ot h es e p a r a t eh y p e r - p l a n a n ds u p p o r tv e c t o r so fs v m s i ti sd i f f i c u l tt og i v ee x a c ts o l u t i o nt o t h i sp r o b l e m i nt h i s p a p e r , w ed e s i g nag e n e t i ca l g o r i t h mt os o l v et h i sp r o b l e m n u m e r i c a ls i m u l a t i o n ss h o wt h e f e a s i b i l i t ya n de f f e c t i v e n e s so ft h i sa l g o r i t h m t h ei n v e r s ep r o b l e mo fs v m sc a l lb e c o n s i d e r e d 硒ah e u r i s t i ct og e n e r a t ed e c i s i o nt r e e sw i t hh i g hg e n e r a l i z a t i o nc a p a b i l i t y k e y w o r d ss t a t i s t i c a ll e a r n i n gt h e o r y ；s u p p o r tv e c t o rm a c h i n e ；h y p e r p l a n e ；g e n e t i ca l g o r i t h m 河北大学 学位论文原创性声明 本人郑重声明： 所呈交的学位论文，是本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知， 除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学位或证书 所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了致谢。 作者签名： 朦乏缈 日期：丛年兰一月主一日 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留并向国 家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。学校可以公布 论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 本学位论文属于 1 、保密口，在年月日解密后适用本授权声明。 2 、不保密仞。 ( 请在以上相应方格内打“”) 作者签名： 导师签名： 日期：丕趔 l 月土日 日期：銎唑年历月l 日 第1 章绪论 1 1 课题来源及意义 第1 章绪论 支撑向量机( s v m ) 理论源于v a p n i k 在1 9 6 3 年提出的用于解决模式识别问题的支持 向量方法，它又是以统计学习理论i u 3 为基础的。统计学习理论是由v a p n i k 等人提出的 针对小样本情况研究统计学习规律的理论。 统计学在解决机器学习问题中起着基础性作用。但是传统的统计学研究的主要是渐 进理论，即样本趋向于无穷多时的统计性质。在现实问题中，我们所面对的样本数目通 常是有限的，有时还十分有限。虽然人们一直知道这一点，但传统上仍以样本数目无穷 多来推导备种算法，希望这样得到的算法在样本较少时也能有较好的( 至少是可接受的) 表现。然而，相反的情况是很容易出现的。其中，近年来经常可以听到人们谈论的所谓 神经网络过学习问题就是一个典型的代表：当样本数有限时，本来很不错的一个学习机 器表现出很差的泛化能力( g e n e r a l i z a t i o n ) 。针对上述问题，出现了统计学习理论。 统计学习理论是传统统计学的重要发展和补充，为研究有限样本情况下机器学习的 理论和方法提供了理论框架，其核心思想是对于一个给定的具有有限数量训练样本的学 习任务，如何在准确性( 对于给定训练集) 和机器容量( 机器可无错误地学习任意训练 集的能力) 进行折衷，以得到最佳的泛化( g e n e r a l i z a t i o n ) 性能。在这理论中发展出 的支持向量机方法是一种新的通用学习机器，较以往方法表现出很多理论和实践上的优 势。已经广泛的被应用于模式识别、信号处理、函数估计及线性方程组的求解等诸多领 域。 本文试图为将s v l d 应用于决策树的生成过程做准备。生成决策树的一般过程是：首 先，将所有训练事例看作树的根节点；然后根据某一启发式信息，将根节点向下划分成 两个子节点，若子节点的事例都属于同一类，则此节点就被认为是一个叶子节点，否则 就一直划分下去，直到出现叶节点。在一般的决策树生成过程中，所用得启发式信息为 最小信息熵。这种方法一般可以得到较小的决策树，且计算复杂度较小，但是其往往不 河北大学理学硕士学位论文 能保证决策树有较好的泛化能力。在本文中，我们提出了一种全新的思想，其以支持向 量机理论为基础，利用其反问题，将一个事例集划分为两部分，且这两类间的间隔最大。 1 2 国内外研究现状 支持向量机是近年来机器学习研究的一项重大成果，根据v a p n i k c h m v o n e n k 的统计学习理论，如果数据服从某个( 固定但未知的) 分布，要使机器的实际输出与理想 输出之间的偏差尽可能小，则机器应当遵循结构风险最小化原理，而不是经验风险最小 化原理，通俗地说就是应当使错误概率的上界最小化。支持向量机正是这一理论的具体 实现，与传统的人工神经网络相比，支持向量机不仅结构简单，而且各种技术性能尤其 是泛化能力明显提高，这已被大量实验证实。 支撑向量机( s v m ) 理论源于v a p n i k 在1 9 6 3 年提出的用于解决模式识别问题的支持 向量方法，现在已经广泛的被应用于模式识别、信号处理、函数估计及线性方程组的求 解等诸多领域。在分类问题上，其中两类分类i 。l 的应用是较成功的。关于多类分类问题， 也已经有了几种方法。这些方法基本上都是将k 类分类问题转化为若干个两类分类问 题。其中最主要的是下列三种方法： ( 1 ) 一对多方法( o a e - a g a i n s t - a 1 1 ) 这是最早的关于解决支持向量机多类分类问题的方 法 ”。它是将k 类分类问题转化成了k 个两类分类问题。其中第i 个分类器是将第i 类 视为一类，其他类视为另一类而构造的分类器。我们将在第2 章详细介绍此方法及以下 两种方法。 ( 2 ) 一对一方法( o n e a g a i n s t - o n e ) ：此思想是将k 类分类问题转化成了k c 砭- 1 ) 1 2 个两 类分类问题i s , g ) 。其中每个分类器都只是由所有训练数据中属于某两类的数据训练而得 的。即对任意两类，都构造一个只针对此两类的分类器。 ( 3 ) 有根非循环图方法a g s v m ) ：此方法的基本思想与o n e - a g a i n s t - o n e 方法一致 只是将k ( i 占】_ 0 ，v 6 0( 2 7 ) 其中，p 表示概率，j i | 。( 国)r ( c o ) 分别表示在n 个样本下的经验风险和对于同一u 的 真实风险。 因为这一定理在统计学习理论中的重要性，被叫做学习理论的关键定理( t h ek e y t h e o r e mo fl e a r n i n gt h e o r y ) 。由于在学习过程中，经验风险和期望风险都是预测函 数的函数( 泛函) ，我们的目的不是用经验风险去逼近期望风险，而是通过求使经验风 险最小化的函数来逼近能使期望风险最小化的函数，因此其一致性条件比传统统计学的 一致性条件更加严格。但是关键定理并没有给出什么样的学习方法满足定理。为此，统 计学习理论定义了一些指标来衡量函数集的性能，其中最重要的是v c 维。 2 2 2 函数集的学习性能与v c 维 1 指示集的熵和生长函数 设有一个指示函数集f ( x ，国) 和一个r 1 个训练样本的样本集 乙= 瓴= ( 五，咒) ，江l ，2 ，甩 考虑函数集的分散性，看函数集中函数能对这组样本实现多少种不同的分类，记这 个数目为( z ) 。 随机熵：指示函数集对某个样本集能实现的不同分类组合数目的对数为函数集在这 个样本集上的随机熵，记作日( 乙) ，即 日( 乙) = i n n ( z ) ( 2 8 ) 第2 章支持向藿机的概念与方法 皇鼻姊i ii 置_ 指示函数集的熵：指示函数集在所有样本数为1 1 的样本集上的随机熵的期望值就叫 做指示函数集的在样本数1 1 上的熵，记作( ，1 ) ，即 h i n ) = e ( 1 nn ( z ) )( 2 9 ) 生长函数：生长函数是在所有可能的样本集上的最大随机熵，记作g ( n ) ，即 g c n ) = l nm ，a xn ( z ) ( 2 i o ) o 2 生长函数的性质与v c 维 定理2 2 所有函数集的生长函数或者与样本数成正比，即 g ( 聍) = n i n 2 ， ( 2 1 1 ) 或者以下列样本数的某个对数为上界，即 g ( 以) ( 1 n 旱+ 1 ) ，n h ， ( 2 1 2 ) 丹 其中h 是一个整数，它是从生长函数满足式( 2 1 1 ) 到满足式( 2 1 2 ) 的转折点，即当 n = h 时，g ( 矗) = h l n 2 而g ( + 1 ) - - j 机器性能和发展新的学习算法的重要基础。 对于指示函数集f ( x ，国) ，如果损失函数q ( z ，c o ) = 三o ，f ( x ，研) 的取值为0 或1 ，则 有如下定理： 定理2 3 对于两类分类问题，对指示函数集中的所有函数，经验风险与实际风险 之间至少以概率1 一r 满足如下关系 r ( ) 尽呷( 国) + 妻；， ( 2 1 3 ) 其中，当函数几种包含无穷多个元素时， ( 孚，塑胁竺兰：! 兰 伍t 4 a ) 而当函数集中包含有限个( n 个) 元素时， 占：21 呈型二幽。 ( 2 1 4 b ) 以 其中，h 为函数集的v c 维。q ，见文献1 1 2 1 。 若损失函数q ( 瓦c o ) 为一般的有界非负实函数。即0 q ( z ，o j ) b ，则有如下结论 定理2 4 对于函数集中的所有函数，下列关系至少以概率1 一r 成立， r ( c o ) ( 小争l + 其中的占仍由( 2 1 4 ) 定义。 ( 2 1 5 ) 由上述两定理我们知道，经验风险最小化原则下学习机器的实际风险是由下面两部 第2 章支持向量机的概念与方法 分组成的： r ( 卯) 也。( 国) + ( 2 1 6 ) 其中，第一部分为训练样本的经验风险，另一部分称作置信范围。也称作v c 信任( v c c o n f i d e n c e ) 。细节见文献 1 2 】。 2 2 4 结构风险最小化 我们已经知道，经验风险最小化原则在样本有限时是不合理的，需要同时最小化经 验风险和置信范围。其实，在传统方法中，选择学习模型和算法的过程，就是优化置信 范围的过程，如果模型比较合适现有的训练样本，则可以获得比较好的效果。但因为缺 乏理论指导，这种选择往往是依赖先验知识和经验进行的，造成某些算法对使用者“技 巧”的过分依赖。统计学习理论提供了另一种方法解决这个问题，就是首先把函数集 s = f ( x ，) eq 分解为函数子集序列， s lc 岛c c 最c c s ( 2 1 7 ) 使各个子集按照v c 维的大小排序，即 l l 如，k ( 2 1 8 ) 这样在同一个子集中置信范围就相同；在每一个子集中寻找最小经验风险，通常随着子 集的复杂度增加而减小。选择最小经验风险与置信范围之和最小的子集，就可以达到期 望风险的最小，这种思想就称为有序风险最小化或者结构风险最小化( s t r u c t u r a lr i s k m i n i m i z a t i o n ) ，简称s 跚原则，如图2 。4 所示。 统计学习理论还给出了合理的函数子集结构应满足的条件及在s r m 原则下，实际风 险收敛的性质 1 , 2 , 1 2 1 。 河北大学理学硕士学位论文 2 3 支持向量机 一n 函数集子集：墨c 是c 墨rv c 维： s 如坞 图2 4 结构风险最小化示意图 统计学习理论是一种专门的小样本学习理论，为研究有限样本情况下的统计识别和 更广泛的机器学习问题建立了一个很好的理论框架，同时也发展了一种新的模式识别方 法一支持向量机，能够较好的解决小样本学习问题。 2 3 1 最优超平面 设有训练数据 可以被一个超平面 ( 五，m ) ，( 而，儿) ，( 一，乃) ，x r ”，ye ( + 1 ，一1 ) ( w z ) 一b = 0 ( 2 。t 9 ) 分开。如果这个向量集合被超平面没有错误的分开，并且离超平面最近的向量与超平面 之间的距离是最大的，则我们说这个向量集合被这个最优超平面( 或最大间隔超平面) 第2 章支持向量机的概念与方法 分开。如图2 5 所示。 o 豳2 5 最优分类超平面是以最大间隔将数据分开的超平 我们使用下面的形式：来描述分类超平面： t ) 一6 l ，弘= 1 ( 葺) 一b 一1 ，咒= 一1 并且有紧凑形式： m 【( x i ) - b 】1 ，j = 1 ，2 ， ( 2 2 0 ) 容易验证，最优超平面就是满足条件( 2 2 0 ) 并且使得 ( ) = 9 国l | 2 ( 2 2 1 ) 最小化的超平面【“。并且通过解决下述优化问题来构造最优超平面： m i n 西( ) ：妻( ) ， s u b ) e c tt o 儿 ( x , ) - b 1 ，f - 1 ，2 ， 最优超平面是在线性可分的前提下讨论的，在线性不可分的情况下，可以在条件中 加入一个松弛变量磊o ，这时的最优超平面称为广义最优超平面，通过解决如下问题 得到： 河北大学理学硕士学位论文 11 m i n m ( 国) = 去( 彩) + c ( 岳) ， 厶 f 。l s u b j e c t t o 咒【( 国x f ) - b 】l 一点，i = l ，2 ，。 2 3 2 支持向量机 支持向量机的定义如下1 1 】：支持向量机通过某种事先选择的非线性映射将输入向量 x 映射到一个高维特征空间z ，在这个高维特征空间中构造最优分类超平面。如图2 6 。 o o oooooo o 0 展开成 第2 章支持向量机的概念与方法 充分必要条件是，对使得 的所有g 0 ，条件 k ( u ，= q o ( 址o ( 而) r = l 9 2 ( “) a u 0 成立。 核函数一般有下面三种形式： 多项式核函数：足( 工，玉) _ ( 舻五) + l 】d 径向基核函数：k , ( 1 l x x , 1 1 ) = e x p - r l l x 一引2 ) ，其中r 为常数。 ( 2 2 3 ) 两层神经网络核函数：x ( x ，而) = s u ( x 而) + c 】，其中，u 为常数，s 为s i g m o i d 函数。 上述定理称为m e r c e r 定理，这样就解决了处理高维空间的技术问题。那么我们可以利 用核函数在输入空间中构造非线性决策函数 ， ，( 砷= s g n ( 只q 芷“，x ) - b ) ， l - l ( 2 2 4 ) 它等价于高维特征空间中线性决策函数。在可分情况下，要求的系数哦，只要求下述优 化问题1 1 1 ： m a x ( 口) ：杰q 一妻圭a i a y y j k ( ，_ ) i - ljj - 1 s u b j e c t t o q m = o ，嘶 - 0 ，i = 1 2 1 构造支持向量机的复杂程度依赖于支持向量的个数，而与特征空间的维数无关。图 2 7 是一个两层支持向量机示意图。 河北大学理学硕士学位论文 决策规则 x lx 2 2 4 支持向量机分类 ) 一b ) 的非线性变换 x n 输入向量p x ，一) 雷2 7 两层支持向量帆 现在，支持向量机已经被广泛的应用于模式识别、信号处理、函数估计及线性方程 组的求解等诸多领域。基于本文的需要，我们简要介绍一下支持向量分类。支持向量分 类包含两类分类问题与多类分类问题。根据本文需要，我们对两类分类问题作一简单介 绍。s v m 最早应用于两类分类问题，现在这方面的理论已经较为成熟，并且在应用中 也得到了较好的结果。 现简单介绍如下：设有训练集 ( x l ，y 1 ) ，( x 2 ，娩) ，( x l ，y 1 ) x r ”y - 1 ，1 ) ， s v m 解决如下优化问题： m i n 。 f 妻( 国国) + c 壹毒 l=l s u b j e c tt o ( c o o ( t ) ) + 6 1 一毒矿咒= 1 ( 中( ) ) + 6 - - l + 善j fy j = 一l 毒0 ，i = l ，2 ，。， 其中，中为某个非线性映射，c 为惩罚系数，毒为松弛变量【”。 上面优化问题的解是由下面的拉格朗日函数的鞍点给出的： 第2 章支持商量机的概念与方法 l ( c o ，f ，b ，口，卢) = 了1 ( c o ) + c ( f ，) ，；l ( 2 2 5 ) 其中q ，屏为拉格朗日乘子。我们需要把拉格朗日函数关于，b ，孝求y ；：l d , f f i ，并且关于 q 0 求其最大值。关于w , b 求其最小值时，w , b ，善须满足下列条件 于是我们有： ol(co,善,b,ct,f1)：珊一1嘶m。(葺)：0009 l 一= l o l ( _ c o , 古广, b , a , f 1 ) ：一圭哪：o 曲 i=l 堂掣：c 一一届：o d 亡 仅i + a = c 将式( 2 ，2 6 ) 代入式( 2 2 5 ) ，并考虑至4 式( 2 2 7 ) ，有： ，1l ， 形 ) = q 一言乃乃q 吩k ( 薯，_ ) i = 1i - l1 = 1 并且满足下面的约束条件： 0 啦c ，i = l ，2 ，l q 咒= 0 i = 1 f 2 2 6 ) 佗2 7 ) ( 2 2 8 ) f 2 2 9 ) 我们通过解决在式( 2 2 9 ) 条件下最大化式( 2 2 8 ) 这个二次优化问题，就构造出了最优超平 面。即得到了一个决策函数( 分类器) ： 声， ， 一 ) 卢， +i 一 、j 6+ ) x ( o 缈 “ y( 口 ， 一 、j 西 ，l m m留 ，闰 = 缈 o = m嘶 ； 河北大学理学硕士学位论文 ， f ( x ) - - s g n ( 只嚷。足( 玉，工) 一b o ) 。 ( 2 3 0 ) f = l 其可对新样本进行预测。理论与实验证明，分类器较之神经网络与决策树有更强的推广 能力。 第3 章遗传算法简介 第3 章遗传算法简介 3 1 遗传算法思想的提出 生物在自然界中的生存繁衍，显示出其对自然环境的优异自适应能力。受其启发， 人们致力于对各种生存特征的机理研究和行为模拟。为人工自适应系统的设计和开发提 供了广阔的前景。遗传算法就是这种生物行为的计算自模拟中令人瞩目的重要成果。基 于对生物遗传和进化过程的计算机模拟，遗传算法使得人工系统具有优良的自适应能力 和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。虽然人们还没有完 全揭开遗传和进化的奥秘，但遗传和进化以下的几个特点却为人们所共识【2 1 】： ( 1 ) 生物的所有遗传信息都包含在其染色体中。 ( 2 ) 染色体是由基因及其有规律的排列所构成的，遗传和进化的过程发生在染色体 上。 ( 3 ) 生物的繁殖过程是由其基因的复制过程来完成的。 ( 4 ) 通过同源染色体的交叉豁然染色体的变异会产生新的物种 ( 5 ) 对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会 遗传到下一代。 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优 化概率搜索算法。他最早由美国密执安大学的h o l l a n d 教授提出，起源于6 0 年代对自然 和人工自适应系统的研究。7 0 年代d ej 0 n g 基于遗传算法的思想在计算机上进行了大量 的纯数值函数优化计算试验，在一系列研究工作的基础上，8 0 年代由g o l d b o r g 进行归 纳总结，形成了遗传算法的基本框架。 3 2 基本遗传算法描述 基于对自然界中生物遗传于进化机理的模仿，针对不同的问题，很多学者设计了许 多不同的染色体编码方法来表示问题的可行解，开发出了许多不同的遗传算子来模仿不 同环境下的生物遗传特性。这样，由不同的编码方法和不同的遗传算子就构成了不同的 河北大学理学硕士学位论文 遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交 叉、变异机制的模仿，来完成对问题最优解的自适应搜索过程。基于这种共同特点， g o l d b e r g 总结出了一种统一的最基本的遗传算法基本遗传算法【1 9 1 。基本遗传算法 只使用遗传算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单， 容易理解，是其他一些遗传算法的雏形和基础，他不仅给各种遗传算法提供了一个基本 框架，同时也具有一定的应用价值。 3 2 1 基本遗传算法的构成要素 ( 1 ) 染色体编码方法。基本遗传算法使用固定长度的二进制符号串来表示群体中的 个体，其等位基因是由二值符号集 0 ，1 ) 所组成的。初始群体中各个个体的基因值可 用均匀分布的随机数来生成。如： x = 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1 就可以表示一个个体，该个体的染色体长度是n = 1 8 。 ( 2 ) 个体适应度评价。基本遗传算法按与个体适应度成正比的概率来决定当前群体中 每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的 适应度必须为正数或零。这样，根据不同种类的问题。必须预先确定好由目标函数值到 个体适应度之间的转换规则，特别是要预先群定好当目标函数值为负数时的处理方法。 ( 3 ) 遗传算子。 选择运算使用比例选择算子； 交叉运算使用单点交叉算子： 变异运算使用基本位变异算子或均匀变异算子； ( 4 ) 基本遗传算法的运行参数。基本遗传算法由下述4 个运行参数需要提前设定： m ：群体大小，即群体中所含个体的数量。 t ：遗传运算的终止进化代数。 p 。：交叉概率。 p 。：变异概率。 2 0 第3 章遗传算法简介 需要说明的是，这4 个运行参数对遗传算法的求解结果和求解效率都有一定的影响， 但目前尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试 算后才能确定出这些参数合理的取值大小或取值范围。 3 2 2 基本遗传算法描述 利用遗传算法解决多变量优化问题过程如下，图3 1 为算法流程图： 1 确定染色体的编码机制，来表示优化问题的解。 2 基于编码机制，初始化染色体，即得到初始代种群 3 确定中群众所有染色体的适应度函数，一般取值在【o ，1 】。 4 在当前种群中，依据适应度函数选择父代染色体。 5 两个父代染色体通过互换部分基因，即通过交叉算子，得到相应的子代染色体。 6 执行变异算子，即改变子代染色体的部分基因。 7 将所有的子代染色体放在一起，构成了下一代种群。 8 检查终止条件是否满足，如果满足，则终止程序，否则，进入步骤4 。 河北大学理学硕士学位论文 _ i _ _ 图3 1 基本遗传算法过程 2 2 第4 章支持向量机反问题及其解法 4 1 问题描述 第4 章支持向量机反问题及其解法 对于一个无导师信息的事例集合，可以被随机的划分为两部分。我们可以运用s v m 得到将这两个事例子集无错误分开的超平面及其间隔。若其线性不可分，则分类间隔为 0 。显然，对事例集合不同的划分，会对应不同的间隔，那么怎样才能得到具有最大间 隔的划分呢? 这是一个优化问题，其数学描述如下：设s = ，屯，h ) 是一个包含个事例的 集合且葺r “i = 1 ，2 ，n ，q = ，i ，：s 一 1 ，一1 。任给一函数厂q ，其可将 s 分为两部分，且按照前面的方法，得到相应的间隔。我们用m a r g i n ( f ) 泛函) 来表示 某一函数所对应的间隔。从而反问题可如下表示 m a x i m u m i 。n ( m a r g i n ( ) ) ) ( 4 1 ) 由于此优化问题的复杂度以指数级增加，从而枚举出q 中所有函数，来寻求有最大间隔 的划分是不现实韵，而且目前也无法找到一个求解问题( 4 1 ) 的严格算法。所以求出其 近似最优解或满意解就成为我们的着眼点。本文中提出利用遗传算法来求解问题( 4 1 ) 。 4 2 问题求解算法 这里，我们基于第3 章的知识，设计一个遗传算法来解决问题( 4 1 ) ，即s v m 反问 题。 s t e p l 确定染色体编码机制。每一个f q 对应于事例集s 的一个划分，从而，可 以用一个维向量来表示，如：1 0 1 1 0 1 0 0 1 0 1 0 1 1 ，其每一个基因只取0 或1 ，对应于 s 中的一个事例。某一位基因取1 ，表示相应事例为正类，反之为负类。这样，由个 基因构成的一个染色体就表示了q 中的某一函数。染色体长度为固定值 即s 中的事 、羽北大学理学硕士学位论文 例个数。 s t e p 2 确定种群规模，生成初始代。即预先选择每一代个体的数量肌生成个取 值为0 或1 的随机数，构成一个染色体，并重复这样的过程次。得到个染色体。 s t e p 3 确定适应度函数。每一染色体，可对应于一个两类分类问题的训练集。我们 运用s v m 得到对应于这一训练集的间隔，并将每一染色体的适应度函数值定义为这个间 隔。 s t e p 4 复制。在这一过程中，染色体根据其适应度值，被复制到下一代。这一过程 一般是通过轮盘赌原理实现的。即每个染色体被复制倒下一代的概率正比于其适应度 值。其执行过程如下： ( 1 ) 设种群为 l ，2 ，盯) ，且厂表示第j 个个体的适应度值。计算 s ，= ：。，( 州f = 1 ，2 ，肘) ( 2 ) 按照均匀分布，在 o ， 范围内，生成一个随机数n 。 ( 3 ) 复制第七个个体到培养池中，其满足j 。 口。 通过复制，仅仅是得到了下一代的个候选个体。并且我们假设这其中包含上一代 中具有最大适应度值的个体( 若没有，我们可以人为的加入) 。 s t e p 5 交叉。复制过程结束后，使得培养池中含有个候选父代个体，通过随机搭 配，形成 彰2 对父代个体。交叉以概率p 。发生在每一对父代个体之间，染色体交叉 位随机生成。通过交叉算子，生成了 州2 对子代个体，即膨染色体。 s t e p 6 变异。其使得每一子代染色体的某个基因被其他基因以概率p ，取代，且此基 因是随机选择的。村父代个体及其个子代个体形成了一个包含2 5 个染色体的集合。 我们从这个染色体集合中选择前彤个有最大适应度值的染色体，来形成下一代个体。 s t e p 7 预先确定的最大繁衍代数t ，作为算法的终止条件。若当前繁衍代数小于t ， 则进入步骤4 ；否则进入步骤8 。 s t e p 8 按照个体适应度值由大至小对所有染色体进行排序，且输出第一个染色体及 其适应度值。根据此染色体基因所表示的意义，事例集s 被划分为两部分，即聚为两类， 2 4 第4 章支持向量机反问题及其解法 墨i il li 皇目摹自| | 蔓自 其间隔就是此染色体的适应度值。 若我们用 五，屯，h ) 表示事例集合，t r 4 ，i = l ，2 ，n n 为布尔向量 c = c t t a ：被视为一个染色体，( - ，) 表示第个个体的适应度值。r a n d o m ( a ) 表示服 从 o ，a 上均匀分布的随机数，腧a 、p 。及儿分别表示最大繁衍代数、种群规模、 交叉概率和变异概率。算法流程如图4 1 所示。 4 3 仿真试验 为了验证本文所提出方法的有效性，我们构造了5 个二维数据集，信息可参见表 4 1 ，并利用基于s v m 反问题将其划分类两类，程序中的相关参数见表4 2 ，划分结果如 图1 至5 所示。 表4 1 ：数据集信息及其划分结果 数据集事例数间隔运行时间( 秒) 最优染色体 11 00 3 2 9 85 2 8 4 3 0 0 0o l l l l l l l l l 22 00 1 2 6 11 3 1 0 3 20 1 1 0 1 0 0 l o l 0 1 1 0 1 1 0 0 0 0 33 00 0 9 1 33 0 9 5 3 2 01 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 44 00 0 5 6 75 1 0 0 7 8 1 1 0 0 1 l l l l l l l l l l l l 0 0 l l l l l 0 0 1 0 0 1 1 1 1 0 0 1 0 0 0 0 1 1 1 1 1 55 00 0 5 8 21 0 8 4 0 3 l o 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 1 1 1 1 表4 2 ；程序参数 程序参数意义 p o p s l 7 e = 1 0 0 ；种群规模 p c = 0 8 ；交叉概率 p m = 0 _ 3 ： 变异概率 n b = 0 3 ：染色体中变异基因的比例 g - - 0 6 ： 代沟 m a x g e n e r a t i o n - - 4 0 ； 最大繁衍代数 k e r = q i n e a r ； s v m 核函数类型 河北大学理学硕士学位论文 一i i 置_ 一 i n i f i a l i z a l i o n ：a 蝴- 而，屯，h , c h o m o s o m e c = a l a 2 口，巧乜l c s s ，r a i l d 。mn u m b e r i n o , a + r ( a s p e c i f y c o 呻鹏m m n g , 只，a n d 以 t t 啦g 蜘啊b m c i l n o t i l 镐，c = q 口，口 i = l ，2 ，m f o r ，。it om d o l x k r m i n t “，m k k ，儿) ，( h ，妇) f o , q a c q u i r c a l 1 = 1 i ，2 - ，n 。6 口a n dw 埘 c h a p t c r 2 ；i f 片( w x , - b ) a t ；i = l 2 ，nt h e n ，( q ) ；( w w ) - 1 y l s e ，( q ) ；o f o r ，。1 i 。m d o s j = 弓i “) 0 = 1 , 2 ，- 一，。 ，) ，口；尺( 互”) d f = q 汀耳d 口主 畦= 气寥坤f ( i o ) = m 栈l # ，t m ，( ) t r a n d o m l ys e l e c t i o 5 m p , + 1p 耵碡( 4 ，嘭) tt 掌【r ( m 一1 ) 卜1 一；自i 自n 】自m i ) ”d 嘭= 屯l 屯i u q n 珥= 4 n 。 q o m 蚧”8 一= 1 一屯n k 4 “) r a n d o m l ys e l e c tf 岣卜id 吐a n dr a n d o m l yc h a n g en bb i t s f o r l = l t o m d o 聃i i i i e x l , x 2 ，h f o d , ，a c q u i r e 口j i i = 1 ，2 ，l ，6 0a n d b yc h a p t c r 2 ； 咒( w 一6 ) 1 ；f ；l 2 ，nt h e n ，( 珥) ；( w w ) - ，e l s e 厂( 西) = o ) s o r t i n g ，如) ，( t x j = l 2 ，m ) f r o mb i g ws m a l l ，蚍d t h e n s e l e c t i n g t h e 眦m c 啪m m = 1 , 2 ，。 + _ 一一n ，球t c m 帕tl ，e s n b上 o i i t l m ( c i ，f “) ) s t o p 图4 1s v m 反问题的流程图 2 6 - 第4 章支持向量机反问题及其解法 圈4 1 事例集l 划分结果 图4 3 事例集3 划分结果 图4 , 5 事例集5 划分结果 图4 2 事例集2 划分结果 图4 4 事例集4 划分结果 从实验结果来看，通过本文所提出的方法，可以将一数据集划分为例两部分，即划 分为两类。虽然间隔并不是最大，但应该是满意解。 下面，为了进一步验证此算法的有效性，我们构造一个含有2 0 个事例的2 维数据 集( 如表4 3 ) ，其空间分布如图4 6 。我们用枚举法与g a 方法分别在原始空间与特征空 间中对这组数据进行测试。其中g a 算法中的参数设定见表4 。 - 2 7 - 河北大学理学硕士学位论文 墨墨一i 量邕鼻- 表4 3 ：数据集信息 事例特征1特征2事例特征i特征2 l0 4 2 80 0 6 41 10 1 20 5 5 2 20 4 1 60 0 8 21 20 1 50 5 3 30 3 8 80 0 9 81 30 1 2 80 5 6 2 40 4 4 40 1 21 40 0 90 5 9 2 5 0 4 6 80 0 9 21 50 1 7 40 5 8 60 7 6 20 2 7 2 1 6 0 4 6 60 7 8 6 70 7 8 40 3 0 21 70 4 4 20 ，8 0 2 8 o 7 50 3 1 41 80 4 3 80 7 6 4 90 7 2 80 2 7 21 90 5 0 20 7 4 2 1 0o 7 1 20 3 3 22 00 4 8 20 8 2 自岍 图4 6 样本空间分布 表4 4 ：g a 算法中的参数 p o p s i z e - - 1 5 0 ：种群规模 p c = o 7 ； 交叉概率 p m = o 8 ：变异概率 n b ：o 3 ：染色体中变异基因的比例 g = o 6 ：代沟 姒x g e n e i m i o n = 2 0 ：最大繁衍代数 - 2 8 - 第4 章支持向量机反问题及其解法 其中p m 为0 v ，此值设置较大，其目的是用来增强g a 中变异的作用，用以产生更多的 新染色体寄希望于出现更优秀的个体。这样可以加快种群进化速度，提高算法的效率。 原始空间中的测试结果见表5 、枚举法的最大与次大间隔超平面如图4 7 、图4 8 所示， g a 方法得到的最大与次大间隔超平面如图4 9 、4 1 0 所示。 表5 原始空间中的铡试结果 圈4 7 枚举法最大间隔超平面图4 8 枚举法次大间隔超平面 图4 9g a 最大间隔超平面图4 1 0g a 次大间隔超平面 通过上述实验结果可以看出，g a 方法比枚举法运行时间要少得多。由于g 是在完全空 间上的不完全搜索。所以其不能保证必能得到最大间隔超平面，但其优势在于能迅速得 到一个较满意的结果若要提高g a 方法得到最大间隔超平面的概率，可以通过增加参 数p o p s i z e 与m a x g e n e r a t i o n 的大小来实现，但这必将以牺牲程序的运行时间为代价。 我们选择3 阶多项式核函数，其他参数不变，对前面的2 0 个点重复进行试验，实 验结果如下： 从上述实验结果来看，在特征空间中，最大间隔和次大间隔分类情况与原始空间中 相同。遗传算法仍很快得到了最大间隔超平面。虽然我们不能保证g a 每次都能得到最 大间隔超平面，但是g a 可以在很短的时间内得到一个较满意的结果。 表6 特征空间中的测试结果 图4 11 枚举最大间隔超平面 图4 1 2 枚举次大间隔超平面 图4 1 3g a 最大间隔超平面 圈4 1 4g a 次大间隔超平面 一一 第4 章支持向量机反问题及其解法 _ _ _ _ _ _ _ _ _ _ - _ _ 自_ _ _ _ _ _ 自| - _ _ _ _ _ _ _ _ - _ _ _ _ - _ _ i _ - _ _ _ _ i l _ _ - _ _ 为了进一步并分析数据库规模与程序运行时间的关系，我们使用来自u c i 的i r i s 数据库进行测试。由于第l 类与2 、3 类线性可分，我们只选择其中属于2 类与3 类的 i 0 0 个事例。每次都是重新从所有事例中随机抽取样本，从5 个样本开始，每次递增5 个，直到全部的1 0 0 个样本，对这2 0 种情况分别用本文方法进行测试。其中，我们仍 选择3 阶多项式核函数，其他参数不变。实验结果如下； 图4 1 5 样本个数与程序运行时间的关系 表7 i r i s 数据库( 2 类与3 类) 测试结果 事例数时间( 分) 事例数时间( 分) 5 0 4 2 9 4 35 52 5 4 5 5 l o o 9 0 2 4 76 03 0 9 2 5 1 5 1 7 7 7 26 53 6 7 9 3 2 03 3 7 0 87 0 4 2 8 3 2 2 5 5 4 3 3 77 55 0 6 4 9 3 07 2 1 4 48 05 9 0 3 6 3 5l o 0 1 38 56 7 5 0 8 4 01 2 9 6 9 0